Discrete Mathematics

140 DISCRETE MATHEMATIC..._

________________________

_

3.4.6

Parallel Task Scheduling

When elements

of

a poset are tasks that need to be done and the partial order has precedence constraints,

topological sorting provides us with a legal way to execute tasks sequentially, that is, without violating any

precedence constraints. But what

if

we have the ability to execute more than one task at the same time? For

example, say tasks are programs, partial order indicates data dependence, and we have a parallel machine

with lots

of

processors instead

of

a sequential machine with only one. How should we schedule the tasks? Our

goal should be