一个C米通信

研究突出了

利用秩收敛实现动态规划算法的高效并行

作者:Saeed Maleki, Madanlal Musuvathi, Todd Mytkowicz
ACM通信，2016年10月，第59卷第10期，85-92页
10.1145 / 2983553
评论

本文针对一类重要的动态规划问题，包括Viterbi、Needleman-Wunsch、Smith-Waterman和最长公共子序列问题，提出了一种高效的并行算法。在动态规划中，相互不依赖的子问题，因此可以并行计算，形式阶段或波阵面时。本文提出的算法提供了额外的并行性，允许多个阶段之间的依赖关系并行计算。该算法的正确性和性能依赖于热带半环上矩阵乘法的秩收敛性质，该矩阵乘法由+作为乘法运算和max作为加性运算构成。

本文通过展示在各种重要的动态规划问题上的显著加速来证明并行算法的效率。特别是，与高度优化的商业基线相比，并行Viterbi解码器的速度高达24倍(使用64个处理器)。

回到顶部

1.简介

动态规划²是解决计算机科学、经济学、基因组学和金融学中各种重要优化问题的一种方法。图1描述了两个例子:维特比，²³它通过隐马尔可夫模型找到一系列观测的最可能路径，而LCS，¹⁰查找两个输入字符串之间的最长公共子序列。动态规划算法通过递归地解决一系列子问题进行运算，这些子问题通常用图中表格中的单元格表示。子问题的解由一组适当的子问题的解构造而成，如图中各自的递归关系所示。

这些数据依赖性自然地将子问题分组为阶段它们的解互不依赖。例如，在Viterbi中，列中的所有子问题构成一级，在LCS中，反对角形式中的所有子问题构成一级。并行化动态规划的一个主要方法是波阵面并行化,¹⁵并行计算一个阶段内的所有子问题。

相反，本文打破了数据依赖性在在之后的算法中分期并修复不正确的值。因此，这种方法为我们所称的一类动态规划算法提供了并行性linear-tropical动态规划(LTDP)。LTDP计算可以看作是在热带半环中执行一系列矩阵乘法，其中半环以加法为乘法算子，以max为加法算子形成。本文论证了一些重要的优化问题，如Viterbi、LCS、Smith-Waterman和Needleman-Wunsch(后两者在生物信息学中用于序列比对)属于LTDP。为了有效地打破跨阶段的数据依赖，该算法使用排名收敛，这是热带半环中矩阵乘积序列的秩很可能收敛于1的性质。

我们的并行算法的一个关键优势是它能够同时使用跨级的粗粒度并行和级内的细粒度波前并行^一个．此外，该算法可以重用现有的利用波前并行的高度优化的实现，而无需进行很少的修改。因此，我们的实现比现有的实现实现了成倍的加速。例如，与最先进的商业基线相比，并行维特比解码器64核的速度高达24倍。¹⁸本文演示了其他LTDP实例的类似加速。

回到顶部

2.背景

2.1.热带森马

一组重要的动态规划算法可以用代数表示热带森马。热带半环有两个二元算子:⊕wherex⊕y= max (x, y)和⊗wherex⊗y＝x+y对所有x而且y在域。热带半环的定域是{ℝ∪{−∞}}，即以−∞扩展的实数集，作为半环的意思是而且．一般代数的大多数性质在热带半环中也成立，使它能够支持半环元素上的矩阵代数。有关热带半环的更详细的讨论，请参阅参考文献第2节。¹³

回到顶部

2.2.矩阵乘法

让一个_n×米用n行和米具有热带半环域元素的柱。让一个［我,我表示元素一个在我th行和j列。的矩阵乘积一个_l×米而且B_米×n是一个B,一个l×n矩阵定义了

注意，这是标准矩阵乘积，乘法用+替换，加法用max替换。

