Placementand Routing Algorithms For Dynamically Reconfigurable FPGAs

The advances in the programmable logic devices especially Field-Programmable Gate Arrays (FPGA) have led to new architectures where the hardware can be dynamically adapted to the application to gain better performance. This kind of FPGA is called Dynamically Reconfigurable FPGA (DRFPGA). However, there are still many challenging problems to be solved before any practical general-purpose reconfigurable system is built. One fundamental problem is the placement of modules on the reconfigurable functional unit (RFU) in DRFPGAs.In this thesis, we start from the architecture and CAD for FPGAs, and introduce the concept of reconfigurable computing. Then we set up the reconfigurable computing system model and DRFPGA model and based on this model, we present a partitioning-based timing-driven online placement and Pathfinder negotiated congestion-based routing algorithms for DRFPGAs. The circuit (in HDL) is first divided into tiers with limited number of inter-tier vias, and then placed on individual tiers, while minimizing the delay of critical path. Experimental results show that our placement scheme achieves on average a total decrease of 27% in delay, 34% (resp. 11%) in wire-length and 42% (resp. 97%) in runtime, compared with the traditional placement methods (resp. [37]'s method). Also, our routing algorithm can reduce the wire-length by 26% and horizontal channel width by 27% on average, respectively, compared with the traditional placement methods, which demonstrates very high performance.