Sistemas Dinamicamente Reconfiguráveis (SDR) têm recebido aceitação crescente ao longo dos últimos anos, uma vez que esta tecnologia aumenta a flexibilidade na ocupação do hardware, geralmente implementada sobre Field Programable Gate Array (FPGA). Concomitantemente, ocorreu a ascensão dos Sistemas-sobre-Silício (do inglês, Systems-on-Chip, SoCs), devido ao crescimento na densidade lógica dos circuitos integrados, implicando na construção de sistemas sobre chip mais complexos, através da unificação destes circuitos menores, portadores de tarefas, em um único chip com módulos processantes (MPs). Diversos paradigmas foram utilizados na comunicação em uma SoC, sendo as redes intrachips (do inglês, Network-on-Chip, NoCs) um dos mais investigados nos últimos anos, devido à sua eficiência em SoCs contendendo muitos IP cores criando-se os Sistemas-Sobre-Silício baseados em redes intrachip (SoC-NoCs). Para a implementação de SDR-NoCs eficientes em termos de parâmetros de desempenho como velocidade e consumo de potência, é imprescindível realizar durante o seu projeto, o mapeamento de tarefas da aplicação considerada a módulos processantes (MPs), definindo as melhores vizinhanças entre si; seguido do posicionamento otimizado dos MPs em termos de espaço, dentro de uma região válida no chip. Por conta da alta escalabilidade das NoCs e capacidade de reconfiguração, tais tecnologias foram alinhadas, criando-se as arquiteturas SDRs baseadas em NoC (SDR-NoCs). Tal arquitetura pode ser classificada em simples, com topologias de NoC regulares e diretas, e MPs de áreas homogêneas; ou complexas, com topologias de NoC irregulares e indiretas, e MPs, implementados por IP cores de áreas heterogêneas, sendo uma arquitetura mais realista. Segundo o nosso conhecimento, o mapeamento e posicionamento de SDR-NoCs Complexas foi apenas tratado com a utilização de Algoritmo Genético. Entretanto, diversas pesquisas apontam que este mesmo problema, para SDR-NoCs simples e NoCs não-SDR simples, a utilização dos algoritmos da família Busca Tabu trazem melhores resultados de otimização. Neste trabalho são apresentadas alternativas para o mapeamento e posicionamento de SDR-NoCs Complexas, através de seis tipos de algoritmos da família Busca Tabu (do inglês, Tabu Search, TS), sendo quatro deles originalmente introduzidos neste trabalho. Além disso, uma aproximação matemática sobre o problema de mapeamento e posicionamento das SDR-NoCs também é feita, mostrando que este é uma variação do problema da associação quadrática (do inglês, Quadratic Assignment Problem, QAP), justificando-se assim o uso dos algoritmos da família TS. Uma série de análises estatísticas também são feitas sobre os resultados dos algoritmos, obtidos por amostragem, a fim de apresentar a consistência de cada um deles para encontrar a melhor solução, comparando-os à solução mínima, encontrada através de um algoritmo determinístico de tempo não polinomial. Os resultados mostram que, considerado todos o benchmarks utilizados, a média do melhor caso obtido com o algoritmo FI-adaTS atingiu 31%, sobre o a média do melhor caso. Além disso, também foi alcançada uma melhora de até aproximadamente sete vezes sobre o tempo de execução.

The acceptance of Dynamically Reconfigurable Systems (DRSs) increased over the lasts years as this technology increases the flexibility of occupancy in hardware, usually implemented on Field Programmable Gate Array (FPGA). Concurrently, the rise of Systems-on-Chip (SoCs), due to the increase of logical density in integrated circuits, implying in the construction of more complex chip-systems, through the inclusion of circuits, processing modules (PMs) carrying systems tasks, on a single chip. Several paradigms have been used for communication in SoC, being Networks-on-Chip (NoCs) one of the most investigated in latest years due to its efficiency in SoCs, with many IP cores, creating the Network-on-Chip-based Systems-on-Chip (SoC-NoCs). In order to implement efficient DRS-NoCs in terms of performance parameters, such as speed and power consumption, it is essential to map the application tasks to processors (PMs) during design time, defining the best neighborhoods among them; this is followed by optimized positioning of the PMs in terms of space, belonging to a valid region on the chip. Due to the high scalability of the NoCs and reconfiguration capability, these technologies were aligned, creating the NoC-based DRSs (DRS-NoCs) architectures. Such architectures can be classified as simple, with regular and direct NoC topologies, and PMs of homogeneous areas; or complex, with irregular and indirect NoC topologies, and PMs, implemented by IP cores of heterogeneous areas, being a more realistic architecture. To our knowledge, the mapping and positioning of DRS-Complex NoCs was only treated in previous works with the use of Genetic Algorithm. However, several studies have pointed out that, for this problem, in simple DRS-NoCs and simple non-DRS NoCs, Tabu Search (TS) family-algorithms bring better optimization results. In this work, we present alternatives for the mapping and positioning of DRS-Complex NoCs, through six types of algorithms of the TS family, four of them originally introduced in this work. In addition, a mathematical treatment of the problem of mapping and positioning of the DRS-NoCs is also made; formalizing that this problem is a variation of the Quadratic Assignment Problem (QAP), thus justifying the use of the algorithms of the TS family. A series of statistical analyses has also been perfomed on the results of the algorithms, obtained by sampling, in order to assessing the consistency of each one of them to find the best solution, comparing them to the minimum solution, found by a non-polynomial time deterministic algorithm. The results show that, by considering all the utilized benchmarks, the average for the best case, with FI-adaTS, has reached a 31% better result than the best-case average. In addition, an improvement of up to about seven times over the runtime was also achieved.