Генерация изображений Мандельброта в c ++ с использованием многопоточности. Нет ускорения?

void mandelbrot_all(std::vector<std::vector<int>>& pixels, int X, int Y, int numThreads) {
using namespace std;

vector<thread> threads (numThreads);
int rowsPerThread = Y/numThreads;
mutex m;

for(int i=0; i<numThreads; i++) {
threads[i] = thread ([&](){
vector<int> row;
for(int j=(i-1)*rowsPerThread; j<i*rowsPerThread; j++) {
row = mandelbrot_row(j, X, Y);
{
lock_guard<mutex> lock(m);
pixels[j] = row;
}
}
});
}
for(int i=0; i<numThreads; i++) {
threads[i].join();
}
}

std::vector<int> mandelbrot_row(int rowNum, int topX, int topY) {
std::vector<int> row (topX);
for(int i=0; i<topX; i++) {
row[i] = mandelbrotOne(i, rowNum, topX, topY);
}
return row;
}

int mandelbrotOne(int currX, int currY, int X, int Y) { //code adapted from http://en.wikipedia.org/wiki/Mandelbrot_set
double x0 = convert(X, currX, true);
double y0 = convert(Y, currY, false);
double x = 0.0;
double y = 0.0;
double xtemp;
int iteration = 0;
int max_iteration = 255;
while ( x*x + y*y < 2*2  &&  iteration < max_iteration) {
xtemp = x*x - y*y + x0;
y = 2*x*y + y0;
x = xtemp;
++iteration;
}
return iteration;
}

Ваш код может выполнять параллельную обработку, но на практике это не так.
По сути, вы тратите свое время на копирование данных и на очереди для доступа к распределителю памяти.

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

Как обычно, C ++ скрывает эти печальные факты от вас под толстой коркой синтаксического сахара.

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

Поскольку этот пример кажется мне учебником параллельной обработки, и я никогда не видел его «образовательного» анализа, я попробую один.

Функциональный анализ

Вы хотите использовать все ядра процессора для сокращения пикселей набора Мандельброта. Это идеальный случай распараллеливаемых вычислений, поскольку вычисление каждого пикселя может выполняться независимо.

Таким образом, в основном, если на вашей машине N ядер, у вас должен быть ровно один поток на ядро, выполняющий 1 / N обработки.

К сожалению, разделение входных данных таким образом, чтобы каждый процессор выполнял 1 / N необходимой обработки, не так очевидно, как может показаться.

Для вычисления данного пикселя может потребоваться от 0 до 255 итераций. «черные» пиксели В 255 раз дороже чем «белые».

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

В реальных случаях это будет не так драматично, но все равно огромная потеря вычислительной мощности.

Балансировки нагрузки

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

В идеале чанки должны быть отсортированы по убыванию сложности, чтобы избежать добавления линейной стоимости большого чанка к общему времени вычислений.

К сожалению, из-за хаотической природы множества Мандлброта, нет никакого практического способа предсказать время вычисления данной области.

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

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

Вот два вывода моего доказательства реализации концепции:

Задания выполняются в обратном порядке (задания 39 — первые, задания 0 — последние).
Каждая строка декодируется следующим образом:

T a-b: резьба n ° a на процессоре b
б : время начала (с начала вычисления изображения)
е : время окончания
d : продолжительность (все время в миллисекундах)

1) 40 заданий с заказом бабочки

job  0: t 1-1  b 162 e 174 d  12 // the 4 tasks finish within 5 ms from each other
job  1: t 0-0  b 156 e 176 d  20 //
job  2: t 2-2  b 155 e 173 d  18 //
job  3: t 3-3  b 154 e 174 d  20 //
job  4: t 1-1  b 141 e 162 d  21
job  5: t 2-2  b 137 e 155 d  18
job  6: t 0-0  b 136 e 156 d  20
job  7: t 3-3  b 133 e 154 d  21
job  8: t 1-1  b 117 e 141 d  24
job  9: t 0-0  b 116 e 136 d  20
job 10: t 2-2  b 115 e 137 d  22
job 11: t 3-3  b 113 e 133 d  20
job 12: t 0-0  b  99 e 116 d  17
job 13: t 1-1  b  99 e 117 d  18
job 14: t 2-2  b  96 e 115 d  19
job 15: t 3-3  b  95 e 113 d  18
job 16: t 0-0  b  83 e  99 d  16
job 17: t 3-3  b  80 e  95 d  15
job 18: t 2-2  b  77 e  96 d  19
job 19: t 1-1  b  72 e  99 d  27
job 20: t 3-3  b  69 e  80 d  11
job 21: t 0-0  b  68 e  83 d  15
job 22: t 2-2  b  63 e  77 d  14
job 23: t 1-1  b  56 e  72 d  16
job 24: t 3-3  b  54 e  69 d  15
job 25: t 0-0  b  53 e  68 d  15
job 26: t 2-2  b  48 e  63 d  15
job 27: t 0-0  b  41 e  53 d  12
job 28: t 3-3  b  40 e  54 d  14
job 29: t 1-1  b  36 e  56 d  20
job 30: t 3-3  b  29 e  40 d  11
job 31: t 2-2  b  29 e  48 d  19
job 32: t 0-0  b  23 e  41 d  18
job 33: t 1-1  b  18 e  36 d  18
job 34: t 2-2  b  16 e  29 d  13
job 35: t 3-3  b  15 e  29 d  14
job 36: t 2-2  b   0 e  16 d  16
job 37: t 3-3  b   0 e  15 d  15
job 38: t 1-1  b   0 e  18 d  18
job 39: t 0-0  b   0 e  23 d  23

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

2) 40 заданий с линейным упорядочением

job  0: t 2-2  b 157 e 180 d  23 // last thread lags 17 ms behind first
job  1: t 1-1  b 154 e 175 d  21
job  2: t 3-3  b 150 e 171 d  21
job  3: t 0-0  b 143 e 163 d  20 // 1st thread ends
job  4: t 2-2  b 137 e 157 d  20
job  5: t 1-1  b 135 e 154 d  19
job  6: t 3-3  b 130 e 150 d  20
job  7: t 0-0  b 123 e 143 d  20
job  8: t 2-2  b 115 e 137 d  22
job  9: t 1-1  b 112 e 135 d  23
job 10: t 3-3  b 112 e 130 d  18
job 11: t 0-0  b 105 e 123 d  18
job 12: t 3-3  b  95 e 112 d  17
job 13: t 2-2  b  95 e 115 d  20
job 14: t 1-1  b  94 e 112 d  18
job 15: t 0-0  b  90 e 105 d  15
job 16: t 3-3  b  78 e  95 d  17
job 17: t 2-2  b  77 e  95 d  18
job 18: t 1-1  b  74 e  94 d  20
job 19: t 0-0  b  69 e  90 d  21
job 20: t 3-3  b  60 e  78 d  18
job 21: t 2-2  b  59 e  77 d  18
job 22: t 1-1  b  57 e  74 d  17
job 23: t 0-0  b  55 e  69 d  14
job 24: t 3-3  b  45 e  60 d  15
job 25: t 2-2  b  45 e  59 d  14
job 26: t 1-1  b  43 e  57 d  14
job 27: t 0-0  b  43 e  55 d  12
job 28: t 2-2  b  30 e  45 d  15
job 29: t 3-3  b  30 e  45 d  15
job 30: t 0-0  b  27 e  43 d  16
job 31: t 1-1  b  24 e  43 d  19
job 32: t 2-2  b  13 e  30 d  17
job 33: t 3-3  b  12 e  30 d  18
job 34: t 0-0  b  11 e  27 d  16
job 35: t 1-1  b  11 e  24 d  13
job 36: t 2-2  b   0 e  13 d  13
job 37: t 3-3  b   0 e  12 d  12
job 38: t 1-1  b   0 e  11 d  11
job 39: t 0-0  b   0 e  11 d  11

Здесь дорогостоящие куски имеют тенденцию собираться вместе в конце очереди, что приводит к заметной потере производительности.

3) запуск только с одним заданием на ядро ​​с активированным от одного до четырех ядер

