# Máquina de acesso randômico paralelo

Em ciência da computação, uma máquina de acesso randômico paralelo (PRAM - parallel random-access machine) é uma máquina abstrata de memória compartilhada. Como o seu nome indica, a PRAM foi concebida como a análoga de computação paralela da máquina de acesso randômico (RAM). Da mesma forma que a RAM é usada por projetistas de algoritmos sequenciais para modelar desempenho algorítmico (tais como complexidade de tempo), a PRAM é usada por projetistas de algoritmos paralelos para modelar o desempenho de algoritmos paralelos (tais como complexidade de tempo, onde o número de processadores assumido, normalmente, é também indicado). Da mesma forma que o modelo RAM negligencia questões práticas, tais como o tempo de acesso à memória cache versus memória principal, o medelo PRAM negligencia questões como sincronização e comunicação, mas fornece qualquer número de processadores (dependendo do tamanho do problema). Custo algorítmico, por exemplo, é estimado utilizando-se dois parâmetros O(tempo) e O(tempo × número de processadores).

## Conflitos de leitura/escrita

Conflitos de leitura/gravação em acessar simultaneamente o mesmo local de memória compartilhada são resolvidos por uma das estratégias abaixo:
* Leitura exclusiva gravação exclusiva (EREW - Exclusive read exclusive write)—toda célula de memória só pode ser lida ou escrita por um único processador de cada vez.
* Leitura concorrente gravação exclusiva (CREW - Concurrent read exclusive write)—múltiplos processadores podem ler uma mesma célula de memória mas somente um processador pode escrever de cada vez.
* Leitura exclusiva gravação concorrente (ERCW - Exclusive read concurrent write)—nunca considerada.
* Leitura concorrente gravação concorrente (CRCW - Concurrent read concurrent write)—múltiplos processadoress podem ler e escrever. Uma CRCW PRAM é as vezes chamada de máquina de acesso randômico concorrente.
Aqui, E e C significam 'exclusivo' e 'concorrente', respectivamente. A leitura é sempre igual, enquanto a escrita concorrente é definida como:
       Comum—todos os processadores escrevem o mesmo valor; do contrário a operação é ilegal
       Arbitraria—apenas uma escrita arbitraria tem sucesso, as outras cessam
       Prioritária—a classificação do processo indica qual vai escrever
Várias suposições são feitas no desenvolvimento de algoritmos para PRAM. São elas:
* Não existe um número limite de processadores na máquina.
* Qualquer local da memória pode ser acessado me maneira igual por todos os processadores.
* Não existe limite para a quantidade de memória compartilhada no sistema.
* Contenção de recursos é ausente.
* Os programas encritos nessas máquinas são, no geral, do tipo SIMD.
Algoritmos desse tipo são úteis para compreender os benefícios da concorrência, dividindo o problema original em subproblemas similares e resolvendo-os em paralelo. A introdução do modelo 'P-RAM' por James C. Wyllie na sua tese em 1979 tinha o objetivo de quantificar a análise de algoritmos paralelos de um modo análogo a máquina de Turing. A análise incidiu sobre um modelo MIMD de programação utilizando um modelo CREW mas mostrou que muitas variantes, incluindo a implementação de um modelo de CRCW e implementação em uma máquina SIMD, era possível com apenas um overhead constante.

## Implementação

Algoritmos PRAM não podem ser paralelizados com a combinação de CPU e dynamic random-access memory (DRAM) porque DRAM não permite acesso simultâneo; mas eles podem ser implementados em hardware ou lidos/gravados no blocos internos de uma memória estática de acesso aleatório (SRAM) de um circuito integrado FPGA, isso pode ser feito usando um algoritmo CRCW.
No entanto, o teste de relevância prática de algoritmos PRAM depende do seu modelo de custo fornecer uma abstração efetiva de algum computador; a estrutura desse computador pode ser muito diferente do modelo teórico. O conhecimento das camadas de software e hardware que precisam de ser inseridas está fora do escopo deste artigo. Mas, artigos tais como Vishkin (2011) demonstram como uma abstração do tipo PRAM pode ser suportada pelo paradigma XMT e artigos tais como Caragea & Vishkin (2011) demonstram que um algoritmo PRAM para o problema do fluxo máximo fornecer um forte ganho de velocidade em relação ao programa em série mais rápido para o mesmo problema.

## Código de exemplo

Este é um exemplo de código SystemVerilog que acha o máximo valor na matriz em apenas 2 ciclos de relógio. Ele compara todas as combinações dos elementos na matriz, no primeiro ciclo, e emerge o resultado no segundo clock. Ele usa memória CRCW; m[i] <= 1 e maxNo <= dados[i] são gravados simultaneamente. A concorrência faz com que não haja conflitos, pois o algoritmo garante que o mesmo valor é escrito para a mesma memória. Este código pode ser executado em hardware FPGA.