Systolic algorithms for some scheduling and graph problems
Óscar H. Ibarra, Tao Jiang, Jung Hwan Chang, Michael A. Palis · 1988
A simple model of a linear systolic array with serial input/output and one-way data communication is considered. It is shown that such an array can be used to solve some scheduling and graph problems efficiently. The systolic algorithms are developed in two stages. First an algorithm on a restricted type of sequential machine is constructed. Then the sequential machine algorithm is transformed into a systolic algorithm. The transformation can be done automatically and efficiently.>