Drexel University Home Pagewww.drexel.edu DREXEL UNIVERSITY LIBRARIES HOMEPAGE >>

iDEA: Drexel E-repository and Archives > Drexel Academic Community > College of Engineering > Department of Electrical and Computer Engineering > Faculty Research and Publications (ECE) > Adaptive allocation of independent tasks to maximize throughput

Please use this identifier to cite or link to this item: http://hdl.handle.net/1860/2544

Title: Adaptive allocation of independent tasks to maximize throughput
Authors: Hong, Bo
Prasanna, Viktor K.
Keywords: Task Allocation;Heterogeneous Computing;Network Flow;Decentralized Algorithm;Throughput
Issue Date: Oct-2007
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Citation: IEEE Transactions on Parallel And Distributed Systems, 18(10): pp. 1420-1435.
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.
URI: http://dx.doi.org/10.1109/TPDS.2007.1042
Appears in Collections:Faculty Research and Publications (ECE)

Files in This Item:

File Description SizeFormat
2007005128.pdf1.42 MBAdobe PDFView/Open
View Statistics

Items in iDEA are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! iDEA Software Copyright © 2002-2010  Duraspace - Feedback