面向多核處理器的內存競爭記錄研究綜述

摘 要： 共享內存多線程編程是挖掘多核處理器并行性的重要方法，然而，共享內存的多線程程序在運行時存在不確定性，線程間的內存競爭是導致不確定性的主要來源。內存競爭信息量大，記錄時帶來的開銷大，實現內存競爭記錄是確定性重演共享內存多線程程序的關鍵。分別概括了現有軟件實現的內存競爭記錄機制和硬件實現的內存競爭記錄機制，并對內存競爭記錄的研究現狀進行了總結，指出了當前內存競爭記錄技術面臨的挑戰。

關鍵詞： 多核處理器； 多線程程序； 確定性重演； 內存沖突； 內存競爭記錄

中圖分類號： TP303 文獻標識碼： A 文章編號：2095-2163（2013）03-0053-07

Study on Memory Race Recording for Multi-core Processors

ZHU Suxia1， JI Zhenzhou1， LI Dong2

（1 School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China；

2 School of software， Harbin Institute of Technology， Harbin 150001， China）

Abstract： Writing shared-memory multithreaded programs become an important means to explore the parallel performance of multi-core processor systems. However， multithreaded programs are nondeterministic at run. Inter-thread memory race is the main source of this nondeterminism. Memory races are large and cost overhead. Memory race recording becomes the key technology to achieve deterministic replay of multithreaded programs. This paper summarizes the existing software memory race recording mechanisms and hardware memory race recording mechanisms. And the challenges for memory race recording are also pointed out.

Key words： Multi-core Processor； Multithreaded Program； Deterministic Replay； Memory Conflict； Memory Race Recording

0 引 言

自2005年Intel發布了基于x86的桌面版雙核處理器后，多核處理器成為應用的主流，編寫共享內存的多線程程序也隨之成為挖掘多核處理器系統并行性的重要技術策略。然而，共享內存的多線程程序在執行時存在著不確定性，即在相同輸入下，同一程序在同一臺處理器系統上運行多次，運行的結果卻可能出現不同。這種執行時的不確定性給多線程程序的編寫、調試、應用等都帶來了相應的實施難度和阻力。

劃分為記錄和重放兩個階段的確定性重演機制是解決共享內存多線程程序執行不確定性的有效手段[1]。確定性重演機制通過在記錄階段記錄程序運行時存在的不確定性信息，在重放階段使用所記錄的不確定性信息操控程序再現原始的執行結果。不確定的信息多種多樣，如輸入信息、檢查點信息、內存競爭等。由于當今處理器系統均提供高效的核間通信機制，使得共享內存的多線程程序在運行時內存競爭頻發，記錄的內存競爭信息量也在增加。同樣，對于較長的大型程序，必須精簡記錄文件，因為記錄的信息和要執行的并發程序共用內外存空間，且隨著目標程序運行記錄信息日漸增多，很大程度上會影響并發程序本身的執行，加重系統的運行負擔。內存競爭記錄目標就是在保證重演和原始執行一致的前提下，盡可能地減少記錄的信息以控制時空消耗。內存競爭記錄是實現共享內存多線程程序確定性重演的關鍵，已成為近年來計算機領域的研究熱點。

1 內存競爭

在共享內存的多線程程序中，如果兩個或多個線程訪問了同一個內存地址，并且至少有一個是寫操作，則會引發內存沖突。內存沖突共有3種類型：寫后讀（WAR—write after read）、讀后寫（RAW—read after write）、寫后又寫（WAW—write after write）。圖1（a）展示了一個包含2個線程的共享內存多線程程序的部分指令執行序列，2個線程都對共享內存x進行了讀寫操作，線程i先寫，線程j后讀，則發生了寫后讀（WAR）內存沖突。

在編寫多線程程序時，程序員通常使用同步操作來協同線程間內存沖突雙方指令的執行順序，使多個線程能夠以確定順序來訪問共享內存。如果使用了正確的同步操作，線程間內存沖突的順序是確定的，否則，線程間內存沖突的順序是不確定的。這種不確定順序的訪問可能會引起內存競爭。程序執行的結果最終將依賴于競爭的結果。

內存競爭是共享內存型多線程程序中最常見的錯誤之一，是多線程程序執行不確定性的根源所在。內存競爭有一般性競爭（general race）和數據競爭（data race）之分[2]。一般性競爭指多線程程序執行過程中所表現出來的不確定性。具體地說，在多線程程序執行過程中，不同線程對共享內存（無論是否由共同的鎖進行同步保護）執行順序的差別，都可以歸類為一般性競爭。數據競爭表現為不同的線程訪問同一個共享內存，而對共享內存操作沒有使用同一個鎖變量進行保護，即臨界區域違反了原子性執行，這是導致多線程程序出現并發錯誤的主要原因。用圖示解說這兩種競爭的發生過程，如圖1所示。

