使用Task并行计算递归算法
如何使用任务将此顺序递归算法转换为并行递归算法？
public static List s = new List(); // random integers, array size is n public static List p = new List(); // random integers, array size is n public static int n = 100; public static int w = 10; static void Main(string[] args) { G1(n, w) } private static int G1(int k, int r) { if (k == 0 || r == 0) { return 0; } if (s[k - 1] > r) { return G1(k - 1, r); } return Math.Max(G1(k - 1, r), p[k - 1] + G1(k - 1, r - s[k - 1])); } 我有一个例子，但它太混乱了，它没有解释，也没有我的情况那么复杂。
class CustomData { public int TNum; public int TResult; } static int F1(int n) { if (n > 1) return F1(n - 1) + F1(n - 2); else return 1; } static int F2(int n) { int fibnum = 0; if (n < 6) fibnum = F1(n); else { //fibnum = F1(n - 3) + 3 * F1(n - 4) + 3 * F1(n - 5) + F1(n - 6); int countCPU = 4; Task[] tasks = new Task[countCPU]; for (var j = 0; j { var data = pp as CustomData; if (data == null) return; data.TResult = F1(n - data.TNum - 3); }, new CustomData() {TNum = j }); Task.WaitAll(tasks); fibnum = (tasks[0].AsyncState as CustomData).TResult + 3 * (tasks[1].AsyncState as CustomData).TResult + 3 * (tasks[2].AsyncState as CustomData).TResult + (tasks[3].AsyncState as CustomData).TResult; } return fibnum; }
对于像这样的简单任务，并行化的开销相当高，所以你绝对不希望天真地并行化每次迭代。 但是，样本任务相当复杂，不仅要将递归函数更改为（某种程度上）并行化的递归函数，还要找到额外的并行化选项以获得四个独立的工作者。 使用过时的multithreading结构也使问题变得更加复杂。 考虑一个更简单的例子：
static int F2(int n) { if (n <= 1) return 1; var a = Task.Run(() => F1(n - 1)); var b = Task.Run(() => F1(n - 2)); return a.Result + b.Result; }
我们将原始工作量（相当简单）分成两个分支。 由于两个分支的工作负载大致相似，因此我们可以有效地使用两个线程。 请注意，这是非常愚蠢的 – 你计算两次相同的东西，并使用两个线程来完成单个线程可以做的工作量（即使没有更深入地理解像Fibonacci序列这样的递归函数）只是通过缓存给定n结果。
但是我会假设练习的目的是展示如何并行化任务， 无论这些任务实际上是多么可并行化（即你被期望是愚蠢和幼稚的）。 我们是如何从双线程版本到四线程版本的？ 跳过第一次迭代，然后立即开始第二次迭代。 这为您提供了四个分支，而不是原始的两个分支。
假设你有n > 6 （在样本中， F1被用作特殊情况）。 F1的第一次迭代主要用于：
return F1(n - 1) + F1(n - 2);
但我们希望将其与第二次迭代合并，以允许四向并行化。 这就像用F1(n)代替F1(n - 1) + F1(n - 2) ：
return F1((n - 1) - 1) + F1((n - 1) - 2) + F1((n - 2) - 1) + F1((n - 2) - 2);
哪个可以简化为
return F1(n - 2) + F1(n - 3) + F1(n - 3) + F1(n - 4);
并进一步
return F1(n - 2) + 2 * F1(n - 3) + F1(n - 4);
哎呀！ 我们失去了一个分支机构。 所以我们确实需要另一种替代：
return F1((n - 2) - 1) + F1((n - 2) - 2) + 2 * (F1((n - 3) - 1) + F1((n - 3) - 2)) + F1((n - 4) - 1) + F1((n - 4) - 2);
哪个适用于……
return F1(n - 3) + F1(n - 4) + 2 * F1(n - 4) + 2 * F1(n - 5) + F1(n - 5) + F1(n - 6);
最终让我们进入了四个分支：
return F1(n - 3) + 3 * F1(n - 4) + 3 * F1(n - 5) + F1(n - 6);
这些分支中的每一个都可以天真地并行运行，并且您可以很好地利用所有四个线程。
您现在可以将相同的推理应用于G1并获得该特定递归函数的四向并行化:)
@Luaan这是我的解决方案，使用两个线程。 我不知道它是否正常，但顺序和并行算法的结果是匹配的，但是时间的减少极少，可能需要使用更多的线程？
private static int G2(int k, int r) { if (k == 0 || r == 0) return 0; if (s[k - 1] > r) // this part gives the wrong results :( { Task task1 = Task.Run(() => G1(k - 2, r)); Task task2 = Task.Run(() => G1(k - 3, r)); return task1.Result + task2.Result; } Task max1 = Task.Run(() => G1(k - 1, r)); Task max2 = Task.Run(() => p[k - 1] + G1(k - 1, r - s[k - 1])); return Math.Max(max1.Result, max2.Result); }
如果（s [k – 1]> r）块给出错误的结果:(