Independent partitioning of algorithms with uniform dependencies
Wentong Shang, J.A.B. Fortes · IEEE Transactions on Computers · 1992
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.>