Journal article
Adaptive allocation of independent tasks to maximize throughput
IEEE transactions on parallel and distributed systems, v 18(10), pp 1420-1435
01 Oct 2007
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
In this paper, we consider the task allocation problem for computing a large set of equal-sized independent tasks on a heterogeneous computing system where the tasks initially reside on a single computer (the root) in the system. This problem represents the computation paradigm for a wide range of applications such as SETI@home and Monte Carlo simulations. We consider the scenario where the systems have a general graph-structured topology and the computers are capable of concurrent communications and overlapping communications with computation. We show that the maximization of system throughput reduces to a standard network flow problem. We then develop a decentralized adaptive algorithm that solves a relaxed form of the standard network flow problem and maximizes the system throughput. This algorithm is then approximated by a simple decentralized protocol to coordinate the resources adaptively. Simulations are conducted to verify the effectiveness of the proposed approach. For both uniformly distributed and power law distributed systems, a close-to-optimal throughput is achieved, and improved performance over a bandwidth-centric heuristic is observed. The adaptivity of the proposed approach is also verified through simulations.
Metrics
Details
- Title
- Adaptive allocation of independent tasks to maximize throughput
- Creators
- Bo Hong - Department of Electrical and Computer Engineering, Drexel University, United StatesViktor K. Prasanna - Department of Electrical Engineering, University of Southern California, United States
- Publication Details
- IEEE transactions on parallel and distributed systems, v 18(10), pp 1420-1435
- Publisher
- IEEE
- Number of pages
- 16
- Grant note
- US National Science Foundation
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Electrical and Computer Engineering; School of Engineering
- Web of Science ID
- WOS:000248943800006
- Scopus ID
- 2-s2.0-34648817298
- Other Identifier
- 991014632722104721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
Source: SDGs in the Output
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Computer Science, Theory & Methods
- Engineering, Electrical & Electronic