El paralelismo a nivel de bucle es una forma de paralelismo en la programación de software que se ocupa de extraer tareas paralelas de los bucles . La oportunidad de paralelismo a nivel de bucle surge a menudo en programas informáticos donde los datos se almacenan en estructuras de datos de acceso aleatorio . Mientras que un programa secuencial itera sobre la estructura de datos y opera en los índices uno a la vez, un programa que explota el paralelismo a nivel de bucle utilizará múltiples subprocesos o procesos que operan en algunos o todos los índices al mismo tiempo. Este paralelismo proporciona una aceleración del tiempo de ejecución general del programa, normalmente en línea con la ley de Amdahl .
En el caso de los bucles simples, donde cada iteración es independiente de las demás, el paralelismo a nivel de bucle puede resultar vergonzosamente paralelo , ya que la paralelización solo requiere asignar un proceso para que se encargue de cada iteración. Sin embargo, muchos algoritmos están diseñados para ejecutarse secuencialmente y fallan cuando los procesos paralelos compiten entre sí debido a la dependencia dentro del código. Los algoritmos secuenciales a veces se pueden aplicar a contextos paralelos con una ligera modificación. Sin embargo, normalmente requieren la sincronización de procesos . La sincronización puede ser implícita, mediante el paso de mensajes , o explícita, mediante primitivas de sincronización como los semáforos .
Considere el siguiente código que opera en una lista Lde longitud n.
para ( int i = 0 ; i < n ; ++ i ) { S1 : L [ i ] += 10 ; } Cada iteración del bucle toma el valor del índice actual de Ly lo incrementa en 10. Si la instrucción S1tarda Ttiempo en ejecutarse, entonces el bucle tarda tiempo n * Ten ejecutarse secuencialmente, ignorando el tiempo que tardan las construcciones del bucle. Ahora, considere un sistema con pprocesadores donde p > n. Si nlos subprocesos se ejecutan en paralelo, el tiempo para ejecutar todos nlos pasos se reduce a T.
Los casos menos simples producen resultados inconsistentes, es decir, no serializables . Considere el siguiente bucle que opera en la misma lista L.
para ( int i = 1 ; i < n ; ++ i ) { S1 : L [ i ] = L [ i -1 ] + 10 ; } Cada iteración establece el índice actual como el valor de la iteración anterior más diez. Cuando se ejecuta secuencialmente, se garantiza que cada iteración anterior ya tendrá el valor correcto. Con múltiples subprocesos, la programación de procesos y otras consideraciones impiden que el orden de ejecución garantice que una iteración se ejecutará solo después de que se cumpla su dependencia. Es muy posible que esto suceda antes, lo que genera resultados inesperados. La serialización se puede restaurar agregando sincronización para preservar la dependencia de iteraciones anteriores.
Existen varios tipos de dependencias que se pueden encontrar dentro del código. [1] [2]
Para preservar el comportamiento secuencial de un bucle cuando se ejecuta en paralelo, se debe preservar la dependencia verdadera. La antidependencia y la dependencia de salida se pueden solucionar dándole a cada proceso su propia copia de variables (lo que se conoce como privatización). [1]
S1 : int a , b ; S2 : a = 2 ; S3 : b = a + 40 ; S2 ->T S3, lo que significa que S2 tiene una verdadera dependencia de S3 porque S2 escribe en la variable a, desde donde S3 lee.
S1 : int a , b = 40 ; S2 : a = b - 38 ; S3 : b = -1 ; S2 ->A S3, lo que significa que S2 tiene una antidependencia con respecto a S3 porque S2 lee de la variable bantes de que S3 escriba en ella.
S1 : int a , b = 40 ; S2 : a = b - 38 ; S3 : a = 2 ; S2 ->O S3, lo que significa que S2 tiene una dependencia de salida en S3 porque ambos escriben en la variable a.
S1 : int a , b , c = 2 ; S2 : a = c - 1 ; S3 : b = c + 1 ; S2 ->I S3, lo que significa que S2 tiene una dependencia de entrada en S3 porque S2 y S3 leen desde la variable c.
Los bucles pueden tener dos tipos de dependencia:
En la dependencia independiente de bucles, los bucles tienen dependencia entre iteraciones, pero no tienen dependencia entre iteraciones. Cada iteración puede tratarse como un bloque y ejecutarse en paralelo sin otros esfuerzos de sincronización.
En el siguiente código de ejemplo utilizado para intercambiar los valores de dos matrices de longitud n, hay una dependencia independiente del bucle de S1 ->T S3.
para ( int i = 1 ; i < n ; ++ i ) { S1 : tmp = a [ i ]; S2 : a [ i ] = b [ i ]; S3 : b [ i ] = tmp ; } En la dependencia basada en bucles, las instrucciones de una iteración de un bucle dependen de instrucciones de otra iteración del bucle. La dependencia basada en bucles utiliza una versión modificada de la notación de dependencia que vimos anteriormente.
Ejemplo de dependencia transportada por bucle donde S1[i] ->T S1[i + 1], donde iindica la iteración actual y i + 1indica la siguiente iteración.
para ( int i = 1 ; i < n ; ++ i ) { S1 : a [ i ] = a [ i -1 ] + 1 ; } Un gráfico de dependencias de bucles muestra gráficamente las dependencias de bucles entre iteraciones. Cada iteración se muestra como un nodo en el gráfico y los bordes dirigidos muestran las dependencias verdaderas, anti y de salida entre cada iteración.
Existen diversas metodologías para paralelizar bucles.
Cada implementación varía ligeramente en la forma en que se sincronizan los subprocesos, si es que se sincronizan. Además, las tareas paralelas deben asignarse de alguna manera a un proceso. Estas tareas pueden asignarse de forma estática o dinámica. Las investigaciones han demostrado que el equilibrio de carga se puede lograr mejor a través de algunos algoritmos de asignación dinámica que cuando se hace de forma estática. [4]
El proceso de paralelización de un programa secuencial se puede dividir en los siguientes pasos discretos. [1] Cada paralelización de bucle concreta a continuación los realiza implícitamente.
Cuando un bucle tiene una dependencia que se transmite a través de un bucle, una forma de paralelizarlo es distribuir el bucle en varios bucles diferentes. Las sentencias que no dependen entre sí se separan para que estos bucles distribuidos se puedan ejecutar en paralelo. Por ejemplo, considere el siguiente código.
para ( int i = 1 ; i < n ; ++ i ) { S1 : a [ i ] = a [ i -1 ] + b [ i ]; S2 : c [ i ] += d [ i ]; } El bucle tiene una dependencia transportada por el 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 ) { S1 : a [ i ] = a [ i -1 ] + b [ i ]; } bucle2 : para ( int i = 1 ; i < n ; ++ i ) { S2 : c [ i ] += d [ i ]; } Tenga en cuenta que ahora loop1 y loop2 se pueden ejecutar en paralelo. En lugar de que se realice una única instrucción en paralelo con diferentes datos, como en el paralelismo a nivel de datos, aquí diferentes bucles realizan diferentes tareas con diferentes datos. Digamos que el tiempo de ejecución de S1 y S2 es y, entonces, el tiempo de ejecución para la forma secuencial del código anterior es . Ahora, como dividimos las dos instrucciones y las colocamos en dos bucles diferentes, obtenemos un tiempo de ejecución de . A este tipo de paralelismo lo llamamos paralelismo de funciones o de tareas.
El paralelismo DOALL existe cuando las instrucciones dentro de un bucle se pueden ejecutar de forma independiente (situaciones en las que no existe una dependencia transportada por el bucle). [1] Por ejemplo, el siguiente código no lee de la matriz ay no actualiza las matrices b, c. Ninguna iteración tiene una dependencia de ninguna otra iteración.
para ( int i = 0 ; i < n ; ++ i ) { S1 : a [ i ] = b [ i ] + c [ i ]; } Digamos que el tiempo de una ejecución de S1 es entonces el tiempo de ejecución para la forma secuencial del código anterior es , ahora debido a que el paralelismo DOALL existe cuando todas las iteraciones son independientes, la aceleración se puede lograr ejecutando todas las iteraciones en paralelo, lo que nos da un tiempo de ejecución de , que es el tiempo que toma una iteración en ejecución secuencial.
El siguiente ejemplo, utilizando un pseudocódigo simplificado, muestra cómo se puede paralelizar un bucle para ejecutar cada iteración independientemente.
comenzar_paralelismo (); para ( int i = 0 ; i < n ; ++ i ) { S1 : a [ i ] = b [ i ] + c [ i ]; fin_paralelismo (); } bloque (); El paralelismo DOACROSS existe cuando las iteraciones de un bucle se paralelizan extrayendo cálculos que se pueden realizar independientemente y ejecutándolos simultáneamente. [5]
La sincronización existe para reforzar la dependencia transportada por bucle.
Consideremos el siguiente bucle sincrónico 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
a[i-1] + b[i] + 1a[i]El cálculo del valor a[i-1] + b[i] + 1y la posterior ejecución de la asignación se pueden descomponer en dos líneas (declaraciones S1 y S2):
S1 : int tmp = b [ i ] + 1 ; S2 : a [ i ] = a [ i -1 ] + tmp ; 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].
publicación ( 0 ); para ( int i = 1 ; i < n ; ++ i ) { S1 : int tmp = b [ i ] + 1 ; esperar ( i -1 ); S2 : a [ i ] = a [ i -1 ] + tmp ; publicación ( i ); } Digamos que el tiempo de ejecución de S1 y S2 es y luego el tiempo de ejecución para la forma secuencial del código anterior es . Ahora bien, debido a que existe el paralelismo DOACROSS, se puede lograr una aceleración ejecutando iteraciones de manera secuenciada, lo que nos da un tiempo de ejecución de .
El paralelismo DOPIPE implementa un paralelismo segmentado para una dependencia transportada por bucles, donde una iteración de bucle se distribuye en múltiples bucles sincronizados. [1] El objetivo de DOPIPE es actuar como una línea de ensamblaje, donde una etapa se inicia tan pronto como hay suficientes datos disponibles para ella de la etapa anterior. [6]
Considere el siguiente código sincrónico con dependencia S1[i] ->T S1[i+1].
para ( int i = 1 ; i < n ; ++ i ) { S1 : a [ i ] = a [ i -1 ] + b [ i ]; S2 : c [ i ] += a [ i ]; } S1 debe ejecutarse secuencialmente, pero S2 no tiene dependencia de bucle. S2 podría ejecutarse en paralelo utilizando el paralelismo DOALL después de realizar todos los cálculos necesarios para S1 en serie. Sin embargo, la aceleración es limitada si se hace esto. Un mejor enfoque es paralelizar de modo que el S2 correspondiente a cada S1 se ejecute cuando dicho S1 finalice.
La implementación del paralelismo canalizado da como resultado el siguiente conjunto de bucles, donde el segundo bucle puede ejecutarse para un índice tan pronto como el primer bucle haya finalizado su índice correspondiente.
para ( int i = 1 ; i < n ; ++ i ) { S1 : a [ i ] = a [ i -1 ] + b [ i ]; post ( i ); } para ( int i = 1 ; i < n ; i ++ ) { esperar ( i ); S2 : c [ i ] += a [ i ]; } Digamos que el tiempo de ejecución de S1 y S2 es y luego el tiempo de ejecución para la forma secuencial del código anterior es , Ahora bien, debido a que existe el paralelismo DOPIPE, se puede lograr una aceleración ejecutando iteraciones de manera secuencial, lo que nos da un tiempo de ejecución de , donde p es el número de procesadores en paralelo.
{{cite journal}}: Requiere citar revista |journal=( ayuda )