基于多核PC的MAP記錄表沖突規避算法

張 婷，李文敬，黃 帆+

(1.廣西民族大學相思湖學院 計算機科學與工程系，廣西 南寧 530008；2.南寧師范大學 物流管理與工程學院，廣西 南寧 530001)

0 引 言

多核處理機的不斷普及，為應用多處理器、充分發揮多核機的潛能、并行解決各領域的實際問題提供了更好的解決方案。而事務內存較鎖機制具有優勢，如：不會導致死鎖；允許事務并發執行[1]；事務的復合或嵌套能更好地實現。事務內存使用的是樂觀的并發機制，當事務發生沖突時，交由競爭管理策略來裁決哪個事務繼續執行，哪個事務被撤銷，重新執行。當系統中事務之間的沖突較小時，該方法可以維持較好的性能[2]。但是，假設一個極端的情況，就是事務之間的沖突極其頻繁，那么這將耗費大量的系統資源來進行沖突檢測及競爭管理的操作。沖突規避就是對事務的沖突情況進行預測，避免可能發生大量沖突的事務進入到系統中。沖突規避是一個新興概念，目前學術界對于沖突規避的研究甚少，文獻[3]提出了基于集群系統的沖突規避方法，即在事務啟動之前，根據歷史發生沖突的情況預測其發生沖突的可能性，并根據預測結果對事務進行調度，以降低事務的失敗率[3]。但是沖突規避的研究空間還很大，例如：如何對歷史沖突情況進行收集、如何提高預測沖突的效率、如何設計算法將數據與預測集合進行快速比較等等，都是需要繼續研究的課題，因此沖突規避還有很大的研究空間，具有極大的研究與應用價值[4]。

1 沖突規避思想的提出

首先分析一個傳統事務內存的生存周期，如圖1所示。事務開始時，底層事務管理器會給事務分配一個ID，并記錄下該事務開始時的指令地址，為防止發生沖突后，該事務可以回滾到開始的位置重新執行[5]。一個事務的執行過程可分為兩種可能，分別是成功和失敗，成功的執行過程為：事務開始→執行階段→事務提交→結束；失敗的執行過程為：事務開始→執行階段→事務回滾。在事務執行過程中進行讀寫一致性檢驗，當檢驗出讀寫地址發生沖突時，由競爭管理選擇一個事務回滾[6]。

圖1 傳統事務生存周期

事務內存使用的是樂觀的并發機制，當事務發生沖突時，交由競爭管理策略來裁決哪個事務繼續執行，哪個事務被撤銷，重新執行。當系統中事務之間的沖突較小時，該方法可以維持較好的性能。但是，假設一個極端的情況，就是事務之間的沖突極其頻繁，那么這將耗費大量的系統資源來進行沖突檢測及競爭管理的操作[7]。文獻[3]提出了沖突規避的思想，即在事務開始之前，判斷該事務發生沖突的可能性，若可能性較大，則暫時不讓該事務執行，避免執行后發生大量沖突影響系統性能。

采用沖突規避機制的事務執行流程如圖2所示，與傳統的事務執行流程所不同的是，事務的開始不再是不受限的，而是在每次新的事務開始之前，或是經過競爭管理被判回滾的事務重新執行之前，都要進行一次沖突預測，若判斷出該事務發生沖突的可能性較大，則掛起事務，反之，放行事務，開始執行[8]。

圖2 事務內存生存周期中加入沖突規避機制

如何預測到沖突的可能性是該算法的關鍵，設計了一個P-RHR(predict-repeat hash by random)，即：基于記錄表的隨機質數算法，可以在運行時記錄下發生沖突的讀寫地址集合，作為歷史沖突情況的記錄，保存到本地私有記錄表H(history)中。在事務開始之前，系統將事務的元素集合C(current)與H相比較，若集合C中的元素與H中的元素重復率達到一個閾值，則要掛起該事務[9]。為改進P-RHR算法耗時長的問題，提出了HLF-RHR(high and low frequency-repeat hash by random)，即：高低頻區分的隨機質數算法，高低頻表角色不同，各施其職，可以縮短記錄表的表長，提升查找速度，進而提高系統性能。

2 基于記錄表的沖突規避算法

2.1 P-RHR算法設計

