RAM paralela - Parallel RAM

Na ciência da computação , uma máquina paralela de acesso aleatório ( RAM paralela ou PRAM ) é uma máquina abstrata de memória compartilhada . Como o próprio nome indica, a PRAM tem o objetivo de ser a analogia da computação paralela à máquina de acesso aleatório (RAM) (não deve ser confundida com a memória de acesso aleatório ). Da mesma forma que a RAM é usada por designers de algoritmos sequenciais para modelar o desempenho algorítmico (como complexidade de tempo), a PRAM é usada por designers de algoritmos paralelos para modelar o desempenho algorítmico paralelo (como complexidade de tempo, onde o número de processadores assumido normalmente também é declarado). Semelhante à maneira como o modelo de RAM negligencia questões práticas, como tempo de acesso à memória cache versus memória principal, o modelo PRAM negligencia questões como sincronização e comunicação , mas fornece qualquer número de processadores (dependente do tamanho do problema). O custo do algoritmo, por exemplo, é estimado usando dois parâmetros O (tempo) e O (tempo × número_processador).

Conflitos de leitura / gravação

Conflitos de leitura / gravação, comumente chamados de intertravamento no acesso ao mesmo local de memória compartilhada simultaneamente, são resolvidos por uma das seguintes estratégias:

  1. Leitura exclusiva, gravação exclusiva (EREW) - cada célula de memória pode ser lida ou gravada por apenas um processador por vez
  2. Leitura simultânea, gravação exclusiva (CREW) - vários processadores podem ler uma célula de memória, mas apenas um pode escrever por vez
  3. Leitura exclusiva e gravação simultânea (ERCW) - nunca considerada
  4. Leitura simultânea, gravação simultânea (CRCW) - vários processadores podem ler e gravar. Um CRCW PRAM às vezes é chamado de máquina de acesso aleatório simultâneo .

Aqui, E e C representam 'exclusivo' e 'simultâneo' respectivamente. A leitura não causa discrepâncias, enquanto a gravação simultânea é ainda definida como:

Comum - todos os processadores gravam o mesmo valor; caso contrário é ilegal
Arbitrário - apenas uma tentativa arbitrária é bem-sucedida, outras se aposentam
Prioridade - a classificação do processador indica quem pode escrever
Outro tipo de operação de redução de array , como SUM, Logical AND ou MAX.

Várias suposições de simplificação são feitas ao considerar o desenvolvimento de algoritmos para PRAM. Eles são:

  1. Não há limite para o número de processadores na máquina.
  2. Qualquer local de memória é uniformemente acessível a partir de qualquer processador.
  3. Não há limite para a quantidade de memória compartilhada no sistema.
  4. A contenção de recursos está ausente.
  5. Os programas escritos nessas máquinas são, em geral, do tipo SIMD .

Esses tipos de algoritmos são úteis para entender a exploração da simultaneidade, dividindo o problema original em subproblemas semelhantes e resolvendo-os em paralelo. A introdução do modelo formal 'P-RAM' na tese de Wyllie de 1979 teve o objetivo de quantificar a análise de algoritmos paralelos de uma forma análoga à Máquina de Turing . A análise se concentrou em um modelo MIMD de programação usando um modelo CREW, mas mostrou que muitas variantes, incluindo a implementação de um modelo CRCW e a implementação em uma máquina SIMD, eram possíveis apenas com sobrecarga constante.

Implementação

Os algoritmos PRAM não podem ser paralelizados com a combinação de CPU e memória dinâmica de acesso aleatório (DRAM) porque a DRAM não permite acesso simultâneo; mas eles podem ser implementados em hardware ou ler / escrever nos blocos internos de memória de acesso aleatório (SRAM) de uma matriz de portas programáveis ​​em campo (FPGA), isso pode ser feito usando um algoritmo CRCW.

No entanto, o teste de relevância prática de algoritmos PRAM (ou RAM) depende se seu modelo de custo fornece uma abstração eficaz de algum computador; a estrutura desse computador pode ser bem diferente do modelo abstrato. O conhecimento das camadas de software e hardware que precisam ser inseridas está além do escopo deste artigo. Mas, artigos como Vishkin (2011) demonstram como uma abstração semelhante a PRAM pode ser suportada pelo paradigma multi-threading explícito (XMT) e artigos como Caragea & Vishkin (2011) demonstram que um algoritmo PRAM para o problema de fluxo máximo pode fornecem acelerações fortes em relação ao programa serial mais rápido para o mesmo problema. O artigo Ghanim, Vishkin & Barua (2018) demonstrou que os algoritmos PRAM no estado em que se encontram podem atingir um desempenho competitivo, mesmo sem nenhum esforço adicional para convertê-los como programas multithread no XMT.

Código de exemplo

Este é um exemplo de código SystemVerilog que encontra o valor máximo na matriz em apenas 2 ciclos de clock. Ele compara todas as combinações dos elementos na matriz no primeiro relógio e mescla o resultado no segundo relógio. Ele usa memória CRCW; m[i] <= 1e maxNo <= data[i]são escritos simultaneamente. A simultaneidade não causa conflitos porque o algoritmo garante que o mesmo valor seja gravado na 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

Veja também

Referências

  • Eppstein, David; Galil, Zvi (1988), "Parallel algorítmicas técnicas para computação combinatória", 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). Programação prática de PRAM . John Wiley and Sons. ISBN 0-471-35351-5.
  • Vishkin, Uzi (2009), Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 páginas (PDF) , notas de aula de cursos sobre algoritmos paralelos ministrados desde 1992 na Universidade de Maryland, College Park, Universidade de Tel Aviv e o 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), "Anúncio breve: Melhores acelerações para fluxo máximo paralelo", Proceedings of the 23rd ACM symposium on Parallelism in algoritms and architectures - SPAA '11 , p. 131, doi : 10.1145 / 1989493.1989511 , ISBN 9781450307437
  • Ghanim, Fady; Vishkin, Uzi; Barua, Rajeev (2018), "Easy PRAM-based High-performance Parallel Programming with ICE", IEEE Transactions on Parallel and Distributed Systems , 29 (2): 377–390, doi : 10.1109 / TPDS.2017.2754376 , hdl : 1903 / 18521

links externos