的转置一个_n×米是矩阵这样．使用标准术语，我们将表示av_n×1矩阵作为列向量,一个v_1×n矩阵作为行向量和一个x_1×1矩阵就是标量x(在这种情况下，通过传统的符号，我们可以识别x作为x_{1, - 1})．这个术语允许我们将上面矩阵-矩阵乘法的定义适当地扩展到矩阵-向量和向量-标量乘法。同时,［我)是我向量的第Th个元素．在热带半环中很容易检验矩阵乘法的结合律:．

2.3.平行向量

两个向量而且平行于热带半环，记为，如果存在非-标量x而且y这样．直觉上,平行向量而且在热带半环线上有一个恒定的偏移。例如，[1 0 2]^T和[3,2,4]^T平行向量的差值为2。

2.4.矩阵的秩

矩阵的秩米_米xn，用rank(表示米)，是最小的数r这样就存在矩阵了C_米xr而且R_rxn是谁的产品米．特别地，一个秩1矩阵是列向量和行向量的乘积。(定义半环中矩阵的秩还有其他方法，例如矩阵中线性无关的行或列的数量。虽然这些定义在普通线性代数中是一致的，但它们在任意半环中是不等价的。⁴）

引理1。对于任何一个向量而且和秩为1 a的矩阵a

直观地说，这个引理表明一个秩1的矩阵将所有的向量映射到一条直线上。如果排名(一个) = 1则它是列向量的乘积一个行向量．对于任何一个向量而且：

为适当的标量x_u而且x_v．举个例子

一个= [1 2 3]^T[0 1 2]是第1位。一个= [6 7 8]^T而且一个= [4 5 6]^T它们平行于一个常数偏移量2。还要注意，秩1矩阵中的所有行都是彼此平行的。

回到顶部

3.Linear-Tropical动态规划

动态规划是一种解决具有最优子结构的问题的方法——问题的解可以从一组重叠子问题的解中得到。子问题之间的这种依赖性可以用递归方程来表示。经典的动态规划实现迭代地解决子问题，应用递归方程的顺序尊重子问题之间的依赖性。

3.1.LTDP定义

一个动态规划问题是LTDP，如果(A)它的解和它的子问题的解在热带半环的范围内，(b)子问题可以被分组到一个阶段序列中，这样一个阶段的子问题的解只依赖于前一个阶段的解，(c)这种依赖性在热带半环中是线性的。换句话说,年代_我［j，子问题的解j在舞台上我，由递归方程给出

为合适的常数一个_我［j，k］．这种线性依赖使我们可以将LTDP看作是从初始解向量进行计算(从递归方程的基本情况中得到)，一个向量序列，其中向量的长度不需要相同，和

对于适当的常数矩阵一个_我从递归方程推导出来。我们将调用的解向量在阶段我并调用一个_我的变换矩阵在阶段我．

3.2.落后的阶段

一旦所有子问题都解决了，寻找底层LTDP优化问题的解决方案通常涉及跟踪前任子问题的落后。子问题的前身是达到式(1)最大值的子问题。为了便于说明，我们定义前任产品一个矩阵的一个和一个向量的向量一个∗这样

注意这个定义与式(1)之间的相似之处。我们假设arg max中的tie被确定性地打破。下面的引理表明，以前的乘积不能区分平行向量，这个性质以后会很有用。

这是根据以下事实得出的:热带半环中的平行向量相差一个常数，当将一个常数加到它的所有参数中时，arg max是不变的。

3.3.顺序LTDP

的顺序LTDP算法可以用公式2表示为矩阵乘法。假设LTDP问题n+ 1阶段在哪里初始解向量是否作为输入参数和给出是所需的输出解。输出解可以用变换矩阵来计算一个₁、……一个_n它捕获了如式(2)所示的LTDP递归的归纳情况。序列算法由前向阶段和后向阶段组成。

前向阶段迭代计算解n迭代。在迭代我,它计算而且．该算法被认为是顺序的，因为由于跨阶段的数据依赖性，它一个接一个地计算阶段。

后向阶段迭代地遵循在前向阶段计算的解的前身。根据LTDP问题，最后阶段的子问题之一年代_n(选择)，包含最优解。那么LTDP问题沿最优路径的解为

这些很容易通过在线性时间内从阶段回溯路径来计算n阶段0。

上面的阐述有意识地隐藏了很多细节∗运营商。实现不需要将阶段中的解表示为(密集的)向量并执行(密集的)矩阵-向量操作。它可能静态地知道当前的解决方案只依赖于前一阶段(一个稀疏矩阵)中的一些子问题，并且只访问那些子问题。此外，如上所述，实现可以使用波前并行计算一个级中的解。最后，实现可以使用像平铺这样的技术来提高顺序计算的缓存效率。所有这些实现细节都与本文中描述的并行算法如何跨阶段并行有关。

回到顶部

4.并行LTDP算法

本节将跨阶段描述第4节中描述的顺序算法的一种高效并行算法。

4.1.破坏跨阶段的数据依赖

将LTDP计算视为热带半环中的矩阵乘法提供了一种打破阶段间数据依赖的方法。考虑最后阶段的解向量．由式(2)可得

标准技术^9，12可以利用矩阵乘法的结合律并行化这个计算。例如，两个处理器可以计算部分乘积一个_{⌊n/ 2⌋+ 1}而且并行，然后计算一个_嗨一个_罗获得．

但是，这样做将执行矩阵-向量乘法的顺序计算(从右向左工作)转换为执行矩阵-矩阵乘法的并行计算。这导致了并行化开销的线性级大小，因此需要线性数量的处理器来观察恒定的加速。实际上，每个阶段的大小很容易达到数百甚至更大，因此在实际问题和硬件上是不实际的。

本文的主要贡献是一种避免了矩阵-矩阵乘法开销的并行算法。该算法依赖于下面讨论的热带半环矩阵秩的收敛性。它的说明需要以下定义:对于给定的LTDP实例，部分产品米_我→j，定义为阶段我≤j，由

请注意,米_我→rj描述了舞台j取决于阶段我,因为．

4.2.排名收敛

两个矩阵乘积的秩不大于任何一个输入矩阵的秩。

这是因为，如果rank(一个) =r,然后一个＝CR对于一些矩阵C与r列。因此,一个B= (CR）B＝C（RB)暗示等级(一个B)≤排名(一个)．类似的参数显示rank(一个B)≤排名(B)．

方程3表示对于阶段k≥j≥我

实际上，随着LTDP计算的进行，部分乘积的秩将永远不会增加。从理论上讲，有一种可能性是队列不减少。但是，我们只观察到在实践中不太可能发生的精心设计的问题实例。相反，这些部分乘积的秩很可能收敛于1，如第6.1节所示。

考虑一个部分积米_我→j他的排名是1。直观上，这意味着弱阶段之间的依赖我而且j。而不是实际的解向量，假设LTDP计算从一个不同的向量开始在阶段我。由引理1，新的解向量在阶段j，，与实际解向量平行．本质上，就是解向量在这个阶段的方向j与阶段无关我；阶段我只决定了它的大小。在热带半环中，乘算子为+，这意味着阶段的解向量j在最坏的情况下，会差一个常数吗我用一个任意的向量。

4.3.平行前进阶段

并行算法利用这种洞察力来打破阶段之间的依赖关系，如图所示图2．这个图使用了三个处理器，P₀，P₁,P₂，以每个处理器6个阶段为例，其余共18个阶段．图2一个表示第4节中描述的顺序算法的前向阶段。每个阶段都用垂直的单元格列表示。(为了画图简单，我们假设每个解向量的长度为4，但通常它们的长度可能不同。)请注意,P₀还包含初始解；还要注意这个阶段之间共享P₀而且P₁，和相似阶段之间共享P₁而且P₂．这些复制阶段由虚线边界区分。每一个阶段通过乘以通过变换矩阵一个_我(公式2)处理器P₀从初始解向量开始年代₀并计算它的所有阶段。如左侧箭头所示，处理器P₁等待P₀计算共享阶段才能开始计算。同样,处理器P₂等待P₁计算共享阶段如右边箭头所示。

在并行算法中所示图2 b、处理器P₁而且P₂从任意的解决方案而且分别平行于P₀．当然，各阶段的解由P₁而且P₂一开始是完全错误的(图中阴影较暗)。然而，如果发生秩收敛，那么这些错误的解向量最终会与实际解向量平行(图中灰色阴影部分)。因此,P₁会生成解向量吗平行于．

在随后的固定相所示,图2 c，P₁使用计算P₀,P₂使用计算P₁，以固定与该阶段实际解向量不平行的阶段。当一个新的计算阶段与前向阶段的计算阶段平行时(通过一个常数关闭)，固定阶段终止。(如果秩收敛没有发生P₁，然后在修理阶段，P₁可能要修理所有的阶段，包括因为它不平行于它是从．在这种情况下，P₂需要重新进行修理阶段。因此，在最坏的情况下，并行算法优雅地简化为串行算法。)在固定之后，每个阶段的解向量与这些各自阶段的实际解向量相同或平行。

对于LTDP，不需要计算实际的解向量。因为平行向量生成相同的前产物(引理2)，在图2 c会生成与前面的解相同的解图2一个．

该算法的通用版本包含伪代码，详见参考文献的第4节。¹³关于正确性(参见参考文献4.4节)。¹³)，并行算法要求任意向量(而且在图2)非．使用与前向阶段相似的思想(参见参考文献中的4.6节)，也可以对后向阶段进行并行化。¹³)．

