É um exemplo de interface de desenvolvimento para memória distribuída por passagem de mensagens

Este artigo apresenta uma proposta que contempla a construção de programas concorrentes híbridos, usando tanto o modelo de troca de mensagens quanto o de memória compartilhada. Esta proposta é implementada no ambiente P-RIO, originalmente orientado à troca de mensagens, que foi estendido de modo a permitir a utilização simultânea dos dois modelos em diferentes partes de uma mesma aplicação. O ambiente inclui uma metodologia baseada em objetos para a construção e programação de aplicações distribuídas e paralelas. Em particular, essa metodologia é centrada no paradigma de configuração, incentivando a composição modular de aplicações e também a reutilização de código. O suporte para memória compartilhada permite a seleção, no domínio da configuração, de protocolos de consistência específicos para cada conjunto de módulos, facilitando a experimentação e ajuste na busca por melhores desempenhos.

This paper presents a proposal that promotes the construction of hibrid concurrent systems using the message passing and distributed shared memory models. This proposal is implemented in the P-RIO environment, originally message-passing oriented, which was extended in order to support simultaneously the use of both models, in different parts of an application. The environment includes an object-based methodology for building and programming parallel and distributed applications. In particular, the methodology hinges on the configuration paradigm that helps to achieve modularity and code reuse. The shared memory support allows the selection, through configuration, of specific consistency protocols for each particular module set, facilitating experimentation and tuning in the search for better performance.

O baixo custo e a disponibilidade de grupos de estações de trabalho, assim como o desenvolvimento de redes de alta velocidade, têm permitido a construção de sistemas de processamento paralelo e distribuído a partir destes elementos. Nestes sistemas, a comunicação entre os diferentes processadores é realizada, nos níveis mais baixos, mediante troca de mensagens. Isso transparece no nível da aplicação através de modelos de programação orientados à troca de mensagens. Embora seja natural, este modelo pode dificultar o desenvolvimento de programas paralelos por parte de pessoas pouco treinadas, especialmente em aplicações aonde os padrões de interação e compartilhamento de dados são complexos.

Uma forma de simplificar a tarefa do programador é gerar, mediante software, a visão de que existe uma memória compartilhada por todas as estações de trabalho. Essa simplificação é particularmente evidente em aplicações que se adaptam ao modelo de programação SPMD (Single Program Multiple Data), aonde a concorrência pode ser derivada a partir da replicação de partes da computação do programa seqüencial original. Atualmente, existem várias propostas para o suporte de DSM (Distributed Shared Memory) por software. Todas elas permitem a abstração de memória compartilhada, em forma transparente e relativamente eficiente, sobre ambientes distribuídos [Pro96].

Por outro lado, nem todas as partes de uma aplicação, nem todas as aplicações, apresentam padrões de comunicação complexos. Algumas aplicações, inclusive, são mais fáceis de programar em um modelo de troca de mensagens que em um modelo de memória compartilhada. Além disso, para certas aplicações o desempenho alcançado através do uso de troca de mensagens pode ser superior ao obtido usando software DSM [Lu95]. Normalmente, isso acontece quando uma aplicação usando um suporte para DSM transmite um número maior de mensagens e dados que o requerido quando programada explicitamente com troca de mensagens. Desta forma, é desejável ter um ambiente que facilite a programação de aplicações em qualquer um destes modelos, permitindo, inclusive, misturar os dois modelos de programação em uma mesma aplicação.

Uma motivação adicional, para nossa pesquisa, é a de facilitar a construção de grandes aplicações de tempo-real baseadas em sistemas distribuídos, mas que incluam, também, subsistemas de alto desempenho baseados em multiprocessadores dedicados.

