如何讓語言模型充分利用GPU：針對大規模並行設備的N-gram

愛丁堡大學的論文《N-gram language models for massively parallel devices》介紹了用於大規模並行設備的 N-gram 語言模型。機器之心技術分析師對該論文進行了解讀。

論文：https://aclweb.org/anthology/P/P16/P16-1183.pdf

引言

這篇論文談的是用於大規模並行設備（GPU）的 N-gram 語言模型，這是最早為 GPU 設計的語言模型（至少在這篇論文發表時是這樣）。N-gram 語言模型的查詢速度存在計算瓶頸，而且儘管 GPU 擅於計算，但在 GPU 上卻並不好實現，因為還不存在針對 GPU 的已有的數據結構類型。這個問題導致我們無法完全發揮 GPU 的效力。

1 背景

也許有的讀者並不真正了解 N-gram 模型是什麼，因此首先我會先簡要介紹一些基本概念：

N-gram 語言模型

參閱：https://lagunita.stanford.edu/c4x/Engineering/CS-224N/asset/slp4.pdf

為詞序列分配概率的模型被稱為語言模型（LM）。N-gram 是目前最簡單的語言模型。N-gram 是 N 個詞構成的序列：2-gram（bi-gram）是兩個詞構成的詞序列，比如「please turn」；3-gram（tri-gram）是三個詞構成的詞序列，比如「please turn your」。

我們需要關注的有兩點（至少這篇論文是這麼說的）：

• 給定之前的詞，如何使用 N-gram 模型來估計 N-gram 中最後一個詞的概率？
• 如何將概率分配給整個序列？

（注意：我們通常會丟棄「模型」這個詞，這樣 N-gram 既可表示詞序列本身，也可表示為其分配概率的預測模型。這或許會產生一點術語歧義。）

對數概率

為什麼為語言模型使用對數概率？因為（按照定義）概率是小於或等於 1 的，所以相乘的概率越多，所得到的積就會越小。乘上足夠多的 N-gram 就會導致數值下溢。通過使用對數概率而非原始概率，我們能得到不會那麼小的值。在對數空間中相加等效於在線性空間中相乘，這樣我們就可以通過加法來將對數概率結合到一起。在對數空間中執行所有計算和存儲是很方便的，如果我們想查看結果，只需要將結果轉換到普通概率空間既可，即求該對數概率的指數：p1 × p2 × p3 × p4 = exp(log p1 +log p2 +log p3 +log p4)

2 這篇論文的動機

因為 N-gram 語言模型的查詢速度在 CPU 上存在計算瓶頸（Heafield (2013) 和 Green et al. (2014) 在靜態機器翻譯任務上展現了這一問題，而且眾所周知神經網路需要大量計算），因此人們轉而使用 GPU。但是，GPU 採用了特殊的結構設計，在很多方面都不同於 CPU，使用已有的數據結構和演算法很難最大化對這一資源的利用。

這篇論文提出了首個專門為這種硬體（GPU）設計的語言模型，它使用了 trie，其中每個節點都由 B-tree 表示，這能最大化數據並行以及最小化內存佔用和延遲。

3 GPU 計算模型

比起 CPU，GPU 有很多更小的核，它們各自都實現一個線程，而且其中很多都屬於下圖所示的一個器件。本質上，在 GPU 上是並行的函數或核執行計算，並會定義一個將被應用的數據元素網格（如下所示）。每個計算都由一個並行線程的模塊處理。每個任務都會被分配一整個包（warp）——至少 32 個核。因此，如果這個任務不需要所有這些核，那麼剩下的核就會閑置。GPU 編程的更多信息可參考：https://people.maths.ox.ac.uk/gilesm/old/pp10/lec2_2x2.pdf

因為運行需要內存存取，所以我們希望使用較小的數據結構。當一個線程向全局內存請求一個位元組時，數據會與很多周圍的位元組一起被複制到共享內存，這樣我們就可以使用聚合的讀取訪問內存了。避免分支指令能充分利用計算資源以及防止線程閑置。從圖中可以看到，需要較長時間才能訪問全局 GPU 內存，所以我們需要最小化全局內存訪問（Bogoychev and Lopez, 2016）。

注意：這裡給出一個例子幫助你理解我們應該避免分支指令的原因：如果 a=0，那麼 b=1；否則 b=2。我們首先必須評估其條件，然後處理接下來的指令。只有滿足條件的線程才會運行，其它線程則會閑置。這能部分地解釋我們在並行架構中需要分支的原因。

4 簡單介紹 Backoff 語言模型

設有一個句子 w1 w2 w3 w4 … wi，其中 wi 是指第 i 個詞。N-gram 模型將 w 的概率定義為：

Chen And Goodman (1999) 根據 N-gram 概率定義了 Backoff 語言模型：

這針對的是從 1 到 N 的所有 N，使用了兩個參數：N-gram 參數

和

我們可以簡單地將它們視為數值參數以簡化我們的闡述，所以我們有：

我們可以用 (a) 和 (b) 得到等式 (2)。因此，如果可以輕鬆得到 p_hat 和 β，我們就可以通過等式 (2) 得到 n-gram 概率。Bogoychev 和 Lopez 基於這種計算設計了一種語言模型數據結構。這篇論文中設計的數據結構可以有效訪問這些參數。