4.4.排名收敛的讨论

可以将解决LTDP问题视为计算图中的最短(或最长)路径。在这个图中，每个子问题是一个节点，有向边表示子问题之间的依赖关系。边上的权值代表常数一个_我［j，k在式1中。LCS (图1 b)，每个子问题都有来自它上面和它左边的子问题的权值为0的传入边，以及一个权值为0的传入边δ_我,我从对角线附近。找到LTDP问题的最优解等于找到这个图中的最长路径C_0,0来C_{m, n}(米而且n是两个输入字符串的长度)。或者，我们可以否定所有的权重，并将式(1)中的最大值改为最小值，将其视为计算最短路径。

偏积中的项米_{l r→}表示从一个节点出发的最短(或最长)路径的代价l到阶段中的节点r。这个乘积的秩是1如果这些最短路径都经过一个节点l而且r。道路网络具有这种特性。例如，从华盛顿州的任何一个城市到马萨诸塞州的任何一个城市的最快路径极有可能经过芝加哥，因为使用I-90州际公路的路线绝对比不使用的要好;城市在开始和结束时的选择不会极大地改变中间阶段的路线。类似地，如果问题实例具有压倒性优于其他解决方案的最优解，则应该期望秩收敛。

回到顶部

5.LTDP例子

本节展示了四个重要优化问题的LTDP解决方案:Viterbi、最长公共子序列、Smith-Waterman和Needleman-Wunsch。我们选择这些特定问题的目的是提供一种直观的理解，即如何将具有不同结构的问题视为LTDP。LTDP的其他应用，在本文中没有评估，包括动态时间翘曲和缝雕刻。

