使用 Task 并行计算递归算法

Question

如何使用任务将此顺序递归算法转换为并行递归算法？

public static List<int> s = new List<int>(); // random integers, array size is n
public static List<int> p = new List<int>(); // 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 < countCPU; j++)
tasks[j] = Task.Factory.StartNew(
(Object pp) =>
{
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;
}

Answer 1

对于像这样的简单任务，并行化的开销相当高，因此您绝对不希望天真地并行化每次迭代。但是，示例任务相当复杂，不仅将递归函数更改为(有点)并行递归函数，而且还要找到额外的并行化选项来获得四个独立的工作线程。通过使用过时的多线程结构，它也变得更加复杂。考虑一个更简单的例子：

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;
}

我们将原始工作负载(相当微不足道)拆分为两个分支。由于两个分支的工作负载量大致相似，这使我们能够有效地使用两个线程。请注意，这是非常愚蠢的 - 你正在计算同样的事情两次，并使用两个线程来完成单个线程也可以做的工作负载(即使没有更深入地了解斐波那契数列等递归函数)，只需缓存给定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并获得该特定递归函数的四向并行化:)

Answer 2

@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<int> task1 = Task.Run(() => G1(k - 2, r));
Task<int> task2 = Task.Run(() => G1(k - 3, r));
return task1.Result + task2.Result;
}
Task<int> max1 = Task.Run(() => G1(k - 1, r));
Task<int> max2 = Task.Run(() => p[k - 1] + G1(k - 1, r - s[k - 1]));
return Math.Max(max1.Result, max2.Result);
}

如果 (S[K - 1]> R) 块给出错误的结果:(