Neste artigo é apresentada uma proposta que permite a construção de programas concorrentes híbridos, usando tanto troca de mensagens quanto memória compartilhada. Esta proposta é baseada no ambiente P-RIO (Parallel-Reconfigurable Interconnectable Objects) [Car95, Car96, Car97], originalmente orientado à troca de mensagens, que foi estendido de modo a permitir a utilização simultânea dos dois modelos em diferentes partes de uma mesma aplicação. O ambiente utiliza uma metodologia baseada em objetos para a programação de aplicações distribuídas e paralelas. Em especial, a metodologia de P-RIO é centrada no paradigma da configuração, facilitando a composição modular de aplicações e também a reutilização de código. O suporte para memória compartilhada, embutido no ambiente, permite a seleção, no domínio da configuração, de protocolos de consistência específicos para cada conjunto de módulos, facilitando a experimentação e ajuste na busca por melhores desempenhos.

A seguir, na seção 2, são descritas brevemente as características principais do ambiente P-RIO. Na seção 3 é mostrada, através de um exemplo, a programação baseada em troca de mensagens no contexto do ambiente. Na seção 4, por outro lado, são apresentados os conceitos e recursos oferecidos pelo sistema para a programação de aplicações usando memória compartilhada; alguns detalhes de implementação são também descritos. Na seção 5 são citados alguns trabalhos relacionados e, finalmente, na seção 6, são apresentadas conclusões e propostas de trabalhos futuros.

P-RIO é um ambiente que permite a programação de aplicações distribuídas e paralelas através de uma abordagem baseada em objetos. Em particular, o ambiente inclui uma metodologia de construção de sistemas centrada no paradigma de configuração, fazendo com que uma aplicação possa ser construída a partir da seleção e interconexão de um conjunto de módulos. A programação de cada módulo individual é, em grande parte, isolada da construção da aplicação, pois cada módulo encapsula suas próprias variáveis e os métodos que atuam sobre essas variáveis. Os módulos podem ser programados pelo usuário ou obtidos de uma biblioteca já existente, o que contribui para a reutilização de código. Para a construção de uma aplicação, dispõe-se de uma linguagem de configuração que permite especificar a criação de instâncias de módulos e definir as suas interconexões, através da ligação de portas de comunicação. De acordo com a proposta original, os métodos, podem ser associados às portas, sendo permitida também uma variedade conectores, associados a diferentes estilos de trocas de mensagens, usados para as interações entre módulos.

Com o objetivo de estabelecer uma diferenciação, no contexto do ambiente P-RIO, entre o modelo original de troca de mensagens e o modelo de memória compartilhada, é usado um sistema para o cálculo da FFT (Fast Fourier Transform), o qual é programado e configurado segundo os dois conceitos. Na próxima seção, é apresentada a versão baseada em troca de mensagens. Na seção 4, considera-se, em mais detalhes, a mesma aplicação utilizando memória compartilhada.

Figura 1. Sistema para Cálculo da FFT

A figura 1 apresenta a configuração gráfica do sistema para cálculo da FFT de um vetor qualquer, via troca de mensagens. O módulo master embaralha o vetor de entrada e o envia através de mensagens para cada um dos módulos slave. Estes módulos, por sua vez, trocam os resultados parciais obtidos ao final de cada uma das fases do cálculo da FFT. Para essa troca é usado o suporte de comunicação de grupo disponível no ambiente P-RIO, que automaticamente distribui as mensagens enviadas por cada módulo a todos os outros módulos, membros do grupo. Deve-se notar que isso simplifica a programação das interações entre os componentes do programa, em relação à utilização exclusiva de comunicação ponto-a-ponto. Uma listagem da especificação usada para a construção desta aplicação, na correspondente linguagem de configuração, é apresentada na figura 2.

Figura 2. Especificação da Configuração: Troca de Mensagens

Na figura 3, é apresentado o código do módulo slave programado com base no modelo de troca de mensagens. Depois da fase de iniciação, cada instância do módulo slave, recebe o vetor x proveniente do módulo master. Posteriormente, em cada fase de processamento (determinada pelo índice j), são atualizados os elementos designados a esse módulo através das funções fmin() e fmax(), as quais dependem do identificador de módulo particular mid. A seguir, os elementos atualizados são enviados às outras instâncias do módulo slave, via comunicação de grupo. Após o envio, cada instância espera o recebimento de todas as modificações feitas pelas outras instâncias, antes de iniciar a execução de uma nova etapa.

