如何通过并行化让曼德博集合代码实现7倍加速？

我正在完成斯坦福大学CS149课程首个作业的首个问题，使用的是开启超线程的i7四核MacBook Pro。

初始尝试与问题 #

最初我让线程i处理从i/numThreads * height到(i + 1)/numThreads * height的行，但最多仅能获得2倍加速。推测问题在于硬件缓存加载了output数组的整行数据，线程切换时新线程会将当前行从缓存中驱逐，导致缓存颠簸。

第一次优化：按列分块避免缓存颠簸 #

随后我修改了mandelbrotSerial的签名，添加stride参数，让线程处理每行内的不同列以避免缓存颠簸，使用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);
        }
    }
}

接着我在workerThreadStart函数中添加计时代码：

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

运行后发现除线程0外，其他线程的运行时间约为70ms，线程0的运行时间约为103ms，推测线程0在为其他线程预热缓存。于是我调整线程0仅负责缓存预热：

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<numThreads; i++) {
      
        // TODO FOR CS149 STUDENTS: You may or may not wish to modify
        // the per-thread arguments here.  The code below copies the
        // same arguments for each thread
        args[i].x0 = x0;
        args[i].y0 = y0;
        args[i].x1 = x1;
        args[i].y1 = y1;
        args[i].width = width;
        args[i].height = height;
        args[i].maxIterations = maxIterations;
        args[i].numThreads = numThreads;
        args[i].output = output;
      
        args[i].threadId = i;
    }

    // Spawn the worker threads.  Note that only numThreads-1 std::threads
    // are created and the main application thread is used as a worker
    // as well.
    for (int i=1; i<numThreads; i++) {
        workers[i] = std::thread(workerThreadStart, &args[i]);
    }
    
    workerThreadStart(&args[0]);

    // join worker threads
    for (int i=1; i<numThreads; i++) {
        workers[i].join();
    }
}

疑问与优化需求 #

作业提示中明确说明“存在一种非常简单的静态分配方式可实现目标，且无需线程间通信/同步”，我担心自己的方向有误，希望获得实现7倍加速的优化建议。

内容的提问来源于stack exchange，提问作者gkv