Parallel Scheduling of Flux Calculations

FACETS is designed to have multiple flux models, and each flux model will run only on specified flux surfaces in the core. Flux models are expected to be flexible enough to run multiple flux surfaces on a single processor or a single flux surface on several processors. This leaves us with a challenge about how to run the flux models in parallel in the optimal amount of time.

General Problem Description

The problem of allocating processors (more precisely MPI ranks) to flux models can be generalized into the following general parallel resource scheduling problem.

Given:

• n - MPI ranks (may correspond to cores or nodes)
• p - parallel tasks
• W_i - a measure linearly proportional to the computational work required to complete parallel task i for i greater than or equal to 1 and less than or equal to p. This is a real valued parameter, and W_i = 2 W_j implies that task i takes twice as long as task j when each is allocated the same number of MPI ranks.
• L_i - an integer lower bound on the number of MPI ranks that parallel task i (i in 1..p) requires (often 1).
• U_i - an integer upper bound on the number of MPI ranks that parallel task i (i in 1..p) can effectively utilize
• D_i - the number of MPI ranks assigned to parallel task i must by integer divisible by D_i. In many cases, D_i is 1 which means any number of ranks satisfying the minimum and maximum constraint is legal. A task requiring an even number of MPI ranks would have D_i of 2.

It is assumed that each FACETS flux components can specify values for L, U, and D.

In thinking about the problem, it seems that we also need to have some indication of the parallel efficiency of the parallel tasks. If all parallel tasks are perfectly scalable, have n integer divisible by D_i, and have U_i greater than or equal to n, one optimal solution is to give the all processors to each flux calculation serially (i.e., task 1 runs on n MPI ranks, followed by task 2 running on n MPI ranks, etc.).

The simplest thing to do initially is to assume linear speed up with a constant efficiency, E, that's less than 1. If we take R_i as the number of MPI ranks assigned to parallel task i, the time required to complete task i, T_i, equals W_i / ( E * R_i' ).

The objective is to find the optimal processor allocation and computing schedule to minimize the time required to complete all p parallel tasks.

Thoughts and Observations About the Solution of the Parallel Allocation/Scheduling Problem

I haven't proven it, but this problem seems more difficult than other known NP-Hard problems (e.g.,  the bin packing problem). Hence, I would say that an algorithm to produce a globally optimum solution is not in the cards.

Even a relatively simple problem involving 4 tasks and 4 MPI ranks can have vastly different optimal solutions depending on the values of W_i. If the values of W are relatively similar, the optimal solution is assigning one processor per task.

However, if W₁ is 12 and the other W values are around 1, assigning one rank per task gives a highly non-optimal result.

One optimal solution is to run task 1 in parallel on processors 1-3 while running tasks 2-4 on processor 4 in serial.

I am guessing that the number of tasks is going to be in the tens, and the number of processors could be in the tens of thousands. With these kinds of numbers, finding the global optimal will most likely take longer than we would like to take.