0

我正在构建一个处理不同基数的程序，我想通过使用并行编程来优化它，但我对所有这些都是新手。

现在，我正在尝试实现一个并行的 Karatsuba 乘法算法：

    public static NX MulAK(NX A, NX B){
    // ¶ Safeguard:
    if(A.Base != B.Base){
        Console.Error.WriteLine("\tError:\nA multiplication of numbers with different bases was attempted!");
        return null!;
    }
    // ¶ Init:
    MatchLength(ref A, ref B);
    // Base Case:
    if(A.Len() == 1){return SingleMul(A, B[0]);}
    // ¶ Init:
    (NX A_L, NX A_H) = SplitHalf(A);
    (NX B_L, NX B_H) = SplitHalf(B);
    // ¶ Recursive calls in parallel:
    NX L;
    NX M;
    NX H;
    Parallel.Invoke(
        () => {L = MulAK(A_L,  B_L);},
        () => {M = MulAK(A_L + B_H, A_H + B_L);},
        () => {H = MulAK(A_H,  B_H);}
    );
    // Return:
    return 
        (L 
        + (M - L - H).ShiftPow(A.Len() / 2) 
        + H.ShiftPow(A.Len())
        ).ShiftPow(A.Powr + B.Powr);
}

调用 Parallel.Invoke() 时它不会显示任何错误，但在返回时会显示：

使用未分配的局部变量 'L' [NumberX] csharp(CS0165)

...对于 L 和所有其他人。

就我而言，如何使 Karatsuba 的递归调用并行工作？

4

1 回答 1

0

您会收到错误，因为编译器无法判断是否L已明确分配。此变量仅由赋予 的委托分配Parallel.Invoke，但编译器无法判断 Parallel.Invoke 是否会实际调用委托，因此您会收到错误消息。

由于您碰巧知道它实际上会这样做，因此您可以通过分配变量来规避错误：NX L = default(NX);

请注意，您通过并行运行事物的“优化”目标可能不会产生积极的结果。任何一种多线程都有一些开销，如果工作量很小，开销将占主导地位并导致性能更差。您的算法是递归的，并且在每次递归中所做的工作很少。经过几次递归后，您将安排比可运行它的内核更多的工作，因此我希望它花费大部分时间在不同任务之间切换。

我建议您改为从分析您的代码开始，以检查花费最多时间的内容。虽然您没有展示 的实现NX，但它看起来像是某种列表，并且在紧密循环内进行任何类型的分配通常对性能没有帮助。所以我希望可能有一些其他的优化比简单地并行运行更有帮助。

请记住，处理器速度非常快。程序接近处理器可以处理的最大吞吐量是相当罕见的。问题更多的是使用了糟糕的算法，或者程序大部分时间都浪费在做不必要的工作上。因此，选择合适的算法并尽量减少浪费的时间通常比并行工作更有效。一旦你确信你已经完成了这个，那么你就可以考虑并行化工作。

于 2022-01-26T15:59:17.607 回答