Optimal mapping of systolic algorithms by regular instruction shifts
- 17 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 224-235
- https://doi.org/10.1109/asap.1994.331801
Abstract
This paper addresses the problem of determining efficient mappings of systems of affinerecurrence equations into regular arrays, in a nearly space-optimal fashion. A new nonlinear allocation technique is presented : the Instruction Shift. It allows to synthesize planarregular arrays without increasing the initial linear schedule. This technique is illustratedwith the LLCholesky factorization.Keywords
This publication has 10 references indexed in Scilit:
- Time optimal linear schedules for algorithms with uniform dependenciesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Calculus of space-optimal mappings of systolic algorithms on processor arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A design methodology for fixed-size systolic arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Synthesis of size-optimal toroïdal arrays for the Algebraic Path Problem: A new contributionParallel Computing, 1992
- Regular partitioning for synthesizing fixed-size systolic arraysIntegration, 1991
- Minimum distance: a method for partitioning recurrences for multiprocessorsIEEE Transactions on Computers, 1989
- Regular iterative algorithms and their implementation on processor arraysProceedings of the IEEE, 1988
- Automatic synthesis of systolic arrays from uniform recurrent equationsPublished by Association for Computing Machinery (ACM) ,1984
- The parallel execution of DO loopsCommunications of the ACM, 1974
- The Organization of Computations for Uniform Recurrence EquationsJournal of the ACM, 1967