Как я могу заставить этот код достичь ожидаемого 7-кратного ускорения за счет параллелизма? ⇐ C++

[Anonymous]

Я пытаюсь решить первую задачу из первого задания из Стэнфордского курса CS 149. Обратите внимание, что я работаю на четырехъядерном процессоре Macbook Pro i7 с включенной поддержкой гиперпоточности.
Я сначала попробовал простой подход: поток i работает со строками от i/numThreads * height до i + 1 /numThreads * height. С помощью этого подхода мне не удалось добиться ускорения более чем в 2 раза, поэтому я предположил, что проблема заключалась в том, что мои аппаратные кэши загружали целые строки выходного массива. Поскольку каждый поток работал со своей собственной строкой, каждый раз, когда ядро ​​переключалось с одного потока на другой, новый поток удалял текущую строку из кэша.
Путем изменения сигнатуры mandelbrotSerial< /code> чтобы включить параметр шага, тогда мне удалось добиться ускорения примерно в 4 раза при работе с 4 или более потоками. Основная идея состоит в том, чтобы потоки работали с отдельными столбцами внутри каждой строки, чтобы избежать перегрузки кэша.

Код: Выделить всё

void mandelbrotSerial(
float x0, float y0, float x1, float y1,
int width, int height,
int startRow, int totalRows,
int maxIterations,
int output[], int stride, int startIdx)
{
float dx = (x1 - x0) / width;
float dy = (y1 - y0) / height;

int endRow = startRow + totalRows;

for (int j = startRow; j < endRow; j++) {
for (int i = startIdx + 1; i < width; i+=stride) {
float x = x0 + i * dx;
float y = y0 + j * dy;

int index = (j * width + i);
output[index] = mandel(x, y, maxIterations);
}
}
}

Затем я добавил код синхронизации в свою функцию workThreadStart:

Код: Выделить всё

void workerThreadStart(WorkerArgs * const args) {
double startTime = CycleTimer::currentSeconds();
int stride = args->numThreads;
int startIdx = args->threadId;
mandelbrotSerial(
args->x0,
args->y0,
args->x1,
args->y1, args->width, args->height, 0, args->height, args->maxIterations, args->output, stride, startIdx);
double endTime = CycleTimer::currentSeconds();
printf("Hello world from thread %d, stride %d, startIdx %d, time %f\n", args->threadId, stride, startIdx, endTime-startTime);
}

Я заметил интересную закономерность: время выполнения большинства потоков, кроме одного, достигало ~70 мс:

Код: Выделить всё

Hello world from thread 2, stride 8, startIdx 2, time 0.070486
Hello world from thread 4, stride 8, startIdx 4, time 0.070031
Hello world from thread 3, stride 8, startIdx 3, time 0.070382
Hello world from thread 5, stride 8, startIdx 5, time 0.070693
Hello world from thread 1, stride 8, startIdx 1, time 0.072447
Hello world from thread 7, stride 8, startIdx 7, time 0.070525
Hello world from thread 6, stride 8, startIdx 6, time 0.070549
Hello world from thread 0, stride 8, startIdx 0, time 0.103877

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

Код: Выделить всё

void workerThreadStart(WorkerArgs * const args) {
double startTime = CycleTimer::currentSeconds();
int stride = args->threadId == 0 ? args->width / args -> numThreads : args->numThreads - 1;
int startIdx = args->threadId;
mandelbrotSerial(
args->x0,
args->y0,
args->x1,
args->y1, args->width, args->height, 0, args->height, args->maxIterations, args->output, stride, startIdx);
double endTime = CycleTimer::currentSeconds();
printf("Hello world from thread %d, stride %d, startIdx %d, time %f\n", args->threadId, stride, startIdx, endTime-startTime);
}

При таком подходе я постоянно получаю ускорение примерно в 5,2 раза:

Код: Выделить всё

Hello world from thread 0, stride 200, startIdx 0, time 0.004734
Hello world from thread 4, stride 7, startIdx 4, time 0.086578
Hello world from thread 1, stride 7, startIdx 1, time 0.089177
Hello world from thread 3, stride 7, startIdx 3, time 0.091931
Hello world from thread 2, stride 7, startIdx 2, time 0.092376
Hello world from thread 5, stride 7, startIdx 5, time 0.092791
Hello world from thread 7, stride 7, startIdx 7, time 0.094090
Hello world from thread 6, stride 7, startIdx 6, time 0.094883
[mandelbrot thread]:            [91.795] ms
Wrote image file mandelbrot-thread.ppm
(5.28x speedup from 8 threads)

Метод mandelbrotThread выглядит следующим образом:

Код: Выделить всё

//
// MandelbrotThread --
//
// Multi-threaded implementation of mandelbrot set image generation.
// Threads of execution are created by spawning std::threads.
void mandelbrotThread(
int numThreads,
float x0, float y0, float x1, float y1,
int width, int height,
int maxIterations, int output[])
{
static constexpr int MAX_THREADS = 32;

if (numThreads > MAX_THREADS)
{
fprintf(stderr, "Error: Max allowed threads is %d\n", MAX_THREADS);
exit(1);
}

// Creates thread objects that do not yet represent a thread.
std::thread workers[MAX_THREADS];
WorkerArgs args[MAX_THREADS];

for (int i=0; i

Подробнее здесь: [url]https://stackoverflow.com/questions/76692330/how-can-i-make-this-code-achieve-the-expected-7x-speedup-through-parallelism[/url]