AVALIAÇÃO DO DESEMPENHO DE OPERAÇÕES COLETIVAS EM MEMÓRIA DISTRIBUÍDA E COMPARTILHADA PARA IMPLEMENTAÇÕES DE MPI

AVALIAÇÃO DO DESEMPENHO DE OPERAÇÕES COLETIVAS EM MEMÓRIA DISTRIBUÍDA E COMPARTILHADA PARA IMPLEMENTAÇÕES DE MPI Lucas P. Queiroz1, Francisco H. de Carvalho-Junior (orientador) Departamento de Computação Universidade Federal do Ceará (UFC) – Fortaleza, CE – Brazil {lucas, heron}@lia.ufc.br Resumo A eficiência de comunicações coletivas e o suporte ao multiprocessamento são dois fatores atualmente determinantes do desempenho de bibliotecas de passagem de mensagens do padrão MPI. Este artigo apresenta uma avaliação de desempenho de duas destas implementações, MPICH e Open MPI, com relação aos fatores mencionados.

1. Introdução No projeto de sistemas computacionais, a avaliação de desempenho é crucial para que sejam tomadas decisões de projeto e/ou implementação necessárias para a sua melhoria [13]. Em geral, não é uma tarefa muito simples e requer alguns cuidados metodológicos. A avaliação de desempenho de programas paralelos voltados à computação de alto desempenho [1] é uma atividade ainda mais complexa. Constitui um desafio devido à diversidade e complexidade de sistemas de computação de alto desempenho contemporâneos. Freqüentemente, é usada de maneira inadequada, podendo a induzir conclusões errôneas. O MPI (Message Passing Interface) é uma biblioteca de passagem de mensagens padrão, consistindo de um conjunto de subrotinas para o suporte em uma linguagem de programação ao mecanismo de sincronização por passagem de mensagens entre um conjunto de processos alocados a processadores de uma arquitetura distribuída [2]. É adequado à construção de programas paralelos sobre clusters e MPP’s (Massive Parallel Processors) visando aplicações de processa-mento de alto desempenho. Duas implementações importantes do padrão MPI são MPICH [3] e Open MPI [4]. Os mo1

Bolsista PIBIC/CNPq.

dos de comunicação suportados por MPI podem ser ponto-a-ponto (entre dois processadores); entre um processador e todos os demais, como disseminação (Um-para-Todos) e recolhimento (Todos-para-Um); e entre todos os processadores, como transposição (Todos-para-Todos). Neste trabalho, pressupõe-se o custo de comunicação e sincronização entre processos em operações coletivas e o suporte ao multiprocessamento, em especial devido à proliferação de processadores de múltiplos núcleos, como fatores hoje determinantes para a eficiência de implementações do padrão MPI. Assim, serão avaliados e comparados o desempenho de duas destas implementações, descritas a seguir, com relação aos aspectos mencionados. Open MPI é produzido por um consórcio de vários grupos que implementam padrões MPI (FT-MPI, LAMPI, LAM/MPI, e PACX-MPI), reunidos de maneira a agregar suas tecnologias e recursos visando criar a melhor implementação do padrão MPI. Open MPI é fundamentado sobre os conceitos de componentes [12]. Sua arquitetura de componentes fornece uma plataforma estável e permite a junção com softwares independentes (add-ons). MPICH é tanto um projeto de pesquisa quanto um projeto de software. Como um projeto de pesquisa tem como objetivo explorar métodos de estreitar a abertura entre o programador de computação paralela do desempenho do hardware. Como um projeto de software promove a adoção do padrão MPI para implementação livre, alto desempenho em diversas plataformas, enquanto ajuda vendedores no fornecimento de suas implementações customizadas. MPICH foi projetada para combinar a portabilidade com eficiência.

Na seção 2, discutiremos a metodologia empregada na análise de desempenho. Na seção 3, apresentaremos alguns resultados relevantes no comportamento do MPICH e Open MPI. Na seção 4, apresentamos algumas conclusões sobre implementações MPI.

