c++ - programacion - vectores en c

find_first de un vector en paralelo en C++

Question

Tengo un vector bastante grande. Algunos de los miembros del vector coinciden con una determinada condición en paralelo. Me gustaría encontrar el primer elemento que coincida con la condición.

Mi problema es muy similar a esta pregunta ( tbb: parallel find first element ), pero no tengo tbb. La condición de comprobación es muy tediosa (por lo tanto, no puedo hacerlo para todos secuencialmente). Es por eso que me gustaría ejecutarlo en paralelo. Debo mencionar que me gustaría encontrar el primer elemento (por lo que la posición del índice del elemento es importante para mí).

Por ejemplo, si tengo 4 hilos.

ThreadNr   Index      condition
1            0         Not Meet
2            1         Not Meet
3            2         Not Meet
4            3         Not Meet

ThreadNr   Index      condition
1            4         Not Meet
2            5          Meet
3            6         Not Meet
4            7          Meet

La función tiene que devolver el número de índice 5. Los hilos deben distribuirse y trabajar en bloques de iteración secuencial (el tamaño del bloque puede ser más de 1. Por ejemplo, el hilo 1 funciona en los primeros 4 elementos, el hilo 2 en los segundos 4 elementos y así en).

Para el ejemplo anterior, si el número de hilo 4 (en el índice 7) encontró el miembro antes del número de hilo 2 (en el índice 5), debe esperar a que todo el hilo termine el trabajo. Como dije antes, el número de índice más bajo es el objetivo.

Por favor corrígeme si tienes un mejor algoritmo en mente.

NOTA: Puedo usar librerías externas como boost 1.62, OpenMP 2.0

Answer 1

Como OpenMP 2.0 no tiene construcciones de cancelación, debe implementar uno por su cuenta, por ejemplo, mediante el uso de una variable compartida. También significa que no se puede usar el constructo de trabajo compartido porque no se permite la ruptura de bucles paralelos (es por eso que OpenMP 4.0 introdujo construcciones de cancelación). Si implementa verificaciones de cancelación entre la evaluación de cada elemento, puede suceder que dos o más subprocesos encuentren elementos que coincidan con el criterio. Por lo tanto, debe realizar una reducción mínima en el índice:

int found = 0;
int first_index = INVALID_VALUE;
int iteration = 0;

#pragma omp parallel
{
   int my_index = INVALID_VALUE;
   int i;

   do
   {
      // Later versions of OpenMP allow for "atomic capture"
      // but OpenMP 2.0 requires a critical directive instead
      #pragma omp critical(iteration)
      {
         i = iteration++;
      }

      if (i < N && check(i))
      {
         found = 1;
         my_index = i;
      }
   } while (!found && i < N);

   #pragma omp critical(reduction)
   if (my_index != INVALID_VALUE)
   {
      if (first_index == INVALID_VALUE || my_index < first_index)
         first_index = my_index;
   }

   // Only needed if more code follows before the end of the region
   #pragma omp barrier

   ...
}

Este código asume que verificar la condición para el elemento i-ésimo ( check(i) ) no altera el estado del elemento, y por lo tanto, lo peor que podría pasar es que el hilo que ha encontrado un elemento coincidente podría tener que esperar para que todos los otros hilos terminen de verificar el elemento en el que trabajan actualmente y ese tiempo de espera será el máximo de todos los tiempos de procesamiento.

La construcción critical utilizada en do-loop es costosa. Si check() no toma tanto tiempo, entonces podría considerar trabajar con fragmentos en lugar de iteraciones:

do
{
   #pragma omp critical(chunk)
   {
       my_chunk = chunk++;
   }

   if (my_chunk >= N_chunks)
      break;

   for (i = my_chunk * chunk_size; !found && i < (my_chunk+1)*chunk_size; i++)
   {
      if (check(i))
      {
         found = 1;
         my_index = i;
         break;
      }
   }
} while (!found && my_chunk < N_chunks);

Otra solución que funciona razonablemente bien cuando la cantidad de elementos no es tan grande y la comprobación de cada uno es costosa:

#pragma omp parallel
{
   #pragma omp for schedule(dynamic,x)
   for (i = 0; i < N; i++)
   {
      if (!found && check(i))
      {
         my_index = i;
         found = 1;
      }
   }

   // Min reduction from the solution above
   ...
}

Una vez found , el resto de las iteraciones de bucle ejecutarán cuerpos "vacíos" porque las propiedades de acceso directo de && .

Answer 2

Con OpenMP puede intentar construir un bucle for con #pragma omp for schedule(dynamic) . Cada hilo ejecutará una iteración en el mismo orden que su vector. Si desea verificar 4 elementos por hilo, intente #pragma omp for schedule(dynamic, 4)