The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Um programa paralelo com um grau fixo de paralelismo não pode ser executado de forma eficiente, ou de todo, por um computador paralelo com um grau diferente de paralelismo. Isto causará um problema na distribuição de aplicações de software num futuro próximo, quando computadores paralelos com vários graus de paralelismo forem amplamente utilizados. Neste artigo propomos uma forma de tornar o código de máquina dos programas independente do paralelismo, ou seja, executável em tempo mínimo em computadores paralelos com qualquer grau de paralelismo. Propomos e avaliamos três algoritmos de escalonamento independentes de paralelismo para grafos acíclicos diretos (DAGs) de tarefas com tempos de execução não uniformes. Para comprovar sua eficiência, realizamos simulações tanto com DAGs aleatórios quanto com DAGs extraídos de aplicações reais. Nós os avaliamos em termos de duração do cronograma, tempo de cálculo e tamanho do programa agendado. Seus resultados são comparados aos do algoritmo tradicional CP/MISF que é usado separadamente para cada número de processadores.
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.
Copiar
Kirilka NIKOLOVA, Atusi MAEDA, Masahiro SOWA, "Proposition and Evaluation of Parallelism-Independent Scheduling Algorithms for DAGs of Tasks with Non-Uniform Execution Times" in IEICE TRANSACTIONS on Fundamentals,
vol. E84-A, no. 6, pp. 1496-1505, June 2001, doi: .
Abstract: A parallel program with a fixed degree of parallelism cannot be executed efficiently, or at all, by a parallel computer with a different degree of parallelism. This will cause a problem in the distribution of software applications in the near future when parallel computers with various degrees of parallelism will be widely used. In this paper we propose a way to make the machine code of the programs parallelism-independent, i.e. executable in minimum time on parallel computers with any degree of parallelism. We propose and evaluate three parallelism-independent scheduling algorithms for direct acyclic graphs (DAGs) of tasks with non-uniform execution times. To prove their efficiency, we performed simulations both with random DAGs and DAGs extracted from real applications. We evaluate them in terms of schedule length, computation time and size of the scheduled program. Their results are compared to those of the traditional CP/MISF algorithm which is used separately for each number of processors.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_6_1496/_p
Copiar
@ARTICLE{e84-a_6_1496,
author={Kirilka NIKOLOVA, Atusi MAEDA, Masahiro SOWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Proposition and Evaluation of Parallelism-Independent Scheduling Algorithms for DAGs of Tasks with Non-Uniform Execution Times},
year={2001},
volume={E84-A},
number={6},
pages={1496-1505},
abstract={A parallel program with a fixed degree of parallelism cannot be executed efficiently, or at all, by a parallel computer with a different degree of parallelism. This will cause a problem in the distribution of software applications in the near future when parallel computers with various degrees of parallelism will be widely used. In this paper we propose a way to make the machine code of the programs parallelism-independent, i.e. executable in minimum time on parallel computers with any degree of parallelism. We propose and evaluate three parallelism-independent scheduling algorithms for direct acyclic graphs (DAGs) of tasks with non-uniform execution times. To prove their efficiency, we performed simulations both with random DAGs and DAGs extracted from real applications. We evaluate them in terms of schedule length, computation time and size of the scheduled program. Their results are compared to those of the traditional CP/MISF algorithm which is used separately for each number of processors.},
keywords={},
doi={},
ISSN={},
month={June},}
Copiar
TY - JOUR
TI - Proposition and Evaluation of Parallelism-Independent Scheduling Algorithms for DAGs of Tasks with Non-Uniform Execution Times
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1496
EP - 1505
AU - Kirilka NIKOLOVA
AU - Atusi MAEDA
AU - Masahiro SOWA
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E84-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2001
AB - A parallel program with a fixed degree of parallelism cannot be executed efficiently, or at all, by a parallel computer with a different degree of parallelism. This will cause a problem in the distribution of software applications in the near future when parallel computers with various degrees of parallelism will be widely used. In this paper we propose a way to make the machine code of the programs parallelism-independent, i.e. executable in minimum time on parallel computers with any degree of parallelism. We propose and evaluate three parallelism-independent scheduling algorithms for direct acyclic graphs (DAGs) of tasks with non-uniform execution times. To prove their efficiency, we performed simulations both with random DAGs and DAGs extracted from real applications. We evaluate them in terms of schedule length, computation time and size of the scheduled program. Their results are compared to those of the traditional CP/MISF algorithm which is used separately for each number of processors.
ER -