Please use this identifier to cite or link to this item: http://monografias.ufrn.br/handle/123456789/4321
Title: O Problema do Mapeamento: Heurísticas de mapeamento de tarefas em MPSoCs baseados em NoC
Other Titles: The Mapping Problem
Authors: Rocha, Hiago Mayk Gomes de Araújo
Keywords: Sistema em Chip;Sistema em Chip Multiprocessado;Problema do Mapeamento;Heurísticas de Mapeamento
Issue Date: 14-Jun-2017
Publisher: Universidade Federal do Rio Grande do Norte
Citation: Rocha, Hiago Mayk Gomes de Araújo. O Problema do Mapeamento: Heurísticas de mapeamento para MPSOCs baseados em NoC. 2017. 109f. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação), Departamento de Informática e Matemática Aplicada, Universidade Federal do Rio Grande do Norte, Natal, 2017.
Portuguese Abstract: Com o avanço na tecnologia de fabricação de circuitos integrados, possibilitado pela diminuição do tamanho dos transistores, assim como previsto por Gordon Moore em 1975, tornou-se possível a criação de sistemas cada vez mais complexos em uma única pastilha de silício, denominados de Sistemas em Chip (SoC) que podem ser compostos por núcleos de processamento, memórias, dentre outros componentes. Contudo, devido ao aumento na complexidade das aplicações atuais, as quais em sua grande maioria, demandam mais poder de processamento e capacidade de execução simultânea de suas diferentes subpartes de processamento, foram desenvolvidos SoCs com múltiplos processadores, denominados de Sistemas em Chip Multiprocessados (MPSoCs), que tentam suprir tal necessidade das aplicações atuais. A comunicação entre os diferentes núcleos desses sistemas é dado por meio de arquiteturas de comunicação, as quais, as mais usadas ultimamente são as Redes em Chip (NoC) que entre outras vantagens, proveem o paralelismo nas comunicações. Devido à capacidade do MPSoC de executar aplicações em paralelo, surgem alguns desafios a serem tratados, tais como o problema de alocação, migração e escalonamento de tarefas. Neste trabalho, focamos no problema de alocação de tarefas, o qual é mais formalmente denominado de Problema do Mapeamento (MP). O MP consiste em identificar quais núcleos de processamento de um MPSoC são mais adequados para receber cada tarefa da aplicação. O MP pertence à classe dos problemas NP-Hard, com isso, não é conhecido um algoritmo de tempo polinomial que gere uma solução exata, tornando inviável a busca por soluções exatas para esse problema quando se trabalha com sistemas multicores com dezenas de núcleos. Logo, deve-se pesquisar alternativas que consigam obter resultados aproximados, e que atendam de forma satisfatória, ao objetivo que se deseja alcançar. Este trabalho consiste na apresentação de uma formulação para o Problema do Mapeamento, em sua forma estática, como uma instância do Problema Quadrático de Alocação (QAP), o qual é um dos problemas encontrados na literatura que mais se assemelha ao MP. A partir dessa formulação, é feita uma avaliação de um algoritmo de busca local, denominado Breakout Local Search (BLS), usado para resolver o QAP, porém agora aplicado ao contexto do MP. Além desse algoritmo, são avaliadas duas heurísticas de mapeamento estático de tarefas, desenvolvidas com o objetivo de prover um maior paralelismo nas comunicações entre as tarefas de uma aplicação e com um algoritmo de mapeamento Sequencial simples. Essas abordagens são comparadas com o BLS, com relação à qualidade das soluções geradas, por meio das métricas obtidas pelo simulador de Redes em Chip SiNoC. Os testes são feitos sob diferentes aplicações reais, considerando MPSoCs com dimensão 4x4 e 8x8, e, por fim, são apresentados os melhores resultados obtidos.
Abstract: With the advance in integrated circuit manufacturing technology, that made possible transistor size reduction, as predicted by Gordon Moore in 1975, it became possible the development of more complex systems in a single chip, called System on Chip (SoC), which can be composed of processing cores, memories and others components. In spite of that, with the increasing complexity of current applications, demanding more performance and parallelism capacity, were developed more complex SoCs that are composed for several cores, called Multiprocessors System on Chip (MPSoC). Communication between different cores is given by communications architectures. Nowadays, the most used ones are Networks on Chip (NoC) which, among other advantages, provide parallelism in communication. Due to the capacity of MPSoC to run applications in parallel, some challenges arise to be addressed, such as, task allocation, migration and scheduling. This work focus on task allocation problem, that is more formally called as Mapping Problem (MP). The MP consists in identifying which processing cores of a MPSoC are more adequate to allocate each application task. The MP is a NP-Hard problem, so is unknown a polynomial time algorithm to generate an exact solution. Therefore, it is necessary to search for solutions to obtain approximate results that meet the performance and/or other aspects requirements. This work consists in a presentation of Mapping Problem formulation, in static context, as a Quadratic Allocation Problem (QAP) instance. QAP is a combinatorial optimization problem, which from the optimization problems found in literature, is the one most similar to MP. From this formulation, it is evaluated an local search algorithm called Breakout Local Search (BLS), used to solve the QAP in MP context. Besides this algorithm, it is also evaluated two static task mapping heuristics. These heuristics were proposed aiming increasing communication parallelism among application tasks. All algorithms are compared to a simple Sequential algorithm in order to evaluate the solution qualities in different aspects. The results are obtained by a NoC simulator, called SiNoC. The evaluations were made considering real applications running on a MPSoC with 4x4 and 8x8 dimensions.
URI: http://monografias.ufrn.br/jspui/handle/123456789/4321
Other Identifiers: 20170008250
Appears in Collections:Ciência da Computação

Files in This Item:
File Description SizeFormat 
ProblemaMapeamento_Rocha_2017.pdfMonografia4.06 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons