Thesis (M. Sc.)--University of Alberta, 2009. / Title from PDF file main screen (viewed on Dec. 14, 2009). "A thesis submitted to the Faculty of Graduate Studies and Research in partial fulfillment of the requirements for the degree of Master of Science, Department of Electrical and Computer Engineering, University of Alberta." Includes bibliographical references.

Thesis (M.S.)--University of Florida, 2002. / Title from title page of source document. Includes vita. Includes bibliographical references.

Title from PDF of title page (University of Missouri--Columbia, viewed on Feb 18, 2010). The entire thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file; a non-technical public abstract appears in the public.pdf file. Thesis advisor: Dr. Harry Tyrer. Includes bibliographical references.

Thesis (M. Eng. Sc.)--University of Queensland, 2002. / Includes bibliographical references.

Thesis (M.S. in Electrical Engineering)--Naval Postgraduate School, June 2003. / Thesis advisor(s): Herschel H. Loomis, Alan A. Ross. Includes bibliographical references (p. 219-224). Also available online.

The era of big data has led to problems of unprecedented scale and complexity that are challenging the computing capability of conventional computer systems. One way to address the computational and communication challenges of such demanding applications is to incorporate the use of non-conventional hardware accelerators such as FPGAs into existing systems. By providing a mix of FPGAs and conventional CPUs as computing resources in a heterogeneous cluster, a distributed computing environment can be achieved to address the need of both compute-intensive and data-intensive applications. However, utilizing heterogeneous clusters requires application developers’ comprehensive knowledge on both hardware and software. In order to assist programmers to take advantage of the synergy between hardware and software easily, an easy-to-use framework for virtualizing the underlying FPGA computing resources of the heterogeneous cluster is motivated. In this work, a heterogeneous cluster consisting of both FPGAs and CPUs was built and a framework for managing multiple FPGAs across the cluster was designed. The major contribution of the framework is to provide an abstraction layer between the application developer and the underlying FPGA computing resources, so as to improve the overall design productivity. An inter-FPGA communication system was implemented such that gateware executing on FPGAs can communicate with each other autonomously to the CPU. Furthermore, to demonstrate a real-life application on the heterogeneous cluster, a generic k-means clustering application was implemented, using the MapReduce programming model. The implementation of the k-means application on multiple FPGAs was compared with a software-only version that was run on a Hadoop multi-core computer cluster. The performance results show that the FPGA version outperforms the Hadoop version across various parameters. An in-depth study on the communication bottleneck presented in the system was also carried out. A number of experiments were specifically designed to benchmark the performance of each I/O channel. The study shows that the major source of I/O bottleneck lies at the communication between the host system and the FPGA. This gives insight into programming considerations of potential applications on the cluster as well as improvement to the framework. Moreover, the benefit of multiple FPGAs was investigated through a series of experiments. Compared with putting all mappers on a single FPGA, it was found that distributing the same amount of mappers across more FPGAs can provide a tradeoff between FPGA resources and I/O performance. / published_or_final_version / Electrical and Electronic Engineering / Master / Master of Philosophy

published_or_final_version / abstract / toc / Electrical and Electronic Engineering / Master / Master of Philosophy

No description available.

A lot of work has been done over the last decade on the logic synthesis and technology mapping of field programmable gate arrays (FPGAs) based on a single size of lookup table (LUT). A significant part of the FPGA market is occupied by devices based on more than one type of lookup tables. Examples of these heterogeneous LUT-based FPGAs are the Xilinx 4000 series devices. The technology mapping for this class of FPGAs has hardly been considered. This thesis covers work on the synthesis for heterogeneous LUT-based FPGAs. The proposed scheme uses the typical steps of graph covering, decomposition, node elimination and Boolean graph simplification. The covering step is based on the concept of flow networks and cut-computation. A theory is devised that reduces the flow network sizes so that a dynamic programming approach can be used to compute the feasible cuts in the network. An iterative selection algorithm can then be used to compute the set cover of the network. For the decomposition, the conventional bin-packing (cube-packing) algorithm has been extended so that it produces two types of bins. It has also been enhanced to explore several packing possibilities and include cube division and cascading of nodes. The classical functional decomposition method is extended to heterogeneous graphs. In particular, variable partitioning is coupled with other decomposition methods and exploits the structure of the functions. Partial collapsing and re-decomposition are used to re-synthesise the graphs. A strategy for eliminating nodes within a heterogeneous graph is developed. A simplification strategy is also derived from logic optimisation techniques. Comparisons of the mapping results on Xilinx devices show an improvement of over 11% over existing mapping tools for the same devices.

Current approaches to supporting module-based FPGA reconfiguration focus on various aspects and sub-problems in the area but do not combine to form a coherent, top-down methodology that factors low-level device parameters into every step of the design flow. This thesis proposes such a top-down methodology from application specification to low-level implementation, centered around examining the problem of generating a point-to-point communications infrastructure to support the changing interfaces of dynamically placed modules. Low-level implementation parameters are considered at every stage to ensure that area, timing and budget constraints of the application are met. The approach advocates the regular layout of modules surrounded by a wiring harness supporting the communications for those modules, and thus provides an advanced understanding of how to implement the "fixed wiring harness" model of reconfigurable computing proposed by Brebner. Results have shown that compared to flattened net lists the regularity of the layout does not impose significant overheads on critical path delays. At high communication densities it can even result in lower delays. The core of the methodology is an infrastructure generation process that allocates modules to slots and merges configuration graphs to form wiring harnesses that support the communications for these merged configurations. This thesis suggests methods and evaluates algorithms for configuration graph merging so as to reduce run-time reconfiguration overheads. Initial experiments with a greedy merging algorithm performed on an optical flow application resulted in a substantial reduction of 64% in reconfiguration time. The effects of graph merging with the initial greedy algorithm and an improved dynamic programming algorithm were explored for a range of device sizes and architectural parameters. Results show that configuration merging using the greedy method results in significant reductions to the reconfiguration delay. The dynamic programming algorithm provides consistent improvements above and beyond the savings provided by the greedy method. In addition, a strong correlation was identified between the quality of front-end design activities such as partitioning and the effectiveness of back-end implementations. The methodology is integrated into the Xilinx commercial tool flow for partial reconfiguration, and is effective for implementing applications for module-based FPGA reconfiguration where the modules and their communications requirements are known at design time. It also allows a system designer to consider alternate device sizes and parameters until a set is found that satisfies the application constraints.