c++ - 写入数组时，最后一个线程比第一个线程执行得慢

Question

我正在尝试优化 Mandelbrot 集生成器，问题是我正在尝试使用 _beginthread() 函数使其成为多线程。我正在解决的计算问题是在二维平面上运行一个函数，我试图同时运行大约 8 个线程，每个线程计算二维数组的一部分(行)，但我注意到第一个线程完成，完成速度比最后一个完成的线程快得多。这是输出:

Starting thread 0
Starting thread 1
Starting thread 2
Starting thread 3
Starting thread 4
Starting thread 5
Starting thread 6
Starting thread 7
Ending thread   0 - Time taken: 1062ms
Ending thread   7 - Time taken: 1031ms
Ending thread   1 - Time taken: 1610ms
Ending thread   6 - Time taken: 1563ms
Ending thread   2 - Time taken: 10265ms
Ending thread   5 - Time taken: 10219ms
Ending thread   4 - Time taken: 31609ms
Ending thread   3 - Time taken: 31641ms

每个线程都有相同的事情要做，但是数字不同，我不明白为什么我得到那些时间 这就是我对它进行多线程处理的方式:

#define HEIGHT 4000
#define WIDTH 4000
#define MAX_THREADS 8
int const maxIterations = 150;

int bitmap[HEIGHT][WIDTH];
bool finishedThreads[MAX_THREADS];

void renderRow(void * arg) {
    int startTime = GetTickCount();
    int * threadNumPinter = (int*)arg;
    int threadNum = *threadNumPinter;
    int startRow = threadNum * (HEIGHT / MAX_THREADS);
    for (int y = startRow; y <= startRow+(HEIGHT / MAX_THREADS); y++) {
        for (int x = 0; x <= WIDTH; x++) {
            double xx = (((double)x / (double)WIDTH) * 4.0) - 2.0;
            double yy = (((double)y / (double)HEIGHT) * 4.0) - 2.0;
            bitmap[x][y] = isPartOfSet(xx, yy) * 10;
        }
    }
    threadNum = startRow / (HEIGHT / MAX_THREADS);
    finishedThreads[threadNum] = true;
    cout << "Ending thread " << threadNum << " - Time: " << GetTickCount() - startTime << "ms" << endl;
    _endthread();
}


int main() {
    int startTime = GetTickCount();
    HANDLE hThread;
    HANDLE ghEvents[2];
    DWORD dwThreadID;
    int rowsPerThread = HEIGHT / MAX_THREADS;
    int arg;
    int threadIds[MAX_THREADS];
    for (int i = 0; i < MAX_THREADS; i ++) {
        threadIds[i] = i;
        cout << "Starting thread " << i << endl;
        arg = i;
        _beginthread(renderRow, 0, &threadIds[i]);
        Sleep(10);
    }
    bool done = true;//Wait for all threads to finish
    while (1) {
        for (int i = 0; i < MAX_THREADS; i++){
            if (finishedThreads[i] == false)done = false;
        }
        if (done == true) break;
        else done = true;
        Sleep(20);
    }
    saveBitmap(WIDTH, HEIGHT);
    cout << endl << "Rendered in " << double(GetTickCount() - startTime) / 1000.0 << " seconds" << endl;
    cin.get();
    main();
}

显然有比这更多的代码，但我认为它对问题没有任何影响。我在这里做错了什么？我在 CUDA 上遇到了同样的问题，所以我相信这就是我实现多线程的方式。谢谢。

Answer 1

在我的回答中，我不会解决线程/同步问题或关于缓存的想法——请参阅其他答案/评论。

我的观点是不同的:你写“每个线程都有相同的事情要做，但有不同的数字”。如果我对 mandelbrot 集的内存对我有用，那么确定一个点是否是该集的成员(IOW 你的 isPartOfSet 函数的实现，你没有提供)是一个迭代过程。有些点会快速“退出”，有些点不会，您必须继续迭代直到达到预定义的最大迭代次数。

所以我要说的是:通过“每个线程一个大块”并行化，您的线程所花费的时间量可能自然会大不相同。

此类问题的解决方案是将问题(即图像)拆分为更小的部分，其大小不取决于线程数，但应根据经验选择a)不要太大以防止工作分配不均(如您的示例中的大块)和 b)不要太小以致导致过多的组织开销。

所以现在，你有 M 个线程和 N 个工作 block (N>>M)，你需要一个实现让每个线程像这样循环工作

while (worktodo) fetch_a_chunk_of_work_and_do_it ()

这种生产者/消费者模式是如何实现的——我会留给其他人描述(或者让你去谷歌 :-))