C ++ OpenMP Parallel For Loop – Alternativas a std :: vector

Basado en este hilo, OpenMP y STL vector , ¿qué estructuras de datos son buenas alternativas para un std :: vector compartido en un bucle for paralelo? El aspecto principal es la velocidad, y el vector podría requerir un cambio de tamaño durante el ciclo.

La pregunta que vinculó fue sobre el hecho de que “ese contenedor de vector STL no es seguro para subprocesos en una situación en la que varios hilos escriben en un único contenedor”. Esto solo es cierto, como se indica correctamente allí, si llama a métodos que pueden causar una reasignación de la matriz subyacente que std::vector tiene. push_back() , pop_back() e insert() son ejemplos de estos métodos peligrosos.

Si necesita una reasignación segura de subprocesos, el bloque de creación de subprocesos de la biblioteca intel le ofrece contenedores de vectores concurrentes . No debe usar tbb :: concurrent_vector en progtwigs de subproceso único porque el tiempo que lleva acceder a elementos aleatorios es mayor que el tiempo que std :: vector tarda en hacer lo mismo (que es O (1)). Sin embargo, el vector concurrente llama a push_back() , pop_back() , insert() de una manera segura para el hilo, incluso cuando ocurre la reasignación.

EDIT 1: Las diapositivas 46 y 47 de la siguiente presentación de Intel dan un ejemplo ilustrativo de reasignación concurrente usando tbb :: concurrent_vector

EDIT 2: Por cierto, si comienzas a usar Intel Tread Building Block (es de código abierto, funciona con la mayoría de los comstackdores y está mucho mejor integrado con C ++ / C ++ 11 que con openmp), entonces no necesitas para usar openmp para crear un parallel_for, aquí hay un buen ejemplo de parallel_for using tbb.

Creo que puedes usar std::vector con OpenMP la mayor parte del tiempo y aún así tener un buen rendimiento. El siguiente código, por ejemplo, llena std::vectors en paralelo y luego los combina al final. Siempre que su función principal de bucle / llenado sea el cuello de botella, esto debería funcionar bien en general y ser seguro para hilos.

 std::vector vec; #pragma omp parallel { std::vector vec_private; #pragma omp for nowait //fill vec_private in parallel for(int i=0; i<100; i++) { vec_private.push_back(i); } #pragma omp critical vec.insert(vec.end(), vec_private.begin(), vec_private.end()); } 

Editar:

OpenMP 4.0 permite reducciones definidas por el usuario usando #pragma omp declare reduction . El código anterior se puede simplificar con a

 #pragma omp declare reduction (merge : std::vector : omp_out.insert(omp_out.end(), omp_in.begin(), omp_in.end())) std::vector vec; #pragma omp parallel for reduction(merge: vec) for(int i=0; i<100; i++) vec.push_back(i); 

Editar: Lo que he mostrado hasta ahora no llena el vector en orden. Si el orden es importante, esto se puede hacer así

 std::vector vec; #pragma omp parallel { std::vector vec_private; #pragma omp for nowait schedule(static) for(int i=0; i 

Esto evita guardar un std :: vector para cada hilo y luego fusionarlos en serie fuera de la región paralela. Aprendí acerca de este "truco" aquí . No estoy seguro de cómo hacer esto (o si es posible) para las reducciones definidas por el usuario. . No es posible hacer esto con reducciones definidas por el usuario.

Me acabo de dar cuenta de que la sección crítica no es necesaria, lo que averigué a partir de esta pregunta paralela-acumulativa-prefijo-sums-en-apertura-comunicación-valores-entre-hilo . Este método también consigue el orden correcto también

 std::vector vec; size_t *prefix; #pragma omp parallel { int ithread = omp_get_thread_num(); int nthreads = omp_get_num_threads(); #pragma omp single { prefix = new size_t[nthreads+1]; prefix[0] = 0; } std::vector vec_private; #pragma omp for schedule(static) nowait for(int i=0; i<100; i++) { vec_private.push_back(i); } prefix[ithread+1] = vec_private.size(); #pragma omp barrier #pragma omp single { for(int i=1; i<(nthreads+1); i++) prefix[i] += prefix[i-1]; vec.resize(vec.size() + prefix[nthreads]); } std::copy(vec_private.begin(), vec_private.end(), vec.begin() + prefix[ithread]); } delete[] prefix;