c++ - resueltos - paralelización significado

La paralelización de un bucle for no da ganancia de rendimiento

Question

Tengo un algoritmo que convierte un canal de imagen de bayer a RGB. En mi implementación tengo un solo bucle anidado que itera sobre el canal de bayer, calcula el índice rgb a partir del índice de bayer y luego establece el valor de ese píxel del canal de bayer. Lo principal que hay que notar aquí es que cada píxel se puede calcular independientemente de otros píxeles (no se basa en cálculos anteriores) y, por lo tanto, el algoritmo es un candidato natural para la parallización. Sin embargo, el cálculo se basa en algunas matrices preestablecidas a las que todos los subprocesos accederán al mismo tiempo pero no cambiarán.

Sin embargo, cuando traté de paralelizar el main for con la cuncurrency::parallel_for de MS cuncurrency::parallel_for no gané ningún impulso en el rendimiento. De hecho, para una entrada de tamaño 3264X2540 que se ejecuta en una CPU de 4 núcleos, la versión no paralelizada se ejecutó en ~ 34 ms y la versión en paralelo se ejecutó en ~ 69 ms (un promedio de más de 10 corridas). Confirmé que la operación fue paralelizada (se crearon 3 nuevos hilos para la tarea).

El uso del compilador de Intel con tbb::parallel_for dio resultados casi exactos. A modo de comparación, comencé con este algoritmo implementado en C# en el que también usé parallel_for y allí encontré ganancias de rendimiento cercanas al X4 (opté por C++ porque para esta tarea en particular, C++ era más rápido incluso con un solo núcleo).

¿Alguna idea de lo que impide que mi código se paralice bien?

Mi código:

template<typename T>
void static ConvertBayerToRgbImageAsIs(T* BayerChannel, T* RgbChannel, int Width, int Height, ColorSpace ColorSpace)
{
        //Translates index offset in Bayer image to channel offset in RGB image
        int offsets[4];
        //calculate offsets according to color space
        switch (ColorSpace)
        {
        case ColorSpace::BGGR:
            offsets[0] = 2;
            offsets[1] = 1;
            offsets[2] = 1;
            offsets[3] = 0;
            break;
        ...other color spaces
        }
        memset(RgbChannel, 0, Width * Height * 3 * sizeof(T));
        parallel_for(0, Height, [&] (int row)
        {
            for (auto col = 0, bayerIndex = row * Width; col < Width; col++, bayerIndex++)
            {
                auto offset = (row%2)*2 + (col%2); //0...3
                auto rgbIndex = bayerIndex * 3 + offsets[offset];
                RgbChannel[rgbIndex] = BayerChannel[bayerIndex];
            }
        });
}

Answer 1

Gastos generales de sincronización

Supongo que la cantidad de trabajo realizado por iteración del bucle es demasiado pequeña . Si hubieras dividido la imagen en cuatro partes y ejecutado el cálculo en paralelo, habrías notado una gran ganancia. Intente diseñar el bucle de manera que se generen menos iteraciones y más trabajo por iteración . El razonamiento detrás de esto es que hay demasiada sincronización hecha.

Uso de caché

Un factor importante puede ser cómo los datos se dividen (particionan) para el procesamiento. Si las filas procesadas se separan como en el caso incorrecto a continuación, más filas causarán una falla de caché . Este efecto será más importante con cada subproceso adicional, porque la distancia entre filas será mayor. Si está seguro de que la función de paralelización realiza una partición razonable, la división manual del trabajo no dará ningún resultado

 bad       good
****** t1 ****** t1
****** t2 ****** t1
****** t1 ****** t1
****** t2 ****** t1
****** t1 ****** t2
****** t2 ****** t2
****** t1 ****** t2
****** t2 ****** t2

Asegúrese también de que accede a sus datos de la misma manera que están alineados ; es posible que cada llamada a offset[] y BayerChannel[] sea ​​una falta de caché. Su algoritmo es muy intensivo de memoria. Casi todas las operaciones son acceder a un segmento de memoria o escribir en él. Es crucial prevenir las fallas de caché y minimizar el acceso a la memoria.

Optimizaciones de código

