Optimal Task Assignment in Hypercube Networks

Sang-Young CHO; Cheol-Hoon LEE; Myunghwan KIM

Optimal Task Assignment in Hypercube Networks

Sang-Young CHO, Cheol-Hoon LEE, Myunghwan KIM

Full Text Views

0

Share
Cite this

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 NP-complete 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 n-dimensional homogeneous hypercube network of N (=2ⁿ) processors and M tasks is first transformed into n two-terminal network flow problems, and then solved in time no worse than O(M³ log N) by applying the Goldberg-Tarjan's maximum flow algorithm on each two-terminal network flow problem.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E75-A No.4 pp.504-511

Publication Date: 1992/04/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on Discrete Mathematics and Its Application)

Category

Cite this

Copy

Sang-Young CHO, Cheol-Hoon LEE, Myunghwan KIM, "Optimal Task Assignment in Hypercube Networks" in IEICE TRANSACTIONS on Fundamentals, vol. E75-A, no. 4, pp. 504-511, April 1992, doi: .
Abstract: 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 NP-complete 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 n-dimensional homogeneous hypercube network of N (=2ⁿ) processors and M tasks is first transformed into n two-terminal network flow problems, and then solved in time no worse than O(M³ log N) by applying the Goldberg-Tarjan's maximum flow algorithm on each two-terminal network flow problem.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e75-a_4_504/_p

Copy

@ARTICLE{e75-a_4_504,
author={Sang-Young CHO, Cheol-Hoon LEE, Myunghwan KIM, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Optimal Task Assignment in Hypercube Networks},
year={1992},
volume={E75-A},
number={4},
pages={504-511},
abstract={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 NP-complete 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 n-dimensional homogeneous hypercube network of N (=2ⁿ) processors and M tasks is first transformed into n two-terminal network flow problems, and then solved in time no worse than O(M³ log N) by applying the Goldberg-Tarjan's maximum flow algorithm on each two-terminal network flow problem.},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - Optimal Task Assignment in Hypercube Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 504
EP - 511
AU - Sang-Young CHO
AU - Cheol-Hoon LEE
AU - Myunghwan KIM
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E75-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1992
AB - 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 NP-complete 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 n-dimensional homogeneous hypercube network of N (=2ⁿ) processors and M tasks is first transformed into n two-terminal network flow problems, and then solved in time no worse than O(M³ log N) by applying the Goldberg-Tarjan's maximum flow algorithm on each two-terminal network flow problem.
ER -