Lower-bound complexity and high performance mechanism for scheduling dependent-tasks on heterogeneous grids

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F18%3A00335922" target="_blank" >RIV/68407700:21230/18:00335922 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21240/18:00335922

Výsledek na webu

<a href="https://ieeexplore.ieee.org/abstract/document/8316591" target="_blank" >https://ieeexplore.ieee.org/abstract/document/8316591</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/ITCE.2018.8316591" target="_blank" >10.1109/ITCE.2018.8316591</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Lower-bound complexity and high performance mechanism for scheduling dependent-tasks on heterogeneous grids

Popis výsledku v původním jazyce

List-scheduling caught the spotlights in solving the problem of task scheduling due to its simplicity, low time complexity and high performance. In general, most list-scheduling algorithms consist of two main phases, task prioritization phase and grid-nodes assignment phase. Performance of both phases has a direct influence on the overall algorithm performance. The performance of grid-nodes assignment mechanism may be enhanced using duplication-based heuristics that may lead to an increase in the mechanism complexity. Mainly three lower-bound complexity grid-nodes assignment mechanisms are presented in the literature. These mechanisms are non-insertion based, insertion based and reverse duplicator. This paper presents a lower-bound complexity grid-nodes assignment mechanism that works with any task prioritization mechanism. Random generated application graphs in addition to real world application graphs have been used to evaluate the performance of the proposed mechanism in terms of SLR, efficiency and quality of schedules. Based on the simulation results, the proposed mechanism outperforms the other three mechanisms.

Název v anglickém jazyce

Lower-bound complexity and high performance mechanism for scheduling dependent-tasks on heterogeneous grids

Popis výsledku anglicky

List-scheduling caught the spotlights in solving the problem of task scheduling due to its simplicity, low time complexity and high performance. In general, most list-scheduling algorithms consist of two main phases, task prioritization phase and grid-nodes assignment phase. Performance of both phases has a direct influence on the overall algorithm performance. The performance of grid-nodes assignment mechanism may be enhanced using duplication-based heuristics that may lead to an increase in the mechanism complexity. Mainly three lower-bound complexity grid-nodes assignment mechanisms are presented in the literature. These mechanisms are non-insertion based, insertion based and reverse duplicator. This paper presents a lower-bound complexity grid-nodes assignment mechanism that works with any task prioritization mechanism. Random generated application graphs in addition to real world application graphs have been used to evaluate the performance of the proposed mechanism in terms of SLR, efficiency and quality of schedules. Based on the simulation results, the proposed mechanism outperforms the other three mechanisms.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

20206 - Computer hardware and architecture

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

2018 International Conference on Innovative Trends in Computer Engineering (ITCE)

ISBN

978-1-5386-0879-1

ISSN

—

e-ISSN

—

Počet stran výsledku

7

Strana od-do

1-7

Název nakladatele

IEEE

Místo vydání

Piscataway, NJ

Místo konání akce

Aswan

Datum konání akce

19. 2. 2018

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000458532100001