Las optimizaciones que se muestran a continuación pueden ser realizadas por el compilador y pueden no dar mejores resultados. Vale la pena saber que se pueden hacer.

    // is the memset really necessary?
    //memset(RgbChannel, 0, Width * Height * 3 * sizeof(T));
    parallel_for(0, Height, [&] (int row)
    {
        int rowMod = (row & 1) << 1;
        for (auto col = 0, bayerIndex = row * Width, tripleBayerIndex=row*Width*3; col < Width; col+=2, bayerIndex+=2, tripleBayerIndex+=6)
        {
            auto rgbIndex = tripleBayerIndex + offsets[rowMod];
            RgbChannel[rgbIndex] = BayerChannel[bayerIndex];

            //unrolled the loop to save col & 1 operation
            rgbIndex = tripleBayerIndex + 3 + offsets[rowMod+1];
            RgbChannel[rgbIndex] = BayerChannel[bayerIndex+1];
        }
    });

Answer 2

Aquí viene mi sugerencia:

1. Trozos de ordenador más grandes en paralelo.
2. deshacerse de módulo / multiplicación

3. desenrollar el bucle interno para calcular un píxel completo (simplifica el código)

   template<typename T> void static ConvertBayerToRgbImageAsIsNew(T* BayerChannel, T* RgbChannel, int Width, int Height)
   {
       // convert BGGR->RGB
       // have as many threads as the hardware concurrency is
       parallel_for(0, Height, static_cast<int>(Height/(thread::hardware_concurrency())), [&] (int stride)
       {
           for (auto row = stride; row<2*stride; row++)
           {
               for (auto col = row*Width, rgbCol =row*Width; col < row*Width+Width; rgbCol +=3, col+=4)
               {
                   RgbChannel[rgbCol+0]  = BayerChannel[col+3];
                   RgbChannel[rgbCol+1]  = BayerChannel[col+1];
                   // RgbChannel[rgbCol+1] += BayerChannel[col+2]; // this line might be left out if g is used unadjusted
                   RgbChannel[rgbCol+2]  = BayerChannel[col+0];
               }
           }
       });
   }

Este código es 60% más rápido que la versión original, pero sigue siendo solo la mitad de rápido que la versión no paralelizada en mi computadora portátil. Esto parece deberse a la limitación de memoria del algoritmo, como otros ya han señalado.

Edit: Pero no estaba feliz con eso. Podría mejorar enormemente el rendimiento paralelo al pasar de parallel_for a std::async :

int hc = thread::hardware_concurrency();
future<void>* res = new future<void>[hc];
for (int i = 0; i<hc; ++i)
{
    res[i] = async(Converter<char>(bayerChannel, rgbChannel, rows, cols, rows/hc*i, rows/hc*(i+1)));
}
for (int i = 0; i<hc; ++i)
{
    res[i].wait();
}
delete [] res;

siendo el convertidor una clase simple:

template <class T> class Converter
{
public:
Converter(T* BayerChannel, T* RgbChannel, int Width, int Height, int startRow, int endRow) : 
    BayerChannel(BayerChannel), RgbChannel(RgbChannel), Width(Width), Height(Height), startRow(startRow), endRow(endRow)
{
}
void operator()()
{
    // convert BGGR->RGB
    for(int row = startRow; row < endRow; row++)
    {
        for (auto col = row*Width, rgbCol =row*Width; col < row*Width+Width; rgbCol +=3, col+=4)
        {
            RgbChannel[rgbCol+0]  = BayerChannel[col+3];
            RgbChannel[rgbCol+1]  = BayerChannel[col+1];
            // RgbChannel[rgbCol+1] += BayerChannel[col+2]; // this line might be left out if g is used unadjusted
            RgbChannel[rgbCol+2]  = BayerChannel[col+0];
        }
    };
}
private:
T* BayerChannel;
T* RgbChannel;
int Width;
int Height;
int startRow;
int endRow;
};

Esto es ahora 3.5 veces más rápido que la versión no paralelizada. Por lo que he visto en el generador de perfiles hasta ahora, asumo que el enfoque de robo de trabajo de parallel_for incurre en una gran cantidad de espera y sobrecarga de sincronización.

Answer 3

En primer lugar, su algoritmo está limitado por el ancho de banda de la memoria . Esa es la carga de memoria / almacenamiento superaría cualquier cálculo de índice que realice.

Las operaciones de vectores como SSE / AVX tampoco ayudarían, no está realizando ningún cálculo intensivo.