A versão anterior do ambiente P-RIO, baseada em troca de mensagens, foi construída usando a biblioteca PVM (Parallel Virtual Machine) [Gei94], o que a torna bastante portável. Ela também inclui uma interface gráfica que permite a configuração, visualização e depuração de aplicações, tanto no nível dos módulos individuais quanto no nível de suas interconexões [Car95]. Esta ferramenta, em conjunto com um configurador, permite que sistemas tenham sua composição alterada na fase operacional, facilitando a substituição de módulos para fins de experimentação.

Com base nas motivações apresentadas na introdução, é proposta a inclusão de mecanismos de suporte que permitam a programação e configuração de aplicações usando o modelo de memória compartilhada no ambiente P-RIO. O alvo central desta proposta é facilitar a utilização simultânea dos dois modelos de programação, troca de mensagens e memória compartilhada, na implementação de uma mesma aplicação. Desta forma, o programador poderá selecionar, para cada módulo, o modelo mais apto às suas necessidades em termos de facilidade de implementação e/ou desempenho.

Figura 3. Código do Módulo Slave: Troca de Mensagens

Além disso, a proposta tenta manter a característica de configurabilidade de P-RIO, conservando, assim, a flexibilidade oferecida pela metodologia na qual o ambiente está baseado [Car97]. Desta maneira, diferentes protocolos de consistência poderão ser selecionados na fase de configuração, de acordo com os requisitos de compartilhamento dos dados por parte de cada aplicação.

Na programação dos módulos que usam o modelo de memória compartilhada, a interação disciplinada entre instâncias replicadas do algoritmo (implementadas por processos concorrentes) pode ser garantida através do uso de primitivas do tipo lock, para situações de exclusão mútua, e do tipo barrier, para situações de sincronização entre as fases de um algoritmo paralelizado, i.e., replicado e executado em diferentes processadores. Todas as variáveis declaradas como compartilhadas, por parte do programador, serão mantidas coerentes através do respectivo protocolo de consistência.

Cada protocolo específico, normalmente, executará uma serie de ações tanto na leitura e escrita de variáveis compartilhadas, como nas chamadas a barreiras e nos acquire e release de locks. Por este motivo, o suporte para memória compartilhada oferecido por P-RIO está centrado na implementação das funções READ(), WRITE(), LOCK(), UNLOCK() e BARRIER(). As três últimas funções podem ser usadas diretamente pelo programador, enquanto que, as duas primeiras, devem ser inseridas pelo compilador em todos os acessos de leitura ou escrita a uma variável compartilhada.

Várias versões deste conjunto de funções podem estar disponíveis no ambiente. Usuários experientes também poderiam implementar suas próprias versões. As diferenças entre as versões destas funções vão determinar o modelo de consistência implementado e/ou as otimizações feitas com base em características altamente dependentes da aplicação.

Como visto, as operações que serão realizadas pelas funções READ(), WRITE(), LOCK(), UNLOCK() e BARRIER(), dependem do tipo de protocolo de consistência selecionado para cada conjunto de módulos, no momento da configuração do programa.

A versão atual do sistema fornece duas variantes deste conjunto de funções. O primeiro implementa um protocolo de consistência relaxada baseada em updates sem otimizar o número de mensagens transmitidas. O segundo, por outro lado, além de implementar um algoritmo de consistência relaxada, também baseado em updates, otimiza o número de mensagens transmitidas mediante o agrupamento de todas as escritas dentro de uma mesma fase de sincronização. A seguir, descreve-se brevemente os dois protocolos.

Modelo Simples

Nesta versão, a função READ() simplesmente verifica se existe alguma mensagem que atualize a variável antes de retornar o seu valor. Se não existe nenhuma mensagem de atualização, a função retorna o valor anterior, caso contrario, mensagens são utilizadas para atualizar a variável antes de retornar o seu valor. A função WRITE(), por sua vez, além de atualizar o valor da variável, gera uma mensagem de atualização dirigida a todos os módulos que compartilham essa variável com a modificação realizada.

