Search

This paper introduces a novel optimization framework for deep neural network (DNN) hardware accelerators, enabling the rapid development of customized and automated design flows. More specifically, our approach aims to automate the selection and configuration of low-level optimization techniques, encompassing DNN and FPGA low-level optimizations. We introduce novel optimization and transformation tasks for building design-flow architectures, which are highly customizable and flexible, thereby enhancing the performance and efficiency of DNN accelerators. Our results demonstrate considerable reductions of up to 92\% in DSP usage and 89\% in LUT usage for two networks, while maintaining accuracy and eliminating the need for human effort or domain expertise. In comparison to state-of-the-art approaches, our design achieves higher accuracy and utilizes three times fewer DSP resources, underscoring the advantages of our proposed framework., Comment: 5 pages, Accepted at FPL'23

Recent advances in algorithm-hardware co-design for deep neural networks (DNNs) have demonstrated their potential in automatically designing neural architectures and hardware designs. Nevertheless, it is still a challenging optimization problem due to the expensive training cost and the time-consuming hardware implementation, which makes the exploration on the vast design space of neural architecture and hardware design intractable. In this paper, we demonstrate that our proposed approach is capable of locating designs on the Pareto frontier. This capability is enabled by a novel three-phase co-design framework, with the following new features: (a) decoupling DNN training from the design space exploration of hardware architecture and neural architecture, (b) providing a hardware-friendly neural architecture space by considering hardware characteristics in constructing the search cells, (c) adopting Gaussian process to predict accuracy, latency and power consumption to avoid time-consuming synthesis and place-and-route processes. In comparison with the manually-designed ResNet101, InceptionV2 and MobileNetV2, we can achieve up to 5% higher accuracy with up to 3x speed up on the ImageNet dataset. Compared with other state-of-the-art co-design frameworks, our found network and hardware configuration can achieve 2% ~ 6% higher accuracy, 2x ~ 26x smaller latency and 8.5x higher energy efficiency.

This article presents XGB-Chiarella, a powerful new approach for deploying agent-based models to generate realistic intra-day artificial financial price data. This approach is based on agent-based models, calibrated by XGBoost machine learning surrogate. Following the Extended Chiarella model, three types of trading agents are introduced in this agent-based model: fundamental traders, momentum traders, and noise traders. In particular, XGB-Chiarella focuses on configuring the simulation to accurately reflect real market behaviours. Instead of using the original Expectation-Maximisation algorithm for parameter estimation, the agent-based Extended Chiarella model is calibrated using XGBoost machine learning surrogate. It is shown that the machine learning surrogate learned in the proposed method is an accurate proxy of the true agent-based market simulation. The proposed calibration method is superior to the original Expectation-Maximisation parameter estimation in terms of the distance between historical and simulated stylised facts. With the same underlying model, the proposed methodology is capable of generating realistic price time series in various stocks listed at three different exchanges, which indicates the universality of intra-day price formation process. For the time scale (minutes) chosen in this paper, one agent per category is shown to be sufficient to capture the intra-day price formation process. The proposed XGB-Chiarella approach provides insights that the price formation process is comprised of the interactions between momentum traders, fundamental traders, and noise traders. It can also be used to enhance risk management by practitioners., Comment: Published in WILMOTT Magazine: May 2022 issue. arXiv admin note: text overlap with arXiv:2208.13654

This paper describes simulations and analysis of flash crash scenarios in an agent-based modelling framework. We design, implement, and assess a novel high-frequency agent-based financial market simulator that generates realistic millisecond-level financial price time series for the E-Mini S&P 500 futures market. Specifically, a microstructure model of a single security traded on a central limit order book is provided, where different types of traders follow different behavioural rules. The model is calibrated using the machine learning surrogate modelling approach. Statistical test and moment coverage ratio results show that the model has excellent capability of reproducing realistic stylised facts in financial markets. By introducing an institutional trader that mimics the real-world Sell Algorithm on May 6th, 2010, the proposed high-frequency agent-based financial market simulator is used to simulate the Flash Crash that took place that day. We scrutinise the market dynamics during the simulated flash crash and show that the simulated dynamics are consistent with what happened in historical flash crash scenarios. With the help of Monte Carlo simulations, we discover functional relationships between the amplitude of the simulated 2010 Flash Crash and three conditions: the percentage of volume of the Sell Algorithm, the market maker inventory limit, and the trading frequency of fundamental traders. Similar analyses are carried out for mini flash crash events. An innovative "Spiking Trader" is introduced to the model, aiming at precipitating mini flash crash events. We analyse the market dynamics during the course of a typical simulated mini flash crash event and study the conditions affecting its characteristics. The proposed model can be used for testing resiliency and robustness of trading algorithms and providing advice for policymakers.

In this work, we present a hardware compatible neural network training algorithm in which we used alternating direction method of multipliers (ADMM) and iterative least-square methods. The motive behind this approach was to conduct a method of training neural networks that is scalable and can be parallelised. These characteristics make this algorithm suitable for hardware implementation. We have achieved 6.9\% and 6.8\% better accuracy comparing to SGD and Adam respectively, with a four-layer neural network with hidden size of 28 on HIGGS dataset. Likewise, we could observe 21.0\% and 2.2\% accuracy improvement comparing to SGD and Adam respectively, on IRIS dataset with a three-layer neural network with hidden size of 8. This is while the use of matrix inversion, which is challenging for hardware implementation, is avoided in this method. We assessed the impact of avoiding matrix inversion on ADMM accuracy and we observed that we can safely replace matrix inversion with iterative least-square methods and maintain the desired performance. Also, the computational complexity of the implemented method is polynomial regarding dimensions of the input dataset and hidden size of the network.