2. Metodologia do Experimento A avaliação de desempenho [13] na programação paralela é um importante estágio que visa à análise dos computadores de alto desempenho, dos algoritmos e das aplicações paralelas bem como à localização dos gargalos limitantes do desempenho e à busca de técnicas que permitam um melhoramento das soluções. A seleção de uma técnica e uma métrica de avaliação de desempenho são duas importantes etapas em um projeto de avaliação de desempenho. Uma avaliação de desempenho baseia-se na análise de métricas de desempenho, que deve ser escolhida com base em diversos aspectos: objetivo da avaliação, características do sistema em estudo e características da carga de trabalho. Geralmente, para um dado problema existem diversas métricas que se aplicam. É importante que a métrica de desempenho reflita com fidelidade o comportamento do sistema sob a carga de trabalho imposta. As métricas de desempenho permitem formalizar os objetivos de um serviço e quantificar os resultados de uma avaliação de desempenho. Neste trabalho, será utilizado o tempo de execução como métrica, o qual inclui os tempos de computação e de comunicação, pois desejamos apenas comparar os tempos brutos de execução dos programas sobre as implementações MPI. Uma outra métrica conveniente para avaliar programas paralelos é a speedup, usada para a análise de escalabilidade. Porém, não o utilizamos tendo em vista o pequeno número de processadores disponíveis, o qual não torna possíveis conclusões confiáveis a partir desta métrica. As técnicas para a avaliação de desempenho são os métodos utilizados para obtenção de informações associadas aos parâmetros que serão usados para a análise. Podemos destacar três tipos de abordagem em se tratando de técnicas de avaliação de desempenho: medição, simulação e modelagem analítica. A abordagem de medição consiste em retirar medições simples utilizando um sistema real como fonte direta de dados ou termos à disposição ao menos um protótipo do sistema. Modelagem analítica é uma técnica que aproxima a realidade por um modelo para imitar o funcionamento de sistemas do mundo real, antecipando os efeitos produzidos por possíveis alterações. Na simulação, é simulado o comportamento de um sistema real. Em geral, é possível construir um mo-

delo muito mais próximo da realidade do que a modelagem analítica. Benchmarking, uma das técnicas de avaliação de desempenho por medição, será adotado em nossa avaliação, pois é uma técnica de aferição bastante empregada na avaliação de desempenho, principalmente, quando se deseja comparar alternativas. Benchmarking é o processo de comparação de desempenho entre dois ou mais sistemas por meio de medições e, para se efetuar tais medições, são utilizadas benchmarks. Benchmarks são programas para avaliar hardware, software ou ambos. Definem cargas de trabalho que representam as características essenciais de um domínio de aplicação. Utilizamos os benchmarks IS (Integer Sorting), pertencente ao pacote NPB (NAS Parallel Benchmarks) [Bailey1991], o qual gasta a maior parte do tempo em comunicação coletiva no padrão Todospara-Todos, recorrente em programas paralelos, e LU (fatoração LU), pertencente ao mesmo pacote, o qual gasta a maior parte do tempo em comunicação ponto-aponto, implementando um padrão de comunicação entre processadores, organizados em uma topologia mesh, conhecido como wavefront. Os fatores usados para a análise foram o número de nodos (1, 2, 4, 8, 16), implementações MPI (Open MPI e MPICH) e modelo de memória (compartilhada e distribuída). Em processamento distribuído foi analisado um processo em cada nó. Para avaliar eficiência na presença de multiprocessamento, foram analisados os casos onde há dois processos em cada nó (X2) e quatro processos em cada nó (X4). O tempo total de processamento de 30 amostras para cada caso foi tomado, escolhendo-se a mediana como valor representativo. Para o caso do IS, foram tomados separadamente os tempos de computação e sincronização/comunicação. A arquitetura empregada é um Infocluster® composto por 28 nós, cada qual com dois processadores Xeon de tecnologia hyper-threading e 1GB de memória RAM.

3. Resultados A escolha de um algoritmo ótimo de comunicação coletiva varia de acordo com a topologia da rede, número de processos na operação, tamanho da mensagem que se deseja transferir e outros fatores. Podendo usar várias maneiras de disseminar os dados como, por exemplo, estrutura de árvores e ramificações usando pipelining de dados dependendo do tamanho da mensagem [6]. Há muitos modelos paralelos de comunicação que predizem o desempenho de toda a operação coletiva dada baseada em parâmetros padronizados do sistema. PRAM [8], BSP [9], LogP e suas variantes

