Search

Random Forest (RF) is one of the most widely used supervised learning methods available. An RF is ensemble of decision tree classifiers with injection of several sources of randomness. It demonstrates a set of improvement over single decision and regression trees and is comparable or superior to major classification tools such as support vector machine (SVM) and adaptive boosting (Adaboost) with respect to accuracy, interpretability, robustness and processing speed. RF can be generally divided into training process and predicting process. Recently with emergence of large-scale data mining applications, the RF training process implemented in software on a single computer can no longer induce a complex RF model within reasonable amount of time. Alternative solutions involving computer clusters and GPUs usually come with disadvantages with respect to Performance/Power ratio and are not feasible for portable/embedded applications. In this work a set of FPGA-based implementations of the RF training process are proposed. FPGA devices allow construction of efficient custom hardware architectures and feature lower power consumption than typical GPPs or GPUs therefore are suitable for portable/embedded applications. The proposed hardware training architectures take advantage of different types of inherent parallelism in the RF training algorithm and distribute the workload to a set of parallel workers. Combining the parallel processing techniques with custom hardware designs featuring low latency, the architectures are able to accelerate the training process without loss in accuracy.

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.

This portfolio document is intended to present the work carried out in order to meet the requirements of the Engineering Doctorate (EngD) program undertaken at the Institute for System Level Integration (ISLI). This program was undertaken in partnership with the Universities of Glasgow, Edinburgh, Strathclyde and Heriott Watt and was funded by EPSRC and SLI Ltd. The use of control systems is becoming ubiquitous with even the simplest of systems now employing some kind of control logic. For this reason the project investigated the use and development of reconfigurable hardware for control applications. This first involved a detailed analysis of the current state of the art in the reconfigurable field as well as some selected applications where it is thought this technology may be of benefit. The main body of the project was separated into three distinct areas of research and is hence presented as a collection of three technical documents. The first of these areas was the use of reconfigurable hardware for the implementation of Finite State Machines (FSM) with particular reference to reducing the size of the hardware block required to implement these structures. From this a novel implementation method was developed based on the principle of Forward Transition Expressions which are capable of implementing FSMs on a reconfigurable device using run-time reconfiguration. The second area of research was the investigation of the characteristics of reconfigurable devices with a view to estimating the amount of hardware required within a device from high level parameters. The final area of research was the development of a custom reconfigurable device specifically tailored for the implementation of FSM.

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 field of Bioinformatics and Computational Biology (BCB) is a multidisciplinary field that has emerged due to the computational demands of current state-of-the-art biotechnology. BCB deals with the storage, organization, retrieval, and analysis of biological datasets, which have grown in size and complexity in recent years especially after the completion of the human genome project. The advent of Microarray technology in the 1990s has resulted in the new concept of high throughput experiment, which is a biotechnology that measures the gene expression profiles of thousands of genes simultaneously. As such, Microarray requires high computational power to extract the biological relevance from its high dimensional data. Current general purpose processors (GPPs) has been unable to keep-up with the increasing computational demands of Microarrays and reached a limit in terms of clock speed. Consequently, Field Programmable Gate Arrays (FPGAs) have been proposed as a low power viable solution to overcome the computational limitations of GPPs and other methods. The research presented in this thesis harnesses current state-of-the-art FPGAs and tools to accelerate some of the most widely used data mining methods used for the analysis of Microarray data in an effort to investigate the viability of the technology as an efficient, low power, and economic solution for the analysis of Microarray data. Three widely used methods have been selected for the FPGA implementations: one is the un-supervised Kmeans clustering algorithm, while the other two are supervised classification methods, namely, the K-Nearest Neighbour (K-NN) and Support Vector Machines (SVM). These methods are thought to benefit from parallel implementation. This thesis presents detailed designs and implementations of these three BCB applications on FPGA captured in Verilog HDL, whose performance are compared with equivalent implementations running on GPPs. In addition to acceleration, the benefits of current dynamic partial reconfiguration (DPR) capability of modern Xilinx’ FPGAs are investigated with reference to the aforementioned data mining methods. Implementing K-means clustering on FPGA using non-DPR design flow has outperformed equivalent implementations in GPP and GPU in terms of speed-up by two orders and one order of magnitude, respectively; while being eight times more power efficient than GPP and four times more than a GPU implementation. As for the energy efficiency, the FPGA implementation was 615 times more energy efficient than GPPs, and 31 times more than GPUs. Over and above, the FPGA implementation outperformed the GPP and GPU implementations in terms of speed-up as the dimensionality of the Microarray data increases. Additionally, the DPR implementations of the K-means clustering have shown speed-up in partial reconfiguration time of ~5x and 17x over full chip reconfiguration for single-core and eight-core implementations, respectively. Two architectures of the K-NN classifier have been implemented on FPGA, namely, A1 and A2. The K-NN implementation based on A1 architecture achieved a speed-up of ~76x over an equivalent GPP implementation whereas the A2 architecture achieved ~68x speedup. Furthermore, the FPGA implementation outperformed the equivalent GPP implementation when the dimensionality of data was increased. In addition, The DPR implementations of the K-NN classifier have achieved speed-ups in reconfiguration time between ~4x to 10x over full chip reconfiguration when reconfiguring portion of the classifier or the complete classifier. Similar to K-NN, two architectures of the SVM classifier were implemented on FPGA whereby the former outperformed an equivalent GPP implementation by ~61x and the latter by ~49x. As for the DPR implementation of the SVM classifier, it has shown a speed-up of ~8x in reconfiguration time when reconfiguring the complete core or when exchanging it with a K-NN core forming a multi-classifier. The aforementioned implementations clearly show FPGAs to be an efficacious, efficient and economic solution for bioinformatics Microarrays data analysis.

