Paralelismo de datos

Paralelización entre múltiples procesadores en entornos de computación paralela

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

Historia

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.

Descripción

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.

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. $O(n^{3})$ $O(n)$

// 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 lugar de cuando se ejecuta en paralelo utilizando procesadores m*k . $O(n)$ $O(m*n*k)$

Paralelismo de datos en la multiplicación de matrices

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

Pasos para la paralelización

El proceso de paralelización de un programa secuencial se puede dividir en cuatro pasos discretos. ^[5]

Tipo	Descripción
Descomposición	El programa se divide en tareas, la unidad de concurrencia explotable más pequeña.
Asignación	Las tareas se asignan a los procesos.
Orquestación	Acceso a datos, comunicación y sincronización de procesos.
Cartografía	Los procesos están ligados a los procesadores.

Paralelismo de datos vs. paralelismo de tareas

Paralelismo de datos	Paralelismo de tareas
Las mismas operaciones se realizan en diferentes subconjuntos de los mismos datos.	Se realizan diferentes operaciones sobre los mismos datos o sobre datos diferentes.
Computación sincrónica	Computación asincrónica
La aceleración es mayor ya que solo hay un hilo de ejecución que opera en todos los conjuntos de datos.	La aceleración es menor ya que cada procesador ejecutará un hilo o proceso diferente en el mismo conjunto de datos o en uno diferente.
La cantidad de paralelización es proporcional al tamaño de los datos de entrada.	La cantidad de paralelización es proporcional al número de tareas independientes a realizar.
Diseñado para un equilibrio de carga óptimo en sistemas multiprocesador.	El equilibrio de carga depende de la disponibilidad del hardware y de los algoritmos de programación, como la programación estática y dinámica.

Paralelismo de datos vs. paralelismo de modelos

Paralelismo de datos	Paralelismo de modelos
Se utiliza el mismo modelo para cada hilo, pero los datos proporcionados a cada uno de ellos se dividen y comparten.	Se utilizan los mismos datos para cada hilo y el modelo se divide entre los hilos.
Es rápido para redes pequeñas, pero muy lento para redes grandes, ya que es necesario transferir grandes cantidades de datos entre procesadores a la vez.	Es lento para redes pequeñas y rápido para redes grandes.
El paralelismo de datos se utiliza idealmente en cálculos de matrices y redes neuronales convolucionales.	El paralelismo de modelos encuentra sus aplicaciones en el aprendizaje profundo

^[6]

Datos mixtos y paralelismo de tareas

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:

El paralelismo de tareas y datos mixtos se utiliza en el modelado climático global. Los cálculos en paralelo de grandes cantidades de datos se realizan creando cuadrículas de datos que representan la atmósfera y los océanos de la Tierra, y el paralelismo de tareas se utiliza para simular la función y el modelo de los procesos físicos.
En la simulación de circuitos basada en tiempo , los datos se dividen entre diferentes subcircuitos y se logra el paralelismo con la orquestación de las tareas.

Entornos de programación paralela de datos

Actualmente existen diversos entornos de programación paralela de datos, los más utilizados son:

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 biblioteca para permitir a los usuarios escribir programas de paso de mensajes portables en C, C++ y Fortran.
Open Multi Processing ^[8] (Open MP): 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 apuntar a dispositivos distintos de las CPU típicas. Puede programar FPGA, DSP, GPU y más. No se limita a GPU como OpenACC.
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 computacionales de la GPU para el procesamiento de propósito general.
Threading Building Blocks y RaftLib : ambos entornos de programación de código abierto que permiten el paralelismo mixto de datos/tareas en entornos C/C++ a través de recursos heterogéneos.

Aplicaciones

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.

Computación intensiva en datos

La computación intensiva en datos es una clase de aplicaciones de computación paralela que utilizan un enfoque de datos paralelos para procesar grandes volúmenes de datos, normalmente de terabytes o petabytes de tamaño y que normalmente se conocen como big data . Las aplicaciones informáticas que dedican la mayor parte de su tiempo de ejecución a los requisitos computacionales se consideran intensivas en computación, mientras que las aplicaciones que se consideran intensivas en datos requieren grandes volúmenes de datos y dedican la mayor parte de su tiempo de procesamiento a la E/S y la manipulación de datos. ^[12]

Véase también

Notas

