On Mon, Mar 03, 2003 at 08:36:04PM +0000, Simon Jenkins wrote:
I'm trying to think about the most general model, at least at this stage. It might
become unmanageably complex and need to be stripped back. OTOH its possible that a
whole lot of complexity could suddenly disappear behind a simple abstaction.
would be nice...
what is the most general model ?
Erm... it turns out to be unmanageably complex on the sorting side of things, so its time for a whole lot of complexity to suddenly disappear behind some simplification.
The most general model seems to be directed cyclic graphs eg network with feedback, and it turns out that many of the problems in this area are NP complete.
Specifically, there's no known algorithm that will identify a minimum set of feedback edges in an arbitrary directed cyclical graph in less than exponential time.
OTOH, once you've identified *some* set of feedback edges you can disregard them and treat what remains as a directed acyclic graph... and once its a DAG you can do lots of relatively easy well understood things with it, such as sort it into an execution order, work out what temporary buffers (or vars for a compiler) you need, identify concurrency.
So, for sorting, strip it back to:
1) something that does a reasonable job of culling feedback edges from a directed cyclical graph to turn it into a DAG, in a reasonable amount of time.
2) a hook for apps to do the culling themselves if they want to try and do better, eg they know something about their graph that we don't.
3) A correct execution order sort of the resulting DAG.
4) Other analyses of the DAG added as required, eg allocation of temp vars/buffers.
"Pull" is the right way to do it if you've got feedback. By analysing backwards from the outputs you detect the unavoidable sources of feedback and deal with them one at a time. You never introduce any avoidable latency at all, or at least you shouldn't.
This definitely gives you a correct sort. It removes a number of edges from the graph and leaves you with a perfect sort order for the resulting DAG. But I no longer think that its optimal (ie removing fewest possible edges) in the general case. I'm looking into this. Perhaps its optimal if you have a single input and output source? Trying to find this out. It does a very good job on the audio graphs I've shown it, but maybe its just a generally good heuristic for an audio graph. Or maybe its good at finding the feedback in "DAVNAGs" (Directed And Very Nearly Acyclic Graphs)
Clocked is where some connections in and out of nodes are clocks thatgalan needs this...
control when the node should be executed. There are graphical programming
languages that do this. You can't fully sort it because the execution
order is at least partially determined at runtime.
i have event handling code in the plugins
these can be triggered by clocks...
if the library would find out these codepaths it would be ideal...
If your execution order is partly determined by the contents of the data flowing through the connections, and not just by the topology of the graph, then it can't all be "sorted away" at compile time, but maybe some of it can.
Do you mean you've got some modules where an event can turn up at an input, causing it to send events to connected modules, so a whole cascade of events can be triggered by a single event?
==== On the graph editing/manipulation side of things:
I definitely want to proceed with that, especially the heirarchical support, but I think it's a separate project from the sorting stuff. I got them entangled in the amble implementation but really things would be a lot cleaner if they were separated.
Simon Jenkins (Bristol, UK)
