[Octal-dev] Re: Topological Sort

[Richard Wesley Todd]

On Sun, 4 Jun 2000 address@hidden wrote:
> 
> This sounds like *exactly* the kind of thing I'd been looking for.
> -- 
> @@@ david o'toole
> @@@ address@hidden
> @@@ www.gnu.org/software/octal

Great!  If it's not clear on anything just ask...I just wrote it for my
own future reference so it might skimp on some details.  

I can tell you that, for a long time I thought the algorithm needed an
overhaul because it didn't try to produce even groups.  For example, it
wouldn't be uncommon to see a set of groups with sizes 1,1,1,2,2,3,19,25.  

But this really doesn't have much to do with the 'optimal' grouping.  What
you really want is to keep *all* the processors busy, *all* the
time.  Without some kind of information about the time-complexity of the
tasks you're scheduling, this can't be done.  But if you assume you have
approximately equal tasks time-wise, the concern is to make groups sized
as a multiple of the number of processors available.

The way I help this along in my code is use the knowledge: A task from
group i+1 can be run with the last ones from group i, as long as there are
no forward links from the running group i tasks to the i+1 task.  (get
it?)

As an example:
  We have 2 processors.  Group 2 has 3 tasks (A B C).  Group 3 has 3 tasks
(D E F).  Here's how we can go:
  1) Execute (A + B)
  2) Execute (C)  Unused processor!  Check D for a connection from C to
D.  None found.  So execute (C + D) instead.
  3) Execute (E + F).
Without the optimization we'd have run:
  1) Execute (A + B)
  2) Execute (C)
  3) Execute (D + E)
  4) Execute (F)
Which is more wasteful.

A heuristic to help this along is to place the nodes with fewer links TO
them first in each group (So that D is more likely to be free to run than
E or F).  Also note that we don't care about A or B's links to D in
step 2 since they have already run.

Richard Todd