Nowadays the ever increasing algorithmic complexity of embedded applications requires the designers to turn towards heterogeneous and highly integrated systems denoted as SoC (System-on-a-Chip). These architectures may embed CPU-based processors, dedicated datapaths as well as recon gurable units. However, embedded SoCs are submitted to stringent requirements in terms of speed, size, cost, power consumption, throughput, etc. Therefore, new computing paradigms are required to ful l the constraints of the applications and the requirements of the architecture. Recon gurable Computing is a promising paradigm that provides probably the best trade-o between these requirements and constraints. Dynamically recon gurable architectures are their key enabling technology. They enable the hardware to adapt to the application at runtime. However, these architectures raise new challenges in SoC design. For example, on one hand, designing a system that takes advantage of dynamic recon guration is still very time consuming because of the lack of design methodologies and tools. On the other hand, scheduling hardware tasks di ers from classical software tasks scheduling on microprocessor or multiprocessors systems, as it bears a further complicated placement problem. This thesis deals with the problem of scheduling online real-time hardware tasks on Dynamically Recon gurable Hardware Devices (DRHWs). The problem is addressed from two angles : (i) Investigating novel algorithms for online real-time scheduling/placement on DRHWs. (ii) Scheduling/Placement algorithms library for RTOS-driven Design Space Exploration (DSE). Regarding the first point, the thesis proposes two main runtime-aware scheduling and placement techniques and assesses their suitability for online real-time scenarios. The first technique discusses the impact of synthesizing, at design time, several shapes and/or sizes per hardware task (denoted as multi-shape task), in order to ease the online scheduling process. The second technique combines a looking-ahead scheduling approach with a slots-based recon gurable areas management that relies on a 1D placement. The results show that in both techniques, the scheduling and placement quality is improved without signi cantly increasing the algorithm time complexity. Regarding the second point, in the process of designing SoCs embedding recon gurable parts, new design paradigms tend to explore and validate as early as possible, at system level, the architectural design space. Therefore, the RTOS (Real-Time Operating System) services that manage the recon gurable parts of the SoC can be re fined. In such a context, gathering numerous hardware tasks scheduling and placement algorithms of various complexity vs performance trade-o s in a kind of library is required. In this thesis, proposed algorithms in addition to some existing ones are purposely implemented in C++ language, in order to insure the compatibility with any C++/SystemC based SoC design methodology.