Struktur  i  analysene

Construir máquinas poderosas como as apresentadas nas seções anteriores, é apenas uma parte da história dos sistemas de computação paralelos. Tais supercomputadores devem ser programados, e softwares dedicados devem ser criados para que essas máquinas obtenham o

desempenho desejado. Para isso, nessa seção, sobe-se um nível na abstração desses sistemas, e trata-se dos processos que são executados nos processadores dessas máquinas paralelas.

Desenvolver programas para qualquer sistema de computador é difícil e exige bastante tempo. Entretanto, essa tarefa de desenvolvimento torna-se ainda mais complicada quando se trata dos detalhes inerentes ao paralelismo [17]. Enquanto a programação seqüencial já é largamente aceita e praticada pela maioria das pessoas, a programação paralela ainda é vista, em alguns casos, como uma rara e exótica subárea da computação, interessante e intelectualmente desafiadora, mas pouco relevante para muitos programadores [3].

No paradigma seqüencial de programação, o programador possui uma visão simplificada da máquina como sendo um único processador que pode acessar certa quantidade de memória. Já o paradigma de troca de mensagens é uma busca da portabilidade para a programação paralela. Neste paradigma, várias instâncias do paradigma seqüencial trabalham juntas. Isto significa que o programador pode imaginar vários processadores, cada um com a sua própria memória, e escrever um programa para executar em cada processador. Entretanto, a programação paralela, por definição, requer a cooperação entre os processadores para resolver o problema, o que torna necessário a implementação de algum meio de comunicação.

2.5.1PARADIGMA DA TROCA DE MENSAGENS

Uma maneira natural de se programar em máquinas de memória distribuída é através da troca de mensagens, assim como, nas máquinas de memória compartilhada, é natural o uso de variáveis compartilhadas. Entretanto, é possível também inverter ou mesclar esses paradigmas, onde se usa troca de mensagem em máquinas de memória compartilhada e variável compartilhada em máquinas de memória distribuída [3]. Ambas as abordagens são praticadas. Contudo, o uso de variáveis compartilhadas em máquinas de memória distribuída exige camadas adicionais de software para prover uma visão compartilhada da memória que se apresenta fisicamente distribuída, conforme foi apresentado na seção 2.3.

A principal característica do paradigma da troca de mensagens é que os processadores comunicam-se através do envio e recebimento de mensagens. Assim, nesse modelo não há o conceito de memória compartilhada ou de processadores que possam acessar a memória de outro processador diretamente.

O paradigma da troca de mensagens vem se tornando cada vez mais popular. Uma das razões é o grande número de plataformas que oferecem suporte à troca de mensagens. Programas escritos neste paradigma podem executar em multiprocessadores de memória distribuída ou compartilhada, redes de computadores e sistemas com um único processador.

Segundo [3], existem três maneiras de programar em um ambiente de troca de mensagens:

• Desenvolvendo uma linguagem de programação paralela.

• Modificando uma linguagem seqüencial existente para manipular a troca de mensagens.

• Usando uma linguagem seqüencial de alto nível já existente, juntamente com uma biblioteca que forneça rotinas de troca de mensagens.

Existem exemplos para as três abordagens citadas. A linguagem OCCAM, que foi criada para ser usada no Transputer, é um exemplo para a primeira abordagem. Para a segunda abordagem, diversas linguagens seqüenciais foram estendidas para prover funcionalidades à troca de mensagem. Como exemplo, é possível citar CC+, que é uma extensão da linguagem C++. E Fortran M, como extensão da linguagem Fortran. Nessa dissertação, os estudos estão concentrados na terceira abordagem, onde são utilizadas linguagens de alto nível como Java e C, apoiadas em bibliotecas que ofereçam suporte a comunicação por troca de mensagem.

Existem algumas bibliotecas para troca de mensagem disponíveis, sejam elas comerciais ou não, e de plataformas especificas ou independentes. Duas bibliotecas muito usadas e que são para plataformas independentes, são: PVM (Parallel Virtual Machine) [18, 19] e MPI (Message Passing Interface) [20]. Um exemplo de biblioteca comercial para plataforma específica é NCube. Nessa seção, o paradigma da troca de mensagem não será abordado em detalhes. Apenas uma descrição abstrata das funções mais usadas será apresentada. Mais detalhes pode ser conseguido em [18, 20].

2.5.1.1ROTINAS PARA TROCA DE MENSAGENS

As funções básicas do paradigma de troca de mensagem são o envio e o recebimento (send e recv), e são usadas respectivamente pelos processos ao enviar e receber mensagens como forma de comunicação. Essas primitivas podem ser tanto síncronas como assíncronas, conforme a Tabela 4:

Tabela 4: Primitivas básicas de comunicação

Síncronas • ssend (bufer, destino)

• recv (bufer, origem)

Assíncronas • send (bufer, destino)

Um conhecimento importante que se deve ter quando se trabalha com funções de troca de mensagens, é a diferença entre síncrona e assíncrona. As funções síncronas, ou bloqueantes (ssend e recv), só retornam após a transferência dos dados ter sido completada. Antes disso, os processos ficam bloqueados, conforme a Figura 8.

Figura 8: Troca de mensagem síncrona

Por outro lado, as funções assíncronas, ou não bloqueantes (send e irecv), retornam imediatamente após a comunicação ter sido iniciada. Nesse caso, a mensagem a ser enviada deve ser copiada para um buffer, e logo após é transferida pelo sistema para o buffer do processo destino. A função de recebimento deve ler essa mensagem do buffer tão logo ela esteja disponível.

Esse comportamento não bloqueante não apresenta problemas para a função send, mas requer alguns cuidados para a função irecv, pois uma vez que a função de recebimento não bloqueante retorna imediatamente, nada garante que a mensagem foi entregue ou não. Para esse propósito, existe uma outra função importante e que pode ser usada para verificar se uma mensagem a ser enviada está disponível ou não, que é a:

• test(origem)

Através dessa função esse problema pode ser solucionado, retornando true caso a mensagem esteja disponível, ou false caso contrário. Essa função de teste geralmente é usada em um laço para o recebimento, onde a função irecv só é chamada quando a função de teste retornar true, indicando que a mensagem está disponível no seu buffer.

A maioria das bibliotecas de troca de mensagem oferece bem mais funções do que as apresentadas acima. Por exemplo, é possível especificar grupos de processos para enviar mensagens de maneira coletiva como: gather, scatter, reduce, entre outras. Mais detalhes e a

lista completa de funções de comunicação podem ser conseguidos em [18, 19, 20]. Entretanto, para esse trabalho, as funções apresentadas são suficientes.

2.5.2PARADIGMA DA VARIÁVEL COMPARTILHADA

A principal diferença desse paradigma para o paradigma da troca de mensagens é o uso de variáveis compartilhadas, ao invés de troca de mensagens. Como já foi visto na Seção 2.2, em ambientes de memória compartilhada, todos os processos têm acesso a uma memória global, com um único espaço de endereçamento. Conseqüentemente, qualquer local da memória pode ser acessado por qualquer processo. Isso requer mecanismos de sincronização para evitar que uma mesma variável seja alterada ao mesmo tempo por mais de um processo, em um mecanismo chamado de exclusão mútua.

Como nesse trabalho o paradigma utilizado é o baseado em troca de mensagens, mais detalhes sobre as variáveis compartilhadas podem ser conseguidos em [3, 4, 12].