UNIVERSIDADE DO RIO GRANDE DO NORTEFEDERAL
UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE
CENTRO DE TECNOLOGIA
PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E DE
COMPUTAÇÃO
Análise de Escalabilidade de uma Implementação
Paralela do Simulated Annealing Acoplado
Kayo Gonçalves e Silva
Orientador: Prof. Dr. Samuel Xavier de Souza
Co-orientador: Prof. Dr. Daniel Aloise
Dissertação de Mestrado apresentada ao Pro-
grama de Pós-Graduação em Engenharia Elé-
trica e de Computação da UFRN (área de con-
centração: Engenharia de Computação) como
parte dos requisitos para obtenção do título de
Mestre em Ciências.
Natal
2013
Kayo Gonçalves e Silva
Análise de Escalabilidade de uma Implementação
Paralela do Simulated Annealing Acoplado
Dissertação de Mestrado apresentada ao
Programa de Pós-Graduação em Engenharia
Elétrica e de Computação da UFRN (área de
concentração: Engenharia de Computação)
como parte dos requisitos para obtenção do
título de Mestre em Ciências.
Orientador: Prof. Dr. Samuel Xavier de
Souza
Co-orientador: Prof. Dr. Daniel Aloise
Natal
2013
UFRN / Biblioteca Central Zila Mamede
Catalogação da Publicação na Fonte.
Silva, Kayo Gonçalves e.
Análise de escalabilidade de uma implementação paralela do simulated annealing
acoplado. / Kayo Gonçalves e Silva - Natal, RN, 2013.
68 f.; il.
Orientador: Prof. Dr. Samuel Xavier de Souza
Co-orientador: Prof. Dr. Daniel Aloise
Dissertação (Mestrado) - Universidade Federal do Rio Grande do Norte. Centro de
Tecnologia. Programa de Pós-Graduação em Engenharia Elétrica e de Computação.
1. Processamento paralelo - Dissertação. 2. Simulated Annealing Acoplado -
Dissertação. 3. Metaheurística - Dissertação. 4. Eficiência paralela - Dissertação. 5.
Escalabilidade paralela - Dissertação. I. Souza, Samuel Xavier de. II. Aloise, Daniel.
III. Universidade Federal do Rio Grande do Norte. IV. Título.
RN/UF/BCZM CDU 004.272.2
Kayo Gonçalves e Silva
Análise de Escalabilidade de uma Implementação
Paralela do Simulated Annealing Acoplado
Dissertação de Mestrado apresentada ao Pro-
grama de Pós-Graduação em Engenharia Elé-
trica e de Computação da UFRN (área de con-
centração: Engenharia de Computação) como
parte dos requisitos para obtenção do título de
Mestre em Ciências.
COMISSÃO EXAMINADORA
Prof. Dr. Samuel Xavier de Souza
Universidade Federal do Rio Grande do Norte - Orientador
Prof. Dr. Daniel Aloise
Universidade Federal do Rio Grande do Norte - Co-orientador
Prof. Dr. Manoel Firmino de Medeiros Júnior
Universidade Federal do Rio Grande do Norte
Prof.a Dr.a Simone de Lima Martins
Universidade Federal Fluminense
Natal
2013
Aos meus pais, Aécio e Gilvaneide, que
me propiciaram uma vida digna onde
eu pudesse crescer, acreditando que
tudo é possível, desde que sejamos
honestos, íntegros de caráter e tendo a
convicção de que desistir nunca seja
uma ação contínua em nossas vidas;
que sonhar e concretizar os sonhos só
dependerão de nossa vontade.
Agradecimentos
Agradeço primeiramente a Deus, por sempre ouvir minhas orações, por sempre estar presente
ao meu lado, seja nos momentos dificeis ou nos fáceis, zelando por mim e por toda minha
família.
Aos meus pais Aécio Medeiros e Gilvaneide Gonçalves, fontes do saber onde busco conselhos
e apoio em minha vida, por serem meus fiéis e sinceros guias na longa jornada da vida.
À minha irmã Kamila Gonçalves, pela sua incontestável amizade.
À querida Lília Pong, que compartilhou comigo esse momento, foi muito paciente em minhas
ausências e me dedicou todo o seu especial carinho.
Ao meu orientador Samuel Xavier de Souza, modelo de profissional, que acreditou no meu
potencial, que dedicou incansáveis horas de ajuda, sem cuja ajuda este trabalho não teria sido
possível.
Ao meu coorientador Daniel Aloise, por ter me acompanhado nessa jornada e pelos ensinamen-
tos que me foram concedidos.
Aos demais professores do departamento que contribuíram direta ou indiretamente com a minha
formação profissional e pessoal.
Aos meus amigos, por me apoiarem e torcerem pelo meu sucesso.
À CAPES e CNPq pelo apoio financeiro.
Muito Obrigado.
Resumo
O presente trabalho analisa o desempenho paralelo de uma implementação do Simulated An-
nealing 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 à di-
ficuldade em aumentar a velocidade de um único núcleo de processamento. Apesar das CPUs
multiprocessadas, ou processadores multicore, serem facilmente encontrados atualmente, diver-
sos 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 veri-
ficada 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 con-
clusões do trabalho caracterizam o CSA como um bom algoritmo paralelo, seja na qualidade
das soluções como na escalabilidade e eficiência paralela.
Palavras-chave: Simulated Annealing Acoplado, metaheurística, eficiência paralela, esca-
labilidade paralela.
Abstract
This paper analyzes the performance of a parallel implementation of Coupled Simulated
Annealing (CSA) for the unconstrained optimization of continuous variables problems. Paral-
lel 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 suita-
ble 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 ele-
ments 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 efficiency.
Keywords: Coupled Simulated Annealing, heuristics, parallel efficiency, parallel scalabi-
lity.
Lista de Figuras
2.1 Pseudocódigo do Algoritmo Simulated Annealing. . . . . . . . . . . . . . . . . 22
2.2 Soma dos custos médios normalizados pelo valor da variância limite . . . . . . 26
2.3 Comportamento da probabilidade de aceitação dos otimizadores SA com a va-
riação da temperatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4 Comportamento dos otimizadores com o controle da variância de probabilidade
de aceitação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5 Pseudocódigo do Algoritmo Simulated Annealing Acoplado. . . . . . . . . . . 29
2.6 Exemplo 1 de espaço de busca multimodal e percurso realizado pelo CSA com
4 otimizadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.7 Exemplo 2 de espaço de busca multimodal e percurso realizado pelo CSA com
4 otimizadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1 Quantidade de transistores nos processadores Intel . . . . . . . . . . . . . . . . 32
3.2 Média de frequência de operação dos processadores de 2000 ate 2012 . . . . . 34
3.3 Funcionamento de uma região crítica . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Limitação que a Lei de Amdahl impõe ao speedup dos algoritmos paralelos . . 39
3.5 Comportamento dos algoritmos paralelos pela Lei de Gustafson . . . . . . . . 40
4.1 Exemplo de espaço de soluções com os otimizadores SA . . . . . . . . . . . . 41
4.2 Implementação do Simulated Annealing Acoplado . . . . . . . . . . . . . . . 45
5.1 Função f3 do grupo 2 de funções de referência em três dimensões. . . . . . . . 49
5.2 Função f8 do grupo 2 de funções de referência em três dimensões. . . . . . . . 49
5.3 Pseudocódigo do Algoritmo Simulated Annealing Acoplado Serial. . . . . . . . 51
5.4 Média das soluções do grupo 1 de funções de referência utilizando o CSA com
24 otimizadores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.5 Média das soluções do grupo 2 de funções de referência utilizando o CSA com
24 otimizadores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.6 Média das soluções do grupo 3 de funções de referência utilizando o CSA com
24 otimizadores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.7 Eficiência vs Dimensão para o grupo 1 de funções de referência. . . . . . . . . 59
5.8 Eficiência vs Dimensão para o grupo 2 de funções de referência. . . . . . . . . 60
5.9 Eficiência vs Dimensão para o grupo 3 de funções de referência. . . . . . . . . 61
5.10 Média da Eficiência vs Dimensão para os grupos de funções de referência. . . . 62
Lista de Tabelas
5.1 Grupo 1: Funções Unimodais e Simples Multimodais . . . . . . . . . . . . . . 48
5.2 Grupo 2: Funções Multimodais . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.3 Qualidade de solução do Simulated Annealing (SA), do Coupled Simulated An-
nealing (CSA) serial e paralelo para D = 10, 25 execuções . . . . . . . . . . . 52
5.4 Qualidade de solução do Simulated Annealing (SA), do Coupled Simulated An-
nealing (CSA) serial e paralelo para D = 160, 25 execuções . . . . . . . . . . 54
5.5 Tempo médio de execução serial (TS), tempo médio de execução paralela (TP)
e speedup (SU) do algoritmo CSA para 160 dimensões. . . . . . . . . . . . . . 57
Sumário
Lista de Figuras
Lista de Tabelas
1 Introdução 15
1.1 Justificativa e Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3 Organização do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2 Simulated Annealing Acoplado 19
2.1 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.1 Definição do Algoritmo Simulated Annealing . . . . . . . . . . . . . . 21
2.2 Simulated Annealing Acoplado . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.1 Definição do Simulated Annealing Acoplado . . . . . . . . . . . . . . 23
3 Escalabilidade e Eficiência Paralela 32
3.1 Motivações e Justificativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 Problemas no paralelismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3 Métricas de Escalabilidade Paralela . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.1 Escalabilidade de Amdahl . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3.2 Escalabilidade de Gustafson . . . . . . . . . . . . . . . . . . . . . . . 39
4 Simulated Annealing Acoplado Paralelo 41
4.1 Histório de implementações . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 Implementação do CSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5 Experimentos e Resultados 47
5.1 Funções de Custo de Referência . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.2 Simulated Annealing Acoplado Serial . . . . . . . . . . . . . . . . . . . . . . 50
5.3 Qualidade da solução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.4 Speedup e Eficiência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.4.1 Análise de escalabilidade para o grupo 1 de funções de referência . . . 59
5.4.2 Análise de escalabilidade para o grupo 2 de funções de referência . . . 60
5.4.3 Análise de escalabilidade para o grupo 3 de funções de referência . . . 61
5.4.4 Análise de escalabilidade média dos grupos de funções . . . . . . . . . 61
Conclusão 63
Referências bibliográficas 66
Glossário
Ω Espaço de soluções
tk Temperatura da k-ésima iteração
t0 Temperatura inicial
f Função objetivo
T Temperatura de geração
Tac Temperatura de Aceitação
Θ Conjunto de todos os estados correntes
i Número do otimizador
xi Solução do i-ésimo otimizador
yi Possível solução do i-ésimo otimizador
AΘ Função de probabilidade de aceitação
γ Termo de acoplamento
σ2 Variância da função de probabilidade de aceita-
ção
σ2D Variância desejada da função de probabilidade de
aceitação
α Taxa de crescimento ou de decaimento da tempe-
ratura de aceitação
S Speedup
Ts Tempo de processamento serial
Tp Tempo de processamento paralelo
E f Eficiência
m Número de processadores
r Número aleatório de distribuição uniforme [0,1]
SA Algoritmo Simulated Annealing
CSA Algoritmo Coupled Simulated Annealing
OpenMP Interface de programação de aplicativo para pro-
gramação multi-processo de memória comparti-
lhada em múltiplas plataformas em C/C++ e For-
tran.
1 Introdução
Nas últimas décadas, a demanda por alto desempenho e baixo custo energético motivam
novas pesquisas no campo da computação. O processamento paralelo surge, então, como um
dos processos chaves de tecnologia que possibilitam a computação moderna (TASOULIS et al.,
2004; YANG et al., 2006) .
Diante das dificuldades encaradas pelos fabricantes em continuar com o crescimento verti-
ginoso do número de transistores por cm2, como comenta a Lei de Moore, utilizar o paralelismo
deixa de ser uma opção e passa a ser uma necessidade.
A Lei de Moore se estabeleceu há alguns anos como uma tendência para a indústria de
semicondutores, dobrando o número de transistores a cada 18 meses. O crescimento da quan-
tidade de transistores era convertido em ganhos de desempenhos computacionais sem nenhuma
alteração no código para cada nova geração de processadores. Infelizmente esse ganho não se
perpetuou. A tecnologia de circuitos de alta densidade se aproxima do limite físico dos dispo-
sitivos eletrônicos enquanto que a escala dos sistemas computacionais aumenta rapidamente,
o que leva a um acentuado consumo de energia dos sistemas de alto desempenho. O resul-
tado, chamado de "Power Wall"(ou, Muralha de Energia, em tradução livre), é o aumento de
consumo de energia dos sistemas computacionais devido à alta densidade dos dispositivos e
suas elevada velocidade de operação. O surgimento de processadores multicore se tornou uma
necessidade porque é mais difícil resfriar processadores de único núcleo com alta velocidade
de processamento. A "Era Multicore", cuja idéia engloba o princípio de duplicação da quanti-
dade de núcleos de processamento em um único chip a cada geração, é comentada por Borkar
(2007). Processadores Multicore possuem o potencial para resolver grandes problemas, per-
mitindo o uso de diferentes núcleos para o processamento de diferentes porções de dados e,
consequentemente, redução no tempo de resposta.
Nos problemas tratados pela Engenharia, grande parte visa modelar problemas complexos
do mundo real. Essa tarefa não é trivial, dado que existem situações em que, ou é impossivel se
construir um modelo fiel em virtude de sua complexidade, ou em que o processo de simplifica-
ção de tal modelo causa perdas de informações relevantes que podem comprometer a exatidão
e, consequentemente, a qualidade da solução obtida. Além da dificuldade inerente à construção
dos modelos, outra característica que os acompanha na fase de resolução é a alta complexidade
CAPÍTULO 1. INTRODUÇÃO 16
de representação do sistema ou de processamento computacional para grandes instâncias1, o
que pode tornar o problema intratável2. Nesse contexto, muitos pesquisadores têm se dedicado
na pesquisa e desenvolvimento de técnicas que visam facilitar a modelagem e a resolução desses
problemas.
Dentre as diversas técnicas para se obter soluções aproximadas de problemas intratáveis,
destacam-se as metaheurísticas. Elas são procedimentos destinados a encontrar uma boa so-
lução, eventualmente ótima, consistindo na aplicação de uma heurística subordinada. As me-
taheurísticas buscam o equilíbrio entre o momento de diversificação das soluções e o momento
da intensificação da busca local em regiões promissoras. Elas se diferenciam das heurísticas
convencionais por seu caráter estocástico, que possibilita escapes das bacias atratoras. Tais
bacias são responsáveis pela estagnação do processo de busca pela solução ótima. Em ambos
os casos, é comum encontrar algoritmos que se inspiram em diversas áreas do conhecimento,
como a Biologia e a Física.
Para problemas NP-Completos, diversas metaheurísticas são empregadas com sucesso, como
o simulated annealing (SA), algoritmos genéticos (GA) e dispersão de partículas (PSO). Ape-
sar de possuírem a capacidade de escapar dos mínimos locais, uma grande desvantagem desses
métodos é a falta de robustez associado aos parâmetros de inicialização. A escolha desses parâ-
metros afeta diretamente a habilidade do algoritmo em encontrar boas soluções. Normalmente,
é necessário o conhecimento empírico para encontrar valores ótimos de tais parâmetros de inici-
alização, o que dificulta seu uso. A característica "Parameter-less" - que propõe uma redução,
exclusão ou maior robustez dos parâmetros de entrada - foi proposta para facilitar o uso des-
ses e de outros algoritmos. Os artigos de Harik (1999) e de Tran (2005), por exemplo, trazem
trabalhos utilizando essa característica. Outro problema, desta vez encarado como uma grande
desvantagem, é o enorme número de avaliações da função custo (XAVIER-DE-SOUZA et al.,
2010).
Devido ao grande esforço computacional necessário na utilização de metaheurísticas e ao
poder de computação provido pelos processadores multicore, diversas metaheurísticas podem
ser reformuladas para explorar seu potencial paralelo, reduzir o tempo de resposta e facilitar,
possivelmente, o seu uso pelos diversos usuários. A fim de melhorar a qualidade da solução e
reduzir o tempo de processamento, Xavier-de-Souza et al. (2010) definiram o algoritmo para-
lelo Simulated Annealing Acoplado (CSA, do inglês Coupled Simulated Annealing) capaz de
encontrar boas soluções para os problemas de otimização de variáveis contínuas sem restrições.
O CSA utiliza diversos otimizadores que buscam a solução ótima. Esses otimizadores trocam
informações entre si de forma a otimizar a busca.
1Instância é usada para se referir à atribuição de valores às variáveis de entrada de um problema.
2Um problema é dito intratável quando não existe um algoritmo que o resolva em tempo polinomial.
CAPÍTULO 1. INTRODUÇÃO 17
Apesar do CSA ser eficiente em refinar soluções, nenhuma análise foi feita para demonstrar
sua escalabilidade paralela. O trabalho corrente, portanto, tem como objetivo a comprovação
tanto do refinamento da qualidade da solução final do CSA paralelo quanto de sua escalabilidade
paralela.
1.1 Justificativa e Motivação
Os algoritmos heurísticos são limitados, pois não conseguem escapar de bacias atratoras, o
que normalmente os levam a estagnar em um ótimo local. Segundo Lima Júnior (2009), com
o anseio por heurísticas mais poderosas, surgiram as metaheurísticas, que podem ser encaradas
como heurísticas direcionadas à otimização global, podendo conter diferentes procedimentos
heurísticos de construção ou busca local da solução a cada iteração do algoritmo .
O principal desafio das metaheurísticas é estabelecer um meio onde se pondere o grau de re-
finamento (refinar a solução utilizando uma busca local) e de exploração (mudar drasticamente
o local de busca a fim de conhecer novos horizontes). Lima e Júnior (2009) comenta que es-
tabelecer esse equilíbrio consiste em decidir adequadamente sobre experimentar ou não novas
situações (explorar novas áreas de solução, mesmo que sejam aparentemente menos favoráveis),
em detrimento daquelas já vivenciadas e tidas como boas soluções.
Uma idéia viável para contornar esse problema é trabalhar com um grupo de agentes otimi-
zadores. Cada agente seria governado por uma ou mais metaheurísticas, semelhantes ou não,
atuando cooperativamente em diversos setores do espaço de soluções viáveis. O importante é
que exista uma troca de informações entre os agentes, de forma que eles tomem decisões não
somente baseados na própria solução, mas na solução dos demais otimizadores. Dessa forma,
os agentes poderiam ponderar melhor se há necessidade de refinar ou explorar.
A idéia de grupo de agentes buscando ao mesmo tempo uma solução remete quase que
instintivamente à computação paralela. Com ela, é possível efetivamente compor um grupo que
trabalhe em concomitância. Com o paralelismo, é possível reduzir o tempo de processamento
de uma tarefa, já que as atividades estariam distribuídas entre os diversos processadores. Além
disso, o paralelismo segue atualmente como uma das principais soluções para evitar o problema
da Muralha de Energia.
O problema conhecido como "A Muralha de Energia" comenta sobre o a proporcionalidade
entre o crescimento do consumo de energia dos dispositivos eletrônicos e a sua frequência de
operação. Ou seja, o consumo de energia aumenta quadraticamente com a frequência de ope-
ração. Para agravar o problema, o número de transistores por chip aumentou drasticamente nos
últimos anos, conforme Moore observou (MOORE, 1965). A alta densidade de componentes
eletrônicos além de consumir mais energia, produz mais calor, que precisa de mais energia para
ser resfriado.
CAPÍTULO 1. INTRODUÇÃO 18
Assim, diante das dificuldades inerentes à resolução de problemas reais complexos, pelo su-
cesso das técnicas de resolução citadas anteriormente, pela necessidade de reduzir o consumo
de energia e pela realidade encarada do frequente aumento do número de núcleos de processa-
mento ao invés de ganhos de velocidade em um único processador, propõe-se neste trabalho a
análise da escalabilidade e da qualidade da solução final de uma implementação paralela do al-
goritmo Simulated Annealing Acoplado. Esse algoritmo utiliza o grupo de agentes otimizadores
como estratégia para decidir sobre o refinamento e exploração.
1.2 Objetivos
Com base no exposto, este trabalho tem como objetivos:
• Objetivos Gerais:
– Analisar a escalabilidade de uma implementação paralela do Simulated Annealing
Acoplado
• Objetivos Específicos:
– Implementar uma versão paralela do algoritmo CSA;
– Implementar uma versão serial do algoritmo CSA;
– Comparar a qualidade das soluções do SA, da versão serial e da versão paralela do
algoritmo CSA;
– Comparar o desempenho computacional das versões serial e paralela do algoritmo
CSA.
1.3 Organização do trabalho
O presente trabalho foi dividido em capítulos, totalizando com este 6 capítulos, organiza-
dos da seguinte forma. No capítulo 2 são descritas as metaheurísticas Simulated annealing e
Simulated Annealing Acoplado. O capítulo 3 apresenta motivações que justificam o uso do
paralelismo, problemas encarados no desenvolvimento de algoritmos paralelos e alguns con-
ceitos sobre as métricas de análise da escalabilidade paralela. No capítulo 4 é descrita, em
detalhes, a implementação final do algoritmo Simulated Annealing Acoplado e as dificuldades
enfrentadas em seu desenvolvimento. O capítulo 5 apresenta as funções de custo utilizadas nos
experimentos, a versão serial do CSA e os resultados quanto à qualidade da solução final e de
escalabilidade paralela. Toda crítica deste capítulo são resultados experimentais obtidos e ana-
lisado estatisticamente. Por fim, o último capítulo aborda as considerações finais e propostas
para trabalhos futuros.
2 Simulated Annealing Acoplado
Metaheurísticas são métodos que orquestram uma interação entre procedimentos de refi-
namento local e estratégias de alto nível para criar um processo capaz de escapar de ótimos
locais e desempenhar uma busca robusta no espaço de soluções (GLOVER e KOCHENBER-
GER, 2003). Ao longo do tempo, esses métodos passaram a incluir procedimentos que utilizam
estratégias para superar a armadilha de otimalidade local em espaços de soluções complexos,
especialmente os processos que utilizam uma ou mais estruturas de vizinhança como um meio
de definição de movimentos admissíveis para a transição de uma solução para outra. Todo esse
esforço em encontrar um algoritmo eficiente na busca de soluções ótimas (mínimas ou máxi-
mas) no espaço de busca se dá devido às suas aplicações.
Nas áreas de Engenharia, computação e pesquisa operacional é comum se deparar com
problemas de difícil solução. Alguns exemplos são:
• Determinar o caminho mínimo entre duas cidades em um mapa, desde que o percurso
passe por todas as cidades;
• Estabelecer a melhor sequência de atividades de uma empresa com a finalidade de mini-
mizar o uso do tempo;
• Determinar a melhor rota de um pacote na internet;
• Encontrar o melhor arranjo de salas de aula na universidade em um perído letivo;
• Estabelecer a melhor sequência de controle para uma planta petrolífera.
Um aspecto importante desses problemas diz respeito às suas características estruturais,
pois as suas modelagens utilizam agrupamentos, ordenações ou designações de um conjunto de
objetos discretos que satisfaçam determinadas restrições. Este aspecto contribui para que tais
problemas apresentem uma alta complexidade computacional. A aplicação de métodos exatos
de resolução (Relaxações, Branch-and-bound, Programação Dinâmica, dentre outros) podem
ser inviáveis em virtude do alto custo de processamento e/ou pela dificuldade na elaboração de
um modelo analítico e preciso das tarefas a serem realizadas. Segundo Lima Júnior (2009), uma
alternativa à resolução de tais problemas é a utilização de metaheurísticas.
O termo metaheurística é obtido através da união do afixo meta (que significa em um nível
CAPÍTULO 2. SIMULATED ANNEALING ACOPLADO 20
superior) ao termo heurística1, que significa encontrar, e foi utilizado originalmente por Glover
(1986) em um texto sobre Busca Tabu.
Um grande número de ferramentas e mecanismos que surgiram a partir da criação de me-
taheurísticas provou ser extraordinariamente eficaz, tanto que as metaheurísticas mudaram-se
para o centro das atenções nos últimos anos, como a linha preferencial de ataque para resolver
vários tipos de problemas complexos, particularmente os de natureza combinatória. Enquanto
metaheurísticas não são capazes de garantir a otimalidade das soluções que encontram, procedi-
mentos exatos (que teoricamente podem fornecer tal resposta caso haja tempo suficiente) muitas
vezes se mostraram incapazes de encontrar soluções, cuja qualidade é próxima às obtidas por
algumas metaheurísticas. Esses resultados motivam pesquisas adicionais e aplicação de novas
e melhoradas metaheurísticas.
Este trabalho propõe a análise da escalabilidade do algoritmo Simulated Annealing Aco-
plado, cujo princípio se inspira na metaheurística Simulated Annealing. As características do
SA e do CSA são descritas em detalhes nas seções a seguir.
2.1 Simulated Annealing
O Simulated Annealing (têmpera simulada) é um algoritmo de busca local capaz de esca-
par de ótimos locais (metaheurística) e baseado no método de Monte Carlo e no algoritmo de
Metropolis (METROPOLIS et al., 1953). A sua facilidade de aplicação, propriedades de con-
vergência e seu uso de movimentos de subida (hill climbing) para escapar de ótimos locais o
tornaram uma técnica popular nos anos de 1990 e 2000. Os artigos de Eglese (1990), Romeo
e Sangiovanni-Vincentelli (1991), Koulamas et al. (1994), Fleischer (1995a, 1995b), Xavier-
de-Souza et al. (2006), Xavier-de-Souza et al. (2010), Peredo e Ortiz (2011), e George et
al. (2012), por exemplo, fornecem uma boa visão do desenvolvimento teórico do Simulated
Annealing e o utilizam como base em seus domínios de aplicação.
O algoritmo de têmpera simulada é assim chamado devido à analogia ao processo físico
de têmpera com sólidos cristalinos, na qual um sólido é aquecido e então resfriado lentamente
até alcançar a configuração cristalina mais regular possível, i.e., seu estado de menor energia,
e assim diminuir as imperfeições do cristal. Se a redução da temperatura, que obedece a um
escalonamento, é suficientemente lenta, a configuração final resulta em sólidos com uma maior
integridade estrutural.
A cada iteração do algoritmo simulated annealing, a função objetivo gera valores para duas
1Segundo Lima Júnior (2009), o termo heurística tem origem na palavra eureka, cujo significado está relacio-
nado ao conceito de descobrir ou encontrar, e é vinculado a suposta exclamação de Arquimedes ao descobrir seu
famoso princípio
CAPÍTULO 2. SIMULATED ANNEALING ACOPLADO 21
possíveis soluções para comparação: a solução corrente e a nova solução selecionada, conhecida
como solução vizinha. Melhores soluções são sempre aceitas, enquanto que piores soluções po-
dem ser aceitas na esperança de escapar das bacias atratoras. A probabilidade dessa aceitação
depende do parâmetro de temperatura. Elevadas temperaturas resultam em uma maior chance
de aceitar soluções não tão boas, ao passo que baixas temperaturas rejeitam com maior proba-
bilidade tais soluções. Como a temperatura é decrementada até zero, os movimentos de subida
(hill climbing) ocorrem com menor frequência a cada iteração e a distribuição de soluções con-
verge para uma forma na qual toda a probabilidade é concentrada em um conjunto de soluções
locais, conforme comentam Glover e Kochenberger (2003).
2.1.1 Definição do Algoritmo Simulated Annealing
Para descrever as características específicas do algoritmo simulated annealing, diversas de-
finições são necessárias. As seguintes definições foram adaptadas de Glover (2003) e são espe-
cíficas para os problemas de minimização.
Seja Ω o espaço de soluções, ou seja, o conjunto de todas as possíveis soluções. Seja
E : Ω ⇒ R a função objetivo, ou energia, definida no espaço de soluções. Defina tk como o
parâmetro temperatura na k-ésima iteração, de tal forma que
tk > 0 para todo k, e limk→+∞ tk = 0. (2.1)
Para a temperatura, diversas equações podem reger o seu escalonamento de resfriamento. É
de comum utilização que o escalonamento seja linear. Seja t0 como a temperatura inicial e k o
número de iterações. O escalonamento linear pode ser expresso da seguinte forma:
tk+1 =
t0
k+1 . (2.2)
A meta é encontrar o mínimo global x∗, i.e., x∗ ∈Ω tal que E(x)≥ E(x∗),∀x ∈Ω. A função
objetivo deve ser limitada para garantir que x∗ exista. Defina N(x, tk) como a função vizinhança
para x ∈ Ω. Portanto, associado a cada solução x ∈ Ω, N(x, tk) gera soluções vizinhas que
são alcançadas em uma única iteração do algoritmo para a temperatura tk. Considere rnd é um
número aleatório de distribuição uniforme [0,1]. Uma das formas de expressar N(x, tk) é utilizar
a inversa da função de distribuição acumulada de Cauchy, da seguinte forma:
N(x, tk) = x+ tk tan
[
pi
(
rnd− 1
2
)]
. (2.3)
O algoritmo Simulated annealing inicia com a solução inicial x∈Ω. Uma solução candidata
(vizinha) y ∈ N(x, tk) é gerada utilizando alguma regra predefinida. As soluções candidatas são
CAPÍTULO 2. SIMULATED ANNEALING ACOPLADO 22
aceitas se possuírem melhores soluções ou se a probabilidade de aceitação A : Ω→ R, definida
em 2.15, for maior que um número aleatório de distribuição uniforme [0,1].
Probabilidade{Aceitar y}= A(x→ y) =

 e