圖1 內存競爭示例

Fig.1 Example of memory race第3期 朱素霞，等：面向多核處理器的內存競爭記錄研究綜述 智能計算機與應用 第3卷

如圖1（a）中，x作為共享內存，因為線程i、j都沒有添加同步操作實現對x的互斥操作，使得兩線程可能會同時執行對x的操作，因而會引發數據競爭，導致程序運行結果不確定。程序執行的結果，最終取決于誰“贏得”競爭。競爭的結果往往取決于機器的配置和初始狀態（例如，緩存替換策略和緩存的初始內容）。在圖1（b）中，線程i、j都在共享內存x操作前后添加了同步操作語句，加鎖（lock）和解鎖（unlock）操作，可以實現兩線程互斥的訪問x，不會引發數據競爭。然而，沒有數據競爭同樣會使得程序存在不確定性。因為這種互斥的訪問并沒有明確排定兩線程間對x的操作順序，有可能線程i先寫x，也可能線程j先讀x，從而可能會引發一般性競爭，可能會導致程序多次運行得到不同的執行結果。

所有的內存競爭都屬于內存沖突，反之，則不成立，只有內存沖突雙方對應的內存操作的執行順序不確定時才會引發內存競爭。

2 內存競爭記錄

內存競爭記錄是實現共享內存多線程程序確定性重演的關鍵技術，已成為近年來計算機領域的研究熱點。截至目前為止，內存競爭記錄的研究已經取得了豐碩成果。下面概括論述國內外內存競爭記錄相關的研究進展。

2.1 軟件實現的內存競爭記錄機制

目前已有不少的軟件系統實現了多線程程序中內存競爭的記錄及重演，有的系統采用基于值的方法實現，有的采用順序的方法實現，有的記錄線程間同步操作的順序，有的記錄線程間內存交互的順序，還有記錄操作系統調度的順序，等等方式不一而足。系統的實現方式不同，應用的場合也有所不同。下面對其進行概略性介紹。

Recap[3]在編譯時對每個共享內存讀操作進行插樁，在程序運行時記錄每個共享內存讀操作的值。這種方式記錄了內存競爭的結果，能夠確定性地重演多線程程序，但是卻不能提供線程間共享內存操作的順序。同時，追蹤每個共享內存讀操作的值，將造成性能開銷增加、記錄的日志龐大。

Instant replay[4]則不記錄共享內存讀操作的值，而是將線程間的交互看做是對共享對象的操作，記錄線程中共享對象讀或寫的順序。Instant replay為每個共享內存對象添加一個版本號，每個線程都將訪問共享對象時的版本號信息記錄到日志文件中。通過這種方式，程序在重演時，就能夠確保所有線程訪問到與其原始執行時相同的版本號，從而可以確定性地重演多線程程序。在這種方式下，用戶要對共享對象及同步操作進行標記，以一種較粗的粒度記錄對共享內存操作的順序。Instant replay因為要跟蹤所有內存的讀寫操作，將帶來不小的開銷，而且只能適用于沒有數據競爭的場合。

SMP-Revirt[5]是Instant Replay對共享對象的一種概括，可記錄共享內存頁的狀態。在記錄日志階段，一個給定的內存頁只能處于并發讀或互斥寫的狀態，這些訪問控制通過改變一個線程的頁的權限來實現。SMP-Revirt同樣也是采用了較粗的粒度來記錄操作的順序，只能適用于沒有數據競爭的場合。因為SMP-ReVirt的插樁操作和對基于頁級粒度的共享內存的保護，存在偽共享和頁競爭。尤其是隨著處理器數目的增加，其開銷也越來越大。在配置4個CPU的情況下，SMP-ReVirt中一個應用開啟記錄功能后的運行時間就能夠達到正常運行時間的9倍之多。

RecPlay[6]通過記錄同步操作的順序，間接地記錄線程間交互的順序。同步操作的順序用一個標量Lamport時戳[7]來識認，在重演時，可以通過重建Lamport時戳實現確定性的重放。同時為了減少存儲的時戳信息，RecPlay只記錄時戳的增量，而非實際的時戳。但RecPlay只能夠重演不包含數據競爭的程序，而且也不能提供線程間內存操作的順序。

Russinovich[8]通過記錄線程調度順序間接記錄內存競爭，可以實現多線程程序的重演。假設多線程程序運行在一個單核處理器上，則指令執行的順序是由調度器決定的，Russinovich記錄器通過記錄調度器發出的調度日志就可以記錄多線程執行的順序。采用相同的調度順序重放程序，就可以再現競爭，實現程序的確定性的重演。然而，為了支持多線程能在單處理器上運行，Russinovich記錄的調度器調度的順序，10%的運行時間開銷在記錄階段，其中一半用于追蹤軟件的指令計數器，而另一半則來自記錄模塊。而且，隨著處理器數目的增加，開銷則會大幅度上漲。