As funções LOCK() e BARRIER() iniciam enviando uma mensagem ao gerente de locks e/ou barriers, e ficam bloqueadas até que recebam a confirmação ao seu pedido. No momento que recebem a confirmação, aplicam todas as mensagens com as modificações feitas pelas outras instâncias antes de continuar com a execução do programa. A invocação da função UNLOCK(), por outro lado, somente gera o envio de uma mensagem ao gerente de locks indicando a saída e liberação da seção crítica.

Modelo Otimizado

No protocolo de consistência otimizado, em relação ao anterior, a função READ() unicamente retorna o valor da variável que está sendo acessada. A função WRITE(), por sua vez, além de atualizar o valor da variável, acumula todas as modificações em uma fila exclusiva para cada instância. As funções de sincronização UNLOCK() e BARRIER() serão as encarregadas de enviar, a todas as outras réplicas do mesmo módulo, as modificações feitas até esse momento. Além disso, elas executam todas as ações definidas no modelo anterior (não otimizado). A função LOCK(), por outro lado, apresenta o mesmo comportamento do modelo anterior.

A especificação da configuração para a mesma aplicação mostrada na seção 3, figura 2, para o cálculo da FFT, usando o paradigma de memória compartilhada, é apresentada na figura 4. Note que, a nível da configuração, esta versão usa um único módulo master e um único módulo slave (figura 5-a). No entanto, a nível da implementação (figura 5-b), devido ao fato que o módulo slave usa a abstração de memória compartilhada, ele é instanciado N vezes (número especificado pelo programador no domínio de configuração) pelo suporte do ambiente P-RIO. Note que em propostas convencionais a paralelização é especificada no código explicitamente através de primitivas tipo fork ou distribute.

Figura 4. Especificação da Configuração: Memória Compartilhada

Neste exemplo, os dados compartilhados pelas réplicas do módulo slave serão mantidos coerentes através do protocolo de consistência dsm_relaxed (uma das versões atualmente disponíveis no sistema). É importante mencionar, também, que além de usar uma programação baseada no modelo de memória compartilhada, o exemplo usa também uma programação com troca de mensagens para a comunicação entre os módulos master e slave. Uma alternativa seria também compartilhar dados (no caso o vetor x) entre os módulos master e slave.

Figura 5. Cálculo da FFT: Memória Compartilhada

Na figura 6 é mostrado o código que implementa o módulo slave. Devido a ainda não dispormos de um compilador especializado, é usada a função SHARED() para substituir a declaração:

Esta função permite incluir, no código, algumas chamadas e declarações que seriam geradas automaticamente por um compilador. Por exemplo, a alocação de um identificador único que acompanhará todas as mensagens com atualizações para essa variável, criar e inicializar todas as estruturas usadas para garantir a coerência entre os valores replicados dessa variável, etc. Note, também, que a função WRITE(), atualmente usada explicitamente no código, poderia ser substituída por expressões do tipo:

posteriormente, o compilador faria a substituição do acesso à variável compartilhada pela função de biblioteca correspondente.

Figura 6. Código do Módulo Slave: Memória Compartilhada

Como se pode constatar, nesse exemplo, a programação pode ser simplificada, através da utilização de um modelo de memória compartilhada, quando comparada com a baseada em troca de mensagens apresentada anteriormente.

No sistema atual, tanto os locks como as barreiras são implementados em forma centralizada [Stu90]. Para isso, existe um gerente de locks e barriers que recebe todos os pedidos por lock, assim como todos os avisos de barreira. O gerente se encarrega, então, de serializar os acessos às seções críticas, e de permitir a continuação dos processos depois da efetivação de uma sincronização por barreira. Implementações futuras, com maiores requisitos de escalabilidade, poderão se beneficiar de um esquema que suporte um gerente individual para cada lock e barreira usados no sistema. Isso eliminaria possíveis contenções, permitindo um melhor desempenho.

