Influência da comunicação no rendimento de uma máquina paralela
virtual baseada em Redes ATM
Marcelo Souza *, Josemar Souza *, Milena Micheli **
( [email protected], [email protected], [email protected])
*
**
Universidade Católica do Salvador
Curso de Informática
Salvador, Bahia, Brasil
Projeto REMAV – SALVADOR (REMA)
Salvador, Bahia – Brasil
Resumo: Este artigo apresenta a avaliação do desempenho de uma máquina paralela virtual
de baixo custo utilizando uma rede de comunicação de alta velocidade padrão ATM. O
trabalho objetiva a criação e avaliação de uma máquina paralela virtual entre instituições
ligadas ao projeto REMAV - SALVADOR. Foram utilizados a estrutura de Rede do projeto
REMAV – SALVADOR, criando-se clusters de máquinas em diferente localidades a fim
de avaliar o desempenho (performance) dessa máquina “rodando” em rede padrão ATM em
comparação a uma máquina “rodando” em rede padrão Ethernet.
Palavras chave: ATM, REMA, Ethernet, PVM, NOW, SPMD, Redes de Computadores,
Sistemas Homogêneos, Computação Paralela, Linux.
1 - Introdução a Computação Paralela Virtual
Computação Paralela refere-se ao conceito de aumento de velocidade na execução de um
programa através da divisão deste em pequenos fragmentos que são distribuídos e
processados paralelamente, cada fragmento em um processador. Com isto obtemos um
ganho de performance na execução de uma tarefa. A premissa é a de que se executando
uma tarefa dividida entre vários processadores conseguiremos executa-la muito mais
rápido. [DIETZ98]
Esses sistemas são compostos por vários processadores que operam concorrentemente,
cooperando na execução de uma determinada tarefa. Nas chamadas arquiteturas paralelas o
objetivo principal é o aumento da capacidade de processamento, utilizando o potencial
oferecido por um grande número de processadores [STE99].
As máquinas paralelas de baixo custo, conhecidas como NOW1, utilizam as redes de
computadores comerciais, locais e/ou remotas para paralelizar suas transações. Utiliza um
software que permite que um conjunto heterogêneo ou homogêneo de computadores (série,
paralelos ou vetoriais) seja visto como uma única máquina. Dentre outros softwares
poderemos utilizar o PVM2 [ALG94] , que é um software que permite que um conjunto
heterogêneo ou homogêneo de computadores seja visto como uma única máquina, sendo a
portabilidade uma de suas características principais – as bibliotecas de rotinas de
comunicação entre processos são “standard” de fato [DON-LUQ99]. A independência de
plataforma que o PVM disponibiliza é indubitavelmente interessante; um software pode ser
executado em ambientes diferentes, este fato gera segurança para desenvolvedores de
software criarem aplicações paralelas, tendo em vista a portabilidade possível.
1.1 Necessidade de Computadores Paralelos
O alto custo de máquinas paralelas de qualidade voltada somente para este fim impede que
muitas instituições que necessitem de grande poder de processamento adquiram uma. Com
a chegada do limiar do aumento de capacidade de processamento das máquinas
seqüenciais, o processamento paralelo se torna uma solução a ser considerada e estudada.
Com a redução de custo e aumento de performance das Workstation, surgimento de
Sistemas Operacionais robustos, gratuitos e de fácil obtenção (Linux, FreeBSD, etc...), a
queda de preços em tecnologia de redes, obtém-se o cenário perfeito para a criação de
máquinas paralelas virtuais. É importante salientar que cada Workstation não perde sua
funcionalidade original ao ser utilizada dentro de um cluster de máquinas paralelas virtuais,
podendo ser incluída e retirada a qualquer momento.
1
Network of Workstation
2
Parallel Virtual Machine
2
1.2. Objetivo do trabalho
Um dos principais fatores, senão o principal, de desempenho de um algoritmo baseado em
troca de mensagens é a quantidade de mensagens geradas durante a sua execução, além do
número de mensagens, o custo de comunicação é muito importante. [SOU2000]
Muitas pesquisas e trabalhos foram feitos utilizando redes de baixo custo, principalmente
fazendo uso de redes padrão Ethernet, largamente aceita e de baixo custo na obtenção e
manutenção. Trabalhos que envolvam tecnologias mais complexas e caras como ATM são
quase escassos, devido ao alto custo de aquisição deste equipamentos e da falta de drivers e
utilitários para a utilização de tal rede em sua forma nativa o que possibilitaria um ganho de
performance nas passagem de mensagens em aplicações paralelas. O sistema operacional
mais utilizado para a criação de máquinas paralelas virtuais é o Linux, onde todos os
drivers e ferramentas para redes ATM ainda estão em desenvolvimento precisando ainda
serem analisados e testados.
1.3 Descrição do problema
O paradigma de programação utilizado foi o SPMD3 implementado com o esquema Mestre
Trabalhador (MT) ou Master Work (MW). No esquema Mestre Trabalhador, um processo
será o mestre, e os restantes trabalhadores. O processo mestre centraliza o controle, inicia
os trabalhadores, distribui o trabalho, sincroniza a comunicação e executa operações de I/O.
Para analisar comparativamente o rendimento em um ambiente de computação paralela que
se utiliza de comunicação pôr passagem de mensagem, principalmente nos aspectos
relacionados a cômputo e comunicação podemos utilizar:
•
aplicações reais;
•
programas sintéticos ou;
•
benchmark.
Em nosso caso, para poder analisar os diferentes aspectos de um sistema heterogêneo em
relação ao desempenho nos interessa escolher como benchmark uma aplicação escalável
tanto em cômputo quanto em comunicação.
3
Single Program Multiple Data
3
Para que um programa possa ser executado por um computador paralelo com memória
distribuída e passagem de mensagem uma das opções é distribuir a mesma cópia do seu
código entre os processadores, e os distintos conjuntos de dados a processar serão
distribuídos entre as diversas máquinas. [SOU-REX00]
Como algoritmo bem conhecido que apresenta estas características de escalabilidade
escolhemos os algoritmos de multiplicação de matrizes, que tem princípio básico de
funcionamento iguais, porém, com algumas modificações na estrutura de envio e
recebimento de dados para os nós da máquina paralela. O fator principal enquanto cômputo
e comunicação do ponto de vista de escalabilidade, e distribuição de carga, é o tamanho dos
blocos enviados para cada processo trabalhador, seguido da aplicação de comandos e
funções específicos da biblioteca PVM.
O algoritmo nos permite a fazer diferentes distribuições de trabalhos em cômputo,
comunicação e sobreposição de cômputo e comunicação. Também poderemos fazer
distribuição de carga simétrica ou distribuição de carga balanceada tendo em conta o grau
de heterogeneidade ou a potência específica de cada máquina.
O grau de heterogeneidade, que é a relação entre os índices de desempenho das distintas
máquinas que constituem o cluster heterogêneo, necessário para fazer a distribuição de
carga em sistemas heterogêneos, pode ser conseguido:
•
executando programa cálculo de matrizes em cada máquina de maneira serial, tomando
o tempo de execução de cada uma delas e dividindo o tempo de execução da máquina
mais rápida pelo tempo de execução das máquinas mais lentas ou;
•
executando um algoritmo que distribua carga dinamicamente, de maneira proporcional
ao desempenho de cada computador (modelo MW dinâmico) extraindo daí o trabalho
resultante que foi atribuído a cada processador, a medida de capacidade de cada
máquina.
2 – Necessidade de uma Rede de Alta Velocidade
A rede numa máquina paralela virtual serve como barramento para a comunicação entre as
máquinas pertencentes ao cluster, a depender da aplicação que está sendo rodada e de como
ela foi desenvolvida tem-se a necessidade de uma grande largura banda e de grande
disponibilidade da rede.
4
Ligando-se algumas dezenas de máquinas num cluster, a quantidade de mensagens
passadas entre elas podem ser um empecilho no aumento de processos, não pode-se perder
tempo na transmissão de mensagens entres as máquinas do cluster, o processador ficaria
ocioso neste tempo, perdendo assim parte da força da máquina paralela.
Foi utilizada para testes a rede de alta velocidade do Projeto REMA, padrão ATM
[ATMFORUM] uma tecnologia baseada na segmentação e transmissão (comutação) da
informação em pequenos pacotes de tamanho fixo chamados de “célula”, tendo uma
comutação rápida de pacotes.
A Rede ATM do Projeto REMA possibilita não só uma alta largura de banda mais
parâmetros de QoS (Qualidade de Serviço), que podem melhorar a transmissão de pacotes
dentro do cluster.
Uma das grandes vantagens da Rede ATM é a de poder interligar pontos distantes a grande
velocidade. O projeto em sua fase final, pretende a criação de uma máquina paralela entre
instituições parceiras. Testes foram e estão sendo feitos utilizando máquinas de duas
instituições (Universidade Católica do Salvador – UCSal e Universidade Federal da Bahia –
UFBa) parceiras, que estão interligadas através de Rede de Fibra Ótica a 155 Mbps do
Projeto REMAV-SALVADOR (Fig. 1)
Fig. 1 Rede do projeto REMAV-SALVADOR
5
3. Experimentos realizados
Foram realizados testes com programas de multiplicação de matrizes devido o seu alto
poder de escalabidade. Foi criado um cluster de duas máquinas homogêneas e executado
em cada uma destas um programa de multiplicação de matrizes seqüencial afim de avaliar a
capacidade de cada máquina incluída no cluster, este teste foram feitos em cada máquina
pertencente ao cluster. Em seguida foram executados dois programas de multiplicação de
matrizes modificados a partir do seqüencial, para fazer uso dos conceitos de paralelismo
utilizando-se do paradigma SPMD adotado. Primeiramente foi utilizado uma rede Padrão
Ethernet de 10Mbps. Logo depois foi utilizado uma Rede Padrão ATM (com placas de
25Mbps em cada máquina). Neste teste utilizou-se uma máquina localizada na
Universidade Católica do Salvador (UCSal) e outra na Universidade Federal da Bahia
(UFBa), parceiras no projeto REMA ligadas através de Fibra Ótica a uma velocidade de
155Mbps. As matrizes utilizadas para multiplicação tiveram dimensão 400 linhas x 400
colunas e 800 linhas x 800 colunas. Os programas utilizados para os testes são descritos a
seguir.
3.1 Programa Serial
O programa “serial.c” será utilizado para caracterizar a potência das máquinas. Esse
programa será executado em todas as máquinas que comporão a máquina paralela virtual .
“serial.c” , é o algoritmo que calcula serialmente a multiplicação de matrizes. Este
algoritmo Inicializa três matrizes. As matrizes “A” e “B” são usadas para o cálculo da
multiplicação, e a matriz
“C” recebe o resultado. O algoritmo “serial.c”, executa os
seguintes passos:
As máquinas utilizadas só tem capacidade de executar o algoritmo com alocação dinâmica
de memória, matrizes de até 800 x 800.
Algoritmo Serial - “serial.c”
Passo 1. O programa Inicializa as matrizes
Passo 2. Captura o tempo inicial
6
Passo 3. Realiza a multiplicação
Passo 4. Captura o tempo final
Passo 5. Diminui o tempo final do tempo inicial
Passo 6. Mostra o tempo de processamento em milisegundos
3.2. Programa Paralelo Mestre (Empacotamento Bloco a Bloco) – Assíncrono
(Mestre e Trabalhador)
Utiliza o empacotamento de dados bloco a bloco “assíncrono” - divide a matriz a ser
calculada pelo número de trabalhadores igualmente e envia as linhas a serem calculadas.
“blbalM.c” e “blbalE.c”, são os algoritmos que calculam paralelamente de maneira
assíncrona a multiplicação de matrizes.
Algoritmo Mestre - “blbalM.c ”
Passo 1. Mapa máquinas que serão utilizadas
Passo 2. Identifica task no PVM
Passo 3. Obtém informações sobre a Máquina Virtual
Passo 4. Imprime na tela o numero de trabalhadores na Máquina Virtual
Passo 5. Retorna e informa o numero de tasks criadas com sucesso
Passo 6. Inicializa ,matrizes
Passo 7. Inicializa o buffer de envio
Passo 8. Empacotam dados no buffer de envio
Passo 9. Inicia posição. na matriz
Passo 10. Envia o conteúdo do buffer de envio para a task escravo
Passo 11. Imprime mensagens diversas informando situação de envio
Passo 12. Espera pôr resultados das tasks trabalhador
Passo 13. Informa o tipo de mensagem
Passo 14. Recebe mensagem do trabalhador
Passo 15. Desempacota linhas
Passo 16. Imprime resultados em milisegundos e segundos
Passo 17. Grava o resultado do tempo decorrido em arquivo
7
Algoritmo Trabalhador - “blbalE.c”
Passo 1. Informa task id do escravo
Passo 2. Recebe mensagem do mestre
Passo 3. Informa tipo de mensagem, pega task id do processo mestre
Passo 4. Espera p/ receber mensagem do mestre
Passo 5. Inicia posição nas matrizes
Passo 6. Recebe linhas
Passo 7. Realiza multiplicação da matriz
Passo 8. Empacota dados do resultado para o mestre.
Passo 9. Informa tipo de mensagem
Passo 10. Inicializa buffer de envio
Passo 11. Envia
3.3 Programa Paralelo Mestre (Empacotamento Linha a Linha) - Semi-Síncrono
(Mestre e Trabalhador)
linhamwM.c e linhamwE.c
Utiliza empacotamento de dados linha a linha “semi-sincrono” - envia uma linha da matriz
a ser calculada para cada um dos trabalhadores que compõe a máquina virtual e recebe os
resultados à medida que elas calculem, tornando a lhes enviar novas linhas.
“linhamwM.c” e “linhamwE.c”, são os algoritmos que calculam paralelamente de maneira
Semi-sincrona a multiplicação de matrizes.
Algoritmo Mestre - “linhamwM.c”
Passo 1. Define linhas a serem enviadas
Passo 2. Faz mapeamento para máquinas estáticas (homogênea)
Passo 3. Identifica task no PVM
Passo 4. Obtêm informações sobre a Máquina Virtual
Passo 5. Informa a quantidade de trabalhadores que conterá a máquina virtual
8
Passo 6. Imprime na tela o numero de trabalhadores na Máquina Virtual
Passo 7. Informa o numero de tasks criadas com sucesso
Passo 8. Inicialização das matrizes
Passo 9. Envia o conteúdo do buffer de envio para a task escravo
Passo 10. Espera pôr resultados das tasks trabalhadoras
Passo 11. Informa o tipo de mensagem
Passo 12. Identifica o buffer do trabalhador
Passo 13. Recebe dados
Passo 14. Inicia posição. na matriz
Passo 15. Recebe linhas
Passo 16. Desempacota dados
Passo 17. Envia o conteúdo do buffer de envio para a task escravo
Passo 18. Envia FIM TRABALHO ao processo
Passo 20. Imprime resultados em milisegundos e segundos
Passo 21. Grava o tempo decorrido em arquivo
Algoritmo Trabalhador - “linhamwE.c”
Passo 1. Informa task id do escravo
Passo 2. Recebe mensagem do mestre
Passo 3. Pega task id do processo mestre
Passo 4. Informa tipo de mensagem
Passo 5. Espera p/ receber mensagem do mestre
Passo 6. Realiza multiplicação da matriz
Passo 7. Informa tipo de mensagem
Passo 8. Recebe dados
Passo 9. Espera p/ receber mensagem do mestre
Passo 10. Empacota dados do resultado para o mestre
Passo 11. Informa tipo de mensagem
Passo 12. Envia dados
Passo 13. Inicializa buffer de envio
Passo 14. Envia
9
3.4. Implementação
Para a implementação da máquina paralela virtual, utilizou-se como sistema operacional o
Linux (Kernel 2.2.9), utilitários para rede ATM (ATM on Linux v0.59), bibliotecas PVM
(PVM v3.4.3) e para implementação dos algoritmos paralelos a linguagem de programação
C, utilizando o compilador GCC4 incluso no Linux e protocolos Tcp/Ip (Tab.1) (Fig.2 ). Na
utilização da Rede ATM optou-se pelo uso de LANE (Lan Emulation) que simula uma rede
Ethernet em cima da rede ATM. Ás máquinas utilizadas para os testes foram.
-
Trabalhadores (PVM)
Host: icaro (UFBa)
IP: 200.123.59.15
Net Mask: 255.255.255.0
CPU: Intel Pentium 166 Mhz
Memória: 16 Mb
HD: IDE – 2.1 GB
Ethernet: 10 Mbps
ATM: 25Mbps
-
Host: pandora (UFBa)
IP: 200.128.59.17
Net Mask: 255.255.255.0
CPU): Pentium 166 Mhz
Memória: 16 Mb
HD: IDE - 2.1 GB
Ethernet: 10 Mbps
ATM: 25 Mbps
Host: perseu (UCSal)
IP: 192.168.103.10
Net Mask: 255.255.255.0
CPU: Intel Pentium 166 Mhz
Memória: 16 Mb
HD: IDE – 2.1 GB
Ethernet: 10Mbps
ATM: 25 Mbps
Mestre (Não envolvido no trabalho, apenas administrar o cluster)
Host: gandalf (UFBa)
IP: 200.128.59.12
Net Mask: 255.255.255.0
CPU: Intel Celeron 466 Mhz
Memória: 64 Mb
HD: IDE – 5.1 GB
Ethernet: 10 Mbps
ATM: 25Mbps
Tab.1 – Especificação das máquinas
4
GCC Gnu C Compiler
10
Fig.2 Ambiente de teste
4. Resultados obtidos
Os seguintes resultados foram obtidos:
Tab.2 - Programa “serial.c”, Multiplicação de Matrizes seqüencial . Executado em cada máquina do
cluster.
Algoritmo
Serial
Serial
Serial
Serial
Máquina
Pandora
Icaro
Perseu
Gandalf
200
5329
5346
4986
-
Matriz (tamanho)
400
51508
50868
48197
8361
800
111749
Tempo de execução
(Mseg)
11
Algoritmo Serial
60000
50000
Mseg
40000
Matriz 200 X 200
30000
Matriz 400 X 400
20000
10000
0
Pandora
Icaro
Perseu
Máquina
O cluster da máquina paralela virtuais nos testes foram formado por dois trabalhadores.
Tab. 3 - Programa “blbal” sobre ATM. Paralelo Bloco a Bloco. Executado no mestre(gandalf) que
distribui a tarefa para os trabalhadores, ao termino do processo os trabalhadores retornam a resposta.
Cluster formado pelas máquinas perseu e icaro.
Algoritmo
Paralelo Bloco a Bloco
Máquina
PVM
Matriz (tamanho)
400
800
28589
248591
Tempo de execução (Mseg)
Tab. 4 - Programa “blbal” sobre Ethernet. Paralelo Bloco a Bloco. Executado no mestre(gandalf) que
distribui a tarefa para os trabalhadores, ao termino do processo os trabalhadores retornam a resposta.
Cluster formado pelas máquinas pandora e icaro.
Algoritmo
Paralelo Bloco a Bloco
Máquina
PVM
Matriz (tamanho)
400
800
30247
260235
Tempo de execução (Mseg)
12
Algoritmo Bloco Balanceado
300000
250000
Mseg
200000
blbal sobre ATM
150000
blbal sobre Ethernet
100000
50000
0
400
800
Tam. Matriz
Tab. 5 - Programa “linhamw” sobre ATM, Paralelo Linha a Linha. Executado no mestre(gandalf) que
distribui a tarefa para os trabalhadores, ao termino do processo os trabalhadores retornam a resposta.
Cluster formado pelas máquinas perseu e icaro.
Algoritmo
Paralelo Linha a Linha
Máquina
PVM
Matriz (tamanho)
400
800
27633
236204
Tempo de execução (Mseg)
Tab. 6 - Programa “linhamw” sobre Ethernet, Paralelo Linha a Linha. Executado no mestre(gandalf)
que distribui a tarefa para os trabalhadores, ao termino do processo os trabalhadores retornam a
resposta. Cluster formado pelas máquinas pandora e icaro.
Algoritmo
Paralelo Linha a Linha
Máquina
PVM
Matriz (tamanho)
400
800
30382
252207
Tempo de execução (Mseg)
13
Algoritmo Linha a Linha Balanceado
300000
Mseg
250000
200000
linhamw sobre ATM
150000
linhame sobre Ethernet
100000
50000
0
400
800
Tam Matriz
5. Conclusões
Notou-se um sensível ganho de performance quando utilizando a Rede Padrão ATM nos
casos de matrizes de tamanho 800 x 800. Nenhuma diferença considerável se notou em
matrizes de tamanho 400 x 400 ou utilizando a transmissão de Linha a Linha. Mais testes
são necessários, com uma quantidade maior de máquinas no cluster, para melhor ser
avaliado a eficiência em uma redes ATM. Implementações de tecnologias para melhora de
transmissão das redes ATM precisam ser testadas e avaliadas.
6. Trabalho futuro
Muitos experimentos ainda são necessários para se avaliar as vantagens de uma Rede ATM
na criação de uma máquina paralela virtual. Novos testes devem serem feitos considerando
diferentes configurações de redes:
•
“Classical IP”: Com o protocolo IP “rodando” diretamente sobre a AAL5.
•
LANE com MPOA: Com conexões ATM fim-a-fim podendo ser estabelecidas entre
máquinas de um cluster pertencentes a ELANS diferentes.
•
Nativa ATM: Com eliminação de overhead causado pelo encapsulamento de pacotes IP
em células ATM.
14
Tais testes são fundamentais para possibilitar a criação de clusters entre instituições filiadas
ao projeto REMA a fim de se obter uma maior quantidade de máquinas na criação de
poderosas Máquinas Paralelas Virtuais. Essas máquinas são necessárias a grandes
instituições que buscam um alto poder de processamento de dados em menor espaço de
tempo mas que não dispõem de recursos para obter uma máquina paralela convencional.
Estando ainda em desenvolvimento os drivers e utilitários para redes ATM em plataforma
Linux – o sistema operacional adotado na criação dessa máquina paralela virtual, ainda não
se tem dados concretos sobre sua eficiência. Serão feitos testes utilizando matrizes muito
grande (acima de 800 x 800) e aplicações reais existentes como por exemplo Pvmpovray
que serve para renderização de gráficos e outras em desenvolvimento.
15
6. Referências Bibliografia
[ALG94] Geist, Al. Beguelin, Adam. Dongarra, Jack. Wicheng, Jiang. Mancheck, Robert.
Sunderam, Vaidy. PVM 3 User’s Guide and Reference Manual. Prepared by the Oak Ridge
National Laboratory. 1994
[DON-LUQ99] Jack Dongarra, Emilio Luque, Tomàs Margalef (Eds.). Recent Advances in Parallel
Virtual Machine and Message Passing Interface. 6th European PVM/MPI User’s Group Meeting.
Barcelona, Spain, September 1999. Proceeding.
[SOU2000] Souza, Josemar R. de. Influencia de la comunicación en el rendimimiento de un sistema
de computación paralela, basado en redes de estaciones de trabajo. Tese de Mestrado, Arquitetura
de Computadores e Processamento Paralelo. Universidade Autônoma de Barcelona, - UAB. 2000
[SOU-REX00] Souza, Josemar. Luque, Emilio. Rexachs, Dolores . Análise da distribuição de carga
em um cluster heterogêneo. VI Congresso Argentino de Ciencias de la Computación – CACIC
2000, Universidad Nacional de la Patagonia San Juan Bosco – UNP, Ushuaia, Tierra del Fuego,
Argentina. 2000. Anais.
[STE99] Sterling, Thomas L. Salmon, John. Becker, Donald J. e Savaresse, Daniel F. How to build
a Beowulf: a guide to the implementation and aplication of PC clusters. Massachusetts Institute of
Technology. 1999
[DIETZ98] Dietz, Hank Linux Parallel Processing How To. 5 January 1998. http://www.ldp.org.
2000.
[ATMFORUM] http://www.atmforum.com
16