An Algorithm for Finding the K-Best Allocations of a Tree Structured Program

✍ Scribed by A. Billionnet; S. Elloumi

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 592 KB
• Volume: 26
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1995.1061

✦ Synopsis

We consider the problem of allocating (n) tasks of a distributed program to (m) processors of a distributed system in order to minimize total communication and processing costs. If the intertask communication can be represented by a tree and if the communication costs are uniform, it is known that an optimal allocation can be determined in (O(\mathrm{~nm})) time. A (K)-optimal solution set (\mathbf{\Omega}=) (\left{A_{1}, \ldots, \mathbb{A}{K}\right}) of a given task allocation problem is a set of allocations such that no allocation (s) which is not contained in (\Omega) is better than any (A{i}, i=1, \ldots, K). In this paper, an algorithm is presented which computes a (K)-optimal set for the considered task allocation problem in (O(K n m)). 1995 Academic Press, lnc.