Task assignment in host-satellite systems

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 166
  • Download : 0
This paper deals with the problem of assigning task modules of a program over a multiple computer 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.(13) However, the general n-processor problem (n > 3) in a fully connected system is known to be NP-complete.(14) A host-satellite system considered in this paper is composed of a powerful host processor p(o) and N homogeneous satellite processors p(k)'s, 1 less than or equal to k less than or equal to N, in which each satellite processor p(k) is connected to the host processor p(o) through a communication link. When any two satellite processors are to communicate with each other, the host processor p(o) must participate in the communication. Therefore, the interprocessor communication cost per unit of information transferred between any two satellite processors is twice as much as that between a satellite processor and the host processor p(o). In this paper, we propose an algorithm which finds an optimal assignment on a host-satellite system in polynomial time. A task assignment problem for a host-satellite system is first transformed into a network flow problem, and then solved by applying the well known network flow algorithm in time no worse than O(N M(3)), where N and M are the number of satellites and the number of modules, respectively.
Publisher
WORLD SCIENTIFIC PUBL CO PTE LTD
Issue Date
1996-06
Language
English
Article Type
Article
Keywords

LINEAR-ARRAY NETWORKS

Citation

JOURNAL OF CIRCUITS SYSTEMS AND COMPUTERS, v.6, no.3, pp.213 - 225

ISSN
0218-1266
DOI
10.1142/S0218126696000170
URI
http://hdl.handle.net/10203/74647
Appears in Collection
EE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0