写入数组时,最后一个线程的执行速度比第一个线程慢

Question

我正在尝试优化Mandelbrot集生成器,问题是我试图通过使用_beginthread()函数使其成为多线程.我正在解决的计算问题是在2D平面上运行一个函数,我试图同时运行大约8个线程,每个线程计算2D阵列的一部分(行),但我注意到第一个线程完成后,完成的最后一个线程完成得快得多.这是输出:

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集合的记忆对我isPartOfSet有用,那么确定一个点是否是该集合的成员(IOW你的函数的实现,你没有提供)是一个迭代过程.有些要点很快就会"拯救",有些要点并没有,你必须继续迭代,直到你预定义的最大数量为止.

所以我所说的是:通过"每个线程一个大块"的并行化,你的线程可能会花费大量不同的时间.

这类问题的解决方案是将问题(即图像)分成较小的部分,其大小不依赖于线程的数量,但应根据经验选择a)不要太大以防止不平等的工作分布(如你的巨大块的例子)和b)不会导致过多的组织开销.

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

while (worktodo) fetch_a_chunk_of_work_and_do_it ()

如何实现这种生产者/消费者模式 - 我将留给其他人描述(或者你为google :-))