Synthesis of a new systolic architecture for the algebraic path problem
type: Item
instance of: scholarly article
title: Synthesis of a new systolic architecture for the algebraic path problem
zbMATH Open document ID: 0723.68076
DOI: 10.1016/0167-6423(90)90082-O
author: Abdelhamid Benaini
author: Yves Robert
author: Patrice Quinton
author: Yannick Saouter
author: Bernard Tourancheau
published in: Science of Computer Programming
publication date: 1990-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q80
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68M01
Mathematics Subject Classification ID: 68W15
zbMATH DE Number: 4193144
zbMATH Keywords: recurrent uniform equations
zbMATH Keywords: synthesis of systolic arrays
zbMATH Keywords: algebraic path problem
MaRDI profile type: Publication
Recommended article: Synthesizing systolic arrays from recurrence equations
Recommended article: Automatic verification of a class of systolic circuits
Recommended article: Q3741035
Recommended article: Q4023844
Recommended article: Q3768390
Recommended article: Q3727375
Recommended article: Generic systolic arrays: A methodology for systolic design
Recommended article: Q5699481
description: scientific article; zbMATH DE number 4193144