CUDA程式設計——Mars：MapReduce on GPU

1 GPU加速機器學習

　　GPU是一種SIMT（單指令多線程）體系結構，即多個線程執行同一個指令，而每個線程操作的資料不同。這種結構令GPU天生具有大規模計算能力。GPU出色的浮點計算性能特别提高了深度學習兩大關鍵活動：分類和卷積的性能，同時又達到所需的精準度。深度學習需要很高的内在并行度、大量的浮點計算能力以及矩陣預算，而GPU可以提供這些能力，并且在相同的精度下，相對傳統CPU的方式，擁有更快的處理速度、更少的伺服器投入和更低的功耗。NVIDIA介紹，TITAN X在工業标準模型AlexNet 上，花了不到三天的時間、使用 120萬個 ImageNet 圖像資料集去訓練模型，而使用16核心的 CPU 得花上四十多天。更震撼的是使用 NVIDIA推出的DIGITS DevBox [1]來訓練 AlexNet 則隻要13個小時就能完成。

　　然而，這種龐大的并行能力需要付出代價：必須編寫專門的軟體才能利用這樣的優勢，GPU程式設計相對于CPU程式設計需要更多程式員的付出。目前GPGPU的程式模型仍不成熟，将資料劃分為不同粒度，送到GPU的每個流處理器（SP）運算，這些工作仍需要程式員手工完成。此外，由于GPU不具有分支預測等複雜的流程控制單元，對于高度分支的程式執行效率差。GPU核心是虛拟化的，線程排程由硬體完成，無法動态排程。程式員需要避免寫有高度分支的程式。GPU由于沒有足夠大的cache，讀寫主存導緻latency。程式員需要利用大量線程隐藏latency。另外不同廠商的GPU硬體架構不同，使用者可以獲得的細節有限。這些都導緻在GPU上設計通用的計算架構，仍然具有很大挑戰。

2 Mars

　　近來，一些GPGPU 程式設計架構被提出，如NVIDIA的CUDA和AMD的Brook+,這些架構大大提升了GPU可程式設計性。Wenbin Fang等認為這些程式設計語言的接口依賴與特定廠商，并且他們的硬體抽象不适合于開發複雜應用。是以提出了一個易于在GPU上程式設計的MapReduce架構[2]。Mars架構可以用在分布式環境中，如hadoop。Mars可以應用在多核CPUs，NVIDIA GPUs，AMD GPUs或者聯合一個多核CPU和一個GPU的單機上。Mars解決了三個技術挑戰：首先MapReduce根據資料分割任務，利用GPU執行大量并行線程時，負載不平衡是一個固有問題，特别是GPU的線程由硬體管理。其次，GPU缺乏有效的全局同步機制，Map或Reduce任務中的線程在輸出緩存上常常發生寫入沖突。盡管GPU現在已經支援原子操作，原子操作的缺陷卻會傷害大量GPU線程的可擴充性[3]。Mars提出一個lock-free排程方法來減少GPU線程同步帶來瓶頸。第三，MapReduce應用通常是資料密集，且結果的規模也是依資料而變。這兩個特性導緻GPU程式設計有以下需求：1）足夠多線程隐藏記憶體延遲，充分利用裝置記憶體的高帶寬。2）預先在裝置記憶體上配置設定輸出緩沖區，利用DMA減少記憶體存取時間。Mars中，有大量thread在GPU上并行運作，每個thread一次運算一個key/value pair，在Map階段，架構平均配置設定key/value pairs到每個thread，Reduce階段，Mars使用一種簡單但高效的傾斜算法重新配置設定資料到Reduce任務，達到負載均衡。為了避免多線程寫入沖突，Mars采用了一種lock-free政策保證并行程式的正确，僅付出很小的同步代價。

2.1 Mars 工作流程

　　Mars的工作流程如下圖。

CUDA程式設計——Mars：MapReduce on GPU

　　以Mars的word count為例，Mars讀取檔案，将檔案切分為ceil（2048）大小的一塊，這裡的ceil（2048）是指≥2048字元長度的連續字元，即塊以非空字元開始，結尾是偏移≥2048字元長度的第一個空字元的前一位。每一塊配置設定給一個GPU thread，256個thread組成一個block，多個block組成一個grid，一次GPU核心函數調用執行一個grid。從排程和運作方式看，GPU上block概念和CPU上的程序很相似，一個程序占用一個CPU核運作，多個程序輪轉排程；一個block占用一個GPU SM運作，多個block輪轉排程。從這個角度看，GPU的SM很像GPU核。

2.2 MapSplit

　　假設原始資料放在磁盤上，Mars利用CPU程式從磁盤讀取資料，将輸入轉換為key/value pairs儲存在主存中，之後傳輸到GPU裝置記憶體。MapSplit階段，将輸入配置設定給GPU thread，配置設定的方式是一種分段式掃描的方式。

