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:
- Escritura exclusiva de lectura exclusiva (EREW): solo un procesador a la vez puede leer o escribir en cada celda de memoria
- Escritura exclusiva de lectura simultánea (CREW): varios procesadores pueden leer una celda de memoria, pero solo uno puede escribir a la vez
- Escritura simultánea de lectura exclusiva (ERCW): nunca se considera
- Lectura concurrente escritura concurrente (CRCW): varios procesadores pueden leer y escribir. Una CRCW PRAM a veces se denomina máquina de acceso aleatorio concurrente . [1]
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:
Se hacen varios supuestos simplificadores al considerar el desarrollo de algoritmos para PRAM. Ellos son:
- No hay límite en la cantidad de procesadores en la máquina.
- Cualquier ubicación de la memoria es accesible de manera uniforme desde cualquier procesador.
- No hay límite en la cantidad de memoria compartida en el sistema.
- La contención de recursos está ausente.
- 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 [2] tenía como objetivo 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] <= 1
y 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 .
módulo FindMax # ( parámetro int len = 8 ) ( bit de entrada de reloj , resetN , bit de entrada [ 7 : 0 ] datos [ len ], bit de salida [ 7 : 0 ] maxNo ); typedef enum bit [ 1 : 0 ] { COMPARE , FUSION , DONE } Estado ; Estado del estado ; 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 ; estado <= COMPARAR ; 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 ; estado final final <= FUSIÓN ; final FUSIÓN: comenzar para ( i = 0 ; i < len ; i ++ ) comenzar si ( m [ i ] == 0 ) maxNo <= datos [ i ]; estado final <= HECHO ; end endcase end end endmodule
Ver también
Referencias
- ^ Neil Immerman, Expresibilidad y complejidad paralela . Revista SIAM de Computación, vol. 18, no. 3, págs. 625-638, 1989.
- ^ Wyllie, James C.La complejidad de los cálculos paralelos , Tesis de doctorado, Departamento de Ciencias de la Computación, Universidad de Cornell
- Eppstein, David; Galil, Zvi (1988), "Técnicas algorítmicas paralelas para la computación combinatoria", 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
- PRAM prototipo de la Universidad de Saarland
- Prototipo PRAM-On-Chip de la Universidad de Maryland . Este prototipo busca poner muchos procesadores en paralelo y el tejido para interconectarlos en un solo chip
- XMTC: Programación similar a PRAM - Versión de software