ACM通信
技术视角:并行计算的力量
随着计算机变得并行化，性能有问题的程序也必须变得并行化。对于某些算法来说，这并不是一个很大的挑战，因为底层问题自然地划分为可以并发计算的独立部分。其他问题就没有这么幸运了。它们的组成计算是紧密相互依赖的，并行实现需要大量的协调和同步，并且可能仍然执行得很差。
递归算法就属于这一类。递归调用是连续函数调用中的计算之间的依赖关系，这使得它们的执行很难显著重叠。没有将递归函数转换为并行执行的通用公式。有必要了解底层计算的内在结构，并找到在并行运行时保持基本关系的方法。
下面的文章展示了动态规划(一个重要的递归算法范式)的一些实例如何通过利用底层计算的代数特性来有效地并行化。动态规划使用一个表来存储子计算的值，并参考这些中间结果来计算新的值。根据所访问的值，可以沿着表的列或对角线并发地执行一些计算。然而，这些计算通常都很小。通信和同步的开销限制了哪些计算可以并行执行。此外，并行度的大小受到表大小的限制。
作者演示了另一种并行化这些计算的方法，即将表划分为独立的块，每个块都可以独立计算，然后这些中间结果“打补丁”，以正确解释本应在早期执行的计算中缺失的依赖项。这种方法的好处很明显，大型独立计算可以在多核处理器上很好地执行，并且比细粒度计算产生的开销更少。
动态规划算法是一系列递归调用，其中每个这样的调用都是输入前缀上的子计算，为当前输入上的计算产生一个结果。这个表记住了子计算，所以它们只需要计算一次。
假设我们想在上并发地执行这个调用序列P处理器。如果我们把这个序列分成P块和每个独立运行，除了第一个计算之外的所有计算都可能产生错误的答案，因为它们缺乏应该早点放入表中的结果。本文展示了如何修正一类重要问题的错误答案。
该方法适用于计算可以用一个热带半环、一个具有两个算子和一个零元的代数结构来描述的动态规划问题。对于动态规划，半环是在矩阵上定义的，通过将乘法替换为加法，将加法替换为max来重新定义标准矩阵乘积。本文的关键见解是，按顺序应用这个矩阵乘积运算永远不会增加结果矩阵的秩，在实践中，这些运算的序列通常收敛于一个秩为1的矩阵。此时，矩阵乘积序列的最终结果与排在第1位的中间结果平行，只是大小不同。
这篇论文很好地提醒了我们，超越计算的自然公式，关注其底层结构的价值。
这种洞察力导致了高效的粗粒度并行化。把这个序列分解成P独立的计算，每一个都从一个连续的乘积计算块开始。每次计算，除了第一次，都可能是错误的，因为它忽略了前面的计算。然而，它们可以通过从先前的计算中依次传播正确的结果并重新进行乘积计算来固定，直到它产生一个排名第一的矩阵，这时可以跳过其余的计算，因为最终结果只相差一个容易计算的偏移量。
在实践中，对于许多问题，收敛到秩1是非常快的;在另一些情况下，它会慢一些，或者根本不会发生。但是，在收敛速度快的情况下(例如，Viterbi和Smith-Waterman)，输入量大的情况下，得到的算法执行得非常好，甚至在后者的问题上产生了超过100核的接近线性的加速。
这篇文章很好地提醒了我们，当程序不能自然地并行化时，要超越计算的自然公式，关注其底层结构。
数字图书馆是由计算机协会出版的。版权所有©2016 ACM, Inc.