Calculus of space-optimal mappings of systolic algorithms on processor arrays
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The authors present a method for the mapping of systolic algorithms that use the minimal number of processors. This method is based on geometrical interpretations on convex polyhedra in Z/sup n/. The authors present a recurrence equation model defining the target problems for systolic program derivation. Some geometrical tools on convex polyhedra in Z/sup n/ are given. They are first used to model systolic timing allocation in terms of geometrical structures, and then to deduce a processor array mapping method that automatically gives space-optimal mappings. The results are used to derive two space-optimal mappings of the Gaussian elimination algorithm.Keywords
This publication has 8 references indexed in Scilit:
- Systematic approaches to the design of algorithmically specified systolic arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Optimal Systolic Design for the Transitive Closure and the Shortest Path ProblemsIEEE Transactions on Computers, 1987
- An implemented method for incremental systolic designPublished by Springer Nature ,1987
- ADVIS: A Software Package for the Design of Systolic ArraysIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Drawing plane graphs nicelyActa Informatica, 1985
- Automatic synthesis of systolic arrays from uniform recurrent equationsPublished by Association for Computing Machinery (ACM) ,1984
- Why systolic architectures?Computer, 1982
- Efficient Planarity TestingJournal of the ACM, 1974