5.1.维特比

维特比算法²³的(离散)隐马尔可夫模型(HMM)中最可能的状态序列n观察。其递归方程如图1一个(参考参考。²³对于意义的p_我,我而且t_{j k,}条款)。图中沿着一列的子问题形成一个阶段，它们只依赖于前一列中的子问题。这种依赖关系并不是方程(1)所期望的形式，但是将对数函数应用到递归方程的两边就得到了这种形式。通过将Viterbi实例转换为计算对数概率而不是概率的实例，我们获得了一个LTDP实例。

5.2.最长公共子序列

LCS查找两个输入字符串的最长公共子序列一个而且B。¹⁰LCS的递推方程如图1 b．在这里,C_我,我是第一个的lcs的长度吗我字符的一个和第一j字符的B(其中子序列的相邻字符在原始序列中不必相邻，但必须以相同的顺序出现)。同时,δ_我,我为1，如果我th的特点一个是一样的jth的特点B和0。LCS的一个而且B中表中最右下的前一项得到的图1 b．

LCS的一些应用，例如diff实用工具，只对最多一个宽度的解感兴趣w远离主对角线，确保LCS仍然与输入字符串相当相似。对于这些应用，递归关系可以修改到C_我,我当|我−j| >w．实际上，这种修改限制了每个阶段的大小，这反过来又限制了波前并行，增加了我们在这里提出的并行执行多个级的需要。

