使用Task并行计算递归算法 [英] Compute a recursive algorithm in parallel using Task

问题描述

如何使用任务将这种顺序递归算法转换为并行递归算法?

how do I convert this sequential recursive algorithm into a parallel recursive algorithm using tasks?

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

我有一个例子，但它太混乱了，没有解释，也没有我的情况复杂.

I have an example, but it's too confusing, it has no explanations and is not as complex as in my case.

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

推荐答案

对于像这样的简单任务，并行化的开销相当高，因此您绝对不希望天真地并行化每个迭代.但是，示例任务相当复杂，不仅要将递归函数更改为(某种程度上)并行化的递归函数，而且还要找到额外的并行化选项以获取四个独立的工作程序.使用过时的多线程构造也使它更加复杂.考虑一个更简单的示例:

The overhead from parallelization is rather high for a simple task like this, so you definitely don't want to parallelize every iteration naïvely. However, the sample task is rather complicated in not only changing the recursive function to a (somewhat) parallelized recursive function, but finding extra parallelization options to get four independent workers. It's also further complicated by using outdated multi-threading constructs. Consider a simpler example:

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的结果缓存.

We split the original workload (rather trivially) into two branches. Since both branches have roughly similar amount of workload, this allows us to efficiently use two threads. Note that this is extremely stupid - you're computing the same thing twice, and using two threads to do the workload that a single thread could do just as well (even without a deeper understanding of recursive functions like the Fibonacci sequence) just by caching results for a given n.

但是，我认为，练习的重点是展示如何并行执行任务，无论这些任务实际可并行性如何(即，您预期变得愚蠢和天真).我们如何从两线程版本升级到四线程版本?跳过第一个迭代，然后立即从第二个迭代开始.这将为您提供四个分支，而不是原始的两个.

But I'll assume that the point of the excercise is to show how you can parallelize tasks regardless of how parallelizable those tasks actually are (i.e. you're expected to be stupid and naïve). How did we get from the two-threaded version to the four-threaded version? By skipping the first iteration, and starting on the second right away. This gives you four branches, instead of the original two.

假设您有n > 6(在示例中，否则将F1用作特殊情况). F1的第一个迭代大致可以实现:

Let's assume you have n > 6 (in the sample, F1 is used otherwise as a special case). The first iteration of F1 works out roughly to:

return F1(n - 1) + F1(n - 2);

但是我们想将其与第二个迭代合并，以允许四向并行化.这就像用F1(n)替换F1(n - 1) + F1(n - 2)一样简单:

But we want to merge this with the second iterations, to allow four-way parallelization. This is as simple as substituting F1(n) for 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);

糟糕！我们失去了一个分支.所以我们实际上需要另一个替代:

Oops! We lost one of the branches. So we actually need another substitution:

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

最终将我们带到我们的四个分支机构:

Which finally gets us to our four branches:

return
 F1(n - 3) + 3 * F1(n - 4) + 3 * F1(n - 5) + F1(n - 6);

这些分支中的每一个都可以简单地并行运行，并且您可以很好地利用所有四个线程.

Each of those branches can naïvely be run in parallel, and you get a good use of all four threads.

您现在可以希望对G1应用相同的推理，并对该特定的递归函数进行四向并行化:)

You can now hopefully apply the same reasoning to G1 and get four-way parallelization of that particular recursive function :)

这篇关于使用Task并行计算递归算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！