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 pretende ser 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).). 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 normalmente también se indica). De manera similar a la forma en que el modelo de RAM ignora cuestiones prácticas, como el tiempo de acceso a la memoria caché frente a la memoria principal, el modelo de PRAM descuida cuestiones como la sincronización y la comunicación , pero proporciona cualquier cantidad de procesadores (depende del tamaño del problema). El costo del algoritmo, por ejemplo, se estima utilizando dos parámetros O (tiempo) y O (tiempo × procesador_número).
Los conflictos de lectura/escritura, comúnmente denominados interbloqueo al acceder a la misma ubicación de memoria compartida simultáneamente, se resuelven mediante una de las siguientes estrategias:
Aquí, E y C significan 'exclusivo' y 'concurrente' respectivamente. La lectura no provoca discrepancias, mientras que la escritura concurrente se define además como:
Se hacen varias suposiciones simplificadoras al considerar el desarrollo de algoritmos para PRAM. Ellos son:
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 el objetivo de 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 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 de 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 simultáneo; pero se pueden implementar en hardware o leer/escribir en los bloques internos de memoria estática de acceso aleatorio (SRAM) de una matriz de puertas programables en campo (FPGA), se puede hacer usando un algoritmo CRCW.