Memoria RAM paralela

En informática , una máquina de acceso aleatorio paralela ( RAM paralela o PRAM ) es una máquina abstracta de memoria compartida . Como su nombre indica, la PRAM se concibe como la analogía en computación paralela de la máquina de acceso aleatorio (RAM) (que no debe confundirse con la memoria de acceso aleatorio ). ^{[ 1 ]} De la misma manera que los diseñadores de algoritmos secuenciales utilizan la RAM para modelar el rendimiento algorítmico (como la complejidad temporal), los diseñadores de algoritmos paralelos utilizan la PRAM para modelar el rendimiento algorítmico paralelo (como la complejidad temporal, donde normalmente también se indica el número de procesadores asumidos). De forma similar a como 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 (dependiente del tamaño del problema). El coste del algoritmo, por ejemplo, se estima utilizando dos parámetros: O(tiempo) y O(tiempo × número_de_procesadores).

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

1. Lectura exclusiva, escritura exclusiva (EREW): cada celda de memoria solo puede ser leída o escrita por un procesador a la vez.
2. Lectura y escritura exclusiva concurrente (CREW): varios procesadores pueden leer una celda de memoria, pero solo uno puede escribir a la vez.
3. Escritura concurrente de lectura exclusiva (ERCW): casi nunca se considera porque casi nunca agrega más potencia ^{[ 2 ]}
4. Lectura y escritura concurrentes (CRCW): varios procesadores pueden leer y escribir. Una PRAM CRCW a veces se denomina máquina de acceso aleatorio concurrente . ^{[ 3 ]}

Aquí, E y C significan "exclusivo" y "concurrente" respectivamente. La lectura no causa discrepancias, mientras que la escritura concurrente 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, los demás se retiran.

Prioridad : el rango del procesador indica quién tiene derecho a escribir.

Otro tipo de operación de reducción de matrices como SUMA, AND lógico o MÁXIMO.

Al considerar el desarrollo de algoritmos para PRAM, se hacen varias suposiciones simplificadoras. Estas son:

1. No existe límite en el número de procesadores de la máquina.
2. Cualquier ubicación de memoria es accesible de forma uniforme desde cualquier procesador.
3. No existe límite en la cantidad de memoria compartida del sistema.
4. No hay contención de recursos .
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 ^{[ 4 ]} tenía como objetivo cuantificar el análisis de algoritmos paralelos de forma análoga a la máquina de Turing . El análisis se centró en un modelo MIMD de programación utilizando un modelo CREW, pero demostró que muchas variantes, incluyendo la implementación de un modelo CRCW y la implementación en una máquina SIMD, eran posibles con una sobrecarga constante.

Los algoritmos PRAM no se pueden paralelizar con la combinación de CPU y memoria de acceso aleatorio dinámica (DRAM) porque la DRAM no permite el acceso concurrente a un solo banco (ni siquiera a diferentes direcciones dentro del banco); pero se pueden implementar en hardware o leer/escribir en los bloques internos de memoria de acceso aleatorio estática (SRAM) de una matriz de puertas programables en campo (FPGA), lo que se puede hacer utilizando un algoritmo CRCW.

Sin embargo, la relevancia práctica de los algoritmos PRAM (o RAM) depende de si su modelo de costos proporciona una abstracción efectiva de algún ordenador; la estructura de dicho ordenador puede ser muy diferente a la del modelo abstracto. El conocimiento de las capas de software y hardware que deben incorporarse está fuera del alcance de este artículo. No obstante, artículos como el de Vishkin (2011) demuestran cómo una abstracción tipo PRAM puede ser soportada por el paradigma de multihilo explícito (XMT), y artículos como el de Caragea y Vishkin (2011) demuestran que un algoritmo PRAM para el problema del flujo máximo puede proporcionar importantes aceleraciones en comparación con el programa serial más rápido para el mismo problema. El artículo de Ghanim, Vishkin y Barua (2018) demostró que los algoritmos PRAM, tal como están, pueden alcanzar un rendimiento competitivo incluso sin ningún esfuerzo adicional para convertirlos en programas multihilo en XMT.

Este es un ejemplo de código SystemVerilog que encuentra el valor máximo en el array en solo 2 ciclos de reloj. Compara todas las combinaciones de los elementos del array en el primer ciclo y combina el resultado en el segundo. Utiliza memoria CRCW m[i] <= 1y maxNo <= data[i]se escribe de forma concurrente. La concurrencia evita conflictos, ya que el algoritmo garantiza que se escriba 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 clock , resetN , bit de entrada [ 7 : 0 ] datos [ len ], bit de salida [ 7 : 0 ] maxNo ); typedef enum bit [ 1 : 0 ] { COMPARE , MERGE , DONE } Estado ; Estado 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 <= COMPARE ; fin si no inicio caso ( estado ) COMPARAR: inicio para ( i = 0 ; i < len ; i ++ ) inicio para ( j = 0 ; j < len ; j ++ ) inicio si ( datos [ i ] < datos [ j ]) m [ i ] <= 1 ; fin fin estado <= FUSIONAR ; fin FUSIONAR: inicio para ( i = 0 ; i < len ; i ++ ) inicio si ( m [ i ] == 0 ) maxNo <= datos[ i ]; estado final <= HECHO ; fin fin caso fin fin fin módulo

• Análisis de algoritmos PRAM
• La taxonomía de Flynn
• Algoritmos sin bloqueo y sin espera
• Máquina de acceso aleatorio
• Modelo de programación paralela
• XMTC
• Memoria externa paralela (Modelo)

• 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), Un estudio de algoritmos paralelos para máquinas de memoria compartida , Universidad de California, Berkeley, Departamento de EECS, Informe técnico UCB/CSD-88-408
• Keller, Jörg; Christoph Keßler; Jesper Traff (2001). Programación práctica de PRAM . John Wiley e hijos. ISBN 0-471-35351-5.
• Vishkin, Uzi (2009), Pensando en paralelo: algunos algoritmos y técnicas básicas de procesamiento paralelo de datos, 104 páginas (PDF) , Apuntes de clase de cursos sobre algoritmos paralelos impartidos desde 1992 en la Universidad de Maryland, College Park, la Universidad de Tel Aviv y el 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), "Anuncio breve: Mejores aceleraciones para el flujo máximo paralelo", Actas del 23.er simposio de la ACM sobre paralelismo en algoritmos y arquitecturas - SPAA '11 , pág.  131, doi : 10.1145/1989493.1989511 , ISBN 9781450307437, S2CID 5511743 
• Ghanim, Fady; Vishkin, Uzi; Barua, Rajeev (2018), "Programación paralela de alto rendimiento basada en PRAM con ICE", IEEE Transactions on Parallel and Distributed Systems , 29 (2): 377–390 , doi : 10.1109/TPDS.2017.2754376 , hdl : 1903/18521

• Prototipo PRAM de la Universidad de Saarland. Archivado el 3 de marzo de 2016 en Wayback Machine.
• Prototipo PRAM-On-Chip de la Universidad de Maryland . Este prototipo busca integrar muchos procesadores paralelos y la arquitectura para interconectarlos en un solo chip.
• XMTC: Programación tipo PRAM - Versión de software