Mapping Loop Structures onto Parametrized Hardware Pipelines

Abstract — This paper shows how a general form of algorithms consisting of a loop with loop dependencies carried from one iteration to the next can automatically be mapped to a para-metric hardware design with pipelining and replication features. A technology-independent parametric model of the proposed design is developed to capture the variations of area and throughput with the number of pipeline stages and replications. Our model allows rapid optimization of design parameters by a few pre-synthesis operations. We present an optimization method based on the model. Our method is evaluated using three different applications implemented on a Xilinx Spartan 6 XC6SLX45T FPGA: a carry-save adder-based Montgomery multiplier, a modular exponentiation module, and an integer square root module. Our model facilitates design space exploration; it can quickly predict the area taken by our designs with less than 5% of error, and their maximum frequencies and throughputs with less than 22 % of error. Our optimization method is up to 96 times faster than a full search through the design space. Index Terms — Design space exploration, field-programmable gate array (FPGA), hardware mapping, loop-carried dependen