ESTUDO PRELIMINAR SOBRE A ESCALABILIDADE DE UM … · Para trabalhos futuros: Serão realizados testes com as demais instâncias do benchmark Análise da escalabilidade e de possibilidades

ESTUDO PRELIMINAR SOBRE A

ESCALABILIDADE DE UM

ALGORITMO GENÉTICO

PARALELIZADO COM OPENMP

Mateus Fontoura Gomes da Rosa

Márcia C. Cera

Roteiro

Introdução

Problema de Roteamento de Veículos

Objetivos da Pesquisa

Algoritmos Genéticos

Paralelização do AG

Apresentação dos Resultados Preliminares

Considerações Finais

2

Problema de Roteamento de Veículos

Consiste de uma derivação do Problema do Caixeiro Viajante

Foi utilizado Algoritmo Genético para solucionar o problema

Fonte: Gressler (2012)

3

Objetivos da Pesquisa

Objetivo Geral:

Analisar a escalabilidade do Algoritmo Genético Paralelo conforme o número de

threads e núcleos de processamento aumenta

Objetivos Específicos:

Analisar o desempenho do AG Paralelo conforme aumenta-se o grau de paralelismo;

Analisar a escalabilidade do AG Paralelo.

4

Roteiro

Introdução


Definição

Fluxograma do Algoritmo Genético




5

Algoritmos Genéticos - Definição

Consiste de uma proposta baseada no modelo evolutivo de Darwin

Possui funções que simulam a genética, como funções de avaliação do

indivíduo, cruzamento e mutação

Essas funções podem ser facilmente adaptadas a qualquer escopo de

problema, visto que o Algoritmo Genético trata soluções parciais como

indivíduos e as melhora gradativamente a cada evolução

6


7

Gressler

(2012)


8

Gressler

(2012)

Técnicas de cruzamento:

Cruzamento 1 ponto;

Cruzamento 2 pontos;

Cruzamento uniforme;

Técnica Híbrida 1;

Técnica Híbrida 2;


9

Gressler

(2012)

Técnicas de Mutação:

Troca;

Inversão;

Inserção;

Técnica Híbrida;


10

Gressler

(2012)

Roteiro

Introdução





11


Paralelização foi feita da seguinte maneira (GRESSLER, 2012):

Foram definidas duas regiões paralelas:

Na perpetuação dos melhores indivíduos

Diretiva sections/section

Nas chamadas às funções Cruzamento e Avaliação na concepção

de uma nova geração

Diretiva parallel for

12

Roteiro

Introdução




Especificação dos Parâmetros

Verificação do Impacto das Políticas de Escalonamento de Iterações

Análise Preliminar da Escalabilidade do Algoritmo Genético Paralelo

Comparação entre os Resultados Obtidos nas Arquiteturas


13

Especificação dos Parâmetros

Foram testadas instâncias do Benchmark de Christofides

c50 – instância com 50 cidades

c100 – instância com 100 cidades

Parâmetros utilizados nos testes (GRESSLER, 2012):

Tamanho da população: N x 10;

Número de Evoluções: N x N x 10;

Técnica de cruzamento: 1 ponto;

Taxa de mutação: variação entre 4 a 10%;

Técnica de mutação: randômica;

14

Especificação dos Parâmetros - i7

Possui um processador Intel® Core™ i7-3517U 1.90GHz com dois núcleos

físicos e dois lógicos;

Para cada configuração foi executado 30 repetições;

Parâmetros do teste:

Número de threads: de 2 a 8;

Valores da política de escalonamento de iterações: Static

15

Especificação dos Parâmetros - Xeon

Possui dois processadores Intel® Xeon E5-2650 com frequência de 2.80 GHz,

cada um com 8 núcleos físicos e Hyper-threading;

A coleta foi repetida 30 vezes para cada configuração;

Parâmetros dos testes:

Número de threads: 2, 4, 8, 16, 32 e 64;

Valor da política de escalonamento de iterações: Static;

16

Xeon: c50 - Análise preliminar da

escalabilidade do Algoritmo Genético

17

5,3

4,4

3,22,6

3,13,7

13,6

0 1 2 4 8 16 32 64

0,0

2,0

4,0

6,0

8,0

10,0

12,0

14,0

16,0

Número de Threads

Te

mp

o (

s)

1,6



18

5,3

4,4

3,22,6

3,13,7

13,6

0 1 2 4 8 16 32 64

0,0

2,0

4,0

6,0

8,0

10,0

12,0

14,0

16,0

Número de Threads

Te

mp

o (

s)

1,2

1,62,0

1,6 1,4

0,3



19

320

231

152

125 121 126

349

1 2 4 8 16 32 64

0

50

100

150

200

250

300

350

400

Número de Threads

Tem

po

(s)



20

320

231

152

125 121 126

349

1 2 4 8 16 32 64

0

50

100

150

200

250

300

350

400

Número de Threads

Tem

po

(s)

1,3

2,1

2,5 2,6 2,5

0,9

Comparação entre os Resultados Obtidos

nas Arquiteturas

c50:

21

1,431,45

0,55

1,21

1,63

2,04

1,69

1,42

0,38

2 4 8 16 32 64

0,00

0,50

1,00

1,50

2,00

2,50

Número de Threads

Spe

ed

up

i7 Xeon

Comparação entre os Resultados Obtidos

nas Arquiteturas

c100:

22

1,56 1,71

0,93

1,39

2,11

2,562,64

2,54

0,92

2 4 8 16 32 64

0

0,5

1

1,5

2

2,5

3

Número de Threads

Spe

ed

up

i7 Xeon

Roteiro

Introdução



Apresentação dos Resultados Obtidos


Conclusões e Trabalhos Futuros

Cronograma de Atividades

Publicações Aceitas Durante a Elaboração do Trabalho

23

Conclusões e Trabalhos Futuros

Foi observado um aumento no desempenho quando o AG foi executado

numa arquitetura mais robusta;

Da mesma forma, é possível ver a influência do overhead de

paralelização nas execuções;

Para trabalhos futuros:

Serão realizados testes com as demais instâncias do benchmark

Análise da escalabilidade e de possibilidades de melhoria do desempenho

24

Referências

CHAPMAN B; JOST B; VAN DER PASS R; Using OpenMP. Cambridge, MA, Estados

Unidos: Massachusetts Institute of Technology, 2008.

ROSA. M. F. G. ; CERA, Márcia C. Análise do desempenho do Algoritmo

Genético paralelizado com OpenMP. Anais do XXVI Congresso Regional de

Iniciação Científica e Tecnologica em Engenharia, 2014, Alegrete - RS. p. 1-4.

LINDEN, R. Algoritmos Genéticos. Rio de Janeiro, RJ, Brasil: Ciência Moderna,

3ª Edição, 2012. Citado 4 vezes nas páginas 17, 20 e 27.

GRESSLER, H. O. ; CERA, Márcia C. O Impacto da paralelização com OpenMP

no desempenho e na qualidade das soluções de um algoritmo genético.

Revista Brasileira de Computação Aplicada, Passo Fundo, v. 6, n. 2, p. 35-47,

2014.

25

Muito obrigado pela

atenção!

Perguntas?

Mateus Fontoura Gomes da Rosa, Márcia Cristina Cera

[email protected], [email protected]

mailto:[email protected]

Documents

ESTUDO PRELIMINAR SOBRE A ESCALABILIDADE DE UM … · Para trabalhos futuros: Serão realizados testes com as demais instâncias do benchmark Análise da escalabilidade e de possibilidades