點(diǎn)擊上方藍(lán)字關(guān)注我們

GPU事務(wù)性內(nèi)存技術(shù)研究

林玉哲^1,2,?張為華^1,2

1?復(fù)旦大學(xué)軟件學(xué)院，上海?201203

2?上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室，上海?201203

論文引用格式：

林玉哲,張為華.GPU事務(wù)性存儲(chǔ)器研究[J].大數(shù)據(jù), 2020, 6(4): 3-17.

LIN Y Z, ZHANG W H.A research on GPU transactional memory[J].Big Data Research，2020, 6(4): 3-17.

1 引言

隨著對(duì)高性能計(jì)算的需求越來越大， GPU因其擁有比CPU更豐富的計(jì)算資源、線程資源和更高的內(nèi)存帶寬，被廣泛應(yīng)用于大數(shù)據(jù)處理和圖形計(jì)算。

在大數(shù)據(jù)領(lǐng)域，有大量的GPU被服務(wù)商組織起來用于數(shù)據(jù)分析和數(shù)據(jù)處理。其中，有一類任務(wù)往往很少需要線程間的數(shù)據(jù)競爭，即使需要，一般也是以一種固定的方式對(duì)數(shù)據(jù)進(jìn)行共享和使用。一般來說， GPU非常適合處理這類任務(wù)（如深度學(xué)習(xí)、圖形計(jì)算）。對(duì)于這類任務(wù)來說，程序員可以預(yù)先估計(jì)訪問或修改共享數(shù)據(jù)的模式，利用GPU提供的原子操作和同步操作進(jìn)行數(shù)據(jù)的同步和保護(hù)。

然而，大數(shù)據(jù)分析和處理中的另一類任務(wù)需要?jiǎng)討B(tài)地對(duì)共享數(shù)據(jù)進(jìn)行并發(fā)訪問和修改。例如，一個(gè)銀行系統(tǒng)中可能存在多個(gè)線程同時(shí)訪問或修改某段數(shù)據(jù)的情況，而這種訪問和修改往往是動(dòng)態(tài)的，是由輸入的數(shù)據(jù)指定的。在這種情況下，想要保證程序的準(zhǔn)確性，就需要程序員實(shí)現(xiàn)更加復(fù)雜的并行機(jī)制。對(duì)于GPU程序來說，由于其線程量巨大以及特殊的單指令多線程（single instruction multiple threads， SIMT）的運(yùn)行機(jī)制，就需要程序員付出更多的努力才能寫出正確的程序。

在CPU中也曾存在同樣的問題，針對(duì)此，人們?cè)O(shè)計(jì)了事務(wù)性內(nèi)存（transactional memory，TM）來簡化程序員的工作。事務(wù)性內(nèi)存提供了合適的API，將程序員從復(fù)雜的并行程序的設(shè)計(jì)中解放出來。同理， GPU也可以用同樣的方式來解決這個(gè)問題，即GPU事務(wù)性內(nèi)存。

本文首先介紹GPU和事務(wù)性內(nèi)存，分析GPU事務(wù)性內(nèi)存的重要性；然后對(duì)兩類不同的GPU事務(wù)性內(nèi)存——軟件事務(wù)性內(nèi)存（software transaction memory， STM）和硬件事務(wù)性內(nèi)存（hardware transaction memory，HTM）的實(shí)現(xiàn)方案和重點(diǎn)問題進(jìn)行分析和探討；最后，對(duì)這些方案進(jìn)行對(duì)比，并對(duì)未來的研究方向進(jìn)行分析和展望。

2 GPU事務(wù)性內(nèi)存介紹

2.1 GPU

GPU是現(xiàn)今非常流行的多核處理器之一，被廣泛應(yīng)用于高性能計(jì)算、大數(shù)據(jù)處理等領(lǐng)域。一種常見的GPU架構(gòu)如圖1所示。GPU中有很多流多處理器（streaming multiprocessor，SM），每一個(gè)流多處理器中包含多個(gè)GPU核心，也稱為流處理器（streaming processor，SP）。首先，在同一個(gè)SM中的多個(gè)SP共同使用寄存器文件以及多種緩存。其中比較重要的是共享內(nèi)存和L1緩存，它們共同占用一塊存儲(chǔ)空間，同一個(gè)SM的不同SP可以通過共享內(nèi)存來共享數(shù)據(jù)，程序員可以人為地劃分共享內(nèi)存的大小，剩下的空間將被用作L1緩存。其次，不同的SM共同擁有L2緩存、專門為常量所使用的常量內(nèi)存和專門針對(duì)紋理信息優(yōu)化過的紋理內(nèi)存。最后，在GPU外有屬于GPU的全局內(nèi)存，CPU可以通過數(shù)據(jù)總線將數(shù)據(jù)傳輸?shù)竭@個(gè)GPU的全局內(nèi)存上。程序在運(yùn)行時(shí)，每一個(gè)SP上可以跑一個(gè)線程，在GPU中，每32個(gè)線程組成一個(gè)線程束（warp），這個(gè)線程束的線程以SIMT的方式執(zhí)行指令。具體而言，一個(gè)線程束中的32個(gè)線程在每一個(gè)時(shí)刻都是同時(shí)執(zhí)行同一條指令的，每一個(gè)線程都擁有獨(dú)立的地址空間。從線程可以使用的空間和層次考慮，每一個(gè)線程可以獨(dú)立地使用所屬SM中的寄存器文件里的寄存器；通過共享內(nèi)存與同SM中的其他線程進(jìn)行數(shù)據(jù)交互；通過全局內(nèi)存與其他線程共同使用共有的數(shù)據(jù)；在全局內(nèi)存上擁有一段獨(dú)立的地址空間，其被作為自己的本地內(nèi)存（local memory）。除此之外，同一個(gè)線程束中的線程還可以通過GPU提供的原語進(jìn)行數(shù)據(jù)交互。

GPU具有高計(jì)算能力、高并發(fā)能力、高訪存速度的特性，利用這些特性實(shí)現(xiàn)的一些常用的數(shù)據(jù)結(jié)構(gòu)比CPU實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)擁有更高的性能。需要處理的數(shù)據(jù)被組織成各種數(shù)據(jù)結(jié)構(gòu)，并被放置在GPU上等待被管理和使用。其中，在只讀的情況下，GPU的性能比比CPU高很多。然而在讀寫混合的情況下，由于存在對(duì)數(shù)據(jù)的保護(hù)和同步的需求，GPU想要保持與CPU相同的性能比就會(huì)非常困難，并且，程序員編程的難度也大大增加。因此GPU迫切需要一個(gè)通用的并行程序設(shè)計(jì)的解決方案。