JaRec[9]和DejaVu[10]是在java虛擬機上實現的記錄器。Jarec使用一個同RecPlay相似的方式，有效記錄了JVM上共享內存操作間的順序，但卻也同樣不能重演具有數據競爭的多線程程序。DejaVu則借鑒與Russinovich相近的思想，通過記錄線程運行時的關鍵事件，為多線程創建了邏輯上的調度。DejaVu獨立于系統底層的調度器，能實現與同java虛擬機的物理調度器分離，具有更好的可移植性。JaRec和DejaVu還同樣都會帶來較大開銷。JaRec可使得宏測試用例的運行速度減緩80%，Dejavu則使得綜合測試用例的運行速度減緩70%，同時使得SPLASH內核的運行速度也相應減緩了35%。

Kendo[11]通過確保同樣于原始執行時獲取鎖的順序而間接記錄內存競爭來重演多線程程序。Kendo要求程序實現正確的同步，但卻不能提供線程間內存操作的順序，另外也不支持包含數據競爭的程序。

Netzer[12]采用點到點記錄方式，為每個線程記錄一個由沖突雙方的指令計數值IC表示的依賴關系組成的日志。Netzer為每個線程提供一個指令計數器IC。IC標記了一個線程內指令執行的順序。而內存沖突則用線程間的一對IC值來表示。Netzer內存競爭記錄器不需要記錄線程內指令執行的順序，而只是記錄線程間指令的Happen-before關系[7]，即由沖突雙方IC值表示的依賴關系。重演時，線程內的指令按照IC值的大小重放，線程間的指令執行順序則按照記錄的偏序重放，這樣就可以重演多線程程序。沖突和程序的執行順序構成一個有向圖，兩者之間還可以進行傳遞性的約減（Transitive Reduction），從而使得有些沖突不需要記錄。這種傳遞性約減在Netzer中可證明是正確的，再次執行程序的過程與沒有約減時執行的過程是一致的。只是運行時間開銷較大，因為要跟蹤所有的內存讀寫操作，使得重演的速度犧牲了至少1個數量級。

PinPlay[13]基于流行的動態插樁工具Pin[14]，實現了一個通過易于使用的框架來捕獲程序執行 信息、確定性重演程序以及在合理的時間和空間消耗范圍內分析大型程序的執行過程。PinPlay主要應用于程序調試，而且只支持離線的重演。

ODR[15]記錄同步操作順序等信息，使用一種稱為DRI的技術，搜索能夠產生相同結果的運行空間，并推斷得出競爭的結果。ODR 減少了記錄階段的信息量及開銷，同時確保原始執行時的所有錯誤在執行時都是可見的。但是，在重放階段，需要搜索可確定性執行的空間，由此導致了重放階段的消耗大幅度增加，速度大尺度下降，且只能實現離線的重演。

Respec[16]支持運行在商業多核處理器上的共享內存多線程程序的確定性重演，能夠實現在線的重演，即記錄和重演可以并發執行。Respec采用兩種策略來減少開銷：可推測的日志記錄和外部重演?？赏茰y的日志記錄只存留更少的能夠確保重演的線程間交互信息，在重放時，如果重放過程偏離記錄過程，則嘗試再次重放，兩次執行必須確保執行的結果和最終的狀態達到一致。這兩種策略可以確保不包含數據競爭的程序段記錄和重放時有較低的開銷，也能夠確保帶數據競爭的程序段的正確重放。只是重放時的速度將大大地放緩。

PRES[17]本著放寬以重現錯誤為第一重演目標的思想，通過只記錄部分程序執行過程中的信息（PRES稱為“草圖”），并借助額外的診斷時間智能搜索未記錄的不確定性空間來重現錯誤。PRES降低了記錄階段的開銷，但因為在重演時搜索不確定的空間，增加了重演階段的消耗，重演的速度為之急劇降低。而且只支持離線的重演。

DoublePlay[18]提供了一種能夠確保在商業多核處理器上的重演手段，通過將線程劃分為并行的epoch，在記錄階段只記錄同步操作等少量的信息，在重演時使用這些信息指導程序實現epoch級并發執行。DoublePlay保證了帶或不帶數據競爭的程序的確定重演，但卻需要一個額外的處理器核，可擴展性不好，并且只支持離線的重演。

2.2 硬件實現的內存競爭記錄機制

