TASK_DIVISION
Divide T Tasks Among P Processors


TASK_DIVISION is a C library which implements a simple procedure for smoothly dividing T tasks among P processors; such a method can be useful in MPI and other parallel environments, particularly when T is not an exact multiple of P, and when the processors can be indexed starting from 0 or from 1.

If we have 16 tasks and 8 processors, it's easy to see that each processor gets two tasks, and that processor 3 gets tasks 5 and 6...(unless we index our processors starting at 0 rather than 1, but let's ignore that possibility for the moment.)

If we have 17 tasks and 8 processors, then we can just give the last processor the extra task, because someone has to do it. But if we have 18 tasks, we shouldn't given everyone else 2 tasks, and the last processor 4 tasks. A better assignment would have two of the processors working on 3 tasks, the rest on 2.

Moreover, we'd like to do this kind of assignment in a regular enough nonarbitrary way, so that any processor, knowning just its processor index and the number of tasks, can work out the number of tasks it got assigned, and even the indices of those tasks.

The TASK_DIVISION library outlines a simple way to do this, which is essentially a "greedy" algorithm that cuts up the "task pie" a slice at a time, using rounding to give each processor about the same number of tasks, in a way that avoids having leftovers.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

TASK_DIVISION is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

MPI, C programs which illustrate the use of the MPI application program interface for carrying out parallel computations in a distributed memory environment.

Source Code:

Examples and Tests:

List of Routines:

You can go up one level to the C source codes.


Last modified on 23 October 2011.