El aumento de la cantidad de trabajo por iteración también es inútil: tanto PPL como TBB son lo suficientemente inteligentes, para no crear subprocesos por iteración, usarían una buena partición, que intentaría además preservar la localidad. Por ejemplo, aquí está la cita de TBB::parallel_for :

Cuando hay subprocesos de trabajo disponibles, parallel_for ejecuta iteraciones es un orden no determinista. No confíe en ningún orden de ejecución particular para la corrección. Sin embargo, para mayor eficiencia, espere paralelismo para tender a operar en corridas de valores consecutivas .

Lo que realmente importa es reducir las operaciones de memoria. Cualquier recorrido superfluo sobre la entrada o el búfer de salida es venenoso para el rendimiento, por lo que debe intentar eliminar su memset o hacerlo en paralelo también.

Usted está atravesando completamente los datos de entrada y salida. Incluso si omite algo en la salida, eso no importa, ya que las operaciones de memoria se realizan mediante fragmentos de 64 bytes en el hardware moderno. Entonces, calcule el size de su entrada y salida, mida el time del algoritmo, divida el size / time y compare el resultado con las características máximas de su sistema (por ejemplo, mida con un benchmark ).

Los resultados son (usé 8x de tu altura): he realizado pruebas para Microsoft PPL , OpenMP y Native for :

Native_For       0.21 s
OpenMP_For       0.15 s
Intel_TBB_For    0.15 s
MS_PPL_For       0.15 s

Si quita memset entonces:

Native_For       0.15 s
OpenMP_For       0.09 s
Intel_TBB_For    0.09 s
MS_PPL_For       0.09 s

Como puede ver, memset (que está altamente optimizado) es responsable por una cantidad significativa de tiempo de ejecución, que muestra cómo su algoritmo está limitado por la memoria.

CÓDIGO FUENTE COMPLETO :

#include <boost/exception/detail/type_info.hpp>
#include <boost/mpl/for_each.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/progress.hpp>
#include <tbb/tbb.h>
#include <iostream>
#include <ostream>
#include <vector>
#include <string>
#include <omp.h>
#include <ppl.h>

using namespace boost;
using namespace std;

const auto Width = 3264;
const auto Height = 2540*8;

struct MS_PPL_For
{
    template<typename F,typename Index>
    void operator()(Index first,Index last,F f) const
    {
        concurrency::parallel_for(first,last,f);
    }
};

struct Intel_TBB_For
{
    template<typename F,typename Index>
    void operator()(Index first,Index last,F f) const
    {
        tbb::parallel_for(first,last,f);
    }
};

struct Native_For
{
    template<typename F,typename Index>
    void operator()(Index first,Index last,F f) const
    {
        for(; first!=last; ++first) f(first);
    }
};

struct OpenMP_For
{
    template<typename F,typename Index>
    void operator()(Index first,Index last,F f) const
    {
        #pragma omp parallel for
        for(auto i=first; i<last; ++i) f(i);
    }
};

template<typename T>
struct ConvertBayerToRgbImageAsIs
{
    const T* BayerChannel;
    T* RgbChannel;
    template<typename For>
    void operator()(For for_)
    {
        cout << type_name<For>() << "/t";
        progress_timer t;
        int offsets[] = {2,1,1,0};
        //memset(RgbChannel, 0, Width * Height * 3 * sizeof(T));
        for_(0, Height, [&] (int row)
        {
            for (auto col = 0, bayerIndex = row * Width; col < Width; col++, bayerIndex++)
            {
                auto offset = (row % 2)*2 + (col % 2); //0...3
                auto rgbIndex = bayerIndex * 3 + offsets[offset];
                RgbChannel[rgbIndex] = BayerChannel[bayerIndex];
            }
        });
    }
};

int main()
{
    vector<float> bayer(Width*Height);
    vector<float> rgb(Width*Height*3);
    ConvertBayerToRgbImageAsIs<float> work = {&bayer[0],&rgb[0]};
    for(auto i=0;i!=4;++i)
    {
        mpl::for_each<mpl::vector<Native_For, OpenMP_For,Intel_TBB_For,MS_PPL_For>>(work);
        cout << string(16,''_'') << endl;
    }
}

Answer 4