letiva, as quais tem sido frequentemente utilizadas na construção de aplicações paralelas em alternativa a seqüências de operações ponto-a-ponto correspondentes, como uma forma de tornar mais estruturado programas paralelos [11]. NPB-LU, classeA - Multiprocessamento-X2 350 Tempo de execução (segundos)

[10] são exemplos de modelos usados freqüentemente para analisar o desempenho de algoritmos paralelos. Avaliar os parâmetros para estes modelos em uma rede é relativamente direto e os métodos para aproximá-los têm sido estabelecidos e já são bem compreendidos. Contudo, existe o tempo para encontrar uma solução semi-ótima de operação coletiva que realiza um extensivo conjunto de testes sobre um espaço de parâmetros fazendo decisões em tempo de execução para selecionar um algoritmo próximo de ótimo e um tamanho de segmento para uma dada operação, comunicador, topologia da rede e diversos outras fatores que influenciam nessa escolha. Open MPI é baseado em uma arquitetura de componentes [7], inclui o framework de componentes para algoritmos coletivos de MPI chamado de “COLL”, back-end de operações coletivas que fornece ferramentas para pesquisadores facilmente projetar, implementar e experimentar novos algoritmos coletivos. As rotinas coletivas são implementadas em componentes autônomos que são reconhecidas pela implementação MPI em tempo de execução. Um módulo do COLL é atribuído para cada comunicador e este módulo é usado para executar todas as operações coletivas que são invocadas por esse comunicador. MPICH usa um conjunto de ponteiros de função em comunicadores para efetuar algum grau de modularidade, mas não tem nenhuma seleção automática ou mecanismo de atribuição, conseqüentemente requerendo violações de abstrações ou modificação manual da implementação.

300 250 200

Open MPI

150

MPICH

100 50 0 2

4

8

16

32

Processos

Figura 2. Medição do LU em modo multiprocessado. X2 significa 2 processos em cada nó.

No caso do IS, Open MPI apresentou melhora a medida que aumentamos o número de processadores em modo distribuído (ver Figura 4). Notamos também que o MPICH melhora quando aumentamos o multiprocessamento, enquanto o Open MPI degrada. Veja que na Figura 4 o Open MPI se comporta melhor do que o MPICH, já na Figura 5 as duas implementações se aproximam e quando vimos a Figura 6 o MPICH ultrapassa o Open MPI. Portanto, evidencia-se que, embora o Open MPI seja mais eficiente no tratamento de operações coletivas, o MPICH é capaz de suplantálo na presença de vários núcleos de processamento em um mesmo nó.

NPB-LU, classeA - Distribuído-X1

NPB-LU, classeA - Multiprocessamento-X4

400 300

Open MPI

200

MPICH

100 0 1

2

4

8

16

Processos

Tempo de execução (segundos)

Tempo de execução (segundos)

500

350 300 250 200

Open MPI

150 100

MPICH

50 0 4

8

Figura 1. Medição do LU em modo distribuído.

Na realização dos testes, a diferença dos tempos totais se dá pelo tempo de comunicação coletiva, pois os tempos de computação são praticamente iguais conforme pode ser visto nos gráficos mostrados. No caso do LU, observou-se a estabilidade do desempenho em comunicação ponto-a-ponto nas duas implementações MPI, como era esperado. Isso demonstra que a diferença de desempenho entre implementações MPI se dá na implementação das operações de comunicação co-

16

32

Processos

Figura 3. Medição do LU em modo multiprocessado. X4 significa 4 processos em cada nó.

4. CONCLUSÃO Uma implementação de MPI inclui algoritmos múltiplos para as operações coletivas de MPI e fornece um mecanismo de seleção escolhendo, em tempo de execução, quais rotinas a se utilizar.

NPB-IS, classe B - Distribuído-X1 Tempo em segundos 35

MPICH computação

30

MPICH comunicação

25 20

MPICH - total

15 10

Open MPI computação

5 0 1

2

4

8

16

Open MPI comunicação Open MPI - total

Processos

Figura 4. Medição do IS em modo distribuído. NPB-IS, classe B - Multiprocessamento-X2 Tempo em segundos 25

MPICH computação

20

MPICH comunicação

15

MPICH - total

10 Open MPI computação

5 0 2

