Automatic latency-optimal design of FPGA-based systolic arrays

"Systolic" algorithms have been shown to be suitable for a very large range of structured problems (i.e., linear algebra, graph theory, computational geometry, number-theoretic algorithms, string matching, sorting/searching, dynamic programming, discreet mathematics). Usage of this systolic architecture class has not been widespread in the past, in part because programmable hardware that supported this computing paradigm was not cost-effective to build and no design tools existed. However, suitable hardware has begun to appear. Complex FPGAs now provide an adequate level of speed, density and programmability in the form of reconfigurable computers, boards, and chips with embedded computational support. Such hardware could allow rapid implementation and change of systolic algorithms leading to inexpensive "programmable" systolic array hardware. Furthermore, the architectural characteristics of much FPGA hardware matches that required by systolic processing, because this technology is constructed from tiling identical memory and logic blocks along with supporting mesh interconnection networks. The symbolic parallel algorithm development environment (SPADE) described here is being developed to allow a designer to easily and rapidly explore the design space of various systolic algorithm implementations so that FPGA system tradeoffs can be efficiently analyzed. The intention is to allow a user to specify his algorithm with traditional high-level code, set some architectural constraints and then view the results in a meaningful graphical format.