Máquinas paralelas de acesso aleatório

Parallel Random Access Machines (PRAM)é um modelo, que é considerado para a maioria dos algoritmos paralelos. Aqui, vários processadores são anexados a um único bloco de memória. Um modelo PRAM contém -

• Um conjunto de processadores semelhantes.

• Todos os processadores compartilham uma unidade de memória comum. Os processadores podem se comunicar entre si apenas por meio da memória compartilhada.

• Uma unidade de acesso à memória (MAU) conecta os processadores com a única memória compartilhada.

Aqui, n número de processadores podem realizar operações independentes em nnúmero de dados em uma determinada unidade de tempo. Isso pode resultar no acesso simultâneo do mesmo local de memória por diferentes processadores.

Para resolver este problema, as seguintes restrições foram aplicadas no modelo PRAM -

• Exclusive Read Exclusive Write (EREW) - Aqui, dois processadores não têm permissão para ler ou gravar no mesmo local de memória ao mesmo tempo.

• Exclusive Read Concurrent Write (ERCW) - Aqui, dois processadores não têm permissão para ler no mesmo local da memória ao mesmo tempo, mas podem gravar no mesmo local da memória ao mesmo tempo.

• Concurrent Read Exclusive Write (CREW) - Aqui, todos os processadores têm permissão para ler no mesmo local da memória ao mesmo tempo, mas não têm permissão para gravar no mesmo local da memória ao mesmo tempo.

• Concurrent Read Concurrent Write (CRCW) - Todos os processadores podem ler ou gravar no mesmo local de memória ao mesmo tempo.

Existem muitos métodos para implementar o modelo PRAM, mas os mais proeminentes são -

• Modelo de memória compartilhada
• Modelo de passagem de mensagens
• Modelo paralelo de dados

Modelo de Memória Compartilhada

A memória compartilhada enfatiza control parallelism do que em data parallelism. No modelo de memória compartilhada, vários processos são executados em diferentes processadores de forma independente, mas eles compartilham um espaço de memória comum. Devido a qualquer atividade do processador, se houver alguma alteração em qualquer local da memória, ela será visível para o restante dos processadores.

Como vários processadores acessam o mesmo local de memória, pode acontecer que, em qualquer ponto específico do tempo, mais de um processador esteja acessando o mesmo local de memória. Suponha que um esteja lendo aquele local e o outro esteja escrevendo naquele local. Isso pode criar confusão. Para evitar isso, algum mecanismo de controle, comolock / semaphore, é implementado para garantir a exclusão mútua.

A programação de memória compartilhada foi implementada no seguinte -

• Thread libraries- A biblioteca de threads permite vários threads de controle que são executados simultaneamente no mesmo local de memória. A biblioteca de threads fornece uma interface que suporta multithreading por meio de uma biblioteca de sub-rotinas. Ele contém sub-rotinas para

  • Criação e destruição de threads
  • Agendamento de execução de thread
  • passando dados e mensagens entre conversas
  • salvar e restaurar contextos de discussão

Exemplos de bibliotecas de thread incluem - threads SolarisTM para Solaris, threads POSIX conforme implementado no Linux, threads Win32 disponíveis no Windows NT e Windows 2000 e threads JavaTM como parte do JavaTM Development Kit (JDK) padrão.

• Distributed Shared Memory (DSM) Systems- Os sistemas DSM criam uma abstração de memória compartilhada em arquitetura fracamente acoplada para implementar a programação de memória compartilhada sem suporte de hardware. Eles implementam bibliotecas padrão e usam os recursos avançados de gerenciamento de memória no nível do usuário, presentes nos sistemas operacionais modernos. Os exemplos incluem Tread Marks System, Munin, IVY, Shasta, Brazos e Cashmere.

• Program Annotation Packages- Isso é implementado nas arquiteturas com características uniformes de acesso à memória. O exemplo mais notável de pacotes de anotação de programa é o OpenMP. OpenMP implementa paralelismo funcional. Ele se concentra principalmente na paralelização de loops.

O conceito de memória compartilhada fornece um controle de baixo nível do sistema de memória compartilhada, mas tende a ser tedioso e errôneo. É mais aplicável à programação do sistema do que à programação do aplicativo.

Méritos da Programação de Memória Compartilhada

• O espaço de endereçamento global oferece uma abordagem de programação amigável para a memória.

• Devido à proximidade da memória com a CPU, o compartilhamento de dados entre os processos é rápido e uniforme.

• Não há necessidade de especificar distintamente a comunicação de dados entre os processos.

• A sobrecarga de comunicação do processo é insignificante.

• É muito fácil aprender.

Deméritos da programação de memória compartilhada

• Não é portátil.
• Gerenciar a localidade dos dados é muito difícil.

Modelo de passagem de mensagem

A passagem de mensagens é a abordagem de programação paralela mais comumente usada em sistemas de memória distribuída. Aqui, o programador deve determinar o paralelismo. Neste modelo, todos os processadores possuem sua própria unidade de memória local e trocam dados por meio de uma rede de comunicação.

Os processadores usam bibliotecas de passagem de mensagens para comunicação entre si. Junto com os dados sendo enviados, a mensagem contém os seguintes componentes -

• O endereço do processador do qual a mensagem está sendo enviada;

• Endereço inicial da localização da memória dos dados no processador de envio;

• Tipo de dados do envio de dados;

• Tamanho dos dados de envio;

