Improved algorithms for partitioning problems in parallel, pipelined, and distributed computing

摘要

S.H. Bokhari (IEEE Trans. Comput., vol.37, p.48-57, 1988) has studied the assignment of the modules of a parallel program to the processors of a multiple-computer system. He proposed algorithms to solve optimally the following problems: (1) partition chain-structured parallel or pipelined programs over chain-connected systems; (2) partition multiple chain-structured parallel or pipelined programs over single-host multiple satellite systems; (3) partition multiple arbitrarily structured serial programs over single-host multiple-satellite systems; (4) partition single-tree structured parallel or pipelined programs over single-host multiple identical satellite systems. The authors solve here problem 1 by dynamic programming and problem 2 by sorting and using bisection search for the bottleneck value. They also note that Bokhari's algorithms for problems 3 and 4 can be improved by using recent results of G. Gallo et al. (1989), and by implementing E.W. Dijkstra's (1959) algorithm, which is used as a subroutine, with a heap structure. The time complexity of all algorithms is thus reduced.