c++ - 通过线程分配 for 循环迭代

Question

我想用 n 计算嵌套循环线程:

for (i = 0; i < matrix.size(); i++) {
    for (j = 0; j < matrix.size(); j++) {
        for (k = 0; k < matrix.size(); k++) {
            // do the job
        }
    }
}

我想用不同的线程计算每个循环操作。让我们调用线程 T .与 3线程和 matrix.size() = 5这是应该如何分配工作:

T[0] computes operation i=0 j=0 k=0
T[1] computes operation i=0 j=0 k=1
T[2] computes operation i=0 j=0 k=2
T[0] computes operation i=0 j=0 k=3
T[1] computes operation i=0 j=0 k=4
T[2] computes operation i=0 j=1 k=0
T[0] computes operation i=0 j=1 k=1
T[1] computes operation i=0 j=1 k=2
T[2] computes operation i=0 j=1 k=3
T[0] computes operation i=0 j=1 k=4
T[1] computes operation i=0 j=2 k=0
T[2] computes operation i=0 j=2 k=1
T[0] computes operation i=0 j=2 k=2
T[1] computes operation i=0 j=2 k=3
T[2] computes operation i=0 j=2 k=4
T[0] computes operation i=0 j=3 k=0
T[1] computes operation i=0 j=3 k=1
T[2] computes operation i=0 j=3 k=2
T[0] computes operation i=0 j=3 k=3
T[1] computes operation i=0 j=3 k=4
T[2] computes operation i=0 j=4 k=0
T[0] computes operation i=0 j=4 k=1
T[1] computes operation i=0 j=4 k=2
T[2] computes operation i=0 j=4 k=3
T[0] computes operation i=0 j=4 k=4
T[1] computes operation i=1 j=0 k=0
T[2] computes operation i=1 j=0 k=1
T[0] computes operation i=1 j=0 k=2
T[1] computes operation i=1 j=0 k=3
T[2] computes operation i=1 j=0 k=4
T[0] computes operation i=1 j=1 k=0
T[1] computes operation i=1 j=1 k=1
T[2] computes operation i=1 j=1 k=2
T[0] computes operation i=1 j=1 k=3
T[1] computes operation i=1 j=1 k=4
T[2] computes operation i=1 j=2 k=0

我设法将最后一行更改为:for (k = PROCESSINDEX; k < matrix.size(); k += PROCESSAMOUNT) ，但结果是这样分配工作:

T[0] computed 25 iterations
T[1] computed 50 iterations
T[2] computed 50 iterations

我该如何改进？

Answer 1

虽然在许多实际任务中，例如将两个矩阵相乘，将其进一步分解很可能会导致性能下降，因为它会破坏线程的内存局部性，但如果您执行的任务确实具有低数据依赖性，则有一个明显的解决方案:您只需枚举从 0 到 n^3-1 的所有三元组 (i,j,k)(假设 n = matrix. size()) 然后将该范围分成 3 个几乎相等的 block 并将它们传递给每个线程。然后每个线程都可以很容易地重建它的工作部分(任务#t 对应于 i+j*n+k*n^2 所以:

i = t % n
j = (t/n) % n
k = t / n /n

另一种解决方案是使用线程池和任务队列。您不会在一开始就为每个线程分配所有工作。您将工作放入队列中，让每个线程从中获取一些批处理的工作，处理完批处理后，返回并从队列中取出下一批处理，使用批处理可以减少队列中的并发冲突。这种方法的优点是，如果处理数据的时间取决于特定数据，那么您将平衡实际执行的工作而不是执行的任务数。