針對軟件實現內存競爭記錄帶來的巨大性能開銷，對原有系統性能影響重大，而且軟件的實現速度也不具備現實可接受性，而與之相對，硬件卻只會帶來很小的、幾乎可以忽略的性能開銷。因此，研究者紛紛提出了硬件支持的內存競爭記錄器。

Goldstein[19]是第一個基于硬件的內存競爭記錄器，在基于監聽總線的多核處理器系統上實現，監聽并記錄總線上的所有事務。每次總線操作，對應指令的IC值則送往記錄器，此記錄器便為多線程記錄了一個總線操作的全序，也就是既記錄了線程間共享內存操作的偏序關系，又記錄了線程內對共享內存操作的順序。為實現這個全序記錄器，Goldstein需要添加一個內存頁狀態表、一個指令計數器表和一個日志緩存。因為內存間交互的記錄由專門硬件設計實現，對程序執行的速度影響小，但Goldstein需要追蹤每一個內存訪問，需要記錄大約50%總線操作，記錄的日志超大，內存開銷也為之加大。同時，又由于其實現是基于監聽總線的多處理器系統下，可擴展性較差。

ReEnact[20]使用線程級推測機制來記錄和重演多線程程序。每個處理器核需要添加版本cache和支持回滾能力硬件部件。每當檢測到同步操作時，結束一個chunk，而同步操作結束后，再開啟一個新的chunk。通過記錄固定數目的chunk，可以確定性地重演至發生內存競爭的位置。但ReEnact的硬件實現結構復雜，且只能實現離線的重演。

CORD[21]使用Lamport時鐘來標記內存競爭的順序，但是以cache塊為粒度，為每個cache塊添加一個時戳，并對原有的cache結構進行了修改。同時，每個處理器添加兩個寄存器用于保留下一個可用內存的物理地址以及chunk結束時對應內存的物理地址。相比ReEnact，CORD硬件實現復雜度降低，但卻犧牲了內存競爭檢測的精度。

BugNet[22]實現了用戶級的確定性重演，在記錄內存競爭時，與Recap一樣，記錄共享內存讀操作的值，但不記錄所有共享內存讀操作的值，而是只記錄第一次讀某個共享內存地址時的值。一個共享內存的值如果為外部事件所修改，其后讀取這個地址的值也將得到同樣的記錄。BugNet實現了多線程程序的重演，記錄了更小的日志，但卻同樣需要追蹤每個共享內存讀操作，因而帶來較大的性能開銷。

FDR[23]是一個硬件實現的全系統記錄器，在進行內存競爭時，記錄共享內存操作間的偏序關系，并實現了Netzer[12]提出的傳遞性約減算法，所記錄的日志格式如圖2所示。

圖2 FDR內存競爭記錄格式

Fig.2 Memory race logging style in FDR

FDR采用點到點的記錄方式記錄由沖突雙方指令IC構成的偏序關系，需要保存每個內存操作的時戳到cache中，利用原有的cache一致性協議進行內存競爭檢測。與Goldstein不同的是，FDR只記錄一致性操作中很少的一部分事件，將記錄信息添加到cache一致性部件中，大大降低了硬件資源消耗。而且，FDR是一種基于目錄cache一致性協議的分布實現方式，具有良好的可擴展性。圖3給出了FDR的硬件實現結構。FDR為系統中的每個核增加一個指令計數器，記錄本線程已執行的指令數；為每個cache行增加了一個cache指令計數器（CIC），存儲訪問這個cache行的最后一次讀指令或寫指令對應的指令計數器值。當一個處理器核收到來自其他核的針對某個cache行的遠程一致性請求時，就將此cache行對應的CIC和核ID號附加到與之相配的應答消息中。發出請求的處理器核記錄下通過由應答方送來的ID和CIC值以及請求方ID與當前的IC形成的依賴關系。為了實現傳遞性優化算法，FDR還需要為每個核增加一個向量指令計數器，追蹤每個核收到的最新的CIC。FDR實現了線程間的內存競爭的記錄，可以實現程序的快速重演，但卻因之帶來了較大的硬件資源消耗。

圖3 FDR內存競爭記錄實現結構

Fig.3 Hardware implementation in FDR

RTR[24]是FDR的改進版本，已不再記錄確切的沖突happens-before關系，而是為沖突創建一種優化的人工順序。這種人工順序能夠獲得比Netzer’TR算法性能更佳的優化，創建了更加緊湊的日志，如圖4所示。與FDR相同，RTR也需要保存內存操作的時戳。但是，RTR為了減少對原有cache的影響，采用了分離的cache結構。而且，RTR也將該內存競爭機制應用在TSO存儲模型中。雖然，RTR記錄了更小的日志，但卻因為需要為每個內存操作保存時戳，并與FDR同樣地，帶來了較大的硬件消耗。

