基于循环的音频DSP有向图的处理节点

Question

对于音频处理链(如Propellerhead理由)，我正在开发一个节点电路，在可能有循环的环境中相互通信(如下所示)。

音频设备(节点)以64帧的批量进行处理，在理想的情况下，通信在单个批处理中传播。不幸的是，可以创建反馈循环，这会导致链的延迟。

我正在寻找最佳的算法来持续最小化反馈循环？

在我的系统中，一个周期导致至少一个音频设备必须是一个“反馈节点”(如下所示)，这意味着它的“反馈输入”不能在同一批处理。

​

​

反馈的一个例子可以在以下处理计划中看到：

• D -> A
• A -> B
• B -> C
• C -> 'D

在这种情况下，从C到D的输出必须在下一批处理。

下面是一个导致两个反馈循环的低效处理计划的例子：

• A -> B
• B -> C
• C -> D
• D -> E，'A
• E、->、F
• F -> G
• G -> 'D

这里，从G到D，D到A的输出必须在下一批处理。这意味着G的输出在2批之后达到A，而A到D的输出发生在同一批中。

最有效的处理调度从D开始，只产生一个反馈节点(D)。

这个图形能变得多大？有1000个音频设备是很常见的(例如一首有30个音频通道，30个效果设备连接的歌曲)，尽管每个设备通常有2-4个输出，电路也不是非常复杂。相反，音频设备往往与本地化的范围相连，因此电路(如果确实存在)更有可能受到本地限制，尽管我只需要准备最有效的节点调度，以减少反馈次数。

具有两条路径(理想情况下)的一对音频设备之间不应该有不匹配的反馈节点。假设有两个节点，M和N，从M到N有两个独立的路径，一个路径上不应该有一个反馈节点，而另一个路径上不应该有一个反馈节点，因为这会使输入到N上去同步，这是非常不想要的。这一目标使算法进一步复杂化。但我将研究理性是如何表现的(因为它可能并不是那么复杂)。

Answer 1

这次调查描述了几种解决反馈集问题的方法，但只简单地描述了分支和界。我认为这个分支和界是一个很有前途的方法，所以我将在这里详述这个描述。

在分支和界中，我们探索一个由节点组成的搜索树，其中为每个顶点分配一个标号0、1或？意思是什么？我们还不知道要给出什么标签，而根节点有所有的顶点标记吗？搜索树的叶子没有标记顶点。节点的子节点，其中至少有一个顶点被标记？是通过选择一个标记的任意顶点来确定的？让它在左边是0，在右边是1。这是分支。

对于一个节点，我们做了一些事情来确定一个下界(因为我们在最小化)在一个解中标记为1的顶点数，其中每个?s被替换为0或a 1。如果这个下界并不比我们到目前为止找到的最佳解好，那么就没有必要进一步探索子树了。为了证明最优性，最好的方法，给定的空间，是深度优先搜索与最佳优先回溯。深度优先搜索部分包括反复探索更有前途的子节点(下限)，并将另一个子队列放入优先级队列。然后，当我们因为在叶子上或者因为节点被修剪而陷入困境时，我们就把最有希望的可能性从队列中拉出来。当队列为空时，我们停止。

获得界的一个非常常见的方法是线性规划。与标号点0或1不同的是，如果允许区间0，1中有分数标号，那么我们就可以相对有效地找到一个“解”。这个解决方案的成本并不比真正的最优值更高，但是，当然，不可能有一个节点是“半反馈”。选择一个具有小数标号的顶点(最接近0.5通常是一个很好的选择)并在其上分支。

事实上，这种方法是如此普遍，以至于大多数线性规划求解者以整数规划的形式为它提供了一个方便的接口。不幸的是，整数编程不能直接为我们工作，因为程序有太多的限制:每个简单的周期一个。(想想看，如果没有太多的简单循环，那么您最终可以使用整数编程。)

反馈顶点集的线性程序如下所示。变量x_v是解标号:0如果v是组合的，1如果v是反馈的，则小数值在这两种可能性之间插值。

minimize sum_v x_v (as few feedback vertices as possible)
subject to
for all simple cycles C, sum_{v in C} x_v >= 1 (at least one vertex on each cycle)
for all v, x_v >= 0 (vertices cannot be "negative feedback")

你实际上想要解决对偶规划，它通过弱LP对偶性，下界最优解在可行的情况下。

maximize sum_C y_C
subject to
for all vertices v, sum_{C ni v} y_C <= 1
for all C, y_C >= 0

这个程序的直观含义如下。假设我们确定了不相交的简单循环。每个循环至少包含一个反馈顶点，并且这些顶点是不同的。这是该技术的分数模拟(它适用于每一个LP，而不仅仅是这个；这个LP的对偶又是第一个LP )。

求解这一LP的技术称为列(即变量)生成。最初，我们将它发送给没有变量的求解器。然后，我们与求解者反复交互，获得解决方案，并添加看起来有用的变量，直到我们达到了最优(或停滞)为止。求解器为所有的x_v返回相应的值，为我们告诉它的C返回y_C。为了找到我们应该包含的另一个循环C'，我们需要sum_{v in C'} x_v < 1，最好少得多。用x_v的值标记每个弧，其中x_v是它的头。对于每个顶点，运行Dijkstra查找最短路径，然后检查进入该顶点的弧是否形成一个短循环。

由于当前节点施加的侧约束，这稍微复杂了一些。如果一个顶点被标记为0或1，那么我们从对偶中省略它的约束，用这个标签代替x_v来标记Dijkstra的图。

我希望，当您确定什么是边约束时，我们可以设计另一个列生成策略来处理它们。我对此更有信心，而不是修改被调查的组合缩减策略。