In this project, we have successfully designed, implemented, deployed and tested a novel FPGA accelerated algorithm for neural network training. The algorithm itself was developed in an independent study option. This training method is based on Alternating Direction Method of Multipliers algorithm, which has strong parallel characteristics and avoids procedures such as matrix inversion that are problematic in hardware designs by employing LSMR. As an intermediate stage, we fully implemented the ADMM-LSMR method in C language for feed-forward neural networks with a flexible number of layers and hidden size. We demonstrated that the method can operate with fixed-point arithmetic without compromising the accuracy. Next, we devised an FPGA accelerated version of the algorithm using Intel FPGA SDK for OpenCL and performed extensive optimisation stages followed by successful deployment of the program on an Intel Arria 10 GX FPGA. The FPGA accelerated program showed up to 6 times speed up comparing to equivalent CPU implementation while achieving promising accuracy.

In the near future FPGAs will be available by the hour, however this new Infrastructure as a Service (IaaS) usage mode presents both an opportunity and a challenge: The opportunity is that programmers can potentially trade resources for performance on a much larger scale, for much shorter periods of time than before. The challenge is in finding and traversing the trade-off for heterogeneous IaaS that guarantees increased resources result in the greatest possible increased performance. Such a trade-off is Pareto optimal. The Pareto optimal trade-off for clusters of heterogeneous resources can be found by solving multiple, multi-objective optimisation problems, resulting in an optimal allocation of tasks to the available platforms. Solving these optimisation programs can be done using simple heuristic approaches or formal Mixed Integer Linear Programming (MILP) techniques. When pricing 128 financial options using a Monte Carlo algorithm upon a heterogeneous cluster of Multicore CPU, GPU and FPGA platforms, the MILP approach produces a trade-off that is up to 110% faster than a heuristic approach, and over 50% cheaper. These results suggest that high quality performance-resource trade-offs of heterogeneous IaaS are best realised through a formal optimisation approach., Comment: Presented at Second International Workshop on FPGAs for Software Programmers (FSP 2015) (arXiv:1508.06320)

In partially reconfigurable architectures, system components can be dynamically loaded and unloaded allowing resources to be shared over time. This paper focuses on the relation between the design options of partial reconfiguration modules and their placement at run-time. For a set of dynamic system components, we propose a design method that optimizes the feasible positions of the resulting partial reconfiguration modules to minimize position overlaps. We introduce the concept of subregions, which guarantees the parallel execution of a certain number of partial reconfiguration modules for tiled reconfigurable systems. Experimental results, which are based on a Xilinx Virtex-4 implementation, show that at run-time the average number of available positions can be increased up to 6.4 times and the number of placement violations can be reduced up to 60.6%.

Additional file 1 SupplementaryData.pdf is available online, and contains all additional data referenced in the main text.

Additional file 1 SupplementaryData.pdf is available online, and contains all additional data referenced in the main text.

In this thesis, we explore alternative architectures for implementing con_gurable Data Center Switches along with the advantages that can be provided by such switches. Our first contribution centers around determining switch architectures that can be implemented on Field Programmable Gate Array (FPGA) to provide configurable switching protocols. In the process, we identify a gap in the availability of frameworks to realistically evaluate the performance of switch architectures in data centers and contribute a simulation framework that relies on realistic data center traffic patterns. Our framework is then used to evaluate the performance of currently existing as well as newly proposed FPGA-amenable switch designs. Through collaborative work with Meng and Papaphilippou, we establish that only small-medium range switches can be implemented on today's FPGAs. Our second contribution is a novel switch architecture that integrates a custom in-network hardware accelerator with a generic switch to accelerate Deep Neural Network training applications in data centers. Our proposed accelerator architecture is prototyped on an FPGA, and a scalability study is conducted to demonstrate the trade-offs of an FPGA implementation when compared to an ASIC implementation. In addition to the hardware prototype, we contribute a light weight load-balancing and congestion control protocol that leverages the unique communication patterns of ML data-parallel jobs to enable fair sharing of network resources across different jobs. Our large-scale simulations demonstrate the ability of our novel switch architecture and light weight congestion control protocol to both accelerate the training time of machine learning jobs by up to 1.34x and benefit other latency-sensitive applications by reducing their 99%-tile completion time by up to 4.5x. As for our final contribution, we identify the main requirements of in-network applications and propose a Network-on-Chip (NoC)-based architecture for supporting a heterogeneous set of applications. Observing the lack of tools to support such research, we provide a tool that can be used to evaluate NoC-based switch architectures. Open Access