2.2 事務(wù)性內(nèi)存

事務(wù)性內(nèi)存是一種常用的并行程序設(shè)計(jì)的解決方案。針對(duì)并行程序，程序員可以通過使用鎖結(jié)構(gòu)（如mutex lock）、原子操作（如比較再交換（compare and swap，CAS））和內(nèi)存屏障（memory barrier）來完成并行程序?qū)蚕頂?shù)據(jù)的保護(hù)和使用。但是對(duì)于這些設(shè)計(jì)，尤其是復(fù)雜的并行程序，往往需要程序員認(rèn)真考慮程序的正確性和效率，這個(gè)過程需要很長時(shí)間。為了簡化這一過程，事務(wù)性內(nèi)存作為一種并行程序設(shè)計(jì)的方式被提出。

事務(wù)（transaction）源自數(shù)據(jù)庫系統(tǒng)，在數(shù)據(jù)庫系統(tǒng)中，事務(wù)必須滿足ACID的原則，即原子性（atomicity）、一致性（consistency）、隔離性（isolation）和持久性（durability）。

圖1???一種常見的GPU架構(gòu)

事務(wù)性內(nèi)存正是借鑒了數(shù)據(jù)庫中事務(wù)的概念實(shí)現(xiàn)的。事務(wù)性內(nèi)存往往會(huì)提供一整套的API供程序員使用。一般而言，事務(wù)性內(nèi)存提供的API至少包括TX_BEGIN和TX_END。TX_BEGIN代表事務(wù)的開始， TX_END代表事務(wù)的結(jié)束，在這之間的所有操作都被視為在同一個(gè)事務(wù)之中。圖2展示了一個(gè)事務(wù)性內(nèi)存的使用案例，從第2行到第6行，TX_BEGIN和TX_END包含的部分即一個(gè)事務(wù)的范圍。在這個(gè)范圍里分別讀取了內(nèi)存中保存的A的值，修改了內(nèi)存中B和C的值。這3個(gè)操作在一定程度上滿足了事務(wù)的原則(①一般不包括持久性，因?yàn)槭聞?wù)性內(nèi)存針對(duì)的是對(duì)內(nèi)存的修改，而一般內(nèi)存中保存的數(shù)據(jù)并不是持久的（宕機(jī)就會(huì)失去）)，即3個(gè)操作必然全都成功或是全都失敗（原子性）；在事務(wù)提交之前，其他事務(wù)無法讀到新的B和C（隔離性）；根據(jù)不同的事務(wù)性內(nèi)存的設(shè)計(jì)，也可以保證在事務(wù)被提交前，A的值不會(huì)被其他人修改（一致性）。而對(duì)于在事務(wù)之外的操作，如第7句對(duì)A值的修改，一般會(huì)直接導(dǎo)致其他涉及A值的讀寫的事務(wù)被中止（abort）。

圖2???事務(wù)性內(nèi)存的使用案例

事務(wù)之中所有對(duì)內(nèi)存的修改在一定程度上滿足了ACID的要求（不同的系統(tǒng)和算法提供的事務(wù)性內(nèi)存的標(biāo)準(zhǔn)可能略有區(qū)別）。這樣，程序員通過使用這種簡單方便的API，可以大大提高編程效率，同時(shí)也提高了程序的準(zhǔn)確性。依據(jù)實(shí)現(xiàn)方式，事務(wù)性內(nèi)存內(nèi)部機(jī)制的實(shí)現(xiàn)被分為軟件事務(wù)性內(nèi)存和硬件事務(wù)性內(nèi)存。目前， CPU上關(guān)于各種事務(wù)性內(nèi)存的設(shè)計(jì)方案和策略以及如何高效地利用事務(wù)性內(nèi)存解決實(shí)際問題的研究已經(jīng)十分豐富，因此本文將討論的重點(diǎn)放在GPU上事務(wù)性內(nèi)存的設(shè)計(jì)上。

2.3 GPU事務(wù)性內(nèi)存

由于GPU使用SIMT的編程模型并且擁有大量的線程，其在復(fù)雜的并行程序上面臨的問題比CPU更加復(fù)雜。因此，雖然GPU提供了原子操作和內(nèi)存同步機(jī)制，但是面對(duì)復(fù)雜的并行程序，GPU上的事務(wù)性內(nèi)存是十分必要的。

GPU事務(wù)性內(nèi)存也同樣根據(jù)其實(shí)現(xiàn)的方式被分為軟件事務(wù)性內(nèi)存和硬件事務(wù)性內(nèi)存。但是相比于CPU事務(wù)性內(nèi)存，其需要考慮的內(nèi)容要更加貼合GPU本身的諸多性質(zhì)。后文會(huì)詳細(xì)分析在不同實(shí)現(xiàn)方式下，事務(wù)性內(nèi)存實(shí)現(xiàn)所需要考慮的問題和解決它們的具體方法。

3 GPU STM

GPU STM是指利用現(xiàn)有的GPU提供的原語用軟件方法實(shí)現(xiàn)的事務(wù)性內(nèi)存。整體來說，雖然不同GPU STM的具體實(shí)現(xiàn)不同，但是其指導(dǎo)思想是一致的。

首先需要確定的是內(nèi)存保護(hù)的粒度，粒度可以以字（4個(gè)字節(jié)）為單位，也可以以指定的步長為單位。系統(tǒng)會(huì)將自己所擁有的所有內(nèi)存以設(shè)定好的粒度記錄在一張被稱為鎖表（lock-table）的表里，該表的每一行對(duì)應(yīng)一個(gè)單位的內(nèi)存，記錄了對(duì)應(yīng)內(nèi)存的版本號(hào)以及其是否正在被占用。

其次需要確定的是執(zhí)行的粒度。具體來講，需要決定執(zhí)行一個(gè)事務(wù)的是一個(gè)線程，還是一個(gè)線程束。這樣的一個(gè)粒度被稱為執(zhí)行單元。每一個(gè)執(zhí)行單元在執(zhí)行一個(gè)事務(wù)時(shí)，會(huì)有一組用于追蹤所有內(nèi)存的讀和寫的讀集和寫集，分別記錄這個(gè)事務(wù)訪問和修改的內(nèi)存位置及其版本號(hào)。

