多线程并行阶乘

Question

我正在尝试制作一个并行计算数字阶乘的函数，仅用于测试目的。假设我的 cpu 上有 4 个内核，所以我会将 "problem" 分成 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

我建议查看 Task Parallel Library。除其他事项外，它将抽象出许多与多线程相关的低关注点。

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

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 在所有线程之间共享，因此这也可能导致一些不可预测的结果，即所有线程都试图同时使用此变量来保存不同的值。

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

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

希望对您有所帮助。

多线程并行阶乘

Parallel factorial with multiple threads

c#

.net

multithreading

parallel-processing

factorial