Please use this identifier to cite or link to this item: https://repositorio.ufrn.br/jspui/handle/123456789/27778
Title: Problema de mapeamento e roteamento: propostas de otimização bioinspiradas híbridas
Other Titles: Mapping and routing problem: proposals of hybrid bioinspired optimization
Authors: Rocha, Hiago Mayk Gomes de Araújo
Keywords: Problema do mapeamento e roteamento;Sistemas em chip multiprocessados;Redes em chip;Mapeamento estático;Mapeamento dinâmico;Math-heurísticas
Issue Date: 19-Jul-2019
Citation: ROCHA, Hiago Mayk Gomes de Araújo. Problema de mapeamento e roteamento: propostas de otimização bioinspiradas híbridas. 2019. 162f. Dissertação (Mestrado em Sistemas e Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2019.
Portuguese Abstract: MPSoCs baseados em NoCs são sistemas capazes de prover a execução de aplicações paralelas com alto desempenho devido ao seu paralelismo inerente. Contudo, para se obter alto desempenho nas execuções, é necessário um eficiente gerenciamento dos recursos disponíveis no sistema, como núcleos de processamento e canais de comunicação. Neste trabalho é abordado o Problema de Mapeamento de tarefas e Roteamento das comunicações (PMR), o qual une características de alocação de tarefas e roteamento para a construção de estratégias de otimização que reduzam a latência de comunicação. A formulação matemática do PMR é apresentada neste trabalho. Além disso, usando a parte de roteamento dessa formulação, são propostas três Math-Heurísticas bioinspiradas (Genético, Memético e Transgenético) para o mapeamento estático de tarefas. Essas estratégias apresentam abordagens gerais para encontrar soluções de mapeamento e dentro delas a parte de roteamento da formulação do PMR é usada como uma avaliação de fitness exato. No contexto de mapeamento dinâmico, são propostas duas heurísticas (TransCand e TransEndo) que usam a metáfora dos Algoritmos Transgenéticos (AT) para prover alocação de tarefas por demanda em tempo de execução. Todas as propostas de algoritmos deste trabalho foram implementados e seus resultados foram simulados em uma ferramenta de NoC. Além disso, também foram implementados quatro algoritmos da literatura para fins de comparação com as propostas apresentadas, sendo três para mapeamento estático e um para o dinâmico. Os resultados demonstram que as propostas que conseguem capturar mais profundamente as características da arquitetura são mais eficientes. Em específico para a alocação estática, o Transgenético apresenta melhores resultados de latência média e máxima. Já para a alocação dinâmica, ambas as propostas apresentam resultados satisfatórios. Contudo, o TransEndo se mostrou mais eficiente tanto no tempo de otimização quanto na qualidade das soluções geradas.
Abstract: NoC-based MPSoCs are systems able to provide high-performance execution of the parallel application due to its inherent parallelism. However, to obtains the high-performance execution it is necessary efficient available resource management in the system, such as processing cores and communication links. In this work, the task Mapping and communication Routing Problem (PMR) is addressed, which merge features of task allocations and communication routing to design optimization strategies that aim to reduce communication latency. The PMR mathematical formulation is presented in this work. Besides that, using the routing part of this formulation, three bioinspired Math-heuristics (Genetic, Memetic and Transgenetic) are proposed to the static task mapping. These strategies use a general approach to find mapping solutions and within them, the PMR formulation routing part is used as an exact fitness function evaluation. In the dynamic mapping context, two heurístics are proposed (TransCand and TransEndo), which use the Transgenetic Algorithms (AT) metaphor to provide by demand allocation task in execution time. All proposes of this work was implemented and its results were simulated using a NoC tool. Besides that, in order to provide comparisons, it was implemented four algorithms of the literature, being three of the static mapping and one of the dynamic mapping. The results show that approaches able to capture more deeply the features of the architecture are more efficient. More specifically to static allocation, the Transgenetic algorithm presents individual best results for average and maximum latency. Even to dynamic allocations, both propose present satisfactory results. However, the TransEndo shows to be more efficient as in optimization time as in generated solution quality.
URI: https://repositorio.ufrn.br/jspui/handle/123456789/27778
Appears in Collections:PPGSC - Mestrado em Sistemas e Computação

Files in This Item:
File Description SizeFormat 
Problemamapeamentoroteamento_Rocha_2019.pdf2,12 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.