[
E(x)−E(y)
tk
]
, se E(y)≥ E(x),
1, se E(y)< E(x).
(2.4)
O algoritmo é finalizado quando o critério de parada é alcançado. É comum encontrar como
critério de parada o tempo de execução do algoritmo ou o número de avaliações da função
objetivo.
Assim, o algoritmo simulated annealing tem a forma descrita na Figura 2.1:
Figura 2.1 – Pseudocódigo do Algoritmo Simulated Annealing.
1) Inicialização:
Selecione uma solução inicial aleatória x ∈Ω
Selecione um contador de mudança de temperatura k = 1
Defina a temperatura inicial tk
2) Geração:
Gere uma solução vizinha y ∈ N(x, tk)
3) Avaliação:
Faça x← y se:
a) E(y)≤ E(x)
b) A(x→ y)> r, onde r é um número aleatório de distribuição uniforme [0,1]
4) Atualização:
Incremente o contador k
Decremente a temperatura tk de acordo com o escalonamento escolhido
5) Parada:
Pare se o critério de parada foi alcançado
Senão volte ao passo 2
Fonte: Elaboração própria, 2013.
2.2 Simulated Annealing Acoplado
Com o foco em desenvolver métodos mais rápidos de otimização global e devido à grande
aplicação das metaheurísticas e dos diversos problemas que motivam o uso do paralelismo na
contemporaneidade, Xavier-de-Souza et al. (2010) desenvolveram um algoritmo estocástico
que se beneficia do paralelismo. O Simulated Annealing Acoplado (CSA, do inglês Coupled Si-
CAPÍTULO 2. SIMULATED ANNEALING ACOPLADO 23
mulated Annealing), assim denominado, é definido como uma classe de métodos de otimização
baseados em simulated annealing que podem ser usados para resolver problemas sem restrições
no espaço de busca contínuo.
O Simulated Annealing Acoplado consiste em um grupo de otimizadores SA (Simulated An-
nealing) que trabalham em conjunto na busca do mínimo global. No CSA, cada otimizador rea-
liza a busca indivual de uma solução, de forma que possa gerar sozinho uma solução canditada e
avaliá-la, aceitando-a ou não. Ao final da execução, cada otimizador terá uma própria solução e
será escolhida a melhor solução. Entretanto, os otimizadores são acoplados uns aos outros pela
função de probabilidade de aceitação, definida na Seção 2.2.1. O termo de acoplamento é uma
função de todos os custos correntes de todos os otimizadores SA. Cada otimizador SA possui
informações sobre o custo de todos os outros otimizadores. A informação que é compartilhada
através de acoplamento permite controlar os indicadores gerais de otimização, permitindo que o
algoritmo tome decisões baseando-se nas soluções correntes de todos os otimizadores. Xavier-
de-Souza et al. (2010) comentam que o acoplamento também pode ser usado entre os processos
de otimização local para ajudar os métodos de otimização por gradiente a escapar do ótimo
local para problemas não convexos. Ainda mais, através da concepção de um mecanismo de
acoplamento com um mínimo de comunicação, esses métodos acoplados podem muito efici-
entemente ser implementados em arquiteturas de computadores paralelos, tornando-os muito
atraentes para a tendência multicore na nova geração de arquiteturas de computadores.
2.2.1 Definição do Simulated Annealing Acoplado
No CSA, cada otimizador SA é executado separadamente. Cada um dos otimizadores é
responsável por gerar uma possível solução (solução vizinha) e avaliá-la, aceitando-a ou não.
A principal diferença entre o SA e o CSA consiste na probabilidade de aceitação. Sendo assim,
fazem-se necessárias algumas definições para o melhor entendimento do CSA. As definições
que se seguem foram adequadas de Xavier-de-Souza et al. (2010).
No CSA, os processos de geração e avaliação das possíveis soluções são controlados por
duas temperaturas: a temperatura de geração T e a de aceitação T ac. A temperatura de geração
T é utilizada na geração de novas soluções. Ela é responsável pelo grau de semelhança entre as
possíveis soluções (vizinhas) e a solução corrente, i.e., elevado valor de T implica em amplas
distribuições de soluções. A temperatura de aceitação T ac tem influência nas probabilidades
dos otimizadores. A forma dessa influência é explicada adiante.
Quanto à probabilidade, no SA é expressa por uma função escalar, 0≤ A(x → y) ≤ 1, para
todo x,y ∈ Ω, com Ω denotando o espaço de soluções. No CSA, essa probabilidade é uma
CAPÍTULO 2. SIMULATED ANNEALING ACOPLADO 24
função escalar, conforme:
0≤ AΘ(γ, xi → yi)≤ 1, (2.5)
para cada xi ∈ Θ, yi ∈ Ω, e Θ ⊂ Ω, onde xi é a solução corrente do i-ésimo otimizador, yi
é a possível solução do i-ésimo otimizador, para i = 1, . . . , m, com m sendo o número de
elementos de Θ. O grupo Θ corresponde ao conjunto de todos os estados correntes e é definido
como Θ≡ {xi}mi=1. Para aceitar a nova solução yi, a decisão depende do estado corrente xi e do
termo de acoplamento γ, que depende da energia de todos os elementos de Θ.
γ = f [E(x1), E(x2), . . . , E(xm)]
"Semelhante ao clássico SA, a probabilidade de aceitação pode assumir diferentes formas.
Essas funções também precisam herdar propriedades específicas" (XAVIER-DE-SOUZA et al.,
2010, p.323). Considere T ack como a temperatura de aceitação na k-ésima iteração do algoritmo.
No corrente trabalho, a probabilidade de aceitação utilizada foi
AΘ(γ, xi → yi) =
exp
(
E(xi)
T ack
)
γ , (2.6)
γ = ∑
x j∈Θ
exp
(
E(x j)
T ack
)
. (2.7)
Observe que a energia de cada otimizador não é limitada numericamente. Dessa forma,
o resultado de γ pode extrapolar o limite numérico máximo da variável computacional ponto
flutuante, tornando-o um número computacionalmente infinito. Este efeito se traduz no cálculo
incorreto da probabilidade de aceitação, que gera inconsistência probabilística, pois o valor
computacional da divisão de um número por um valor infinito resulta é um no nmero (do
inglês NaN, Not a Number). Felizmente, esse problema pode ser contornado facilmente com
uma normalização da função custo. Entretanto, para funções com limites desconhecidos, é
necessário utilizar outras aproximações dessa função. Assim, como sugestão de Xavier-de-
Souza et al. (2010), subtrai-se de todas as energias em (2.6) e (2.7) o valor da energia máxima
corrente.
A∗Θ(γ∗, xi → yi) =
exp
(E(xi)−max(E(xi))xi∈Θ
T ac
)
γ∗ , (2.8)
γ∗ = ∑
∀x∈Θ
exp
(
E(x)−max(E(xi))xi∈Θ
T ac
)
. (2.9)
CAPÍTULO 2. SIMULATED ANNEALING ACOPLADO 25
O resultado dessas equações são computacionalmente mais atrativos.
Os benefícios que o termo de acoplamento pode oferecer vão além de uma pura troca de
informação e podem ser utilizados para controlar medidas gerais estatísticas, possibilitando
modificar alguns parâmetros de controle que podem ter influência crucial na otimização. Nesse
caso, por exemplo, a variância das probabilidades de aceitação das soluções correntes pode ser
controlada utilizando a temperatura de aceitação T ac. O controle da variância das probabilida-
des de aceitação é comentado posteriormente.
De acordo com a forma que a probabilidade de aceitação está definida, a sua variância
sempre tem um valor limitado e pode ser calculado. Sabendo que
∑
∀xi∈Θ
AΘ(γ, xi → yi)≡ ∑
∀xi∈Θ
AΘ = 1. (2.10)
A variância para AΘ assume a seguinte forma
σ2 =
1
m
∑
∀xi∈Θ
A2Θ−
(
1
m
∑
∀xi∈Θ
AΘ
)2
,
=
1
m
∑
∀xi∈Θ
A2Θ−
1
m2
. (2.11)
Sabendo que
1
m
≤ ∑
∀xi∈Θ
A2Θ ≤ 1, (2.12)
conclui-se que
0≤ σ2 ≤ m−1
m2
. (2.13)
Para efetivar o controle da variância de probabilidade, necessita-se descobrir a medida limiar
que seja a melhor para o algoritmo. Em experimentos com diferentes funções custo, Xavier-
de-Souza et al. (2010) mostraram que o desempenho da otimização melhora com a variância
limite (ou variância desejada) em torno de 99% do seu máximo valor. Para a análise, Xavier-
de-Souza et al. (2010) utiliza 14 funções de referência. As funções estão separadas em 3
grupos, sendo o grupo 1 composto de duas funções unimodais, o grupo 2 composto por 6
funções multimodais, e o grupo 3 composto pela rotação das funções multimodais do grupo 2.
As funções são detalhadas na seção 5.1. O custo médio normalizado das funções é calculado
sobre 50 execuções de cada função e é dado em função do percentual da variância desejada. A
Figura 2.2 mostra o resultado obtido da análise.
CAPÍTULO 2. SIMULATED ANNEALING ACOPLADO 26
Figura 2.2 – Gráfico da soma dos custos médios normalizados pelo valor da variância limite, cha-
mada de variância desejada σ2D (expressa no percentual de seu valor máximo). O custo
médio foi calculado sobre 50 execuções, cada uma para 14 funções.
% da variância desejada
So
m
a
do
s
cu
st
o
s
n
o
rm
al
iz
ad
o
s
Fonte: Xavier-de-Souza et al., 2010.
Um simples controle pode então ser formulado como se segue.
se σ2 < σ2D, T ac ← T ac(1−α);
se σ2 ≥ σ2D, T ac ← T ac(1+α).
onde σ2D é a variância desejada (99% do valor máximo da variância) e α é a taxa de crescimento
ou decaimento da temperatura de aceitação, normalmente na faixa de (0,0.1] (XAVIER-DE-
SOUZA et al., 2010, p.326). Quando o valor da variância está abaixo do valor desejado, a
temperatura de aceitação diminui por um fator de 1−α; caso contrário, o seu valor é multi-
plicado por 1+α. Elevados valores de α torna o processo de busca do algoritmo totalmente
aleatória.
Durante a execução do CSA, os diversos otimizadores SA possuirão valores energéticos di-
ferentes e, portanto, alguns otimizadores possuirão baixas e outros elevadas probabilidades de
aceitação. Durante a fase de aumento de temperatura, os otimizadores com baixa probabilidade
de aceitação passarão a ter maiores chances de realizar exploração, enquanto que os otimiza-
dores com elevados valores probabilísticos terão tais chances reduzidas. Isso tentará igualar
as probabilidades de aceitação dos otimizadores SA. O caso inverso é análogo. Ao reduzir a
temperatura, os otimizadores com baixas probabilidades terão menores probabilidades de acei-
tação, ao passo que os otimizadores com elevadas probabilidades terão maiores chances. A
Figura 2.3 mostra ambos os casos.
CAPÍTULO 2. SIMULATED ANNEALING ACOPLADO 27
Figura 2.3 – Comportamento da probabilidade de aceitação dos otimizadores SA com a variação da
temperatura. G1 representa os otimizadores com menores probabilidades de aceitação
e G2 aqueles com as altas probabilidades. Caso a temperatura aumente, há maiores
chances das probabilidades de aceitação de G1 e G2 se aproximarem. Caso haja redu-
ção da temperatura, tais probabilidades terão maiores chances de se distanciarem.
P
rob
abilid
ad
e
G1G1
G2
G2
Baixas Altas
Temperaturas Temperaturas
Refinamento
Exploração
Fonte: Elaboração própria, 2013.
O controle da variância de probabilidade evita que otimizadores com soluções energetica-
mente parecidas se restrinjam a buscar soluções muito parecidas. Quando esse caso é verifi-
cado, a temperatura é aumentada e os otimizadores tendem a se espalhar novamente no espaço
de busca. Esse efeito é visualizado na Figura 2.4. Cada ponto verde representa um otimizador.
Inicialimente os otimizadores possuem soluções energeticamente parecidas e, ao aumentar a
temperatura, os otimizadores se espalham no espaço de busca.
Figura 2.4 – Comportamento dos otimizadores com o controle da variância de probabilidade de
aceitação. Quando as soluções são semelhantes, o algoritmo procura espalha-los pelo
espaço de busca.
-3
-2
-1
0
1
2
3
-3
-2
-1
0
1
2
3
0
10
20
30
XY
E
-3
-2
-1
0
1
2
3
-3
-2
-1
0
1
2
3
0
10
20
30
XY
E
Aumento da
Temperatura
Fonte: Elaboração própria, 2013.
Para Xavier-de-Souza et al. (2010), o controle da variância traz consigo uma série de van-
tagens. Ela substitui o escalonamento para a temperatura de aceitação e, mais importante, fun-
ciona para qualquer temperatura de aceitação inicial. Isso é importante porque a configuração
de parâmetros iniciais em SA é, na maioria das vezes, um processo muito experimental. Com
essa abordagem, podem-se reduzir dois problemas de inicialização de uma vez: 1) a escolha do
CAPÍTULO 2. SIMULATED ANNEALING ACOPLADO 28
escalonamento da temperatura de aceitação e 2) a escolha de uma temperatura aceitação inicial.
Em contrapartida, duas novas variáveis foram introduzidas, i.e., α e σ2D, mas esses parâmetros
possuem a faixa de operação bem definida e são menos dependentes do problema de otimização.
O escalonamento da temperatura de geração T é comumente realizado linearmente. Con-
sidere T0 como a temperatura de geração inicial e k o número de iterações. O escalonamento
linear pode ser expresso da seguinte forma:
T =
T0
k+1 . (2.14)
Semelhante ao Simulated Annealing, é possível utilizar a inversa da função de distribuição
acumulada de Cauchy para gerar soluções candidatas yi. Tome rnd como um número aleatório
de distribuição uniforme [0,1]. A solução candidata yi do i-ésimo otimizador pode ser definida
da seguinte forma:
yi = xi + tk tan
[
pi
(
rnd− 1
2
)]
. (2.15)
Assim, o algoritmo da implementação do Simulated Annealing Acoplado pode ser definido
como no Figura 2.5.
As Figuras 2.6 e 2.7 mostram dois exemplos de espaço de busca e o comportamento do CSA
com 4 otimizadores em busca do ótimo global. Nestas duas figuras, cada otimizador é represen-
tado por uma cor. Cada ponto mostra uma solução aceita pelo respectivo otimizador. Verifica-se
que a busca percorre tanto boas soluções (refinamento) quanto péssimas (exploração). Cabe des-
tacar que o CSA observou outras soluções, no entanto elas não estão representadas no gráfico
por não serem aceitas no processo de refinamento de soluções e de exploração do espaço de
busca.
CAPÍTULO 2. SIMULATED ANNEALING ACOPLADO 29
Figura 2.5 – Pseudocódigo do Algoritmo Simulated Annealing Acoplado.
1) Inicialização:
Atribua soluções iniciais aleatórias a Θ
Avalie os custos E(xi), ∀xi ∈Θ
Calcule o termo de acoplamento γ
Defina as temperaturas iniciais de T e T ac
2) Geração:
Gere uma possível solução yi para cada elemento de Θ de acordo com xi, ∀xi ∈ Θ
Avalie os custos de todas as possíveis soluções: E(yi),∀i = 1, . . . ,m
3) Avaliação:
Faça xi ← yi se:
a) E(yi)≤ E(xi)
b) AΘ > r, onde r é um número aleatório de distribuição uniforme [0,1]
Calule o termo acoplado γ
4) Atualização:
Atualize T ac de acordo com a regra
Se σ2 < σ2D então T ac = T ac(1−α)
Se σ2 > σ2D então T ac = T ac(1+α)
Decremente a temperatura de geração T de acordo com o escalonamento escolhido
5) Parada:
Pare se o critério de parada foi alcançado
Senão volte ao passo 2
Fonte: Adaptado de Xavier-de-Souza et al., 2013.
CAPÍTULO 2. SIMULATED ANNEALING ACOPLADO 30
Figura 2.6 – Exemplo 1 de espaço de busca multimodal e percurso realizado pelo CSA com 4
otimizadores
(a) Espaço de busca multimodal
(b) Percurso do CSA com 4 otimizadores no espaço de busca multimodal
-10 -8 -6 -4 -2 0 2 4 6 8 10
-10
-8
-6
-4
-2
0
2
4
6
8
10
2
4
6
8
10
12
14
16
18
20
22
Contorno
Otimizador 1
Otimizador 2
Otimizador 3
Otimizador 4
Fonte: Elaboração própria, 2013.
CAPÍTULO 2. SIMULATED ANNEALING ACOPLADO 31
Figura 2.7 – Exemplo 2 de espaço de busca multimodal e percurso realizado pelo CSA com 4
otimizadores
(a) Espaço de busca multimodal
-500
-400
-300
-200
-100
0
100
200
300
400
500
-500
-400
-300
-200
-100
0
100
200
300
400
500
0
200
400
600
800
1000
1200
1400
1600
1800
(b) Percurso do CSA com 4 otimizadores no espaço de busca multimodal
-500 -400 -300 -200 -100 0 100 200 300 400 500
-500
-400
-300
-200
-100
0
100
200
300
400
500
200
400
600
800
1000
1200
1400
1600
Contorno
Otimizador 1
Otimizador 2
Otimizador 3
Otimizador 4
Fonte: Elaboração própria, 2013.
3 Escalabilidade e Eficiência Paralela
3.1 Motivações e Justificativas
Durante os anos de 1960, o cofundador da Intel Gordon Moore observou um aumento expo-
nencial no número de transistores por circuito integrado e previu que essa tendência continuaria,
predição hoje conhecida como Lei de Moore. A Figura 3.1 mostra a evolução na quantidade de
transistores nos processadores Intel.
Figura 3.1 – Quantidade de transistores nos processadores Intel. O aumento da quantidade de
transistores ao longo dos anos é discutido pela Lei de Moore.
Fonte: Held et al., 2010.
Devido aos esforços em pesquisa e desenvolvimento feito pelas empresas do ramo, a du-
plicação de transistores a cada um ano e meio tem sido mantida por mais de 40 anos. Cada
avanço na tecnologia de projeto e fabricação de microprocessadores levava imediatamente a al-
goritmos mais rápidos sem qualquer modificação. Esses avanços, tratados neste trabalho como
CAPÍTULO 3. ESCALABILIDADE E EFICIÊNCIA PARALELA 33
verticais, tratam do aumento da frequência do relógio de um processador e/ou de aumento no
grau de paralelismo ao nível de instrução, como por exemplo, execução fora de ordem, especu-
lação e sistemas VLIW (Very Long Instruction Word). Entretanto, essa duplicação e o aumento
da frequência de operação dos processadores têm sido mais difíceis de se manter por causa de
diversos motivos. O primeiro é que a velocidade das memórias não aumenta tão rapidamente
quanto a dos processadores. Esse efeito é conhecido como Muralha da Memória ou Memory
Wall. Segundo Yang et al. (2006), a latência1 do acesso à memória local em 2006 era aproxi-
madamente 90ns, o que seria 300 vezes o tempo do ciclo de clock de um processador (cerca de
0.3ns). Já a latência da comunicação entre processadores de diferentes nós era perto de 2000ns,
o que corresponderia a 22 vezes a latência de acesso à memória local. Assim, do ponto de vista
das tendências de desenvolvimento de tecnologias, o intervalo tem aumentado: a velocidade de
um processador aumenta 60% ao ano, de acordo com a Lei de Moore, enquanto que o incre-
mento da velocidade de acesso à memória e anualmente de 7%, dobrando seu valor a cada 10
anos. Durante os dias da CPU i486 no final de 1980 e início de 1990, os requisitos foram 6 a
8 clocks por ciclo para acessar a memória (KOCH, 2005). Em 2005, os processadores Intel R©
Pentium R© precisavam de 224 clocks, um aumento de 20 vezes. Estes ciclos de clock podem
anular os benefícios do aumento de frequência dos processadores.
O segundo motivo diz respeito ao tamanho dos transistores. Como eles se tornam cada
vez menores, os chips atuais são mais densos e precisam de maiores comprimentos de fios de
interconexão. Koch (2005) afirma que devido a essas conexões com centenas de milhares de
metros de comprimento, surgem os atrasos de propagação de informação no caminho, podendo
cancelar parcialmente o aumento de transistores.
O terceiro motivo, e talvez o mais importante, é o insustentável aumento no consumo de
energia. O consumo de Energia aumenta proporcionalmente com a frequência de operação
(KOCH, 2005, p.4). Esse efeito é conhecido como Muralha de Energia ou Power Wall. O nú-
mero de transistores por chip aumentou nos últimos anos e o novo desafio da engenharia é traba-
lhar na criação de dispositivos elétricos que consumam menos energia e produzam menos calor.
Em 1993, a título de exemplo, os processadores Intel R© Pentium R© possuiam aproximadamente
3 milhões de transistores, enquanto que o processador Intel R© Itanium R© 2 em 2005 possuiam
cerca de 1 bilhão de transistores. Segundo comenta Koch (2005), se essa taxa continuar, os
processadores Intel logo produzirão mais calor por centímetro quadrado que a superfície do sol
- é por isso que o problema do calor já estabelece difíceis limites para o aumento da frequência.
A situação se agrava quando se parte para uma esfera global. É comum que as famílias pos-
suam computadores em casa. As escolas, colégios, universidades e empresas também partilham
dos mesmos bens. Nos últimos 10 anos, vê-se um crescente aumento dos dispositivos portá-
1Latência é uma medida do atraso de tempo experimentado por um sistema
CAPÍTULO 3. ESCALABILIDADE E EFICIÊNCIA PARALELA 34
teis, como relógios, celulares, tablets, MP4, entre outros. Todos esses dispositivos possuem
uma estrutura semelhante, ou seja, contêm processadores, memórias e processam dados. Dessa
forma, a busca por geração e uso da energia de forma racional se torna um dos focos do mundo
contemporâneo e um grande desafio para as gerações futuras.
Em 2005, a indústria mudou o curso de projeto de microprocessadores. A Intel, seguindo o
caminho dos processadores Power 4 da IBM e Niagara da Sun Microsystems, anunciou que seus
processadores de alto desempenho iriam ser compostos de múltiplos núcleos de processamento.
Desde então, devido à dificuldade de se manter a regularidade de avanços verticais, a tendência
da indústria de microprocessadores vem sendo caracterizada por esta forma de avanço, definido
como horizontal. Esta tendência vem sendo chamada de Era Multicore ou era de múltiplos nú-
cleos, detalhada por Koch (2005) e Borkar (2007), cuja ideia engloba o princípio de duplicação
da quantidade de núcleos de processamento em um único chip a cada geração.
Os chips multicore podem realizar mais trabalhos a cada ciclo, portanto podem ser projeta-
dos para operar em menores frequências quando comparadados com sua contraparte de único
núcleo. Como o consumo de energia aumenta quadraticamente com a velocidade de operação,
as arquiteturas multicore oferecem um dos meios para solucionar o problema da muralha de
energia. A Figura 3.2 mostra que a partir de 2005 os ganhos de velocidade de operação dos
processadores são cada vez menores.
Figura 3.2 – Média de frequência de operação dos processadores de 2000 ate 2012. A partir de 2005
percebe-se uma menor taxa de crescimento da frequência, já que os processadores
começam a possuir múltiplos núcleos. Os dispositivos portáveis possuem uma menor
frequência de operação porque necessitam de um menor consumo energético.
PC Desktop Portável
3/
00
9/
01
6/
02
3/
03
9/
04
6/
05
3/
06
9/
07
6/
08
3/
09
9/
10
6/
11
3/
12
12
/0
0
12
/0
3
12
/0
6
12
/0
9
0.0
0.5
1.0
1.5
2.0
2.5
3.0
G
ig
ah
er
tz
(G
H
z)
Fonte: Tech Talk (acesso em 12 dez. 2012).
CAPÍTULO 3. ESCALABILIDADE E EFICIÊNCIA PARALELA 35
Além disso, o processamento multicore pode melhorar a experiência do usuário em muitos
aspectos, como a melhoria do desempenho de computação e largura de banda de atividades,
aumentando o número de tarefas que podem ser realizadas simultaneamente e aumentando o
número de usuários que podem utilizar o mesmo dispositivo. Isto pode significar uma thread2
em execução a partir de um aplicativo e uma segunda thread executando o sistema operacional,
ou threads paralelas executando em um único aplicativo, ou outras combinações de uso. Koch
(2005) diz que as aplicações multimídia são especialmente propícias para discussão de nível de
paralelismo, já que muitas de suas operações podem ser executadas em paralelo.
Para que os avanços da era multicore sejam traduzidos em mais desempenho para um deter-
minado algoritmo, é necessário que esse algoritmo suporte a tendência de avanços horizontais
através de execução paralela. Apesar dessa nova era da computação beneficiar imediatamente
o processamento de diversas tarefas ao mesmo tempo, a aceleração de uma tarefa ou algoritmo
isolado requer um esforço adicional, que muitas vezes não é trivial. Alguns problemas que
dificultam a implementação de algoritmos paralelos serão discutidos na próxima seção.
3.2 Problemas no paralelismo
Especificar um algoritmo paralelo envolve mais que simplismente especificar passos. É
importante obter qualquer benefício de desempenho do uso da computação paralela. Na busca
de desempenho, alguns problemas devem ser superados. Segundo Gramma et al. (2003), na
prática, especificar um algoritmo paralelo não trivial pode incluir alguns ou todos os itens a
seguir:
• identificar porções de trabalho que podem ser processados concorrentemente;
• mapear porções de trabalho em múltiplos processos executando em paralelo;
• distribuir os dados de entrada, de saída e intermediários associados com o programa;
• gerenciar o acesso às dados compartilhados pelos múltiplos processadores;
• sincronizar os processadores em vários estágios de execução do programa paralelo.
O processo de dividir uma computação em partes menores, algumas ou todas das quais
podem potencialmente ser executadas em paralelo é chamado de decomposição (GRAMMA
et al., 2003). As tarefas são unidades de computação definidas pelo programador em que a
2Uma thread, ou linha de execução, é a menor seqüência de instruções programadas que pode ser gerenciada
de forma independente pelo escalonador de processos do sistema operacional. A implementação de uma thread
e processo diferem de um sistema operacional para outro, mas na maioria dos casos, uma thread está contida
no interior de um processo. Várias threads podem existir dentro do mesmo processo e partilhar recursos, como
memória, enquanto os processos diferentes não compartilham esses recursos.
CAPÍTULO 3. ESCALABILIDADE E EFICIÊNCIA PARALELA 36
computação principal é subdividida por meio de decomposição. A execução de diversas tarefas
simultaneamente é a chave para reduzir o tempo de processamento do problema.
O número e o tamanho de tarefas no qual o problema é decomposto determina sua granula-
ridade (GRAMMA et al., 2003). A granulação fina ocorre quando a decomposição é realizada
sob um elevado número de pequenas tarefas. A decomposição com um pequeno número de
grandes tarefas é chamada de granulação grossa.
As tarefas podem ser executadas juntas ou em alguma sequência predefinida. Algumas tare-
fas podem eventualmente utilizar dados que são produzidos por outras tarefas e, portanto, devem
esperar essas tarefas terminarem suas execuções. Essa dependência entre tarefas caracteriza o
sincronismo. O conceito de grau de concorrência surge neste contexto. O grau de concorrên-
cia é o número de tarefas que podem ser executadas concorrentemente. Segundo Gramma et
al. (2003), o número máximo de tarefas que podem ser executadas simultaneamente em um
programa paralelo em qualquer tempo é conhecido como o gráu máximo de concorrência. Eles
também comentam que um indicador mais útil do desempenho de um programa paralelo é o
grau médio de concorrência, que é o número médio de tarefas que podem ser executadas si-
multaneamente durante toda a duração da execução do programa. Como o grau máximo de
concorrência mostra o nível de concorrência máximo em qualquer parte da implementação,
pode ocorrer que a execução de uma parte do programa execute com um elevado grau de con-
corrência, enquanto que as demais partes executem com baixo grau. Dessa forma, o valor que
melhor expressa o nível de concorrência é o grau médio de concorrência. O intuito é maximar
o grau médio de concorrência.
Além da dependência entre tarefas caracterizar o sincronismo, ela não é única. O gerencia-
mento de dados compartilhados entre as tarefas também podem motivar o uso de sincronismo.
As operações com dados compartilhados podem necessitar uma ordem de execução. Um dos
meios para evitar concorrência nestes casos é utilizar região crítica. Em programação concor-
rente, uma região crítica é uma área de código de um algoritmo que tem acesso a um recurso
compartilhado que não pode ser acessado concorrentemente por mais de uma tarefa, processo
ou linha de execução. Uma técnica utilizada para evitar que duas tarefas, processos ou threads
acessem simultaneamente um recurso compartilhado é a exclusão mútua. Um meio simples de
obter exclusão mútua é através de semáforo binário, uma variável compartilhada que só pode
assumir dois valores distindos, 0 e 1, por exemplo. O travamento por semáforo deve ser feito
antes de utilizar o recurso, e após o uso o recurso deve ser liberado. Enquanto o recurso esti-
ver em uso, qualquer outra tarefa que o utilize deve esperar a liberação. A Figura 3.3 exibe o
funcionamento de uma região crítica.
A consequência do sincronismo é o overhead. No atual contexto, o overhead é qualquer
tempo de computação excessivo que não é utilizado para computar dados. O tempo que uma
tarefa gasta sem computar dados esperando uma outra tarefa terminar sua execução é um exem-
CAPÍTULO 3. ESCALABILIDADE E EFICIÊNCIA PARALELA 37
Figura 3.3 – Funcionamento de uma região crítica. A tarefa B somente acessa a região crítica após
a tarefa A liberá-la. Enquanto não é liberada, a tarefa B permanece bloqueada.
Tarefa A
Tarefa B
A entra na região crítica
A sai da região crítica
B bloqueado
B tenta entrar na região crítica
B entra na região crítica
B sai da região crítica
Tempo
Fonte: Elaboração própria, 2013.
plo de overhead. O balanceamento de carga é um exemplo que pode gerar overhead. Como as
tarefas não consumem necessariamente o mesmo tempo de computação, poderá existir tarefas
com maior carga de trabalho que outras, o que necessita maior tempo de processamento. Com
tarefas sendo executadas mais rapidamente que outras, poderá existir tarefas aguardando a exe-
cuções de outras, o que causa o overhead. Aplicar granularidade grossa poderá causar o efeito
anteriormente comentado. O efeito causado pela granularidade fina poderá resultar em elevado
overhead de comunicação. Este tipo de overhead acontece durante a troca de informação entre
tarefas. Ele é o tempo de comunicação entre a requisição e a resposta. A decisão destes aspectos
deverá ser realizada em algum momento durante o desenvolvimento do algoritmo.
Os problemas comentados anteriormente fazem parte das dificuldades enfrentadas durante o
processo de desenvolvimento de um algoritmo paralelo. Após implementado, o algoritmo deve
ser analisado em diversos pontos. Entre eles, destacam-se: a análise da qualidade da solução
processada e a escalabilidade paralela de um sistema. Para esta última, utilizam-se as métricas
de escalabilidade, que são detalhadas a seguir.
3.3 Métricas de Escalabilidade Paralela
Muitas pesquisas atuais, diante da era multicore, visam criar processos sistemáticos de pa-
ralelização de algoritmos. Diversas tentativas foram feitas na direção de compiladores paraleli-
zadores. No entanto, esses compiladores se aplicam apenas a uma classe restrita de problemas
e, no corrente estágio da era multicore, podem falhar em empregar eficientemente todos núcleos
de um microprocessador multicore. Mesmo que consigam, não há garantias quanto a eficiência
da paralelização automática do algoritmo. Portanto, atualmente, é papel do programador refi-
CAPÍTULO 3. ESCALABILIDADE E EFICIÊNCIA PARALELA 38
nar seu código, identificando e corrigindo os pontos que causam baixo desempenho. Entretanto,
essa etapa é considerada complexa para a maioria dos usuários em virtude da grande quantidade
de parâmetros que precisam ser manipulados para se obter ganhos de desempenho.
Todo algoritmo paralelo possui uma fração de código que necessita ser executado sequen-
cialmente e uma outra fração que é executada concorrentemente. Segundo Amdhal (1967), a
porção serial do código limita fortemente a aceleração de algoritmos paralelos. Ele traz consigo
uma consequência muito importante para a era multicore: os algoritmos com largo perfil se-
quencial tem pouco a ganhar com avanços horizontais da era; em contra partida, é provável que
algoritmos tidos como sequencialmente menos eficientes possam ter um largo perfil paralelo e
se tornem mais atrativos. Tais perfis estão diretamente interligados à arquitetura do computador
e à implementação do algoritmo.
Para simplificar os apectos de análise de escalabilidade dos algoritmos, a análise será reali-
zada sob os aspectos da Lei de Amdahl e da Lei de Gustafson. Em ambas as análises, é comum
o termo tamanho do problema. Ele pode se referir, por exemplo, ao tamanho de uma matriz, ao
número de pontos a ser analisado pelo algoritmo, ao número de dimensão de uma função, etc.
As duas análises serão comentadas nas seções a seguir.
3.3.1 Escalabilidade de Amdahl
Para essa análise de escalabilidade, considere speedup S, definido como a divisão do tempo
de processamento serial Ts pelo tempo de processamento paralelo Tp. O speedup expressa em
quantas vezes o algoritmo paralelo é mais rápido que o sequencial.
S = Ts
Tp
(3.1)
Para o speedup, valores maiores que m (número de processadores ou CPUs) mostram spe-
edup superlinear; abaixo, expressam sublinearidade, e speedup linear quando igual a m. Na
prática, speedup superlinear pode ser observado em alguns casos. Segundo Gramma et al.
(2003), isso ocorre quando o trabalho realizado pelo algoritmo serial é maior que a formulação
paralela ou devido a recursos de hardware que colocam a implementação de série em desvanta-
gem. Por exemplo, os dados para um problema pode ser demasiado grande para caber dentro do
cache de um único elemento de processamento, degradando assim o seu desempenho, devido à
utilização de elementos de memória mais lentas. Mas quando dividido entre vários elementos
de processamento, as partições de dados individuais seria pequeno o suficiente para caber em
seus respectivos elementos de processamento de caches. Assim, considera-se que a meta para
os algoritmos paralelos é alcançar o speedup linear.
CAPÍTULO 3. ESCALABILIDADE E EFICIÊNCIA PARALELA 39
A primeira noção de escalabilidade é a de Amdahl, que é definida como a forma como
o tempo de execução varia de acordo com o número de processadores de um problema com
tamanho fixo. Para alguns algoritmos paralelos, o aumento do número de unidades de proces-
samento (CPU’s), para um problema de tamanho fixo, reduz o speedup. Esta característica é
evitada. Para outro grupo de algoritmos paralelos, quanto maior for o número de unidades de
processamento, maior será o speedup. Neste último caso, todavia, o speedup possui um valor
máximo devido à fração serial do código.
Segundo a Lei de Amdahl, a velocidade de processamento paralelo é limitada. Ela afirma
que uma pequena porção do programa que não pode ser paralelizada limitará o aumento de
velocidade disponível com o paralelismo. A consequência é que haverá um limite onde o pro-
cessamento paralelo pode ser aplicado. A Figura 3.4 exemplifica tal limitação. Nela existem
dois algoritmos, Alg. A e Alg. B, de tamanhos diferentes, cujos speedups aumentam com a
quantidade de CPU’s. S e P representam a porção serial e paralela do código, respectivamente.
Alg. B possui maior speedup, quando comparado ao Alg. A, porque possui menor parcela serial
e maior paralela. Apesar disso, seu speedup será limitado, já que o paralelismo não reduz o
tempo de processamento da porção serial.
Figura 3.4 – Exemplo da limitação que a Lei de Amdahl impõe ao speedup dos algoritmos parale-
los. A porção serial limitará o speedup, pois não poderá se beneficiar do paralelismo.
Códigos com maior percentual paralelo ganham mais com o processamento paralelo
e, portanto, possuem melhores speedups.
Alg. A
Alg. B
S P
S P
S P
S P
S P
S P
S P
S P
1 CPU
2 CPUs
4 CPUs
1000 CPUs
Alg. A
Alg. B
Ideal
#CPUs
S
Tamanho fixo do problema
Tamanho do problema
Fonte: Elaboração própria, 2013.
3.3.2 Escalabilidade de Gustafson
Neste caso, considere a eficiência E f como a divisão do speedup S por m processadores,
como mostra a Equação 3.2. A eficiêcia é um valor, normalmente entre zero e um, que expressa
o percentual de speedup alcançado pelo algoritmo em relação ao speedup linear, i.e., estima o
CAPÍTULO 3. ESCALABILIDADE E EFICIÊNCIA PARALELA 40
quão bem os processadores estão sendo utilizados para resolver o problema.
Para a eficiência, valores acima de 1 indicam eficiência superlinear; abaixo, eficiência subli-
near, e igual a 1, eficiência linear. Como a meta na análise de escalabilida de Amdahl é alcançar
speedup linear, ou seja, S = m, a meta na análise de escalabilidade de Gustafson é alcançar
eficiência unitária.
E f = S
m
(3.2)
Apesar da eficiência mostrar o quão bom é o algoritmo paralelo, seu valor pode ser inapro-
priadamente utilizado para mensurar a escalabilidade. Para pequenos problemas, a porção serial
do código pode ocupar um percentual maior, enquanto que para grandes problemas tal porção
poderia ocupar um percentual menor. Logo, para comprovar a escalabilidade de um algoritmo
paralelo, faz-se necessário aumentar o tamanho do problema e verificar o comportamento da
eficiência. Espera-se um aumento de eficiência com o crescimento do problema. Os algoritmos
que possuem este comportamento da eficiência são considerados escaláveis. Isso ocorre porque
incrementar o tamanho do problema para algoritmos escaláveis aumenta mais a porção paralela
P que a fração serial S, como mostra Alg. B na Figura 3.5. Esta será a principal análise utilizada
na avaliação da escalabilidade do Simulated Annealing Acoplado.
Figura 3.5 – Comportamento dos algoritmos paralelos pela Lei de Gustafson. Para algoritmos
escaláveis, o aumento do tamanho do problema incrementa mais a porção paralela
P que a fração serial S. O algoritmo paralelo escalável, portanto, terá uma maior
eficiência, pois ele atuará na maior parte do código (Alg. B). Este fato não ocorre nos
algoritmos com baixa escalabilidade (Alg. A).
S P
S P
S P
S PAlg. A
Alg. B
S P
S
PS
P
S P
Alg. A
Alg. B
Ideal
Tamanho do problema
Ef Número fixo de CPUs
1
Tamanho do problema
Aumento do
tamanho do
problema
Fonte: Elaboração própria, 2013.
4 Simulated Annealing Acoplado Paralelo
Durante o desenvolvimento do algoritmo, algumas dificuldades surgiram e motivaram mu-
danças na implementação do CSA. A seção 4.1 mostra os problemas encarados neste desen-
volvimento e as diferentes versões de implementação paralela do CSA. A seção 4.2 exibe a
implementação paralela definitiva do CSA.
4.1 Histório de implementações
O Simulated Annealing Acoplado consiste em um grupo de vários otimizadores Simulated
Annealing (SA) trabalhando em conjunto na busca do mínimo global. Cada otimizador SA tem
liberdade de percorrer o espaço de busca, procurar uma própria solução e avaliá-la. A Figura 4.1
mostra um exemplo de espaço de soluções e de diversos otimizadores SA, representados em
verde.
Figura 4.1 – Exemplo de espaço de soluções com os otimizadores SA. Cada ponto verde representa
um otimizador SA que está procurando uma boa solução no espaço de busca.
−3
−2
−1
0
1
2
3
−3
−2
−1
0
1
2
3
5
10
15
20
25
Fonte: Elaboração própria, 2013.
Os otimizadores se comunicam uns com os outros, informando-os o valor da função custo o
CAPÍTULO 4. SIMULATED ANNEALING ACOPLADO PARALELO 42
qual ele se encontra - o que comumente é chamado de a situação do estado corrente. Durante
a busca, os otimizadores decidem se irão refinar a solução que já possuem (refinamento) ou
se partirão para locais do espaço de soluções menos favoráveis (exploração) na esperança de
encontrar um ótimo global. Para realizá-las, os otimizadores verificam os estados correntes dos
demais. Se houver uma grande diferença entre os estados correntes, eles tenderão a refinar as
soluções atuais. Caso não haja tanta diferença, os otimizadores tentarão partir para outros locais
do espaço de busca, mesmo que esses sejam desfavoráveis. O valor que pondera esta decisão
é a variância de probabilidade. Essa variância de probabilidade gera um número baseado no
estado corrente de todos os otimizadores SA. Percebe-se, portanto, que deve haver uma troca de
informações entre cada otimizador sobre o seu estado corrente e que tal valor seja atualizado.
A implementação do CSA foi realizada utilizando OpenMP e C++. OpenMP é uma in-
terface de programação de aplicativo (API) para a programação multi-processo de memória
compartilhada em múltiplas plataformas em C/C++ e Fortran. Ela implementa o modelo de
execução multitarefa, que permite que várias threads possam existir dentro do contexto de um
processo único. Estas threads compartilham recursos do processo, mas são capazes de executar
de forma independente. Ao serem criadas, as threads são distribuídas aos processadores por um
escalanador de tarefas segundo algum algoritmo de escalonamento. Vale frisar que pode haver
mais de uma thread sendo executada em um único processador. Na implementação, cada thread
representa um único otimizador. Entretanto, como o algoritmo do escalonador de tarefas visa
utilizar o máximo da computação disponível e o número de otimizadores foi menor ou igual ao
número de processadores, sempre ocorria a distribuição de uma thread para cada processador,
isto é, um único otimizador sendo executado por processador.
Em sua versão original, comentada por Xavier-de-Souza et al. (2010), o CSA foi implemen-
tado de forma síncrona. O pseudocódigo do algoritmo Simulated Annealing Acoplado é descrito
na Figura 2.5. Inicialmente, os otimizadores são criados, cada um contendo uma solução pró-
pria. As temperaturas de geração e de aceitação são únicas e comuns a todos os otimizadores.
Após a inicialização de cada otimizador, cada um gerará e avaliará de forma assíncrona uma
possível solução, aceitando-a ou não. Antes de realizar a atualização das temperaturas e poste-
riormente o critério de parada, uma barreira é implementada, de forma a sincronizar todos os
otimizadores neste ponto. É então realizado o cálculo da variância da função de probabilidade
de aceitação e a atualização das temperaturas por um dos otimizadores. O ciclo assíncrono de
geração e avaliação é então reiniciado se o critério de parada não for alcançado.
A mudança que todas as versões das implementações do CSA deste trabalho sofreram foi a
retirada do sincronismo antes da atualização das temperaturas. A mudança visa reduzir o tempo
de overhead que ocorre no caso síncrono. Dessa forma, o trabalho não força a atualização das
temperaturas a cada iteração do algoritmo, o que muda a idéia inicial do algoritmo. Implementar
o CSA assíncrono reveleu problemas não encarados pela versão síncrona. Os problemas enca-
CAPÍTULO 4. SIMULATED ANNEALING ACOPLADO PARALELO 43
rados serão discutidos juntamente com as respectivas versões de implementação assíncrona do
CSA. Para melhor entendimento do desenvolvimento das versões assíncronas implementadas,
tome como base o pseudocódigo do algoritmo Simulated Annealing Acoplado encontrado na
Figura 2.5.
A primeira idéia de compartilhamento das soluções correntes entre os otimizadores surgiu
a partir de um contador global de iterações. Esse contador era compartilhado entre os otimiza-
dores. Cada otimizador partiria da 1a iteração e a incrementaria à medida que fosse realizando
as buscas. Um otimizador somente calcularia a variância de probabilidade se estivesse numa
iteração maior que o valor do contador. O contador seria atualizado com o valor da iteração do
último otimizador que calculou a variância de probabilidade. Dessa forma, somente os otimi-
zadores mais adiantados poderiam alterar a variância de probabilidade e, consequentemente, o
curso do algoritmo em refinar e explorar. Isso também permitiria que os otimizadores atrasados
pudessem se aproximar e, quem sabe, realizar alterações nas iterações futuras. Infelizmente a
idéia não obteve êxito. Durante os testes verificou-se que as alterações somente eram realizadas
por um grupo pequeno de otimizadores. Além disso, como a leitura dos estados correntes de
cada otimizador não impedia que outros otimizadores atualizassem seus estados, alguns oti-
mizadores poderiam calcular a variância de probabilidade enquanto outro otimizador ainda o
estava calculando. As consequências eram diversas soluções desatualizadas, incoerência pro-
babilística no cálculo da função de probabilidade de aceitação AΘ. A estratégia, portanto, foi
alterada.
A idéia seguinte tentou impedir que qualquer otimizador calculasse a variância de proba-
bilidade enquanto um outro estivesse calculando. Caso o otimizador se deparasse com essa
situação, ele ignora essa fase e continua com o ciclo normal do SA. A idéia parecia resolver
os problemas de incoerência probabilística, mas não resolveu. Agora, a incoerência probabi-
lística acontecia não pela leitura dos dados ou cálculo da variância de probabilidade, mas na
atualização do seu estado corrente. Ou seja, não adiantava impedir que os demais otimizado-
res calculassem a variância de probabilidade se eles estavam alterando seus estados correntes.
Além disso, como ainda era utilizada a idéia do contador, verificou-se também que somente
alguns otimizadores adentravam a região crítica para o cálculo do variância de probabilidade.
Então, decidiu-se retirar o contador de iterações compartilhado e ampliar a região crítica para
que englobasse tanto a atualização das soluções correntes de cada otimizador quanto o cálculo
da variância de probabilidade. Essa alteração conseguiu resolver tanto o problema de incoe-
rência probabilística como o da baixa quantidade de otimizadores calculando a variância da
probabilidade, tornando-se a implementação final do CSA.
CAPÍTULO 4. SIMULATED ANNEALING ACOPLADO PARALELO 44
4.2 Implementação do CSA
A introdução de uma região crítica foi a principal característica inserida na versão paralela
proposta. Foi necessário inserir uma região crítica no algoritmo, pois existem recursos que
devem ser compartilhados de forma organizada e que envolver operações que devem ser rea-
lizadas sem concorrência de threads. Segundo expresso nas Equações 2.8 e 2.9, é necessário
utilizar todas as soluções correntes do sistema. Qualquer alteração em alguma das energias
correntes durante o processo de cálculo de AΘ pode acarretar inconsistência probabilística, pois
seriam utilizados valores desatualizados. Logo, os recursos compartilhados entre as threads são
variáveis residentes na região crítica. Estas variáveis são:
• Variáveis compartilhadas:
– as soluções correntes xi do i-ésimo otimizador SA;
– temperatura de geração T ;
– temperatura de aceitação T ac.
• Variáveis não compartilhadas (local):
– γ (utilizada no cálculo da função de probabilidade de geração. AΘ);
– Variância de probabilidade de aceitação σ2.
Na Figura 4.2, a implementação final do Simulated Annealing Acoplado é dada. Todo o
processo de busca ocorre simultaneamente e tira máximo de proveito do paralelismo, a começar
pela inicialização de parâmetros. Somente o necessário é executado em serial. Dessa forma, a
porção paralela do código é ampliada e o desempenho melhorado.
No começo, as temperaturas e dimensão do problema são inicializadas, e a variância de-
sejada calculada. Uma região paralela é criada e cada thread corresponde a um otimizador
Simulated Annealing. Cada otimizador encontrará uma solução aleatória e calculará seu custo.
Antes do laço de iterações começar, é necessário calcular γ. Somente um dos otimizadores re-
aliza essa ação logo após esperar todos os outros inicializarem. A partir dai, cada otimizador
gerará possíveis soluções, aceitando-as ou não. Então, caso a solução vizinha seja aceita, cada
otimizador entrará obrigatoriamente na região crítica para atualizar sua solução. Para tal, os oti-
mizadores devem solicitar entrada na região crítica. Quando conseguir o acesso, ele atualizará
sua solução corrente. Se uma solução for atualizada ou a solução não for aceita durante a fase
de avaliação de solução candidata, o otimizador tentará entrar na região crítica novamente a fim
de atualizar as temperaturas T e T ac. Caso adentre na região, realizará as atualizações e ava-
liará o critério de parada; caso não consiga, somente avaliará o critério de parada. Destaca-se
que a região crítica é a mesma tanto na atualização da solução quanto das temperaturas - impe-
dindo que diferentes otimizadores SA realizem as duas operações ao mesmo tempo. Uma nova
CAPÍTULO 4. SIMULATED ANNEALING ACOPLADO PARALELO 45
iteração inicia caso o critério de parada não seja alcançado; caso contrário, o otimizador será
encerrado. O algoritmo é encerrado quando o critério de parada for alcançado. Com exeção da
fase de atualização de solução, o ciclo que inclui a geração/avaliação de soluções candidatas e
atualização de temperaturas é totalmente assíncrono. Entretanto, a adição da região crítica na
atualização das soluções causa sincronismo entre os otimizadores que necessitam atualizar suas
soluções, gerando overhead e afetando negativamente o tempo de execução do algoritmo.
Figura 4.2 – Implementação do Simulated Annealing Acoplado. Cada otimizador SA irá procurar
possíveis soluções, aceitando-as ou não. Para atualizar a sua solução, ele deverá aden-
trar a região crítica. Essa mesma região é utilizada para atualizar as temperaturas. A
região crítica única garante que ambas as operações sejam realizadas atômicamente,
evitando assim inconsistência numérica.
Fonte: Elaboração própria, 2013.
Alguns comentários podem ser tecidos diante do explicado.
• Antes de criar a região paralela, o bloco Inicialização é executado em serial;
• Na Inicialização Paralela não há problemas quanto a alteração da solução inicial xi,
afinal, o i-ésimo otimizador somente altera a i-ésima solução. O fim desta função é
bloqueante, ou seja, o bloco Calcular Gamma somente é executado quando todos os
otimizadores de Inicialização Paralela concluírem suas operações;
• Calcular Gamma, apesar de ser executado serialmente, não destrói os otimizadores an-
teriormente criados. Para tal, somente um dos otimizadores realiza a avaliação de γ en-
quanto que os outros aguardam bloqueados a finalização da avaliação;
• Geração é o bloco que exige maior esforço computacional. Um grande custo computa-
cional pode ser demandado para gerar possíveis soluções yi e avaliar E(yi), tudo depen-
dendo das restrições (caso tenha), da dimensão do problema e da função de avaliação.
Esse bloco é executado na porção paralela do código e, como tal, aumentará a eficiência
da escalabilidade paralela caso tenha elevado custo computacional;
CAPÍTULO 4. SIMULATED ANNEALING ACOPLADO PARALELO 46
• O bloco Acessar Região Crítica é um pedido bloqueante para acessar a região crítica.
Este é o único ponto do algoritmo em que os otimizadores podem ficar ociosos enquanto
esperam entrar na região crítica. O tempo ocioso tem má influência na eficiência paralela;
• Em Atualizar solução é possível acrescentar um código para guardar as melhores solu-
ções;
• O acesso ao bloco Atualizar Temperaturas é não bloqueante, ou seja, caso um otimi-
zador SA já esteja acessando a região crítica, seja neste bloco ou em Atualizar Solução,
um novo otimizador irá executar o bloco Critério de Parada;
• É comum utilizar como critério de parada um número fixo de iterações. Entre as pos-
sibilidades de fixá-lo, destacam-se duas: fixar ao otimizador e fixar ao algoritmo. Caso
se fixe em relação ao otimizador, cada otimizador será responsável por um número fixo
de iterações. Do ponto de vista paralelo, isto torna o código ineficiente, pois permite
que alguns otimizadores terminem suas operações primeiro que outros e fiquem ociosos
enquanto esperam os demais terminarem suas operações. A outra forma, fixando ao algo-
ritmo, é assíncrona quanto a divisão de iterações. Neste método cada otimizador realiza
uma iteração, verifica se alguma outra ainda falta e a realiza caso seja necessário, de modo
que os otimizadores são utilizados ao máximo. Este foi o critério de parada utilizado no
algoritmo. Uma outra possibilidade de critério de parada é baseado na qualidade da solu-
ção. Aqui, o algoritmo só pára quando alcançar uma solução tão boa ou melhor que uma
pré-definida. Este método é normalmente utilizado quando se quer comparar algoritmos
quanto ao tempo de resolução do problema;
• Os otimizadores executam o CSA de maneira assíncrona, i.e., podem existir otimizadores
executando diferentes blocos do código.
5 Experimentos e Resultados
Para a realização dos experimentos, a plataforma computacional usada é baseada em um sis-
tema com dois processadores AMD Opteron 6172, cada um com 12 núcleos de 2.1 GHz, 16 GB
DDR3 RAM, contendo a versão Ubuntu 12.04.1 LTS. O algoritmo proposto foi implementado
em C++ usando a biblioteca OpenMP.
Em todos os experimentos, os algoritmos foram testados utilizando 14 funções de referência,
descritas na Seção 5.1, e 1.000.000 avaliações da função de custo como o critério de parada.
Todas as funções foram analisadas para o caso das dimensões D = [10,20,40,80,160] e m
núcleos, com m = [4,8,12,16,20,24]. Cada núcleo executou apenas 1 otimizador SA por vez.
Para cada configuração do CSA, executam-se 25 vezes e resgata-se a melhor solução, a pior
solução, a média e o desvio padrão das soluções de cada função. Nestas análises, a dimensão D
das funções de referência é utilizada como descritor para o tamanho do problema, descrito na
seção 3.3. As funções de custo de referência, a descrição do CSA serial e dos resultados obtidos
nos experimentos serão comentados nas próximas seções.
5.1 Funções de Custo de Referência
Para garantir a qualidade da versão do CSA, experimentos foram realizados repetidas vezes
em 14 funções de referências f1− f14, com D dimensões, utilizadas por Xavier-de-Souza et
al. (2010). Todas as quatorze funções possuem custo mínimo em zero, qualquer que seja a
dimensão. Elas são detalhadas a seguir.
1. (Grupo 1: f1− f2) Funções unimodais: Elas são funções simples e fáceis de minimizar.
2. (Grupo 2: f3− f8) Funções Multimodais: Essas funções separáveis apresentam muitos
mínimos locais e são consideradas difíceis de otimizar, principalmente para enormes di-
mensões. A título de exemplo, as funções f3 e f8 são mostradas na Figura 5.1 e 5.2,
respectivamente.
3. (Grupo 3: f9− f14) Funções Multimodais rotacionadas: Apesar das funções do Grupo
2 serem consideradas problemas difíceis de minimizar, elas podem ser separadas. Essa
condição significa que o problema de minimização pode ser resolvido usando D buscas
CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 48
Tabela 5.1 – Grupo 1: Funções Unimodais e Simples Multimodais
No Função f (x) Limites
1 f1 =
D
∑
i=1
x2i [-100,100]
2 f2 =
D−1
∑
i=1
(1− xi)2 +100(xi+1− x2i )2 [-2.048,2.048]
Fonte: Xavier-de-Souza et al., 2010.
Tabela 5.2 – Grupo 2: Funções Multimodais
No Função f (x) Limites
3 f3 =−20exp
[
−0.2
√
1
D
D
∑
i=1
x2i
]
− exp
[
1
D
D
∑
i=1
cos(2pixi)
]
+20+ e [-32.768,32.768]
4 f4 =
D
∑
i=1
x2i
4000 −
D
∏
i=1
cos
(
xi√
i
)
+1 [-600,600]
5 f5 =
D
∑
i=1
[
20
∑
k=0
(0.5)kcos
(
2pi3k(xi +0.5)
)]−D 20∑
k=0
(0.5)kcos(pi3k) [-0.5,0.5]
6 f6 =
D
∑
i=1
x2i −10cos(2pixi)+10 [-5.12,5.12]
7 f7 =
D
∑
i=1
y2i −10cos(2piyi)+10 , yi =
{
xi |xi|< 12
round(2xi)
2 |xi| ≥ 12
, ∀i = 1 , . . . , D [-5.12,5.12]
8 f8 = 419×D+
D
∑
i=1
xisin|xi| 12 [-500,500]
Fonte: Xavier-de-Souza et al., 2010.
CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 49
Figura 5.1 – Função f3 do grupo 2 de funções de referência em três dimensões. A função é plotada
fora de seus limites para facilitar sua visualização.
Fonte: Elaboração própria, 2013.
Figura 5.2 – Função f8 do grupo 2 de funções de referência em três dimensões.
Fonte: Elaboração própria, 2013.
unidimensionais, onde D é a dimensão do problema. Diversas situações da vida real são
consideradas não separáveis. Portanto, para aproximar esses problemas, nesse grupo de
funções utiliza-se as versões rotacionadas das funções do grupo 2.
"Para rotacionar a função, multiplicamos o argumento X da função original pela matriz
de rotação ortogonal M para obter um novo argumento Z para funções rotacionadas. Essa
rotação de matriz é obtida usando o Método de Salomon" (XAVIER-DE-SOUZA et al.,
2010, p.327).
CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 50
Definem-se as funções do grupo como:
fn(X) = fn−6(Z) ∀n = 9 , . . . , 13 (5.1)
com
Z = Mx (5.2)
para os primeiros 5 problemas testes no grupo. A última função é definida como se segue:
f14 = f8(Z) (5.3)
com
zi =
{
yisin
(
|yi| 12
)
, |yi| ≤ 500
0.001(|yi|−500)2, |yi|> 500
, ∀i = 1 , . . . , D (5.4)
Y = Y ′+420.96 (5.5)
Y ′ = M(X−420.96) (5.6)
Essa condição é necessária para manter o ótimo local da função de Schwefel, onde é
localizado em [420.96, 420.96, . . . , 420.96], dentro dos limites da função após a rotação.
5.2 Simulated Annealing Acoplado Serial
Para realizar a análise quanto ao speedup e eficiência paralela, é necessário uma implemen-
tação serial do Simulated Annealing Acoplado, visto na seção 4.2. O pseudocódigo do CSA
serial esta descrito na Figura 5.3.
O primeiro passo é inicializar o algoritmo. Neste momento é atribuído sequencialmente
soluções aleatória a todos os otimizadores, avaliado cada uma dessas soluções, calculado o
termo de acoplamento e definido as temperaturas iniciais de geração e aceitação. Em seguida,
cada otimizador irá gerar uma solução candidata e avaliá-la, aceitando-a ou não. Após todos os
otimizadores realizarem tais operaçãoes, será calculado o termo de acoplamento e atualizado as
temperaturas de aceitação e geração. O algoritmo pára caso o critério de parada for alcançado.
No CSA serial não existe região crítica. Como a avaliação dos otimizadores é realizada
serialmente, otimizador a otimizador, não é necessário implementar a região crítica, pois não
haverá mudanças nos estados correntes dos otimizadores. Além disso, devido a impossibilidade
de implementar a assincronismo que ocorre no CSA paralelo, foi optado que o cálculo do termo
CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 51
de acoplamento e a atualização das temperaturas de aceitação e geração (item Atualização no
pseudocódigo da Figura 5.3) sejam feitos uma vez após cada laço de geração e avalização de
soluções de todos os otimizadores.
Figura 5.3 – Pseudocódigo do Algoritmo Simulated Annealing Acoplado Serial.
1) Inicialização:
Atribua soluções iniciais aleatórias a Θ
Avalie os custos E(xi), ∀xi ∈Θ
Calcule o termo de acoplamento γ
Defina as temperaturas iniciais de T e T ac
2) Para cada otimizador, faça:
2.1) Geração:
Gere uma possível solução yi do i-ésimo otimizador de acordo com xi
Avalie o custo da possível soluções: E(yi)
2.2) Avaliação:
Faça xi ← yi se:
a) E(yi)≤ E(xi)
b) AΘ > r, onde r é um número aleatório de distribuição uniforme [0,1]
3) Atualização:
Calule o termo de acoplamento γ
Atualize T ac de acordo com a regra
Se σ2 < σ2D então T ac = T ac(1−α)
Se σ2 > σ2D então T ac = T ac(1+α)
Decremente a temperatura de geração T de acordo com o escalonamento escolhido
4) Parada:
Pare se o critério de parada foi alcançado
Senão volte ao passo 2
Fonte: Elaboração própria, 2013.
5.3 Qualidade da solução
A primeira análise visa mostrar a qualidade da solução da versão paralela proposta do Si-
mulated Annealing Acoplado. Além de verificar a qualidade numérica da solução, já que é
conhecido antecipadamente o valor mínimo de cada função, o CSA serial é utilizado para com-
parar os resultados.
Na Tabela 5.3, a seguir, um conjunto simplificado de resultados obtidos nos experimentos
é mostrado. Ele inclui o valor da solução ótima, da pior, da média e o desvio padrão para
25 execuções do algoritmo utilizando 24 otimizadores, além do tempo médio de execução em
CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 52
segundos, tanto para a versão serial como paralela do CSA. Para cada uma das execuções, o
critério de parada é 1.000.000 avaliações da função de custo. As avaliações serão divididas entre
os otimizadores. Dessa forma, na média, cada otimizador realizará aproximadanente 41.667
avaliações do custo. Esse valor pode ser diferente para o CSA paralelo, o que na atual fase não é
importante, pois, devido à implementação do CSA observado na Figura 4.2, alguns otimizadores
poderão adentrar a região crítica mais que outros.
Tabela 5.3 – Qualidade de solução do Simulated Annealing (SA), do Coupled Simulated Annealing
(CSA) serial e paralelo para D = 10, 25 execuções. O CSA é executado com 24
otimizadores. O CSA é executado com 24 otimizadores. Das 25 execuções, resgata-se
a melhor solução, a pior solução, bem como calcula-se a média, o desvio padrão e o
tempo médio de execução em segundos dos algoritmos.
Função Algoritmo Melhor Pior Média das Desvio Tempo
Solução Solução Soluções Padrão Médio
f1
SA 5.75E-006 1.81E-005 1.35E-005 3.55E-006 1.53E+000
CSA Serial 5.90E-006 2.38E-005 1.55E-005 4.61E-006 1.30E+000
CSA Paralelo 8.42E-007 2.91E-006 1.73E-006 5.34E-007 2.24E+000
f2
SA 1.39E-005 3.72E-005 2.59E-005 6.04E-006 1.55E+000
CSA Serial 3.43E-003 4.23E+000 1.03E+000 1.35E+000 1.32E+000
CSA Paralelo 2.18E-005 5.91E-004 1.16E-004 1.12E-004 2.52E+000
f3
SA 1.96E-003 3.37E-003 2.53E-003 3.34E-004 2.11E+000
CSA Serial 1.05E-002 5.50E-002 2.51E-002 1.07E-002 1.86E+000
CSA Paralelo 2.71E-003 5.46E-003 4.35E-003 8.18E-004 2.04E+000
f4
SA 1.25E-002 1.08E-001 5.30E-002 2.53E-002 2.39E+000
CSA Serial 4.75E-002 3.41E-001 1.29E-001 6.14E-002 2.13E+000
CSA Paralelo 4.07E-003 4.81E-002 1.96E-002 1.16E-002 2.57E+000
f5
SA 2.60E-002 3.69E-002 3.17E-002 2.82E-003 7.61E+001
CSA Serial 1.11E-001 4.89E-001 1.81E-001 7.81E-002 7.60E+001
CSA Paralelo 3.95E-002 6.35E-002 5.40E-002 7.27E-003 3.42E+000
f6
SA 2.73E-005 5.58E-005 3.98E-005 7.66E-006 2.01E+000
CSA Serial 6.95E-004 9.97E-001 1.29E-001 3.01E-001 1.80E+000
CSA Paralelo 5.14E-005 2.51E-004 1.43E-004 5.31E-005 2.34E+000
f7
SA 2.20E-005 5.55E-005 3.83E-005 9.77E-006 2.02E+000
CSA Serial 7.03E-004 3.75E-002 7.18E-003 1.04E-002 1.83E+000
CSA Paralelo 4.57E-005 2.16E-004 1.34E-004 4.05E-005 2.37E+000
f8
SA 1.71E-001 2.37E+002 3.97E+001 6.69E+001 2.36E+000
CSA Serial 4.74E+002 1.70E+003 9.89E+002 3.56E+002 2.12E+000
CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 53
CSA Paralelo 1.19E+002 5.92E+002 2.36E+002 1.23E+002 2.30E+000
f9
SA 3.98E-001 4.12E-001 4.05E-001 5.67E-003 1.59E+000
CSA Serial 3.98E-001 4.14E-001 4.07E-001 6.90E-003 1.35E+000
CSA Paralelo 3.89E-001 4.12E-001 4.04E-001 1.04E-002 1.93E+000
f10
SA 3.00E+000 8.40E+001 3.34E+001 3.22E+001 1.53E+000
CSA Serial 3.00E+000 3.08E+001 1.95E+001 1.32E+001 1.31E+000
CSA Paralelo 3.00E+000 3.05E+001 1.93E+001 1.29E+001 2.00E+000
f11
SA 1.62E-011 1.46E-001 7.89E-002 7.41E-002 1.64E+000
CSA Serial 1.71E-009 7.50E-006 3.83E-007 1.49E-006 1.39E+000
CSA Paralelo 1.25E-011 9.41E-010 2.37E-010 2.79E-010 1.84E+000
f12
SA 3.16E-006 8.58E-006 6.23E-006 1.42E-006 2.16E+000
CSA Serial 2.18E-006 8.49E-006 4.71E-006 1.67E-006 1.94E+000
CSA Paralelo 2.38E-007 9.02E-007 5.55E-007 2.02E-007 2.54E+000
f13
SA 4.14E-018 3.81E-013 4.33E-014 7.95E-014 1.55E+000
CSA Serial 5.78E-013 3.19E-010 3.65E-011 6.44E-011 1.31E+000
CSA Paralelo 1.65E-016 5.83E-013 5.88E-014 1.20E-013 1.92E+000
f14
SA 7.23E-010 2.09E-008 8.71E-009 5.84E-009 1.61E+000
CSA Serial 3.19E-010 4.08E-009 1.47E-009 8.78E-010 1.38E+000
CSA Paralelo 1.82E-012 1.07E-010 3.91E-011 3.09E-011 1.81E+000
Fonte: Dados dos experimentos, 2013.
As soluções encontrados na Tabela 5.3 são boas e se aproximam do ótimo. O CSA para-
lelo obteve soluções melhores ou próximo as que o CSA serial em todas as funções analisadas.
No CSA serial os otimizadores são executados um a um, sequencialmente, e somente o último
realiza a operação de atualização de temperatura (encontrada em Atualizar Temperaturas na
Figura 4.2), i.e., todos os 24 otimizadores tem maior probabilidade de realizar ou refinamento
ou exploração ao mesmo tempo (a cada ciclo de 24 avaliações da função custo). Já no CSA
paralelo, o refinamento e exploração pode ocorrer no meio de um desses ciclos, afinal, a qual-
quer momento um otimizador pode adentrar a região critica e alterar a temperatura. Ou seja,
parte dos otimizadores realizam refinamento e parte realizam exploração. Ainda mais, como a
alternância entre refinamento e exploração não é feita em momentos exatos, espera-se que os
otimizadores do CSA paralelo se distribuam melhor no espaço de busca, o que acarreta me-
lhores soluções finais. Este mesmo motivo explica os pequenos desvios padrões das soluções
encontradas, chegando em 10−11 no serial, e 10−13 no paralelo.
Entretanto, nem todos os resultados do CSA paralelo foram melhores que do Simulated
Annealing. Como o CSA possui muitos otimizadores e o número de iterações do algoritmo é
CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 54
fixo, cada otimizador realiza poucas iterações, pois estas serão divididas pelos otimizadores.
Isso pode dificultar a busca de soluções melhores porque os otimizadores podem não realizar
iterações suficientes para uma bom refinamento e exploração.
O tempo médio de execução do CSA paralelo para a maioria das funções foi maior que o
do SA e CSA serial. A inserção da região crítica no CSA paralelo cria overheads no algoritmo.
Quanto maior a quantidade de otimizadores, maior será o tempo desperdiçado em overhead.
Ademais, a baixa dimensão das funções implica em uma menor carga computacional a ser
processada. Como as funções são avaliadas individualmente por cada otimizador, isto é, na
região paralela do código, o CSA paralelo não obtêm um melhor desempenho por não possuir
uma carga de trabalho elevada. A exceção ocorre com a função f5. Ela possui um elevado custo
computacional de processamento, e, devido a isso, o CSA paralelo possui um melhor tempo
médio de processamento.
A Tabela 5.4 descreve os resultados obtidos das 25 execuções do SA e CSA com 24 otimi-
zadores e 160 dimensões. De maneira geral, as soluções foram boas e estão próximas do ótimo
global. Assim como no caso anterior, a qualidade da solução final do CSA paralelo é melhor
que os resultados obtidos pela versão serial, mas, em alguns casos, pior que do Simulated Anne-
aling. Quando comparado às soluções encontradas com 10 dimensões, os resultados são piores.
Entretanto, como a dimensão é 16 vezes maior, o tamanho do problema e a sua complexidade
tendem a aumentar e dificultam, na maioria dos casos, a busca das boas soluções. Apesar disso,
o tempo médio de solução do CSA paralelo para a 160 dimensões foi inferior em todos os casos.
Tabela 5.4 – Qualidade de solução do Simulated Annealing (SA), do Coupled Simulated Annealing
(CSA) serial e paralelo para D = 160, 25 execuções. O CSA é executado com 24 oti-
mizadores. Das 25 execuções, resgata-se a melhor solução, a pior solução, bem como
calcula-se a média, o desvio padrão e o tempo médio de execução dos algoritmos.
Função Algoritmo Melhor Pior Média das Desvio Tempo
Solução Solução Soluções Padrão Médio
f1
SA 3.38E-004 4.17E-004 3.86E-004 1.87E-005 2.24E+001
CSA Serial 3.85E-002 5.48E-001 2.46E-001 1.56E-001 2.17E+001
CSA Paralelo 2.38E-004 2.28E-001 5.34E-002 5.93E-002 4.15E+000
f2
SA 6.52E+001 1.33E+002 1.16E+002 1.38E+001 2.27E+001
CSA Serial 1.57E+002 1.61E+002 1.59E+002 1.49E+000 2.20E+001
CSA Paralelo 1.55E+002 1.59E+002 1.57E+002 8.85E-001 4.17E+000
f3
SA 6.72E-003 7.71E-003 7.15E-003 2.36E-004 3.04E+001
CSA Serial 6.93E-001 1.99E+000 1.35E+000 3.88E-001 3.03E+001
CSA Paralelo 1.63E-002 2.61E-001 5.53E-002 6.60E-002 4.02E+000
f4
SA 1.47E-003 8.70E-001 2.13E-001 2.15E-001 3.32E+001
CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 55
CSA Serial 9.42E-001 1.51E+000 1.26E+000 1.20E-001 3.25E+001
CSA Paralelo 1.12E-002 1.14E+000 6.55E-001 2.92E-001 4.13E+000
f5
SA 1.20E+000 3.77E+000 1.52E+000 5.77E-001 1.12e+003
CSA Serial 1.19E+001 1.75E+001 1.49E+001 1.37E+000 1.12E+003
CSA Paralelo 2.45E+000 5.52E+000 4.02E+000 7.89E-001 4.73E+001
f6
SA 1.10E+001 4.08E+001 2.32E+001 6.89E+000 3.18E+001
CSA Serial 5.51E+000 2.46E+001 1.45E+001 5.83E+000 2.92E+001
CSA Paralelo 2.14E-002 9.86E+000 3.81E+000 2.37E+000 4.12E+000
f7
SA 1.40E+001 3.00E+001 2.12E+001 4.50E+000 3.22E+001
CSA Serial 2.07E+000 2.22E+001 1.28E+001 5.45E+000 2.94E+001
CSA Paralelo 5.11E-001 6.75E+000 3.04E+000 1.77E+000 4.03E+000
f8
SA 6.58E+003 1.00E+004 7.99E+003 9.62E+002 3.61E+001
CSA Serial 4.18E+004 4.86E+004 4.61E+004 1.59E+003 3.50E+001
CSA Paralelo 3.94E+004 4.59E+004 4.25E+004 1.88E+003 4.02E+000
f9
SA 3.98E-001 2.71E+000 4.94E-001 4.71E-001 2.23E+001
CSA Serial 4.01E-001 5.01E-001 4.58E-001 4.34E-002 2.14E+001
CSA Paralelo 3.82E-001 4.97E-001 4.52E-001 5.07E-002 4.02E+000
f10
SA 3.00E+000 8.40E+001 3.11E+001 3.03E+001 2.22E+001
CSA Serial 3.00E+000 3.00E+001 2.68E+001 8.95E+000 2.13E+001
CSA Paralelo 3.00E+000 8.30E+001 1.08E+001 1.83E+001 4.14E+000
f11
SA 5.86E-013 1.46E-001 5.46E-002 7.20E-002 2.23E+001
CSA Serial 2.04E-011 4.79E-009 5.13E-010 1.18E-009 2.14E+001
CSA Paralelo 9.63E-014 1.43E-011 3.01E-012 3.59E-012 4.00E+000
f12
SA 3.35E-004 4.15E-004 3.78E-004 1.75E-005 3.37E+001
CSA Serial 3.89E-002 5.27E-001 3.09E-001 1.44E-001 3.30E+001
CSA Paralelo 2.02E-004 2.29E-001 4.83E-002 5.68E-002 4.14E+000
f13
SA 8.69E-019 1.94E-015 2.67E-016 5.12E-016 2.22E+001
CSA Serial 1.89E-016 2.33E-011 1.31E-012 4.64E-012 2.14E+001
CSA Paralelo 1.66E-018 1.11E-014 1.02E-015 2.36E-015 3.97E+000
f14
SA 2.83E-011 2.33E-009 9.22E-010 6.00E-010 2.24E+001
CSA Serial 2.58E-013 5.32E-011 1.95E-011 1.28E-011 2.14E+001
CSA Paralelo 6.03E-014 6.73E-012 1.54E-012 1.61E-012 4.20E+000
Fonte: Dados dos experimentos, 2013.
Para mostrar os demais resultados, os gráficos a seguir exibem a média das soluções de 25
CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 56
execuções das versões serial e paralela do CSA com 24 otimizadores. Serão exibidas as médias
para as dimensões 10, 20, 40, 80 e 160. Os gráficos são dividos em três grupos, conforme se
caracteriza as funções de referência encontradas na Seção 5.1. Cada função tem exibida a sua
média para o CSA serial e paralelo.
Figura 5.4 – Média das soluções do grupo 1 de funções de referência utilizando o CSA com 24
otimizadores.
0 20 40 60 80 100 120 140 160
-8
-6
-4
-2
0
2
4
Lo
g 1
0
(M
éd
ia
)
Dimensão
f1 serialf1 paralelof2 serialf2 paralelo
Fonte: Dados dos experimentos, 2013.
A Figura 5.4 exibe em escala logarítmica o valor médio das soluções das funções do grupo
1 para 25 execuções da versão serial do Simulated Annealing Acoplado com 24 otimizadores,
sendo aplicada a versão serial e paralela. Como as duas funções desse grupo são ditas fáceis de
otimizar, espera-se boa média das soluções encontradas mesmo com a maiores dimensões do
problema. A média de soluções da versão paralela são melhores ou parecidas com as soluções
da versão serial.
Figura 5.5 – Média das soluções do grupo 2 de funções de referência utilizando o CSA com 24
otimizadores.
(a) Funções f3, f4 e f5
0 20 40 60 80 100 120 140 160
-6
-4
-2
0
2
4
6
Lo
g 1
0
(M
éd
ia
)
Dimensão
f3 serialf3 paralelof4 serialf4 paralelof5 serialf5 paralelo
(b) Funções f6, f7 e f8
0 20 40 60 80 100 120 140 160
-6
-4
-2
0
2
4
6
Lo
g 1
0
(M
éd
ia
)
Dimensão
f6 serialf6 paralelof7 serialf7 paralelof8 serialf8 paralelo
Fonte: Dados dos experimentos, 2013.
CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 57
A análise do grupo 2 utilizando o CSA paralelo, exibido nas Figuras 5.5(a) e 5.5(b), mostra
o crescimento da média das soluções para a maioria das funções. Entretanto, apesar deste
crescimento, as médias das soluções do CSA paralelo foram melhores que a versão serial.
Para o último caso, as Figuras 5.6(a) e 5.6(b) mostram os resultados dos experimentos para o
grupo 3 de funções de referência. Como esperado, a versão paralela obteve melhores soluções.
Figura 5.6 – Média das soluções do grupo 3 de funções de referência utilizando o CSA com 24
otimizadores.
(a) Funções f9, f10 e f11
0 20 40 60 80 100 120 140 160
-20
-15
-10
-5
0
5
Lo
g 1
0
(M
éd
ia
)
Dimensão
f9 serialf9 paralelof10 serialf10 paralelof11 serialf11 paralelo
(b) Funções f12, f13 e f14
0 20 40 60 80 100 120 140 160
-20
-15
-10
-5
0
5
Lo
g 1
0
(M
éd
ia
)
Dimensão
f12 serialf12 paralelof13 serialf13 paralelof14 serialf14 paralelo
Fonte: Dados dos experimentos, 2013.
5.4 Speedup e Eficiência
Para testar a eficiência e o speedup, o Simulated Annealing Acoplado foi executado em 4, 8,
12, 16, 20 e 24 núcleos de processamento, cada um correspondendo a um otimizador SA. Para
cada caso, 25 repetições são completadas e os tempos decorridos são contabilizados. Utilizam-
se 1.000.000 avaliações da função custo como critério de parada e as 14 funções comentadas
na Seção 5.1. O tempo médio de execução do algoritmo serial e paralelo, e o speedup do CSA
para a função custo de 160 dimensões são dados na Tabela 5.5.
Tabela 5.5 – Tempo médio de execução serial (TS), tempo médio de execução paralela (TP) e
speedup (SU) do algoritmo CSA para 160 dimensões.
Coupled Simulated Annealing
#Otimizadores 4 8 12
Função TS TP SU TS TP SU TS TP SU
f1 22.0105 6.6609 3.3044 21.8267 5.0865 4.2911 21.7640 4.5696 4.7628
f2 22.3270 6.7347 3.3152 22.1082 5.1336 4.3066 22.028 4.6843 4.7026
f3 33.9321 8.6030 3.9442 32.8198 5.4792 5.9899 31.9633 4.7021 6.7977
f4 36.4494 9.3451 3.9004 34.2087 5.6939 6.0080 33.3743 4.9694 6.7159
f5 1129.0 279.5345 4.0390 1126.4 140.8097 7.9997 1124.1 94.1583 11.9382
CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 58
f6 32.8796 8.5804 3.8320 31.2673 5.4329 5.7552 30.1474 4.8391 6.2300
f7 33.4877 8.6596 3.8671 31.6215 5.4444 5.8081 30.5270 4.8706 6.2676
f8 36.4247 9.7475 3.7368 35.6351 5.8777 6.0628 35.3728 4.9803 7.1025
f9 21.8575 6.6032 3.3101 21.5671 5.1104 4.2202 21.5502 4.5624 4.7234
f10 21.7789 6.5363 3.3320 21.5585 4.9942 4.3167 21.4457 4.5560 4.7071
f11 21.9259 6.5952 3.3245 21.6488 5.0932 4.2505 21.5398 4.5775 4.7056
f12 34.0484 9.2339 3.6873 33.3541 5.6876 5.8644 33.1871 4.9258 6.7374
f13 21.7826 6.5734 3.3137 21.4903 5.0547 4.2516 21.4780 4.4577 4.8182
f14 21.8786 6.6053 3.3123 21.6536 5.0368 4.2991 21.5382 4.5722 4.7107
#Otimizadores 16 20 24
Função TS TP SU TS TP SU TS TP SU
f1 21.7235 4.0707 5.3365 21.6870 3.9152 5.5393 21.6810 4.1505 5.2238
f2 22.0459 4.2007 5.2482 21.9749 4.0382 5.4417 21.9550 4.1681 5.2674
f3 31.4060 4.5081 6.9665 30.9802 4.3209 7.1699 30.2875 4.0194 7.5353
f4 33.0400 4.5065 7.3316 32.7176 4.3506 7.5203 32.5305 4.1313 7.8742
f5 1128.5 70.7337 15.9539 1117.4 56.7619 19.6852 1123.0 47.3497 23.7171
f6 29.7370 4.4865 6.6281 29.2803 4.3373 6.7508 29.1710 4.1156 7.0880
f7 29.9522 4.5289 6.6136 29.5680 4.2512 6.9553 29.3617 4.0300 7.2858
f8 35.2265 4.6048 7.6500 35.1166 4.4104 7.9623 34.9923 4.0187 8.7074
f9 21.5185 4.0101 5.3661 21.4468 3.8796 5.5281 21.4235 4.0213 5.3275
f10 21.4341 4.0256 5.3245 21.3972 4.0440 5.2911 21.3482 4.1417 5.1545
f11 21.5135 4.0330 5.3343 21.4430 3.9075 5.4876 21.4257 3.9987 5.3581
f12 33.1496 4.5590 7.2713 33.0658 4.2606 7.7609 33.0246 4.1362 7.9842
f13 21.4327 4.0627 5.2755 21.3905 3.9788 5.3761 21.3668 3.9739 5.3767
f14 21.5431 4.0241 5.3535 21.4717 3.9167 5.4821 21.4462 4.2048 5.1004
Fonte: Dados dos experimentos, 2013.
Para confirmar a boa escalabilidade do algoritmo, deve haver um crescimento da efici-
ência quando o tamanho do problema aumenta, conforme Alg. B na Figura 3.5. Para essa
análise, o número de otimizadores é fixado e a dimensão do problema é variado em D =
[10,20,40,80,160]. Cada otimizador foi executado em um único processador. Para simplificar
o demonstrativo dos resultados, somente os resultados para 4, 8, 16 e 24 núcleos são exibidos.
Para cada um desses, são expostos os gráficos para os grupos 1, 2 e 3 das funções de referência.
Para a análise do tempo, Lin e Snyder (2009) comentam que muitos pesquisadores relatam
que é bom utilizar tempo médio de execução se a configuração de execução normal do programa
é em um sistema multiusuário, entretanto a mediana é provavelmente um melhor valor porque
ignora os efeitos de algumas péssimas execuções, onde outros processos tomam processamento
suficiente para que a medição do tempo de execução não seja puramente do algoritmo em aná-
lise. O menor tempo de execução tambem é importante, uma vez que indica o desempenho que
o processo pode alcançar nas melhores condições. Como a plataforma de testes é multiusuário,
utilizou-se a mediana para os cálculos da eficiência. Os resultados estão a seguir.
CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 59
5.4.1 Análise de escalabilidade para o grupo 1 de funções de referência
A Figura 5.7 exibe os valores da eficiência paralela para o grupo 1 de funções de referência
ao utilizar 4, 8, 16 e 24 otimizadores. Há uma tendência do aumento da eficiência com o
crescimento da dimensão do problema. Essa característica mostra que o CSA se comporta de
forma escalável para o grupo 1 de funções de referência.
Figura 5.7 – Eficiência vs Dimensão para o grupo 1 de funções de referência.
(a) 4 otimizadores
0 20 40 60 80 100 120 140 160
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Efi
ci
ên
ci
a
Dimensão
f1f2
(b) 8 Otimizadores
0 20 40 60 80 100 120 140 160
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Efi
ci
ên
ci
a
Dimensão
f1f2
(c) 16 Otimizadores
0 20 40 60 80 100 120 140 160
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Efi
ci
ên
ci
a
Dimensão
f1f2
(d) 24 Otimizadores
0 20 40 60 80 100 120 140 160
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Efi
ci
ên
ci
a
Dimensão
f1f2
Fonte: Dados dos experimentos, 2013.
Percebe-se também que, para uma dada dimensão, aumentar o número de otimizadores
implica na redução da eficiência. O aumento de otimizadores contribui para o crescimento da
porção serial na inicialização do algoritmo e para um maior número de otimizadores disputando
a região crítica do algoritmo, o que tem como resultado um maior tempo de espera para adentrar
tal região. Os otimizadores neste estado não realizam qualquer computação, prolongando o
tempo de processamento do algoritmo e, consequentemente, reduzindo a eficiência do CSA.
CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 60
5.4.2 Análise de escalabilidade para o grupo 2 de funções de referência
O grupo 2 se comportou com as mesmas características do grupo 1. A eficiência é sublinear
e tende a crescer. Entretanto, os ganhos foram maiores, especialmente a função f5, apesar
de sua constância. Entretanto, os ganhos foram maiores, especialmente a função f5, apesar
de sua quase constância. Devido a implementação do algoritmo, a avaliação da função de
custo é realizada na porção paralela do código. Quanto maior for o custo computacional dessa
avaliação, maior será a porção paralela. A consequência é o aumento da eficiência. A função
f5 é extremamente custosa computacionalmente e, por isso, sua eficiência é melhor que todas
as outras funções, qualquer que seja a dimensão ou o número de otimizadores.
Figura 5.8 – Eficiência vs Dimensão para o grupo 2 de funções de referência.
(a) 4 otimizadores
0 20 40 60 80 100 120 140 160
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Efi
ci
ên
ci
a
Dimensão
f3f4f5f6f7f8
(b) 8 Otimizadores
0 20 40 60 80 100 120 140 160
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Efi
ci
ên
ci
a
Dimensão
f3f4f5f6f7f8
(c) 16 Otimizadores
0 20 40 60 80 100 120 140 160
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Efi
ci
ên
ci
a
Dimensão
f3f4f5f6f7f8
(d) 24 Otimizadores
0 20 40 60 80 100 120 140 160
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Efi
ci
ên
ci
a
Dimensão
f3f4f5f6f7f8
Fonte: Dados dos experimentos, 2013.
Os resultados demonstram que o CSA tem comportamento escalável para o grupo 2 de
funções de referência. A Figura 5.8 mostra a eficiência paralela para o grupo 2 de funções de
referência ao utilizar 4, 8, 16 e 24 otimizadores.
CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 61
5.4.3 Análise de escalabilidade para o grupo 3 de funções de referência
Para o último grupo de funções de referência, o CSA também demonstra ter comportamento
escalável. A eficiência também aumenta com a dimensão do problema. A Figura 5.9 exibe a
eficiência paralela para o grupo 3 de funções de referência ao utilizar 4, 8, 16 e 24 otimizadores.
Figura 5.9 – Eficiência vs Dimensão para o grupo 3 de funções de referência.
(a) 4 otimizadores
0 20 40 60 80 100 120 140 160
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Efi
ci
ên
ci
a
Dimensão
f9f10f11f12f13f14
(b) 8 Otimizadores
0 20 40 60 80 100 120 140 160
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Efi
ci
ên
ci
a
Dimensão
f9f10f11f12f13f14
(c) 16 Otimizadores
0 20 40 60 80 100 120 140 160
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Efi
ci
ên
ci
a
Dimensão
f9f10f11f12f13f14
(d) 24 Otimizadores
0 20 40 60 80 100 120 140 160
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Efi
ci
ên
ci
a
Dimensão
f9f10f11f12f13f14
Fonte: Dados dos experimentos, 2013.
5.4.4 Análise de escalabilidade média dos grupos de funções
Analisando as eficiências do grupo 1, 2 e 3, verifica-se que além de ganhos sublineares e
tendência de crescimento da eficiência, algumas funções possuem uma elevada taxa crescimento
e outras não. Percebe-se que a eficiência do grupo 3, com excessão da função f12, se assemelha
bastante com as encontradas no grupo 1. Ou seja, a divisão do tempo de execução serial pelo
paralelo é semelhante em ambos os grupos. Isso não significa necessariamente que ambos
possuem o mesmo tempo de computação. O mesmo fato observa-se no Grupo 2 (desprezando
f5) e a função f12. A Figura 5.10 exibe tais comparações para 4, 8, 16 e 24 núcleos.
CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 62
Figura 5.10 – Média da Eficiência vs Dimensão para os grupos de funções de referência.
(a) 4 otimizadores
0 20 40 60 80 100 120 140 160
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Efi
ci
ên
ci
a
Dimensão
Grupo 1
Grupo 2 - f5
Grupo 3 - f12f12
(b) 8 Otimizadores
0 20 40 60 80 100 120 140 160
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Efi
ci
ên
ci
a
Dimensão
Grupo 1
Grupo 2 - f5
Grupo 3 - f12f12
(c) 16 Otimizadores
0 20 40 60 80 100 120 140 160
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Efi
ci
ên
ci
a
Dimensão
Grupo 1
Grupo 2 - f5
Grupo 3 - f12f12
(d) 24 Otimizadores
0 20 40 60 80 100 120 140 160
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Efi
ci
ên
ci
a
Dimensão
Grupo 1
Grupo 2 - f5
Grupo 3 - f12f12
Fonte: Dados dos experimentos, 2013.
Conclusão
A classe de métodos de otimização Simulated Annealing Acoplado (CSA) proposto vem
suprir duas necessidades da metaheurística Simulated Annealing tradicional: a carência de im-
plementação de algoritmos paralelos eficientes devido a era multicore e a necessidade de maior
robustez de algoritmos quanto aos parâmetros de inicialização. Um dos principais motivos para
o surgimento da era multicore é a dificuldade de resfriamento dos processadores devido a alta
frequência de operação, efeito conhecido como Power Wall (Muralha de Energia). Uma das
soluções para contornar o problema é utilizar diversos processadores de menor frequência de
operação para realizar a operação. Esta mudança de paradigma atualmente ainda é encarada
por muitos como um obstáculo, já que em troca do poderio computacional, os programadores
devem se preocupar com outros aspectos que não somente o algoritmo, como a hierarquia de
memória, coerência de cache e o tipo de interconexão.
O trabalho ressalta a implementação do Simulated Annealing (SA), Simulated Annealing
Acoplado (CSA) serial e paralelo. Quanto ao processo de desenvolvimento destes algoritmos,
os desafios residiram nas adequações da implementação do CSA junto às suas definições, de
maneira que não houvesse incoerência probabilística de suas variáveis e que o algoritmo pu-
desse ter o máximo possível de eficiência paralela. Para o estudo de desempenho, avaliou-se
exaustivamente um conjunto de 14 funções de referência. Elas estão separadas em 3 grupos,
sendo duas funções unimodais, seis funções multimodais e outras seis multimodais rotaciona-
das. Para cada um destas, executou-se o CSA serial e paralelo com 4, 8, 16 e 24 otimizadores
sendo aplicados à 10, 20, 40, 80 e 160 dimensões. O SA foi analisado somente quanto a quali-
dade da solução final, sendo aplicado somente às dimensões 10 e 160 para comparação com os
demais algoritmos.
Na comparação de desempenho quanto a qualidade da solução, o CSA apresentou excelentes
e promissores resultados. Neste quesito, o Simulated Annealing (SA) foi superior ao Coupled
Simulated Annealing (CSA) paralelo em alguns casos. Entretanto, nestes as soluções foram
muito próximas. Como o critério de parada do algoritmo é um número fixo de iterações, cada
otimizador do CSA realizará poucas iterações, pois serão divididas entre os otimizadores. Isto
pode dificultar a busca de melhores soluções, de modo que os otimizadores podem não realizar
iterações suficientes para um bom refinamento e exploração. Cabe ao programador pesar entre
uma melhor qualidade da solução e um menor tempo de processamento. Já quando comparado
64
ao CSA serial, o SA e o CSA paralelo obtiveram melhores resultados em todas as funções de
referência.
Na análise de escalabilidade paralela, o CSA obteve um ótimo comportamento. O pri-
meiro resultado mostra que há uma queda de eficiência, para uma mesma dimensão e problema,
quando o número de otimizadores aumenta. O fato ocorre devido à disputa da região crítica
pelos otimizadores do CSA, o que resume em comunicação entre os processos. Apesar disso,
esse comportamento é normal e esperado na maioria dos algoritmos paralelos.
O segundo visa analisar a escalabilidade do CSA. Para tal, incrementou-se o tamanho do
problema e verificou-se a eficiência. O comportamento da eficiência ocorreu de forma que
houve o seu crescimento quando a dimensão do problema aumentou. Confirmou-se também
que funções computacionalmente custosas obtêm melhores eficiências, pois sua avaliação é
realizada na porção paralela do código.
Portanto, diante das dificuldades inerentes à resolução de problemas reais complexos, pelo
sucesso das aplicações das metaheurísticas, pela necessidade de reduzir o consumo de ener-
gia, pela realidade encarada do frequente aumento do número de núcleos de processamento ao
invés de ganhos de velocidade em um único processador, e pelos resultados obtidos neste traba-
lho, o Coupled Simulated Annealing se revela como um algoritmo viável a ser aplicado na era
multicore, destacando-se , em especial, a sua ótima escalabilidade paralela.
Trabalhos Futuros
Apesar do Simulated Annealing Acoplado controlar a variância das probabilidades de acei-
tação, incorporando assim a característica parameter-less na temperatura de aceitação Tac, a
temperatura de geração T ainda não é controlada e obedece um escalonamento, reduzindo seu
valor a cada iteração do algoritmo. No intuito de robustecer o algoritmo quanto ao valor da
temperatura de geração, é proposto o desenvolvimento de um novo algoritmo. O algoritmo per-
mitirá o controle automático de T e a redução do número de variáveis inicializadas. Portanto,
eliminará o escalonamento da temperatura de geração T , mantendo o controle de variância.
Para tal, poderá ser desenvolvido um algoritmo que funcionará baseado no algoritmo CSA
da seguinte forma: agrupam-se diversos processos CSA executando em paralelo. Cada um
dos processos, chamado de repositório, possui um conjunto próprio de otimizadores Simulated
Annealing. Todos os otimizadores de cada repositório serão executados em uma temperatura
fixa. As temperaturas dos repositórios serão escalonados de forma que possuam, numa ponta,
um repositório executando em elevados níveis de temperatura de geração e, na outra ponta, um
repositório em baixa temperatura. Todos os demais repositórios possuirão temperaturas nesse
intervalo.
Durante o processo de busca, os repositórios trocarão algumas soluções para evitar uma
65
estagnação da busca das soluções em bacias atratoras. A meta é alcançar um resultado funcional
semelhante ao encontrado com o escalonamento clássico da temperatura de geração, mas com
maior robustez.
Após implementado, podem-se realizar diversos experimentos funcionais a fim de atestar
as melhores faixas de temperaturas para diversos problemas. Na sequência, avalia-se seu de-
sempenho comparando-o com outras versões de algoritmos, paralelos ou não, seja quanto ao
refinamento da solução, seja quanto à análise de escalabilidade paralela.
Referências Bibliográficas
AMDAHL, G. M. (1967), ‘Validity of the single processor approach to achieving large scale
computing capabilities’, Proc. AFIPS 1967 Spring Joint Computer Conf pp. 483–485.
United States of America, Atlantic City.
ASANOVIC, K., BODIK, R., CATANZARO, B. C., GEBIS, J. J., HUSBANDS, P., KEUTZER,
K., PATTERSON, D. A., PLISHKER, W. L., SHALF, J., WILLIAMS, S. W. ; YELICK, K.
A. (2006), The landscape of parallel computing research: A view from berkeley, Relatório
técnico, EECS Department, University of California, Berkeley.
BASTURK, A. ; AKAY, R. (2012), ‘Parallel implementation of synchronous type artificial bee
colony algorithm for global optimization’, Journal of Optimization Theory and Applicati-
ons .
BORKAR, S. (2007), ‘Thousand core chips-a technology perspective’, 44th ACM/IEEE Design
Automation Conference pp. 746–749.
EGLESE, R. W. (1990), ‘Simulated annealing: a tool for operation research’, Journal of Ope-
rational Research 46, 271–281.
FLEISCHER, M. A. (1995a), Assessing the Performance of the Simulated Annealing Algo-
rithm Using Information Theory, Tese de doutorado, Department of Operations Research,
Case Western Reserve University, Clevelend, Ohio.
FLEISCHER, M. A. (1995b), ‘Simulated annealing: past, present, and’, Proceedings of the
1995 Winter Simulation Conference pp. 155–161.
GEORGE, H. A., JIMENEZ, J. T. ; HERNÁNDEZ, V. (2012), ‘New bounds for ternary cove-
ring arrays using a parallel simulated annealing’, Mathematical Problems in Engineering
pp. 1–19.
GLOVER, F. (1986), ‘Future paths for integer programming and links to artificial intelligence’,
Computers and Operations Research 5, 533–549.
GLOVER, F. ; KOCHENBERGER, G. A. (2003), Handbook of Metaheuristics, Kluwer Aca-
demic Publishers.
66
REFERÊNCIAS BIBLIOGRÁFICAS 67
GRAMMA, A., GUPTA, A., KARYPIS, G. ; KUMAR, V. (2003), Introduction to Parallel
Computing, Addison-Wesley.
GUSTAFSON, J. L. (1988), ‘Reevaluating amdahl’s law’, Communications of the ACM
pp. 532–533.
HARIK, G. R. ; LOBO, F. G. (1999), A parameter-less genetic algorithm, em ‘GECCO-99: Pro-
ceedings of the Genetic and Evolutionary Computation Conference’, pp. 258–265. United
States of America, Orlando.
HELD, J., BAUTISTA, J. ; KOEHL, S. (2010), From a few cores to many: A tera-scale compu-
ting research overview.
HILL, M. D. ; MARTY, M. R. (2008), ‘Amdahl’s law in the multicore era’, Computer 41(7), 33–
38.
KOCH, G. (2005), Discovering multi-core: Extending the benefits of moore’s law, Relatório
técnico, Intel Corporation.
KOULAMAS, C., ANTONY, S. R. ; JAEN, R. (1994), ‘A survey of simulated annealing appli-
cations to operations-research problems’, OMEGA-International Journal of Management
Science 22, 41–56.
KURBEL, K., SCHNEIDER, B. ; SINGH, K. (1998), ‘Solving optimization problems by pa-
rallel recombinative simulated annealing on a parallel computer - an application to stan-
dard cell placement in vlsi design’, IEEE Transactions on Systems, Man, and Cybernetics
28, 454–461.
LIMA JÚNIOR, F. C. (2009), Algoritmo Q-Learning como Estratégia de Exploração e/ou Ex-
plotação para as Metaheurísticas GRASP e Algoritmo Genético, Tese de doutorado, Uni-
versidade Federal do Rio Grande do Norte, Brasil, Natal.
LIN, C. ; SNYDER, L. (2009), Principles of Parallel Programming, Pearson Addison-Wesley.
MCCREADIE, R., MACDONALD, C. ; OUNIS, I. (2012), ‘Mapreduce indexing strategies:
Studying scalability and efficiency’, Information Processing & Management 48.
METROPOLIS, N., ROSENBLUTH, A. W., ROSENBLUTH, M. N. ; TELLER, A. H. (1953),
‘Equation of state calculations by fast computing machines’, The Journal of Chemical
Physics 21(6), 1087–1092.
MOORE, G. E. (1965), ‘Cramming more components onto integrated circuits’, Electronics
Magazine 38(8).
REFERÊNCIAS BIBLIOGRÁFICAS 68
NAWROCKI, W. (2010), ‘Physical limits for scaling of integrated circuits’, Journal of Physics
Conference Series 248.
PAPADIMITRIOUS, C. ; YANNAKAKIS, M. (1988), ‘Towards an architecture-independent
analysis of parallel algorithms’, Proceedings of the twentieth annual ACM symposium on
theory of computing pp. 510–513. United States of America, New York.
PEREDO, O. ; ORTIZ, J. M. (2011), ‘Parallel implementation of simulated annealing to repro-
duce multiple-point statistics’, COMPUTERS & GEOSCIENCES 8.
ROMEO, F. ; SANGIOVANNI-VINCENTELLI, A. (1991), ‘A theoretical framework for simu-
lated annealing’, Algorithmica 6, 302–345.
SUYKENS, J. A. K., VANDEWALLE, J. ; MOOR, B. (2001), ‘Intelligence and cooperative
search by coupled local minimizers’, Int. J. Bifurcation Chaos 11(8), 2133–2144.
TALK, TECH (2012), ‘Cpu trends’. Disponível em: <http://techtalk.pcpitstop.com/research-
charts-cpu/>. Acesso em 12/12/2012.
TASOULIS, D. K., PAVLIDIS, N. G., PLAGIOANAKOS, V. P. ; VRAHATIS, M. N. (2004),
‘Parallel differential evolution’, Congress on Evolutionary Computation (CEC 2004)
pp. 2023–2029. United States of America, Portland.
TRAN, K. D. (2005), ‘Elitist non-dominated sorting ga-ii (nsga-ii) as a parameter-less multi-
objective genetic algorithm’, Proceedings of the IEEE SoutheastCon 2004: Excellence in
Engineering, Science, and technology pp. 359–367. United States of America, Broward.
XAVIER-DE-SOUZA, S., SUYKENS, J. A. K., VANDEWALLE, J. ; BOLLÉ, D. (2006), ‘Co-
operative behavior in coupled simulated annealing processes with variance control’, Int.
Symp. NOLTA 48, 879–882. Italy, Bologna.
XAVIER-DE-SOUZA, S., SUYKENS, J. A. K., VANDEWALLE, J. ; BOLLÉ, D. (2010),
‘Coupled simulated annealing’, IEEE Transactions on Systems, Man, and Cybernetics
40(2), 320–335. Belgium, Leuven.
YANG, X., DOU, Y. ; HU, Q. (2006), ‘Progress and challenges in high performance computer
technology’, J. Comput. Sci. Technol 21(5), 674–681.