reported cores: 4
Master: start jobs 4 workers 1
job  0: t 0-0  b 410 e 590 d 180 // purely linear execution
job  1: t 0-0  b 255 e 409 d 154
job  2: t 0-0  b 127 e 255 d 128
job  3: t 0-0  b   0 e 127 d 127
Master: start jobs 4 workers 2   // gain factor : 1.6 out of theoretical 2
job  0: t 1-1  b 151 e 362 d 211
job  1: t 0-0  b 147 e 323 d 176
job  2: t 0-0  b   0 e 147 d 147
job  3: t 1-1  b   0 e 151 d 151
Master: start jobs 4 workers 3   // gain factor : 1.82 out of theoretical 3
job  0: t 0-0  b 142 e 324 d 182 // 4th packet is hurting the performance badly
job  1: t 2-2  b   0 e 158 d 158
job  2: t 1-1  b   0 e 160 d 160
job  3: t 0-0  b   0 e 142 d 142
Master: start jobs 4 workers 4   // gain factor : 3 out of theoretical 4
job  0: t 3-3  b   0 e 199 d 199 // finish at 199ms vs. 176 for butterfly 40, 13% loss
job  1: t 1-1  b   0 e 182 d 182 // 17 ms wasted
job  2: t 0-0  b   0 e 146 d 146 // 44 ms wasted
job  3: t 2-2  b   0 e 150 d 150 // 49 ms wasted

Здесь мы получаем 3-кратное улучшение, в то время как лучшее распределение нагрузки могло бы дать 3,5-кратное улучшение.
И это очень мягкий тестовый случай (вы можете видеть, что время вычислений изменяется только примерно в 2 раза, тогда как теоретически они могут варьироваться в 255 раз!).

В любом случае, если вы не реализуете какую-то балансировку нагрузки, весь блестящий многопроцессорный код, который вы могли бы написать, все равно будет приводить к плохой производительности.

Реализация

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

Одним из таких помех является распределение памяти. Каждый раз, когда вы выделяете хотя бы один байт памяти, вы будете ставить в очередь эксклюзивный доступ к глобальному распределителю памяти (и тратить немного ресурсов ЦП на выделение ресурсов).

Кроме того, создание рабочих задач для каждого вычисления изображения — еще одна трата времени и ресурсов. Вычисления могут использоваться для отображения набора мандлеброт в интерактивном приложении, поэтому лучше заранее создавать и синхронизировать рабочие для вычисления последовательных изображений.

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

Очевидное решение — полностью отказаться от копий и работать с исходными данными.

дизайн

Вы должны предоставить своим рабочим потокам все, что им нужно для беспрепятственной работы. Для этого вам необходимо:

• определить количество доступных ядер в вашей системе
• предварительно выделить всю необходимую память
• предоставить доступ к списку фрагментов изображений каждому вашему работнику
• запускать ровно по одному потоку на ядро ​​и позволить им свободно работать

очередь на работу

Нет необходимости в причудливом бездействии или в каких-то штучках, и при этом мы не должны уделять особое внимание оптимизации кэша.
Здесь снова, время, необходимое для вычисления пикселей, уменьшает затраты на синхронизацию между потоками и эффективность кеширования.

По существу, очередь может быть рассчитана как целое в начале генерации изображения. Рабочие должны будут только читать задания из этого: никогда не будет одновременного доступа для чтения / записи в этой очереди, поэтому более или менее стандартные фрагменты кода для реализации очередей заданий будут неоптимальными и слишком сложными для выполняемой работы.

Нам нужны две точки синхронизации:

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

рабочие будут ждать, пока длина очереди не изменится на положительное значение.
Затем они все проснутся и начнут атомарно уменьшать длину очереди. Текущее значение длины очереди предоставит им эксклюзивный доступ к связанным данным задания (в основном это область Mandlebrot, установленная для вычисления, со связанной областью точечного рисунка для хранения вычисленных значений итерации).

Тот же механизм используется для увольнения работников. Вместо того, чтобы найти новую партию рабочих мест, бедные рабочие проснутся, чтобы найти приказ прекратить работу.

мастер, ожидающий завершения изображения, будет пробужден рабочим, который завершит обработку последнего задания. Это будет основано на атомном счетчике количества заданий для обработки.

Вот как я это реализовал:

class synchro {
friend class mandelbrot_calculator;

mutex              lock;    // queue lock
condition_variable work;    // blocks workers waiting for jobs/termination
condition_variable done;    // blocks master waiting for completion
int                pending; // number of jobs in the queue
atomic_int         active;  // number of unprocessed jobs
bool               kill;    // poison pill for workers termination

void synchro (void)
{
pending = 0;  // no job in queue
kill = false; // workers shall live (for now :) )
}

int worker_start(void)
{
unique_lock<mutex> waiter(lock);
while (!pending && !kill) work.wait(waiter);
return kill
? -1         // worker should die
: --pending; // index of the job to process
}

void worker_done(void)
{
if (!--active) // atomic decrement (exclusive with other workers)
done.notify_one(); // last job processed: wakeup master
}

void master_start(int jobs)
{
unique_lock<mutex> waiter(lock);
pending = active = jobs;
work.notify_all(); // wakeup all workers to start jobs
}

void master_done(void)
{
unique_lock<mutex> waiter(lock);
while (active) done.wait(waiter); // wait for workers to finish
}

void master_kill(void)
{
kill = true;
work.notify_all(); // wakeup all workers (to die)
}
};

