Алгоритм распределения рабочей нагрузки в пуле потоков

Question

Допустим, что у нас есть T количество потоков, и мы хотим распространять проблему с размером N в эти темы. Каждый поток выбирает часть этой проблемы для ее выполнения. Каждый поток будет использовать thread_id (число от 0 до T-1), T и N, чтобы рассчитать диапазон подзадачи. Предположим, что область подзадачи - [S, E), где S и E принадлежат [0, N].

Например. Допустим, у нас есть массив целых чисел. Размер массива равен 10. Мы хотим увеличить каждый элемент этого массива на один, и мы хотим сделать это параллельно, используя 4 потока.

• 1-нить с thread_id == 0 будет использовать диапазон [0, 3)
• 2-й нити с thread_id == 1 будет использовать диапазон [3, 6)
• 3-я нить с thread_id = = 2 будет использовать диапазон [6, 8)
• 4-нить с thread_id == 3 будет использовать диапазон [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; 

Я не думаю, что можно избежать ветвей.

Чувствуя приключений я сделал в питона в live demo, она включает в себя метод 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)]