^ Algunos datos de entrada (por ejemplo, cuando 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.

Referencias

^ "La computadora de Salomón".
^ "SIMD/Vector/GPU" (PDF) . Consultado el 7 de septiembre de 2016 .
^ Hillis, W. Daniel y Steele, Guy L. , Algoritmos de datos paralelos Comunicaciones del ACM Diciembre de 1986
^ Barney, Blaise. "Introducción a la computación paralela". computing.llnl.gov . Archivado desde el original el 2013-06-10 . Consultado el 2016-09-07 .
^ Solihin, Yan (2016). Fundamentos de la Arquitectura Paralela . Boca Ratón, FL: CRC Press. ISBN 978-1-4822-1118-4.
^ "Cómo paralelizar el aprendizaje profundo en GPU, parte 2/2: paralelismo de modelos". Tim Dettmers . 2014-11-09 . Consultado el 2016-09-13 .
^ "La Netlib" (PDF) .
^ "OpenMP.org". openmp.org . Archivado desde el original el 2016-09-05 . Consultado el 2016-09-07 .
^ Boyer, L. L; Pawley, G. S (1988-10-01). "Dinámica molecular de cúmulos de partículas que interactúan con fuerzas por pares utilizando una computadora masivamente paralela". Journal of Computational Physics . 78 (2): 405–423. Bibcode :1988JCoPh..78..405B. doi :10.1016/0021-9991(88)90057-5.
^ Yap, TK; Frieder, O.; Martino, RL (1998). "Computación paralela en análisis de secuencias biológicas". IEEE Transactions on Parallel and Distributed Systems . 9 (3): 283–294. CiteSeerX 10.1.1.30.2819 . doi :10.1109/71.674320.
^ Singh, H.; Lee, Ming-Hau; Lu, Guangming; Kurdahi, FJ; Bagherzadeh, N.; Filho, EM Chaves (1 de junio de 2000). "MorphoSys: un sistema reconfigurable integrado para aplicaciones de computación intensiva y de datos en paralelo". IEEE Transactions on Computers . 49 (5): 465–481. doi :10.1109/12.859540. ISSN 0018-9340.
^ Manual de computación en la nube, "Tecnologías de uso intensivo de datos para computación en la nube", de AM Middleton. Manual de computación en la nube. Springer, 2010.

Hillis, W. Daniel y Steele, Guy L. , Algoritmos de datos paralelos Comunicaciones del ACM Diciembre de 1986
Blelloch, Guy E, Modelos vectoriales para computación paralela de datos MIT Press 1990. ISBN 0-262-02313-X

[5] Algunos datos de entrada (por ejemplo, cuando 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.

[1] "La computadora de Salomón".

[2] "SIMD/Vector/GPU" (PDF) . Consultado el 7 de septiembre de 2016 .

[3] Hillis, W. Daniel y Steele, Guy L. , Algoritmos de datos paralelos Comunicaciones del ACM Diciembre de 1986

[4] Barney, Blaise. "Introducción a la computación paralela". computing.llnl.gov . Archivado desde el original el 2013-06-10 . Consultado el 2016-09-07 .

[Solihin-6] Solihin, Yan (2016). Fundamentos de la Arquitectura Paralela . Boca Ratón, FL: CRC Press. ISBN 978-1-4822-1118-4.

[7] "Cómo paralelizar el aprendizaje profundo en GPU, parte 2/2: paralelismo de modelos". Tim Dettmers . 2014-11-09 . Consultado el 2016-09-13 .

[8] "La Netlib" (PDF) .

[9] "OpenMP.org". openmp.org . Archivado desde el original el 2016-09-05 . Consultado el 2016-09-07 .

[10] Boyer, L. L; Pawley, G. S (1988-10-01). "Dinámica molecular de cúmulos de partículas que interactúan con fuerzas por pares utilizando una computadora masivamente paralela". Journal of Computational Physics . 78 (2): 405–423. Bibcode :1988JCoPh..78..405B. doi :10.1016/0021-9991(88)90057-5.

[11] Yap, TK; Frieder, O.; Martino, RL (1998). "Computación paralela en análisis de secuencias biológicas". IEEE Transactions on Parallel and Distributed Systems . 9 (3): 283–294. CiteSeerX 10.1.1.30.2819 . doi :10.1109/71.674320.

[12] Singh, H.; Lee, Ming-Hau; Lu, Guangming; Kurdahi, FJ; Bagherzadeh, N.; Filho, EM Chaves (1 de junio de 2000). "MorphoSys: un sistema reconfigurable integrado para aplicaciones de computación intensiva y de datos en paralelo". IEEE Transactions on Computers . 49 (5): 465–481. doi :10.1109/12.859540. ISSN 0018-9340.

[13] Manual de computación en la nube, "Tecnologías de uso intensivo de datos para computación en la nube", de AM Middleton. Manual de computación en la nube. Springer, 2010.