Header menu link for other important links
X
Static task allocation for heterogeneous distributed computing systems
S. Salvakumar
Published in Institute of Electrical and Electronics Engineers Inc.
1991
Volume: 3
   
Pages: 190 - 193
Abstract
In this paper, we investigate the problem of static task allocation of concurrent programs for heterogeneous distributed computing systems, i.e, given a set of n concurrent communicating processes and a two processor distributed computing system, in which each processor may have certain resources not available with the other processor (i.e., unique resources), to which processor should each module be assigned so as to maximize the throughput? Our problem is a variant of the task allocation problem considered by Stone2 in that we consider concurrent execution of the processes comprising the task. Also we explicitly consider the resource usage costs for each module thereby resulting in a more realistic model of the distributed system. This task allocation problem is NP-hard and hence, we provide an efficient heuristic algorithm for obtaining satisfactory suboptimal solution to it in a reasonable amount of computation time. Our algorithm works by constructing an augmented task graph and taking a load balanced mincut on it and has a time complexity of O((n+m)2) where m is the total number of unique resources in the two processor system. © 1991 IEEE.
About the journal
JournalData powered by TypesetIEEE Region 10 Annual International Conference, Proceedings/TENCON
PublisherData powered by TypesetInstitute of Electrical and Electronics Engineers Inc.
ISSN21593442
Open AccessNo
Concepts (13)
  •  related image
    Computational efficiency
  •  related image
    Computer control systems
  •  related image
    Concurrency control
  •  related image
    Heuristic algorithms
  •  related image
    COMMUNICATING PROCESS
  •  related image
    Computation time
  •  related image
    CONCURRENT EXECUTION
  •  related image
    Concurrent program
  •  related image
    Distributed computing systems
  •  related image
    Distributed systems
  •  related image
    Suboptimal solution
  •  related image
    Task allocation
  •  related image
    Distributed computer systems