Durante o processo de compilação, um identificador diferente é associado a cada variável compartilhada. Como o atual suporte para memória compartilhada de P-RIO está baseado em uma abordagem SPMD, esses identificadores são sempre os mesmos em todas as réplicas dos módulos. Desta forma, para que as atualizações sejam aplicadas corretamente, é necessário que cada modificação vá acompanhada pelo identificador da variável, e caso se trate de um array, pelos índices respectivos.

Toda a comunicação necessária para o envio das atualizações, assim como para as tarefas de sincronização, foi implementada através de sockets. Isso objetiva evitar o overhead imposto pelo sistema PVM, em que se baseia a versão com troca de mensagens de P-RIO, especialmente para operações de disseminação, que são realizadas através de uma série de mensagens ponto-a-ponto. Desta forma pode-se aproveitar o suporte de disseminação em baixo nível provido por algumas redes. Assim, no protótipo implementado sobre estações de trabalho ligadas por uma rede Ethernet, as modificações feitas por cada instância são enviadas a todas as outras réplicas através de uma única mensagem de broadcast. Por outro lado, os pedidos de lock e avisos de barreira são enviados através de mensagens ponto-a-ponto entre os diferentes módulos e o gerente correspondente. Cada lock e cada barreira são identificados através do nome da variável associada, expressa na forma de uma cadeia de caracteres. Para esta comunicação, é utilizado o protocolo UDP.

Deve-se ressaltar que tanto o envio de mensagens de broadcast como a utilização do protocolo UDP não oferecem confiabilidade total na comunicação de dados. A simplicidade desta camada de software pode se justificar pela baixa taxa de probabilidade de perda de pacotes em redes locais. Tal opção é adotada pela maioria de propostas para software DSM, sendo compatível com às classes de aplicações que pretendem suportar. Contudo, para o uso deste paradigma em subsistemas pertencentes a aplicações de tempo-real, ou com um tempo de execução muito longo, maiores garantias de confiabilidade devem ser asseguradas. Neste sentido, pretendemos ainda investigar técnicas que permitam obter tolerância a falhas e alta confiabilidade sem comprometer fortemente o desempenho do sistema, e.g., [Ker97].

Como foi mencionado anteriormente, um dos objetivos desta proposta é estender as características do paradigma de configuração ao suporte de memória compartilhada, assim permitindo que o protocolo de consistência possa ser selecionado no domínio de configuração. O suporte de operação necessário é obtido através de diferentes bibliotecas, associadas aos protocolos disponíveis, que são ligadas a cada módulo específico. Na versão atual, são mantidas várias versões de um mesmo módulo, cada uma ligada a uma biblioteca diferente. No entanto, nada impede que o processo de ligação seja efetuado somente quando requerido, mantendo-se então uma única versão para cada módulo.

Existem vários sistemas que permitem a construção de programas paralelos sobre uma rede de estações de trabalho. PVM [Gei95] e MPI [Don96], por exemplo, usam o modelo de troca de mensagens. Os dois são disponíveis através de bibliotecas portáveis, sendo que MPI, antes que uma biblioteca, é um padrão adotado por vários construtores de software e hardware. Diferentemente de PVM e MPI, P-RIO separa a programação dos componentes, da construção da própria aplicação, utilizando para isso o paradigma da configuração. Esta característica de modularidade, além de simplificar a programação, facilita a reutilização de código.

Sistemas que usam o modelo de memória compartilhada também têm chegado a ser muito populares (e.g. Midway [Ber93] e TreadMarks [Kel94]). A maioria deles é disponível através de bibliotecas, que compiladas junto às aplicações, permitem dispor de um espaço de endereçamento global que é enxergado por todos os processos da aplicação. Nossa proposta não descarta a integração destas bibliotecas no ambiente P-RIO. Contudo, para isso devem ser solucionados diversos problemas referentes à compatibilidade com as outras bibliotecas já utilizadas pelo ambiente. Na fase atual do projeto, no lugar de usar uma destas bibliotecas para a implementação dos módulos que fazem uso de memória compartilhada, preferiu-se usar um conjunto de protocolos simples e especializados, de modo a dar ao usuário a possibilidade de seleção e experimentação no nível de cada conjunto de módulos.