This thesis seeks to improve low latency application performance via architectural improvements in reconfigurable devices. This is achieved by improving resource utilisation and access, and by exploiting the different environments within which reconfigurable devices are deployed. Our first contribution leverages devices deployed at the network level to enable the low latency processing of financial market data feeds. Financial exchanges transmit messages via two identical data feeds to reduce the chance of message loss. We present an approach to arbitrate these redundant feeds at the network level using a Field-Programmable Gate Array (FPGA). With support for any messaging protocol, we evaluate our design using the NASDAQ TotalView-ITCH, OPRA, and ARCA data feed protocols, and provide two simultaneous outputs: one prioritising low latency, and one prioritising high reliability with three dynamically configurable windowing methods. Our second contribution is a new ring-based architecture for low latency, parallel access to FPGA memory. Traditional FPGA memory is formed by grouping block memories (BRAMs) together and accessing them as a single device. Our architecture accesses these BRAMs independently and in parallel. Targeting memory-based computing, which stores pre-computed function results in memory, we benefit low latency applications that rely on: highly-complex functions; iterative computation; or many parallel accesses to a shared resource. We assess square root, power, trigonometric, and hyperbolic functions within the FPGA, and provide a tool to convert Python functions to our new architecture. Our third contribution extends the ring-based architecture to support any FPGA processing element. We unify E heterogeneous processing elements within compute pools, with each element implementing the same function, and the pool serving D parallel function calls. Our implementation-agnostic approach supports processing elements with different latencies, implementations, and pipeline lengths, as well as non-deterministic latencies. Compute pools evenly balance access to processing elements across the entire application, and are evaluated by implementing eight different neural network activation functions within an FPGA. Open Access

This thesis proposes novel algorithm and hardware optimisation approaches to accelerate Deep Neural Networks (DNNs), including both Convolutional Neural Networks (CNNs) and Bayesian Neural Networks (BayesNNs). The first contribution of this thesis is to propose an adaptable and reconfigurable hardware design to accelerate CNNs. By analysing the computational patterns of different CNNs, a unified hardware architecture is proposed for both 2-Dimension and 3-Dimension CNNs. The accelerator is also designed with runtime adaptability, which adopts different parallelism strategies for different convolutional layers at runtime. The second contribution of this thesis is to propose a novel neural network architecture and hardware design co-optimisation approach, which improves the performance of CNNs at both algorithm and hardware levels. Our proposed three-phase co-design framework decouples network training from design space exploration, which significantly reduces the time-cost of the co-optimisation process. The third contribution of this thesis is to propose an algorithmic and hardware co-optimisation framework for accelerating BayesNNs. At the algorithmic level, three categories of structured sparsity are explored to reduce the computational complexity of BayesNNs. At the hardware level, we propose a novel hardware architecture with the aim of exploiting the structured sparsity for BayesNNs. Both algorithmic and hardware optimisations are jointly applied to push the performance limit. Open Access

Existing FPGA accelerators for short read mapping often fail to utilize the complete biological information in sequencing data for simple hardware design, leading to missed or incorrect alignment. In this work, we propose a runtime reconfigurable alignment pipeline that considers all information in sequencing data for the biologically accurate acceleration of short read mapping. We focus our efforts on accelerating two string matching techniques: FM-index and the Smith-Waterman algorithm with the affine-gap model which are commonly used in short read mapping. We further optimize the FPGA hardware using a design analyzer and merger to improve alignment performance. The contributions of this work are as follows. 1. We accelerate the exact-match and mismatch alignment by leveraging the FM-index technique. We optimize memory access by compressing the data structure and interleaving the access with multiple short reads. The FM-index hardware also considers complete information in the read data to maximize accuracy. 2. We propose a seed-and-extend model to accelerate alignment with indels. The FM-index hardware is extended to support the seeding stage while a Smith-Waterman implementation with the affine-gap model is developed on FPGA for the extension stage. This model can improve the efficiency of indel alignment with comparable accuracy versus state-of-the-art software. 3. We present an approach for merging multiple FPGA designs into a single hardware design, so that multiple place-and-route tasks can be replaced by a single task to speed up functional evaluation of designs. We first experiment with this approach to demonstrate its feasibility for different designs. Then we apply this approach to optimize one of the proposed FPGA aligners for better alignment performance. Open Access

The amount of data stored and processed in data centers is growing at an unprecedented rate. At the same time, the improvement in processing capabilities of central processing units (CPUs) has relatively stagnated over the last decade, creating an increasing demand for specialised processing. Specialised accelerators have gotten the spotlight for computationally intensive applications, such as with deep learning on graphics processing units (GPUs), though such special purpose processors tend to be optimised for the trending applications and are not efficient for each entity’s computational needs. On the other hand, reconfigurable computing has shown impressive potential in accelerating specialised tasks, including database applications. Hence, field-programmable gate arrays (FPGAs) have started evolving into an integral part in the data center. However, the heterogeneity found in today’s systems featuring FPGAs, such as through non-uniform memory accesses (NUMA), has complicated the deployment and development of database accelerators. This PhD introduces novel parallel algorithms and FPGA designs for database acceleration that take into consideration the inter-chip communication limitations. The presented designs accelerate fundamental database operators such as sorting, sort-merge join and distinct count, with notable advantages over the state-of-the-art. Additionally, some building blocks such as the parallel round-robin arbiter and the fast lightweight merge sorter (FLiMS) are shown to have a wider applicability, including in single-instruction multiple-data (SIMD) algorithms and network switches. The proposed designs operate in a streaming access pattern with a wide path in order to achieve scalability to input size and future high-bandwidth architectures. Finally, a discussion on future architectures with reconfigurable instructions is provided as future work to further address the challenges appearing when accelerating big data using today’s FPGAs. Open Access

