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 del paralelismo a nivel de bucle a menudo surge en programas informáticos donde los datos se almacenan en estructuras de datos de acceso aleatorio . Cuando un programa secuencial iterará sobre la estructura de datos y operará en índices uno a la vez, un programa que explote el paralelismo a nivel de bucle utilizará múltiples subprocesos o procesos que operan en algunos o todos los índices al mismo tiempo. Dicho paralelismo proporciona una aceleración del tiempo de ejecución general del programa, generalmente en línea con la ley de Amdahl..
Descripción
Para bucles simples, donde cada iteración es independiente de las demás, el paralelismo a nivel de bucle puede ser vergonzosamente paralelo , ya que la paralelización solo requiere asignar un proceso para manejar cada iteración. Sin embargo, muchos algoritmos están diseñados para ejecutarse secuencialmente y fallan cuando los procesos paralelos corren debido a la dependencia dentro del código. En ocasiones, los algoritmos secuenciales se pueden aplicar a contextos paralelos con ligeras modificaciones. Sin embargo, normalmente requieren sincronización de procesos . La sincronización puede ser implícita, a través del paso de mensajes , o explícita, a través de primitivas de sincronización como semáforos .
Ejemplo
Considere el siguiente código operando en una lista L
de longitud n
.
para (int i = 0; i;> S1: L [i] = L [i] + 10;}
Cada iteración del ciclo toma el valor del índice actual de L
y lo incrementa en 10. Si la instrucción S1
tarda T
en ejecutarse, entonces el ciclo tarda n * T
en ejecutarse secuencialmente, ignorando el tiempo que tardan las construcciones de ciclo. Ahora, considere un sistema con p
procesadores donde p > n
. Si los n
subprocesos se ejecutan en paralelo, el tiempo para ejecutar todos los n
pasos se reduce a T
.
Los casos menos simples producen resultados inconsistentes, es decir, no serializables . Considere el siguiente ciclo operando en la misma lista L
.
para (int i = 1; i;> S1: L [i] = L [i - 1] + 10;}
Cada iteración establece que el índice actual sea el valor del anterior más diez. Cuando se ejecuta secuencialmente, cada iteración tiene la garantía de que la iteración anterior ya tendrá el valor correcto. Con múltiples subprocesos, la programación del proceso y otras consideraciones impiden que la orden de ejecución garantice que una iteración se ejecutará solo después de que se cumpla su dependencia. Es muy posible que suceda antes, dando lugar a resultados inesperados. La serialización se puede restaurar agregando sincronización para preservar la dependencia de iteraciones anteriores.
Dependencias en el código
Hay varios tipos de dependencias que se pueden encontrar dentro del código. [1] [2]
Tipo | Notación | Descripción |
---|---|---|
Verdadera dependencia (flujo) | S1 ->T S2 | Una verdadera dependencia entre S1 y S2 significa que S1 escribe en una ubicación que luego lee S2 |
Anti-dependencia | S1 ->A S2 | Una anti-dependencia entre S1 y S2 significa que S1 lee desde una ubicación que luego escribe S2. |
Dependencia de la producción | S1 ->O S2 | Una dependencia de salida entre S1 y S2 significa que S1 y S2 escriben en la misma ubicación. |
Dependencia de entrada | S1 ->I S2 | Una dependencia de entrada entre S1 y S2 significa que S1 y S2 leen desde la misma ubicación. |
Para preservar el comportamiento secuencial de un bucle cuando se ejecuta en paralelo, se debe preservar la dependencia real. La antidependencia y la dependencia del producto se pueden abordar dando a cada proceso su propia copia de variables (conocida como privatización). [1]
Ejemplo de verdadera dependencia
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
, de la cual S3 lee.
Ejemplo de anti-dependencia
S1: int a, b = 40;S2: a = b - 38;S3: b = -1;
S2 ->A S3
, lo que significa que S2 tiene una anti-dependencia de S3 porque S2 lee de la variable b
antes de que S3 escriba en ella.
Ejemplo de dependencia de la producción
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 de S3 porque ambos escriben en la variable a
.
Ejemplo de dependencia de insumos
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 de S3 porque S2 y S3 leen de la variable c
.
Dependencia en bucles
Dependencia transportada por bucle frente a independiente de bucle
Los bucles pueden tener dos tipos de dependencia:
- Dependencia en bucle
- Dependencia independiente del bucle
En la dependencia independiente del bucle, los bucles tienen dependencia entre iteraciones, pero no tienen dependencia entre iteraciones. Cada iteración puede tratarse como un bloque y realizarse 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, existe una dependencia de bucle independiente de S1 ->T S3
.
para (int i = 1; i;> S1: tmp = a [i]; S2: a [i] = b [i]; S3: b [i] = tmp;}
En la dependencia llevada a un bucle, las declaraciones en una iteración de un bucle dependen de las declaraciones en otra iteración del bucle. La dependencia transportada por bucle utiliza una versión modificada de la notación de dependencia vista anteriormente.
Ejemplo de dependencia en bucle donde S1[i] ->T S1[i + 1]
, donde i
indica la iteración actual e i + 1
indica la siguiente iteración.
para (int i = 1; i;> S1: a [i] = a [i - 1] + 1;}
Gráfico de dependencia transportada por bucle
Un gráfico de dependencia transportada por bucle muestra gráficamente las dependencias transportadas por bucle entre iteraciones. Cada iteración se enumera como un nodo en el gráfico, y los bordes dirigidos muestran las dependencias verdaderas, anti y de salida entre cada iteración.
Tipos
Existe una variedad de metodologías para paralelizar bucles.
- Bucle DISTRIBUIDO
- Paralelismo DOALL
- Paralelismo DOACROSS
- HELIX [3]
- Paralelismo DOPIPE
Cada implementación varía ligeramente en cómo se sincronizan los subprocesos, si es que se sincronizan. Además, las tareas paralelas deben asignarse de alguna manera a un proceso. Estas tareas se pueden asignar de forma estática o dinámica. La investigación ha 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 estáticamente. [4]
El proceso de paralelizar un programa secuencial se puede dividir en los siguientes pasos discretos. [1] Cada paralelización de bucles concretos a continuación los realiza implícitamente.
Tipo | Descripción |
---|---|
Descomposición | El programa se divide en tareas, la unidad de concurrencia más pequeña que se puede explotar. |
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 vinculados a los procesadores. |
Bucle DISTRIBUIDO
Cuando un bucle tiene una dependencia transportada por bucles, una forma de paralelizarlo es distribuir el bucle en varios bucles diferentes. Las sentencias que no dependen unas de otras se separan para que estos bucles distribuidos se puedan ejecutar en paralelo. Por ejemplo, considere el siguiente código.
para (int i = 1; i;> S1: a [i] = a [i -1] + b [i]; S2: c [i] = c [i] + d [i];}
El bucle tiene una dependencia de transporte de bucle, S1[i] ->T S1[i + 1]
pero S2 y S1 no tienen una dependencia independiente de bucle, por lo que podemos reescribir el código de la siguiente manera.
loop1: for (int i = 1; i;> S1: a [i] = a [i -1] + b [i];}loop2: for (int i = 1; i ;> S2: c [i] = c [i] + d [i];}
Tenga en cuenta que ahora loop1 y loop2 se pueden ejecutar en paralelo. En lugar de realizar una sola instrucción en paralelo en diferentes datos como en el paralelismo a nivel de datos, aquí diferentes bucles realizan diferentes tareas en diferentes datos. Digamos que el tiempo de ejecución de S1 y S2 sea y entonces el tiempo de ejecución para la forma secuencial del código anterior es Ahora, debido a que dividimos las dos declaraciones y las colocamos en dos bucles diferentes, nos da un tiempo de ejecución de . A este tipo de paralelismo lo llamamos paralelismo de funciones o de tareas.
Paralelismo DOALL
El paralelismo DOALL existe cuando las sentencias dentro de un bucle se pueden ejecutar de forma independiente (situaciones en las que no hay dependencia llevada por el bucle). [1] Por ejemplo, el siguiente código no se lee de la matriz a
y no actualiza las matrices b, c
. Ninguna iteración depende de ninguna otra iteración.
para (int i = 0; i;> S1: a [i] = b [i] + c [i];}
Digamos que el tiempo de una ejecución de S1 sea entonces el tiempo de ejecución para la forma secuencial del código anterior es Ahora, debido a que el paralelismo de 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 necesario para una iteración en la ejecución secuencial.
El siguiente ejemplo, que utiliza un pseudocódigo simplificado, muestra cómo un bucle se puede paralelizar para ejecutar cada iteración de forma independiente.
begin_parallelism ();para (int i = 0; i;> S1: a [i] = b [i] + c [i]; end_parallelism ();}cuadra();
Paralelismo DOACROSS
DOACROSS El paralelismo existe cuando las iteraciones de un bucle se paralelizan extrayendo cálculos que se pueden realizar de forma independiente y ejecutándolos simultáneamente. [5]
La sincronización existe para reforzar la dependencia llevada a cabo en bucle.
Considere el siguiente bucle síncrono con dependencia S1[i] ->T S1[i + 1]
.
para (int i = 1; i;> a [i] = a [i - 1] + b [i] + 1;}
Cada iteración de bucle realiza dos acciones
- Calcular
a[i - 1] + b[i] + 1
- Asignar el valor a
a[i]
Calcular el valor a[i - 1] + b[i] + 1
y luego realizar la asignación se puede 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 transporte de bucle. Luego, el bucle se puede paralelizar calculando el valor de temperatura en paralelo y luego sincronizando la asignación a a[i]
.
publicar (0);para (int i = 1; i;> S1: int tmp = b [i] + 1; esperar (i - 1); S2: a [i] = a [i - 1] + tmp; puesto (i);}
Digamos que el tiempo de ejecución de S1 y S2 sea y entonces el tiempo de ejecución para la forma secuencial del código anterior es Ahora, debido a que existe el paralelismo DOACROSS, la aceleración se puede lograr ejecutando iteraciones de manera canalizada, lo que nos da un tiempo de ejecución de .
Paralelismo DOPIPE
DOPIPE Parallelism implementa el paralelismo canalizado para la dependencia de bucle 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 montaje, donde una etapa se inicia tan pronto como se dispone de datos suficientes de la etapa anterior. [6]
Considere el siguiente código síncrono con dependencia S1[i] ->T S1[i + 1]
.
para (int i = 1; i;> S1: a [i] = a [i - 1] + b [i]; S2: c [i] = c [i] + a [i];}
S1 debe ejecutarse secuencialmente, pero S2 no tiene dependencia de transporte de bucle. S2 podría ejecutarse en paralelo usando DOALL Parallelism 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 manera que el S2 correspondiente a cada S1 se ejecute cuando dicho S1 haya terminado.
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 terminado su índice correspondiente.
para (int i = 1; i;> S1: a [i] = a [i - 1] + b [i]; puesto (i);}para (int i = 1; i ;> esperar (i); S2: c [i] = c [i] + a [i];}
Digamos que el tiempo de ejecución de S1 y S2 sea y entonces el tiempo de ejecución para la forma secuencial del código anterior es Ahora, debido a que existe el paralelismo DOPIPE, la aceleración se puede lograr ejecutando iteraciones en forma de canalización, lo que nos da un tiempo de ejecución de , donde p es el número de procesadores en paralelo.
Ver también
- Paralelismo de datos
- Paralelismo de tareas
- Paralelismo utilizando diferentes tipos de modelos de memoria como compartidos y distribuidos y paso de mensajes
Referencias
- ↑ a b c d e Solihin, Yan (2016). Fundamentos de la Arquitectura Paralela . Boca Raton, FL: CRC Press. ISBN 978-1-4822-1118-4.
- ^ Goff, Gina (1991). "Pruebas prácticas de dependencia". Actas de la conferencia ACM SIGPLAN 1991 sobre diseño e implementación de lenguajes de programación - PLDI '91 . págs. 15-29. doi : 10.1145 / 113445.113448 . ISBN 0897914287.
- ^ Murphy, Niall. "Descubrimiento y explotación del paralelismo en bucles DOACROSS" (PDF) . Universidad de Cambridge . Consultado el 10 de septiembre de 2016 .
- ^ Kavi, Krishna. "Paralelización de DOALL y DOACROSS Loops-a Survey". Cite journal requiere
|journal=
( ayuda ) - ^ Unnikrishnan, Priya (2012), "A Practical Approach to DOACROSS Parallelization" , Procesamiento paralelo Euro-Par 2012 , Lecture Notes in Computer Science, 7484 , págs. 219-231, doi : 10.1007 / 978-3-642-32820-6_23 , ISBN 978-3-642-32819-0
- ^ "DoPipe: un enfoque eficaz para paralelizar la simulación" (PDF) . Intel . Consultado el 13 de septiembre de 2016 .