Heurísticas híbridas para escalonamento estático de tarefas em sistemas com processadores heterogêneos

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorOchi, Luiz Satoru-
Autor(es): dc.contributorCPF:31609080822-
Autor(es): dc.contributorhttp://lattes.cnpq.br/9171815778534257-
Autor(es): dc.contributorBoeres, Maria Cristina Silva-
Autor(es): dc.contributorCPF:29609077322-
Autor(es): dc.contributorhttp://lattes.cnpq.br/0306766365983082-
Autor(es): dc.contributorRebello, Eugene Francis Vinod-
Autor(es): dc.contributorCPF:29509088322-
Autor(es): dc.contributorhttp://lattes.cnpq.br/8795680989708219-
Autor(es): dc.contributorProtti, Fábio-
Autor(es): dc.contributorCPF:28907060422-
Autor(es): dc.contributorhttp://lattes.cnpq.br/5898801580033554-
Autor(es): dc.contributorBoeres, Maria Claudia Silva-
Autor(es): dc.contributorCPF:32410090822-
Autor(es): dc.contributorhttp://lattes.cnpq.br/0528154281423964-
Autor(es): dc.creatorRios, Eyder Franco Sousa-
Data de aceite: dc.date.accessioned2024-07-11T17:43:01Z-
Data de disponibilização: dc.date.available2024-07-11T17:43:01Z-
Data de envio: dc.date.issued2021-03-10-
Data de envio: dc.date.issued2008-03-19-
Data de envio: dc.date.issued2021-03-10-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/17115-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/756011-
Descrição: dc.descriptionThe utilization of existing resources in distributed computing systems with adequate allocation of parallel application's components is not an elementary is- sue. Such process constitutes the Task Scheduling Problem which is in general a NP-complete problem, and it has been explored in specialized literature. The com- plexity of this problem has motivated the development of heuristic methods to solve it, in which algorithms within the list scheduling class constitute commonly used me- chanisms. However, the greedy characteristic of such heuristics can, in many cases, contribute negatively on the achievmento of the best solution. This work investiga- tes the applicability of the integration of List Scheduling class heuristics with search mechanisms based on meta-heuristics. The goal is to combine meta-heuristics search power with low-complexity of List Scheduling heuristics for generating efficient sche- dules on distributed computing systems, in which resources are heterogeneous, in general. For this, two heuristics are proposed: HTSGA and HTSG, which are based on Genetic Algorithm and GRASP, respectively. The search mechanisms implemen- ted in such heuristics aims to eliminate the greedy behaviour of List Scheduling algorithm, providing new scheduling possibilities by determinating different task al- location sequences during the solution construction. Moreover, it was investigated the possibility of adapting proposed heuristics to different parallel application clas- ses. To validate this work, the solutions generated by the proposed heuristics were compared with traditional construction algorithms presented in the literature and to a meta-heuristic which was the basis of this work. The results showed that the proposed algorithms are robust both related to adaptability to characteristics of the submitted instances and to quick convergency to sub-optimal solutions.-
Descrição: dc.descriptionA exploração dos recursos existentes em sistemas computacionais distribuí- dos através da alocação adequada dos componentes de aplicações paralelas não é um processo elementar. Tal procedimento constitui o Problema de Escalonamento de Tarefas que é, em sua forma geral, um problema NP-Completo e tem sido bastante explorado pela literatura especializada. A alta complexidade deste problema tem incentivado a pesquisa de métodos heurísticos para sua resolução, onde algoritmos da classe list scheduling constituem mecanismos comumente empregados. Todavia, a característica inerentemente gulosa destas heurísticas pode, em muitos casos, con- tribuir negativamente para o desempenho destes algoritmos. Este trabalho investiga a aplicabilidade da integração de heurísticas da classe list scheduling com mecanis- mos de busca baseados em metaheurísticas. O objetivo é combinar o poder de busca das metaheurísticas com a baixa complexidade de heurísticas list scheduling para a geração de escalonamentos eficientes em sistemas computacionais distribuídos, cujos recursos são geralmente heterogêneos. Para tanto, são propostas duas heurísticas denominadas HTSGA e HTSG baseadas, respectivamente, em Algoritmo Genético e GRASP. O mecanismo de busca implementado por estas heurísticas procura eli- minar o comportamento guloso dos algoritmos list scheduling fornecendo novas pos- sibilidades de escalonamento através da determinação de diferentes seqüências de atribuição de tarefas durante a construção de soluções. Além disso, foi investi- gada a possibilidade de adaptação das heurísticas propostas a diferentes classes de aplicações paralelas. Como forma de validação deste trabalho, o desempenho das heurísticas propostas foi comparado com algoritmos de construção tradicionais exis- tente na literatura e com uma metaheurística que serviu de base para este trabalho. Os resultados mostraram que os algoritmos propostos são robustos tanto em rela- ção à adaptabilidade às características das instâncias submetidas quanto na rápida convergência para soluções sub-ótimas.-
Formato: dc.formatapplication/pdf-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherPrograma de Pós-Graduação em Computação-
Publicador: dc.publisherComputação-
Direitos: dc.rightsAcesso Aberto-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectCiência da computação-
Palavras-chave: dc.subjectAlgoritmo genético-
Palavras-chave: dc.subjectProcessador de escalonamento de tarefa-
Palavras-chave: dc.subjectEscalonamento de tarefas-
Palavras-chave: dc.subjectEscalonamento estático de tarefas-
Palavras-chave: dc.subjectOtimização-
Palavras-chave: dc.subjectProcessamento paralelo-
Palavras-chave: dc.subjectMetaheurística-
Palavras-chave: dc.subjectAlgoritmo genético-
Palavras-chave: dc.subjectGRASP-
Palavras-chave: dc.subjectStatic task scheduling-
Palavras-chave: dc.subjectMetaheuristics-
Palavras-chave: dc.subjectGenetic algorithm-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO-
Título: dc.titleHeurísticas híbridas para escalonamento estático de tarefas em sistemas com processadores heterogêneos-
Título: dc.titleHybrid heuristics for static task scheduling in computing systems with heterogeneous processors-
Tipo de arquivo: dc.typeDissertação-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.