0

我正在尝试提出一种算法，以在多个线程上尽可能均匀地划分多个进程。每个过程花费相同的时间。进程的数量可以从 1 到 100 万不等。threadCount 是固定的，可以是 4 到 48 之间的任意值。

下面的代码确实平均分配了所有工作，除了最后一种情况，我把剩下的东西扔进去。有没有办法解决这个问题，使工作分布更均匀？

    void main(void)
{
    int processBegin[100];
    int processEnd[100];
    int activeProcessCount = 6243;
    int threadCount = 24;

int processsInBundle  = (int) (activeProcessCount / threadCount);
int processBalance    = activeProcessCount - (processsInBundle * threadCount);

for (int i = 0; i < threadCount; ++i)
{
    processBegin[ i ] = i * processsInBundle;
    processEnd[ i ]   = (processBegin[ i ] +  processsInBundle) - 1;
}

processEnd[ threadCount - 1 ] += processBalance;


FILE *debug = fopen("s:\\data\\testdump\\debug.csv", WRITE);
for (int i = 0; i < threadCount; ++i)
{
    int processsInBucket = (i == threadCount - 1) ? processsInBundle + processBalance : processBegin[i+1] - processBegin[i];
    fprintf(debug, "%d,start,%d,stop,%d,processsInBucket,%d\n", activeProcessCount, processBegin[i], processEnd[i], processsInBucket);
}
fclose(debug);

}

4

2 回答 2

3

给第一个activeProcessCount % threadCount线程processInBundle + 1进程并给其他线程processsInBundle。

int processInBundle  = (int) (activeProcessCount / threadCount);
int processSoFar = 0;
for (int i = 0; i < activeProcessCount % threadCount; i++){
    processBegin[i] = processSoFar;
    processSoFar += processInBundle + 1;
    processEnd[i] = processSoFar - 1;
}
for (int i = activeProcessCount % threadCount; i < threadCount; i++){
    processBegin[i] = processSoFar;
    processSoFar += processInBundle;
    processEnd[i] = processSoFar - 1;
}
于 2013-09-06T14:49:40.393 回答
0

这与试图将 5 便士分给 3 个人的问题相同。除非你能看到硬币的一半，否则这是不可能的。

此外，即使所有进程都需要相同数量的理论运行时间，但这并不意味着由于内核调度、缓存性能和各种其他硬件相关因素，它们将在相同的时间内执行。

提出一些性能优化建议：

  • 使用动态调度。即把你的工作分成几批（可以是1号），让你的线程一次拿一批，运行它，然后再拿下一个。这样，线程将始终工作，直到所有批次都消失了。
  • 更高级的是从大批量开始（通常numwork/numthreads在每次线程从池中取出工作时减小它）。OpenMP 将其称为引导式调度。
于 2013-09-06T14:44:53.180 回答