Subject: Re: [linux-audio-dev] XAP spec - early scribbles
From: Simon Jenkins (sjenkins_AT_blueyonder.co.uk)
Date: Sat Mar 01 2003 - 05:03:37 EET
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)
This archive was generated by hypermail 2b28 : Sat Mar 01 2003 - 04:02:38 EET