Собираем все вместе:

class mandelbrot_calculator {
int      num_cores;
int      num_jobs;
vector<thread> workers; // worker threads
vector<job> jobs;      // job queue
synchro sync;          // synchronization helper

mandelbrot_calculator (int num_cores, int num_jobs)
: num_cores(num_cores)
, num_jobs (num_jobs )
{
// worker thread
auto worker = [&]()
{
for (;;)
{
int job = sync.worker_start(); // fetch next job

if (job == -1) return; // poison pill
process (jobs[job]);   // we have exclusive access to this job

sync.worker_done();    // signal end of picture to the master
}
};

jobs.resize(num_jobs, job()); // computation windows
workers.resize(num_cores);
for (int i = 0; i != num_cores; i++)
workers[i] = thread(worker, i, i%num_cores);
}

~mandelbrot_calculator()
{
// kill the workers
sync.master_kill();
for (thread& worker : workers) worker.join();
}

void compute(const viewport & vp)
{
// prepare worker data
function<void(int, int)> butterfly_jobs;
butterfly_jobs = [&](int min, int max)
// computes job windows in butterfly order
{
if (min > max) return;
jobs[min].setup(vp, max, num_jobs);

if (min == max) return;
jobs[max].setup(vp, min, num_jobs);

int mid = (min + max) / 2;
butterfly_jobs(min + 1, mid    );
butterfly_jobs(mid + 1, max - 1);
};
butterfly_jobs(0, num_jobs - 1);

// launch workers
sync.master_start(num_jobs);

// wait for completion
sync.master_done();
}
};

Тестирование концепции

Этот код очень хорошо работает на моих 2-ядерных / 4-процессорных процессорах Intel I3 @ 3,1 ГГц, скомпилированных с Microsoft Dev Studio 2013.

Я использую немного набора, который имеет в среднем 90 итераций / пиксель в окне 1280×1024 пикселей.

Время расчета составляет около 1.700s только с одним работником и падает до 0.480s с 4 работниками.
Максимально возможный выигрыш будет в 4 раза. Я получу в 3,5 раза. Не так уж плохо.

Полагаю, что это отчасти связано с архитектурой процессора (у I3 только два «настоящих» ядра).

Вмешательство в планировщик

Моя программа заставляет потоки работать на одном ядре (используя MSDN SetThreadAffinityMask).
Если планировщик остается свободным для распределения задач, коэффициент усиления падает с 3,5 до 3,2.

Это важно, но все же планировщик Win7 отлично справляется с работой, когда остается один.

издержки синхронизации

запуск алгоритма в «белом» окне (за пределами < 2) дает хорошее представление о системных издержках.

Для вычисления этой «белой» области требуется около 7 мс, по сравнению с 480 мс типичной области.

Что-то вроде 1,5%, включая как синхронизацию, так и вычисление очереди заданий. И это делает синхронизацию в очереди из 1024 заданий.

Совершенно пренебрежимо, я бы сказал. Это может дать пищу для размышлений всем фанатам очереди без ожидания.

оптимизирующие итерации

То, как выполняются итерации, является ключевым фактором для оптимизации.
После нескольких испытаний я остановился на этом методе:

static inline unsigned char mandelbrot_pixel(double x0, double y0)
{
register double x = x0;
register double y = y0;
register double x2 = x * x;
register double y2 = y * y;
unsigned       iteration = 0;
const int      max_iteration = 255;
while (x2 + y2 < 4.0)
{
if (++iteration == max_iteration) break;
y = 2 * x * y + y0;
x = x2 - y2   + x0;
x2 = x * x;
y2 = y * y;
}
return (unsigned char)iteration;
}

Чистая прибыль: + 20% по сравнению с методом ОП

( register директивы не имеют большого значения, они просто для украшения)

убивая задачи после каждого вычисления

Выгода от того, что рабочие остаются живыми, составляет около 5% времени вычислений.

эффект бабочки

В моем тестовом случае порядок «бабочки» работает очень хорошо, принося более 30% прироста в крайних случаях и обычно 10–15% из-за «распаковки» самых громоздких запросов.