Independent partitioning of algorithms with uniform dependencies

1 January 1992

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. 41 (2) , 190-206
https://doi.org/10.1109/12.123395

Abstract

Uniform dependence algorithms with arbitrary index sets are considered, and two computationally inexpensive methods to find their independent partitions are proposed. Each method has advantages over the other one for certain kinds of applications, and they both outperform previously proposed approaches in terms of computational complexity and/or optimality. Also, lower and upper bounds are given for the cardinality of maximal independent partitions. In multiple instruction multiple data (MIMD) systems, if different blocks of an independent partition are assigned to different processors, communications between processors will be minimized to zero. This is significant because the communications usually dominate the overhead in MIMD machines.

Keywords

This publication has 12 references indexed in Scilit:

Time optimal linear schedules for algorithms with uniform dependencies
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2003
Minimum distance: a method for partitioning recurrences for multiprocessors
IEEE Transactions on Computers, 1989
Parallel Supercomputing Today and the Cedar Approach
Science, 1986
Partitioning and Mapping Algorithms into Fixed Size Systolic Arrays
IEEE Transactions on Computers, 1986
Essential Issues in Multiprocessor Systems
Computer, 1985
On the design of algorithms for VLSI systolic arrays
Proceedings of the IEEE, 1983
High-Speed Multiprocessors and Compilation Techniques
IEEE Transactions on Computers, 1980
Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
SIAM Journal on Computing, 1979
Time and Parallel Processor Bounds for Fortran-Like Loops
IEEE Transactions on Computers, 1979
The Organization of Computations for Uniform Recurrence Equations
Journal of the ACM, 1967