将LCS的子问题分组分为阶段有两种方法，如图3．在第一种方法中，阶段对应反对角线，如阶段组成z_我年代图3一．这个阶段依赖于前面的两个阶段x_我年代和y_我s)并且不严格遵守LTDP的规则。解决这个问题的一种方法是将阶段定义为重叠的反对角线对，如阶段x−和舞台y−z在图3一．子问题y_我S在两个阶段复制，允许阶段y−z只依靠舞台x−．虽然这种表示方式的缺点是每个阶段的大小增加了一倍，但它有时会导致高效的表示。对于LCS，可以证明一个阶段中连续子问题的解之间的差是1或0。这允许将阶段紧凑地表示为一个位序列。¹¹

在第二种方法中，阶段对应于中所示的行(或列)图3 b．需要展开递归，以避免一个阶段内子问题之间的依赖关系。例如,问_我取决于所有p_j为j≤我。在这种方法中，由于最终解是从最后一个条目中获得的，所以在后向阶段中的前一个遍历必须被修改以从这个条目开始，比如在末尾添加一个额外的矩阵来将这个解移动到添加阶段中的第一个解。

5.3.Needleman-Wunsch

这个算法¹⁷发现一个全球两个输入序列的比对，通常用于蛋白质或DNA序列的比对。递归方程与LCS中的递归方程非常相似。

在这个方程,年代_我,我长度前缀的最佳对齐分数是多少我第一个输入和长度的前缀j对于第二个输入，米［我,我是对齐各自前缀的最后一个字符的匹配得分，和d是对齐期间插入或删除的惩罚。基本用例定义为年代_我，0=−我·d而且年代_0，j＝- j·d．此外，可以使用与LCS中相同的方法将子问题分组为阶段。

5.4.均为

这个算法¹⁹执行一个当地的序列比对，与Needleman-Wunsch相反。给定两个输入字符串，Smith-Waterman找到子字符串有最佳对齐的输入，其中较长的子串有较好的对齐。递归方程的最简单形式是

与Needleman-Wunsch的关键区别是max中的0项，它确保了当分数低于0时对齐“重新启动”。因为这一项，常数一个_我需要对式1中的矩阵进行相应设置。这个细微的变化显著地影响了Smith-Waterman的收敛特性(见第6.1节)。

回到顶部

6.评价

本节评估在第5节中讨论的四个问题上的并行LTDP算法。

6.1.LTDP排名收敛

确定LTDP并行算法是否有利于动态规划问题需要:(1)问题是LTDP(在第4节中讨论)和(2)秩收敛发生在合理数量的步骤中。本节演示如何度量秩收敛，并对第5节中讨论的LTDP问题进行评估。

秩收敛是矩阵乘法序列的经验性质，它既依赖于LTDP递归关系又依赖于输入。表1提出了度量跨不同算法和输入的秩收敛所需的步骤数。对于由算法(第1列)和输入(第2列)定义的LTDP实例，我们首先计算每个阶段的实际解向量。然后，从一个随机的全非零向量开始，在200个不同的等间距阶段，我们测量了收敛到一个与实际解向量平行的向量所需的步数。列3、4和5分别显示了收敛所需的最小、中值和最大步骤数。对于每个输入，第2列指定计算宽度(每个阶段的大小)。每种算法对宽度都有特定的定义:对于维特比解码器，宽度是每个解码器的状态数;在Smith-Waterman中，它是每个查询的大小;在LCS和Needleman-Wunsch中，它是每个阶段对角线周围的固定宽度。在某些情况下，LCS从不收敛，因此我们将这些条目留空。收敛速度取决于算法和输入(例如，Smith-Waterman收敛速度很快，而LCS有时不收敛)，一般来说，更宽的宽度需要更多的步骤来收敛。 We use this table later in Section 6.3 to explain scalability of our approach.

