Hardware Reference
In-Depth Information
of a full-blown standardization bureaucracy is not necessarily a drawback. When
all was said and done, it appears that MPI won.
MPI programmers can easily create jobs requesting multiple CPUs and run-
ning for substantial periods of time. When multiple independent requests are avail-
able from different users, each needing a different number of CPUs for different
time periods, the cluster needs a scheduler to determine which job gets to run
when.
In the simplest model, the job scheduler requires each job to specify how many
CPUs it needs. Jobs are then run in strict FIFO order, as shown in Fig. 8-45(a). In
this model, after a job is started, a check is made to see if enough CPUs are avail-
able to start the next job in the input queue. If so, it is started, and so on. Other-
wise, the system waits until more CPUs become available. As an aside, although
we have suggested that this cluster has eight CPUs, it might well have 128 CPUs
that are allocated in units of 16 (giving eight CPU groups), or another combination.
CPU group
CPU group
CPU group
01234567
01234567
01234567
1
1
4
1
4
7
7
2
3
3
6
5
9
3
8
5
5
2
4
6
9
2
6
8
9
8
7
(a)
(b)
(c)
Figure 8-45.
Scheduling a cluster. (a) FIFO. (b) Without head-of-line blocking.
(c) Tiling. The shaded areas indicate idle CPUs.
A better scheduling algorithm avoids head-of-line blocking by skipping over
jobs that do not fit and picking the first one that does fit. Whenever a job finishes,
the queue of remaining jobs is checked in FIFO order. This algorithm gives the re-
sult of Fig. 8-45(b).
A still more sophisticated scheduling algorithm requires each submitted job to
specify its shape, that is, how many CPUs for how many minutes. With that infor-
mation, the job scheduler can attempt to tile the CPU-time rectangle. Tiling is