事務(wù)在需要訪問或修改一段內(nèi)存時(shí)，會(huì)先訪問鎖表，確定該段內(nèi)存是否被占用，在確定可用時(shí)，會(huì)將其記錄在自己的讀集或?qū)懠?#xff0c;并獲取相應(yīng)的鎖（根據(jù)方案的不同也可以不獲取鎖，只是確定其是否被占用）。接著，就可以執(zhí)行想要執(zhí)行的指令和操作（一般指內(nèi)存的讀和寫）。這里的寫操作是特殊的，有可能并不是直接寫回內(nèi)存，而是寫在一個(gè)緩沖區(qū)里。不同的算法將數(shù)據(jù)寫回內(nèi)存的時(shí)機(jī)并不相同，一般來說，它們會(huì)將時(shí)機(jī)選擇在進(jìn)行寫操作或提交的時(shí)候。但是不論何時(shí)寫回，這個(gè)寫回過程都是受到鎖保護(hù)的。如果在寫入內(nèi)存之前發(fā)現(xiàn)鎖表記錄的版本號(hào)與自己的讀/寫集記錄的版本號(hào)不一致或是鎖表中顯示該段內(nèi)存已被占用，則該事務(wù)會(huì)被中止并回退（roll back）。成功完成的事務(wù)被稱為提交（commit）成功。

在以上的設(shè)計(jì)中，GPU STM和CPU STM的設(shè)計(jì)是類似的，但是在具體的策略方面，GPU STM需要一些單獨(dú)的考慮。

3.1 執(zhí)行粒度與鎖問題

GPU STM的執(zhí)行粒度一般有兩種：以一個(gè)線程束為粒度。

在GPU中，一個(gè)線程束里的32個(gè)線程是以SIMT的方式運(yùn)行的，也就是說，這32個(gè)線程每時(shí)每刻都在執(zhí)行同一條指令。以線程束為粒度的STM可以用于一個(gè)線程束處理一個(gè)任務(wù)的應(yīng)用。這個(gè)線程束通過共享內(nèi)存來使用同一組讀/寫集。這種設(shè)計(jì)將一個(gè)線程束看作一個(gè)執(zhí)行單元，回避了很多SIMT獨(dú)有的問題，但是這種設(shè)計(jì)同時(shí)也限制了GPU STM的使用范圍，即要求使用者必須以線程束為粒度來處理問題。

相比于以線程束為粒度，以一個(gè)線程為粒度的方案更加靈活。以一個(gè)線程為粒度意味著每一個(gè)線程會(huì)維護(hù)一組讀集和寫集，并自己負(fù)責(zé)這個(gè)線程的事務(wù)的處理和提交。這樣的設(shè)計(jì)適用于更多的應(yīng)用場景，但是以線程為粒度的STM需要解決可能由SIMT導(dǎo)致的死鎖和活鎖問題。

3.1.1 死鎖問題

首先，考慮一種常見的實(shí)現(xiàn)方式：自旋鎖（spinlock）。如圖3所示，每一個(gè)線程在訪問一段內(nèi)存前都會(huì)申請(qǐng)對(duì)應(yīng)的鎖（一般用CAS指令將lock-table的對(duì)應(yīng)位置置為真），如果沒有獲得這個(gè)鎖，則會(huì)不停地重復(fù)申請(qǐng)，直到獲得這個(gè)鎖才會(huì)繼續(xù)前進(jìn)，在使用完這段內(nèi)存或是提交時(shí)再釋放這個(gè)鎖。這樣的方案在CPU的設(shè)計(jì)中可能是可行的，但是在GPU中，設(shè)想這樣一種情況：位于同一個(gè)線程束的線程1和線程2需要同時(shí)修改同一段內(nèi)存，它們會(huì)同時(shí)運(yùn)行這段代碼，請(qǐng)求那段內(nèi)存的鎖。那么兩個(gè)線程必然會(huì)有一個(gè)成功、一個(gè)失敗。假設(shè)線程1成功得到了這個(gè)鎖，那么線程2會(huì)由于獲取鎖失敗而一直重復(fù)運(yùn)行第一行。由于GPU是以SIMT的方式運(yùn)行的，同一個(gè)線程束中的線程總是運(yùn)行同一條指令，那么線程1會(huì)被迫隨著線程2在第一句處空轉(zhuǎn)，無法進(jìn)入critical p進(jìn)行針對(duì)這段內(nèi)存的操作，自然也無法釋放一直被線程2請(qǐng)求的那個(gè)鎖，于是這里產(chǎn)生了死鎖。

解決自旋鎖的死鎖問題很簡單，因?yàn)樽孕i產(chǎn)生的原因是本可以正常前進(jìn)的線程被迫跟著不能正常前進(jìn)的線程空轉(zhuǎn)，所以只需要改變?cè)O(shè)計(jì)方案，使不能正常前進(jìn)的線程跟著正常前進(jìn)的線程空轉(zhuǎn)即可。如圖4所示，線程2會(huì)在第3行失敗，但是由于這里只是一個(gè)if的判斷語句，線程2會(huì)跟著線程1繼續(xù)前進(jìn)，線程1會(huì)進(jìn)入第4行和第5行，而線程2會(huì)跟著線程1一起空轉(zhuǎn)。線程1在第5行釋放了鎖，在運(yùn)行完第6行之后，結(jié)束任務(wù)，于是線程2可以回到第2行（線程1此時(shí)空轉(zhuǎn)），然后在第3行重新申請(qǐng)已經(jīng)被線程1釋放的鎖。

圖3???通過自旋鎖實(shí)現(xiàn)并發(fā)控制

圖4???解決了死鎖的自旋鎖實(shí)現(xiàn)方案

3.1.2 活鎖問題

雖然圖4的方案解決了死鎖的問題，但是其只考慮了一個(gè)需求一個(gè)鎖的情況，在實(shí)際使用時(shí)，STM往往會(huì)申請(qǐng)多個(gè)內(nèi)存單元的鎖，這時(shí)圖4的算法又會(huì)帶來活鎖的問題。

