O Problema do Mapeamento: Heurísticas de mapeamento de tarefas em MPSoCs baseados em NoC

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.