Generating the communications infrastracture for module-based dynamic reconfiguration of FPGAs

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