Question on Graph / Topological Sort

Development
16

It seems like many people are not aware of this, but ParGroup can be nested arbitrarily deep. In fact, Supernova calculates a dependency graph, which is updated whenever the DSP tree structure changes, i.e. when Nodes are added, moved or removed.

The problem with the original Group structure is that it is just a container, there is no information about the relationship between its children. In Supernova, Group actually means “serial group”, i.e. its children depend on each other and form a dependency chain. ParGroup, on the other hand, means that its children are independent from each other. I guess things would be more clear if Group was renamed to SerGroup :slight_smile:

Now, if you use (Ser)Group and ParGroup consequently, Supernova will do a decent job at parallizing the full graph. For example, if you have four independent “tracks” (e.g. a synth track, a bass track, a drum track, etc.), all tracks should go into a ParGroup. Each track itself might contain multiple voices, followed by serial FX chain. You would end up with a structure like this:

P = ParGroup
S = (Ser)Group

                     P(tracks)
              /           |         \
             /            |          \
       S(bass)         S(synth)     S(drums)
     /        \          etc.          etc.
P(voices) ->   S(fx)
            /    |    \
         FX1 -> FX2 -> FX3

As @scztt noted correctly, the parallelization is not perfect. There are certain degenerate cases, for example:

        Group
      /       \
 ParGroup     N5
/  |  |  \
N1 N2 N3 N4

If N1 takes a lot more CPU time than N2-N4, the DSP helper threads will busy wait and just burn CPU cycles; only when N1 has finished they can move on to N5.

Another problem arises when you put a lot of nodes into a ParGroup; Supernova creates a dedicated DSP “task” for each node and the resulting scheduling overhead can diminish or even outweight the parallalization gains. This is particularly true if the nodes are very lightweight. If all the nodes are the same, or every similar, you actually want to group them into N tasks, where N = number of cores. For example, if you have 120 lightweight synth nodes in a ParGroup on a 8-core machine, you would want to schedule 8 tasks with 15 nodes each. IIRC, I have somewhere proposed an option for ParGroup that would enable exactly this.

5 Likes