5 大規模並行語言模型（這篇論文的成果）

Trie 語言模型

Bogoychev 使用了 Heafield (2011) 設計的 trie 數據的變體來滿足上述 Backoff 語言模型的計算需求。（其實驗證明了這一假設：trie 更慢的查詢速度可以通過 GPU 的吞吐量得到補償。我們後面會談到這一實驗。）下面展示了一些常見數據結構的細節，以滿足 Backoff 和在 GPU 上實現的需求。他選擇了 Trie 作為基本結構：

注意：本文假設讀者對 Backoff 語言模型已有一定了解；這是描述性的，而不是教程。要真正理解究竟發生了什麼，你也許應該嘗試下面的練習：假設你有 5-gram「I like pie with rhubarb」，你想要根據上面的 (2) 式計算 P(rhubarb | I like pie with)。

1. 如果 p_hat(rhubarb | I like pie with) > 0，你會使用哪幾項？
2. 如果 p_hat(rhubarb | I like pie with) = 0 但 p_hat(rhubarb | like pie with) > 0，你會使用哪幾項？
3. 如果 p_hat(rhubarb | like pie with) = 0 但 p_hat(rhubarb | pie with) > 0，你會使用哪幾項？

……這應當有助於使該遞歸過程清晰。

我們將 n-gram 鍵值存儲在一個有序數組 A 中，並將它們的相關值

存儲在同等長度的數組 V 中。

我想用一個真實案例來解釋這篇論文中的逆 trie 模型的過程、K-ary 搜索和 B-tree。

逆 trie（基於Bogoychev and Lopez 中的圖像）

這裡用綠色展示了 N-gram 「I like basketball」的路徑。對 N-gram 「they like basketball」的查詢能遍歷同一路徑，但最後的節點中沒有「they」，因此它會為鍵值 b

返回鍵值對，並且由於 backoff 參數 β(they like)，只會返回根一次。對於更大的 n，只需迭代式地檢索計算式 (2) 所需的參數。

注意：原論文這一段第五行有一個錯誤，描述了當 n>1 時的查詢過程：

這與我們剛剛描述的一樣，因為這裡沒有任何與 K 有關的描述，作者也確認了這個錯誤。

K-ary 搜索和 B-tree

上面描述的 trie 搜索演算法效率不高，需要太多次搜索。K-ary 搜索的速度比二元搜索更快，但需要從全局內存讀取數據，因為完整的 trie 必須駐留於全局內存中以適應大型語言模型。Bogoychev 和 Lopez 使用 B-tree（Bayer and McCreight）來替換連續內存位置中的 K 個元素，使得它們可以從全局內存被複制到共享內存，以便合併讀取。

所以其完整的數據結構是 trie，其中根節點之外每個節點都是一個 B-tree。根節點包含所有可能的鍵（unigram），這可以由在沒有任何搜索的恆定時間內索引的數組表示。下圖準確地展示了這一數據結構（來自 Bogoychev 的論文）：

在這幅圖中，第一行是 unigram。第二行是 2-gram，第三行是 3-gram。（注意：小圖 1 是來自那一段根的 4-ary。）

B-tree 節點包含 K 個子節點相對地址（非全局地址以節省空間）、鍵 w 和關聯值

6 實驗和結論

這篇論文設計了七個實驗並將該模型與另一個已有的語言模型 KenLM（Heafield, 2011）進行了比較，考慮了實踐中的資金成本和性能。

• GPU：英偉達 Geforce GTX, 於 2015 年第一季度發布（1000 美元）
• CPU：單線程的 CPU 測試，英特爾 Quad Core i7 4720HQ，於 2015 年第一季度發布（280 美元）
• 多線程 CPU：兩個英特爾 Xeon E5-2680 CPU，能提供 16 核和 32 線程（3500 美元）

查詢速度

上表通過修改 KenLM 的線程數而對這兩個模型進行了比較。當 KenLM 的表現優於 gLM 時，CPU 的成本也更高（3500 比 1000），所以從經濟角度看，gLM 在這一實驗中更優。

B-tree 節點大小的影響

隨著節點增大，吞吐量（每秒的 n-gram 查詢）也會增大，直到達到 33 的節點大小，接著吞吐量陡然下降。

使 GPU 飽和

這一實驗比較了吞吐量隨批大小的變化情況，以觀察我們何時能使 GPU 飽和，以充分利用 GPU。

模型大小和 N-gram 順序對性能的影響

第四個實驗展示了不同語言模型大小下的性能（吞吐量）。

第五個實驗展示了不同 n-gram 順序下的性能（吞吐量）。

此外，這篇論文還通過改變內存類型驗證了 gLM 的計算限制，但語言模型通常受 CPU 上的內存限制。

總結和個人看法

這篇論文為我們展現了一個新領域：探索 GPU 上的基本數據結構。因為 GPU 和 CPU 之間的差異，高效利用 GPU 是非常重要的。這篇論文認為，gLM 模型並沒有在真實的機器翻譯系統上實現。因為 NMT 通常運行在 GPU 上，所以這可能是一個提升 NMT 的好方法。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！