通常來說，在一個(gè)線程需要多個(gè)鎖時(shí)，如果它不能獲得需要的全部的鎖，那么它必須在發(fā)現(xiàn)不能獲取全部的鎖時(shí)，釋放自己已經(jīng)獲得的鎖，這是為了避免自己一直持有的鎖和其他線程產(chǎn)生死鎖。圖5展示了需要同時(shí)申請(qǐng)兩個(gè)鎖的情況下的一種代碼實(shí)現(xiàn)。假設(shè)一個(gè)事務(wù)擁有一個(gè)需要申請(qǐng)的鎖的表單（數(shù)組locks，在這個(gè)例子中其長度為2），在第3行和第4行分別申請(qǐng)兩個(gè)鎖。一旦第二個(gè)鎖獲取失敗，其就會(huì)釋放第一個(gè)鎖（第11行）。在CPU的設(shè)計(jì)中，這么做是有一定概率產(chǎn)生活鎖的，因?yàn)榭赡艽嬖趦蓚€(gè)線程，線程1的數(shù)組locks的內(nèi)容為鎖1和鎖2，而線程2的數(shù)組locks的內(nèi)容為鎖2和鎖1。這兩個(gè)線程首先都執(zhí)行了第3行，分別獲得了鎖1和鎖2，而后又恰好同時(shí)執(zhí)行了第4行，雙方都發(fā)現(xiàn)自己無法繼續(xù)獲得鎖，繼而又同時(shí)執(zhí)行了第11行，各自釋放了自己獲得的鎖，進(jìn)入重試（retry），然后在重試時(shí)又一次經(jīng)歷了這種獲得鎖和釋放鎖的過程。

圖5???申請(qǐng)兩個(gè)鎖的情況下的實(shí)現(xiàn)方案

時(shí)間上的巧合使得線程1和線程2不斷地重復(fù)獲得鎖和釋放鎖的過程。這種活鎖的情況對(duì)于CPU來說是可能發(fā)生的，而在GPU上由于SIMT的特性（同一個(gè)線程束內(nèi)不同的線程同時(shí)執(zhí)行同一個(gè)指令），導(dǎo)致這種同時(shí)性成為必然，即在GPU編程中，這種設(shè)計(jì)必然會(huì)導(dǎo)致活鎖問題。

為了解決活鎖問題，不同的研究者給出了不同的解決方案。GPU-STM采用了一種復(fù)雜的鎖排序的機(jī)制來避免活鎖的產(chǎn)生。簡單來說，產(chǎn)生活鎖的前提是兩個(gè)線程同時(shí)獲得了對(duì)方需要的鎖，然后發(fā)現(xiàn)無法進(jìn)一步獲取被對(duì)方拿在手里的其他鎖，因此又同時(shí)釋放了自己已經(jīng)拿到的鎖，進(jìn)入這樣一個(gè)循環(huán)狀態(tài)。而如果線程獲取鎖的順序按照一種固定的邏輯，就不會(huì)存在這樣的情況了。如圖5所示的例子，如果兩個(gè)線程需要鎖的順序都是鎖1、鎖2，就不會(huì)出現(xiàn)活鎖了。

盡管鎖排序解決了活鎖的問題，但是排序的代價(jià)是很大的，因此Shen Q等人提出了另一種解決方案，為鎖設(shè)計(jì)了優(yōu)先級(jí)。在他們的設(shè)計(jì)中，擁有較小線程號(hào)的事務(wù)擁有更高的優(yōu)先級(jí)，它們能夠從擁有較低優(yōu)先級(jí)的事務(wù)那里將鎖“搶”過來。于是，在圖5的情境中，線程1和線程2首先分別獲得了鎖1和鎖2，在接下來的一步中，線程1的優(yōu)先級(jí)比線程2高，因此線程1可以將鎖2從線程2那里“搶”過來，現(xiàn)在線程1擁有了全部的鎖，線程2沒有獲得鎖，線程2會(huì)陪著線程1空轉(zhuǎn)，待線程1完成自己的事務(wù)釋放了兩個(gè)鎖之后，線程2才會(huì)重新開始自己申請(qǐng)鎖的流程。

3.2 執(zhí)行策略

與CPU TM相同，GPU STM也需要考慮執(zhí)行策略，其內(nèi)容主要包括版本管理（version management）、沖突檢測（conflict detection）、重試和回退，大部分與GPU TM相關(guān)的文章對(duì)這些策略進(jìn)行了一定的分析和討論。

3.2.1 版本管理

版本管理一般包括積極的版本管理（eager version management）和消極的版本管理（lazy version management），其主要決定了事務(wù)在何時(shí)將修改的內(nèi)容真正地寫回內(nèi)存。

積極的版本管理指的是事務(wù)在寫回?cái)?shù)據(jù)的策略上是積極的，具體來說，在積極的版本管理中，事務(wù)會(huì)立即將自己修改的內(nèi)容寫回內(nèi)存。在積極的版本管理的流程中，事務(wù)首先申請(qǐng)獲得要訪問的內(nèi)存的鎖以及版本號(hào)（根據(jù)一致性保護(hù)程度的不同，可以在需要用到時(shí)申請(qǐng)鎖，也可以在事務(wù)的開頭一次性全部申請(qǐng)），然后進(jìn)行自己的操作，讀和寫都在已經(jīng)得到保護(hù)的內(nèi)存上進(jìn)行，其中寫操作還需要將舊值記錄在一個(gè)被稱為undo-log的緩存中。在提交時(shí)，事務(wù)將釋放所有的鎖，事務(wù)正常結(jié)束，到此即可視為提交成功。當(dāng)出現(xiàn)沖突（如獲取鎖失敗）或宕機(jī)時(shí)，根據(jù)undo-log的內(nèi)容進(jìn)行回退。

消極的版本管理指的是事務(wù)執(zhí)行寫操作時(shí)，并不會(huì)立刻將其寫回內(nèi)存，而是先寫在一處緩存中，在提交時(shí)一次性將所有的內(nèi)存改變寫回內(nèi)存。也就是說，首先，事務(wù)檢查要訪問的內(nèi)存是否被占用。然后，對(duì)于讀操作，在讀取數(shù)據(jù)的同時(shí)，讀取其版本號(hào)并記錄在讀集中；對(duì)于寫操作，將要寫的數(shù)據(jù)寫入一段被稱為redo-log的緩存中，并記錄其版本號(hào)。在所有的操作結(jié)束后，進(jìn)入提交階段，提交階段首先會(huì)根據(jù)寫集和讀集獲取相關(guān)內(nèi)存的版本號(hào)，并申請(qǐng)寫集中需要寫回的內(nèi)存的鎖，比較讀/寫集記錄的版本號(hào)與新獲得的版本是否匹配，在匹配成功且獲得了需要的鎖的情況下，事務(wù)會(huì)將緩存中的內(nèi)容寫回內(nèi)存，然后將鎖釋放。

