Paralelismo a nivel de bucle

ent a , b ; // s1 a = 2 ; // s2 b = a + 40 ; // s3

s2 ->T s3, lo que significa que s2 tiene una verdadera dependencia de s3 porque s2 escribe en la variable a, de la cual s3 lee.

int a , b = 40 ; // s1 a = b - 38 ; // s2 b = -1 ; // s3

s2 ->A s3, lo que significa que s2 tiene una antidependencia de s3 porque s2 lee de la variable bantes de que s3 escriba en ella.

int a , b = 40 ; // s1 a = b - 38 ; // s2 a = 2 ; // s3

s2 ->O s3, lo que significa que s2 tiene una dependencia de salida de s3 porque ambos escriben en la variable a.

int a , b , c = 2 ; // s1 a = c - 1 ; // s2 b = c + 1 ; // s3

s2 ->I s3, lo que significa que s2 tiene una dependencia de entrada de s3 porque tanto s2 como s3 leen de la variable c.

Los bucles pueden tener dos tipos de dependencia:

• Dependencia transmitida por bucles
• Dependencia independiente del bucle

En la dependencia independiente de bucles, los bucles presentan dependencia entre iteraciones, pero no entre iteraciones. Cada iteración puede tratarse como un bloque y ejecutarse en paralelo sin necesidad de sincronización adicional.

En el siguiente código de ejemplo utilizado para intercambiar los valores de dos matrices de longitud n, existe una dependencia independiente del bucle de s1 ->T s3.

