0

当给出多个静态数据流时，我试图找到一个最佳调度策略。例如，

stream 0: 000---00--000

stream 1: 1111--11--11-11

stream 2: 22-222---2-2

...

这里，“1”表示一个周期内处理的有效数据，“-”表示一个周期停顿。调度程序在每个周期中只能处理来自一个流的有效数据。当一个流停止时，调度程序总是可以切换到另一个等待有效数据的流。或者调度器可以使用其他调度策略做出流切换决策。

例如，一个严格的循环策略（遵循顺序流 0 1 2，即使当前选择的流已停止或为空）如下所示：

DispatchTimeLine: 012012012-1201201-01201201xx1

stream 0 time line:   0xx0xx0---xx0xx0--0xx0xx0xxxx  

stream 1 time line:   x1xx1xx1xx1--1xx1--1xx1-x1xx1 

stream 2 time line:   xx2xx2-x2xx2xx2---xx2-x2xxxxx

在这种情况下，调度程序需要 29 个周期来处理所有数据。如果使用贪心策略，总共可以实现 26 个循环。（“x”表示等待或空闲。）

如果目标是最佳性能（最少的总周期数），如何为调度程序推导出最优策略？是否有任何理论证据可用于更一般的情况？

下面是这个问题的一般描述：

假设有N个数据点流（0到N-1），每个数据点流（Di）都有自己的静态数据点模式（如“valid, valid, valid...stall,stall,...” ，即“valid”和“stall”点的交错序列。“valid”的数量为Vi，“stall”的数量为Si。每个流内的时间顺序是固定的。）没有特定的约束对于 N、Vi 和 Si 的值，每个数据流的数据模式在调度期间也是固定的。也就是说，可以有多个，也可以有一个数据流，数据流的组成和长度不受限制。

对于调度器，它在一个周期内只能处理一个流中的一个数据点。当流Di被停顿时，调度器可以选择其他流走，并且在调度器处理其他流时可以隐藏流Di的停顿时间。一旦对流 Di 进行了停顿，它就有资格再次被选中。当一个周期内所有流都处于停顿状态时，在这个周期内不能处理任何数据，一个NOP会在调度器的时间线上占据这个周期。

这里唯一的目标是调度程序的最少总处理时间（或者说最高性能）。这里没有其他要求，例如流之间的公平性。

直觉上，我认为贪婪策略在某些情况下可能是最优的，例如在上面的数字示例中。但我不确定这项政策是否在所有情况下都是最好的。我想知道它是否可以从理论上证明？或者是否有一种系统的方法可以帮助找到最佳调度策略的过程？

4

1 回答 1

0

我将推测，一般来说，找到一个最佳时间表是 NP 难的。当可用任务到达非常接近调度程序的吞吐量时，似乎应该减少一些利用调度技巧的分区问题。当然，我尝试过的各种贪心算法都没有成功（我之前没有意识到每个流都有一个只有一个元素的“缓冲区”）。

对于每个长度为 n 的 k 个流，有一个固定参数算法，通过动态编程在时间 O(n^k) 中运行。当k = 48时这对你没有用，所以我不会描述它。我建议改为约束编程，它有机会利用您的特定输入的特征。

这是将问题表述为约束程序的一种方法。对于第 i个流中的第 j个项目，令 t ij为该项目处理完成的整数时间。要在第 i个流中的第 j个和第 (j + 1)个项目之间强制停顿长度为 k ，请约束 t i(j+1) - t ij > k。对于所有 i，约束 t i1 > 0。对每一个变量施加一个完全不同的约束并最小化它们的最大值。

有各种解决约束程序的软件包。他们使用智能约束传播和分支策略，应该比蛮力快得多。我觉得我没有足够的经验来提出具体的建议，所以找一个看起来易于使用且相当成熟的。

于 2014-03-27T21:56:46.803 回答