這兩種版本管理的設(shè)計(jì)在GPU上都是可行的。總體來說，積極的版本管理在面對(duì)沖突較低的情形時(shí)擁有更高的效率，因?yàn)榉e極的版本管理回退的代價(jià)要高于正確提交的代價(jià)，而消極的版本管理則相反，在高競爭的場景中效率更高。

在以上的設(shè)計(jì)中，為了能夠充分利用GPU的存儲(chǔ)特性，如果容量足夠，redolog或undo-log會(huì)盡量放置在共享內(nèi)存或L1緩存中，而lock-table等全局共用的數(shù)據(jù)則被安置在全局內(nèi)存中。

3.2.2 沖突檢測

沖突檢測包括積極的沖突檢測和消極的沖突檢測。積極的沖突檢測會(huì)選擇在盡可能早的時(shí)間點(diǎn)進(jìn)行沖突檢測（或者說版本號(hào)的檢測），而消極的沖突檢測在提交時(shí)才進(jìn)行沖突檢測。

從理論上說，積極的沖突檢測可以避免線程做很多無用功，并盡早地進(jìn)行中止和回退，但是這會(huì)帶來一個(gè)問題，即GPU是以SIMT的方式運(yùn)行的，一個(gè)線程的中止和回退并不代表其真的可以重新開始這個(gè)事務(wù)，它必須要空轉(zhuǎn)，直到同一個(gè)線程束里的其他線程完成自己的事務(wù)或也進(jìn)入回退。因此這種設(shè)計(jì)往往更適合以線程束為粒度的TM設(shè)計(jì)，否則就需要讓同一個(gè)線程束里的所有線程處理的事務(wù)盡可能地有相似的行為。

對(duì)于消極的沖突檢測來說，當(dāng)其檢查到?jīng)_突時(shí)，事務(wù)已經(jīng)處于提交狀態(tài)，此時(shí)寫集的內(nèi)容大多已經(jīng)被寫過一次，這意味著這些操作都會(huì)變成無效的內(nèi)容，會(huì)造成資源的浪費(fèi)。但是由于檢測的次數(shù)少，在消極的沖突檢測中，出現(xiàn)沖突的次數(shù)會(huì)減少，回退的次數(shù)也會(huì)減少。

版本管理的方案也會(huì)影響沖突檢測的策略。積極的版本管理在寫集上的沖突檢測必然也是積極的，因?yàn)槠錇閷懠系膬?nèi)容申請(qǐng)鎖的條件之一就是要確認(rèn)版本號(hào)。但是積極的版本管理中在讀集上的沖突檢測既可能是積極的，也可能是消極的，因?yàn)樽x集在某些情況下是可以不申請(qǐng)鎖的。因此，讀集里的內(nèi)容可以在需要的時(shí)候立刻檢查版本（積極的沖突管理），也可以在最后提交時(shí)再檢查版本（消極的沖突管理）。

3.2.3 重試和回退

對(duì)于鎖的訪問，筆者使用了諸多的方法來保證不會(huì)出現(xiàn)死鎖或是活鎖問題。接下來需要討論的是，在真正遇到無法獲得鎖的情況下，尤其在積極的版本管理的情況下，是選擇重復(fù)嘗試獲取鎖，還是選擇中止并回退。一般而言，回退會(huì)直接放棄線程之前已經(jīng)做完的內(nèi)容，而重試意味著還有機(jī)會(huì)將當(dāng)前的事務(wù)繼續(xù)完成。但是也有相關(guān)研究顯示，在GPU上，回退比重試有更高的性能。原因是獲取鎖的行為本質(zhì)上是針對(duì)GPU全局內(nèi)存中l(wèi)ock-table里表示目標(biāo)內(nèi)存的條目的，通過CAS操作將其表示是否被占用的標(biāo)志位賦值為真，而這種原子操作會(huì)由GPU特定的硬件單元來完成，這意味著重復(fù)進(jìn)行這種CAS操作會(huì)頻繁地占用GPU資源，導(dǎo)致其他線程的CAS操作無法盡快完成。因此，理論上調(diào)用原子操作的次數(shù)越少越好。

4 GPU HTM

GPU HTM是指從硬件的角度對(duì)GPU的體系結(jié)構(gòu)進(jìn)行改進(jìn)，從而實(shí)現(xiàn)的事務(wù)性內(nèi)存。GPU HTM涉及的策略問題與GPU STM涉及的策略問題是類似的，區(qū)別在于GPU HTM旨在使用硬件的方法解決這一問題。GPU HTM一般需要對(duì)GPU的體系結(jié)構(gòu)做一定程度的更改。

一般來說，為了實(shí)現(xiàn)GPU HTM，對(duì)硬件的設(shè)計(jì)應(yīng)當(dāng)著重于解決這幾個(gè)問題：如何在SIMT的硬件模型下解決事務(wù)控制流的回退問題，如何設(shè)計(jì)讀集和寫集，如何完成事務(wù)的提交。

4.1 SIMT硬件模型下事務(wù)的回退

GPU要支持事務(wù)性內(nèi)存，有一個(gè)問題是繞不開的，即如何讓GPU支持事務(wù)的回退。這與CPU事務(wù)的回退有所不同，在以線程為粒度的事務(wù)性內(nèi)存中，同一個(gè)線程束中并行的復(fù)數(shù)個(gè)事務(wù)中，可能只有一部分線程的事務(wù)失敗需要回退，而GPU是以SIMT的方式來執(zhí)行指令的，這里就會(huì)產(chǎn)生控制流的分歧（divergence）。值得參考的是，GPU在處理判斷等語句時(shí)也會(huì)產(chǎn)生類似的分歧，因此GPU HTM一般會(huì)采用與之類似的方法來使GPU的硬件支持事務(wù)的回退。

4.1.1 分歧和回退處理的硬件基礎(chǔ)

