如何让斐波那契数计算利用全部CPU线程以满负荷运行？

你的串行斐波那契计算是强依赖迭代，每一步都需要前两项的结果，这也是为什么Parallel.For完全无效的原因——没法把独立的计算任务分配给多个核心。要利用多核心，必须换用可分治的斐波那契算法，通过拆分计算任务为独立子任务来并行执行。

核心思路：斐波那契分治公式 #

斐波那契数列可以通过以下分治公式拆分计算：

• 当n为偶数时：F(2n) = F(n) * [ 2*F(n-1) + F(n) ]
• 当n为奇数时：F(2n+1) = F(n+1)² + F(n)²

基于这个公式，我们可以把计算F(n)的任务拆分为计算更小的斐波那契数，这些子任务可以并行执行，从而利用多个CPU核心。

实现步骤 #

1. 获取当前系统的CPU核心数：使用Environment.ProcessorCount。
2. 实现分治+并行的斐波那契计算：递归拆分任务，当子任务足够大时，用Task并行执行子计算，合并结果；当子任务较小时（设置阈值，比如1000），用串行迭代避免并行开销。

完整代码示例 #

using System;
using System.Numerics;
using System.Threading.Tasks;

static public class Operations
{
    // 并行计算的阈值：当n小于该值时用串行，避免并行开销
    private const int ParallelThreshold = 1000;

    static public BigInteger CalculateFib(int iterations)
    {
        if (iterations < 0)
            throw new ArgumentOutOfRangeException(nameof(iterations), "迭代次数不能为负数");
        if (iterations == 0)
            return 0;
        if (iterations == 1)
            return 1;

        // 获取CPU核心数（线程池会基于此合理分配任务到核心）
        int coreCount = Environment.ProcessorCount;

        // 调用分治并行方法
        return ParallelFib(iterations);
    }

    private static BigInteger ParallelFib(int n)
    {
        // 小任务用串行迭代，避免并行调度开销
        if (n <= ParallelThreshold)
            return SerialFib(n);

        if (n % 2 == 0)
        {
            int k = n / 2;
            // 并行计算两个独立子任务
            var taskFk = Task.Run(() => ParallelFib(k));
            var taskFkMinus1 = Task.Run(() => ParallelFib(k - 1));
            Task.WaitAll(taskFk, taskFkMinus1);

            BigInteger fk = taskFk.Result;
            BigInteger fkMinus1 = taskFkMinus1.Result;
            return fk * (2 * fkMinus1 + fk);
        }
        else
        {
            int k = (n - 1) / 2;
            // 并行计算两个独立子任务
            var taskFkPlus1 = Task.Run(() => ParallelFib(k + 1));
            var taskFk = Task.Run(() => ParallelFib(k));
            Task.WaitAll(taskFkPlus1, taskFk);

            BigInteger fkPlus1 = taskFkPlus1.Result;
            BigInteger fk = taskFk.Result;
            return fkPlus1 * fkPlus1 + fk * fk;
        }
    }

    // 原有的串行迭代实现
    private static BigInteger SerialFib(int n)
    {
        BigInteger a = 0;
        BigInteger b = 1;
        for (int i = 0; i < n; i++)
        {
            BigInteger temp = a;
            a = b;
            b = temp + b;
        }
        return a;
    }
}

关键说明 #

• 并行阈值：设置ParallelThreshold是因为当n很小时，并行创建Task的开销会超过多核心计算的收益，小任务用串行更高效。
• CPU利用率：Task.Run会依托系统线程池调度任务，线程池会根据Environment.ProcessorCount的核心数，将任务分配到各个CPU核心，从而达到接近100%的CPU利用率。
• 效率提升：分治算法的时间复杂度为O(log n)，比原串行的O(n)效率提升显著，结合并行后，处理大迭代次数时速度会有质的飞跃。

内容的提问来源于stack exchange，提问作者user29362427