6.2.环境设置

我们在共享内存机器和分布式内存机器上进行了实验。共享内存机有利于快速通信，是波前方法的理想选择。分布式内存机器拥有更多的处理器，因此我们可以更好地理解并行算法是如何扩展的。共享内存有40核(Intel Xeon E7)。这种分布式内存机器被称为Stampede²¹；在我们的实验中，我们使用了128个核(英特尔至强E5)。看到裁判。¹³为更多的细节。

6.3.并行LTDP基准测试和性能

本节评估了四个LTDP问题的并行算法。为了证实我们的可伸缩性结果，我们在各种各样的实际输入中评估每个基准测试。我们将结果分解为LTDP问题。对于每个LTDP问题，我们使用现有的最佳顺序算法作为基线，如下所述。对于并行LTDP算法，我们实现了第4节中描述的算法，并使用顺序基线实现作为黑箱从一个阶段推进到下一个阶段。

维特比译码器。作为我们的基线，我们使用了Spiral¹⁸维特比解码器，一个高度优化(通过自动调谐)的解码器，利用SIMD在一个阶段内并行解码。我们使用两种真实的卷积码，CDMA和LTE，它们在现代手机网络中普遍使用。对于这两个卷积码，我们研究了四种网络包大小(2048、4096、8192和16384)的影响，它们决定了计算中的阶段数。对于每种大小，我们使用Spiral的输入生成器创建50个网络数据包，并考虑平均性能。

图4显示两种解码器的性能、加速和效率。为了评估不同解码器大小的影响，每个图有四行(每个网络包大小有一行)。一个点(x, y)在性能/加速情节与主要y-axis表示吞吐量y(每秒处理的比特数)以每秒兆比特(Mb/s)作为处理器数量的函数x用于执行维特比解码。第二个问题也是一样的y右边的-轴显示了加速y与x处理器数量超过顺序性能。注意，螺旋顺序性能x对于不同的包大小，= 1几乎是相同的。图中填充的数据点表明，在第4节描述的并行LTDP算法的固定阶段的第一次迭代中发生了收敛(即，每个处理器的阶段都足够大，可以收敛)。未填充的数据点表明需要多次迭代修复循环。

图4证明了(i)我们的方法在顺序基线上提供了显著的加速，(ii)不同的卷积码和网络包大小有不同的性能特征。例如，在64个处理器的情况下，我们的CDMA维特比解码器处理大小为16384的数据包的解码速度比顺序算法快了约24倍，而我们的LTE解码器的解码速度为约13倍。这种差异是由于CDMA的每比特计算量是LTE的4倍，但收敛速度的中位数几乎相同(表1)．另外，请注意图4，更大的网络包大小在所有卷积码上提供更好的性能(即，网络包大小为16,384为总是最快的实现，不考虑卷积代码)，因为重新计算的量(即计算中没有收敛的部分)，作为整个计算的比例，随着网络包大小的增大而减少。

均为。我们的基线实现了已知最快的CPU版本，Farrar的算法，它利用SIMD在一个阶段内并行化。⁵对于数据，我们将人类参考基因组hg19中的1、2、3和4号染色体作为数据库，并将四个随机选择的表达序列标记作为查询。所有的输入都可以从Ref下载。¹⁶我们报告了所有DNA和查询组合(共16个)的平均性能。

一个点(x, y)在性能/加速情节中图5与主y-轴在左边，给出性能y以每秒千兆单元更新(GigaCUPS)为单位，作为用于执行Smith-Waterman对齐的处理器数量的函数。GigaCUPS是生物信息学中用来衡量基于dna的序列比对问题性能的标准指标，它指的是每秒更新的细胞数量(在动态规划表中)。类似维特比解码器的情节，次要的y左边的-轴显示每个处理器数量的加速。

我们的方法对该算法的性能增益是显著的。作为图5演示，并行LTDP算法在多达128个处理器的情况下提供几乎线性的加速。我们的算法在处理器数量更高的情况下也能很好地扩展，但我们报告最多只能保留128个处理器图5和其他的一致。

