具有多个线程的并行阶乘

Question

我正试图制作一个函数，并行计算一个数字的阶乘，只是为了测试目的。假设我的cpu上有4个核心，所以我将把"问题"分成4块。

这么说，我做了这个：

public class FactorialPTest
{
    public static object _locker = new object();
    public static long Factorial(int x)
    {
        long result = 1;
        int right = 0;
        int nr = x;
        bool done = false;
        for (int i = 0; i < nr; i += (nr / 4))
        {
            int step = i;
            new Thread(new ThreadStart(() =>
                {
                    right = (step + nr / 4) > nr ? nr : (step + nr / 4);
                    long chunkResult = ChunkFactorial(step + 1, right);
                    lock (_locker)
                    {
                        result *= chunkResult;
                        if (right == nr)
                            done = true;
                    }
                })).Start();
        }
        while(!done)
        { 
            Thread.Sleep(10);
        }
        return result;
    }
    public static long ChunkFactorial(int left, int right)
    {
        //Console.WriteLine("left: {0} ; right: {1}", left, right);
        Console.WriteLine("ChunkFactorial Thread ID :" + Thread.CurrentThread.ManagedThreadId);
        if (left == right)
            return left == 0 ? 1 : left;
        else return right * ChunkFactorial(left, right - 1);
    }
    public static void main()
    {
        Console.WriteLine(Factorial(15));
    }
}

有时是有效的，有时它给了我中间的结果，有时会发生死锁。

为什么会发生这种情况？Thread.Sleep(10)不应该暂停主线程直到我得到最终结果吗？

Answer 1

我建议查看任务并行库。除其他外，它将抽象掉许多与多线程相关的低关注点。

你可以用一个任务来表示每一块工作，添加到一个集合中，然后等待它们全部完成：

public static long Factorial(int x)
{
    long result = 1;
    int right = 0;
    int nr = x;
    bool done = false;
    var tasks = new List<Task>();
    for (int i = 0; i < nr; i += (nr / 4))
    {
        int step = i;
        tasks.Add(Task.Run(() =>
            {
                right = (step + nr / 4) > nr ? nr : (step + nr / 4);
                long chunkResult = ChunkFactorial(step + 1, right);
                lock (_locker)
                {
                    result *= chunkResult;
                }
            }));
    }
    Task.WaitAll(tasks.ToArray());
    return result;
}

在您的原始代码中，可以想象最后一个块可以首先完成它的工作，并且right将等于nr，即使其他块尚未计算。此外，right在所有线程之间共享，因此这也可能导致一些不可预测的结果，即所有线程都试图使用此变量同时保存不同的值。

一般来说，如果可能的话，应该尽量避免线程之间共享状态。上面的代码可以通过让每个任务返回其结果来改进，然后使用这些结果来计算最终结果：

public static long Factorial(int x)
{
    int nr = x;
    var tasks = new List<Task<long>>();
    for (int i = 0; i < nr; i += (nr / 4))
    {
        int step = i;
        tasks.Add(Task.Run(() =>
            {
                int right = (step + nr / 4) > nr ? nr : (step + nr / 4);
                return ChunkFactorial(step + 1, right);
            }));
    }
    Task.WaitAll(tasks.ToArray());
    return tasks.Select(t => t.Result).Aggregate(((i, next) => i * next));
}

Answer 2

您可以使用一个带有聚合的Parallel.For重载，它将为您处理并行性、工作负载分区和结果聚合。对于long类型的结果，如果我没有错的话，你只能做21的阶乘。添加checked {...}来捕获溢出也是有意义的。代码可能看起来像：

    public long CalculateFactorial(long value)
    {
        var result = 1L;
        var syncRoot = new object();
        checked
        {
            Parallel.For(
                // always 1
                1L,
                // target value
                value,
                // if need more control, add { MaxDegreeOfParallelism = 4}
                new ParallelOptions(),
                // thread local result init
                () => 1L,
                // next value
                (i, state, localState) => localState * i,
                // aggregate local thread results
                localState =>
                {
                    lock (syncRoot)
                    {
                        result *= localState;
                    }
                }
                );                
        }
        return result;
    }

希望这能有所帮助。