Partitioning considerations in systolic array design

Efficient scheduling techniques are developed for methods in partitioning problems that do not match the array size exactly. In particular, scheduling for the locally-parallel-globally-sequential (LPGS) technique and the locally-sequential-globally-parallel (LSGP) technique are developed. The scheduling procedure exploits the fact that after LPGS and LSGP partitioning, the locality constraints get modified, allowing the use of certain interconnections that were not available before. The scheduling method allows development of a flexible scheduling order for LPGS that is useful in evaluating a trade-off between execution time and the size of the partitioning buffers. The scheduling techniques are illustrated with the help of matrix multiplication and QR decomposition examples