An evolutionary approach for the task mapping problem

Abstract

Este trabalho têm como objetivo a implementação de um algoritimo evolucionário, baseado no algoritmo de Evolução Diferencial (DE), para a resolução do problema de Mapeamento de Tarefas em Redes em Chip. Foi implementada uma variação do algoritmo clássico de Evolução Diferencial, alterando-se o procedimento de operação genética da etapa de Recombinação, que passou a premiar individuos com base na existencia de uma condição indicativa de maior proximidade entre tarefas muito comunicantes. Nossa implementação foi avaliada a partir do uso do pacote de benchmark NASA Numerical Aerodynamic Simulation (NASA NAS) e os resultados mostraram que nossa implementação do DE se mostrou viável e competitiva. Na comparação com o mapeamento realizado com o framework CAFES, nossa implementação se mostrou superior em duas das 5 aplicações testadas, obtendo desempenho equivalente ao CAFES em uma aplicação e obtendo soluções menos eficientes em duas aplicações.

This works has the goal to implement an Evolutionary Algorithm, based on the classical Differential Evolution, to solve the Task Mapping onto NoC problem. Our variant implemented a changing on the genetic operator of recombination, that started to reward individuals containing a pre-select condition that indicates when most communicating tasks are allocated near to each other onto the NoC. Our implementation was subject to the NASA Numerical Aerodynamic Simulation (NASA NAS) benchmark and results have shown that our variant is feasible and competitive. When compared to the CAFES Framework, our DE variant presented superior results on two of five tested applications, reaching equivalent quality on one of the applications and getting worst results in two of them.