An Exact Synthesis Algorithm for Multi-loop Array Computations on Field Programmable Gate Arrays (FPGAs)

Nagaraj Shenoy, Prithviraj Banerjee, Alok Choudhary
Northwestern University

Mahmut Kandemir
Pennsylvania State University

March 2000

Abstract

Array intensive computations are characterized by processing of large arrays stored in the external memory in multiple loops. Synthesizing these computations onto FPGAs involves automatic translation of the behavioral description into state machines controlled by a clock such that the execution time of the program as a whole is the minimum and area requirement does not exceed a predefined limit. The synthesis algorithm also needs to efficiently sequence the array accesses taking into account memory access requirements such as pipelining.

In this report we present an MILP based algorithm that can optimally synthesize behavioral descriptions. It tries to minimize both execution time and area. Our algorithm not only looks at individual loops to exploit parallelism but also considers them together while deciding the clock. The overall execution time is minimized and not just the number of cycles or the cycle time. It also efficiently synthesizes memory accesses to fully exploit the memory pipelining. We compare the results of this algorithm with the the results generated by a heuristic based algorithm.

Gzipped Postscript version of the paper