Optimal and near-optimal temporal partitioning techniques for reconfigurable computer

This thesis presents optimal temporal partitioning and behavioral design space exploration techniques for mapping behavioral specifications of application specific circuits (ASIC) on reconfigurable computers (RC). The techniques support both task level and operation level behavior specifications. Contemporary RCs have various architectural features: (1) number of reconfigurable devices, (2) granularity of reconfigurable element, (3) presence of context cache and (4) levels of memory hierarchy. The thesis presents techniques that exploit these architectural features. The objective of the techniques is to minimize the execution time of the application subject to the RC resource constraints. The techniques exploit the run time reconfiguration facility of the RCs and attempt to amortize the reconfiguration overhead by block processing. The techniques perform design space exploration at behavior level. They consider various implementations for each temporal partition that have different latency and resource requirements.;The thesis presents algorithms to perform temporal partitioning for FPGA based fine-grained RC architectures. First, an operation level temporal partitioning and design space exploration technique is presented. Then, a temporal partitioning and design space exploration technique for task level specifications is developed. A novel block processing method is developed to amortize the reconfiguration overhead for a class of image/signal processing applications. Finally, a design flow of the task level temporal partitioning method and external spatial partitioning tools is developed to generate designs for fine-grained RCs containing multiple devices (multi-FPGA architectures).;The temporal partitioning techniques for fine-grained architectures can also be used for coarse-grained architectures because the partitioner is independent of the architecture. However, to take advantage of specific hardware features, the task level temporal partitioning techniques are extended for coarse-grained architectures to perform resource sharing among tasks on a temporal segment. Specific extensions are presented for context caching and memory hierarchies.;All techniques developed in this thesis use integer linear programming (ILP) methods to solve the problems. The thesis also present extensions to obtain near optimal results in a reasonable time period for large sized problems. Extensive experimental results on typical ASIC benchmarks circuits like Discrete Cosine Transform (DCT) and Fast Fourier Transform (FFT) are presented for all techniques.