Application mapping for platform FPGAs with partial dynamic reconfiguration

Partial dynamic reconfiguration, frequently referred to as RTR, (Run-Time Reconfiguration), is a key feature available in the current generation of SRAM-based FPGAs (Field Programmable Gate Arrays). This feature opens up the possibility of true on-the-fly computing. An application invoked dynamically is assigned available system resources (such as hardware logic), and partial RTR allows customization of the logic during application execution to better satisfy application requirements such as increased performance (shorter application execution time).; However, this feature imposes strict physical and architectural constraints making it very challenging for an application mapping approach to successfully exploit its potential. In this thesis, we first demonstrate that even for the simplest form of partial RTR, i.e., columnar partial RTR, the traditional application mapping steps of partitioning (and scheduling) followed by placement results in physically unrealizable designs. We propose the first integrated application mapping strategy that guarantees physically realizable designs. Our proposed approach is computationally efficient and we demonstrate that it generates high-quality results with experiments over a large design space that includes synthetic experiments and a detailed application case study.; Next, we extend our approach with detailed considerations of key characteristics of typical applications executed on such devices. We specifically focus on data-parallelism property of typical image-processing tasks. Thus, our proposed strategy goes beyond simple application mapping by including application restructuring as an integral step. Our approach enables an application to effectively adapt to its run-time environment by including the input image size and logic resource availability as key parameters available only when the application is ready to execute. Given our goal of enabling run-time customization, the execution time of our approach needs to be low enough for inclusion in a run-time scheduler. We therefore propose a low-execution-complexity heuristic with local optimizations that generates good-quality schedules. We confirm the applicability of our approach in a run-time scheduling environment with detailed analysis of execution time estimates on a typical embedded processor. Last but not the least, our proposed approach addresses key practical issues such as bandwidth availability, power concerns, etc.; We demonstrate the validity of our proposed approach with experimental date, obtained from a cycle-accurate simulation platform. Our simulation platform includes detailed system implementation considerations such as bus contention, memory RAS/CAS timing, routing implications of partial RTR, etc. Experimental data from a set of image-filtering benchmarks (Sobel filter, Laplace filter, etc.) confirm that even with detailed consideration of the large set of constraints imposed by partial RTR, our approach is successful in exploiting this capability to better satisfy application performance/power requirements.