List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table

• Tipo: Artigo em Revista Científica Internacional
• Data: 2014

Autores

Hamid Arabnejad (Autor) FEUP; Jorge Manuel Gomes Barbosa (Autor) FEUP

Revista

Título: IEEE Transactions on Parallel and Distributed Systems

Vol. 25 Nº 3

Páginas: 682-694

ISSN: 1045-9219

Editora: IEEE

Indexação

ISI Web of Science

Scopus

COMPENDEX

INSPEC

Classificação Científica

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

CORDIS: Ciências Tecnológicas > Engenharia > Engenharia de computadores

Outras Informações

DOI: 10.1109/TPDS.2013.57

Abstract (EN): Efficient application scheduling algorithms are important for obtaining high performance in heterogeneous computing systems. In this paper, we present a novel list-based scheduling algorithm called Predict Earliest Finish Time (PEFT) for heterogeneous computing systems. The algorithm has the same time complexity as the state-of-the-art algorithm for the same purpose, that is, O(v^2.p) for v tasks and p processors, but offers significant makespan improvements by introducing a look-ahead feature without increasing the time complexity associated with computation of an Optimistic Cost Table (OCT). The calculated value is an optimistic cost because processor availability is not considered in the computation. Our algorithm is only based on an OCT table that is used to rank tasks and for processor selection. The analysis and experiments based on randomly generated graphs with various characteristics and graphs of real-world applications show that the PEFT algorithm outperforms the state-of-the-art list-based algorithms for heterogeneous systems in terms of schedule length ratio, efficiency and frequency of best results.

Idioma: Inglês

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