This thesis addresses problems inherent to the development of complex applications for reconfig- urable systems. Many projects fail to complete or take much longer than originally estimated by relying on traditional iterative software development processes typically used with conventional computers. Even though designer productivity can be increased by abstract programming and execution models, e.g., dataflow, development methodologies considering the specific properties of reconfigurable systems do not exist. The first contribution of this thesis is a design methodology to facilitate systematic develop- ment of complex applications using reconfigurable hardware in the context of High-Performance Computing (HPC). The proposed methodology is built upon a careful analysis of the original application, a software model of the intended hardware system, an analytical prediction of performance and on-chip area usage, and an iterative architectural refinement to resolve identi- fied bottlenecks before writing a single line of code targeting the reconfigurable hardware. It is successfully validated using two real applications and both achieve state-of-the-art performance. The second contribution extends this methodology to provide portability between devices in two steps. First, additional tool support for contemporary multi-die Field-Programmable Gate Arrays (FPGAs) is developed. An algorithm to automatically map logical memories to hetero- geneous physical memories with special attention to die boundaries is proposed. As a result, only the proposed algorithm managed to successfully place and route all designs used in the evaluation while the second-best algorithm failed on one third of all large applications. Second, best practices for performance portability between different FPGA devices are collected and evaluated on a financial use case, showing efficient resource usage on five different platforms. The third contribution applies the extended methodology to a real, highly demanding emerging application from the radiotherapy domain. A Monte-Carlo based simulation of dose accumu- lation in human tissue is accelerated using the proposed methodology to meet the real time requirements of adaptive radiotherapy. Open Access

Machine learning applications are computationally expensive, but they can benefit from hardware acceleration. In recent years, there has been substantial research on accelerating the inference stage of machine learning models, but the work on the training stage has been limited. This thesis explores the hardware acceleration of the training stage of machine learning models. Specifically, this thesis makes the following three contributions. The first contribution of this thesis is incremental and decremental training of Support Vector Regression (SVR). At the algorithm level, we handle the boundary case ignored by existing algorithms to ensure correctness. At the hardware level, we design an efficient hardware architecture that circumvents algorithmic obstacles. FPGA implementation of the proposed SVR training scheme is evaluated with high frequency financial data. Significant speed-up is achieved using our FPGA-based system over CPU and GPU. The second contribution of this thesis is the hardware architecture for Trust Region Policy Optimisation (TRPO), an advanced Reinforcement Learning algorithm. The main novelty is the use of Pearlmutter Propagation to circumvent algorithm level obstacles in order to enable a streamlined hardware implementation. The proposed hardware architecture implemented on FPGA is evaluated with robotic control benchmarks. It achieves significant speed-up against machine learning libraries running on CPU and GPU. The third contribution of this thesis is the application of hardware accelerated TRPO training to real robotic control. We propose a workflow of training the controller in simulation with TRPO then port it to the real robot. In addition to the hardware accelerated TRPO, a Customised Lightweight Simulator running on FPGA significantly speeds up the simulation process. The workflow is applied to a real robot arm. Several experiments are performed to illustrate the effectiveness of the proposed workflow in controlling a real robot arm. Open Access

Financial markets are rapidly evolving to exploit powerful computational and statistical tools to construct both risk management and alpha strategies. This research seeks to develop new tools to identify efficient trading strategies through the use of genetic programming and some mathematical optimisation methods such as adaptive elastic net regularisation while leveraging the powerful hardware acceleration capabilities of Field Programmable Gate Array technology. The first contribution of this thesis represents a Field Programmable Gate Array based algorithmic trading system which supports multiple trading strategies that can be either run in parallel or switched at run-time according to changes in market volatility, for more elaborate trading strategies. Three types of hardware designs are compared: a static reconfiguration, a full reconfiguration, and a partial reconfiguration design. We evaluate our approach using both synthetic and historical market data and we notice that our system can obtain a considerable speedup when compared to its software implementation counterpart. The second contribution of this thesis presents an evolutionary hybrid genetic program which uses aspects of swarm intelligence to seek reliable and profitable trading patterns to enhance trading strategies. We use Field Programmable Gate Array technology to accelerate the fitness evaluation step, one of the most computationally demanding operations in genetic programming. The proposed design is based on run-time reconfiguration to improve hardware resource utilisation, being substantially faster than an optimised, multi-threaded software implementation while achieving comparable financial returns. The third contribution of this thesis represents a Field Programmable Gate Array based custom regularisation and regression solver, CRRS. We also introduce an Adaptive Elastic Net pipelined architecture implemented on Field Programmable Gate Arrays for maximum parallelism performance. We further show how CRRS can provide an efficient, scalable solution, allowing us to handle large-scale datasets that cannot fit the on-board DRAM of a single FPGA. Our solver proves to be efficient in different scenarios. For example, when applied to dimensionality reduction for a portfolio of foreign exchange rates, which uses the ``efficient kitchen-sink regression" approach within the ``Parametric Portfolio Policies" technique. Open Access

