stringtranslate.com

RAM paralela

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).

Conflictos de lectura/escritura

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:

  1. Lectura exclusiva y escritura exclusiva (EREW): cada celda de memoria puede ser leída o escrita por un solo procesador a la vez
  2. Lectura exclusiva y escritura simultánea (CREW): varios procesadores pueden leer una celda de memoria, pero solo uno puede escribir a la vez
  3. Lectura concurrente y escritura exclusiva (ERCW): generalmente nunca se considera porque en general no agrega más potencia [2]
  4. Lectura y escritura simultáneas (CRCW): varios procesadores pueden leer y escribir. A una PRAM CRCW a veces se la denomina máquina de acceso aleatorio concurrente . [3]

Aquí, E y C significan "exclusivo" y "concurrente" respectivamente. La lectura no genera 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 puede escribir
Otro tipo de operación de reducción de matriz como SUM, AND lógico o MAX.

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

  1. No hay límite en la cantidad de procesadores en la máquina.
  2. Cualquier ubicación de memoria es accesible uniformemente desde cualquier procesador.
  3. No hay límite en la cantidad de memoria compartida en el sistema.
  4. No existe 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 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.

Implementación

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 concurrente 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) internos 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.

Código de ejemplo

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        

Véase también

Referencias

  1. ^ Fortune, Steven; Wyllie, James (1 de mayo de 1978). "Paralelismo en máquinas de acceso aleatorio". Actas del décimo simposio anual de la ACM sobre teoría de la computación - STOC '78 . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 114-118. doi :10.1145/800133.804339. hdl : 1813/7454 . ISBN . 978-1-4503-7437-8.
  2. ^ MacKenzie, Philip D.; Ramachandran, Vijaya (6 de abril de 1998). "ERCW PRAMs y comunicación óptica". Ciencias de la Computación Teórica . 196 (1): 153–180. doi :10.1016/S0304-3975(97)00199-0. ISSN  0304-3975.
  3. ^ Neil Immerman, Expresibilidad y complejidad paralela . SIAM Journal on Computing, vol. 18, núm. 3, págs. 625-638, 1989.
  4. ^ Wyllie, James C. La complejidad de los cálculos paralelos, tesis doctoral, Departamento de Ciencias de la Computación, Universidad de Cornell

Enlaces externos