Partitioning and Mapping Algorithms into Fixed Size Systolic Arrays
- 1 January 1986
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-35 (1) , 1-12
- https://doi.org/10.1109/tc.1986.1676652
Abstract
A technique for partitioning and mapping algorithms into VLSI systolic arrays is presented in this paper. Algorithm partitioning is essential when the size of a computational problem is larger than the size of the VLSI array intended for that problem. Computational models are introduced for systolic arrays and iterative algorithms. First, we discuss the mapping of algorithms into arbitrarily large size VLSI arrays. This mapping is based on the idea of algorithm transformations. Then, we present an approach to algorithm partitioning which is also based on algorithm transformations. Our approach to the partitioning problem is to divide the algorithm index set into bands and to map these bands into the processor space. The partitioning and mapping technique developed throughout the paper is summarized as a six step procedure. A computer program implementing this procedure was developed and some results obtained with this program are presented.Keywords
This publication has 7 references indexed in Scilit:
- Parallelism detection and transformation techniques useful for VLSI algorithmsJournal of Parallel and Distributed Computing, 1985
- On the design of algorithms for VLSI systolic arraysProceedings of the IEEE, 1983
- On the Analysis and Synthesis of VLSI AlgorithmsIEEE Transactions on Computers, 1982
- Pin Limitations and Partitioning of VLSI Interconnection NetworksIEEE Transactions on Computers, 1982
- Wavefront Array Processor: Language, Architecture, and ApplicationsIEEE Transactions on Computers, 1982
- Partitioned algorithms and VLSI structures for large-scale matrix computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- The Organization of Computations for Uniform Recurrence EquationsJournal of the ACM, 1967