Análise de escalabilidade de uma implementação paralela do simulated annealing acoplado

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 das CPUs multiprocessadas, ou processadores multicore, serem facilmente encontrados atualmente, diversos algoritmos ainda não são adequados para executar em arquiteturas paralelas. O algoritmo do CSA é caracterizado por um grupo de otimizadores Simulated Annealing (SA) trabalhando em conjunto no refinamento da solução. Cada otimizador SA é executado em uma única 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 do algoritmo 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 verificada a qualidade da solução final. Para o estudo, esse trabalho analisa uma versão paralela do CSA 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 como na escalabilidade e eficiência paralelaThis paper analyzes the performance of a parallel implementation of Coupled Simulated Annealing (CSA) for the unconstrained optimization of continuous variables problems. Parallel processing is an efficient form of information processing with emphasis on exploration of simultaneous events in the execution of software. It arises primarily due to high computational performance demands, and the difficulty in increasing the speed of a single processing core. Despite multicore processors being easily found nowadays, several algorithms are not yet suitable for running on parallel architectures. The algorithm is characterized by a group of Simulated Annealing (SA) optimizers working together on refining the solution. Each SA optimizer runs on a single thread executed by different processors. In the analysis of parallel performance and scalability, these metrics were investigated: the execution time; the speedup of the algorithm with respect to increasing the number of processors; and the efficient use of processing elements with respect to the increasing size of the treated problem. Furthermore, the quality of the final solution was verified. For the study, this paper proposes a parallel version of CSA and its equivalent serial version. Both algorithms were analysed on 14 benchmark functions. For each of these functions, the CSA is evaluated using 2-24 optimizers. The results obtained are shown and discussed observing the analysis of the metrics. The conclusions of the paper characterize the CSA as a good parallel algorithm, both in the quality of the solutions and the parallel scalability and parallel efficienc