圖4 FDR內存競爭記錄格式

Fig.4 Memory race logging style in FDR

Rerun[25]首先提出了chunk記錄方式。chunk是指程序運行時相互獨立的內存指令的集合。在chunk記錄方式下，硬件資源消耗低，由此其后很多內存競爭記錄研究成果中也都紛紛采用了chunk記錄方式。

在Rerun中，chunk可稱為episode，如圖5所示。Rerun為每個處理器核增加一個讀、寫簽名，分別用來記錄此核

圖5 Rerun中的episode

Fig.5 Episode in Rerun

當前chunk中內存塊的讀寫地址；添加一個全局的Lamport時鐘，用于標記chunk的時戳，如圖6所示。當cache收到一個遠程請求時，就查找簽名來檢測沖突。如果檢測到沖突，結束當前chunk，并且清空讀寫簽名，記錄剛才結束的chunk長度和時戳至內存競爭日志中，同時更新時戳值。處理器核則會將更新后的時戳附加到一致性協議的應答消息中，確保每個處理器核的chunk的順序。這種記錄方式大幅降低了硬件資源消耗，還在較弱的程度上壓縮了所記錄的日志，并且記錄的日志容量還有良好的可擴展性，不會隨著處理器數目的增加而成倍上升。然而，Rerun在重演時只能按照chunk時戳的大小順序進行重放，重演速度則大為降低。

圖6 Rerun內存競爭記錄實現結構

Fig.6 Hardware implementation in Rerun

與Rerun相同，DeLorean[26]也使用簽名實現內存競爭檢測，但卻只能運行在另一個不同的多處理器執行環境BulkSC[27]下。在這個環境中，處理器核不斷地執行由檢查點寄存器彼此分隔的chunk，在能提交一個chunk之前，其所對應的簽名就要同其他chunk的簽名進行比較來檢測沖突。如果一個chunk檢測到沖突，對應簽名就會清空，chunk彈回并重新執行。雖然已經證實Delorean表現良好，但由于其只能應用在一款不同的多處理器下，執行的環境并不標準，而且還需要硬件擴展，且同硬件支持的事務內存較為類似[28]，因此很難得到大范圍的應用。

文獻[29]在Rerun的基礎上實現了基于監聽總線的多核系統下chunk的記錄，而且提出了并發chunk域來提高重演速度。IMMR在一個chunk結束時，會發出廣播信息，使所有線程的chunk結束，具有相同時戳的chunk將構成并發chunk域。采用這種并發chunk域，重演時的速度可以提高幾個數量級，但卻需要記錄更大的內存競爭日志。

Timetraveler[30]通過挖掘Rerun中記錄的循環chunk，記錄了一個無循環的內存競爭日志。Timetraveler為cache一致性部件添加了一個Time-delay緩沖區，并在二級cache中添加一個過期時戳，以檢測循環的chunk。Timetraveler最大限度地減少了記錄的內存競爭日志，但卻改變了cache系統的結構，也沒有提及如何提高重演的速度。

Karma[31]對 Rerun進行了擴展，通過將chunk記錄到一個有向無循環圖DAG中來標記chunk執行的先后順序，而不再記錄Lamport時戳。在每次檢測到沖突后，Karma就在DAG中添加一個指向后續chunk的邊，這個邊由前驅chunk和后繼chunk的相關信息組成。Karma這種DAG圖的記錄方式提高了重演的并行性，加快了重演的速度，但重演的速度性相比前面介紹的點到點的記錄方式，即FDR和RTR，還有待進一步提升。

Strata[32]采用向量時鐘表示訪存操作間的happens-before關系，由于向量時間戳可以間接地表示多個happens-before關系，所以可以減少記錄信息的數目。Strata在發生一個內存沖突時，記錄一個Stratum，Stratum就將包含這一時刻的所有線程時戳。一個Stratum可以將記錄內存沖突發生前和記錄內存沖突后的內存操作做以有效區別，通過分析兩個相鄰的Stratum就可以捕獲內存沖突。采用這種記錄方式可以不用記錄讀后寫類型的沖突，減小了內存競爭日志。但若要想知道共享內存間的依賴關系究竟為如何，就需要進行離線的分析。同時，隨著處理器數目的增加，記錄的日志會增加太多，可擴展性較差[22]。

Rainbow[33]同Strata一樣，用向量時鐘表示訪存操作間的happens-before關系[7]，但其通過建立精確的happens-before關系，有效地減小了記錄信息，并采用邏輯向量時鐘描述沖突訪存操作間的happens-before關系，而與采用標量時鐘相比，則可以避免happens-before關系的誤識，同時降低重放執行過程中并行度的損失。在4核處理器上，Rainbow與Strata相對照，在記錄條數上平均減少了17%。但Rainbow的可擴展性卻同Strata一樣，均屬表現較差。

