id cris-123456789-1299
recordtype dspacecris
spelling cris-123456789-12992018-02-08T10:56:33Z DAG Scheduling using Integer Programming in heterogeneous parallel execution environments Βαλουξής, Χρήστος Γκόγκος, Χρήστος Αλεφραγκής, Παναγιώτης Γούλας, Γεώργιος Βώρος, Νικόλαος Χούσος, Ευθύμιος Scheduling--Computer programs Integer programming Scheduling DAG Directed Acyclic Graph Computer programs http://www.alma-project.eu/downloads/Mista2013.pdf A computer program can be represented by a Directed Acyclic Graph (DAG) in order to capture the dependencies between the individual tasks that should be executed each time the program runs. This paper proposes a mathematical model of Integer Programming that can be applied in order to schedule the tasks in the presence of multiple processors serving as the execution environment. The target is to minimize the overall execution time of the DAG known as schedule length or makespan. An approach called MATH using the full model is applied to small sized problems and then a more elaborate approach called MATHL is presented where the DAG is partitioned to levels. Levels are formed according to the hops needed for each node to be reached starting from the source node. Hence sub-problems have manageable size and can be solved in a timely manner. Consecutive optimal solutions for each level result in a high quality schedule for the overall problem even for cases consisting of several hundreds of nodes. Results show that this method constantly gives very good results and it is compared favorably with other approaches to the problem that can be found in the bibliography. 2013 Paper http://cris.teiep.gr/jspui/handle/123456789/1299 en MISTA 2013, Ghent, Belgium
institution T.E.I. of Epirus
collection DSpace CRIS
language English
topic Scheduling--Computer programs
Integer programming
Scheduling
DAG
Directed Acyclic Graph
Computer programs
spellingShingle Scheduling--Computer programs
Integer programming
Scheduling
DAG
Directed Acyclic Graph
Computer programs
Βαλουξής, Χρήστος
DAG Scheduling using Integer Programming in heterogeneous parallel execution environments
descriptionnotes http://www.alma-project.eu/downloads/Mista2013.pdf
abstract A computer program can be represented by a Directed Acyclic Graph (DAG) in order to capture the dependencies between the individual tasks that should be executed each time the program runs. This paper proposes a mathematical model of Integer Programming that can be applied in order to schedule the tasks in the presence of multiple processors serving as the execution environment. The target is to minimize the overall execution time of the DAG known as schedule length or makespan. An approach called MATH using the full model is applied to small sized problems and then a more elaborate approach called MATHL is presented where the DAG is partitioned to levels. Levels are formed according to the hops needed for each node to be reached starting from the source node. Hence sub-problems have manageable size and can be solved in a timely manner. Consecutive optimal solutions for each level result in a high quality schedule for the overall problem even for cases consisting of several hundreds of nodes. Results show that this method constantly gives very good results and it is compared favorably with other approaches to the problem that can be found in the bibliography.
format Paper
author Βαλουξής, Χρήστος
author-letter Βαλουξής, Χρήστος
author2 Γκόγκος, Χρήστος
Αλεφραγκής, Παναγιώτης
Γούλας, Γεώργιος
Βώρος, Νικόλαος
Χούσος, Ευθύμιος
author2Str Γκόγκος, Χρήστος
Αλεφραγκής, Παναγιώτης
Γούλας, Γεώργιος
Βώρος, Νικόλαος
Χούσος, Ευθύμιος
title DAG Scheduling using Integer Programming in heterogeneous parallel execution environments
title_short DAG Scheduling using Integer Programming in heterogeneous parallel execution environments
title_full DAG Scheduling using Integer Programming in heterogeneous parallel execution environments
title_fullStr DAG Scheduling using Integer Programming in heterogeneous parallel execution environments
title_full_unstemmed DAG Scheduling using Integer Programming in heterogeneous parallel execution environments
title_sort dag scheduling using integer programming in heterogeneous parallel execution environments
publishDate 2013
url http://cris.teiep.gr/jspui/handle/123456789/1299
conferencename MISTA 2013, Ghent, Belgium
_version_ 1646089570741125120
score 11.36895