Title :
Dynamic task assignment in heterogeneous linear array networks for metacomputing
Author :
Cho, Sang-Young ; Park, Kyu Ho
Author_Institution :
Dept. of Electr. Eng., Korea Adv. Inst. of Sci. & Technol., Seoul, South Korea
Abstract :
In a heterogeneous computing system, the tasks of a program must be assigned to the heterogeneous machines so as to utilize the computational capabilities and resources of the system efficiently. This paper deals with a dynamic task assignment problem in heterogeneous computing systems, which permits each task to be relocated from machine to machine during the execution of a program. This problem is known to be NP-complete in the general case. In this paper, we extend the network-flow approach of C.-H. Lee, D. Lee and M. Kim (1992) to dynamic assignment for metacomputing. The dynamic assignment problem for a linear array network is first transformed into the network flow problem, and then solved by applying the Goldberg-Tarjan´s (1988) network flow algorithm in time not worse than O(n2m2φ2 log nmφ), where n, m, and φ are the numbers of machines, tasks, and phases of program execution, respectively
Keywords :
computational complexity; distributed processing; resource allocation; NP-complete problem; computational capabilities; dynamic task assignment; heterogeneous computing system; heterogeneous linear array networks; metacomputing; network flow algorithm; program execution; program task assignment; resource utilization; task relocation; Computer networks; Concurrent computing; Costs; Distributed computing; Embedded computing; Intelligent networks; Metacomputing; Parallel processing; Phased arrays; Tree graphs;
Conference_Titel :
Heterogeneous Computing Workshop, 1994., Proceedings
Conference_Location :
Cancun
Print_ISBN :
0-8186-5592-5
DOI :
10.1109/HCW.1994.324960