LReplay[34]提出了一種簡潔的硬件輔助機制實現確定性重演。LReplay不記錄內存交互的順序，而是記錄指令或指令塊的延遲時間信息，雖然硬件資源消耗少，記錄的日志也小，但卻只能應用于一款特殊的體系結構Godson-3[35]。

現有的絕大多數的內存競爭記錄器只考慮了順序一致性模型，RTR，Karma雖然提供了對TSO儲存模型的支持，但卻都需要修改cache子系統的結構或cache一致性協議，這將很難在商用處理器中得到圓滿實施。文獻[36]給出了一個高效、低復雜度的處理器方案，支持TSO存儲模型下的記錄和重演，記錄初始的寄存器狀態和cache未命中的數據。使用這些信息，每個線程在重演時，使用離線算法推導得出線程間共享內存的TSO兼容的因果順序。同時，這一方案也討論了限定搜索空間的方法及降低離線分析時間的優化方法。但該記錄機制只能支持離線的重演，且重演時則因為要搜索空間，重演速度也較低。

CoreRacer[37]是一個針對x86 TSO處理器核、基于chunk的內存競爭記錄器，而且不需要修改cache系統和一致性協議。通過利用一個特殊x86體系結構特征—不變的時間戳，CoreRacer無需向高速緩存一致性的消息中添加消息就可以維護chunk間的順序。CoreRacer通過記錄chunk結束時寫緩沖中等待提交的寫操作的數目來處理TSO存儲模型。另外，CoreRacer還利用所記錄的信息仿真了寫緩沖，但同文獻[33]一樣的是，只能實現離線的重演。

3 內存競爭記錄面臨的挑戰

現有軟件實現的內存競爭機制帶來了較大的性能開銷，雖然有些系統通過一系列舉措來減小記錄的開銷，如RecPlay等通過減小所需記錄的程序的范圍來降低開銷，PRES和ODR通過放松對確定性重演的定義來降低開銷，DoublePlay通過轉換工作從記錄階段到離線重演階段來降低開銷等等。但相比硬件實現，開銷仍顯巨大。而且，硬件在價格不斷下降的同時，性能卻在持續增強，因此，硬件實現的內存競爭記錄更具發展前景，同時為越發復雜的軟件系統提供內存競爭記錄的技術支持也顯得尤為必要。但硬件的實現的內存競爭記錄機制卻仍然在如下方面存在艱巨挑戰，需要正視和應對。

（1）日志大小

現在的計算機支持快速的通訊機制，內存競爭頻發，雖然FDR、RTR采用傳遞性遞減方法在一定程度上減小了內存競爭日志，但如果是長時間地運行程序，仍會造成記錄的日志過大。Timetraveler雖然努力減小了內存競爭日志，但卻帶來了一定的設計復雜度，并且其重演速度同Rerun一樣也要受限。Karma雖然可以通過調節chunk的長短來減小內存競爭日志，但這種調節又會反過來影響重演速度。而實際應用中，如果長期開啟內存競爭記錄功能，不僅會產生大量的內存競爭日志，還會消耗大量的內存，對重演速度也會發生高度影響。LReplay顯著減小了內存競爭日志，但也只能適用于特殊結果的處理器。

（2）帶寬開銷

除Delorean外，所有的內存競爭記錄器必須附加cache一致性消息來維護系統中時間的順序。例如，在FDR中，當前的指令計數值CIC就附加到cache一致性應答消息中，用以記錄不同進程兩指令間點對點的依賴關系。Rerun中的時戳則附加到每個一致性應答中，用于維護塊間的因果關系。FDR和Rerun在功能仿真中會帶來10%的帶寬開銷，并因其帶寬帶來了一定壓力而損傷了性能。其他硬件實現的內存競爭記錄機制同樣存在帶寬開銷大的弱點，而對于一直都要開啟確定性重演功能的系統來說，帶寬的消耗更是不可估量。

（3）重演性能

