Employment of parameter adaptive techniques to bio-inspired meta-heuristics for mapping real-time applications onto NoC based MPSoCs

Abstract

O problema de mapear tarefas de uma aplicação em tempo-real (RTA) em uma plataforma com múltiplos processadores no mesmo chip do tipo (MPSoC) que utiliza uma rede intra-chip (NoC) como arquitetura de comunicação pode ser abordado como um problema de otimização que possui o intuito de melhorar características do design do sistema utilizando uma análise estática. Exemplos de característica que se deseja que sejam melhoradas são a conformidade do sistema com as suas restrições temporais e o use dos seus recursos. Uma meta-heurística bio-inspirada, como o Algoritmo Genético (GA) pode obter mapeamento de tarefas no qual todas as tarefas da aplicação são agendadas. Além disso, no contexto de meta-heurísticas, algoritmos que incorporam técnicas adaptativas para os seus parâmetros e operadores são capazes de mudar os seus mecanismos de busca baseando-se no problema que está sendo otimizado com o intuito de simultaneamente buscar por soluções ótimas para o problema utilizado e por parâmetros melhores. Essas características permitem que meta-heurísticas que empregam esses mecanismos de mitigar a necessidade de um estágio para configurar os seus parâmetros e melhorar os seus desempenhos. Em luz dessas informações, esse trabalho visa efetuar um estudo para explorar múltiplos técnicas de adaptação para meta-heurísticas bio-inspiradas e empregá-las no desenvolvimento de novas versões adaptativas de meta-heurísticas como o GA, o algoritmo de otimização por enxame de partículas (PSO), e o algoritmo de evolução diferencial (DE). Essas novas meta-heurísticas são subsequentemente aplicadas em múltiplas instâncias do problema de mapeamento de tarefas de uma RTA em uma plataforma do tipo MPSoC que usa NoC utilizando funções com um único ou múltiplos objetivos. Em adição à aplicação dessas meta-heurísticas, esse trabalho também apresenta uma comparação estatística para verificar os seus desempenhos. O experimento onde esse estudo estatístico é aplicado foi conduzido para utilizar as meta-heurísticas desenvolvidas nesse trabalho e também as suas versões originais em múltiplas configurações do problema de mapeamento utilizando plataformas MPSoC com diferentes tamanhos e uma RTA utilizada como benchmark com RTA geradas de forma sintética. Os resultados obtidos indicam que, para o conjunto de problemas avaliados, meta-heurísticas com técnicas adaptativas são capazes de alcançar melhores resultados, na média, do que as suas versões sem esquemas de adaptação. Outra contribuição desse trabalho é o desenvolvimento de um plataforma de software orientado a objetos em C++ cuja aplicação não se restringe ao problema de mapeamento de tarefas e pode ser utilizado em outros problemas de otimização como a lista de funções de otimização de benchmark.