Scheduling for Independent-Task Applications on Heterogeneous Parallel Computing Environments under the Unidirectional One-Port Model

Fukuhito OOSHITA; Susumu MATSUMAE; Toshimitsu MASUZAWA

doi:10.1093/ietisy/e90-d.2.403

Scheduling for Independent-Task Applications on Heterogeneous Parallel Computing Environments under the Unidirectional One-Port Model

Fukuhito OOSHITA, Susumu MATSUMAE, Toshimitsu MASUZAWA

Full Text Views

0

Cite this

Summary :

For execution of computation-intensive 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.

Publication: IEICE TRANSACTIONS on Information Vol.E90-D No.2 pp.403-417

Publication Date: 2007/02/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1093/ietisy/e90-d.2.403

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)

Category: Parallel and Distributed Computing

Cite this

Copy

Fukuhito OOSHITA, Susumu MATSUMAE, Toshimitsu MASUZAWA, "Scheduling for Independent-Task Applications on Heterogeneous Parallel Computing Environments under the Unidirectional One-Port Model" in IEICE TRANSACTIONS on Information, vol. E90-D, no. 2, pp. 403-417, February 2007, doi: 10.1093/ietisy/e90-d.2.403.
Abstract: For execution of computation-intensive 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.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e90-d.2.403/_p

Copy

@ARTICLE{e90-d_2_403,
author={Fukuhito OOSHITA, Susumu MATSUMAE, Toshimitsu MASUZAWA, },
journal={IEICE TRANSACTIONS on Information},
title={Scheduling for Independent-Task Applications on Heterogeneous Parallel Computing Environments under the Unidirectional One-Port Model},
year={2007},
volume={E90-D},
number={2},
pages={403-417},
abstract={For execution of computation-intensive 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.},
keywords={},
doi={10.1093/ietisy/e90-d.2.403},
ISSN={1745-1361},
month={February},}

Copy

TY - JOUR
TI - Scheduling for Independent-Task Applications on Heterogeneous Parallel Computing Environments under the Unidirectional One-Port Model
T2 - IEICE TRANSACTIONS on Information
SP - 403
EP - 417
AU - Fukuhito OOSHITA
AU - Susumu MATSUMAE
AU - Toshimitsu MASUZAWA
PY - 2007
DO - 10.1093/ietisy/e90-d.2.403
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E90-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2007
AB - For execution of computation-intensive 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.
ER -