在GPU的程序中，經(jīng)常會(huì)出現(xiàn)由判斷或循環(huán)導(dǎo)致的分歧，同一個(gè)線程束中的不同線程需要運(yùn)行不同分支上的指令，由于GPU的SIMT的執(zhí)行方式，這些線程在不同分支上的指令不得不被串行執(zhí)行，即在一部分線程運(yùn)行其中一個(gè)分歧上的指令時(shí)，其他線程也必須跟著這些線程空轉(zhuǎn)。為了減少這種串行帶來的影響，GPU使用SIMT指令棧來安排和調(diào)度指令，并負(fù)責(zé)控制每一個(gè)線程在分歧結(jié)束時(shí)的跳轉(zhuǎn)位置。

SIMT指令棧的實(shí)現(xiàn)如圖6所示。SIMT棧中保存了匯合地址、下一條指令地址和在該地址活躍的線程（活躍線程對(duì)應(yīng)的比特置為1）。GPU每從棧中出棧一個(gè)條目，就會(huì)根據(jù)該條目令相應(yīng)的活躍線程執(zhí)行相應(yīng)的指令，令非活躍線程空轉(zhuǎn)，并根據(jù)情況將下一條指令的條目入棧。圖6左側(cè)所示為將棧首標(biāo)記的條目出棧，右側(cè)所示為執(zhí)行的情況。

圖6展示了一個(gè)只有4個(gè)線程的線程束，其在A處進(jìn)行了一個(gè)判斷，然后第1線程和第4線程進(jìn)入了B，第2線程和第3線程進(jìn)入了C，在執(zhí)行完B或C后，4個(gè)線程于D處匯合。首先如圖6（a）所示，4個(gè)線程執(zhí)行A，棧中的第一個(gè)條目包括了這條指令的地址以及相應(yīng)的活躍線程。然后該條目出棧，令4個(gè)線程執(zhí)行A。由于該語句是一條判斷，會(huì)再入棧3個(gè)條目，結(jié)果如圖6（b）所示，按入棧先后分別表示：在分支結(jié)束后最終4個(gè)線程會(huì)共同執(zhí)行D；有兩個(gè)線程進(jìn)入了C分支執(zhí)行C處指令，它們將會(huì)在D處與其他線程匯合；有兩個(gè)線程進(jìn)入了B分支執(zhí)行B處指令，它們也會(huì)在D處與其他線程匯合。接下來依次將3個(gè)條目出棧，并分別執(zhí)行語句B、C、D。以圖6（b）將要出棧的表示B的條目為例，將該條目出棧，執(zhí)行B，理論上應(yīng)該再入棧一條表示緊接著B之后那條指令的條目，但是由程序流程圖可知，那條指令即D，為匯合處的指令，因此不需要再將該條目入棧了。圖6（c）和圖6（d）同理，在將圖6（d）中的條目出棧后，流程結(jié)束。

4.1.2 利用SIMT棧實(shí)現(xiàn)事務(wù)回退

在GPU HTM的設(shè)計(jì)中，往往需要對(duì)SIMT指令棧的細(xì)節(jié)進(jìn)行更改，使其能夠在事務(wù)回退時(shí)正確地安排需要回退的線程回退到指定的指令位置，并使不需要回退的線程保持空轉(zhuǎn)。

利用SIMT指令棧實(shí)現(xiàn)事務(wù)的回退如圖7所示，該指令棧是由Fung W W L等人設(shè)計(jì)的能夠支持回退的SIMT指令棧。在這個(gè)例子中，該段程序使用了一個(gè)事務(wù)，該事務(wù)除了開始與提交外，只包括了一條語句A，在事務(wù)結(jié)束之后，又執(zhí)行了一條語句B。其中，事務(wù)在提交時(shí)有一定的可能性會(huì)失敗，提交失敗的線程會(huì)回退到事務(wù)的開始處，并重新執(zhí)行。在改進(jìn)后的SIMT指令棧中設(shè)置了幾種狀態(tài)，其中N（normal）代表一般狀態(tài)，R（transaction retry）代表事務(wù)重試，T（transaction top）代表事務(wù)執(zhí)行到的最前面的位置。

圖6???SIMT指令棧的實(shí)現(xiàn)

當(dāng)執(zhí)行TX_BEGIN時(shí)（如圖7（a）所示），SIMT指令棧會(huì)保留TX_BEGIN的條目，并入棧兩個(gè)特殊的條目（如圖7（b）所示），按時(shí)間順序分別代表回退線程的起始地址和事務(wù)真正要執(zhí)行的地址，因此狀態(tài)分別為R和T，其中前者的活躍線程為空（因?yàn)槟壳皼]有線程要回退），后者的活躍線程應(yīng)與TX_BEGIN的活躍線程相同，這里為4個(gè)線程。當(dāng)執(zhí)行到TX_COMMIT時(shí)，第2線程、第3線程提交失敗（如圖7（c）所示），那么在R條目中這兩個(gè)線程對(duì)應(yīng)的比特就會(huì)被置為1（如圖7（d）所示）。接著為了執(zhí)行R條目，SIMT棧會(huì)復(fù)制一份除狀態(tài)為T外，其他與R條目完全相同的條目入棧，并將R條目的活躍線程清空。這樣，新的T條目就會(huì)被作為回退線程的起始（如圖7（e）所示）。在回退線程也成功提交后（如圖7（d）所示），剩下的R條目回退線程為空，這就代表沒有線程需要回退，該R條目也將被出棧（如圖7（f）所示）。此時(shí)，可以根據(jù)之前保留的TX_BEGIN條目確定該事務(wù)的活躍線程，并入棧相應(yīng)的TX_COMMIT之后的指令地址（如圖7（g）所示）。

圖7???利用SIMT指令棧實(shí)現(xiàn)事務(wù)的回退

4.2 讀集和寫集的硬件設(shè)計(jì)

GPU HTM和GPU STM一樣，需要使用讀集和寫集來記錄自己訪問或修改的內(nèi)存條目，同時(shí)，讀集和寫集也可以作為redo-log或undo-log來實(shí)現(xiàn)不同的版本控制。因此需要在GPU中開辟出一個(gè)空間作為讀集和寫集。

