Synthesis of a new systolic architecture for the algebraic path problem (Q757083): Difference between revisions

The authors apply a method of systematic synthesis of systolic arrays based upon uniform recurrence equations developed by \textit{P. Quinton} [Automatic synthesis of systolic arrays from recurrent uniform equations, Proceedings 11th Annual International Symposium on Computer Architectures, Ann Arbor, MI, 208-214 (1984)], on a target example: the algebraic path problem (APP for short). The main result is a new systolic array for the APP, whose area-time performances overcome those of the many existing arrays [\textit{M. C. Chen}, J. Parallel Distributed Comput., 461-491 (1986)]. After describing the new systolic architecture, the authors show how to synthesize it using the above mentioned systematic methodology. Such a synthesis provides also a proof of the correctness of the architecture. The authors have verified the operation of the new systolic array using a program written in SISYC, which is a language for the simulation and the validation of systolic-algorithms, based on the mathematical model for the specification and verification of systolic networks due to \textit{R. G. Melhem} and \textit{W. C. Rheinboldt} [SIAM J. Comput. 13, 541-565 (1984; Zbl 0546.94031)]. A SISYC compiler and environment tools developed by \textit{A. Benaini} [Conception et validation es algorithmes systoliques, Thèse de l'Institut National Polytechnique de Grenoble, Grenoble, France (1988)] were used for the test.