Performance evaluation of list based scheduling on heterogeneous systems

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2011

Autores

Hamid Arabnejad (Autor) FEUP; Jorge G. Barbosa (Autor) FEUP

Ata de Conferência Internacional

Título: HeteroPar'11

Páginas: 440-449

9th International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Platforms

Bordéus, 29 de Agosto de 2011

Indexação

ISI Proceedings

ISI Web of Science

Scopus

INSPEC

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Engenharia electrotécnica, electrónica e informática

CORDIS: Ciências Físicas > Matemática > Algoritmos

Outras Informações

DOI: 10.1007/978-3-642-29737-3-49

Abstract (EN): This paper addresses the problem of evaluating the schedules produced by list based scheduling algorithms, with metaheuristic algorithms. Task scheduling in heterogeneous systems is a NP-problem, therefore several heuristic approaches were proposed to solve it. These heuristics are categorized into several classes, such as list based, clustering and task duplication scheduling. Here we consider the list scheduling approach. The objective of this study is to assess the solutions obtained by list based algorithms to verify the space of improvement that new heuristics can have considering the solutions obtained with metaheuritcs that are higher time complexity approaches. We concluded that for a low Communication to Computation Ratio (CCR) of 0.1, the schedules given by the list scheduling approach is in average close to metaheuristic solutions. And for CCRs up to 1 the solutions are below 11\% worse than the metaheuristic solutions, showing that it may not be worth to use higher complexity approaches and that the space to improve is narrow.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Notas: LNCS 7155/2012

Nº de páginas: 10