4

8

16

32

Open MPI comunicação Open MPI - total

Processos

Figura 5. Medição do IS em modo multiprocessado (X2) . NPB-IS, classe B - Multiprocessamento-X4 Tempo em segundos 25

MPICH computação

20

MPICH comunicação

15

MPICH - total

10 Open MPI computação

5 0 4

8

16

Processos

32

Open MPI comunicação Open MPI - total

Figura 6. Medição do IS em modo multiprocessado (X4).

Evidenciamos a importância do rigor metodológico em avaliação de desempenho de sistemas paralelos, que nos levou a conclusões úteis a cerca da relevância de avaliar-se o desempenho de implementações de MPI com relação ao desempenho de operações coletivas e ao suporte ao multiprocessamento, ao escolher-se entre várias destas implementações, ao invés de restringir-se a análise do desempenho de comunicação ponto-aponto, como freqüentemente se faz. Operações coletivas e multiprocessamento têm sido freqüentemente abordadas na construção de aplicações de alto desempenho, tendo em vista, respectivamente, a maior estruturação do código e o melhor aproveitamento do desempenho de processadores de múltiplos núcleos. Isso foi evidenciado pela diferença de desempenho de comunicação coletiva, no caso do IS, em favor do Open MPI; pela estabilidade do desempenho em comunica-

ção ponto-a-ponto, com relação ao LU; e pela maior degradação do desempenho do Open MPI em modo multiprocessado, em relação ao MPICH, chegando este a compensar seu fraco desempenho, comparado ao Open MPI, em operações coletivas.

5. Agradecimentos Os autores são gratos ao Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) e a Universidade Federal do Ceará pelo apoio concedido.

6. Referências [1] Dongarra, J. – Foster, I. – Fox, G. – Gropp, W. – Kennedy, K. – Torczon, L. (2003), A. Sourcebook of Parallel Computing. Morgan Kauffman Publishers. [2] MPI-FORUM. (1994) MPI: A Message-Passing Interface Standard. International Journal of Supercomputer Applications and High Performance Computing. [3] Gropp, W., Lusk, E., Doss, N., and Skjellum, A. A HighPerformance, Portable Implementation of the MPI Message Passing Interface Standard. Parallel Computing 22, 6 (1996), 789-828. [4] Graham, R. L., Shipman, G. M., Barrett, B. W., Castain, R. H., Bosilca, G., and Lumsdaine, A. Open MPI: A high-performance, heterogeneous MPI. In Proceedings, Fifth International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks (Barcelona, Spain, September 2006). [5] Bailey, D. H., and et al. The NAS Parallel Benchmarks. International Journal of Supercomputing Applications 5, 3 (1991), 63-73. [6] Squyres, J. M., Barrett, B., and Lumsdaine, A. MPI collective operations system services interface (SSI) modules for LAM/MPI. Technical Report TR577, Indiana University, Computer Science Department, 2003. [7] Squyres, J. M., and Lumsdaine, A. The component architecture of open MPI: Enabling third-party collective algorithms. In Proceedings of 18th ACM International Conference on Supercomputing, Workshop on Component Models and Systems for Grid Applications (St. Malo, France, July 2004), V. Getov and T. Kielmann, Eds., Springer, pp. 167-185. [8] Fortune, S., and Wyllie J. Parallelism in Random Access Machines. In Proceedings of the 10th Ann. ACM Symposium on Theory of Computing (1978), ACM Press, pp. 114-118. [9] Valiant, L. G. A Bridging Model for Parallel Computation. Communications of the ACM 33, 8 (1990), 103-111. [10] Culler, D. E., Karp, R. M., Patterson, D. A., Sahay, A., Schauser, K. E., Santos, E., Subramonian, R., and von Eicken, T. LogP: Towards a Realistic Model of Parallel Computation. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (May 1993), pp. 1-12. [11] Gorlatch, S. Send-Recv Considered Harmful? Myths and Truths about Parallel Programming. ACM Transactions in Programming Languages and Systems 26, 1 (Jan. 2004), 47-56. [12] Leavens, G. T., and Sitaraman, M. Foundations of Component Based Systems. Cambridge University Press, 2000. [13] Jain, R. - The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation and Modeling. John Wiley & Sons, 1991.