La reducción de rendimiento podría estar ocurriendo porque está intentando distribuir para el bucle en la "fila" número de núcleos, que no estarán disponibles y, por lo tanto, de nuevo se convertirá en una ejecución secuencial con la sobrecarga del paralelismo.

Answer 5

No estoy muy familiarizado con el paralelo para los bucles, pero me parece que la contención está en el acceso a la memoria. Parece que sus hilos están superpuestos al acceso a las mismas páginas.

¿Se puede dividir el acceso a la matriz en segmentos de 4k de forma que se alinee con el límite de la página?

Answer 6

No he usado tbb :: parallel_for not quuncurrency :: parallel_for, pero si sus números son correctos, parecen tener demasiada sobrecarga. Sin embargo, le recomiendo encarecidamente que ejecute más de 10 iteraciones al realizar las pruebas, y también asegúrese de hacer tantas iteraciones de calentamiento antes de la sincronización.

Probé su código exactamente usando tres métodos diferentes, con un promedio de más de 1000 intentos.

Serial:      14.6 += 1.0  ms
std::async:  13.6 += 1.6  ms
workers:     11.8 += 1.2  ms

El primero es el cálculo en serie. El segundo se hace usando cuatro llamadas a std :: async. Lo último se hace enviando cuatro trabajos a cuatro subprocesos de fondo ya iniciados (pero en reposo).

Las ganancias no son grandes, pero al menos son ganancias. Hice la prueba en un MacBook Pro 2012, con dos núcleos con hiperhilos = 4 núcleos lógicos.

Para referencia, aquí está mi std :: async paralelo para:

template<typename Int=int, class Fun>
void std_par_for(Int beg, Int end, const Fun& fun)
{
    auto N = std::thread::hardware_concurrency();
    std::vector<std::future<void>> futures;

    for (Int ti=0; ti<N; ++ti) {
        Int b = ti * (end - beg) / N;
        Int e = (ti+1) * (end - beg) / N;
        if (ti == N-1) { e = end; }

        futures.emplace_back( std::async([&,b,e]() {
            for (Int ix=b; ix<e; ++ix) {
                fun( ix );
            }
        }));
    }

    for (auto&& f : futures) {
        f.wait();
    }
}

Answer 7

No tiene sentido hablar de rendimiento paralelo antes de no haber optimizado el bucle for para el código de serie. Aquí está mi intento de hacerlo (algunos compiladores buenos pueden obtener versiones optimizadas de manera similar, pero prefiero no confiar en eso)

    parallel_for(0, Height, [=] (int row) noexcept
    {
        for (auto col=0, bayerindex=row*Width,
                  rgb0=3*bayerindex+offset[(row%2)*2],
                  rgb1=3*bayerindex+offset[(row%2)*2+1];
             col < Width; col+=2, bayerindex+=2, rgb0+=6, rgb1+=6 )
        {
            RgbChannel[rgb0] = BayerChannel[bayerindex  ];
            RgbChannel[rgb1] = BayerChannel[bayerindex+1];
        }
    }); 

Answer 8

Cosas para revisar o hacer

• ¿Está utilizando un procesador Core 2 o anterior? Tienen un bus de memoria muy estrecho que es fácil de saturar con un código como este. En contraste, los procesadores Sandy Bridge-E de 4 canales requieren múltiples hilos para saturar el bus de memoria (no es posible que un solo hilo enlazado a memoria lo sature por completo).
• ¿Has poblado todos tus canales de memoria ? Por ejemplo, si tiene una CPU de doble canal pero solo tiene una tarjeta RAM instalada o dos que están en el mismo canal, está obteniendo la mitad del ancho de banda disponible.
• ¿Cómo estás sincronizando tu código?
  
  • El tiempo debe hacerse dentro de la aplicación, como sugiere Evgeny Panasyuk.
  • Debe hacer varias ejecuciones dentro de la misma aplicación. De lo contrario, es posible que esté sincronizando el código de inicio único para iniciar los grupos de subprocesos, etc.
• Retire el memset superfluo, como han explicado otros.
• Como lo han sugerido ogni42 y otros, desenrolle su bucle interno (no me molesté en verificar la corrección de esa solución, pero si está mal, debería poder arreglarlo). Esto es ortogonal a la cuestión principal de la paralelización, pero es una buena idea de todos modos.
• Asegúrese de que su máquina esté inactiva cuando realice pruebas de rendimiento.