for ( int i = 1 ; i < n ; ++ i ) { tmp = a [ i ]; // s1 a [ i ] = b [ i ]; // s2 b [ i ] = tmp ; // s3 }

En la dependencia de bucle, las instrucciones de una iteración dependen de las instrucciones de otra iteración del mismo bucle. La dependencia de bucle utiliza una versión modificada de la notación de dependencia vista anteriormente.

Ejemplo de dependencia llevada por bucle donde s1[i] ->T s1[i + 1], donde iindica la iteración actual, e i + 1indica la siguiente iteración.

for ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + 1 ; // s1 }

Un grafo de dependencias de bucle muestra gráficamente las dependencias entre iteraciones. Cada iteración se representa como un nodo en el grafo, y las aristas dirigidas muestran las dependencias verdaderas, inversas y de salida entre cada iteración.

Cuando un bucle tiene una dependencia entre bucles, una forma de paralelizarlo es distribuirlo en varios bucles diferentes. Las instrucciones que no dependen unas de otras se separan para que estos bucles distribuidos puedan ejecutarse en paralelo. Por ejemplo, considere el siguiente código.

for ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + b [ i ]; // s1 c [ i ] += d [ i ]; // s2 }

El bucle tiene una dependencia de bucle, s1[i] ->T s1[i + 1]pero s2 y s1 no tienen una dependencia independiente del bucle, por lo que podemos reescribir el código de la siguiente manera.

// bucle1 para ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + b [ i ]; // s1 }// bucle2 para ( int i = 1 ; i < n ; ++ i ) { c [ i ] += d [ i ]; // s2 }

Tenga en cuenta que ahora loop1 y loop2 pueden ejecutarse en paralelo. En lugar de que una sola instrucción se ejecute en paralelo sobre diferentes datos, como en el paralelismo a nivel de datos, aquí diferentes bucles realizan diferentes tareas sobre diferentes datos. Digamos que el tiempo de ejecución de s1 y s2 es${\displaystyle T_{s_{1}}}$y${\displaystyle T_{s_{2}}}$Entonces, el tiempo de ejecución para la forma secuencial del código anterior es${\displaystyle n\cdot (T_{s_{1}}+T_{s_{2}})}$Ahora, debido a que dividimos las dos instrucciones y las colocamos en dos bucles diferentes, obtenemos un tiempo de ejecución de${\displaystyle n\cdot T_{s_{1}}+T_{s_{2}}}$A este tipo de paralelismo lo denominamos paralelismo de funciones o paralelismo de tareas.

El paralelismo DOALL existe cuando las instrucciones dentro de un bucle pueden ejecutarse de forma independiente (situaciones en las que no hay dependencia entre bucles). ^{[ 1 ]} Por ejemplo, el siguiente código no lee del array ay no actualiza los arrays b, c. Ninguna iteración depende de ninguna otra.

for ( int i = 0 ; i < n ; ++ i ) { a [ i ] = b [ i ] + c [ i ]; // s1 }

Digamos que el tiempo de una ejecución de s1 es${\displaystyle T_{s_{1}}}$Entonces, el tiempo de ejecución para la forma secuencial del código anterior es${\displaystyle n\cdot T_{s_{1}}}$Ahora bien, debido a que el paralelismo DOALL existe cuando todas las iteraciones son independientes, se puede lograr una aceleración ejecutando todas las iteraciones en paralelo, lo que nos da un tiempo de ejecución de${\displaystyle T_{s_{1}}}$, que es el tiempo que tarda una iteración en la ejecución secuencial.

El siguiente ejemplo, utilizando un pseudocódigo simplificado, muestra cómo se podría paralelizar un bucle para ejecutar cada iteración de forma independiente.

beginParallelism ();for ( int i = 0 ; i < n ; ++ i ) { a [ i ] = b [ i ] + c [ i ]; // s1 endParallelism (); }bloquear ();

El paralelismo DOACROSS existe cuando las iteraciones de un bucle se paralelizan extrayendo cálculos que pueden realizarse de forma independiente y ejecutándolos simultáneamente. ^{[ 5 ]}

La sincronización existe para imponer la dependencia transmitida por el bucle.

Considere el siguiente bucle síncrono con dependencia s1[i] ->T s1[i + 1].

para ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + b [ i ] + 1 ; }

Cada iteración del bucle realiza dos acciones.

• Calculara[i - 1] + b[i] + 1
• Asigne el valor aa[i]

El cálculo del valor a[i - 1] + b[i] + 1y la posterior realización de la asignación se pueden descomponer en dos líneas (instrucciones s1 y s2):

int tmp = b [ i ] + 1 ; // s1 a [ i ] = a [ i - 1 ] + tmp ; // s2

La primera línea, int tmp = b[i] + 1;, no tiene dependencia de bucle. El bucle se puede paralelizar calculando el valor temporal en paralelo y luego sincronizando la asignación a a[i].

post ( 0 ); for ( int i = 1 ; i < n ; ++ i ) { int tmp = b [ i ] + 1 ; // s1 wait ( i - 1 );a [ i ] = a [ i - 1 ] + tmp ; // s2 post ( i ); }

Digamos que el tiempo de ejecución de s1 y s2 es${\displaystyle T_{s_{1}}}$y${\displaystyle T_{s_{2}}}$Entonces, el tiempo de ejecución para la forma secuencial del código anterior es${\displaystyle n\cdot (T_{s_{1}}+T_{s_{2}})}$Ahora bien, debido a que existe el paralelismo DOACROSS, se puede lograr una aceleración ejecutando iteraciones de forma segmentada, lo que nos da un tiempo de ejecución de${\displaystyle T_{s_{1}}+n\cdot T_{s_{2}}}$.

DOPIPE Parallelism implementa paralelismo segmentado para dependencias entre bucles, donde una iteración de bucle se distribuye entre múltiples bucles sincronizados. ^{[ 1 ]} El objetivo de DOPIPE es funcionar como una cadena de montaje, donde una etapa se inicia tan pronto como haya suficientes datos disponibles de la etapa anterior. ^{[ 6 ]}

Considere el siguiente código síncrono con dependencia s1[i] ->T s1[i + 1].

for ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + b [ i ]; // s1 c [ i ] += a [ i ]; // s2 }

s1 debe ejecutarse secuencialmente, pero s2 no tiene dependencia de bucle. s2 podría ejecutarse en paralelo usando el paralelismo DOALL después de realizar todos los cálculos necesarios para s1 en serie. Sin embargo, la mejora de velocidad es limitada si se hace de esta manera. Un enfoque mejor es paralelizar de forma que el s2 correspondiente a cada s1 se ejecute cuando dicho s1 haya finalizado.

La implementación del paralelismo segmentado da como resultado el siguiente conjunto de bucles, donde el segundo bucle puede ejecutarse para un índice tan pronto como el primer bucle haya terminado con su índice correspondiente.

for ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + b [ i ]; // s1 post ( i ); }for ( int i = 1 ; i < n ; i ++ ) { wait ( i ); c [ i ] += a [ i ]; // s2 }

Digamos que el tiempo de ejecución de s1 y s2 es${\displaystyle T_{s_{1}}}$y${\displaystyle T_{s_{2}}}$Entonces, el tiempo de ejecución para la forma secuencial del código anterior es${\displaystyle n\cdot (T_{s_{1}}+T_{s_{2}})}$Ahora bien, debido a que existe el paralelismo DOPIPE, se puede lograr una aceleración ejecutando iteraciones de forma segmentada, lo que nos da un tiempo de ejecución de${\displaystyle n\cdot T_{s_{1}}+({\frac {n}{p}})\cdot T_{s_{2}}}$donde p es el número de procesadores en paralelo.