Chapter 9 Directed graphs & Partial Orders254
two different elements in the set are comparable. A chain is said toend atan its
maximum element.
Thus, the time it takes to schedule tasks, even with an unlimited number of pro-
cessors, is at least the length of the longest chain. Indeed, if we used less time, then
two items from a longest chain would have to be done at the same time, which con-
tradicts the precedence constraints. For this reason, a longest chain is also known
as acritical path. For example, Figure 9.9 shows the critical path for the getting-
dressed poset.
In this example, we were in fact able to schedule all the tasks intsteps, where
tis the length of the longest chain. The really nice thing about posets is that this
is always possible! In other words, for any poset, there is a legal parallel schedule
that runs intsteps, wheretis the length of the longest chain.
In general, aschedulefor performing tasks specifies which tasks to do at succes-
sive steps. Every task,a, has to be scheduled at some step, and all the tasks that
have to be completed before taska, must be scheduled for an earlier step.
Definition 9.10.5.Aparallel schedulefor a strict partial order, , on a set,A, is a
partition^9 ofAinto setsA 0 ;A 1 ;:::;such that for alla;b 2 A,k 2 N,
Œa 2 AkANDb aç IMPLIES b 2 Ajfor somej < k:The setAkis called the set of elementsscheduled at stepk, and thelengthof
the schedule is the number of setsAkin the partition. The maximum number of
elements scheduled at any step is called thenumber of processorsrequired by the
schedule.
In general, the earliest step at which an elementacan ever be scheduled must be
at least as large as any chain that ends ata. Alargestchain ending atais called a
critical pathtoa, and the size of the critical path is called thedepthofa. So in any
possible parallel schedule, it takes at least depth.a/steps to complete taska.
There is a very simple schedule that completes every task in this minimum num-
ber of steps. Just use a “greedy” strategy of performing tasks as soon as possible.
Namely, schedule all the elements of depthkat stepk. That’s how we found the
schedule for getting dressed given above.
(^9) Partitioning a set,A, means “cutting it up” into non-overlapping, nonempty pieces. The pieces
are called the blocks of the partition. More precisely, apartitionofAis a setBwhose elements are
nonempty subsets ofAsuch that
ifB;B^02 Bare different sets, thenB\B^0 D;, and
S
B 2 BBDA.