Utilize este identificador para referenciar este registo:
https://hdl.handle.net/10216/97674
Autor(es): | Hamid Arabnejad Jorge Manuel Gomes Barbosa |
Título: | List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table |
Data de publicação: | 2014 |
Resumo: | Efficient application scheduling algorithms are important for obtaining high performance in heterogeneous computingsystems. In this paper, we present a novel list-based scheduling algorithm called Predict Earliest Finish Time (PEFT) forheterogeneous computing systems. The algorithm has the same time complexity as the state-of-the-art algorithm for the samepurpose, that is, O(v^2.p) for v tasks and p processors, but offers significant makespan improvements by introducing a look-aheadfeature without increasing the time complexity associated with computation of an Optimistic Cost Table (OCT). The calculatedvalue is an optimistic cost because processor availability is not considered in the computation. Our algorithm is only based on anOCT table that is used to rank tasks and for processor selection. The analysis and experiments based on randomly generatedgraphs 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 bestresults. |
Assunto: | Engenharia de computadores, Engenharia electrotécnica, electrónica e informática Computer engineering, Electrical engineering, Electronic engineering, Information engineering |
Áreas do conhecimento: | Ciências da engenharia e tecnologias::Engenharia electrotécnica, electrónica e informática Engineering and technology::Electrical engineering, Electronic engineering, Information engineering |
URI: | https://repositorio-aberto.up.pt/handle/10216/97674 |
Tipo de Documento: | Artigo em Revista Científica Internacional |
Condições de Acesso: | restrictedAccess |
Aparece nas coleções: | FEUP - Artigo em Revista Científica Internacional |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
64753.pdf Restricted Access | 624.71 kB | Adobe PDF | Request a copy from the Author(s) |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.