multithreading - stop - Dividir iteraciones de bucle entre hilos

programa de hilos en python

Question

Hace poco escribí un pequeño programa de crujido de números que básicamente gira sobre una cuadrícula de N dimensiones y realiza algunos cálculos en cada punto.

for (int i1 = 0; i1 < N; i1++)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        histogram[bin_index(i1, i2, i3, i4)] += 1; // see bottom of question

Funcionó bien, yadda yadda yadda, resultaron gráficos encantadores ;-) Pero luego pensé, tengo 2 núcleos en mi computadora, ¿por qué no hacer que este programa sea multiproceso para poder ejecutarlo dos veces más rápido?

Ahora, mis loops ejecutan un total de, digamos, alrededor de mil millones de cálculos, y necesito alguna manera de dividirlos entre hilos. Me imagino que debería agrupar los cálculos en "tareas", es decir, cada iteración del ciclo más externo es una tarea, y repartir las tareas en hilos. Lo he considerado

• simplemente dando thread #n todas las iteraciones del bucle más externo donde i1 % nthreads == n - esencialmente predeterminando qué tareas van a qué hilos
• tratando de configurar alguna variable protegida por mutex que contenga los parámetros ( i1 en este caso) de la próxima tarea que se debe ejecutar, asignando tareas a los hilos de manera dinámica

¿Qué razones hay para elegir un enfoque sobre el otro? ¿O algún otro enfoque en el que no haya pensado? ¿Incluso importa?

Por cierto, escribí este programa en particular en C, pero me imagino que haré el mismo tipo de cosas también en otros idiomas, así que las respuestas no necesitan ser específicas de C. (Si alguien conoce una biblioteca C para Linux que hace este tipo de cosas, me gustaría saberlo)

EDITAR : en este caso bin_index es una función determinística que no cambia nada excepto sus propias variables locales. Algo como esto:

int bin_index(int i1, int i2, int i3, int i4) {
    // w, d, h are constant floats
    float x1 = i1 * w / N,  x2 = i2 * w / N, y1 = i3 * d / N, y2 = i4 * d / N;
    float l = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + h * h);
    float th = acos(h / l);
    // th_max is a constant float (previously computed as a function of w, d, h)
    return (int)(th / th_max);
}

(Aunque aprecio todos los comentarios, incluso aquellos que no se aplican a bin_index determinista)

Answer 1

El primer acercamiento es simple. También es suficiente si espera que la carga se equilibre uniformemente sobre los hilos. En algunos casos, especialmente si la complejidad de bin_index es muy dependiente de los valores de los parámetros, uno de los hilos podría terminar con una tarea mucho más pesada que el resto. Recuerde: la tarea finaliza cuando finaliza el último subproceso.

El segundo enfoque es un poco más complicado, pero equilibra la carga de manera más uniforme si las tareas son lo suficientemente precisas (el número de tareas es mucho mayor que el número de subprocesos).

Tenga en cuenta que puede tener problemas al colocar los cálculos en hilos separados. Asegúrese de que bin_index funciona correctamente cuando varios subprocesos lo ejecutan simultáneamente. Tenga cuidado con el uso de variables globales o estáticas para resultados intermedios.

Además, "el histograma [bin_index (i1, i2, i3, i4)] + = 1" podría ser interrumpido por otro hilo, haciendo que el resultado sea incorrecto (si la tarea recupera el valor, lo incrementa y almacena el valor resultante en el formación). Podría introducir un histograma local para cada hilo y combinar los resultados en un solo histograma cuando todos los hilos hayan terminado. También puede asegurarse de que solo un hilo esté modificando el histograma al mismo tiempo, pero eso puede hacer que los hilos se bloqueen la mayor parte del tiempo.

Answer 2

El primer acercamiento es suficiente. No hay necesidad de complicación aquí. Si comienzas a jugar con mutexes, te arriesgas a que sea difícil detectar los errores.

No empieces a complicarte a menos que realmente veas que lo necesitas. Los problemas de sincronización (especialmente en el caso de muchos hilos en lugar de muchos procesos) pueden ser realmente dolorosos.

Answer 3

Según tengo entendido, OpenMP se hizo solo por lo que intentas hacer, aunque tengo que admitir que aún no lo he usado. Básicamente, parece reducirse a simplemente incluir un encabezado y agregar una cláusula pragma.

