Citation

Pineda, A. A. S.; Pecero, J. E; Huacuja, H. J. F.; Barbosa, J. J. G. and Bouvry, P An Iterative Local Search Algorithm for Scheduling Precedence-Constrained Applications on Heterogeneous Machines. In proceedings of the 6th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2013), 27 - 30 Aug 2013, Ghent, Belgium, pages 472-485, 2013.

Paper


Abstract

The paper deals with the problem of scheduling precedence-constrained applications on a distributed heterogeneous computing system with the aim of minimizing the response time or total execution time. The main contribution is a scheduling algorithm that promotes an iterative local search process. Due to a lack of generally accepted standard benchmarks for the evaluation of scheduling algorithms in the heterogeneous computing systems we also generate a benchmark of synthetic instances. The benchmark is composed of small size synthetic deterministic non-preemptive program graphs known in the literature. We compute the optimal solution and the global optimal value with an exact enumerative search method that explores all possible solutions. We compare the performance of the proposed local search algorithm with the optimal values. We have simulated the proposed algorithm using graphs obtained from real-world applications emphasizing the interest of the approach


pdf

You can download the pdf of this publication from here


doi

This publication does not have a doi, so we cannot provide a link to the original source

What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information



URL

This pubication does not have a URL associated with it.

The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.


Bibtex

@INPROCEEDINGS{2013-472-485-P, author = { A. A. Santiago Pineda and J. E. Pecero and H. J. Fraire Huacuja and J. J. Gonzalez Barbosa and P. Bouvry},
title = {An Iterative Local Search Algorithm for Scheduling Precedence-Constrained Applications on Heterogeneous Machines},
booktitle = {In proceedings of the 6th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2013), 27 - 30 Aug 2013, Ghent, Belgium},
year = {2013},
editor = {G. Kendall and B. McCollum and G. {Venden Berghe}},
pages = {472--485},
note = {Paper},
abstract = {The paper deals with the problem of scheduling precedence-constrained applications on a distributed heterogeneous computing system with the aim of minimizing the response time or total execution time. The main contribution is a scheduling algorithm that promotes an iterative local search process. Due to a lack of generally accepted standard benchmarks for the evaluation of scheduling algorithms in the heterogeneous computing systems we also generate a benchmark of synthetic instances. The benchmark is composed of small size synthetic deterministic non-preemptive program graphs known in the literature. We compute the optimal solution and the global optimal value with an exact enumerative search method that explores all possible solutions. We compare the performance of the proposed local search algorithm with the optimal values. We have simulated the proposed algorithm using graphs obtained from real-world applications emphasizing the interest of the approach},
owner = {Graham},
timestamp = {2017.01.16},
webpdf = {2013-472-485-P.pdf} }