用于混合gpu/cpu数据处理的方法
用于混合gpu/cpu数据处理的方法
【专利说明】用于混合GPU/CPU数据处理的方法 相关申请的交叉引用 本申请是一个PCT国际申请，其要求序列号为61/743, 607、题目为Methods for Hybrid GPU/CPU Data Processing的于2012年9月7日提交的美国临时申请的权益，该美国临时 申请的全部内容通过引用合并于本申请中。 技术领域 此发明涉及数据处理的领域。更具体地，此发明涉及用来在并行处理器平台上执行大 规模图形遍历的方法。 【背景技术】 近年来，对于计算机而言具有多核进程和许多核进程已经变得更加普遍，通过以并行 方式横跨不同处理核执行复杂的计算任务显著地增加了可以执行这样的任务的速度。然而 对于一些复杂的计算任务而言，这样的处理器受到它们存储器容量的限制。例如，许多核图 形处理单元（GPU)具有2-8千兆字节（GB)的存储器的限制。对于包括许多数百万计的弧 和模型的图形结构的这样的大规模图形遍历的计算可能在规模上处于GB的100s的量级或 者更大量级的任务而言，此存储器呈现出极限。 因而，存在对通过有效地支持异类并行计算核有效地在并行处理器平台上执行大规模 图形遍历的方法的需要。 需要这样的改进的方法的一个领域是大词汇连续语音识别（large vocabulary continuous speech recognition, LVCSR)领域。作为这样的需要的一个示例，话音用户接 口作为用于下一代智能设备的核心技术正在不断发展。为了确保吸引用户体验，关键的是 用在这些系统内的语音识别引擎是鲁棒的、快速的、具有低延迟并且在系统可能遇到的极 其大的词汇上提供充足的覆盖性。为了获得高的识别准确性，用于诸如广播新闻手稿[1，2] 或者话音搜索[3, 4]之类的任务的现有技术水平的语音识别系统可以在大词汇（>1百万个 词）、大声学模型（数百万的模型参数）以及极其大的语言模型（数十亿的n-gram个条目） 的情况下执行识别。在可以把这些模型应用在离线语音识别任务中时，对于实时语音识别 而言由于在解码期间需要大的计算成本的原因它们是不可实施的。 使用静态编制的加权有限状态转换机（Weighted Finite State Transducer，WFST)网 络，其中，WFST表示隐马尔可夫模型（Hidden Markov Model, HMM)，声学模型H、上下文模 型C、发音词典L、和语言模型G被组成为一个单个网络，通常称为H级WFST，这使得它可以 非常有效地执行语音识别[5]。然而，当使用大模型时这样的搜索网络的构成和优化变得不 可行。 联机构成是用来在单个完全构成的WFST的情况下执行语音识别的一个实践选择。联 机构成涉及顺序地应用两个或更多个子WFST的组，在解码期间按需要对它们进行构成。一 个通常方案是在解码之前对HoCoL进行预构成，然后利用语法网络G对此进行联机构成。在 存储器方面联机构成已经显示出是经济的，但是解码显著慢于静态编制WFST[6]。 用于有效WFST解码的一个可选方案是执行假设再评分[3]而不是在搜索期间进行构 成。在此方案中，Viterbi搜索使用H〇C〇Gmi来执行，而另一 WFST网络GWtH仅仅用于对 以联机方式从Viterbi搜索过程生成的假设进行再评分。由于此算法从搜索开始允许所有 的知识源都是可用的，所以对于选择正确的路径和修剪假设这二者而言这是有效的。 现在在许多核的图形处理单元（GPU)的情况下，对于许多计算任务而言商品资源、混 合GPU/CPU计算架构是一个实际的解决方案。对于每个计算子任务而言，通过支持最适合 的架构比通过单独使用任一平台能够取得显著更高的吞吐量。现有工作[7, 8]已经例证了 对于语音识别而言使用GPU处理器的有效性，并且对于有限的词汇任务而言在吞吐量方面 获得了显著的改进[7]。然而，当在识别期间以及还对于其它大规模图形遍历计算而言应 用大声学和语言模型时，关于这些架构的有限的存储器成为一个显著瓶颈。对于这样的计 算的最显著的挑战是处理在现代宽域语音识别系统中使用的极其大的语言模型[1，2, 4]。 这些模型可能包含数百万的唯一词汇条目，数十亿的n-gram上下文，并且可能轻易地要求 20GB或者更多以便存储在存储器中。即使当被显著地修剪时，这些模型也不能适于在GPU 平台上可用的有限的存储器内。为了在大声学模型和语言模型的情况下高效地执行语音识 另IJ，我们已经开发了混合GPU/CPU架构，该架构在GPU架构的计算吞吐量的情况下支持大的 存储器和CPU的局部高速缓冲。
【发明内容】
本发明描述了用于在并行处理器平台上执行大规模图形遍历计算的方法。本发明描述 了用于联机假设再评分的方法，其利用图形处理单元（GPU)结合利用计算设备的中央处理 单元（CPU)。在应用到大词汇连续语音识别任务的一个实施例中描述了本发明。本领域技 术人员将意识到本发明的方法可适用于其它大规模图形遍历计算。 【附图说明】 图1示出了如应用到大规模图形遍历任务的本发明的实现方式结构的示意图。 图2示出了所实施方案的示意图，所实施方案用来从大模型中来子选择条目（即，来自 标志序列的马尔可夫模型的概率）以包括在加权有限状态转换机（WFST)构成期间将应用 的小模型中。所得到的完全构成的WFST搜索图将足够小以在图形处理单元（GPU)上执行 搜索； 图3示出了用来构成适合于在图形处理单元（GPU)上执行搜索的小WFST搜索图的所 实现方案的示意图。 图4示出了包含在WFST搜索图中的状态和相邻弧内的信息的示意图。这些包括 statelD、进入弧列表、外出弧列表以及输入和输出符号。每个弧包含弧特定权重。输入符 号匹配于由"观测模型"产生的概率。输出符号匹配于由对过程进行搜索所产生的标志。例 如，对于语音识别任务而言，这些标志会映射至词； 图5示出了适合于在图形处理单元（GPU)上进行搜索的小WFST搜索图的示例。该示 例示出了应用在用于非常简单任务的语音识别中的搜索图，该搜索图包括以任何次序出现 的三个词（"nice (好的）"，"recognize (识别）"，和 "speech (语音）"）； 图6示出了一个示例语言模型，其中针对当前词、给定的已知词历史列出了语言模型 的概率； 图7示出了适合于当编制用在图形处理单元（GPU)上的基于WFST的搜索图时在构成 期间使用的小语言模型的示例。此语言模型是在语言模型可能性的情况下使用〇. 05的语 言模型阈限〇YM)从图6中的更大的语言模型中子选择而来； 图8示出了对于自动语音识别的任务而言分别使用图6和图7中示出的大语言模 型和小语言模型的部分假设再评分的示例。在再评分之前，短语"识别海滩recognize a beach…"具有最高概率，然而在利用大语言模型进行再评分之后，具有最高概率的部分假 设是"识别语音recognize speech"。 图9示出了例证假设组合和假设修剪的本发明的示意图； 图10示出了在5000个词的词汇大小的情况下应用到大词汇连续语音识别的使用现 有技术方案的准确性和解码速度与本发明的准确性和解码精度的数据比较。Eval. set:WSJ 5Knov' 92 (330个句子）），nL3=9,mL3= 1，n2.3= 3,m2.3= 4,lbw2.3= 7)。 图11示出了在1百万的词汇大小的情况下应用到大词汇连续语音识别的使用现有技 术方案的准确性和解码速度与本发明的准确性和解码精度的数据比较。1M词汇评估结果 (Eval.set:WSJ 5K nov'92+WSJ 20k nov' 93(543 个句子），n2.3=n3.4= 3，m2.3= m3.4 = 24)； 图12示出了在把本发明应用到大词汇连续语音识别的任务的实验中关于处理时间每 计算短语的比率的数据。（说词汇，％4=3，1113.4=24) ; 图13示出了用于如在本发明中所使用的"并行原子合并和排序"方法的输入和输出。 输入包括L个排序列表（Si，…，SJ，而输出是单个排序列表（T); 图14示出了用来在如本发明中所使用的"原子合并和排序"方法中存储部分假设信息 的数据结构； 图15示出了用在如本发明中所使用的"原子合并和排序"方法中的数据结构和函数的 概览。函数"merge-and-sort(〈sourcelist〉，〈targetlist〉）"针对需要合并的所有 L个 排序列表以，…，SJ ; 图16示出了如在本发明中所使用的"并行原子合并和排序"方法的示意图； 图17示出了如在本发明中所使用的转变为"快速和存储器高效查找"架构的语言模型 的示例； 图18示出了在如本发明中所使用的"快速和存储器高效查找"架构的情况下提取概率 (针对给定历史和输出标志）的过程的示意图； 图19示出了通过在如本发明中所使用的"快速和存储器高效查找"架构中选择最适当 的数据结构（HASH-MAP, STATIC ARRAY, BINARY SEARCH TREE, single INTEGER)来产生存储 器高效模型的过程的示意图； 图20示出了在"快速和存储器高效查找"架构中在存储器优化之前外出弧和状态数目 的数据比较，其中是在1百万字词汇大小的情况下被应用到大词汇连续语音识别的任务； 图21示出了存储器足迹与外出弧数目的数据比较以在"快速和存储器高效查找"架构 中使用二进制搜索树，如被应用到达词汇连续语音识别的任务； 图22示出了应用到大词汇连续语音识别任务的现有技术方案（即，KenL M)的速度 (即，实时因子（RTF))和实施"快速和存储器高效查找"架构的速度的数据比较；以及 图23示出了应用到大词汇连续语音识别任务的现有技术方案（g卩，KenLM)的存储器 足迹（兆字节）和实施"快速和存储器高效查找"架构的存储器足迹（兆字节）的数据比 较。 【具体实施方式】 本发明描述了用于在并行处理器平台上执行大规模图形遍历计算的方法。本发明描述 了用于"联机假设再评分（〇n-the-fly hypothesis rescoring)"的方法，其利用图形处理 单元（GPU)结合利用计算设备的一个或多个中央处理单元（CPU)。在应用到大词汇连续语 音识别（LVCSR)任务的一个实施例中描述了本发明。本领域技术人员将意识到本发明的方 法可适用于需要大规模图形遍历计算的其它统计推断任务；示例包括手写识别、基于图像 的手势识别以及图像理解。 在本发明中，我们描述了用于混合GPU/CPU架构的新颖联机假设再评分算法。本发明 的方案的概览如图1中所示。 给定输入信号（项1)和一组统计模型（项15, 16和18)，执行搜索以共同通过最接近 匹配于输入信号的模型找到最佳标志序列（项2)。 在本发明的一个实施例中，即针对大词汇语音识别（LVCSR)任务，输入信号（项1)可 以是从麦克风捕获的数字音频，而输出（项2)最接近匹配于用户表达的内容的词序列。对 于大词汇语音识别（LVCSR)任务，项15会映射到声学模型（例如高斯混合模型或基于深度 神经网络的随机模型），项16是完全构成的基于H级加权有限状态转换机的搜索图（这样 的图的例证示例示出在图5中），以及项18是语言模型（例如，存储在静态查找表或可替 选地基于深度神经网络的统计模型中的语言模型概率）。 在本发明中，以下列方式执行搜索。在初始化（图1，步骤3)时，清除任何暂存工作存 储器（项17和19)，针对搜索网络初始化状态似然率。具体地，将该网络中初始状态（状态 0)的似然率设定为1.0,而所有其它状态的似然率设定为0。作为例证示例，项37标识了 图5中的搜索图的初始状态。 当首先接收到INPUT SIGNAL (输入信号）时，捕获样本（步骤4)，并且从样本计算或提 取一组代表特征（步骤5)。所得的"特征向量"是所捕获信号的大多数信息方法的低维表 示。根据应用任务，每个样本可以计算一个或多个特征向量。 在本发明的一个实施例中，即LVCSR，输入信号（项1)是数字音频。为了此任务，每 10ms可以捕获25ms的音频样本（步骤4和13)，这允许输入信号的重叠。然后，可以针对 每个25ms音频样本计算声学特征。可以用于此任务的标准声学特征包括日志-梅尔滤波 带（Log-Mel filterband)能量和梅尔倒谱系数（Mel-Frequency-Cepstral-Coefficient， MFCC)特征。当图像或音频-视频信号是输入信号时，还可以使用类似的方案。使用CPU或 GPU计算架构可以在任何计算设备上执行样本捕获（步骤4和13)和特征计算（步骤5)。 它们未必需要在与本发明中其它步骤相同的计算设备上执行。 一旦生成了特征向量（步骤5)，于是就在GPU上执行N-最佳搜索（步骤6, 7, 8, 11和 12)，这支持CPU计算合并模型似然率校正（步骤9和10)，使用存储在CPU主存储器中的 大标志序列模型（项18)。在搜索期间，使用统计观测模型（项15)(例如高斯混合模型或 基于深度神经网络）针对每个新特征向量计算第一观测似然率（步骤6)。在步骤7中，使 用公式（1)，基于在步骤6中计算的观测似然率和先前时间步骤中的状态似然率，状态似然 率。新的部分假设g'的状态似然率a [g']计算如下： a [gr ] = a [g] + |3 [e] + ? [e]. (1) 其中，0 [e]是输入符号i[e](使用项15计算的）的观测似然率，w[e]是状态转变概 率（来自项16)，以及a [g]是来自先前时间同步的状态似然率（步骤6)。 在本发明中，引入了模型似然率校正c [e，h [g]]，以使得显著更大的模型能够被联机应 用。 a [gr ] = a [g] + |3 [e] + ? [e]+c[e, h[g]] (2) 模型似然率校正因子c [e，h [g]]是较小模型Puni (o [e])(即在WFST构成期间应用的 语言模型）的模型似然率与在搜索期间应用的大得多的模型P_(〇[e] |h[g])(项18)之间 的差： c[e,h[g]] = log(Puni(o[e]))-log(Pngm(o[e]]h[g])). (3) 其中，h[g]是假设g的输出符号序列。 在搜索过程期间，如果任何部分假设g(h[g])的输出符号序列改变了（步骤8)，则针 对该假设执行再评分。在再评分阶段，首先，计算模型似然率校正因子c [e，h [g]](公式3) (步骤9)。这里，使用存储在CPU存储器中的大模型（项18)来计算P_(〇[e]|h[g])。接 下来，使用模型似然率校正因子更新该部分假设的状态似然率a [g']，如公式2中所描述 的（步骤10)。 在执行再评分之后，基于它们的状态似然率a [g']对部分假设进行排等级，并且出 于考虑去除低于等级阈限的那些（步骤11)。 对此搜索过程（步骤6, 7, 8, 9, 10, 11，12, 13)进行迭代直到遇到最后的样本（步骤 12)。在该点对CPU执行后追踪（步骤14)，这产生最终的1-最佳假设输出（项2)。在 GPU(项17)和CPU(项19)之间的工作存储器中共享后追踪表（对有效的部分假设列表进 行存储的表，以及至部分假设改变的早期框架的后指针）。为了保持此表同步，在处理完每 个样本之后，CPU把后追踪信息从GPU拷贝到CPU (项20)。 在一个实施例中，每20个样本或者在单个最佳输出在将来将不改变的点处在CPU (步 骤14)上执行后追踪，而不是在执行后追踪之前等待遇到最后样本（步骤12)。 在本发明中，通过将n-最佳假设列表赋予每个弧和状态来实施n-最佳Viterbi搜索。 当多个弧满足相同状态时，对n-最佳假设列表进行合并并且Viterbi搜索在所有n-最佳 假设列表中选择n个最小加权假设。在图9中，来自状态s2的f4和来自状态s3的f2基 于它们的总权重被维持在排定次序中。另外，如果假设具有相同的更高次序历史，则将仅维 持较低加权假设。例如，f"l被裁剪，这是因为当这些满足于s5中时此假设具有相同的更 高次序历史"ba"，但是与f" 4相比具有更高的权重。保持n-最佳列表对于达到可比较的 准确度是重要的[7]。如果我们选择如2. 1中所解释的最佳假设，则最终的最佳假设的部分 假设在它达到转变e之前可以被裁剪出，其中转变e具有可以对假设再评分的非e输出。 此场景图示在图9中，其中，假设fl是使用标准解码方案的原始最佳路径，以及f4是再 评分的最佳路径。如果我们仅保持最佳假设，则不能使整个最佳假设f4到达s3和s4之间 的弧，其中可以应用再评分。应当基于词汇的大小和语言模型的量级认真决定n-最佳列表 的最大大小。在给定的词汇大小下，与利用较高量级语言模型构成的WFST相比较，由于弧 至相同目的地状态的严重会聚的原因，利用较低量级的语言模型构成的WFST要求更多的n 来达到可比较的准确度。类似地，具有更多词汇的WFST要求更大的n-最佳列表来最终保 持最佳直到它到达再评分点。 已经依据若干示例性实施例描述了本发明，这些若干示例性实施例意图在所有方面是 说明性的而不是限制性的。特别地，在被应用到大词汇连续语音识别技术的一个实施例中 描述了本发明。本领域技术人员将意识到本发明适用于5个其它类型的大规模图形遍历计 算。因而，在详细实现方式中本发明能够具有很多变体，这些变体可以根据本文所包含的描 述由本领域技术人员导出。将所有这样的变体和其它变体视为处于本发明的范围和精神之 内。 例证示例 为了例证所提出的"联机"再评分方法的有效性，我们针对图6、7和8中的语音识别任 务提出了一组示例模型。 首先，为了准备搜索图（图1，项16)，我们必须从我们的大语言模型（图7)来子选择 条目以便在模型编制期间使用。在此例证示例中，我们子选择了概率大于〇. 05的那些模型 条目。这得到了图6中所示的小语言模型。所得的搜索图是类似于图5中所示的类似结构。 用来从大模型选择最优模型条目以产生小模型的方法和搜索分别示出在图2和图3 中。 图8示出了在使用图6和7中所列的语言模型之前和之后，与六个部分假设有关的概 率。图8示出了 "recognizeabeach…在评分之前具有最高概率。然而，在评分之后，最 合理的，假设"recognizespeech"具有最高概率。在原始模型中词序列（"<s>recognize SpeeCh〈/s>"）的概率相对高，但是这些条目必须要丢弃以便生成小语言模型和搜索图以便 在GPU上执行搜索。 实验评估 我们评估了我们的发明对于使用WSJ任务的大词汇版本的大词汇连续语音识别 (LVCSR)任务的有效性。我们使用了组合评估集，其包括1992年11月的ARPA WSJ 5k评估 集（330个句子）和1993年11月的ARAP WSJ 20k评估集（213个句子，开放词汇）。 在WSJ数据集使用Kaldi工具套件[22]来训练我们的声学模型，其中在LDA转变的情 况下WSJ数据集具有39维MFCC专长。所得到的声学模型包含240K个高斯和2946个表音 状态。
表1 :针对各个语言模型的 WFST的大小。 为了高效并行时间同步图形遍历，对GPU加速平台离线构成和优化WFST，如[5, 6]中 所描述的。表1示出了针对5k和1000k词汇语言模型的最终完全构成的WFST的大小。在 具有两个因特尔Xeon E5-26406核CPU的4-路NVIDIA特斯拉K20GPU服务器中，我们使用 单个GPU来评估所提出的算法。NVIDIA特斯拉K20GPU包含13个具有2496个CUDA核和 5GB⑶DR5存储器的流式多处理器（SMX)。操作系统是Ubuntu 12. 04LTS (64位），并且用 g++4. 6和nvcc5. 0 [23]来编制解码器。在以下部分，我们对下列构成模式进行比较：使用 利用3-gram语言模型（STD-3)构成的WFST的标准方案，使用格束作为lbw2. 3的格生成的 再评分2-gram/3-gram语言模型组合（LATR-2. 3)，以及利用m2. 3线程实施n2. 3-最佳搜索 的所提出的联机再评分2-gram/3-gram组合（0TFR-2. 3)。 准确度性能：在第一评估中，我们试图使用小词汇5K测试集来验证所提出的再评分 方案（0TFR)的准确度。我们使用相同的知识源但是不同的语言模型生成了 3个完全构成 的WFST。对于1-gram和2-gram情况，我们应用了我们提出的联机假设再评分方案。当 nl. 3, n2. 3分别是9, 3时，利用N1，N2进行解码并且使用3-gram语言模型连机再评分获得 了 STD-3情况和LATR-2. 3的相似词误率（WER)。nl. 3大于n2. 3以达到与n2. 3相比较的 可比WER，5. 4%，如3中所解释的。类似地，LATR-2. 3要求更宽的lbw2. 3以在所有解码方 案中对于给定全局束宽度达到可比较的准确度。在大词汇（1M词汇）评估中，当n2. 4, n3.4 为3时，与OTFR-3. 4相比较，OTFR-2. 4示出了 0. 3%的绝对准确度劣化。这揭示了在标准 和格再评分算法的情况下，较低量级语言模型以及较大的词汇要求更多的n以达到可比较 的准确度。 速度性能：在第二评估中，我们使用单核实现方式和GPU加速多核实现方式这两者 来评估解码速度。使用自动调节线性代数软件（Automatically Tuned Linear Algebra Software，ATLAS)来优化基线实现方式以加速声学权重计算过程。图10和图11中的GPU/ CPU评估，在多个CPU核上，与在GPU上的声学模型计算并发地，并行执行了语言模型查找。 这些步骤的分解在图12中示出。图12示出了在没有任何优化的情况下基线GPU标准解码 方案。语言模型查找消耗了绝大部分的解码时间。通过使用OpenMp (b)执行语言模型查找， 查找所需的时间从11. 6X0. 71RTF减小至11. 6X0. 06RTF。最后，通过与在GPU上的声学权 重计算并发地执行语言模型查找，将整个解码时间从〇. 20RTF减小到0. 12RTF。在图10中， 0TRF-3. 4示出了解码速度，当使用GPU和多核CPU，WER为6. 5%时，解码速度比实时快10 倍。与高度优化的单CPU实现方式相比较，快24倍。结果示出了在解码速度方法利用较 高量级语言模型构成的WFST更适合。在图11中，当WER为5. 4%时，0TFR2. 3比0TFR-1. 3 相对快40%。我们从图11中观测到，0TFR-3. 4比0TFR-2. 4相对快。 一种用于在高度并行计算架构上合并排序的列表的方法：原子合并和排序 在Viterbi搜索期间维持n-最佳假设具有许多并行化挑战。最重要的挑战是在再会 聚路径上n-最佳列表的合并。我们领先选择在最小加权假设的情况下维持排序的n-最佳 列表。这简化了将n-最佳假设列表合并到"合并和排序"过程的过程。在CPU上，此过程 能够相当有效地执行。 然而，在GPU上，存在数百的弧，每个都具有n-最佳列表，试图在目的地状态同时写入 到n-最佳列表中。我们开发了一种新方法，用来使用如图16中所示的原子比较和交换操 作在高度并行平台上原子地合并n-最佳列表。GPU提供了有效实施的支持硬件的原子操 作，在此平台上我们支持此能力来实现"原子合并和排序"方法。图13、14、15和16。 用于马尔可夫模型概率的快速且存储器高效查找的架构 上面描述的联机假设再评分方法使得在GPU上大模型（典型地，为标志序列提供概率 的马尔可夫模型）能够被引入到WFST搜索中。当在GPU上在搜索期间遇到标志界限时，使 用在CPU上存储的较大的模型对部分假设（其包括历史statelD，WFST权重和当前标志） 进行再评分。对于快速识别，模型查找的效率（图1中所示，步骤9"计算再评分权重"）是 关键。 为了减小此步骤所需的时间，我们开发了针对快速假设再评分所优化的基于图形的新 颖模型结构。此模型的概览在图17中示出。此模型表示了历史（标志序列）作为图结构 中的状态。历史的概率被储存为自这些状态的外出弧。在此框架内历史和标志都被表示为 整数，并且其中使用的标志ID直接与在GPU上的搜索期间所应用的完全构成的WFST中的 那些匹配。在假设再评分期间，针对特定的〈statelD (h)，tokenID (t) >对计算概率涉及找 到statelD (其是阵列中的直接索引查找），针对兴趣tokenID搜索外出弧，然后返回概率 p (tokenID (t) |stateID(h))和更新的 statelD。 图17示出了在所提出的基于图形的结构中表示的小语言模型。每个节点表示唯一的 历史（唯一的标志序列）。实线弧用标志和其概率来标记并且引向新的历史。虚线弧表示 放弃的弧。它们用放弃权重来标记，并且它们引向具有减小的历史的状态。 图18示出了使用此方案获得特定的〈statelD(h),tokenID(t)>对的概率所需的过程。 为了减小此模型所需的存储器足迹，我们使用新颖的方法，在该新颖方法中，用来存储 外出弧集合的数据结构根据退出状态的弧数目而变化。我们实现了用于四个数据结构的原 型，g卩：HASH-MAP (缺省），STATIC ARRAY, BINARY-SEARCH TREE,或者单个 INTEGER,然而对 于此目的还可以使用其它数据结构。 图19中所描述的方法用来使需要存储数据的存储器足迹最小化。首先，我们加载初 始模型（项9)，其中使用哈希图存储所有的外出弧，以及在该模型中选择第一状态（S)[步 骤]。对于该模型中的每个状态我们于是比较外出弧的数目。 实验评估 在一原型中，我们评估使用如上面所描述的异类数据结构来存储根据非常大语言模 型（1百万字，488百万概率）的概率。首先，我们用单个INTEGER代替仅具有单个条目的 HARSH-MAPS。这将所需的存储器足迹减小了 21. 4%。从28. 64兆字节至22. 50兆字节。 接下来，我们用与总词汇大小匹配的STATIC ARRAY数据结构代替大于外出弧中词汇 90%的HASH-MAPS。在这种情况下，在此阵列内将未在外出弧集中出现的标志标识（利用一 次查找）出来。使用此方案将存储器利用率从22. 50兆字节减少到22. 47兆字节。 最后，我们用BINARY-SEARCH TREE代替具有多于外出弧Tare的HASH-MAPS。通过将 。的值从2改变至10000 (小于总词汇大小的1 % )，我们将存储器利用率减小到10. 5兆 字节，与基于HASH-MAP的原始实现方式相比存储器利用率减小了 63. 4%。针对具体的平台 或者数据集、存储器足迹比对查找速度可以对TaJi行优化。实验结果示出在图20、21、22 和23中。 虽然参考本公开的具体实施例已经详细描述了本公开，但是对于本领域技术人员而言 将显然的是在不偏离实施例的精神和范围的情况下可以在其中进行各种改变和修改。因 而，意图是本公开覆盖落入所附权利要求书及其等同体的范围内的各种修改和变体。
【主权项】
1. 一种用于图形遍历的计算机实现的统计推断方法，包括下面方法步骤： 提供包括中央处理单元（CPU)和图形处理单元（GPU)的计算平台； 对似然率进行初始化； 捕获输入信号的样本； 从所述样本计算样本特征； 针对所述样本特征中的每一个计算观测似然率； 基于所述样本特征中的每一个的观测似然率和先前时间步骤中的似然率来更新似然 率以形成部分假设集； 针对所述部分假设集中的每个部分假设计算似然率校正； 针对所述部分假设集中的每个部分假设更新似然率；以及 对更新的部分假设集执行回追踪并且确定所述更新的部分假设集中的最可能的部分 假设。
【专利摘要】本发明描述了用于在并行处理器平台上执行大规模图形遍历计算的方法。本发明描述了用于联机假设再评分的方法，其利用图形处理单元(GPUs)结合利用计算设备的中央处理单元(CPUs)。在应用到大词汇连续语音识别任务的一个实施例中描述了本发明。
【IPC分类】G06F9/38, G06F9/46
【公开号】CN104903849
【申请号】CN201380046737
【发明人】伊恩·莱恩, 杰克·冲, 金贞硕
【申请人】卡内基·梅隆大学
【公开日】2015年9月9日
【申请日】2013年9月9日
【公告号】EP2893435A1, US20150243285, WO2014040003A1
【专利说明】用于混合GPU/CPU数据处理的方法 相关申请的交叉引用 本申请是一个PCT国际申请，其要求序列号为61/743, 607、题目为Methods for Hybrid GPU/CPU Data Processing的于2012年9月7日提交的美国临时申请的权益，该美国临时 申请的全部内容通过引用合并于本申请中。 技术领域 此发明涉及数据处理的领域。更具体地，此发明涉及用来在并行处理器平台上执行大 规模图形遍历的方法。 【背景技术】 近年来，对于计算机而言具有多核进程和许多核进程已经变得更加普遍，通过以并行 方式横跨不同处理核执行复杂的计算任务显著地增加了可以执行这样的任务的速度。然而 对于一些复杂的计算任务而言，这样的处理器受到它们存储器容量的限制。例如，许多核图 形处理单元（GPU)具有2-8千兆字节（GB)的存储器的限制。对于包括许多数百万计的弧 和模型的图形结构的这样的大规模图形遍历的计算可能在规模上处于GB的100s的量级或 者更大量级的任务而言，此存储器呈现出极限。 因而，存在对通过有效地支持异类并行计算核有效地在并行处理器平台上执行大规模 图形遍历的方法的需要。 需要这样的改进的方法的一个领域是大词汇连续语音识别（large vocabulary continuous speech recognition, LVCSR)领域。作为这样的需要的一个示例，话音用户接 口作为用于下一代智能设备的核心技术正在不断发展。为了确保吸引用户体验，关键的是 用在这些系统内的语音识别引擎是鲁棒的、快速的、具有低延迟并且在系统可能遇到的极 其大的词汇上提供充足的覆盖性。为了获得高的识别准确性，用于诸如广播新闻手稿[1，2] 或者话音搜索[3, 4]之类的任务的现有技术水平的语音识别系统可以在大词汇（>1百万个 词）、大声学模型（数百万的模型参数）以及极其大的语言模型（数十亿的n-gram个条目） 的情况下执行识别。在可以把这些模型应用在离线语音识别任务中时，对于实时语音识别 而言由于在解码期间需要大的计算成本的原因它们是不可实施的。 使用静态编制的加权有限状态转换机（Weighted Finite State Transducer，WFST)网 络，其中，WFST表示隐马尔可夫模型（Hidden Markov Model, HMM)，声学模型H、上下文模 型C、发音词典L、和语言模型G被组成为一个单个网络，通常称为H级WFST，这使得它可以 非常有效地执行语音识别[5]。然而，当使用大模型时这样的搜索网络的构成和优化变得不 可行。 联机构成是用来在单个完全构成的WFST的情况下执行语音识别的一个实践选择。联 机构成涉及顺序地应用两个或更多个子WFST的组，在解码期间按需要对它们进行构成。一 个通常方案是在解码之前对HoCoL进行预构成，然后利用语法网络G对此进行联机构成。在 存储器方面联机构成已经显示出是经济的，但是解码显著慢于静态编制WFST[6]。 用于有效WFST解码的一个可选方案是执行假设再评分[3]而不是在搜索期间进行构 成。在此方案中，Viterbi搜索使用H〇C〇Gmi来执行，而另一 WFST网络GWtH仅仅用于对 以联机方式从Viterbi搜索过程生成的假设进行再评分。由于此算法从搜索开始允许所有 的知识源都是可用的，所以对于选择正确的路径和修剪假设这二者而言这是有效的。 现在在许多核的图形处理单元（GPU)的情况下，对于许多计算任务而言商品资源、混 合GPU/CPU计算架构是一个实际的解决方案。对于每个计算子任务而言，通过支持最适合 的架构比通过单独使用任一平台能够取得显著更高的吞吐量。现有工作[7, 8]已经例证了 对于语音识别而言使用GPU处理器的有效性，并且对于有限的词汇任务而言在吞吐量方面 获得了显著的改进[7]。然而，当在识别期间以及还对于其它大规模图形遍历计算而言应 用大声学和语言模型时，关于这些架构的有限的存储器成为一个显著瓶颈。对于这样的计 算的最显著的挑战是处理在现代宽域语音识别系统中使用的极其大的语言模型[1，2, 4]。 这些模型可能包含数百万的唯一词汇条目，数十亿的n-gram上下文，并且可能轻易地要求 20GB或者更多以便存储在存储器中。即使当被显著地修剪时，这些模型也不能适于在GPU 平台上可用的有限的存储器内。为了在大声学模型和语言模型的情况下高效地执行语音识 另IJ，我们已经开发了混合GPU/CPU架构，该架构在GPU架构的计算吞吐量的情况下支持大的 存储器和CPU的局部高速缓冲。
【发明内容】
本发明描述了用于在并行处理器平台上执行大规模图形遍历计算的方法。本发明描述 了用于联机假设再评分的方法，其利用图形处理单元（GPU)结合利用计算设备的中央处理 单元（CPU)。在应用到大词汇连续语音识别任务的一个实施例中描述了本发明。本领域技 术人员将意识到本发明的方法可适用于其它大规模图形遍历计算。 【附图说明】 图1示出了如应用到大规模图形遍历任务的本发明的实现方式结构的示意图。 图2示出了所实施方案的示意图，所实施方案用来从大模型中来子选择条目（即，来自 标志序列的马尔可夫模型的概率）以包括在加权有限状态转换机（WFST)构成期间将应用 的小模型中。所得到的完全构成的WFST搜索图将足够小以在图形处理单元（GPU)上执行 搜索； 图3示出了用来构成适合于在图形处理单元（GPU)上执行搜索的小WFST搜索图的所 实现方案的示意图。 图4示出了包含在WFST搜索图中的状态和相邻弧内的信息的示意图。这些包括 statelD、进入弧列表、外出弧列表以及输入和输出符号。每个弧包含弧特定权重。输入符 号匹配于由"观测模型"产生的概率。输出符号匹配于由对过程进行搜索所产生的标志。例 如，对于语音识别任务而言，这些标志会映射至词； 图5示出了适合于在图形处理单元（GPU)上进行搜索的小WFST搜索图的示例。该示 例示出了应用在用于非常简单任务的语音识别中的搜索图，该搜索图包括以任何次序出现 的三个词（"nice (好的）"，"recognize (识别）"，和 "speech (语音）"）； 图6示出了一个示例语言模型，其中针对当前词、给定的已知词历史列出了语言模型 的概率； 图7示出了适合于当编制用在图形处理单元（GPU)上的基于WFST的搜索图时在构成 期间使用的小语言模型的示例。此语言模型是在语言模型可能性的情况下使用〇. 05的语 言模型阈限〇YM)从图6中的更大的语言模型中子选择而来； 图8示出了对于自动语音识别的任务而言分别使用图6和图7中示出的大语言模 型和小语言模型的部分假设再评分的示例。在再评分之前，短语"识别海滩recognize a beach…"具有最高概率，然而在利用大语言模型进行再评分之后，具有最高概率的部分假 设是"识别语音recognize speech"。 图9示出了例证假设组合和假设修剪的本发明的示意图； 图10示出了在5000个词的词汇大小的情况下应用到大词汇连续语音识别的使用现 有技术方案的准确性和解码速度与本发明的准确性和解码精度的数据比较。Eval. set:WSJ 5Knov' 92 (330个句子）），nL3=9,mL3= 1，n2.3= 3,m2.3= 4,lbw2.3= 7)。 图11示出了在1百万的词汇大小的情况下应用到大词汇连续语音识别的使用现有技 术方案的准确性和解码速度与本发明的准确性和解码精度的数据比较。1M词汇评估结果 (Eval.set:WSJ 5K nov'92+WSJ 20k nov' 93(543 个句子），n2.3=n3.4= 3，m2.3= m3.4 = 24)； 图12示出了在把本发明应用到大词汇连续语音识别的任务的实验中关于处理时间每 计算短语的比率的数据。（说词汇，％4=3，1113.4=24) ; 图13示出了用于如在本发明中所使用的"并行原子合并和排序"方法的输入和输出。 输入包括L个排序列表（Si，…，SJ，而输出是单个排序列表（T); 图14示出了用来在如本发明中所使用的"原子合并和排序"方法中存储部分假设信息 的数据结构； 图15示出了用在如本发明中所使用的"原子合并和排序"方法中的数据结构和函数的 概览。函数"merge-and-sort(〈sourcelist〉，〈targetlist〉）"针对需要合并的所有 L个 排序列表以，…，SJ ; 图16示出了如在本发明中所使用的"并行原子合并和排序"方法的示意图； 图17示出了如在本发明中所使用的转变为"快速和存储器高效查找"架构的语言模型 的示例； 图18示出了在如本发明中所使用的"快速和存储器高效查找"架构的情况下提取概率 (针对给定历史和输出标志）的过程的示意图； 图19示出了通过在如本发明中所使用的"快速和存储器高效查找"架构中选择最适当 的数据结构（HASH-MAP, STATIC ARRAY, BINARY SEARCH TREE, single INTEGER)来产生存储 器高效模型的过程的示意图； 图20示出了在"快速和存储器高效查找"架构中在存储器优化之前外出弧和状态数目 的数据比较，其中是在1百万字词汇大小的情况下被应用到大词汇连续语音识别的任务； 图21示出了存储器足迹与外出弧数目的数据比较以在"快速和存储器高效查找"架构 中使用二进制搜索树，如被应用到达词汇连续语音识别的任务； 图22示出了应用到大词汇连续语音识别任务的现有技术方案（即，KenL M)的速度 (即，实时因子（RTF))和实施"快速和存储器高效查找"架构的速度的数据比较；以及 图23示出了应用到大词汇连续语音识别任务的现有技术方案（g卩，KenLM)的存储器 足迹（兆字节）和实施"快速和存储器高效查找"架构的存储器足迹（兆字节）的数据比 较。 【具体实施方式】 本发明描述了用于在并行处理器平台上执行大规模图形遍历计算的方法。本发明描述 了用于"联机假设再评分（〇n-the-fly hypothesis rescoring)"的方法，其利用图形处理 单元（GPU)结合利用计算设备的一个或多个中央处理单元（CPU)。在应用到大词汇连续语 音识别（LVCSR)任务的一个实施例中描述了本发明。本领域技术人员将意识到本发明的方 法可适用于需要大规模图形遍历计算的其它统计推断任务；示例包括手写识别、基于图像 的手势识别以及图像理解。 在本发明中，我们描述了用于混合GPU/CPU架构的新颖联机假设再评分算法。本发明 的方案的概览如图1中所示。 给定输入信号（项1)和一组统计模型（项15, 16和18)，执行搜索以共同通过最接近 匹配于输入信号的模型找到最佳标志序列（项2)。 在本发明的一个实施例中，即针对大词汇语音识别（LVCSR)任务，输入信号（项1)可 以是从麦克风捕获的数字音频，而输出（项2)最接近匹配于用户表达的内容的词序列。对 于大词汇语音识别（LVCSR)任务，项15会映射到声学模型（例如高斯混合模型或基于深度 神经网络的随机模型），项16是完全构成的基于H级加权有限状态转换机的搜索图（这样 的图的例证示例示出在图5中），以及项18是语言模型（例如，存储在静态查找表或可替 选地基于深度神经网络的统计模型中的语言模型概率）。 在本发明中，以下列方式执行搜索。在初始化（图1，步骤3)时，清除任何暂存工作存 储器（项17和19)，针对搜索网络初始化状态似然率。具体地，将该网络中初始状态（状态 0)的似然率设定为1.0,而所有其它状态的似然率设定为0。作为例证示例，项37标识了 图5中的搜索图的初始状态。 当首先接收到INPUT SIGNAL (输入信号）时，捕获样本（步骤4)，并且从样本计算或提 取一组代表特征（步骤5)。所得的"特征向量"是所捕获信号的大多数信息方法的低维表 示。根据应用任务，每个样本可以计算一个或多个特征向量。 在本发明的一个实施例中，即LVCSR，输入信号（项1)是数字音频。为了此任务，每 10ms可以捕获25ms的音频样本（步骤4和13)，这允许输入信号的重叠。然后，可以针对 每个25ms音频样本计算声学特征。可以用于此任务的标准声学特征包括日志-梅尔滤波 带（Log-Mel filterband)能量和梅尔倒谱系数（Mel-Frequency-Cepstral-Coefficient， MFCC)特征。当图像或音频-视频信号是输入信号时，还可以使用类似的方案。使用CPU或 GPU计算架构可以在任何计算设备上执行样本捕获（步骤4和13)和特征计算（步骤5)。 它们未必需要在与本发明中其它步骤相同的计算设备上执行。 一旦生成了特征向量（步骤5)，于是就在GPU上执行N-最佳搜索（步骤6, 7, 8, 11和 12)，这支持CPU计算合并模型似然率校正（步骤9和10)，使用存储在CPU主存储器中的 大标志序列模型（项18)。在搜索期间，使用统计观测模型（项15)(例如高斯混合模型或 基于深度神经网络）针对每个新特征向量计算第一观测似然率（步骤6)。在步骤7中，使 用公式（1)，基于在步骤6中计算的观测似然率和先前时间步骤中的状态似然率，状态似然 率。新的部分假设g'的状态似然率a [g']计算如下： a [gr ] = a [g] + |3 [e] + ? [e]. (1) 其中，0 [e]是输入符号i[e](使用项15计算的）的观测似然率，w[e]是状态转变概 率（来自项16)，以及a [g]是来自先前时间同步的状态似然率（步骤6)。 在本发明中，引入了模型似然率校正c [e，h [g]]，以使得显著更大的模型能够被联机应 用。 a [gr ] = a [g] + |3 [e] + ? [e]+c[e, h[g]] (2) 模型似然率校正因子c [e，h [g]]是较小模型Puni (o [e])(即在WFST构成期间应用的 语言模型）的模型似然率与在搜索期间应用的大得多的模型P_(〇[e] |h[g])(项18)之间 的差： c[e,h[g]] = log(Puni(o[e]))-log(Pngm(o[e]]h[g])). (3) 其中，h[g]是假设g的输出符号序列。 在搜索过程期间，如果任何部分假设g(h[g])的输出符号序列改变了（步骤8)，则针 对该假设执行再评分。在再评分阶段，首先，计算模型似然率校正因子c [e，h [g]](公式3) (步骤9)。这里，使用存储在CPU存储器中的大模型（项18)来计算P_(〇[e]|h[g])。接 下来，使用模型似然率校正因子更新该部分假设的状态似然率a [g']，如公式2中所描述 的（步骤10)。 在执行再评分之后，基于它们的状态似然率a [g']对部分假设进行排等级，并且出 于考虑去除低于等级阈限的那些（步骤11)。 对此搜索过程（步骤6, 7, 8, 9, 10, 11，12, 13)进行迭代直到遇到最后的样本（步骤 12)。在该点对CPU执行后追踪（步骤14)，这产生最终的1-最佳假设输出（项2)。在 GPU(项17)和CPU(项19)之间的工作存储器中共享后追踪表（对有效的部分假设列表进 行存储的表，以及至部分假设改变的早期框架的后指针）。为了保持此表同步，在处理完每 个样本之后，CPU把后追踪信息从GPU拷贝到CPU (项20)。 在一个实施例中，每20个样本或者在单个最佳输出在将来将不改变的点处在CPU (步 骤14)上执行后追踪，而不是在执行后追踪之前等待遇到最后样本（步骤12)。 在本发明中，通过将n-最佳假设列表赋予每个弧和状态来实施n-最佳Viterbi搜索。 当多个弧满足相同状态时，对n-最佳假设列表进行合并并且Viterbi搜索在所有n-最佳 假设列表中选择n个最小加权假设。在图9中，来自状态s2的f4和来自状态s3的f2基 于它们的总权重被维持在排定次序中。另外，如果假设具有相同的更高次序历史，则将仅维 持较低加权假设。例如，f"l被裁剪，这是因为当这些满足于s5中时此假设具有相同的更 高次序历史"ba"，但是与f" 4相比具有更高的权重。保持n-最佳列表对于达到可比较的 准确度是重要的[7]。如果我们选择如2. 1中所解释的最佳假设，则最终的最佳假设的部分 假设在它达到转变e之前可以被裁剪出，其中转变e具有可以对假设再评分的非e输出。 此场景图示在图9中，其中，假设fl是使用标准解码方案的原始最佳路径，以及f4是再 评分的最佳路径。如果我们仅保持最佳假设，则不能使整个最佳假设f4到达s3和s4之间 的弧，其中可以应用再评分。应当基于词汇的大小和语言模型的量级认真决定n-最佳列表 的最大大小。在给定的词汇大小下，与利用较高量级语言模型构成的WFST相比较，由于弧 至相同目的地状态的严重会聚的原因，利用较低量级的语言模型构成的WFST要求更多的n 来达到可比较的准确度。类似地，具有更多词汇的WFST要求更大的n-最佳列表来最终保 持最佳直到它到达再评分点。 已经依据若干示例性实施例描述了本发明，这些若干示例性实施例意图在所有方面是 说明性的而不是限制性的。特别地，在被应用到大词汇连续语音识别技术的一个实施例中 描述了本发明。本领域技术人员将意识到本发明适用于5个其它类型的大规模图形遍历计 算。因而，在详细实现方式中本发明能够具有很多变体，这些变体可以根据本文所包含的描 述由本领域技术人员导出。将所有这样的变体和其它变体视为处于本发明的范围和精神之 内。 例证示例 为了例证所提出的"联机"再评分方法的有效性，我们针对图6、7和8中的语音识别任 务提出了一组示例模型。 首先，为了准备搜索图（图1，项16)，我们必须从我们的大语言模型（图7)来子选择 条目以便在模型编制期间使用。在此例证示例中，我们子选择了概率大于〇. 05的那些模型 条目。这得到了图6中所示的小语言模型。所得的搜索图是类似于图5中所示的类似结构。 用来从大模型选择最优模型条目以产生小模型的方法和搜索分别示出在图2和图3 中。 图8示出了在使用图6和7中所列的语言模型之前和之后，与六个部分假设有关的概 率。图8示出了 "recognizeabeach…在评分之前具有最高概率。然而，在评分之后，最 合理的，假设"recognizespeech"具有最高概率。在原始模型中词序列（"<s>recognize SpeeCh〈/s>"）的概率相对高，但是这些条目必须要丢弃以便生成小语言模型和搜索图以便 在GPU上执行搜索。 实验评估 我们评估了我们的发明对于使用WSJ任务的大词汇版本的大词汇连续语音识别 (LVCSR)任务的有效性。我们使用了组合评估集，其包括1992年11月的ARPA WSJ 5k评估 集（330个句子）和1993年11月的ARAP WSJ 20k评估集（213个句子，开放词汇）。 在WSJ数据集使用Kaldi工具套件[22]来训练我们的声学模型，其中在LDA转变的情 况下WSJ数据集具有39维MFCC专长。所得到的声学模型包含240K个高斯和2946个表音 状态。
表1 :针对各个语言模型的 WFST的大小。 为了高效并行时间同步图形遍历，对GPU加速平台离线构成和优化WFST，如[5, 6]中 所描述的。表1示出了针对5k和1000k词汇语言模型的最终完全构成的WFST的大小。在 具有两个因特尔Xeon E5-26406核CPU的4-路NVIDIA特斯拉K20GPU服务器中，我们使用 单个GPU来评估所提出的算法。NVIDIA特斯拉K20GPU包含13个具有2496个CUDA核和 5GB⑶DR5存储器的流式多处理器（SMX)。操作系统是Ubuntu 12. 04LTS (64位），并且用 g++4. 6和nvcc5. 0 [23]来编制解码器。在以下部分，我们对下列构成模式进行比较：使用 利用3-gram语言模型（STD-3)构成的WFST的标准方案，使用格束作为lbw2. 3的格生成的 再评分2-gram/3-gram语言模型组合（LATR-2. 3)，以及利用m2. 3线程实施n2. 3-最佳搜索 的所提出的联机再评分2-gram/3-gram组合（0TFR-2. 3)。 准确度性能：在第一评估中，我们试图使用小词汇5K测试集来验证所提出的再评分 方案（0TFR)的准确度。我们使用相同的知识源但是不同的语言模型生成了 3个完全构成 的WFST。对于1-gram和2-gram情况，我们应用了我们提出的联机假设再评分方案。当 nl. 3, n2. 3分别是9, 3时，利用N1，N2进行解码并且使用3-gram语言模型连机再评分获得 了 STD-3情况和LATR-2. 3的相似词误率（WER)。nl. 3大于n2. 3以达到与n2. 3相比较的 可比WER，5. 4%，如3中所解释的。类似地，LATR-2. 3要求更宽的lbw2. 3以在所有解码方 案中对于给定全局束宽度达到可比较的准确度。在大词汇（1M词汇）评估中，当n2. 4, n3.4 为3时，与OTFR-3. 4相比较，OTFR-2. 4示出了 0. 3%的绝对准确度劣化。这揭示了在标准 和格再评分算法的情况下，较低量级语言模型以及较大的词汇要求更多的n以达到可比较 的准确度。 速度性能：在第二评估中，我们使用单核实现方式和GPU加速多核实现方式这两者 来评估解码速度。使用自动调节线性代数软件（Automatically Tuned Linear Algebra Software，ATLAS)来优化基线实现方式以加速声学权重计算过程。图10和图11中的GPU/ CPU评估，在多个CPU核上，与在GPU上的声学模型计算并发地，并行执行了语言模型查找。 这些步骤的分解在图12中示出。图12示出了在没有任何优化的情况下基线GPU标准解码 方案。语言模型查找消耗了绝大部分的解码时间。通过使用OpenMp (b)执行语言模型查找， 查找所需的时间从11. 6X0. 71RTF减小至11. 6X0. 06RTF。最后，通过与在GPU上的声学权 重计算并发地执行语言模型查找，将整个解码时间从〇. 20RTF减小到0. 12RTF。在图10中， 0TRF-3. 4示出了解码速度，当使用GPU和多核CPU，WER为6. 5%时，解码速度比实时快10 倍。与高度优化的单CPU实现方式相比较，快24倍。结果示出了在解码速度方法利用较 高量级语言模型构成的WFST更适合。在图11中，当WER为5. 4%时，0TFR2. 3比0TFR-1. 3 相对快40%。我们从图11中观测到，0TFR-3. 4比0TFR-2. 4相对快。 一种用于在高度并行计算架构上合并排序的列表的方法：原子合并和排序 在Viterbi搜索期间维持n-最佳假设具有许多并行化挑战。最重要的挑战是在再会 聚路径上n-最佳列表的合并。我们领先选择在最小加权假设的情况下维持排序的n-最佳 列表。这简化了将n-最佳假设列表合并到"合并和排序"过程的过程。在CPU上，此过程 能够相当有效地执行。 然而，在GPU上，存在数百的弧，每个都具有n-最佳列表，试图在目的地状态同时写入 到n-最佳列表中。我们开发了一种新方法，用来使用如图16中所示的原子比较和交换操 作在高度并行平台上原子地合并n-最佳列表。GPU提供了有效实施的支持硬件的原子操 作，在此平台上我们支持此能力来实现"原子合并和排序"方法。图13、14、15和16。 用于马尔可夫模型概率的快速且存储器高效查找的架构 上面描述的联机假设再评分方法使得在GPU上大模型（典型地，为标志序列提供概率 的马尔可夫模型）能够被引入到WFST搜索中。当在GPU上在搜索期间遇到标志界限时，使 用在CPU上存储的较大的模型对部分假设（其包括历史statelD，WFST权重和当前标志） 进行再评分。对于快速识别，模型查找的效率（图1中所示，步骤9"计算再评分权重"）是 关键。 为了减小此步骤所需的时间，我们开发了针对快速假设再评分所优化的基于图形的新 颖模型结构。此模型的概览在图17中示出。此模型表示了历史（标志序列）作为图结构 中的状态。历史的概率被储存为自这些状态的外出弧。在此框架内历史和标志都被表示为 整数，并且其中使用的标志ID直接与在GPU上的搜索期间所应用的完全构成的WFST中的 那些匹配。在假设再评分期间，针对特定的〈statelD (h)，tokenID (t) >对计算概率涉及找 到statelD (其是阵列中的直接索引查找），针对兴趣tokenID搜索外出弧，然后返回概率 p (tokenID (t) |stateID(h))和更新的 statelD。 图17示出了在所提出的基于图形的结构中表示的小语言模型。每个节点表示唯一的 历史（唯一的标志序列）。实线弧用标志和其概率来标记并且引向新的历史。虚线弧表示 放弃的弧。它们用放弃权重来标记，并且它们引向具有减小的历史的状态。 图18示出了使用此方案获得特定的〈statelD(h),tokenID(t)>对的概率所需的过程。 为了减小此模型所需的存储器足迹，我们使用新颖的方法，在该新颖方法中，用来存储 外出弧集合的数据结构根据退出状态的弧数目而变化。我们实现了用于四个数据结构的原 型，g卩：HASH-MAP (缺省），STATIC ARRAY, BINARY-SEARCH TREE,或者单个 INTEGER,然而对 于此目的还可以使用其它数据结构。 图19中所描述的方法用来使需要存储数据的存储器足迹最小化。首先，我们加载初 始模型（项9)，其中使用哈希图存储所有的外出弧，以及在该模型中选择第一状态（S)[步 骤]。对于该模型中的每个状态我们于是比较外出弧的数目。 实验评估 在一原型中，我们评估使用如上面所描述的异类数据结构来存储根据非常大语言模 型（1百万字，488百万概率）的概率。首先，我们用单个INTEGER代替仅具有单个条目的 HARSH-MAPS。这将所需的存储器足迹减小了 21. 4%。从28. 64兆字节至22. 50兆字节。 接下来，我们用与总词汇大小匹配的STATIC ARRAY数据结构代替大于外出弧中词汇 90%的HASH-MAPS。在这种情况下，在此阵列内将未在外出弧集中出现的标志标识（利用一 次查找）出来。使用此方案将存储器利用率从22. 50兆字节减少到22. 47兆字节。 最后，我们用BINARY-SEARCH TREE代替具有多于外出弧Tare的HASH-MAPS。通过将 。的值从2改变至10000 (小于总词汇大小的1 % )，我们将存储器利用率减小到10. 5兆 字节，与基于HASH-MAP的原始实现方式相比存储器利用率减小了 63. 4%。针对具体的平台 或者数据集、存储器足迹比对查找速度可以对TaJi行优化。实验结果示出在图20、21、22 和23中。 虽然参考本公开的具体实施例已经详细描述了本公开，但是对于本领域技术人员而言 将显然的是在不偏离实施例的精神和范围的情况下可以在其中进行各种改变和修改。因 而，意图是本公开覆盖落入所附权利要求书及其等同体的范围内的各种修改和变体。
【主权项】
1. 一种用于图形遍历的计算机实现的统计推断方法，包括下面方法步骤： 提供包括中央处理单元（CPU)和图形处理单元（GPU)的计算平台； 对似然率进行初始化； 捕获输入信号的样本； 从所述样本计算样本特征； 针对所述样本特征中的每一个计算观测似然率； 基于所述样本特征中的每一个的观测似然率和先前时间步骤中的似然率来更新似然 率以形成部分假设集； 针对所述部分假设集中的每个部分假设计算似然率校正； 针对所述部分假设集中的每个部分假设更新似然率；以及 对更新的部分假设集执行回追踪并且确定所述更新的部分假设集中的最可能的部分 假设。
【专利摘要】本发明描述了用于在并行处理器平台上执行大规模图形遍历计算的方法。本发明描述了用于联机假设再评分的方法，其利用图形处理单元(GPUs)结合利用计算设备的中央处理单元(CPUs)。在应用到大词汇连续语音识别任务的一个实施例中描述了本发明。
【IPC分类】G06F9/38, G06F9/46
【公开号】CN104903849
【申请号】CN201380046737
【发明人】伊恩·莱恩, 杰克·冲, 金贞硕
【申请人】卡内基·梅隆大学
【公开日】2015年9月9日
【申请日】2013年9月9日
【公告号】EP2893435A1, US20150243285, WO2014040003A1
最新回复(0)