
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Optimal Task Assignment in Hypercube Networks
SangYoung CHO CheolHoon LEE Myunghwan KIM
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E75A
No.4
pp.504511 Publication Date: 1992/04/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Issue on Discrete Mathematics and Its Application) Category: Keyword: combinatorial algorithm, homogeneous network, hypercube network, maximum flow, minimum cut, network flow, optimal algorithm, task assignment,
Full Text: PDF>>
Summary:
This paper deals with the problem of assigning tasks to the processors of a multiprocessor system such that the sum of execution and communication costs is minimized. If the number of processors is two, this problem can be solved efficiently using the network flow approach pioneered by Stone. This problem is, however, known to be NPcomplete in the general case, and thus intractable for systems with a large number of processors. In this paper, we propose a network flow approach for the task assignment problem in homogeneous hypercube networks, i.e., hypercube networks with functionally identical processors. The task assignment problem for an ndimensional homogeneous hypercube network of N (=2^{n}) processors and M tasks is first transformed into n twoterminal network flow problems, and then solved in time no worse than O(M^{3} log N) by applying the GoldbergTarjan's maximum flow algorithm on each twoterminal network flow problem.

