Accuracy of the Minimum Time Estimate for Programs on Heterogeneous Machines
Summary :
Parallelism on heterogeneous machines brings cost effectiveness, but also raises a new set of complex and challenging problems. This paper addresses the problem of estimating the minimum time taken to execute a program on a fine-grained parallel machine composed of different types of processors. In an earlier publication, we took the first step in this direction by presenting a graph-construction method which partitions a given program into several homogeneous parts and incorporates timing constraints due to heterogeneous parallelism into each part. In this paper, to make the method easier to be applied in a scheduling framework and to demonstrate its practical utility, we present an efficient implementation method and compare the results of its use to the optimal schedule lengths obtained by enumerating all possible solutions. Experimental results for several different machine models indicate that this method can be effectively used to estimate a program's minimum execution time.
- Publication
- IEICE TRANSACTIONS on Information Vol.E81-D No.1 pp.19-26
- Publication Date
- 1998/01/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Category
- Computer Systems
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Dingchao LI, Yuji IWAHORI, Naohiro ISHII, "Accuracy of the Minimum Time Estimate for Programs on Heterogeneous Machines" in IEICE TRANSACTIONS on Information,
vol. E81-D, no. 1, pp. 19-26, January 1998, doi: .
Abstract: Parallelism on heterogeneous machines brings cost effectiveness, but also raises a new set of complex and challenging problems. This paper addresses the problem of estimating the minimum time taken to execute a program on a fine-grained parallel machine composed of different types of processors. In an earlier publication, we took the first step in this direction by presenting a graph-construction method which partitions a given program into several homogeneous parts and incorporates timing constraints due to heterogeneous parallelism into each part. In this paper, to make the method easier to be applied in a scheduling framework and to demonstrate its practical utility, we present an efficient implementation method and compare the results of its use to the optimal schedule lengths obtained by enumerating all possible solutions. Experimental results for several different machine models indicate that this method can be effectively used to estimate a program's minimum execution time.
URL: https://global.ieice.org/en_transactions/information/10.1587/e81-d_1_19/_p
Copy
@ARTICLE{e81-d_1_19,
author={Dingchao LI, Yuji IWAHORI, Naohiro ISHII, },
journal={IEICE TRANSACTIONS on Information},
title={Accuracy of the Minimum Time Estimate for Programs on Heterogeneous Machines},
year={1998},
volume={E81-D},
number={1},
pages={19-26},
abstract={Parallelism on heterogeneous machines brings cost effectiveness, but also raises a new set of complex and challenging problems. This paper addresses the problem of estimating the minimum time taken to execute a program on a fine-grained parallel machine composed of different types of processors. In an earlier publication, we took the first step in this direction by presenting a graph-construction method which partitions a given program into several homogeneous parts and incorporates timing constraints due to heterogeneous parallelism into each part. In this paper, to make the method easier to be applied in a scheduling framework and to demonstrate its practical utility, we present an efficient implementation method and compare the results of its use to the optimal schedule lengths obtained by enumerating all possible solutions. Experimental results for several different machine models indicate that this method can be effectively used to estimate a program's minimum execution time.},
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - Accuracy of the Minimum Time Estimate for Programs on Heterogeneous Machines
T2 - IEICE TRANSACTIONS on Information
SP - 19
EP - 26
AU - Dingchao LI
AU - Yuji IWAHORI
AU - Naohiro ISHII
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E81-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 1998
AB - Parallelism on heterogeneous machines brings cost effectiveness, but also raises a new set of complex and challenging problems. This paper addresses the problem of estimating the minimum time taken to execute a program on a fine-grained parallel machine composed of different types of processors. In an earlier publication, we took the first step in this direction by presenting a graph-construction method which partitions a given program into several homogeneous parts and incorporates timing constraints due to heterogeneous parallelism into each part. In this paper, to make the method easier to be applied in a scheduling framework and to demonstrate its practical utility, we present an efficient implementation method and compare the results of its use to the optimal schedule lengths obtained by enumerating all possible solutions. Experimental results for several different machine models indicate that this method can be effectively used to estimate a program's minimum execution time.
ER -
English
