
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Scheduling for IndependentTask Applications on Heterogeneous Parallel Computing Environments under the Unidirectional OnePort Model
Fukuhito OOSHITA Susumu MATSUMAE Toshimitsu MASUZAWA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E90D
No.2
pp.403417 Publication Date: 2007/02/01
Online ISSN: 17451361
DOI: 10.1093/ietisy/e90d.2.403
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science) Category: Parallel and Distributed Computing Keyword: heterogeneous parallel computing environment, independent task, scheduling algorithm, steady state, collective communication,
Full Text: PDF(855.2KB)>>
Summary:
For execution of computationintensive applications, one of the most important paradigms is to divide the application into a large number of small independent tasks and execute them on heterogeneous parallel computing environments (abbreviated by HPCEs). In this paper, we aim to execute independent tasks efficiently on HPCEs. We consider the problem to find a schedule that maximizes the throughput of task execution for a huge number of independent tasks. First, for HPCEs where the network forms a directed acyclic graph, we show that we can find, in polynomial time, a schedule that attains the optimal throughput. Secondly, for arbitrary HPCEs, we propose an (+ε)approximation algorithm for any constant ε(ε>0). In addition, we also show that the framework of our approximation algorithm can be applied to other collective communications such as the gather operation.