We present a novel method to optimise sparse matrix kernels for reconfigurable accelerators, through instance directed tuning - the tuning of reconfigurable architectures based on a sparse matrix instance. First, we present two novel reconfigurable architectures for the Conjugate Gradient Method that are optimised based on the problem dimension and sparsity pattern. These architectures provide the context for illustrating the opportunities and challenges for tuning sparse matrix kernels, which guide the design of the proposed method. Second, we introduce CASK, a novel framework for sparse matrix kernels on reconfigurable accelerators. CASK is: (1) instance directed, since it can account for differences in the matrix instances to generate and select adequate architectures; (2) unified, as it can be applied to a broad range of kernels and optimisations; (3) systematic, since it can support optimisations at multiple levels of encompassed reconfigurable architectures; and (4) automated, since it can operate with minimal user input, encapsulating and simplifying the tuning process. Third, we demonstrate the benefits of the proposed approach, by applying it to the Sparse Matrix Vector Multiplication kernel: (1) to tune a novel parametric reconfigurable architecture, resulting in up to 2 times energy effciency gains compared to optimised GPU and Xeon Phi implementations; (2) to include a novel compression method for nonzero values, resulting in up to 2.5 times compression ratio compared to the Compressed Sparse Row format; and (3) to tune a novel architecture for the block diagonal sparsity pattern arising in the Finite Element Method, enabling larger problems to be supported with up to 3 times speedup compared to an optimised CPU implementation. Open Access

In this work we explore how Field-Programmable Gate Arrays (FPGAs) can be used to alleviate the data processing bottlenecks in DNA sequencing. We focus our efforts on accelerating the FM-index, a data structure used to solve the computationally intensive string matching problems found in DNA sequencing analysis such as short read alignment. The main contributions of this work are: 1) We accelerate the FM-index using FPGAs and develop several novel methods for reducing the memory bottleneck of the search algorithm. These methods include customising the FM-index structure according to the memory architecture of the FPGA platform and minimising the number of memory accesses through both architectural and algorithmic optimisations. 2) We present a new approach for accelerating approximate string matching using the backtracking FM-index. This approach makes use of specialised approximate string matching modules and a run-time reconfigurable architecture in order to achieve both high sensitivity and high performance. 3) We extend the FM-index search algorithm for reference-based compression and accelerate it using FPGAs. This accelerated design is integrated into fastqZip and fastaZip, two new tools that we have developed for the fast and effective compression of sequence data stored in the FASTQ and FASTA formats respectively. We implement our designs on the Maxeler Max4 Platform and show that they are able to outperform state-of-the-art DNA sequencing analysis software. For instance, our hardware-accelerated compression tool for FASTQ data is able to achieve a higher compression ratio than the best performing tool, fastqz, whilst the average compression and decompression speeds are 25 and 43 times faster respectively. Open Access

The study of event streams involves modelling arrival times of discrete random events. Predictive systems for event streams infer information about future occurrences of random events. These systems are useful for various applications such as stock trading modelling and earthquake analysis, but the computational burdens limit their predictive power. This thesis addresses the design and optimisation of reconfigurable predictive systems for event streams. The first contribution of this thesis is the reconfigurable acceleration solution for the calculations in the Hawkes point process models. We propose reconfigurable dataflow engines for intensity evaluation and likelihood evaluation for univariate and multivariate Hawkes point process models. We also establish an efficient collaboration scheme between the CPU platform and the reconfigurable accelerator to speed up parameter estimation. The second contribution of this thesis is a novel predictive model for event streams. As the Hawkes point process models have limited predictive accuracy and low computational efficiency, we propose a predictive model for event streams using regression techniques. We derive the model from the intensity function of the Hawkes point process, but the final form of the proposed model works without point process models. A software system based on the proposed model reduces the prediction error by 3\%--7\% compared to a system based on the Hawkes process. A hardware-accelerated system based on the proposed model is 5--66 times faster in model fitting compared to the accelerated system based on the Hawkes process, while the two systems produce similar predictive accuracy. The third contribution of this thesis is the design of two reconfigurable accelerators for time series analysis. One accelerator is for the estimation of correlation for multivariate time series. The other accelerator is for the ordinal pattern encoding for univariate time series. We design the two accelerators by transforming the calculations of the corresponding statistical metrics into pipeline-friendly forms. Compared to multicore CPUs, both accelerators show high efficiency for large time series data. Open Access

Genetic Algorithms (GAs) are a class of numerical and combinatorial optimisers which are especially useful for solving non-linear and non-convex problems. However, the required execution time often limits their application to small-scale or latency-insensitive problems, so techniques to increase the speed and computational efficiency of GAs are needed. FPGA-based acceleration has significant potential for speeding up genetic algorithms, but existing FPGA-based GA systems are limited by the need for extensive hardware architecture customisation by end users and the relatively small improvement in performance. The main reasons for these limitations are that most of the units in these GA systems are fixed and the algorithms of these FPGA-based systems are just inherited from software GAs without making full use of reconfigurable hardware. This thesis examines the previous work and then rethinks the creation of genetic algorithms with reconfigurable computing, and aims to address the problems of low-level programmability, flexibility, and performance in current GA systems. The thesis first presents a general-purpose automated framework for creating and executing a flexible parallel GA system on one FPGA or even multiple FPGAs, which increases the flexibility in GA architecture and removes the low-level hardware programmability barrier for non-expert users. The thesis then proposes a novel hardware-oriented approach called Pipelined Genetic Propagation (PGP), which is intrinsically spatially distributed and fully pipelined. PGP represents a GA solver as a graph of loosely coupled genetic operators, which allows the system to be scaled to the available resources, and also to dynamically change connection topology at run-time to explore different strategies. Finally the thesis extends PGP in three ways: Recursive PGP for multiple level optimisation problems, machine learning guided PGP for automatically changing the connection topology, and partially reconfigurable PGP to increase flexibility. Overall, the thesis presents new ways to perform genetic algorithms in reconfigurable computing, with high-level programmability, sufficient flexibility and high performance. Open Access

