Hardware Synthesis for Systems of Recurrence Equations with Multi Dimensional Schedule

Abstract — This paper introduces methods for extending the classical systolic synthesis methodology to multi-dimensional time. Multi-dimensional scheduling enables complex algorithms that do not admit linear schedules to be parallelized, but it requires the use of memories in the architecture. The synthesis of such an architecture requires the definition of an allocation function that maps the calculations on the processors, and memory functions that define where the data are stored during execution. As our approach targets custom VLSI architectures, we constrain the synthesis method to produce parallel ar-chitectures that that satisfy the computer owns rule, i.e., each processor computes the data which are stored in its local memory. We explain how to combine the allocation and memory functions in order to meet the computer owns rule, and we present an original mechanism for controlling the operation of the architecture. We detail the different steps needed to generate a HDL description of the architecture, and we illustrate our method on the matrix multiplication algorithm. We describe a structural VHDL program that has been derived and synthesized for a FPGA platform using these design principles. Our results show that the complexity added in each processor by the memories and the control is moderate and justifies in practice the use of such architectures