[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Octal-dev] Re: Topological Sort
From: |
Richard Wesley Todd |
Subject: |
[Octal-dev] Re: Topological Sort |
Date: |
Sun, 4 Jun 2000 15:32:56 -0500 (CDT) |
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
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Octal-dev] Re: Topological Sort,
Richard Wesley Todd <=