General methodology for mapping iterative approximation algorithms to adaptive dynamically partially reconfigurable systems

This paper presents a general methodology for mapping a class of algorithms known as iterative algorithms to FPGA-based dynamically partially reconfigurable architectures in an adaptive and efficient manner. Hereby, each iteration step is mapped to a partial module on the FPGA, and modules can be added or removed to these connected modules on the FPGA dynamically using partial reconfiguration. The more modules and iteration steps, respectively, are concurrently executed on the FPGA, the higher the achieved through-put due to exploitation of pipelining in the design. Especially, numerical approximation algorithms allow a trade-off between precision of the final result and the execution time, and benefit by the proposed mapping methodology: When mapping an element of that class of algorithms to a partially dynamically reconfigurable platform, the number of modules can be increased or decreased at runtime depending on the desired quality of the results and the available area. Thus, the proposed general mapping methodology provides an acceleration of an important class of algorithms due to the execution in hardware, and allows at runtime a trade-off decision between execution time and quality of the results. Furthermore, a detailed description of an experimental implementation of a square root calculation on a reconfigurable platform is given as a prototype example to explain and show the benefits of the proposed approach.