Currently, the optimization of reconfigurable design parameters is typically done manually and often involves substantial amount effort. The main focus of this thesis is to reduce this effort. The designer can focus on the implementation and design correctness, leaving the tools to carry out optimization. To address this, this thesis makes three main contributions. First, we present initial investigation of reconfigurable design optimization with the Machine Learning Optimizer (MLO) algorithm. The algorithm is based on surrogate model technology and particle swarm optimization. By using surrogate models the long hardware generation time is mitigated and automatic optimization is possible. For the first time, to the best of our knowledge, we show how those models can both predict when hardware generation will fail and how well will the design perform. Second, we introduce a new algorithm called Automatic Reconfigurable Design Efficient Global Optimization (ARDEGO), which is based on the Efficient Global Optimization (EGO) algorithm. Compared to MLO, it supports parallelism and uses a simpler optimization loop. As the ARDEGO algorithm uses multiple optimization compute nodes, its optimization speed is greatly improved relative to MLO. Hardware generation time is random in nature, two similar configurations can take vastly different amount of time to generate making parallelization complicated. The novelty is efficient use of the optimization compute nodes achieved through extension of the asynchronous parallel EGO algorithm to constrained problems. Third, we show how results of design synthesis and benchmarking can be reused when a design is ported to a different platform or when its code is revised. This is achieved through the new Auto-Transfer algorithm. A methodology to make the best use of available synthesis and benchmarking results is a novel contribution to design automation of reconfigurable systems. Open Access

Computing is increasingly heterogeneous. Beyond Central Processing Units (CPUs), different architectures such as massively parallel Graphics Processing Units (GPUs) and reconfigurable Field Programmable Gate Arrays (FPGAs) are seeing widespread adoption. However, the failure of conventional programming approaches to support portable execution, predict the runtime characteristics and partition workloads optimally is hindering the realisation of heterogeneous computing. By narrowing the scope of expression in a natural manner, using a domain specific approach, these three challenges can be addressed. A domain specific heterogeneous computing methodology enables three features: Portability, Prediction and Partitioning. Portable, efficient execution is enabled by a domain specific approach because only a subset of domain functions need to be supported across the heterogeneous computing platforms. Predictive models of runtime characteristics are enabled as the structure of the domain functions may be analysed a priori. Finally optimal partitioning is possible because the metric models can be used to form an optimisation program that can be solved by either heuristic, machine learning or Mixed Integer Linear Programming (MILP) approaches. Using the example of the application domain of financial derivatives pricing, a domain specific application framework, the Forward Financial Framework (F^3), can execute a single pricing task upon a diverse range of CPU, GPU and FPGA platforms from many different vendors. Not only do these portable implementations exhibit strong parallel scaling, but are competitive with state-of-the-art, expert created implementations of the same option pricing problems. Furthermore, F^3 can model the crucial runtime metrics of latency and accuracy for these heterogeneous platforms using a small benchmarking procedure to within 10% of the run-time value of these metrics. Finally, the framework can optimally partition work across heterogeneous platforms, using a MILP framework, that is up to 270 times more efficient than what is achieved by using a heuristic approach. Open Access

This thesis proposes novel optimisations for high performance runtime reconfigurable designs. For a reconfigurable design, the proposed approach investigates idle resources introduced by static design approaches, and exploits runtime reconfiguration to eliminate the inefficient resources. The approach covers the circuit level, the function level, and the system level. At the circuit level, a method is proposed for tuning reconfigurable designs with two analytical models: a resource model for computational and memory resources and memory bandwidth, and a performance model for estimating execution time. This method is applied to tuning implementations of finite-difference algorithms, optimising arithmetic operators and memory bandwidth based on algorithmic parameters, and eliminating idle resources by runtime reconfiguration. At the function level, a method is proposed to automatically identify and exploit runtime reconfiguration opportunities while optimising resource utilisation. The method is based on Reconfiguration Data Flow Graph, a new hierarchical graph structure enabling runtime reconfigurable designs to be synthesised in three steps: function analysis, configuration organisation, and runtime solution generation. At the system level, a method is proposed for optimising reconfigurable designs by dynamically adapting the designs to available runtime resources in a reconfigurable system. This method includes two steps: compile-time optimisation and runtime scaling, which enable efficient workload distribution, asynchronous communication scheduling, and domain-specific optimisations. It can be used in developing effective servers for high performance applications. Open Access

