En informática , una máquina de acceso aleatorio en paralelo ( 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 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 manera similar a la forma en que el modelo RAM descuida cuestiones prácticas, como el tiempo de acceso a la memoria caché frente a la memoria principal, el modelo PRAM descuida 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 interbloqueos al acceder simultáneamente a la misma ubicación de memoria compartida, se resuelven mediante una de las siguientes estrategias:
Aquí, E y C significan "exclusivo" y "concurrente" respectivamente. La lectura no genera discrepancias, mientras que la escritura concurrente se define además como:
Al considerar el desarrollo de algoritmos para PRAM, se hacen varias suposiciones simplificadoras:
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 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 MIMD de programación 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.
Los algoritmos PRAM no se pueden paralelizar con la combinación de CPU y memoria de acceso aleatorio dinámico (DRAM) porque la DRAM no permite el acceso simultáneo a un solo banco (ni siquiera a diferentes direcciones en el banco); pero se pueden implementar en hardware o leer/escribir en los bloques de memoria de acceso aleatorio estático (SRAM) interna 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 costo proporciona una abstracción efectiva de alguna computadora; la estructura de esa computadora puede ser bastante diferente del 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 similar a PRAM puede ser apoyada por el paradigma de subprocesamiento múltiple explícito (XMT) y artículos como Caragea y Vishkin (2011) demuestran que un algoritmo PRAM para el problema de flujo máximo puede proporcionar fuertes aceleraciones en relación con el programa serial más rápido para el mismo problema. El artículo Ghanim, Vishkin y Barua (2018) demostraron que los algoritmos PRAM tal como están pueden lograr un rendimiento competitivo incluso sin ningún esfuerzo adicional para convertirlos en programas multiproceso en XMT.
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 ciclo de reloj y fusiona el resultado en el segundo. Utiliza memoria CRCW m[i] <= 1y maxNo <= data[i]se escriben simultáneamente. La concurrencia no causa conflictos porque el algoritmo garantiza que el mismo valor se escriba en la misma memoria. Este código se puede ejecutar en hardware FPGA .
módulo FindMax #( parámetro int len = 8 ) ( bit de entrada reloj , resetN , bit de entrada [ 7 : 0 ] datos [ len ], bit de salida [ 7 : 0 ] maxNo ); typedef enum bit [ 1 : 0 ] { COMPARAR , FUSIONAR , HECHO } Estado ; Estado estado ; bit m [ len ] ; int i , j ; always_ff @( posedge reloj , negedge resetN ) comenzar si ( ! resetN ) comenzar para ( i = 0 ; i < len ; i ++ ) m [ i ] <= 0 ; estado <= COMPARAR ; fin de lo contrario comienzo caso ( estado ) COMPARAR: comienzo para ( i = 0 ; i < len ; i ++ ) comienzo para ( j = 0 ; j < len ; j ++ ) comienzo si ( datos [ i ] < datos [ j ]) m [ i ] <= 1 ; fin fin estado <= FUSIONAR ; fin FUSIONAR: comienzo para ( i = 0 ; i < len ; i ++ ) comienzo si ( m [ i ] == 0 ) núm máx <= datos [ i ]; estado final <= HECHO ; fin caso final fin fin módulo final