Uma proposta de paralelização da metaheurística Iterated Greedy Search para a solução do Problema de Instalação de Fibras em Redes Óticas

Daniel Morais dos Reis¹; Álvaro Martins Espíndola¹; Guilherme de Morais Bessa¹; Sérgio Ricardo de Souza¹; Anolan Yamilé Milanés Barrientos¹

¹ CEFET-MG

doi:10.20906/CPS/CILAMCE2017-1199

Resumo

Técnicas de paralelismo, além da levarem à execução acelerada de programas, permitem também que estes sejam implementados de diferentes formas, as quais obtêm desempenhos diferentes entre si não somente sob a ótica da redução do tempo final de execução necessário, mas também também acerca da qualidade de solução encontrada. O presente artigo avalia qual, dentre diferentes formas de implementações paralelas da metaheurística Iterated Greedy Search (IGS), otimiza o seu desempenho ao ser aplicada à solução de instâncias do Problema de Instalação de Fibras em Redes Óticas - PIFRO, quando realizada com técnicas de paralelismo em uma mesma CPU dotada com mais de um núcleo de processamento em um ambiente de memória compartilhada. O desempenho é calculado através da verificação do speedup encontrado à medida em que são disponibilizadas mais threads executadas simultaneamente e um valor alvo a ser atingido. A paralelização da metaheurística IGS é realizada nas modalidades de Paralelização Monopertubação e Paralelização Multipertubação, sendo ambas testadas com e sem a sincronização da melhor solução corrente. O speedup encontrado entre as diferentes formas de paralelização mostra-se superlinear em alguns casos.

Palavras-chave: Metaheurísticas; Computação Paralela; Problema de Instalação de Redes de Fibras Óticas