Discussion

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 P Alg. A Alg. B S P S P S 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

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.

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 1aiteraçã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