Revisiting the decomposition of Karp, Miller and Winograd
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
This paper is devoted to the construction of multi-dimensional schedules for a system of uniform recurrence equations. We show that this problem is dual to the problem of computability of a system of uniform recurrence equations. We propose a new study of the decomposition algorithm first proposed by Karp, Miller and Winograd: we base our implementation on linear programming resolutions whose duals give exactly the desired multi-dimensional schedules. Furthermore, we prove that the schedules built this way are optimal up to a constant factor.Keywords
This publication has 7 references indexed in Scilit:
- Some efficient solutions to the affine scheduling problem. Part II. Multidimensional timeInternational Journal of Parallel Programming, 1992
- LINEAR SCHEDULING IS NEARLY OPTIMALParallel Processing Letters, 1991
- Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphsPublished by Association for Computing Machinery (ACM) ,1989
- Detecting cycles in dynamic graphs in polynomial timePublished by Association for Computing Machinery (ACM) ,1988
- Automatic synthesis of systolic arrays from uniform recurrent equationsACM SIGARCH Computer Architecture News, 1984
- The parallel execution of DO loopsCommunications of the ACM, 1974
- The Organization of Computations for Uniform Recurrence EquationsJournal of the ACM, 1967