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 una analogía de la computación paralela a 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 del tiempo), los diseñadores de algoritmos paralelos utilizan la PRAM para modelar el rendimiento algorítmico paralelo (como la complejidad del tiempo, donde la normalmente también se indica el número de procesadores asumido). De manera similar a la forma en que el modelo RAM ignora cuestiones prácticas, como el tiempo de acceso a la memoria caché versus 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 costo del algoritmo, por ejemplo, se estima utilizando dos parámetros O(tiempo) y O(tiempo × número_procesador).
Los conflictos de lectura/escritura, comúnmente denominados interbloqueo 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 causa 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, dividir el problema original en subproblemas similares y resolverlos 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 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 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 internos de memoria estática de acceso aleatorio (SRAM) de una matriz de puertas programables en campo (FPGA), esto 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 a la del modelo abstracto. El conocimiento de las capas de software y hardware que deben insertarse está fuera del alcance de este artículo. Pero artículos como Vishkin (2011) demuestran cómo una abstracción similar a 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 y Barua (2018) demostró 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 reloj y fusiona el resultado en el segundo reloj. Utiliza memoria CRCW; m[i] <= 1y maxNo <= data[i]se escriben al mismo tiempo. 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 ) ( reloj de bits de entrada , reinicioN , bit de entrada [ 7 : 0 ] datos [ len ], bit de salida [ 7 : 0 ] maxNo ); bit de enumeración typedef [ 1 : 0 ] { COMPARAR , FUSIONAR , HECHO } Estado ; Estado estado ; poco m [ len ]; int yo , j ; siempre_ff @( reloj posedge , reinicio negedgeN ) comienza si ( ! resetN ) comienza para ( i = 0 ; i < len ; i ++ ) m [ i ] <= 0 ; estado <= COMPARAR ; fin si no comenzar caso ( estado ) COMPARAR: comenzar para ( i = 0 ; i < len ; i ++ ) comenzar para ( j = 0 ; j < len ; j ++ ) comenzar si ( datos [ i ] < datos [ j ]) metro [ yo ] <= 1 ; final estado final <= FUSIONAR ; finalizar FUSIÓN: comenzar para ( i = 0 ; i < len ; i ++ ) comenzar si ( m [ i ] == 0 ) maxNo <= datos [ i ]; estado final <= HECHO ; final extremo final extremo final módulo final