DOPIPE

El paralelismo DOPIPE es un método para lograr el paralelismo a nivel de bucle mediante la segmentación de las instrucciones dentro de un bucle. El paralelismo segmentado puede existir en diferentes niveles de abstracción, como bucles, funciones y etapas algorítmicas. El grado de paralelismo depende de la capacidad de los programadores para aprovechar al máximo este concepto. También depende de factores como la identificación y separación de las tareas independientes y su ejecución en paralelo. ^{[ 1 ]}

El objetivo principal de emplear el paralelismo a nivel de bucle es buscar y dividir tareas secuenciales de un programa y convertirlas en tareas paralelas sin información previa sobre el algoritmo . Las partes de los datos que se repiten y consumen una cantidad significativa de tiempo de ejecución son buenas candidatas para el paralelismo a nivel de bucle . Algunas aplicaciones comunes del paralelismo a nivel de bucle se encuentran en métodos de análisis matemático que utilizan matrices multidimensionales que se iteran en bucles anidados. ^{[ 2 ]}

Existen diferentes técnicas de paralelización que se utilizan en función de la sobrecarga de almacenamiento de datos, el grado de paralelización y las dependencias de los datos . Algunas de las técnicas conocidas son: DOALL , DOACROSS y DOPIPE .

DOALL: Esta técnica se utiliza cuando podemos paralelizar cada iteración del bucle sin ninguna interacción entre ellas. Por lo tanto, el tiempo total de ejecución se reduce de N * T (para un procesador en serie, donde T es el tiempo de ejecución de cada iteración) a solo T (ya que las N iteraciones se ejecutan en paralelo).

DOACROSS: Esta técnica se utiliza siempre que existe la posibilidad de dependencias de datos. Por lo tanto, paralelizamos las tareas de tal manera que todas las tareas independientes de datos se ejecutan en paralelo, mientras que las dependientes se ejecutan secuencialmente. Se utiliza cierto grado de sincronización para sincronizar las tareas dependientes entre los procesadores paralelos.

DOPIPE es una técnica de paralelización en pipeline que se utiliza en programas donde cada elemento producido durante cada iteración se consume en la siguiente. El siguiente ejemplo muestra cómo implementar la técnica DOPIPE para reducir el tiempo total de ejecución dividiendo las tareas dentro del bucle y ejecutándolas en pipeline . La división en tareas se realiza de tal manera que todas las dependencias dentro del bucle son unidireccionales; es decir, la siguiente iteración no depende de la anterior.

Ejemplo

El programa que se muestra a continuación presenta un pseudocódigo ^{[ 2 ]} para la paralelización de DOPIPE.

En este código, vemos que hay tres tareas (F0, F1 y F2) dentro de un bucle que itera jde 1 a N. A continuación se muestra una lista de dependencias en el código:

F1[j] → ^T F1[j+1], implica que la instrucción F1 en la iteración j+1debe ejecutarse después de la instrucción F1 en la iteración j. Esto también se conoce como dependencia verdadera.

F1[j] → ^T F2[j], implica que la instrucción F2 en la iteración jdebe ejecutarse después de la instrucción F1 en la iteración j.

para (j=1; j<=N; j++) { F0: o[j] = x[j] - a[j]; F1: z[j] = z[j-1] * 5; F2: y[j] = z[j] * w[j]; } 

Si este código se hubiera ejecutado secuencialmente, el tiempo total consumido sería igual a N * (T _F0 + T _F1 + T _F2 ), donde T _F0 , T _F1 y T _F2 denotan el tiempo de ejecución de las funciones F0, F1 y F2 respectivamente por iteración. Ahora bien, si paralelizamos el bucle canalizando las instrucciones dentro del bucle de la siguiente manera:

para (j=1; j<=N; j++) { F0: o[j] = x[j] - a[j]; // Paralelismo DOALL } para (j=1; j<=N; j++) { F1: z[j] = z[j-1] * 5; // Paralelismo DOPIPE post(j); // El resultado de F1 se publica y está disponible para su uso. } para (j=1; j<=N; j++) { wait(j); // Espera hasta que F1 se complete y produzca el valor z[j] que será utilizado por F2. F2: y[j] = z[j] * w[j]; } 

Dado que F0 es una función independiente, es decir, no tiene ninguna dependencia de bucle (sin dependencia de j+1iteraciones j-1). Tampoco tiene ninguna dependencia con otras instrucciones dentro del bucle. Por lo tanto, podemos separar completamente esta función y ejecutarla en paralelo usando el paralelismo DOALL . Por otro lado, las instrucciones F1 y F2 son dependientes (explicado anteriormente), por lo que las dividimos en dos bucles diferentes y las ejecutamos de forma segmentada . Usamos post(j)y wait(j)para sincronizar entre los bucles F1 y F2.

A partir de la primera iteración de j, la instrucción F1 se ejecuta en T _F1 tiempo. Mientras tanto, F2 no se ejecuta ya que está esperando el valor z[j]que F1 produce. Cuando F1 completa su ejecución para la iteración j, publica el valor usando post(j). Después de esperar la ejecución de F1, usando wait(j), F2 comienza su ejecución ya que tiene el valor z[j]disponible para su uso. Además, como la ejecución de F1 no está restringida por F2, F1 se ejecuta j+1simultáneamente. La siguiente figura muestra la línea de tiempo de ejecución de todas las instrucciones.

En la figura, observamos que el tiempo total de ejecución de F0 es T _F0 , ya que todas las iteraciones de F0 se ejecutan en paralelo. Mientras que para F1 y F2, el tiempo total de ejecución es igual a N * T _F1 + T _F2 (considerando un tiempo de sincronización insignificante).

Esto es considerablemente menor que el tiempo obtenido durante la ejecución secuencial.

El paralelismo DOALL se basa principalmente en el principio de divide y vencerás. En este caso, todas las tareas se ejecutan en diferentes iteraciones que utilizan conjuntos de datos únicos. El problema con esta implementación es que, al procesar grandes cantidades de datos simultáneamente, se requiere un amplio espacio de caché para que trabajen los distintos hilos . Dado que no existen dependencias entre los hilos , no hay sobrecarga en la comunicación entre ellos.

En DOPIPE, existe una sobrecarga de sincronización entre los hilos. Sin embargo, debido a su estructura en paralelo, requiere menos espacio de caché porque los datos producidos son consumidos inmediatamente por el consumidor. ^{[ 2 ]}

• Computación paralela
• Paralelismo a nivel de bucle
• Paralelismo de tareas
• dependencia de datos
• OpenMP
• Paralelización automática
• Hilo (informática)
• Caché (informática)