Allocating tree structured programs in a distributed system with uniform communication costs
Alain Billionnet · IEEE Transactions on Parallel and Distributed Systems · 1994
Studies the complexity of the problem of allocating m modules to n processors in a distributed system to minimize total communication and execution costs. When the communication graph is a tree, Bokhari has shown that the optimum allocation can be determined in O(mn/sup 2/) time. Recently, this result has been generalized by Fernandez-Baca, who has proposed an allocation algorithm in O(mn/sup k+1/) when the communication graph is a partial k-tree. The author shows that in the case where communication costs are uniform, the module allocation problem can be solved in O(mn) time if the communication graph is a tree. This algorithm is asymptotically optimum.>