task_division


task_division, a C++ code 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 code 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 MIT license

Languages:

task_division is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

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

task_division_test

Source Code:


Last modified on 21 April 2020.