Needleman-Wunsch。我们的基线使用SIMD并行化在采用分组技术的阶段图3一．对于数据，我们使用两对DNA序列作为输入:人类染色体(21,22)和(X, Y)来自人类参考基因组hg19。我们只使用每个序列的前100万个元素，因为Stampede在单个节点上没有足够的内存来存储完整染色体的细胞值。我们还只使用了4种不同的宽度(1024、2048、4096和8192)，因为我们发现宽度大于8192并不影响最终的对齐评分。

图6显示了使用我们的方法并行化的Needleman-Wunsch算法的性能和加速。秩收敛依赖于输入数据;因此，并行LTDP算法在对(X, Y)和(21,22)，如图所示。图中的图显示了每种宽度大小的结果:1024、2048、4096和8192。与Viterbi解码器基准测试类似，填充/非填充数据点显示是否在修复阶段的第一次迭代中发生了收敛。

在图6，较大的宽度比较小的宽度表现更差，因为收敛速度取决于LTDP实例中每个阶段的大小。

LCS。我们的基线采用已知最快的LCS单核算法，利用位并行来并行计算在一个列。^3.，11该方法使用中所示的分组技术图3 b．对于数据，我们使用了与Needleman-Wunsch相同的输入数据，只是我们使用了以下4个宽度:8192、16,384、32,768和65,536。我们报告的业绩数字为Needleman-Wunsch。

性能和加速图图7很像图6:输入对的选择对秩收敛有很大的影响图7．

LTDP和波阵面。我们还比较了我们的LTDP并行方法和LCS和Needleman-Wunsch的波前方法。参见参考文献6.4节。¹³获取详细信息。

回到顶部

7.相关工作

由于它的重要性，在并行化动态规划方面已有大量的工作。主要的实现是使用波前并行在一个阶段内进行并行化。例如，Martins等人使用波前并行构建了基于消息传递的序列对齐动态程序(例如Smith-Waterman和Needleman-Wunsch)实现。¹⁴相比之下，本文利用的是与波前并行正交的跨级并行。

Stivala等人使用了一种并行化动态规划的替代策略。^20.他们使用一种“自顶向下”的方法，通过递归并行地解决子问题来解决动态规划问题。为了避免对同一个子问题的冗余解决方案，他们使用无锁定的数据结构来记住子问题的结果。这种共享的数据结构使得跨多台机器的并行化非常困难。

还有大量关于动态规划实例的并行复杂性的理论工作。他们中的一些人^1，8，22将动态规划实例视为在适当的图中寻找最短路径，并并行计算图分区中的全对最短路径。我们的工作建立在这些见解之上，可以看作是使用秩收敛来有效地计算全对最短路径。

以前的工作也做了和利用了类似秩收敛的观察。维特比解码的经典作品²⁴使用解码路径的收敛来同步解码，并通过截断后向阶段的路径来节省内存。Fettweis和Meyr^6，7利用这个观察结果，通过处理输入的重叠块来并行化维特比解码。然而，尽管在极其罕见的情况下，它们的并行化可能产生错误的解码。

回到顶部

8.结论

本文介绍了一种新的方法来并行求解一类动态规划问题，即线性-热带动态规划问题，该问题包括Viterbi和最长公共子序列等重要优化问题。该算法利用热带半环的代数性质，有效地打破了数据依赖性。

我们的实现比优化后的顺序实现有显著的加速。特别是，并行维特比解码比高度优化的商业基线快24倍(64核)。

当我们在集群上评估我们的方法时，我们期望在各种并行硬件平台(共享内存机器、gpu和fpga)上得到同样令人印象深刻的结果。

回到顶部

致谢

本材料基于国家科学基金会资助的工作。CNS 1111407。作者感谢德克萨斯州高级计算中心为Stampede集群提供的计算时间。我们也非常感谢Guy Steele为编辑本文所做的宝贵评论和努力。我们还要感谢Serdar Tasiran和匿名审稿人对本文的有益反馈。

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2016 ACM, Inc.

---

没有发现记录