Tiempos adicionales

He fusionado las sugerencias de Evgeny Panasyuk y ogni42 en una implementación básica de C ++ 03 Win23:

#include "stdafx.h"

#include <omp.h>
#include <vector>
#include <iostream>
#include <stdio.h>

using namespace std;

const int Width = 3264;
const int Height = 2540*8;

class Timer {
private:
    string name;
    LARGE_INTEGER start;
    LARGE_INTEGER stop;
    LARGE_INTEGER frequency;
public:
    Timer(const char *name) : name(name) {
        QueryPerformanceFrequency(&frequency);
        QueryPerformanceCounter(&start);
    }

    ~Timer() {
        QueryPerformanceCounter(&stop);
        LARGE_INTEGER time;
        time.QuadPart = stop.QuadPart - start.QuadPart;
        double elapsed = ((double)time.QuadPart /(double)frequency.QuadPart);
        printf("%-20s : %5.2f/n", name.c_str(), elapsed);
    }
};

static const int offsets[] = {2,1,1,0};

template <typename T>
void Inner_Orig(const T* BayerChannel, T* RgbChannel, int row)
{
    for (int col = 0, bayerIndex = row * Width;
         col < Width; col++, bayerIndex++)
    {
        int offset = (row % 2)*2 + (col % 2); //0...3
        int rgbIndex = bayerIndex * 3 + offsets[offset];
        RgbChannel[rgbIndex] = BayerChannel[bayerIndex];
    }
}

// adapted from ogni42''s answer
template <typename T>
void Inner_Unrolled(const T* BayerChannel, T* RgbChannel, int row)
{
    for (int col = row*Width, rgbCol =row*Width;
         col < row*Width+Width; rgbCol +=3, col+=4)
    {
        RgbChannel[rgbCol+0]  = BayerChannel[col+3];
        RgbChannel[rgbCol+1]  = BayerChannel[col+1];
        // RgbChannel[rgbCol+1] += BayerChannel[col+2]; // this line might be left out if g is used unadjusted
        RgbChannel[rgbCol+2]  = BayerChannel[col+0];
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    vector<float> bayer(Width*Height);
    vector<float> rgb(Width*Height*3);
    for(int i = 0; i < 4; ++i)
    {
        {
            Timer t("serial_orig");
            for(int row = 0; row < Height; ++row) {
                Inner_Orig<float>(&bayer[0], &rgb[0], row);
            }
        }
        {
            Timer t("omp_dynamic_orig");
            #pragma omp parallel for
            for(int row = 0; row < Height; ++row) {
                Inner_Orig<float>(&bayer[0], &rgb[0], row);
            }
        }
        {
            Timer t("omp_static_orig");
            #pragma omp parallel for schedule(static)
            for(int row = 0; row < Height; ++row) {
                Inner_Orig<float>(&bayer[0], &rgb[0], row);
            }
        }

        {
            Timer t("serial_unrolled");
            for(int row = 0; row < Height; ++row) {
                Inner_Unrolled<float>(&bayer[0], &rgb[0], row);
            }
        }
        {
            Timer t("omp_dynamic_unrolled");
            #pragma omp parallel for
            for(int row = 0; row < Height; ++row) {
                Inner_Unrolled<float>(&bayer[0], &rgb[0], row);
            }
        }
        {
            Timer t("omp_static_unrolled");
            #pragma omp parallel for schedule(static)
            for(int row = 0; row < Height; ++row) {
                Inner_Unrolled<float>(&bayer[0], &rgb[0], row);
            }
        }
        printf("-----------------------------/n");
    }
    return 0;
}

Estos son los horarios que veo en una caja Core i7-950 de triple canal y 8 vías:

serial_orig          :  0.13
omp_dynamic_orig     :  0.10
omp_static_orig      :  0.10
serial_unrolled      :  0.06
omp_dynamic_unrolled :  0.04
omp_static_unrolled  :  0.04

Las versiones "estáticas" le dicen al compilador que divida uniformemente el trabajo entre los hilos en la entrada del bucle. Esto evita la sobrecarga de intentar realizar un robo de trabajo u otro equilibrio dinámico de carga. Para este fragmento de código, no parece hacer una diferencia, a pesar de que la carga de trabajo es muy uniforme en todos los subprocesos.