This thesis addresses the problem of designing real-time reconfigurable systems. Our first contribution of this thesis is to propose novel data structures and memory architectures for accelerating real-time proximity queries, with potential application to robotic surgery. We optimise performance while maintaining accuracy by several techniques including mixed precision, function transformation and streaming data flow. Significant speedup is achieved using our reconfigurable system over double-precision CPU, GPU and FPGA designs. The second contribution of this thesis is an adaptation methodology for real-time sequential Monte Carlo methods. Adapting to workload over time, different configurations with various performance and power consumption trade-offs are loaded onto the FPGAs dynamically. Promising energy reduction has been achieved in addition to speedup over CPU and GPU designs. The approach is evaluated in an application to robot localisation. The third contribution of this thesis is a design flow for automated mapping and optimisation of real-time sequential Monte Carlo methods. Machine learning algorithms are used to search for an optimal parameter set to produce the highest solution quality while satisfying all timing and resource constraints. The approach is evaluated in an application to air traffic management. Open Access

This thesis proposes a reconfigurable computing approach for supporting parallel processing in large-scale graph traversal algorithms. Our approach is based on a reconfigurable hardware architecture which exploits the capabilities of both FPGAs (Field-Programmable Gate Arrays) and a multi-bank parallel memory subsystem. The proposed methodology to accelerate graph traversal algorithms has been applied to three case studies, revealing that application-specific hardware customisations can benefit performance. A summary of our four contributions is as follows. First, a reconfigurable computing approach to accelerate large-scale graph traversal algorithms. We propose a reconfigurable hardware architecture which decouples computation and communication while keeping multiple memory requests in flight at any given time, taking advantage of the high bandwidth of multi-bank memory subsystems. Second, a demonstration of the effectiveness of our approach through two case studies: the breadth-first search algorithm, and a graphlet counting algorithm from bioinformatics. Both case studies involve graph traversal, but each of them adopts a different graph data representation. Third, a method for using on-chip memory resources in FPGAs to reduce off-chip memory accesses for accelerating graph traversal algorithms, through a case-study of the All-Pairs Shortest-Paths algorithm. This case study has been applied to process human brain network data. Fourth, an evaluation of an approach based on instruction-set extension for FPGA design against many-core GPUs (Graphics Processing Units), based on a set of benchmarks with different memory access characteristics. It is shown that while GPUs excel at streaming applications, the proposed approach can outperform GPUs in applications with poor locality characteristics, such as graph traversal problems. Open Access

The large-scale integrative mechanisms of the brain, the means by which the activity of functionally segregated neuronal regions are combined, are not well understood. There is growing agreement that a flexible mechanism of integration must be present in order to support the myriad changing cognitive demands under which we are placed. Neuronal communication through phase-coherent oscillation stands as the prominent theory of cognitive integration. The work presented in this thesis explores the role of oscillation and synchronisation in the transfer and integration of information in the brain. It is first shown that complex metastable dynamics suitable for modelling phase-coherent neuronal synchronisation emerge from modularity in networks of delay and pulse-coupled oscillators. Within a restricted parameter regime these networks display a constantly changing set of partially synchronised states where some modules remain highly synchronised while others desynchronise. An examination of network phase dynamics shows increasing coherence with increasing connectivity between modules. The metastable chimera states that emerge from the activity of modular oscillator networks are demonstrated to be synchronous with a constant phase relationship as would be required of a mechanism of large-scale neural integration. A specific example of functional phase-coherent synchronisation within a spiking neural system is then developed. Competitive stimulus selection between converging population encoded stimuli is demonstrated through entrainment of oscillation in receiving neurons. The behaviour of the model is shown to be analogous to well-known competitive processes of stimulus selection such as binocular rivalry, matching key experimentally observed properties for the distribution and correlation of periods of entrainment under differing stimuli strength. Finally two new measures of network centrality, knotty-centrality and set betweenness centrality, are developed and applied to empirically derived human structural brain connectivity data. It is shown that human brain organisation exhibits a topologically central core network within a modular structure consistent with the generation of synchronous oscillation with functional phase dynamics.

Growing demand for computational performance, and the rising cost for chip design and manufacturing make reconfigurable hardware increasingly attractive for digital system implementation. Reconfigurable hardware, such as field-programmable gate arrays (FPGAs), can deliver performance through parallelism while also providing flexibility to enable application builders to reconfigure them. However, reconfigurable systems, particularly those involving run-time reconfiguration, are often developed in an ad-hoc manner. Such an approach usually results in low designer productivity and can lead to inefficient designs. This thesis covers three main achievements that address this situation. The first achievement is a model that captures design parameters of reconfigurable hardware and performance parameters of a given application domain. This model supports optimisations for several design metrics such as performance, area, and power consumption. The second achievement is a technique that enhances the relocatability of bitstreams for reconfigurable devices, taking into account heterogeneous resources. This method increases the flexibility of modules represented by these bitstreams while reducing configuration storage size and design compilation time. The third achievement is a technique to characterise the power consumption of FPGAs in different activity modes. This technique includes the evaluation of standby power and dedicated low-power modes, which are crucial in meeting the requirements for battery-based mobile devices.

