Problema de mapeamento e roteamento: propostas de otimização bioinspiradas híbridas

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.