# Transitive relation's effect on scheduling parallel tasks

One of my friends asked me about this today but I'm unsure the exact answer.

Assume we have a program that consists of different subprograms. Each subprogram has an input and an output, some subprograms' inputs can be other subprograms' outputs. We are able to use several processors to process the subprograms in parallel (each processor can process only 1 subprogram). The question is to describe this in terms of relations and how this relation helps with scheduling the subprograms.

For the first thought, I think this is all to do with transitive relations between the subprograms. But I'm not pretty sure about the explanation of how this relation helps with scheduling the subprograms.

I'm happy to discuss.

-

## 1 Answer

Write the relation $A < B$ if subprogram $B$ can't start until subprogram $A$ finishes (e.g. because program $A$'s output is an input to program $B$).

-
I'm not quite understand what you mean by 'write a relation A<B'. –  conbongu Oct 29 '11 at 2:21
Hmm.. just found that it's related to reachability relation. –  conbongu Oct 29 '11 at 3:00