• O endereço do processador para o qual a mensagem está sendo enviada;

• Endereço inicial da localização da memória para os dados no processador receptor.

Os processadores podem se comunicar uns com os outros por qualquer um dos seguintes métodos -

• Comunicação Ponto a Ponto
• Comunicação Coletiva
• Interface de passagem de mensagens

Comunicação Ponto a Ponto

A comunicação ponto a ponto é a forma mais simples de transmissão de mensagens. Aqui, uma mensagem pode ser enviada do processador de envio para um processador de recebimento por qualquer um dos seguintes modos de transferência -

• Synchronous mode - A próxima mensagem é enviada somente após o recebimento de uma confirmação de que sua mensagem anterior foi entregue, para manter a seqüência da mensagem.

• Asynchronous mode - Para enviar a próxima mensagem, não é necessário o recebimento da confirmação de entrega da mensagem anterior.

Comunicação Coletiva

A comunicação coletiva envolve mais de dois processadores para a passagem de mensagens. Os seguintes modos permitem comunicações coletivas -

• Barrier - O modo de barreira é possível se todos os processadores incluídos nas comunicações executam um bock particular (conhecido como barrier block) para passagem de mensagens.

• Broadcast - A transmissão é de dois tipos -

  • One-to-all - Aqui, um processador com uma única operação envia a mesma mensagem para todos os outros processadores.

  • All-to-all - Aqui, todos os processadores enviam mensagens para todos os outros processadores.

As mensagens transmitidas podem ser de três tipos -

• Personalized - Mensagens exclusivas são enviadas para todos os outros processadores de destino.

• Non-personalized - Todos os processadores de destino recebem a mesma mensagem.

• Reduction - Na transmissão de redução, um processador do grupo coleta todas as mensagens de todos os outros processadores do grupo e as combina em uma única mensagem que todos os outros processadores do grupo podem acessar.

Méritos da transmissão de mensagens

• Fornece controle de baixo nível de paralelismo;
• É portátil;
• Menos sujeito a erros;
• Menos sobrecarga na sincronização paralela e distribuição de dados.

Deméritos da passagem de mensagens

• Em comparação com o código de memória compartilhada paralela, o código de passagem de mensagens geralmente precisa de mais sobrecarga de software.

Bibliotecas de passagem de mensagens

Existem muitas bibliotecas de passagem de mensagens. Aqui, discutiremos duas das bibliotecas de passagem de mensagens mais usadas -

• Interface de passagem de mensagens (MPI)
• Máquina Virtual Paralela (PVM)

Interface de passagem de mensagens (MPI)

É um padrão universal para fornecer comunicação entre todos os processos concorrentes em um sistema de memória distribuída. A maioria das plataformas de computação paralela comumente usadas fornece pelo menos uma implementação de interface de passagem de mensagem. Foi implementado como uma coleção de funções predefinidas chamadaslibrary e podem ser chamados de linguagens como C, C ++, Fortran, etc. MPIs são rápidos e portáteis em comparação com outras bibliotecas de passagem de mensagens.

Merits of Message Passing Interface

• É executado apenas em arquiteturas de memória compartilhada ou arquiteturas de memória distribuída;

• Cada processador tem suas próprias variáveis ​​locais;

• Em comparação com grandes computadores com memória compartilhada, os computadores com memória distribuída são mais baratos.

Demerits of Message Passing Interface

• Mais alterações de programação são necessárias para o algoritmo paralelo;
• Às vezes é difícil depurar; e
• Não funciona bem na rede de comunicação entre os nós.

Máquina Virtual Paralela (PVM)

PVM é um sistema de passagem de mensagens portátil, projetado para conectar máquinas host heterogêneas separadas para formar uma única máquina virtual. É um único recurso de computação paralela gerenciável. Grandes problemas computacionais como estudos de supercondutividade, simulações de dinâmica molecular e algoritmos de matriz podem ser resolvidos de forma mais econômica usando a memória e o poder agregado de muitos computadores. Ele gerencia todo o roteamento de mensagens, conversão de dados, agendamento de tarefas na rede de arquiteturas de computador incompatíveis.

Features of PVM

• Muito fácil de instalar e configurar;
• Vários usuários podem usar o PVM ao mesmo tempo;
• Um usuário pode executar vários aplicativos;
• É um pacote pequeno;
• Suporta C, C ++, Fortran;
• Para uma determinada execução de um programa PVM, os usuários podem selecionar o grupo de máquinas;
• É um modelo de transmissão de mensagens,
• Computação baseada em processo;
• Suporta arquitetura heterogênea.

Programação paralela de dados

O principal foco do modelo de programação paralela de dados é executar operações em um conjunto de dados simultaneamente. O conjunto de dados é organizado em alguma estrutura como uma matriz, hipercubo, etc. Os processadores executam operações coletivamente na mesma estrutura de dados. Cada tarefa é executada em uma partição diferente da mesma estrutura de dados.

É restritivo, pois nem todos os algoritmos podem ser especificados em termos de paralelismo de dados. Esta é a razão pela qual o paralelismo de dados não é universal.

Linguagens paralelas de dados ajudam a especificar a decomposição de dados e o mapeamento para os processadores. Também inclui instruções de distribuição de dados que permitem ao programador ter controle sobre os dados - por exemplo, quais dados irão para qual processador - para reduzir a quantidade de comunicação dentro dos processadores.