Распараллеливание цикла for не дает прироста производительности

Синхронизация накладных расходов

Я бы догадался, что объем работы, выполненной за итерацию цикла, слишком мал. Если бы вы разбили изображение на четыре части и выполнили вычисления параллельно, вы бы заметили большой выигрыш. Попытайтесь спроектировать цикл таким образом, чтобы в нем было меньше итераций и больше работы на одну итерацию. Причиной этого является то, что слишком много синхронизации сделано.

Использование кэша

Важным фактором может быть то, как данные разделяются (разбиваются) для обработки. Если обработанные строки разделены как в плохом случае ниже, то больше строк приведет к отсутствию кэша. Этот эффект станет более важным с каждым дополнительным потоком, потому что расстояние между рядами будет больше. Если вы уверены, что функция распараллеливания выполняет разумное разбиение, то ручное разделение работы не даст никаких результатов.

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

Также убедитесь, что вы получить доступ к вашим данным так же, как они выровнены; возможно, что каждый звонок offset[] а также BayerChannel[] промах кеша Ваш алгоритм очень интенсивно использует память. Почти все операции либо обращаются к сегменту памяти, либо записывают в него. Предотвращение пропадания кэша и минимизация доступа к памяти имеют решающее значение

Оптимизация кода

приведенные ниже оптимизации могут быть выполнены компилятором и могут не дать лучших результатов. Стоит знать, что они могут быть сделаны.

    // 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];
}
});

Вот мое предложение:

1. Компьютер больше кусков параллельно
2. избавиться от модуля / умножения

3. развернуть внутренний цикл для вычисления одного полного пикселя (упрощает код)

   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];
   }
   }
   });
   }
   

Этот код работает на 60% быстрее, чем оригинальная версия, но все еще вдвое быстрее, чем непараллельная версия на моем ноутбуке. Похоже, это связано с ограниченностью памяти алгоритма, как уже указывали другие.

Редактировать: Но я не был доволен этим. Я мог бы значительно улучшить параллельную производительность при переходе от parallel_for в 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;

с конвертером, являющимся простым классом:

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;
};

Теперь это в 3,5 раза быстрее, чем непараллельная версия. Из того, что я видел в профилировщике до сих пор, я предполагаю, что подход к краже работы Parallel_for влечет за собой большие затраты на ожидание и синхронизацию.

Я не использовал tbb :: parallel_for, а не cuncurrency :: parallel_for, но если ваши числа верны, они, похоже, несут слишком много накладных расходов. Тем не менее, я настоятельно рекомендую вам выполнить более 10 итераций при тестировании, а также обязательно выполнить столько же итераций разогрева до начала времени.

Я протестировал ваш код точно, используя три разных метода, в среднем более 1000 попыток.

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

Первый — это последовательный расчет. Второе выполняется с помощью четырех вызовов std :: async. Последнее делается путем отправки четырех заданий четырем уже запущенным (но спящим) фоновым потокам.

Прибыль не большая, но, по крайней мере, это прибыль. Я проводил тестирование на MacBook Pro 2012 года с двумя гиперпоточными ядрами = 4 логическими ядрами.

Для справки вот моя параллель std :: async для:

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();
}
}

Вещи, чтобы проверить или сделать

• Вы используете процессор Core 2 или более старый? У них очень узкая шина памяти это легко насытить таким кодом. В отличие от 4-канальных процессоров Sandy Bridge-E требовать несколько потоков для насыщения шины памяти (невозможно, чтобы один поток, связанный с памятью, полностью насыщал ее).
• Вы заселили все свои каналы памяти? Например. если у вас двухканальный процессор, но установлена ​​только одна карта ОЗУ или две на одном канале, вы получаете половину доступной пропускной способности.
• Как твои дела синхронизация ваш код?
  • Время должно быть сделано внутри приложения, как предлагает Евгений Панасюк.
  • Вы должны сделать несколько запусков в одном приложении. В противном случае вы можете синхронизировать одноразовый код запуска для запуска пулов потоков и т. Д.
• Убрать лишнее memset, как объяснили другие.
• Как предположили ogni42 и другие, развертываться Ваш внутренний цикл (я не удосужился проверить правильность этого решения, но если оно не так, вы сможете исправить его). Это ортогонально основному вопросу распараллеливания, но в любом случае это хорошая идея.
• Убедитесь, что ваша машина работает иначе вхолостую при тестировании производительности.

Дополнительные тайминги

Я объединил предложения Евгения Панасюка и ogni42 в простой реализации C23 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;
}

Вот моменты времени, которые я вижу на трехканальном 8-канальном гиперпоточном процессоре Core i7-950:

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

«Статические» версии сообщают компилятору о равномерном распределении работы между потоками при входе в цикл. Это позволяет избежать лишних усилий при попытке кражи работы или другой динамической балансировки нагрузки. Для этого фрагмента кода это, похоже, не имеет значения, хотя рабочая нагрузка очень равномерна по потокам.

Снижение производительности может происходить из-за того, что вы пытаетесь распределить циклы по «ряду» по числу ядер, которые не будут доступны, и, следовательно, это снова станет последовательным выполнением с издержками параллелизма.

Не очень знаком с параллельными циклами for, но мне кажется, что спор заключается в доступе к памяти. Похоже, ваши темы перекрывают доступ к одним и тем же страницам.

Можете ли вы разбить ваш доступ к массиву на 4k фрагментов, несколько выровненных по границе страницы?

Нет смысла говорить о параллельной производительности, пока не оптимизировали цикл for для последовательного кода. Вот моя попытка сделать это (некоторые хорошие компиляторы могут получить аналогично оптимизированные версии, но я бы предпочел не полагаться на это)

    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];
}
});