paralelismo de datos

El paralelismo de datos es la paralelización en múltiples procesadores en entornos de computación paralela . Se centra en distribuir los datos entre diferentes nodos, que operan sobre ellos en paralelo. Se puede aplicar a estructuras de datos regulares como arreglos y matrices, trabajando con cada elemento en paralelo. Se diferencia del paralelismo de tareas , que es otra forma de paralelismo.

Una tarea de procesamiento paralelo de datos en un array de n elementos se puede dividir equitativamente entre todos los procesadores. Supongamos que queremos sumar todos los elementos del array 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 tardará el proceso será de n × Ta unidades de tiempo, ya que suma todos los elementos del array. Por otro lado, si ejecutamos esta tarea como una tarea de procesamiento paralelo de datos en 4 procesadores, el tiempo se reduciría a ( n /4) × Ta + unidades de tiempo de sobrecarga de fusión. La ejecución paralela resulta en una aceleración de 4 con respecto a la ejecución secuencial. La localidad de las referencias de datos juega un papel importante en la evaluación del rendimiento de un modelo de programación de procesamiento paralelo de datos. La localidad de los datos depende de los accesos a memoria realizados por el programa, así como del tamaño de la caché.

La explotación del concepto de paralelismo de datos comenzó en la década de 1960 con el desarrollo de la máquina Solomon. ^{[ 1 ]} La máquina Solomon, también llamada procesador vectorial , se desarrolló para acelerar el rendimiento de las operaciones matemáticas trabajando con una gran matriz de datos (operando con múltiples datos en pasos de tiempo consecutivos). La concurrencia de operaciones de datos también se explotó operando con múltiples datos al mismo tiempo usando 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 usó ampliamente para programar Connection Machines en lenguajes de paralelismo de datos 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 operar con múltiples datos en el espacio y el tiempo usando una sola instrucción.

La mayoría del hardware de procesamiento paralelo de datos solo admite un número fijo de niveles de paralelismo, 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 que los programadores no pueden aprovechar el paralelismo de hardware anidado. El lenguaje de programación NESL fue un primer intento de implementar un modelo de programación de paralelismo de datos anidado en máquinas paralelas planas, e introdujo, en particular, la transformación de aplanamiento que convierte 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 datos distribuidos diferentes. En algunos casos, un único hilo de ejecución controla las operaciones sobre todos los datos. En otros, diferentes hilos controlan la operación, pero ejecutan el mismo código.

Por ejemplo, consideremos la multiplicación y la suma de matrices de forma secuencial, como se explica 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 y B , y almacena el resultado en la matriz de salida C.

Si los siguientes programas se ejecutaran secuencialmente, el tiempo que se tardaría en calcular el resultado sería de${\displaystyle O(n^{3})}$(suponiendo que las longitudes de fila y columna de ambas matrices son n) y${\displaystyle O(n)}$para la multiplicación y la suma respectivamente.

// Multiplicación de matrices for ( int i = 0 ; i < A . rowLength (); i ++ ) { for ( int k = 0 ; k < B . columnLength (); k ++ ) { int sum = 0 ; for ( int j = 0 ; j < A . columnLength (); j ++ ) { sum += A [ i ][ j ] * B [ j ][ k ] ; } C [ i ][ k ] = sum ; } }

// Adición de arreglos for ( int i = 0 ; i < c . size (); 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 mediante OpenMP . Una directiva de OpenMP, "omp parallel for", indica al compilador que ejecute el código del 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, haciendo así la tarea paralela. Por ejemplo: A[mxn] punto B[nxk] se puede terminar en${\displaystyle O(n)}$en lugar de${\displaystyle O(m*n*k)}$cuando se ejecuta en paralelo utilizando procesadores m*k .

// Multiplicación de matrices en paralelo #pragma omp parallel for schedule ( dynamic , 1 ) collapse ( 2 ) for ( int i = 0 ; i < A.rowLength (); i ++ ) { for ( int k = 0 ; k < B.columnLength ( ); k ++ ) { int sum = 0 ; for ( int j = 0 ; j < A.columnLength ( ) ; j ++ ) { sum += A [ i ][ j ] * B [ j ] [ k ] ; } C [ i ] [ k ] = sum ; } }

Como se puede observar en el ejemplo, se requerirán muchos procesadores a medida que aumente el tamaño de las matrices. Si bien la prioridad es minimizar el tiempo de ejecución, al incrementarse el tamaño de la matriz, surgen otras limitaciones, como la complejidad del sistema y sus costos asociados. Por lo tanto, limitando el número de procesadores, podemos aplicar el mismo principio y dividir los datos en fragmentos más grandes para calcular el producto de dos matrices. ^{[ 4 ]}

