Suma paralela para vectores

Question

¿Podría alguien dar algunas sugerencias sobre cómo puedo disminuir lo siguiente para el tiempo de ejecución del ciclo mediante multihilo? Supongamos que también tengo dos vectores llamados 'a' y 'b'.

for (int j = 0; j < 8000; j++){ 
    // Perform an operation and store in the vector 'a' 
    // Add 'a' to 'b' coefficient wise 
} 

Este bucle for se ejecuta muchas veces en mi programa. Las dos operaciones en el ciclo de arriba para arriba ya están optimizadas, pero solo se ejecutan en un núcleo. Sin embargo, tengo 16 núcleos disponibles y me gustaría utilizarlos.

He intentado modificar el ciclo de la siguiente manera. En lugar de tener el vector 'a', tengo 16 vectores, y supongo que el i-ésimo se llama un [i]. Mi bucle ahora se ve como

for (int j = 0; j < 500; j++){ 
    for (int i = 0; i < 16; i++){ 
     // Perform an operation and store in the vector 'a[i]' 
    } 
    for (int i = 0; i < 16; i++){ 
     // Add 'a[i]' to 'b' coefficient wise 
    } 

} 

utilizo el OpenMP en cada uno de los bucles en el interior mediante la adición de 'omp paralelo para #pragma' antes de cada uno de los bucles internos. Todos mis procesadores están en uso, pero mi tiempo de ejecución solo aumenta significativamente. ¿Alguien tiene alguna sugerencia sobre cómo puedo disminuir el tiempo de ejecución de este ciclo? Gracias de antemano.

Answer 1

omp crea subprocesos para su programa dondequiera que inserte la etiqueta pragma, por lo que crea subprocesos para etiquetas internas pero el problema es que se crean 16 subprocesos, cada uno realiza 1 operación y luego todos se destruyen con su método. crear y destruir subprocesos lleva mucho tiempo, por lo que el método que usaste aumenta el tiempo general de tu proceso aunque usa los 16 núcleos. no tenía que crear fors internos simplemente coloque la etiqueta #pragma omp parallel for antes de que su bucle 8000 sea omp para separar los valores entre las huellas, por lo que lo que hizo para crear el segundo bucle es el trabajo de omp. de esa manera omp crear hilos sólo una vez y luego procesar 500 números useing que cada hilo y el fin de ellos después de que (usando 499 menos la creación del hilo y destrucción)

Answer 2

Does anyone have any suggestions on how I can decrease the runtime of this loop?

for (int j = 0; j < 500; j++){ // outer loop 
    for (int i = 0; i < 16; i++){ // inner loop 

Siempre trate de hacer exterior iteraciones de bucle menores que bucle interno. Esto le ahorrará desde inicializaciones de bucle interno que muchas veces. En el código anterior, el bucle interno i = 0; se inicializa 500 veces. Ahora,

for (int i = 0; j < 16; i++){ // outer loop 
    for (int j = 0; j < 500; j++){ // inner loop 

Ahora, j = 0; bucle interno se inicializa sólo 16 veces! Pruebe modificando su código en consecuencia, si tiene algún impacto.

Answer 3

En realidad, voy a poner estos comentarios en una respuesta.

Hilos de bifurcación para operaciones triviales simplemente agrega sobrecarga.

En primer lugar, asegúrese de que el compilador está utilizando instrucciones vectoriales para implementar el bucle. (Si no sabe cómo hacer esto, es posible que tenga código con instrucciones vectoriales usted mismo, tratar de buscar "instrinsics ESS" Pero para este tipo de simple adición de vectores, vectorización automática debería ser posible..)

Asumiendo que su compilador GCC es una bastante moderna, con lo invocan:

gcc -O3 -march=native ... 

Añadir -ftree-vectorizer-verbose=2 para averiguar si es o no de auto-vectorizado su bucle y por qué.

Si ya está usando instrucciones vectoriales, entonces es posible que esté saturando el ancho de banda de su memoria. Los núcleos de CPU modernos son bastante rápidos ... Si es así, necesitas reestructurar a un nivel más alto para obtener más operaciones dentro de cada iteración del ciclo, encontrando formas de realizar muchas operaciones en bloques que se ajustan dentro de la caché L1.