How to calculate evenly distributed number of jobs for fixed number of threads?

user_1659758 0
Viewed 159

Let's presume I have tasks number of tasks and threads number of threads to run them. Each thread can run only once, so I want to distribute those tasks evenly through existing threads. To calculate number of tasks per thread I wrote this simple app:

#include <iostream>
using namespace std;

int main(){
    int tasks = 15; 
    int threads = 8; 

    if(tasks < threads)
        threads = tasks;

    int tasksPerThread = tasks / threads;

    for (int i = 0, start = 1; i < threads; i++) {
        start = tasksPerThread * i + 1;
        int end = start + tasksPerThread - 1;
        if (i == threads - 1 && end < tasks)
            end = tasks;
        if(start == end)
            cout << "Thread " << i + 1 << ": task " << end << endl;
        else
            cout << "Thread " << i + 1 << ": task " << start << "-" << end << endl;
    }
    return 0;
}

When having 16 tasks and 8 threads, each thread would get 2 tasks. But, in this case when having 15 tasks with 8 threads I get the following distribution as a result:

  • Thread 1: task 1
  • Thread 2: task 2
  • Thread 3: task 3
  • Thread 4: task 4
  • Thread 5: task 5
  • Thread 6: task 6
  • Thread 7: task 7
  • Thread 8: task 8-15

Last thread would perform to many task in comparison to others, and that is why I would like to fix this distribution to be something like this:

  • Thread 1: task 1-2
  • Thread 2: task 3-4
  • Thread 3: task 5-6
  • Thread 4: task 7-8
  • Thread 5: task 9-10
  • Thread 6: task 11-12
  • Thread 7: task 13-14
  • Thread 8: task 15

I need help fixing the code above to get this kind of result where each thread has similar number of tasks to perform. Thanks.

EDIT: Here is the solution thanks to @shananton's formula.

int tasks = 15;
int threads = 8;

if (tasks < threads)
    threads = tasks;

int start, usedTasks = 0, tasks_for_this_thread = 0;

for (int i = 0; i < threads; i++) {
    usedTasks += tasks_for_this_thread;
    start = usedTasks + 1;
    tasks_for_this_thread = tasks / threads + (i < tasks % threads);
    int end = start + tasks_for_this_thread - 1;

    if (start == end)
        cout << "Thread " << i + 1 << ": task " << end << endl;
    else
        cout << "Thread " << i + 1 << ": task " << start << "-" << end << endl;
}
c++
2 Answers

To calculate the number of tasks per thread in advance, you can use this formula:

int tasks = 10;
int threads = 3;

for (int i = 0; i < threads; ++i) {
    int tasks_for_this_thread = tasks / threads + (i < tasks % threads);
    // do whatever you want to 
}

For example, for 10 tasks and 3 threads, it distributes the tasks as 4, 3, 3.

user_65085980

A simple round robin by iterating through tasks.

int tasks(15);
int threads(8);

int thread_index(0);
for( int i = 0 ; i < tasks; i++){
    set( thread_index , i ); // pseudo code to start the task 
    thread_index = ( thread_index+1 ) % threads;
}
user_41237030
Related