目前學術界對于沖突規避的研究甚少，文獻[3]提出了基于集群系統的沖突規避方法，即在事務啟動之前，根據歷史發生沖突的情況預測其發生沖突的可能性，對事務進行調度，以降低事務的失敗率。但是沖突規避的研究空間還很大，例如：如何對歷史沖突情況進行收集、如何提高預測沖突的效率、如何設計算法將數據與預測集合進行快速比較等等，都是需要繼續研究的課題[10]。本文提出了一種基于記錄表的沖突規避算法，并改進記錄表的存儲方式。經實驗驗證，該算法能有效減少系統中的沖突，能夠防止高的沖突頻率對系統性能的影響。

首先需要建立一個記錄表，使用Hash算法來檢測讀寫沖突，將Hash沖突檢測出來的地址值記錄在內，記錄的方法有多種：編譯時直接生成、運行時隨時記錄[11]。選擇在運行時記錄下歷史發生沖突的地址值，生成一個動態的可供參考的記錄表[12]。

記錄表中記錄著地址值以及其對應的沖突次數n，其中，n是隨著沖突次數的增加而累加的，n的最大值定義為“線程數-1”。例如：線程數為16，則記錄的沖突次數n最大值為15。閾值的確定是本算法中的一個難點，經實驗研究，設定閾值為記錄表中的沖突次數n，能夠獲得較好的性能。

下面，對沖突規避算法用數學語言進行描述和量化。

分配一個隨機數p1作為優先級，其中，在加入沖突規避機制下，事務啟動的條件是優先級p1大于記錄表中的沖突次數n，即

p1>n

于是事務啟動的概率

從上面式子可以看出，影響事務的啟動的因素有線程數M和歷史沖突次數n，在線程數為M既定的情況下，事務歷史沖突次數n越大，事務啟動的概率越低，從而規避掉大量沖突。

例如：線程數為16，記錄表中某個地址值的沖突次數達到了15，則事務被分配的優先級必須大于15，也就是只能分配到16才能得以開始執行，幾率是1/16,所以歷史沖突越多，則事務越難得以開始執行。

在沖突檢測算法中加入沖突規避機制，算法描述如下：

輸入、輸出及(1)中定義最大線程數的過程請參見文獻[13]。

(2)每一個線程都取一個隨機數作為關鍵字，同時會獲得一個以線程數為上限的隨機數作為優先級p1，與本地的記錄表進行遍歷比對。例如：線程數為16，某線程得到56478作為關鍵字地址值，同時獲得一個小于16的隨機數5作為優先級。

(3)若關鍵字在記錄表里找不到相同地址值，直接進入到(7)。

(4)若關鍵字與記錄表里有相同的地址值，且該地址值的歷史沖突次數n小于該事務的優先級p1，則該事務可以順利開始執行，進入到(7)。例如，某線程的優先級是隨機數5，記錄表中相同地址值的歷史沖突次數是4，則線程可以開始執行。

(5)若關鍵字與記錄表里有相同的地址值，且該地址值的歷史沖突次數n大于或等于該事務的優先級p1，則該事務被掛起。

(6)重新給該事務分配新的隨機數作為地址值，重復(3)、(4)，若出現記錄表里相同地址值的歷史沖突次數n仍大于或等于事務的優先級p2，則繼續掛起重試，直到優先級pn大于記錄表中的沖突次數n，進入到(7)。

(7)事務得以順利開始執行，進行沖突檢測的步驟。若檢測過程中，該事務發生地址沖突，則記錄表中該地址值的歷史沖突次數增加1。

事務與記錄表進行地址值對比的流程如圖3所示。

圖3 事務與記錄表進行地址值對比

2.2 應用示例

用火車票網上售票系統來直觀說明該問題，若1000人同時訂購同一張“北京—上?！钡挠沧保瑒t讀寫地址的沖突情況嚴重，系統要花大量時間對1000個讀寫地址進行一致性檢驗，若同時訪問的人數更多，系統則更不堪重負。因此，可以將較為搶手的火車票在系統中的地址值記錄下來，假設“北京—上?！蹦秤沧钡牡刂分禐?821，“廣州—深圳”某硬座票的地址值為3881，建立成為一個記錄表，并將每個地址值的歷史沖突次數進行累計，假設某張票的歷史沖突次數為1000次。當購票高峰來臨時，若同時訂購同一張“4821”火車票的人數為3000人，系統將會給每個購票者分配一個小于3000的隨機數作為優先級，若購票者甲的優先級是1500，大于歷史沖突次數1000，則甲可以進入到訂票步驟；若購票者乙的優先級是800，小于歷史沖突次數1000，則被提示“很抱歉，無法訂購”。

