Análise de Escalabilidade de uma Implementação Paralela do Simulated Annealing Acoplado
Simulated Annealing Acoplado, metaheurística, eficiência de algoritmos, desempenho paralelo, escalabilidade paralela
O presente trabalho analisa o desempenho paralelo de uma implementação do Simulated Annealing Acoplado (CSA, do inglês: Coupled Simulated Annealing) para otimização de variáveis contínuas sem restrições. O processamento paralelo é uma forma eficiente de processamento de informação com ênfase na exploração de eventos simultâneos na execução de um software. Ele surge principalmente devido às elevadas exigências de desempenho computacional e à dificuldade em aumentar a velocidade de um único núcleo de processamento. Apesar dos CPUs multiprocessadas, ou processadores multicore, serem facilmente encontrados atualmente, diversos algoritmos ainda não são adequados para executar em arquiteturas paralelas. A utilização do paralelismo somente a nível de tarefas do sistema operacional, em muitos casos, não eficiente. No desenvolvimento de aplicações paralelas é necessário também utilizar paralelismo dentro da tarefa. A implementação do CSA descrita no presente trabalho explora o real potencial desse tipo de paralelismo. O algoritmo é caracterizado por um grupo de otimizadores Simulated Annealing (SA) trabalhando em conjunto no refinamento da solução. Cada otimizador SA é executado em uma thread, e essas executadas por diferentes processadores. Na análise de desempenho e escalabilidade paralela, as métricas investigadas foram: o tempo de execução, o speedup doalgoritmo com respeito ao aumento do número de processadores e a eficiência na utilização de elementos de processamento com relação ao aumento da instância do problema tratado. Além disso, foi verificado a qualidade da solução final. Para o estudo, esse trabalho propõe uma versão paralela do Coupled Simulated Annealing e sua versão serial equivalente. Ambos algoritmos foram analisados sobre 14 funções de referência. Para cada uma dessas funções, o CSA é avaliado utilizando de 2 a 24 otimizadores. Os resultados obtidos são exibidos e comentados observando-se as métricas de análise. As conclusões do trabalho caracterizam o CSA como um bom algoritmo paralelo, seja na qualidade das soluções ou na escalabilidade e desempenho paralela.