The demand for high-speed computation in many digital signal processing (DSP) and scientific application and the availability of low cost, high speed, high density VLSI technology have provided a new dimension in implementing architectures, particularly the evolvement of algorithm- based application-specific architectures. Systolic array is one class of such architectures that exploits the strength of VLSI and is particularly suitable for implementing many DSP algorithms which are well-structured and locally recursive. As demand in speed and application rises, many systolic arrays have become more complex in terms of cell structure, interconnection topology, and data flow. Complete, precise, and formal description of architectures has become vital for unambiguous and complete communication among designers and implementers, as well as for formal verification of design correctness. The main objective of the research is to fully develop a solid formalism and apply it to systolic array level specification and design verification: (1) The formalism must provide simple, and yet complete and precise description (specification) of any systolic structure and behavior; (2) the formalism and related techniques developed must exploit unique attributes of systolic arrays ( synchrony, modularity, regularity, spatial and temporal locality, pipelinability, repeatability, and parallel processing ability) to produce notations and verification procedures that are simple, elegant, and efficient; (3) the constructs and operators involved should preferably be able to be unified with one useful lower level formalism for coherent multilevel reasoning; (4) the techniques should be automated and developed into a CAD tool eventually; (5) the formalism must be further expanded for synthesis description and design debugging. The proposed research will be carried out through rigorous and comprehensive survey, theoretical analysis, design, and implementation.