沖突規避的思想可以在事務有可能產生沖突頻率較大的情況下，限制事務的啟動，對系統進行維護，以免造成不必要的開銷[13]。

2.3 實驗結果與分析

本地維護的記錄表使用C++的MAP類實現，MAP是一個關聯式容器，自動建立Key-Value對應，key和value 可以是自定義的類型，用戶可以對MAP內元素進行快速的查找、刪除、修改操作，因此可以實現歷史沖突地址值的查找、刪除、沖突次數增加等操作[14]。

加入沖突規避機制的算法與原算法RHR性能對比見表1。

由表1看出，加入了沖突規避機制的算法在運行時間上比無沖突規避算法耗時更多，因為需要在每次事務開始前進行一次調度，有一定的性能消耗，但是沖突規避算法的思想是“未雨綢繆”、“以時間為代價換穩定”，雖然犧牲了一些時間，但是沖突規避的好處還是顯而易見的，實驗結果表明，沖突規避算法中線程間發生沖突的次數明顯少于無沖突規避算法，能減少一半以上的沖突。隨著線程數的增加，沖突次數增加，運行時間減少。

表1 沖突規避算法與無沖突規避算法的性能對比

3 高低頻區分的HLF-RHR沖突規避算法

用MAP記錄表實現的沖突規避算法能減少一部分的沖突，但是耗時較多。因此，需要對算法的時間復雜度進行理論上的分析。對于記錄表中元素的查找，使用的是線性查找，在理想的情況下，每個元素依次找到對應值，時間復雜度為O(n)，在不理想的情況下，每一個元素都要經過n次查找來遍歷記錄表，則時間復雜度為O(n2)。n的大小與記錄表的長度有關，記錄表中的地址值越多，則遍歷的長度n就越大。

記錄表里的沖突地址值是隨著運行的次數不斷增加，有可能其中存放著大量的只發生過一次沖突的地址值，這些地址值極少被命中，存儲著這些低頻的地址值，不僅加長了記錄表的長度，還增加了遍歷記錄表的耗時，消耗系統性能，沖突規避的優勢不能很好體現出來。為了進一步減少查找的時間復雜度，對MAP記錄表沖突規避算法進行改進，提出高低頻區分的沖突規避算法，提高運行效率。

3.1 HLF-RHR沖突規避算法的機理

為了提高查找記錄表的效率，本文提出高低頻區分的沖突規避算法，HLF(high and low frequency)法，將只發生過一次地址沖突的地址值先存放到低頻表，當該地址值再次發生沖突，則將其從低頻表轉移至高頻表中，每發生一次沖突，高頻表里的沖突次數n就累加一次，n的上限為“線程數-1”。這樣，每次事務開始執行前，先與高頻表中的地址值進行比對，高頻表中存放著出現沖突頻率高的地址值，命中率較高。而低頻表則作為一個“過渡區”，存放著低頻地址，并負責將沖突次數增加的地址“運送”到高頻表。高低頻表角色不同，各施其職，可以縮短表長，提升查找速度，進而提高系統性能，工作流程如圖4所示。

圖4 事務與高低頻區分的記錄表進行比對

為了保持高頻表中的地址值永遠“高頻”，引入了清理機制，將一定時間內沒有增加沖突次數的地址值進行清理，將其轉回低頻表中。在實驗中，設置為1 s內，若記錄表中某地址值沒有被讀取的話，不管其在高頻表還是低頻表，都將沖突次數依次減1。

3.2 HLF-RHR沖突規避算法設計

在沖突檢測算法中加入HLF沖突規避機制，維護兩個記錄表，分別是HIGHMAP和LOWMAP，算法描述如下：

Begin：

輸入、輸出及(1)中定義最大線程數的過程請參見文獻[14]。

(2)每一個線程都取一個隨機數作為關鍵字，同時會獲得一個以線程數為上限的隨機數作為優先級p1，與本地的HIGHMAP高頻記錄表進行遍歷比對。

