A theory for automated synthesis of architectures for repetitive algorithms
Sanjay R. Deshpande · 1990
A theoretical framework is developed to achieve automated architectural synthesis for data-independent, repetitive, multi-rate algorithms from their behavioral specifications. Multi-rate functions are formally defined. It is shown that systolic architectures for algorithms incorporating multi-rate functions make inefficient use of hardware components and that a multi-clock design style can produce more efficient architectures. A graph-oriented language, called Data Dependency Graphs (DDGs), is introduced to facilitate the specification of multi-rate computations. Computational semantics suitable for multi-rate computations are associated with the nodes and edges of the DDG. A compatible model for function execution by hardware components is proposed. A bus-based architectural scheme is also proposed. The synthesis process is seen as a translation from DDGs to an architecture. Analytic techniques are introduced to extract design information from the DDGs. Synthesis problems are formulated, and heuristic solutions are suggested for them. An implementation of a heuristic synthesis program is described. The implementation is evaluated via experiments.