Para la suma de arreglos en una implementación de procesamiento paralelo de datos, supongamos un sistema más sencillo con dos unidades centrales de procesamiento (CPU) A y B. La CPU A podría sumar todos los elementos de la mitad superior de los arreglos, mientras que la CPU B podría sumar todos los elementos de la mitad inferior. Dado que ambos procesadores trabajan en paralelo, la suma de arreglos tardaría la mitad del tiempo que si se realizara la misma operación en serie con una sola CPU.

El programa expresado en pseudocódigo a continuación —que aplica alguna operación arbitraria, foo, a cada elemento de la matriz— dilustra el paralelismo de datos: ^{[ nb 1 ]}

si CPU = "a" entonces límite_inferior := 1 límite_superior := redondeo(d.longitud / 2) de lo contrario si CPU = "b" entonces límite_inferior := redondeo(d.longitud / 2) + 1 límite_superior := d.longitud para i desde límite_inferior hasta 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 sitúan en algún punto intermedio entre el paralelismo de tareas y el paralelismo de datos.

El proceso de paralelizar un programa secuencial se puede dividir en cuatro pasos discretos. ^{[ 5 ]}

^{[ 6 ]}

El paralelismo de datos y tareas puede implementarse simultáneamente combinándolos para la misma aplicación. Esto se denomina paralelismo mixto de datos y tareas. El paralelismo mixto requiere algoritmos de planificación sofisticados y soporte de software. Es el mejor tipo de paralelismo cuando la comunicación es lenta y el número de procesadores es elevado. ^{[ 7 ]}

El paralelismo de tareas y datos mixtos tiene muchas aplicaciones. Se utiliza particularmente en las siguientes aplicaciones:

1. El paralelismo de datos y tareas se aplica en la modelización climática global. Los cálculos paralelos de grandes conjuntos de datos se realizan mediante la creación de cuadrículas de datos que representan la atmósfera y los océanos de la Tierra, y el paralelismo de tareas se emplea para simular el funcionamiento y el modelo de los procesos físicos.
2. En la simulación de circuitos basada en temporización , los datos se dividen entre diferentes subcircuitos y el paralelismo se logra mediante la orquestación de las tareas.

Actualmente se dispone de una variedad de entornos de programación paralela de datos, entre los que destacan los siguientes:

1. Interfaz de paso de mensajes : Es una interfaz de programación de paso de mensajes multiplataforma para computadoras paralelas. Define la semántica de las funciones de la biblioteca para permitir a los usuarios escribir programas portátiles de paso de mensajes en C, C++ y Fortran.
2. OpenMP : ^{[ 8 ]} Es una interfaz de programación de aplicaciones (API) que admite modelos de programación de memoria compartida en múltiples plataformas de sistemas multiprocesador. Desde la versión 4.5, OpenMP también puede dirigirse a dispositivos distintos de las CPU típicas. Puede programar FPGA, DSP, GPU y más. No se limita a las GPU como OpenACC.
3. CUDA y OpenACC : CUDA y OpenACC (respectivamente) son plataformas API de computación paralela diseñadas para permitir que un ingeniero de software utilice las unidades de cálculo de las GPU para el procesamiento de propósito general.
4. Threading Building Blocks y RaftLib : Ambos son entornos de programación de código abierto que permiten el paralelismo mixto de datos y tareas en entornos C/C++ a través de recursos heterogéneos.

El paralelismo de datos encuentra aplicaciones en diversos campos, desde la física, la química y la biología hasta la ciencia de los materiales y el procesamiento de señales. Las ciencias lo emplean 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. Entre los principales impulsores del paralelismo de datos en el procesamiento de señales se encuentran la codificación de vídeo, el procesamiento de imágenes y gráficos, y las comunicaciones inalámbricas ^{[ 11 ]} , por mencionar algunos.

• Mensaje activo
• Paralelismo a nivel de instrucción
• Modelo de programación paralela
• Suma de prefijo
• Paralelismo escalable
• Escaneo segmentado
• paralelismo a nivel de hilo

• Hillis, W. Daniel y Steele, Guy L. , Algoritmos de procesamiento paralelo de datos , Communications of the ACM, diciembre de 1986
• Blelloch, Guy E., Modelos vectoriales para computación paralela de datos, MIT Press, 1990. ISBN 0-262-02313-X