　　分段掃描，就是對資料集進行有規律的掃描操作（最大值，最小值，總和等），并附帶一個額外的數組，将原來的數組分成不同大小的塊。每塊配置設定一個或多個線程進行計算。由于附加的數組可以在運作時進行更新，是以如果分段掃描能保持在一個單獨的線程塊内執行，就可以減少調用多核心的需要。否則，則需要采用一種更簡單的解決辦法。分段式掃描能夠在多數情況下正常工作，并且線程和線程塊的數量能随着并行度增加或縮減靈活改變。

2.3 MapCount

　　MapCount用于計算Map輸出的中間結果的大小，以便預先配置設定GPU記憶體，計算方式是通過求字首和（Prefix Sum）獲得輸出大小和每個線程寫入資料的位置。字首和也叫累積和，一組數序列 x0,x1,x2,... 的字首和還是一組數序列 y0,y1,y2,... ，計算方法如下：

　　y0=x0　　y1=x0+x1　　y2=x0+x1+x2　　...　　

例如，自然數的字首和是三角形數：

input numbers	1	2	3	4	5	6	…
prefix sums	1	3	6	10	15	21	…

2.4 Map&Group

　　通過字首和，标記每個線程的輸出的位置，提前配置設定GPU記憶體。最後GPU線程執行使用者的Map函數，接着Map以lock-free方式獲得每個線程輸出結果的大小和寫入位置，輸出結果。

在Group階段，按照key排序分組和hash分組都是可行的，Mars采用了排序分組，因為有些應用需要把輸出排序，并且hash分組也必須為每個hash bucket進行排序。

2.5 Reduce

　　ReduceCount和MapCount相似，不再贅述。

　　Reduce階段，把key相同的中間結果配置設定給一個GPU thread，由于不同key的記錄數量不同，這可能造成線程負載不均衡。Mars采用了一種傾斜處理政策減緩負載不均衡問題，可以跨reduce workers配置設定負載，即使使用者定義的Reduce操作之間是關聯的。這個政策就是疊代運作兩步：1）把資料分為M大小相同的塊。2）對每個塊執行Reduction，M個thread執行Reduce函數，計算單個塊内的一組記錄。注意：在每次疊代中，Reduction隻在具有相同keys中間結果上執行。

接着Reduce以lock-free方式獲得每個線程輸出結果的大小和寫入位置。最後把所有Reduce workers輸出到一個緩存區域。

2.6 Lock-free方案

　　在GPU運算前，Mars已經在裝置上以array格式配置設定好記憶體。然而，Map和Reduce輸出的大小都是未知的，多線程在一個共享的array上寫結果常常發生沖突。為了解決這兩個問題，Mars提出了Lock-free方案。每個線程運作MapCount都會輸出三個計數，如：中間結果的個數，中間結果keys的大小，和中間結果values的大小。根據中間結果key的大小，Mars計算prefix sum[6]，産生寫入位址，該位址是一個輸出array開始位置加偏移量。字首和（prefix sum）計算在并行計算中很有用,因為在處理負載平衡問題時,經常需要将若幹段資料重新平分,計算字首和通常是一種有效的将資料平分的方法。

　　通過這些prefix sum，可以知道中間結果的準确大小，這樣可以預先在裝置上配置設定記憶體儲存中間結果。由于每個Map有确定的和不重疊的結果緩存區，就可以避免寫入沖突。Lock-free非常适合于大量線程并行運作的程式。

3 什麼是lock-free?

　　衆所周知，鎖在解決并行過程中臨界資源通路問題的同時可能會引入諸多新的問題，比如死鎖(dead lock)，另外鎖的申請/釋放對性能也有不小的影響，當然最大的問題還在于使用鎖的代碼子產品通常難以進行組合。

Lock-free的目标就是要消除鎖對程式設計帶來的不利影響。那麼lock-free是什麼？一個lock-free的解釋是一個“鎖無關”的程式能夠確定執行它的所有線程中，如果某一個線程被挂起，那麼其絕對不會阻止其他線程繼續運作（Non-Blocking）[2]。

　　換句話說，各個線程不會互相阻塞，那麼你的程式才能成為lock-free的。像我們平常用的互斥鎖，當有線程獲得鎖，其他線程就被阻塞掉了，這裡的問題就是如果獲得鎖的線程挂掉了，而且鎖也沒有釋放，那麼整個程式其實就被block在那了，而如果程式是lock-free的那麼即使有線程挂掉，也不影響整個程式繼續向下進行。是以，如果程式中的某一部分符合下面的條件判定描述，則我們稱這部分程式是符合lock-free的。反過來說，如果某一部分程式不符合下面的條件描述，則稱這部分程式是不符合 lock-free的。

CUDA程式設計——Mars：MapReduce on GPU

　　是不是不用鎖就是lock-free呢？舉個例子：

while (x == ) {
    x = -x;
}

　　在這裡如果兩個線程同時執行，可能同時進入while循環，然後x兩次改變值之後，依然是0，那麼兩個線程就會一直互相在這裡阻塞掉了，是以這裡雖然沒有鎖，依然不是lock-free的。