Orca [Bal92] é também um sistema baseado em objetos que permite a programação de aplicações paralelas sobre sistemas distribuídos. A sincronização, nesta proposta, é mantida através de exclusão mútua a nível dos métodos de acesso às funções de cada objeto. O sistema também permite a replicação de objetos, mas a consistência é garantida mediante a difusão, em uma mesma ordem, das mensagens de invocação dos métodos para todas as réplicas. Assumindo que os métodos têm um processamento determinístico, a coerência dos dados é assegurada. A ordenação das mensagens é garantida através de um protocolo de difusão confiável disponível no sistema operacional Amoeba [Tan92]. Métodos que não alteram valores de dados (chamados read-only) podem ser executados localmente visando maior desempenho. Eles são identificados pelo compilador de Orca ou pelo programador.

P-RIO, por outro lado, diminui a quantidade de processamento sincronizado em cada nó, por não requerer a sincronização total da execução de todos os métodos em todas as réplicas. A coerência dos dados de cada módulo é mantida usando protocolos de consistência ativados pelas primitivas de sincronização, especificadas explicitamente pelo programador. Alternativamente, a ativação do protocolo de consistência em P-RIO também poderia ser associada à invocação dos métodos, como na proposta de Orca. Contudo, a primeira alternativa, adotada em nosso protótipo, permite uma granularidade mais fina de sincronização, o que é benéfico em termos de desempenho. Além disso, ela suporta naturalmente a execução de métodos que executam somente leitura de dados.

P-RIO também se diferencia dos outros sistemas mencionados, no fato de integrar, em um mesmo ambiente, o modelo de troca de mensagens com o modelo de memória compartilhada. Por ser centrado no paradigma da configuração, facilita a seleção de diversos protocolos de consistência e mapeamentos entre processos e processadores, para fins de experimentação e ajuste, na busca de melhores desempenhos.

Este trabalho apresentou uma proposta que integra os modelos de memória compartilhada e troca de mensagens em único ambiente de desenvolvimento de programas paralelos e distribuídos. Como exemplificado, a disponibilidade dos dois modelos de programação permite que o programador faça opções visando simplificar a programação e/ou otimizar o desempenho de uma aplicação. P-RIO é um sistema baseado em objetos, centrado no paradigma de configuração, que separa a construção de uma aplicação da programação dos seus componentes, além de facilitar a adição de características operacionais a componentes específicos. Desta forma, o suporte para memória compartilhada embutido em P-RIO permite, no domínio da configuração, a seleção do protocolo de consistência a ser usado por determinado conjunto de módulos. Essa capacidade, simplifica a experimentação e o ajuste de aplicações, na busca por melhores desempenhos.

O suporte oferecido pelo ambiente permite a generalização, do exemplo apresentado na figura 5, para servidores com diversos métodos (módulos slave), bem como para suportar diversos clientes (módulos master). Esta característica, além de permitir o uso da abstração de memória compartilhada, pode ser utilizada para acelerar a execução de aplicações distribuídas através de acessos locais mais rápidos, em forma similar à proposta de Orca.

Nessa primeira etapa, uma implementação sobre uma rede de estações de trabalho foi realizada. Futuramente, pretende-se portar a metodologia usada por P-RIO a arquiteturas paralelas mais eficientes no suporte do modelo de memória compartilhada (e.g. IBM SP-2). Isso permitirá obter melhores desempenhos, em aplicações com granularidade relativamente fina, que os possíveis atualmente. Outros estudos, relacionados com a construção de aplicações distribuídas tolerantes a falhas, através do uso de memória compartilhada, também estão sendo realizados.

É um exemplo de interface de desenvolvimento?

Qual é o objetivo do MPI?

O que é Comunicação MPI?