Partitioning for fpga-based reconfigurable computers
Ranga R. Vemuri, Vinoo Srinivasan · 1999
This thesis addresses the issues involved in partitioning and synthesis for Reconfigurable Computers (RC). Typically, RCs host multiple-FPGAs (Field Programmable Gate Arrays) and distributed-memories that are connected through a programmable interconnection network. State-of-the-art CAD environments for reconfigurable computers are far from utilizing the underlying hardware, storage, and interconnect resources to their full potential. In order to efficiently use an RC, there is need for effective specification, implementation and cost-evaluation models. In addition, a design may be implemented in several different ways (design space), depending on the amount of resources available. Accurate cost estimation and design space exploration techniques are required to guide the partitioner toward high-quality designs. Partitioning a design for an RC involves binding the computational elements of the design to the FPGAs, assigning physical memory space to the logical storage elements in the design, and implementing the necessary inter-FPGA communication and synchronization. This must be done without violating any implicit constraints such as FPGA area and memory size, while at the same time meeting the optimization goals. The thesis investigates partitioning and synthesis of designs specified in four different specification models that are progressively developed in a bottom-up fashion. First a data-flow graph model is considered. We then introduce control constructs and define a block graph specification model. In order to accommodate parallel control threads a task graph model is built around the block graph. Finally, we develop a unified specification model that succinctly captures the concurrency, synchronization, storage, and communication semantics of the design. For each specification model, we present a detailed partitioning and synthesis methodology, targeting an abstract RC model. In each case, we present the implementation model of the partitioned design, cost estimation techniques, and the design space exploration mechanism. A summary of advantages and disadvantages of each RC partitioning approach is discussed in detail. One of the challenging problems in RC partitioning is the development of an architecture-independent partitioner. The presence of complex interconnection patterns between the FPGAs and memories makes this process difficult. We call the combined problem of FPGA pin-assignment and inter-FPGA routing interconnection synthesis. An architecture independent interconnection synthesis technique based on Boolean satisfiability is presented. In addition, we also implement a board-specific interconnection router for the Wildforce reconfigurable computer. We tightly integrate the various interconnection synthesis modules, and other cost estimators with the partitioner and develop a partitioning tool for the Wildforce board. Several experiments were conducted to analyze the performance and feasibility of the partitioning environment. Results show that effectiveness of the partitioner in handling multiple RC constraints and optimization goals.