title: Processing nodes in circuit based digraph with cycles for audio DSP
body: <p>For an audio processing chain (like <a href="https://www.propellerheads.se/products/reason/index.cfm?fuseaction=get_article&amp;article=features_creative_flow" rel="nofollow noreferrer">Propellerheads' Reason</a>), I'm developing a circuit of nodes which communicate with each other in an environment where there may be loops (shown below).</p>
  
  <p>Audio devices (nodes) are processed in batches of 64 audio frames, and in the ideal situation, communication propagates within a single batch. Unfortunately feedback loops can be created, which causes a delay in the chain.</p>
  
  <p><strong>I am looking for the best type of algorithm to consistently minimize feedback loops?</strong></p>
  
  <p>In my system, a cycle leads to at least one audio device having to be a "feedback node" (shown below), which means its "feedback input" cannot be processed within the same batch.</p>
  
  <p><img src="https://i.stack.imgur.com/2vpeq.png" alt="Digraph"></p>
  
  <p>An example of feedback can be seen in the following processing schedule:</p>
  
  <ul>
  <li>D -> A</li>
  <li>A -> B</li>
  <li>B -> C</li>
  <li>C -> 'D</li>
  </ul>
  
  <p>In this case the output from C to D has to be processed on the next batch.</p>
  
  <p>Below is an example of an inefficient processing schedule which results in two feedback loops:</p>
  
  <ul>
  <li>A -> B</li>
  <li>B -> C</li>
  <li>C -> D</li>
  <li>D -> E, 'A</li>
  <li>E -> F</li>
  <li>F -> G</li>
  <li>G -> 'D</li>
  </ul>
  
  <p>Here the output from G to D, and D to A must be processed on the next batch. This means that the output from G reaches A after 2 batches, compared to the output from A to D occurring within the same batch.</p>
  
  <p>The most efficient processing schedule begins with D, which results in just one feedback node (D).</p>
  
  <p><strong>How large can this graph become?</strong>
  It's quite common to have 1000 audio devices (for example a song with 30 audio channels, with 30 effects devices connected), though the there are typically 2-4 outputs per device and the circuits aren't incredibly complex. Instead audio devices tend to be connected with localised scopes so circuits (if they do exist) are more likely to be locally confined though I just need to prepare the most efficient node schedule to reduce the number feedbacks.</p>
  
  <p><strong>A pair of audio devices with two paths (ideally) should not have mismatched feedback nodes between them</strong>
  Suppose there are two nodes, M and N, with two separate paths from M to N, there should not be a feedback node on one path but not on the other as this would desynchronise the input to N, which is highly undesired. This aim complicates the algorithm further. But I will examine how Reason behaves (as it might not actually be so complex).</p>