用于在线程池中分配工作负载的算法

Question

假设我们有 T 个线程，我们想将大小为 N 的问题分配给这些线程。每个线程都会选择该问题的一部分来执行它。每个线程将使用thread_id(从 0 到 T-1 的数字(、T 和 N 来计算子问题的范围。假设子问题的范围是 [S， E(，其中 S 和 E 属于 [0， N]。

例如。假设我们有一个整数数组。数组的大小为 10。我们希望将该数组的每个元素增加一个，并且我们希望使用 4 个线程并行执行此操作。

• 第一个具有 thread_id==0 的线程将使用范围 [0， 3(
• 具有 thread_id==1 的第二个线程将使用范围 [3， 6(
• 具有 thread_id==2 的第 3 个线程将使用范围 [6， 8(
• thread_id==3 的第 4 个线程将使用范围 [8， 10(

有谁知道可以计算这些范围的快速算法？最好没有原子或分支。

Answer 1

如果我理解正确，您正在寻找这样的等式？

S = floor(thread_id * N/T)
E = floor((thread_id + 1) * N/T)

如果你先乘(threadId * N(后除(/N(，你可以使用整数进行计算，floor函数是不必要的。

Answer 2

我认为这两个例子应该有效。所有操作都是整数。除了那个标记为不是。

这个逻辑更简单，但它不会按照您的要求分配工作。它将把更大的工作分配给所有工人，除了最后一个会得到明显较低的份额。从理论上讲，这应该不是问题，因为一个工人的最大工作量保持不变。

items_per_thread = ceil(N/T); // This is not an integer division.
start = thread_id*items_per_thread;
stop = min(start+items_per_thread, N);

这个应该根据您的需要分配工作。

items_per_thread = N/T;
start = thread_id*items_per_thread+min(thread_num, N mod T);
stop = start+items_per_thread;
if(thread_num < N mod T) stop += 1;

我认为不可能避免分支。

感觉很冒险，我用python做了一个现场演示，它也包括ciamej的方法。

import math
def distribution1(id ,N, T):
    items_per_thread = math.ceil(N/T);
    start = id*items_per_thread;
    stop = min(start+items_per_thread, N);
    return (start, stop)
def distribution2(id ,N, T):
    items_per_thread = math.floor(N/T);
    start = id*items_per_thread+min(id, N % T);
    stop = start+items_per_thread;
    if(id < N % T): stop += 1;
    return (start, stop)
def distribution3(id ,N, T):
    S = math.floor(id * N/T)
    E = math.floor((id + 1) * N/T)
    return (S,E)
def distribute(N, T, method):
    ret = []
    for i in range(T):
        ret.append(method(i, N, T))
    return ret
N=10
T=4
print(distribute(N, T, distribution1))
print(distribute(N, T, distribution2))
print(distribute(N, T, distribution3))

输出：

[(0, 3), (3, 6), (6, 9), (9, 10)]
[(0, 3), (3, 6), (6, 8), (8, 10)]
[(0, 2), (2, 5), (5, 7), (7, 10)]