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, el PRAM está diseñado 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 RAM 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 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 (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).
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:
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. 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 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 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.
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.