D. Cláusula schedule

Una región paralela tiene al menos una barrera, al final, y puede tener barreras adicionales dentro de ella. En cada barrera, los demás miembros del equipo deben esperar a que llegue el último subproceso. Para minimizar este tiempo de espera, se debe distribuir el trabajo compartido de modo que todos los subprocesos lleguen a la barrera aproximadamente al mismo tiempo. Si parte de ese trabajo compartido está contenido en construcciones for, la cláusula schedule se puede usar para este propósito.

Cuando hay referencias repetidas a los mismos objetos, la elección de programación para una construcción for puede determinarse principalmente por características del sistema de memoria, como la presencia y el tamaño de cachés y si los tiempos de acceso a la memoria son uniformes o no uniformes. Estas consideraciones pueden hacer que sea preferible que cada subproceso haga referencia de forma coherente al mismo conjunto de elementos de una matriz en una serie de bucles, incluso si a algunos subprocesos se les asigna relativamente menos trabajo en algunos de los bucles. Esta configuración se puede realizar mediante la programación static con los mismos límites para todos los bucles. En el ejemplo siguiente, cero se usa como límite inferior en el segundo bucle, aunque k sería más natural si la programación no fuera importante.

#pragma omp parallel
{
#pragma omp for schedule(static)
  for(i=0; i<n; i++)
    a[i] = work1(i);
#pragma omp for schedule(static)
  for(i=0; i<n; i++)
    if(i>=k) a[i] += work2(i);
}

En los ejemplos restantes, se supone que el acceso a la memoria no es la consideración dominante. A menos que se indique lo contrario, se supone que todos los subprocesos reciben recursos informáticos comparables. En estos casos, la elección de programación para una construcción for depende de todo el trabajo compartido que se realizará entre la barrera anterior más cercana y la barrera de cierre implícita o la barrera siguiente más cercana, si hay una cláusula nowait. Para cada tipo de programación, un breve ejemplo muestra cómo es probable que ese tipo de programación sea la mejor opción. Una breve explicación sigue a cada ejemplo.

La programación static también es adecuada para el caso más sencillo, una región paralela que contiene una sola construcción for, con cada iteración que requiere la misma cantidad de trabajo.

#pragma omp parallel for schedule(static)
for(i=0; i<n; i++) {
  invariant_amount_of_work(i);
}

La programación static se caracteriza por las propiedades de que cada subproceso obtiene aproximadamente el mismo número de iteraciones que cualquier otro subproceso, y cada subproceso puede determinar de forma independiente las iteraciones asignadas a él. Por lo tanto, no se requiere sincronización para distribuir el trabajo y, bajo la suposición de que cada iteración requiere la misma cantidad de trabajo, todos los subprocesos deben finalizar al mismo tiempo.

Para un equipo de subprocesos p, deje que ceiling(n/p) sea el entero q, que satisface n = p*q - r con 0 <= r < p. Una implementación de la programación static de este ejemplo asignaría q iteraciones a los primeros p-1 subprocesos y q-r iteraciones al último subproceso. Otra implementación aceptable asignaría q iteraciones a los primeros p-r subprocesos y q-1 a los subprocesos r subprocesos restantes. En este ejemplo se muestra por qué un programa no debe confiar en los detalles de una implementación determinada.

La programación dynamic es adecuada para el caso de una construcción for con las iteraciones que requieren cantidades de trabajo variables, o incluso impredecibles.

#pragma omp parallel for schedule(dynamic)
  for(i=0; i<n; i++) {
    unpredictable_amount_of_work(i);
}

La programación dynamic se caracteriza por la propiedad de que ningún subproceso espera en la barrera durante más tiempo que el que le toma a otro subproceso ejecutar su iteración final. Este requisito significa que las iteraciones se deben asignar de una en una a los subprocesos a medida que estén disponibles, con sincronización para cada asignación. La sobrecarga de sincronización se puede reducir especificando un tamaño mínimo de fragmento k mayor que 1, de modo que a los subprocesos se les asignek a la vez hasta que permanezcan menos de k. Esto garantiza que ningún subproceso espere más tiempo en la barrera que el que le toma a otro subproceso ejecutar su fragmento final de (como máximo) k iteraciones.

La programación dynamic puede ser útil si los subprocesos reciben recursos informáticos variables, lo que tiene aproximadamente el mismo efecto que las distintas cantidades de trabajo de cada iteración. Del mismo modo, la programación dinámica también puede ser útil si los subprocesos llegan a la construcción for en momentos diferentes, aunque en algunos de estos casos, la programación guided puede ser preferible.

La programación guided es adecuada para el caso en el que los subprocesos pueden llegar a diferentes momentos en una construcción for con cada iteración que requiera aproximadamente la misma cantidad de trabajo. Esta situación puede ocurrir si, por ejemplo, la construcción for va precedida por una o varias secciones o construcciones for con cláusulas nowait.

#pragma omp parallel
{
  #pragma omp sections nowait
  {
    // ...
  }
  #pragma omp for schedule(guided)
  for(i=0; i<n; i++) {
    invariant_amount_of_work(i);
  }
}

Al igual que dynamic, la programación guided garantiza que ningún subproceso espere en la barrera más tiempo que el que le toma a otro subproceso ejecutar su iteración final o sus k iteraciones finales si se especifica un tamaño de fragmento de k. Entre estas programaciones, la programación guided se caracteriza por la propiedad de que requiere la menor cantidad de sincronizaciones. Para el tamaño de fragmento k, una implementación típica asignará q = ceiling(n/p) iteraciones al primer subproceso disponible, establecerá n como el mayor entre n-q y p*k, y se repetirá hasta que se asignen todas las iteraciones.

Cuando la elección de la programación óptima no es tan clara como en estos ejemplos, la programación runtime es conveniente para experimentar con diferentes programaciones y tamaños de fragmentos sin tener que modificar y volver a compilar el programa. También puede ser útil cuando la programación óptima depende (de alguna manera predecible) de los datos de entrada a los que se aplica el programa.

Para ver un ejemplo de las ventajas y desventajas entre diferentes programaciones, considere la posibilidad de compartir 1000 iteraciones entre ocho subprocesos. Suponga que hay una cantidad invariable de trabajo en cada iteración y úsela como unidad de tiempo.

Si todos los subprocesos se inician al mismo tiempo, la programación static ocasionará que la construcción se ejecute en 125 unidades, sin sincronización. Pero supongamos que un subproceso llega tarde en 100 unidades. Entonces, los siete subprocesos restantes esperan 100 unidades en la barrera y el tiempo de ejecución de toda la construcción aumenta a 225.

Dado que tanto las programaciones dynamic como guided aseguran que ningún subproceso espera más de una unidad en la barrera, el subproceso retrasado ocasiona que los tiempos de ejecución de la construcción aumenten solo a 138 unidades, posiblemente aumentados por retrasos de la sincronización. Si estos retrasos no son insignificantes, es importante que el número de sincronizaciones sea de 1000 para dynamic, pero solo 41 para guided, suponiendo que el tamaño de fragmento predeterminado es uno. Con un tamaño de fragmento de 25, dynamic y guided finalizan en ambos casos con 150 unidades, además de los retrasos de las sincronizaciones necesarias, que ahora solo se cuentan en 40 y 20, respectivamente.