El paralelismo de datos es la paralelización entre múltiples procesadores en entornos de computación paralela . Se centra en la distribución de los datos entre diferentes nodos, que operan sobre los datos en paralelo. Se puede aplicar a estructuras de datos regulares, como matrices y arreglos, trabajando sobre cada elemento en paralelo. Contrasta con el paralelismo de tareas , que es otra forma de paralelismo.
Un trabajo de datos en paralelo sobre una matriz de n elementos se puede dividir equitativamente entre todos los procesadores. Supongamos que queremos sumar todos los elementos de la matriz dada y que el tiempo para una sola operación de suma es Ta unidades de tiempo. En el caso de la ejecución secuencial, el tiempo que tarda el proceso será n ×Ta unidades de tiempo, ya que suma todos los elementos de una matriz. Por otro lado, si ejecutamos este trabajo como un trabajo de datos en paralelo sobre 4 procesadores, el tiempo que tarda se reduciría a ( n /4) × Ta + unidades de tiempo de sobrecarga de fusión. La ejecución en paralelo da como resultado una aceleración de 4 sobre la ejecución secuencial. Una cosa importante a tener en cuenta es que la localidad de las referencias de datos juega un papel importante en la evaluación del rendimiento de un modelo de programación paralela de datos. La localidad de los datos depende de los accesos a la memoria realizados por el programa, así como del tamaño de la memoria caché.
La explotación del concepto de paralelismo de datos comenzó en la década de 1960 con el desarrollo de la máquina de Solomon. [1] La máquina de Solomon, también llamada procesador vectorial , se desarrolló para acelerar la ejecución de operaciones matemáticas al trabajar en una gran matriz de datos (operando sobre múltiples datos en pasos de tiempo consecutivos). La concurrencia de operaciones de datos también se explotó al operar sobre múltiples datos al mismo tiempo utilizando una sola instrucción. Estos procesadores se denominaron "procesadores de matriz". [2] En la década de 1980, se introdujo el término [3] para describir este estilo de programación, que se utilizó ampliamente para programar máquinas de conexión en lenguajes de datos paralelos como C* . Hoy en día, el paralelismo de datos se ejemplifica mejor en las unidades de procesamiento gráfico (GPU), que utilizan ambas técnicas de operación en múltiples datos en el espacio y el tiempo utilizando una sola instrucción.
La mayoría de los hardware de paralelismo de datos solo admiten un número fijo de niveles paralelos, a menudo solo uno. Esto significa que dentro de una operación paralela no es posible iniciar más operaciones paralelas de forma recursiva y significa que los programadores no pueden hacer uso del paralelismo de hardware anidado. El lenguaje de programación NESL fue un esfuerzo temprano por implementar un modelo de programación de paralelismo de datos anidado en máquinas paralelas planas y, en particular, introdujo la transformación de aplanamiento que transforma el paralelismo de datos anidado en paralelismo de datos plano. Este trabajo fue continuado por otros lenguajes como Data Parallel Haskell y Futhark , aunque el paralelismo de datos anidado arbitrario no está ampliamente disponible en los lenguajes de programación de paralelismo de datos actuales.
En un sistema multiprocesador que ejecuta un único conjunto de instrucciones ( SIMD ), el paralelismo de datos se logra cuando cada procesador realiza la misma tarea sobre diferentes datos distribuidos. En algunas situaciones, un único hilo de ejecución controla las operaciones sobre todos los datos. En otras, diferentes hilos controlan la operación, pero ejecutan el mismo código.
Por ejemplo, considere la multiplicación y la suma de matrices de manera secuencial como se analiza en el ejemplo.
A continuación se muestra el pseudocódigo secuencial para la multiplicación y suma de dos matrices donde el resultado se almacena en la matriz C. El pseudocódigo para la multiplicación calcula el producto escalar de dos matrices A , B y almacena el resultado en la matriz de salida C.
Si los siguientes programas se ejecutaran secuencialmente, el tiempo necesario para calcular el resultado sería de (asumiendo que las longitudes de fila y columna de ambas matrices son n) y para la multiplicación y la suma respectivamente.
// Multiplicación de matrices para ( i = 0 ; i < longitud_fila_A ; i ++ ) { para ( k = 0 ; k < longitud_columna_B ; k ++ ) { suma = 0 ; para ( j = 0 ; j < longitud_columna_A ; j ++ ) { suma += A [ i ][ j ] * B [ j ][ k ]; } C [ i ][ k ] = suma ; } } // Adición de matrices para ( i = 0 ; i < n ; i ++ ) { c [ i ] = a [ i ] + b [ i ]; } Podemos aprovechar el paralelismo de datos en el código anterior para ejecutarlo más rápido, ya que la aritmética es independiente del bucle. La paralelización del código de multiplicación de matrices se logra utilizando OpenMP . Una directiva de OpenMP, "omp parallel for", indica al compilador que ejecute el código en el bucle for en paralelo. Para la multiplicación, podemos dividir las matrices A y B en bloques a lo largo de filas y columnas respectivamente. Esto nos permite calcular cada elemento de la matriz C individualmente, lo que hace que la tarea sea paralela. Por ejemplo: A[mxn] punto B [nxk] se puede finalizar en en lugar de cuando se ejecuta en paralelo utilizando procesadores m*k .
// Multiplicación de matrices en paralelo #pragma omp parallel for schedule(dynamic,1) collapse(2) para ( i = 0 ; i < longitud_fila_A ; i ++ ){ para ( k = 0 ; k < longitud_columna_B ; k ++ ){ suma = 0 ; para ( j = 0 ; j < longitud_columna_A ; j ++ ){ suma += A [ i ][ j ] * B [ j ][ k ]; } C [ i ][ k ] = suma ; } } Se puede observar en el ejemplo que se necesitarán muchos procesadores a medida que el tamaño de las matrices siga aumentando. Mantener bajo el tiempo de ejecución es la prioridad, pero a medida que aumenta el tamaño de la matriz, nos enfrentamos a otras limitaciones, como la complejidad de un sistema de este tipo y sus costos asociados. Por lo tanto, al limitar el número de procesadores en el sistema, aún podemos aplicar el mismo principio y dividir los datos en fragmentos más grandes para calcular el producto de dos matrices. [4]
Para la adición de matrices en una implementación de datos en paralelo, supongamos un sistema más modesto con dos unidades de procesamiento central (CPU) A y B: la CPU A podría agregar todos los elementos de la mitad superior de las matrices, mientras que la CPU B podría agregar todos los elementos de la mitad inferior de las matrices. Dado que los dos procesadores funcionan en paralelo, la tarea de realizar la adición de matrices tomaría la mitad del tiempo que realizar la misma operación en serie utilizando una sola CPU.
El programa expresado en pseudocódigo a continuación, que aplica alguna operación arbitraria, foo, en cada elemento de la matriz, dilustra el paralelismo de datos: [nb 1]
Si CPU = "a" entonces límite inferior := 1 límite superior := round(d.length / 2)De lo contrario, si CPU = "b" , entonces límite inferior := round(d.length / 2) + 1 límite superior := d.longitudpara i desde el límite inferior al límite superior en 1 hacer foo(d[i])
En un sistema SPMD ejecutado en un sistema de 2 procesadores, ambas CPU ejecutarán el código.
El paralelismo de datos enfatiza la naturaleza distribuida (paralela) de los datos, en contraposición al procesamiento (paralelismo de tareas). La mayoría de los programas reales se encuentran en algún punto intermedio entre el paralelismo de tareas y el paralelismo de datos.
El proceso de paralelización de un programa secuencial se puede dividir en cuatro pasos discretos. [5]
[6]
El paralelismo de datos y tareas se puede implementar simultáneamente combinándolos para la misma aplicación. Esto se denomina paralelismo mixto de datos y tareas. El paralelismo mixto requiere algoritmos de programación sofisticados y soporte de software. Es el mejor tipo de paralelismo cuando la comunicación es lenta y la cantidad de procesadores es grande. [7]
El paralelismo de datos y tareas mixtas tiene muchas aplicaciones. Se utiliza especialmente en las siguientes aplicaciones:
Actualmente existen diversos entornos de programación paralela de datos, los más utilizados son:
El paralelismo de datos se aplica en una variedad de campos, desde la física, la química, la biología, las ciencias de los materiales hasta el procesamiento de señales. Las ciencias implican el paralelismo de datos para simular modelos como la dinámica molecular [9] , el análisis de secuencias de datos genómicos [10] y otros fenómenos físicos. Las fuerzas impulsoras del procesamiento de señales para el paralelismo de datos son la codificación de video, el procesamiento de imágenes y gráficos, las comunicaciones inalámbricas [11] , por nombrar algunas.
d.lengthse evalúa como 1 y roundse redondea hacia cero [esto es solo un ejemplo, no hay requisitos sobre qué tipo de redondeo se utiliza]) darán lugar a que lower_limitsean mayores que upper_limit, se supone que el bucle saldrá inmediatamente (es decir, se producirán cero iteraciones) cuando esto suceda.