4 Lock-free的實作方式

　　當我們準備要滿足 lock-free 程式設計中的非阻塞條件時，有一系列的技術和方法可供使用，如原子操作（Atomic Operations）、記憶體栅欄（Memory Barrier）、避免 ABA 問題（Avoiding ABA Problem）等。那麼我們該如何抉擇在何時使用哪種技術呢？可以根據下圖中的引導來判斷。

CUDA程式設計——Mars：MapReduce on GPU

4.1 RMW

　　Read-modify-write是一類原子操作(such as test-and-set, fetch-and-add, and compare-and-swap)，即同時讀取一個記憶體位置和寫入一個新值，不論寫入的新值是一個全新的值或是前一個值的函數。所謂原子操作是指不會被線程排程機制打斷的操作；這種操作一旦開始，就一直運作到結束，中間不會有任何線程切換。原子操作也大量用于非阻塞同步。

4.2 CAS

　　Compare-and-swap 比較記憶體中一個位置的内容和給定值，隻有兩個值相同時，用新的值更新記憶體中那個位置的内容。CAS由一個原子操作完成。原子性保證新的值是基于最新的資訊計算的。如果那個值在這個過程中被其它線程更新過，則會發生寫入失敗。CAS的傳回值表示操作是否成功，如可以傳回一個bool值，這種CAS變體稱為compare-and-set，也可以傳回從記憶體中讀到的值（不是被寫入的值）。

function cas(p : pointer to int, old : int, new : int) returns bool {
    if *p ≠ old {
        return false
    }
    *p ← new
    return true
}

4.3 ABA problem

　　下面是 ABA 問題發生的過程：

T1 線程從共享的記憶體位址讀取A；
T1 線程被搶占，線程 T2 開始運作；
T2 線程将共享的記憶體位址中的值由A修改成B，然後又修改回A；
T1 線程繼續執行，讀取共享的記憶體位址中的值仍為A，認為沒有改變然後繼續執行。

　　如果同步機制通過值相同來判斷“沒有改變”，如CAS，就可能産生錯誤。因為在讀兩次值期間，其它線程可能執行了，甚至其它線程修改了第一個線程的運作假設，第一個線程被欺騙，以為“什麼都沒發生”，繼續以舊的假設運作，這樣就會造成錯誤。

4.4 Memory barrier

　　記憶體栅欄也叫記憶體屏障，是一類同步屏障指令，是CPU或編譯器在對記憶體随機通路的操作中的一個同步點，使得此點之前的所有讀寫操作都執行後才可以開始執行此點之後的操作。

　　大多數現代計算機為了提高性能而采取亂序執行，這使得記憶體屏障成為必須。語義上，記憶體屏障之前的所有寫操作都要寫入記憶體；記憶體屏障之後的讀操作都可以獲得同步屏障之前的寫操作的結果。是以，對于敏感的程式塊，寫操作之後、讀操作之前可以插入記憶體屏障。

5 是lock-free 還是 wait-free？

　　在lock-free程式中，任何特定的線程可能會被其他線程阻塞，當給定線程被挂起時，其絕對不會阻止其他線程繼續運作。CPUs可以繼續執行其它線程中。那麼lock-free算法提高系統的整體吞吐量，并且僅僅隻增加特定事務的延時。

　　Wait-free算法確定CPUs持續做有用的工作，明確定證沒有線程會被另一個線程阻塞[5]。相對于lock-free，wait-free算法更強力地保證高吞吐量， Linux核心的lockless page cache就是一個 wait-free例子。

　　我們回過頭來看Mars中的設計，Mars中多線程讀寫的是共享記憶體嗎？雖然名字上是共享記憶體，整個記憶體對于任一線程都是可存取的，但是每個線程隻會讀寫屬于自己的局部記憶體區，任何一個線程都不會被其他線程阻塞。是不是更應該是一個wait-free算法？

[1] https://developer.nvidia.com/digits

[2] http://preshing.com/20120612/an-introduction-to-lock-free-programming/

[3] Wenbin Fang, Bingsheng He, Qiong Luo, Naga K. Govindaraju: Mars: Accelerating MapReduce with Graphics Processors. IEEE Trans. Parallel Distrib. Syst. 22(4): 608-620 (2011)

[4] CUDA—Tutorial 5—Performance of Atomics. http://supercomputingblog.com/cuda/cuda-tutorial-5-performance-of-atomics

[5] Alistarh, Dan, Keren Censor-Hillel, and Nir Shavit. “Are lock-free concurrent algorithms practically wait-free?.” Proceedings of the 46th Annual ACM Symposium on Theory of Computing. ACM, 2014.

[6] https://en.wikipedia.org/wiki/Prefix_sum

[7] https://en.wikipedia.org/wiki/Memory_barrier

[8] https://en.wikipedia.org/wiki/Prefix_sum

CUDA程式設計——Mars：MapReduce on GPU