考慮到事務(wù)性內(nèi)存的粒度和第2.1節(jié)介紹的GPU體系結(jié)構(gòu)中各層級(jí)的存儲(chǔ)空間，GPU HTM往往以L1緩存或共享內(nèi)存為首選的讀/寫集的位置，然后在提交時(shí)，將讀/寫集中的內(nèi)容按照規(guī)則提交到L2緩存中，進(jìn)而提交到內(nèi)存里。這樣的設(shè)計(jì)一般符合redo-log的模式，即將寫集視為redo-log。但是在實(shí)際情況中，上層的緩存一般是有限的，因此往往只是作為對(duì)讀/寫集的緩存，真正的存儲(chǔ)位置為全局內(nèi)存中線程所擁有的本地內(nèi)存（local memory）。

4.3 GPU HTM的沖突檢測和提交

GPU HTM的沖突檢測和提交是通過在GPU中加入新的硬件實(shí)現(xiàn)的。如提出的方案，他們通過在GPU中加入日志單元（log unit）和提交單元（commit unit）來實(shí)現(xiàn)HTM的事務(wù)的沖突檢測和提交。他們的方案采用了基于值的沖突檢測，即沖突檢測中不使用版本號(hào)，而使用數(shù)據(jù)的值。GPU HTM中的讀集和寫集分別記錄了一個(gè)事務(wù)中讀取的值和更改的值。在提交時(shí)，日志單元負(fù)責(zé)收集每一個(gè)線程的讀集和寫集中的記錄，并傳送給提交單元，提交單元會(huì)將收到的寫集里的值寫回內(nèi)存，對(duì)比讀集里的值與對(duì)應(yīng)的全局內(nèi)存，若相同，則通過了沖突檢測。

提交單元用于提交事務(wù)并將修改的值寫回內(nèi)存的單元，為了能夠并行提交盡量多的數(shù)據(jù)，一般將內(nèi)存分成幾段，每一段對(duì)應(yīng)一個(gè)提交單元。每一個(gè)提交單元維護(hù)一個(gè)隊(duì)列，按順序以一種流水線的方式分階段同時(shí)處理傳遞過來的多個(gè)事務(wù)的記錄，為了提高效率，提交單元一般會(huì)在提交的最后同時(shí)寫回多個(gè)事務(wù)的記錄。處理流程大致分為5個(gè)步驟：第一步，提交單元獲得日志單元傳輸過來的記錄，檢查其中讀集的內(nèi)容和內(nèi)存中的內(nèi)容是否一致，由于這里的檢查一般需要一些時(shí)間，因此提交單元僅僅發(fā)起檢查，而不用等待檢查結(jié)束就開始下一步。第二步，檢查同時(shí)提交的事務(wù)中是否存在冒險(xiǎn)，即兩個(gè)同時(shí)提交的事務(wù)是否存在讀寫的沖突。第三步，等待第一步的檢查結(jié)束，對(duì)于產(chǎn)生冒險(xiǎn)的事務(wù)，會(huì)待其他事務(wù)提交之后再根據(jù)更新后的內(nèi)存重新進(jìn)行檢查。第四步，由于每一個(gè)提交單元負(fù)責(zé)一部分內(nèi)存，因此提交單元要將自己對(duì)某事務(wù)的預(yù)計(jì)提交結(jié)果廣播出去，并回收其他提交單元的預(yù)計(jì)提交結(jié)果，如果每個(gè)提交單元都確定可以提交，則通過這一步。第五步，將可以提交的事務(wù)提交，釋放相關(guān)內(nèi)存，并通知相關(guān)的線程提交是否成功。

圖8???添加了新硬件的GPU HTM的架構(gòu)

5 GPU STM和GPU HTM的性能分析與比較

5.1 性能分析

在GPU的性能測試上，事務(wù)性內(nèi)存常見的測試集包括Bank、哈希表等，由于不同的工作負(fù)載（如讀寫比例、沖突比例、線程數(shù)目、內(nèi)存大小）等原因，其性能表現(xiàn)有很大的差異。

在一般的GPU STM研究中，研究者多會(huì)將GPU STM與CPU TM進(jìn)行性能比較，以試圖體現(xiàn)他們的設(shè)計(jì)比一般的CPU設(shè)計(jì)有更高的性能和更好的應(yīng)用前景。參考文獻(xiàn)比較了PR-STM（GPU STM）和TinySTM（CPU STM）的性能差異，在前者使用512個(gè)線程，后者使用8個(gè)線程，測試集為哈希表的情況下，相比于TinySTM，PR-STM性能更高，是TinySTM性能的1～5倍，并且隨著事務(wù)大小（transaction size）的增加，PRSTM的性能優(yōu)勢逐漸增大。其中，PRSTM視情況大約能達(dá)到8×106TX/s的吞吐率，相對(duì)地，另一個(gè)GPU STM的設(shè)計(jì)GPU-STM能達(dá)到6×106TX/s，而基于CPU STM設(shè)計(jì)的TinySTM能達(dá)到2×106?TX/s?？紤]到GPU擁有更多的線程、更高的帶寬，這種性能差異并不令人滿意。在lightweight STM（GPU STM）與CPU TM的對(duì)比中，lightweight STM性能也只能達(dá)到CPU性能的5~7倍，并且實(shí)驗(yàn)中CPU為8核，GPU使用的是能達(dá)到最佳性能的配置?？紤]到一般情況下CPU HTM比CPU STM擁有更高的性能，這個(gè)性能差異會(huì)更小。

由于目前的GPU HTM的設(shè)計(jì)大多是在模擬器（GPGPU-Sim）中實(shí)現(xiàn)的，因此對(duì)GPU HTM的性能分析都停留在GPU HTM不同方案在不同情況下的速度差異，無法與GPU STM或CPU TM（包括STM和HTM）進(jìn)行比較，故在本文中缺少這個(gè)方面的數(shù)據(jù)。

5.2 GPU STM和GPU HTM的對(duì)比

GPU STM和GPU HTM各有優(yōu)劣，其主要區(qū)別是實(shí)現(xiàn)方法不同，但是它們想要實(shí)現(xiàn)的目標(biāo)、實(shí)現(xiàn)目標(biāo)所需要的策略是一致的。不同的實(shí)現(xiàn)方法決定了它們的性能和實(shí)現(xiàn)難易程度的不同。表1總結(jié)了它們的異同。

