[linux-audio-dev] XAP spec - early scribbles

[Simon Jenkins]

torbenh at gmx.de wrote:

>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 that
>>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.
>>    
>>
>galan needs this...
>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)