One of the challenges of designing hardware circuits is representing the data in an efficient way - minimising area and power while maximising clock frequency. There are several ways of representing variables, each with different characteristics, such as the effect arithmetic operations have on the absolute and relative error. In the first part of this thesis, a new method of transforming arithmetic by combining different numerical representations to exploit their advantages is discussed. The problem is formulated as a set of linear equations which are then solved to find the optimal solution. Algorithms that generate sub-optimal solutions are investigated because they take a fraction of the time to run. A new reconfigurable device structure is proposed based on the results presented. In this case, the accuracy of the original application is guaranteed to be met regardless of the input data. In many applications, guaranteeing that a transformed design has at least the same accuracy as the original is not a strong enough constraint. For this reason, the error on the output is guaranteed to be lower than a specified value. In the second part of this thesis, accuracy reduction is investigated with the goal of minimising circuit area. Energy-efficient run-time reconfigurable hardware is automatically created by systematically deactivating parts of the circuit based on the accuracy required. A model to determine the conditions under which reconfiguring the chip, if this is possible, is more energy-efficient than multiplexing is shown. The approach is expanded to general purpose processors; a new computational model - both software and hardware architecture - to reduce the energy of future devices is introduced.

The high-level goal of this research is to identify a method to accelerate general purpose software using heterogeneous systems. Heterogeneous systems offer the potential of improving performance through the use of hardware components specialised for a particular task. The issue considered in this research is how best to map parts of an existing piece of software to components in a heterogeneous architecture to deliver the optimal program execution time. The heterogeneous partitioning problem is an NP-hard quadratic optimisation problem. However, before the problem could be addressed using optimisation techniques, the problem had to be quantified and formalised using software characterisation and computational abstraction models. The main contributions delivered by this research are: • 3S: a novel software characterisation framework that combines static instrumentation with dynamic characterisation enabling simple tools to measure real fine-grained execution timing, control and data flow information for any compilable program. • MAP: a new execution model and multi-level parallel assignment approach that delivers up to 64 times the heterogeneous acceleration potential of previous work for the benchmarks considered. • MIP: the first formal work on multiple instantiation under activation sequence uncertainty, providing more than twice the acceleration potential of previous optimal assignment methods for the software considered and capable of being integrated with MAP to deliver significant gains for heterogeneous partitioning. These contributions have been published in a collection of research papers and are the focus of Chapters 3, 4 and 5 of this thesis.

We present a methodology for generating floating-point arithmetic hardware designs which are, for suitable applications, much reduced in size, while still retaining performance and IEEE-754 compliance. Our system uses three key parts: a profiling tool, a set of customisable floating-point units and a selection of system integration methods. We use a profiling tool for floating-point behaviour to identify arithmetic operations where fundamental elements of IEEE-754 floating-point may be compromised, without generating erroneous results in the common case. In the uncommon case, we use simple detection logic to determine when operands lie outside the range of capabilities of the optimised hardware. Out-of-range operations are handled by a separate, fully capable, floatingpoint implementation, either on-chip or by returning calculations to a host processor. We present methods of system integration to achieve this errorcorrection. Thus the system suffers no compromise in IEEE-754 compliance, even when the synthesised hardware would generate erroneous results. In particular, we identify from input operands the shift amounts required for input operand alignment and post-operation normalisation. For operations where these are small, we synthesise hardware with reduced-size barrel-shifters. We also propose optimisations to take advantage of other profile-exposed behaviours, including removing the hardware required to swap operands in a floating-point adder or subtractor, and reducing the exponent range to fit observed values. We present profiling results for a range of applications, including a selection of computational science programs, Spec FP 95 benchmarks and the FFMPEG media processing tool, indicating which would be amenable to our method. Selected applications which demonstrate potential for optimisation are then taken through to a hardware implementation. We show up to a 45% decrease in hardware size for a floating-point datapath, with a correctable error-rate of less then 3%, even with non-profiled datasets.

On-chip communication system has emerged as a prominently important subject in Very-Large- Scale-Integration (VLSI) design, as the trend of technology scaling favours logics more than interconnects. Interconnects often dictates the system performance, and, therefore, research for new methodologies and system architectures that deliver high-performance communication services across the chip is mandatory. The interconnect challenge is exacerbated in Field-Programmable Gate Array (FPGA), as a type of ASIC where the hardware can be programmed post-fabrication. Communication across an FPGA will be deteriorating as a result of interconnect scaling. The programmable fabrics, switches and the specific routing architecture also introduce additional latency and bandwidth degradation further hindering intra-chip communication performance. Past research efforts mainly focused on optimizing logic elements and functional units in FPGAs. Communication with programmable interconnect received little attention and is inadequately understood. This thesis is among the first to research on-chip communication systems that are built on top of programmable fabrics and proposes methodologies to maximize the interconnect throughput performance. There are three major contributions in this thesis: (i) an analysis of on-chip interconnect fringing, which degrades the bandwidth of communication channels due to routing congestions in reconfigurable architectures; (ii) a new analogue wave signalling scheme that significantly improves the interconnect throughput by exploiting the fundamental electrical characteristics of the reconfigurable interconnect structures. This new scheme can potentially mitigate the interconnect scaling challenges. (iii) a novel Dynamic Programming (DP)-network to provide adaptive routing in network-on-chip (NoC) systems. The DP-network architecture performs runtime optimization for route planning and dynamic routing which, effectively utilizes the in-silicon bandwidth. This thesis explores a new horizon in reconfigurable system design, in which new methodologies and concepts are proposed to enhance the on-FPGA communication throughput performance that is of vital importance in new technology processes.