很多應用都能得益于確定性重演，如容錯、長時間間隔的調試等應用，因此需要開發實用技術來提高重演速度。Delorean、FDR和RTR均能以程序原始執行時的速度來重演一個程序。在Delorean中，通過并行的、而且以在原始執行過程中記錄的提交順序為依據地重新同步程序塊才得以完成重演。FDR、RTR可以并行重演，只有在原始執行過程中記錄的點到點的依賴關系處重新同步來實現重演。然而FDR、RTR和Delorean都不可能成為現實中內存競爭記錄器的實際選擇，因為FDR和RTR都需要增加較多的硬件資源，而硬件復雜度卻是當代多核處理器的一大設計難關，而Delorean的執行環境又極不標準。Rerun中按照chunk時戳增長的順序進行重演，幾乎是串行的，因此，Rerun不能滿足內存競爭記錄應用對重演速度的需求，如容錯處理。作為一個替代的重演方案，文獻[29]提出了一種稱為并發chunk域的重演策略，一定程度上提高了重演速度，但卻是在犧牲日志尺寸情況下獲得的速度提升。Karma采用DAG圖記錄chunk，脫卻了全局時鐘的限制，但其重演的速度相對點到點記錄方式仍然有待改進。而文獻[36]和CoreRacer只支持離線的重演。

（4）支持非順序存儲模型

目前提出的內存競爭記錄機制，只有很少的一部分能夠支持非SC存儲模型，這對商用處理器來說，是一大挑戰。文獻[36]和CoreRacer雖然針對TSO存儲模型，但只支持離線的重演。為了開拓內存競爭記錄的應用場合，早日進入實際應用中，就需要開展針對非SC存儲模型的內存競爭記錄機制的進一步研究。

4 結束語

隨著多核處理器的流行，共享內存多線程程序的應用也日益廣泛。然而，共享內存多線程程序在執行時卻存在著不確定性。線程在執行時內存競爭頻發，是導致多線程程序執行不確定性的主要原因。要實現共享內存多線程程序的確定性重演，最大難點就在于高效實現內存競爭的記錄及重演。本文對內存競爭記錄的國內外研究現狀進行了概括，比較和論述了現有軟件實現的內存競爭記錄機制和硬件實現的內存競爭記錄機制，指出硬件實現的內存競爭記錄更具競爭前途，并且分析了當前硬件實現的內存競爭記錄在內存競爭日志大小、帶寬開銷、重演性能及是支持非順序存儲模型4個方面存在的挑戰。

參考文獻：