(3)若關鍵字在高頻表中找不到相同的地址值，直接進入到(7)。

(4)若關鍵字與高頻表里有相同的地址值，且該地址值的歷史沖突次數n小于該事務的優先級p1，則該事務可以順利開始執行，進入到(7)。

(5)若關鍵字與記錄表里有相同的地址值，且該地址值的歷史沖突次數n大于或等于該事務的優先級p1，則該事務被掛起。

(6)重新給該事務分配新的隨機數作為地址值，重復(3)、(4)，若出現記錄表里相同地址值的歷史沖突次數n仍大于或等于事務的優先級p2，則繼續掛起重試，直到優先級pn大于記錄表中的沖突次數n，進入到(7)。

(7)事務得以順利開始執行，進行沖突檢測的步驟。

(8)若檢測出事務與其它事務發生地址值沖突，如果該事務的地址值在高頻表中，將高頻表中地址值的沖突次數增加1；如果地址值在低頻表中，將低頻表的地址值沖突次數增加1，沖突次數累加到2次時，將該地址值從低頻表中刪除，添加到高頻表中。

接下來分析高低頻區分的記錄表是否比單個記錄表更具有效率上的優勢。查找單個記錄表中一個元素，理想的時間復雜度為O(n)，為了減少記錄表的長度，將記錄表分為高頻表和低頻表，假設高低頻表中的地址值數量剛好是1∶1,那么每個表的長度是原來的一半，可以用數據結構當中的折半查找來說明該問題。折半查找將每次事務查找記錄表的長度縮小二分之一，在理想的情況下，時間復雜度可以縮短到O(lgn)[15]。

3.3 應用示例

繼續用火車票網上售票系統的實例說明該問題，根據歷史發生讀寫地址沖突的情況，將容易發生沖突的地址值記錄在高頻表中，高頻表中維護的是一組“高頻詞”序列。而某些路線車票的歷史購買沖突情況不多，則將其放入低頻中。

當訂票高峰來臨，購買“北京—上海”火車票的地址值在與高頻表進行比對時，由于高頻表的長度比原先的記錄表短，因此能快速查找到相應的地址值，相對于將所有產生過沖突的地址值進行一一查找，該方法更具針對性，更能節約時間。

當某個路線被開發成旅游景點，該低頻路線的火車票變得炙手可熱時，其沖突次數在低頻表中累加，累加到某個值時，該火車票地址值被轉移到高頻表中，實行沖突規避機制，避免系統中產生大規模沖突的情況。

3.4 HLF-RHR沖突規避算法實現

高低頻表使用C++的MAP類實現，分別為HIGHMAP和LOWMAP。事務啟動前，先查找高頻表的記錄，低頻表中的歷史沖突地址若沖突次數增加到2次，則將該地址轉移到高頻表中。MAP實現的部分代碼如圖5所示。

圖5 MAP實現的高低頻表

實現沖突規避的部分代碼如圖6所示。

圖6 實現沖突規避的部分代碼

3.5 實驗結果與分析

使用了HLF沖突規避算法的HLF-RHR與原算法P-RHR的性能對比見表2。

表2 HLF-RHR與P-RHR性能對比

實驗結果表明，HLF-RHR算法在運行速度上比P-RHR算法有提高，因為將“歷史高頻地址”專門用高頻表維護之后，節省了“高頻地址”查找記錄表元素的時間，“高頻地址”往往出現的幾率和數量較多，在數據量大的情況下，HLF-RHR算法在效率上的優勢更加顯著。隨著線程數的增加，運行時間減少。

4 結束語

本文將沖突規避思想應用在基于多核PC的事務內存設計中。通過在事務開始執行之前，預測事務發生沖突的幾率，控制事務的發生和重啟，能夠防止高的沖突頻率對系統性能的影響。實驗結果表明，引入沖突規避機制的并行算法能避免較大的沖突。在算法上改進了基于記錄表的沖突規避算法，使用高低頻區分的方法，將記錄表的記錄按照沖突頻率分別用高頻表和低頻表維護，便于事務地址的查找，實驗結果表明，該算法相比原算法，在運行速度上有很大提升。

目前學術界對于沖突規避的研究甚少，還有很大的研究空間，沖突規避是一個新興概念，具有極大的研究與應用價值。