從目標(biāo)上來說，GPU STM和GPU HTM想要達(dá)到的目標(biāo)是一致的，即提供一組滿足程序員需求的API，使他們能夠避免煩瑣的并發(fā)設(shè)計(jì)、復(fù)雜的鎖的實(shí)現(xiàn)，以及使用原子操作和同步操作。

從需要考慮和關(guān)注的問題上來說， GPU STM和GPU HTM是類似的，都需要解決SIMT帶來的執(zhí)行的問題，包括活鎖、死鎖和回退，讀集和寫集的實(shí)現(xiàn)，版本管理，沖突檢測等策略選擇。

從性能上來說，GPU HTM比GPU STM擁有更大的潛力。因?yàn)槔碚撋嫌布脑O(shè)計(jì)更容易達(dá)到更好的效果。但是目前的情況是GPU HTM大多是在模擬器上實(shí)現(xiàn)的。

從實(shí)現(xiàn)難易程度上來說，GPU HTM比GPU STM復(fù)雜得多，因?yàn)镚PU的硬件更新?lián)Q代很快，GPU HTM也需要跟著硬件設(shè)計(jì)的改變而改變，除此之外還可能要有相適應(yīng)的編譯工具。而GPU STM理論上不會(huì)遇到這些問題，程序員甚至可以在沒有現(xiàn)成的GPU STM的情況下，自己寫一個(gè)簡易的版本在程序中使用。

6 GPU事務(wù)性內(nèi)存的總結(jié)和展望

就目前的發(fā)展情況來看，GPU事務(wù)性內(nèi)存還不夠成熟。由于GPU本身的特性， GPU事務(wù)性內(nèi)存的設(shè)計(jì)和使用受到諸多因素的制約。

首先，GPU的特性會(huì)導(dǎo)致事務(wù)性內(nèi)存的設(shè)計(jì)面臨諸多挑戰(zhàn)。由于GPU的SIMT的執(zhí)行方式，事務(wù)回退時(shí)會(huì)產(chǎn)生高額的代價(jià)；由于GPU具有大量的線程，在面對(duì)相同的處理數(shù)據(jù)時(shí)，GPU能夠并發(fā)地處理更多的數(shù)據(jù)，但也會(huì)遇到更多的競爭，產(chǎn)生回退的可能性更大；由于GPU的訪存模式， GPU在處理規(guī)則的數(shù)據(jù)時(shí)擁有更高的性能，但一般需要使用事務(wù)性內(nèi)存的應(yīng)用的數(shù)據(jù)大部分是動(dòng)態(tài)的，這并不十分適合使用GPU進(jìn)行處理。

其次，從實(shí)現(xiàn)方案和性能的角度來說，GPU事務(wù)性內(nèi)存不同的實(shí)現(xiàn)方法會(huì)造成不同程度的額外開銷。具體來說，盡管GPU STM可以給使用者帶來便利，但是其理論上的性能并不會(huì)高于使用者自己手動(dòng)設(shè)計(jì)的并發(fā)策略。并且，不同的事務(wù)性內(nèi)存的策略往往適用于不同的應(yīng)用，因此，使用者依然有必要仔細(xì)考慮自己的應(yīng)用更適合使用哪種方案的事務(wù)性內(nèi)存，甚至有必要根據(jù)自己的應(yīng)用對(duì)GPU STM進(jìn)行專門的優(yōu)化。而GPU HTM因?yàn)槭怯布脑O(shè)計(jì)，理論上可以達(dá)到比STM或使用者自己手動(dòng)實(shí)現(xiàn)的方案更好的性能，但是GPU HTM提供給使用者的選項(xiàng)也會(huì)相應(yīng)地減少，使用者依然要考慮已有的GPU HTM方案是否適合自己的應(yīng)用場景。

盡管GPU事務(wù)性內(nèi)存在諸多方面有所限制，但是其依然具有十分重要的潛在價(jià)值。GPU事務(wù)性內(nèi)存往往應(yīng)用于并發(fā)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，因此它的一個(gè)潛在的應(yīng)用場景是GPU數(shù)據(jù)庫系統(tǒng)。越來越多的研究試圖利用GPU來加速數(shù)據(jù)庫運(yùn)算以及利用GPU實(shí)現(xiàn)高效的底層數(shù)據(jù)結(jié)構(gòu)，而這也催生了對(duì)事務(wù)性內(nèi)存等通用的并發(fā)編程解決方案的需求。

GPU事務(wù)性內(nèi)存的發(fā)展還有很長的路要走，現(xiàn)在雖然已有針對(duì)GPU HTM的研究，但是門檻較高，研究者需要足夠精通GPU的硬件以及相關(guān)的模擬器。相比而言，針對(duì)GPU STM的研究相對(duì)容易，但是暫時(shí)缺乏非常高效和通用的版本。

總而言之，GPU事務(wù)性內(nèi)存仍然有很大的發(fā)展空間。

作者簡介

林玉哲（1996-），男，復(fù)旦大學(xué)軟件學(xué)院碩士生，主要研究方向?yàn)镚PU、并行計(jì)算、事務(wù)性內(nèi)存等 。

張為華（1974-），男，復(fù)旦大學(xué)軟件學(xué)院教授，主要研究方向?yàn)榫幾g、體系結(jié)構(gòu)、并行計(jì)算、系統(tǒng)軟件等 。

大數(shù)據(jù)期刊

《大數(shù)據(jù)（Big Data Research，BDR）》雙月刊是由中華人民共和國工業(yè)和信息化部主管，人民郵電出版社主辦，中國計(jì)算機(jī)學(xué)會(huì)大數(shù)據(jù)專家委員會(huì)學(xué)術(shù)指導(dǎo)，北京信通傳媒有限責(zé)任公司出版的期刊，已成功入選中文科技核心期刊、中國計(jì)算機(jī)學(xué)會(huì)會(huì)刊、中國計(jì)算機(jī)學(xué)會(huì)推薦中文科技期刊，并被評(píng)為2018年國家哲學(xué)社會(huì)科學(xué)文獻(xiàn)中心學(xué)術(shù)期刊數(shù)據(jù)庫“綜合性人文社會(huì)科學(xué)”學(xué)科最受歡迎期刊。

關(guān)注《大數(shù)據(jù)》期刊微信公眾號(hào)，獲取更多內(nèi)容

總結(jié)

以上是生活随笔為你收集整理的GPU事务性内存技术研究的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。