Automatic Hardware Synthesis of Nested Loops Using UET Grids and VHDL

摘要

This paper considers the automatic synthesis of systolic crchitectures from nested loop algoithmic specifications. The high level input is given in the form of uniform dependence loops with unit dependencies and the target architecture is a nultidimensional systolic array with unbounded number of cells. A complete methodology for the hardware synthesis of the resulting architecture, based on VHDL specifications, is presented. This mehtodology automaticlaly detects all necessary conputation and communication elements and produces optimal layouts. The theoretical frameworks of our method is based on the properties of the generalized UET grids. Frist, we calculate the optimal makespan for the achieve the optimal makespan. The complexity of the proposed scheduling algorithm is completely independent of the size of the nested loop and depends only on its dimension, thus being the most efficient (in terms of complexity) known to us. All these methods were implemented and incorporated in an integrated software package which provides the designer with a powerful parallel design environment. from high level algorithmic specifications to lowlevel(i.e. actual layouts) optimal implementation.