[1]PERONA P， MALIK J. Scale-space and edge detection using anisotropic diffusion [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1990， 12（7）： 629-639.

[2]NETZER R H B， MILLER B P. What are race conditions？ some issues and formalizations [J]. Journal ACM Letters on Programming Languages and Systems （LOPLAS）， 1992， 1（1）： 74-88.

[3]PAN D Z， LINTON M A. Supporting reverse execution for parallel programs [C]//Proceedings of the 1988 ACM SIGPLAN/SIGOPS Workshop on Parallel and Distributed Debugging， 1988： 124-129.

[4]LEBLANC T， MELOR-CRUMMEY J. Debugging parallel programs with instant replay [J]. IEEE Transactions on Computers， 1987， 36（4）： 471-482.

[5]DUNLAP G W， LUCCHETTI D G， et al. Execution replay of multiprocessor virtual machines [C]∥ Proceeding VEE’08 Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments， 2008： 121-130.

[6]RONSSE M，De BOSSCH-ERE K . RecPlay： a fully integrated practical record/replay system [J]. ACM Transactions on Computer Systems， 1999， 17（2）： 133–152.

[7]LAMPORT L. Time， clocks and the ordering of events in a distributed system [J]. Communications of the ACM， 1978， 21（7）： 558–565.

[8]RUSSINOVICH M， COGSWELL B. Replay for concurrent non-deterministic shared-memory applications [C]// Proceedings of the ACM SIGPLAN Conference on Programming language Design and Implementation， 1996：258-266.

[9]GEORGES A， CHRISTIAENS M， et al. Jarec： a portable record/replay environment for multi-threaded java applications [J]. Software： Practice and Experience， 2004， 34（6）： 523–547.

[10]CHOI J， SRINIVASAN H. Deterministic replay of Java multithreaded applications [J]. Proceedings of the SIGMETRICS Symposium on Parallel and Distributed Tools， 1998：48-59.

[11]OLSZEWSKI M， ANSEL J， AMARASINGHE S. Kendo： efficient deterministic multithreading in software [C]//Proceedings of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems， 2009：97-108.

[12]NETZER R H B. Optimal tracing and replay for debugging shared memory parallel programs [C]// Proceedings of the ACM/ONR Workshop on Parallel and Distributed Debugging （PADD）， 1993：1-11.

[13]PATIL H， PEREIRA C， et al. PinPlay： a framework for deterministic replay and reproducible analysis of parallel programs [C]//Proceeding CGO’10 Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization， 2010：2-11.

[14]CHI-KEUNG ， COHN L R， et.al. Pin： building customized program analysis tools with dynamic instrumentation [C]//Proceeding PLDI’05 Proceedings of the ACM SIGPLAN conference on Programming language design and implementation， 2005：190-200.

[15]ALTEKAR G， STOICA I. ODR： output-deterministic replay for multicore debugging [C]//Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles， 2009：193-206.

[16]LEED， WESTER B， et.al. Respec： efficient online multiprocessor replay via speculation and external determinism [C]//Proceeding ASPLOS XV Proceedings of the fifteenth edition of ASPLOS on Architectural support for programming languages and operating systems， 2010：77-90.

[17]PARK S，ZHOU Yuanyuan， et.al. PRES： probabilistic replay with execution sketching on multiprocessors [C]//Proceeding SOSP’09 Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles， 2009：177-192.

[18]VEERARAGHVAN K， LEE Dongyoon， et al. DoublePlay： parallelizing sequential logging and replay [C]//Proceeding ASPLOS XVI Proceedings of the sixteenth international conference on Architectural support for programming languages and operating systems， 2011：15-26.

[19]BACON D F， GOLDSTEIN S C. Hardware-assisted replay of multiprocessor programs [C]//Proceedings of the ACM/ONR Workshop on Parallel and Distributed Debugging， published in ACM SIGPLAN Notices， 1991：194-206.

[20]PRULOVIC M， TORRELLAS J. ReEnact： using thread-level speculation mechanisms to debug data races in multithreaded codes [C]//Proceedings of the 30th annual international symposium on Computer architecture， May 2003， 31（2）： 110-121.

[21]PRVULOVIC M， et al. CORD： cost-effective （and nearly overhead-free） order recording and data race detection [C]//Proceeding of the 12th IEEE symposium on high-performance computer architecture. Feb 2006， 232-243.

[22]NARAYNASAMY S， POKAM G， CALDER B. BugNet： recording application level execution for deterministic replay debugging [J]. Micro， IEEE， 2006， 26（1）： 100-109.

[23]XU M， BODIK R， HILL M. A flight data recorder for enabling full-system multiprocessor deterministic replay [C]//Proceedings of the International Symposium on Computer Architecture， 2003：122-135.

[24]XU M， BOD’IK R， HILL M D. A regulated transitive reduction （RTR） for longer memory race recording [C]//Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems， 2006：49-60.

[25]HOWER D， HILL M. Rerun： exploiting episodes for lightweight memory race recording [C]//Proceedings of the International Symposium on Computer Architecture， 2008：265-276.

[26]MONTESINOS P， CEZE L， TORRELLAS J. DeLorean： recording and deterministically replaying shared-memory multiprocessor execution efficiently [C]//Proceedings of the International Symposium on Computer Architecture， 2008：289-300.

[27]CEZE L， TUCK J， MONTESINOS P， et al. BulkSC： bulk enforcement of sequential consistency [C]∥ Proc. of the 34th Annual Intnl. Symp. on Computer Architecture， 2007-06： 278-289.

[28]LARUS J， RAJWAR R. Transactional Memory[M]. Morgan Claypool， 2006.

[29]POKAM G， PEREIRA C， DANNE K， et al . Architecting a chunk-based memory race recorder in modern CMPs [C]//Proceedings of the International Symposium on Microarchitecture， 2009：576-585.

[30]VOSKUILEN G ， AHMAD F， VIJAYKUMAR T N. Timetraveler： exploiting acyclic races for optimizing memory race recording [C]//Proceedings of the 37th annual international symposium on computer architecture. Jun 2010：198-209.

[31]BASU A， BOBBA J， HILL M D. Karma： scalable deterministic record-replay， University of Wisconsin Computer Sciences technical report CS-TR-2010-1680， Oct. 2010.

[32]NARAYANASAMY S， PEREIRA C， CALDER B. Recording shared memory dependencies using strata [C]//Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems， 2006： 229-240.

[33]劉磊， 黃河， 唐志敏. 支持多核并行程序確定性重放的高效訪存沖突記錄方法[J]. 計算機研究與發展， 2012， 49（1）： 64-75.

[34]CHEN Yunji， HU Weiwu， WU Ruiyang. LReplay： a pending period based deterministic replay scheme [C]//Proceeding ISCA’10 Proceedings of the 37th annual international symposium on Computer architecture， 2010： 187-197.

[35]GAO X， CHEN YJ， WANG HD. System architecture of godson-3 multi-core processors [J]. Journal of computer science and technology， 2010， 25（2）： 181–191.

[36]LEEY D， SAIDZ M， NARAYANASAMYY S， YANGZ Z. Offine symbolic analysis to infer total store order [C]∥ High Performance Computer Architecture （HPCA）， 2011 IEEE 17th International Symposium on Date of Conference， 2011：357- 358.

[37]POKAM G， PEREIRA C， et al. CoreRacer： a practical memory race recorder for multicore x86 TSO processors [C]//Proceeding MICRO-44’11 Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture， 2011： 216-225.