A METHODOLOGY FOR PAST SCHEDULING OF PARTITIONED SYSTOLIC ALGORITHMS

Various methods for mapping signal processing algorithms into systolic arrays have been developed in the past few years. In this paper, effi cient scheduling techniques are developed for the partitioning problem , i.e. problems with size that do not match the array size. In particu lar, scheduling for the Locally Parallel-Globally Sequential (LPGS) te chnique and the Locally Sequential-Globally Parallel (LSGP) technique are developed. The scheduling procedure developed exploits the fact th at after LPGS and LSGP partitioning, the locality constraints are less stringent allowing for more flexibility in the choice of algorithms a nd inter-processor communication. A flexible scheduling order is devel oped that is useful in evaluating the trade-off between execution time and size of storage buffers. The benefits of the scheduling technique s are illustrated with the help of matrix multiplication and least squ ares examples.