RAM paralela - Parallel RAM

En informática , una máquina paralela de acceso aleatorio ( RAM paralela o PRAM ) es una máquina abstracta de memoria compartida . Como su nombre lo indica, la PRAM está pensada como la analogía de computación paralela con la máquina de acceso aleatorio (RAM) (que no debe confundirse con la memoria de acceso aleatorio ). De la misma manera que los diseñadores de algoritmos secuenciales utilizan la RAM para modelar el rendimiento algorítmico (como la complejidad del tiempo), los diseñadores de algoritmos paralelos utilizan la PRAM para modelar el rendimiento algorítmico paralelo (como la complejidad del tiempo, donde el número de procesadores se asume típicamente también). De manera similar a la forma en que el modelo RAM ignora cuestiones prácticas, como el tiempo de acceso a la memoria caché frente a la memoria principal, el modelo PRAM ignora cuestiones como la sincronización y la comunicación , pero proporciona cualquier número de procesadores (que depende del tamaño del problema). El costo del algoritmo, por ejemplo, se estima usando dos parámetros O (tiempo) y O (tiempo × número de procesador).

Conflictos de lectura / escritura

Los conflictos de lectura / escritura, comúnmente denominados enclavamiento al acceder a la misma ubicación de memoria compartida simultáneamente, se resuelven mediante una de las siguientes estrategias:

  1. Escritura exclusiva de lectura exclusiva (EREW): solo un procesador a la vez puede leer o escribir en cada celda de memoria
  2. Escritura exclusiva de lectura simultánea (CREW): varios procesadores pueden leer una celda de memoria, pero solo uno puede escribir a la vez
  3. Escritura simultánea de lectura exclusiva (ERCW): nunca se considera
  4. Lectura concurrente escritura concurrente (CRCW): varios procesadores pueden leer y escribir. Una CRCW PRAM a veces se denomina máquina de acceso aleatorio concurrente .

Aquí, E y C significan 'exclusivo' y 'concurrente' respectivamente. La lectura no causa discrepancias, mientras que la escritura simultánea se define además como:

Común: todos los procesadores escriben el mismo valor; de lo contrario es ilegal
Arbitrario: solo un intento arbitrario tiene éxito, otros se retiran
Prioridad : el rango del procesador indica quién puede escribir
Otro tipo de operación de reducción de matriz como SUM, Logical AND o MAX.

Se hacen varios supuestos simplificadores al considerar el desarrollo de algoritmos para PRAM. Ellos son:

  1. No hay límite en la cantidad de procesadores en la máquina.
  2. Cualquier ubicación de la memoria es accesible de manera uniforme desde cualquier procesador.
  3. No hay límite en la cantidad de memoria compartida en el sistema.
  4. La contención de recursos está ausente.
  5. Los programas escritos en estas máquinas son, en general, de tipo SIMD .

Este tipo de algoritmos son útiles para comprender la explotación de la concurrencia, dividiendo el problema original en subproblemas similares y resolviéndolos en paralelo. La introducción del modelo formal 'P-RAM' en la tesis de Wyllie de 1979 tenía el objetivo de cuantificar el análisis de algoritmos paralelos de una manera análoga a la Máquina de Turing . El análisis se centró en un modelo de programación MIMD utilizando un modelo CREW, pero mostró que muchas variantes, incluida la implementación de un modelo CRCW y la implementación en una máquina SIMD, eran posibles con solo una sobrecarga constante.

Implementación

Los algoritmos PRAM no se pueden paralelizar con la combinación de CPU y memoria dinámica de acceso aleatorio (DRAM) porque DRAM no permite el acceso concurrente; pero se pueden implementar en hardware o leer / escribir en los bloques internos de memoria de acceso aleatorio estático (SRAM) de una matriz de puertas programables en campo (FPGA), se puede hacer usando un algoritmo CRCW.

Sin embargo, la prueba de relevancia práctica de los algoritmos PRAM (o RAM) depende de si su modelo de costos proporciona una abstracción efectiva de alguna computadora; la estructura de esa computadora puede ser bastante diferente al modelo abstracto. El conocimiento de las capas de software y hardware que deben insertarse está más allá del alcance de este artículo. Pero, artículos como Vishkin (2011) demuestran cómo una abstracción tipo PRAM puede ser respaldada por el paradigma explícito de subprocesos múltiples (XMT) y artículos como Caragea y Vishkin (2011) demuestran que un algoritmo PRAM para el problema de flujo máximo puede proporcionan fuertes aceleraciones en relación con el programa en serie más rápido para el mismo problema. El artículo Ghanim, Vishkin & Barua (2018) demostró que los algoritmos PRAM como están pueden lograr un rendimiento competitivo incluso sin ningún esfuerzo adicional para convertirlos en programas multiproceso en XMT.

Código de ejemplo

Este es un ejemplo de código SystemVerilog que encuentra el valor máximo en la matriz en solo 2 ciclos de reloj. Compara todas las combinaciones de los elementos de la matriz en el primer reloj y fusiona el resultado en el segundo reloj. Utiliza memoria CRCW; m[i] <= 1y maxNo <= data[i]se escriben al mismo tiempo. La simultaneidad no causa conflictos porque el algoritmo garantiza que se escribe el mismo valor en la misma memoria. Este código se puede ejecutar en 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 también

Referencias

  • Eppstein, David; Galil, Zvi (1988), "Técnicas algorítmicas paralelas para el cálculo combinatorio", Annu. Rev. Comput. Sci. , 3 : 233–283, doi : 10.1146 / annurev.cs.03.060188.001313
  • JaJa, Joseph (1992), Introducción a los algoritmos paralelos , Addison-Wesley, ISBN 0-201-54856-9
  • Karp, Richard M .; Ramachandran, Vijaya (1988), A Survey of Parallel Algorithms for Shared-Memory Machines , Universidad de California, Berkeley, Departamento de EECS, Tech. Representante UCB / CSD-88-408
  • Keller, Jörg; Christoph Keßler; Jesper Träff (2001). Programación práctica de PRAM . John Wiley e hijos. ISBN 0-471-35351-5.
  • Vishkin, Uzi (2009), Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 páginas (PDF) , Notas de clase de cursos sobre algoritmos paralelos impartidos desde 1992 en la Universidad de Maryland, College Park, la Universidad de Tel Aviv y la Technion
  • Vishkin, Uzi (2011), "Usando la abstracción simple para reinventar la computación para el paralelismo", Communications of the ACM , 54 : 75–85, doi : 10.1145 / 1866739.1866757
  • Caragea, George Constantin; Vishkin, Uzi (2011), "Breve anuncio: Mejores aceleraciones para el flujo máximo paralelo", Actas del 23º simposio de ACM sobre paralelismo en algoritmos y arquitecturas - 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

enlaces externos