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

[Simon Jenkins]

Dave Griffiths wrote:

>On Fri, 28 Feb 2003 19:05:19 +0100
>David Olofson <david at olofson.net> wrote:
>
>>On Friday 28 February 2003 09.20, torbenh at gmx.de wrote:
>>[...]
>>    
>>
>>>random latency ? how do you mean that ?
>>>      
>>>
>>Latency depends on how you happen to construct the net (order of 
>>instantiation, connections etc) and/or the actual layout of the net, 
>>in "non-obvious" ways.
>>    
>>
>
>In ssm I sort the network each time a connection is made/destroyed, and generate a ordered list of modules to process from the root up to the leaves. It has to cope with circular sections, which unavoidably introduce latency, but it works. It also automatically means unconnected modules don't get processed, which is nice.
>
I just took a look at the SSM GraphSort code (from 0.2.1rc2). Its a neat 
encapsulation but the sort algorithm
seems to mess up on an important case:

GraphSort MySort;
MySort.AddConnection( 1, false, 2, false );
MySort.AddConnection( 1, false, 3, false );
MySort.AddConnection( 2, false, 4, false );
MySort.AddConnection( 3, false, 4, false );
MySort.Sort();

In other words 1feeds both 2 and 3, and then 2 and 3 both feed 4.

GraphSort gives the ordering  4,2,1,3 for this graph (ie execution order 
3,1,2,4)
introducing latency into what could have been evaluated straight through:
Execution order 1,2,3,4 OR execution order 1,3,2,4 would have done the 
trick.

Well, maybe this isn't an important case in ssm (I haven't looked) but 
its certainly
important to the more general issue of sorting graphs.

My amble demo contains a correct (AFAIK) graph ordering algorithm but its
poorly encapsulated, the code is a bit of a mess, and it has a slightly 
different
underlying model of a graph: More general in some ways (one output can feed
many inputs) and less general in others (there's only one "root" node, 
there's no
separate notion of a "terminal" node).

SSM and amble both ignore unconnected nodes which is nice if that's what you
want, but not if its not. A general solution to the graph sorting 
problem would
need to at least allow for the possibility that an unconnected node 
might need
to be processed.

That's easily solved... but here's a problem that's not:

A general solution to the graph sorting problem would have to know about the
I/O dependencies *inside* the nodes. This isn't usually a problem on 
the  scale
where a node represents, for example, a simple filter or oscillator. But 
what about
the scale where a node represents a quad noise gate or a reasonably 
well-featured
mixer (ie with inserts etc)?  Nodes like that aren't just difficult to 
place correctly
in the execution order... they can be *impossible* to place correctly in 
a very large
number of perfectly reasonable graphs: Different parts of their 
internals need to
be executed at different times!

Simon Jenkins
(Bristol, UK)