Máquina paralela de acesso aleatório
Na ciência da computação, uma máquina paralela de acesso aleatório , ou PRAM para abreviar , é uma máquina para analisar algoritmos paralelos . É uma máquina de registro que foi expandida para incluir a capacidade de processar comandos em paralelo. Como acontece com todos os modelos de máquina de registro, existem diferentes variações do PRAM. A ideia comum a todos os modelos é que vários registradores podem realizar cálculos ao mesmo tempo e armazenar o resultado em células de memória . O PRAM serve, inter alia. na teoria da complexidade para definir a classe NC de problemas decidíveis paralelos de forma eficiente .
Exemplo de uma realização
Mesmo que as máquinas de registro no sentido mais restrito suportem apenas um conjunto muito simples de instruções , máquinas de registro equivalentes podem ser definidas cujos programas podem ser especificados em uma linguagem de programação de alto nível . O processamento paralelo de comandos agora pode ser feito pela introdução de uma nova instrução semelhante a esta:
- para <condição> pardo <instruções>
pardo significa do em paralelo . Um exemplo:
- para i = 1 a 100 pardo x i : = 0
Esta instrução inicializa 100 locais de memória com o valor 0 ao mesmo tempo. Por exemplo, x pode ser considerado uma matriz com campos indexados de 1 a 100. A notação mais geral x i não inclui tais detalhes de implementação . O exemplo dado certamente não é de grande importância prática. Portanto, aqui está um exemplo mais útil que demonstra as capacidades de um poço PRAM:
É fornecida uma lista de n valores diferentes, que são armazenados sem classificação nas células de memória x 1 a x n . Procuramos aquele x i que contém o maior valor. Surpreendentemente, esta pesquisa pode ser realizada em paralelo em um PRIORITY-CRCW-PRAM (veja abaixo), que não requer ativação dos processadores, para n de qualquer tamanho em tempo constante :
for i=1 to n pardo
bi := 1
for i,j=1 to n pardo
if xj > xi
then
bi := 0
fi
for i=1 to n pardo
if bi = 1
then
m := i
fi
Após o segundo laço for, b i só tem o valor 1 se x i for o máximo. Todos os outros b j com j ≠ i têm o valor 0. O i com b i = 1 é, portanto, o índice procurado e pode ser encontrado após a execução do programa m. O máximo em uma lista não classificada de qualquer comprimento n pode, portanto, ser calculado com esforço constante, ou seja, no tempo O (1).
Diferentes modelos PRAM
PRAMs SIMD e MIMD
A instrução pardo descrita acima permite a execução simultânea de uma determinada instrução em diferentes variáveis dentro de um ciclo de tempo . Esses modelos paralelos são chamados de modelos de dados múltiplos de instrução única ou SIMD, para abreviar . Se diferentes comandos são permitidos em um ciclo de tempo, isso é chamado de modelo de dados múltiplos de instrução múltipla ( MIMD ). A instrução pardo é definida de maneira muito restrita para tal modelo.
Acesso simultâneo de leitura e gravação a células de memória idênticas
Deve ser definido se o acesso simultâneo de leitura e gravação a células de memória idênticas deve ser permitido ou não. O algoritmo acima para busca máxima requer ambos: dentro da segunda instrução pardo, células de memória idênticas x i são acessadas simultaneamente por diferentes processadores para compará-las umas com as outras, e a célula de memória b i é acessada simultaneamente para escrita . Você nem sempre deseja permitir tais liberdades. Portanto, é feita uma distinção:
- CRCW PRAM: leitura simultânea, gravação simultânea - acesso simultâneo de leitura e gravação possível
- CREW PRAM: leitura simultânea, gravação exclusiva - acesso de leitura simultânea, mas apenas permissão de acesso exclusivo de gravação
- EREW PRAM: Leitura Exclusiva, Gravação Exclusiva - somente acesso exclusivo de leitura e gravação permitido
No caso de um EREW, por exemplo, apenas um processador pode ter acesso de leitura ou gravação a uma célula de memória específica. Caso contrário, o programa será encerrado .
Acesso de gravação a CRCWs
No caso de um CRCW PRAM, ainda deve ser esclarecido o que deve acontecer no caso de acesso de gravação simultâneo quando diferentes processadores desejam gravar valores diferentes na célula de memória. Existem 3 modos:
- comum: apenas a escrita de valores idênticos é permitida.
- arbitrário: um valor aleatório é selecionado e escrito.
- prioridade: o processador com o endereço mais baixo recebe acesso de gravação.
Com algoritmos específicos, as diferentes variações de PRAM levam a diferentes complexidades no consumo de recursos. Por exemplo, o algoritmo acima mencionado para pesquisa máxima depende do acesso simultâneo de leitura e gravação, ou seja, em um CRCW PRAM, conforme descrito. Uma solução em tempo constante não seria possível em uma PRAM que não permite isso. Qual modelo PRAM você escolhe para uma investigação específica, portanto, depende dos objetivos de análise que você busca com ele.
