A Theory for Automated Synthesis of Architectures for Repetitive Multi-RateAlgorithms
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 translation from DDGs to architectures. Analytic techniques are introduced to extract design information from the DDGs. Synthesis problems are formulated, and heuristic approaches are suggested for their solution. An implementation of a heuristic synthesis system is described. The implementation is evaluated via experiments.