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:

1. 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.
2. 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.
3. Leitura exclusiva gravação concorrente (ERCW - Exclusive read concurrent write)—nunca considerada.
4. 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:

1. Não existe um número limite de processadores na máquina.
2. Qualquer local da memória  pode ser acessado me maneira igual por todos os processadores.
3. Não existe limite para a quantidade de memória compartilhada no sistema.
4. Contenção de recursos é ausente.
5. 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.

module FindMax #(parameter int len = 8)
                (input bit clock, resetN, input bit[7:0] data[len], output bit[7:0] maxNo);
    typedef enum bit[1:0] {COMPARE, MERGE, DONE} State;
                    
    State state;
    bit m[len];
    int i, j;
    
    always_ff @(posedge clock, negedge resetN) begin
        if (!resetN) begin
            for (i = 0; i < len; i++) m[i] <= 0;
            state <= COMPARE;
        end else begin
            case (state)
                COMPARE: begin
                    for (i = 0; i < len; i++) begin
                        for (j = 0; j < len; j++) begin
                            if (data[i] < data[j]) m[i] <= 1;
                        end
                    end
                    state <= MERGE;
                end
                
                MERGE: begin
                    for (i = 0; i < len; i++) begin
                        if (m[i] == 0) maxNo <= data[i];
                    end
                    state <= DONE;
                end
            endcase
        end
    end
endmodule

Ver também

• Analysis of PRAM algorithms
• Flynn's taxonomy
• Lock-free and wait-free algorithms
• Random-access machine
• Parallel programming model
• XMTC

Referências

• Eppstein, David; Galil, Zvi (1988), "Parallel algorithmic techniques for combinatorial computation", Annu. Rev. Comput. Sci. 3: 233–283, doi:10.1146/annurev.cs.03.060188.001313
• JaJa, Joseph (1992), An Introduction to Parallel Algorithms, Addison-Wesley, ISBN 0-201-54856-9
• Karp, Richard M.; Ramachandran, Vijaya (1988), "A Survey of Parallel Algorithms for Shared-Memory Machines", University of California, Berkeley, Department of EECS, Tech. Rep. UCB/CSD-88-408
• Keller, Jörg; Christoph Keßler; Jesper Träff (2001). Practical PRAM Programming. John Wiley and Sons. ISBN 0-471-35351-5.
• Vishkin, Uzi (2009), Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages (PDF), Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion
• Vishkin, Uzi (2011), "Using simple abstraction to reinvent computing for parallelism", Communications of the ACM 54: 75–85, doi:10.1145/1866739.1866757
• Caragea, George Constantin; Vishkin, Uzi (2011), "Better speedups for parallel max-flow", ACM SPAA, doi:10.1145/1989493.1989511

Ligações externas

• Saarland University's prototype PRAM
• Universidade De Maryland PRAM-On-Chip protótipo. Este protótipo pretende colocar muitos processadores paralelos, e o tecido para a inter-conexão-las em um único chip
• XMTC: CARRINHO-como Programação (versão de Software