Probablemente también pueda usar la Biblioteca de bloques de creación de hilos de Intel.

Answer 4

Si alguna vez lo hace en .NET, use las Extensiones Paralelas .

Answer 5

Si desea escribir código de procesamiento de números multiproceso (y lo hará en el futuro), le sugiero que consulte un lenguaje funcional como OCaml o Haskell.

Debido a la falta de efectos secundarios y la falta de estado compartido en los lenguajes funcionales (bueno, principalmente) hacer que su código se ejecute en varios hilos es mucho más fácil. Además, es probable que descubras que terminas con mucho menos código.

Answer 6

Si nunca codificaste una aplicación de varios subprocesos, te descubrí para comenzar con OpenMP:

• la biblioteca ahora está incluida en gcc de forma predeterminada
• esto es muy fácil de usar

En su ejemplo, solo debe agregar este pragma:

#pragma omp parallel shared(histogram)
{
for (int i1 = 0; i1 < N; i1++)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        histogram[bin_index(i1, i2, i3, i4)] += 1;
}

Con este pragma, el compilador agregará algunas instrucciones para crear subprocesos, ejecutarlos, agregar algunos mutex alrededor de los accesos a la variable de histogram , etc ... Hay muchas opciones, pero pragma bien definido hacen todo el trabajo por usted. Básicamente, la simplicidad depende de la dependencia de datos.

Por supuesto, el resultado no debería ser óptimo, como si codificaras todo a mano. Pero si no tiene un problema de equilibrio de carga, tal vez podría acercarse a una velocidad de 2x. En realidad, esto es solo escribir en matriz sin dependencia espacial.

Answer 7

Estoy de acuerdo con Sharptooth en que su primer enfoque parece ser el único plausible.

Su aplicación de una sola hebra está asignando continuamente a la memoria. Para obtener cualquier aceleración, sus varios hilos necesitarían también estar asignando continuamente a la memoria. Si solo se asigna un hilo a la vez, no obtendrás ninguna aceleración en absoluto. Entonces, si tus tareas están resguardadas, todo el ejercicio fallará.

Este sería un enfoque peligroso ya que asigna a la memoria compartida sin un guardia. Pero parece que vale la pena el peligro (si una aceleración x2 importa). Si puede estar seguro de que todos los valores de bin_index (i1, i2, i3, i4) son diferentes en su división del ciclo, entonces debería funcionar, ya que la asignación del conjunto sería a diferentes ubicaciones en su memoria compartida. Aún así, uno siempre debe mirar y poner duro a enfoques como este.

Supongo que también produciría una rutina de prueba para comparar los resultados de las dos versiones.

Editar:

Mirando su bin_index (i1, i2, i3, i4), sospecho que su proceso no podría ser paralelizado sin un esfuerzo considerable.

La única manera de dividir el trabajo de cálculo en su bucle es, nuevamente, asegurarse de que sus hilos accedan a las mismas áreas en la memoria. Sin embargo, parece que bin_index (i1, i2, i3, i4) probablemente repita los valores con bastante frecuencia. Puede dividir la iteración en las condiciones donde bin_index es más alto que un punto de corte y donde es menor que un punto de corte. O podría dividirlo arbitrariamente y ver si el incremento se implementa atómicamente. Pero es poco probable que cualquier enfoque de enhebrado complejo proporcione mejoras si para empezar solo puede tener dos núcleos.

Answer 8

Haría algo como esto:

void HistogramThread(int i1, Action<int[]> HandleResults)
{
    int[] histogram = new int[HistogramSize];

    for (int i2 = 0; i2 < N; i2++)
       for (int i3 = 0; i3 < N; i3++)
          for (int i4 = 0; i4 < N; i4++)
             histogram[bin_index(i1, i2, i3, i4)] += 1;

    HandleResults(histogram);
}

int[] CalculateHistogram()
{
    int[] histogram = new int[HistogramSize];

    ThreadPool pool; // I don''t know syntax off the top of my head
    for (int i1=0; i1<N; i1++)
    {
       pool.AddNewThread(HistogramThread, i1, delegate(int[] h)
       {
           lock (histogram)
           {
               for (int i=0; i<HistogramSize; i++)
                   histogram[i] += h[i];
           }
       });
    }
    pool.WaitForAllThreadsToFinish();

    return histogram;
}

De esta forma, no es necesario compartir ninguna memoria, hasta el final.