馮雅妮，蔣 林，山 蕊，劉 陽，張 園

1.西安郵電大學(xué)電子工程學(xué)院，西安710121

2.西安科技大學(xué)集成電路實驗室，西安710054

3.西安郵電大學(xué)計算機學(xué)院，西安710121

1 引言

隨著半導(dǎo)體工藝的飛速發(fā)展，單個芯片能夠集成更多的處理器核，一定程度上可以提升陣列處理器計算能力，但是核數(shù)的增多使得“存儲墻[1-2]”問題日益突出。同時，面向超高清視頻編解碼等計算密集型應(yīng)用時[3]，處理器需進行大量的并行計算，因此數(shù)據(jù)的吞吐量成為了影響系統(tǒng)性能提升的瓶頸。

為了緩解陣列處理器中日益嚴重的“存儲墻”問題，通常在片上集成大容量的Cache以實現(xiàn)數(shù)據(jù)共享和信息交互，從而減小訪問延遲[4]。共享Cache容量大、失效率低，且一致性維護開銷小，但在訪問沖突情況下，訪問延遲較大；私有Cache在本地命中情況下訪問延遲低，具有較高的并行度，但一致性維護開銷較大，且可能出現(xiàn)負載不均衡現(xiàn)象，導(dǎo)致Cache整體有效空間減少[5-6]。目前研究人員大多采用多級Cache技術(shù)，以減少訪問延遲并提高訪問帶寬[7-8]。多級Cache具有層次化的存儲結(jié)構(gòu)，其一致性維護增加了電路的復(fù)雜度及功耗。為了降低訪問延遲并且提高訪問的并行度，面向陣列處理器設(shè)計的分布式共享存儲結(jié)構(gòu)采用統(tǒng)一編址方式，從邏輯上提供了一個片上大容量存儲資源，并采用軟硬件協(xié)同技術(shù)，實現(xiàn)了片上存儲資源的高效利用[9]。針對片上互連結(jié)構(gòu)中訪問延遲的不均衡特性，Kim等人首次提出了非一致Cache體系結(jié)構(gòu)（non-uniform Cache architecture，NUCA）[10]的概念。Huang等人提出了自適應(yīng)動態(tài)非一致性訪問（pressure self-adapting dynamic non-uniform Cache assess，PSA-NUCA）機制[11]，研究了存儲訪問的不對稱分布特征和非一致性訪問延遲結(jié)構(gòu)，可有效緩解失效率和實際命中延遲之間的矛盾。為了充分發(fā)揮NUCA在多核系統(tǒng)下的性能優(yōu)勢，可以根據(jù)提前預(yù)測的關(guān)鍵路徑信息對Cache中的數(shù)據(jù)進行遷移[12]。但是，關(guān)鍵路徑只能提前預(yù)測而不能實時響應(yīng)，因此基于關(guān)鍵路徑預(yù)測進行數(shù)據(jù)遷移并不適用于陣列處理器這種數(shù)據(jù)量級訪問的系統(tǒng)。

為了緩解陣列處理器中遠程訪問情況下分布式存儲結(jié)構(gòu)存在的長延遲問題，論文基于分布式Cache結(jié)構(gòu)設(shè)計了一種改進的數(shù)據(jù)Cache實時動態(tài)遷移機制，以一段時間內(nèi)遠程Cache中數(shù)據(jù)塊的訪問頻率為依據(jù)，通過四級全互連和遷移互連，對遠程數(shù)據(jù)進行動態(tài)調(diào)度。本文的貢獻如下：

（1）設(shè)計實時動態(tài)遷移機制，基于分布式Cache結(jié)構(gòu)對頻繁訪問的遠程數(shù)據(jù)進行動態(tài)調(diào)度；

（2）設(shè)計遷移互連，在保證數(shù)據(jù)一致性的前提下，建立遷移與取消遷移鏈路，同時確保陣列處理器對已遷移數(shù)據(jù)的正確訪問；

（3）采用運動補償算法對所提出的動態(tài)遷移機制進行驗證，并分析訪存性能。

2 陣列處理器分布式Cache結(jié)構(gòu)

Fig.1 Dstributed Cache structure of array processor圖1 陣列處理器分布式Cache結(jié)構(gòu)

陣列處理器的簇內(nèi)分布式Cache結(jié)構(gòu)如圖1所示。陣列處理器中處理元簇（processing element group，PEG）由4×4個處理元（process element，PE）以陣列的形式組成。陣列結(jié)構(gòu)中每個PE各具有一個本地Cache從而構(gòu)成分布式Cache結(jié)構(gòu)，每個PE對本地Cache和遠程Cache都具有讀寫訪問權(quán)限。當(dāng)PE發(fā)出訪問請求時，根據(jù)PE發(fā)出的訪問信息，通過四級全互連對訪問的目的Cache進行索引，進而對相應(yīng)的Cache進行訪問。若訪問命中，則直接對分布式Cache中的數(shù)據(jù)進行訪問；若訪問不命中，則通過仲裁器仲裁出一路訪問請求去訪問主存，將目的數(shù)據(jù)塊從主存搬移到Cache中，再將目的數(shù)據(jù)返回給PE。

當(dāng)Cache接收PE發(fā)送的訪問請求時，Cache內(nèi)部首先通過比較訪問請求中的標(biāo)志信息與該Cache的標(biāo)志信息，并結(jié)合Cache當(dāng)前的狀態(tài)信息判斷本次訪問是否命中。為保證Cache與主存間的數(shù)據(jù)一致性，訪問不命中且Cache內(nèi)無空閑行時，采用最近最少用算法（least recently used，LRU）對Cache行數(shù)據(jù)進行替換，同時向數(shù)據(jù)存儲單元發(fā)送臟與不臟時的控制信息，若替換行臟，還需遵循寫回策略將臟的替換行數(shù)據(jù)寫回主存。

在陣列處理器的大規(guī)模數(shù)據(jù)訪問過程中，若簇內(nèi)的PE訪問16個Cache的概率相當(dāng)，則PE訪問本地Cache的概率僅為6.25%，并且本地Cache容量有限。由此可見，遠程訪問是整個系統(tǒng)訪存操作的重要組成部分。在分布式Cache中，PE頻繁訪問遠程Cache中數(shù)據(jù)將帶來較大的訪問延遲。因此，為了緩解頻繁的遠程訪問帶來的長延遲問題，本文提出了一種改進的基于分布式數(shù)據(jù)Cache的實時動態(tài)遷移機制，通過動態(tài)和靜態(tài)相結(jié)合的地址映射方式降低遠程訪問延遲。

3 數(shù)據(jù)Cache實時動態(tài)遷移機制

論文設(shè)計的改進的數(shù)據(jù)Cache實時動態(tài)遷移機制，在遠程訪問情況下，根據(jù)數(shù)據(jù)訪問的局部性，并以PE在一段時間內(nèi)訪問遠程數(shù)據(jù)Cache的頻率為主要遷移依據(jù)對遠程數(shù)據(jù)進行動態(tài)調(diào)度，將頻繁訪問的遠程Cache行數(shù)據(jù)遷移到距離該PE最近的存儲單元中，從而降低遠程訪問延遲。

3.1 分布式Cache實時動態(tài)遷移結(jié)構(gòu)

Fig.2 Real-time dynamic migration structure of distributed Cache圖2 分布式Cache實時動態(tài)遷移結(jié)構(gòu)

分布式Cache實時動態(tài)遷移結(jié)構(gòu)主要由遷移查找表（Find）、四級全互連、數(shù)據(jù)Cache、訪問記錄表（Record）、遷移輸出單元（Output）及遷移互連六部分組成，如圖2所示。遷移查找表是距離PE最近的本地存儲單元；PE通過四級全互連準確地訪問目的Cache；訪問記錄表統(tǒng)計Cache行被PE訪問的頻率；當(dāng)PE在一段時間內(nèi)訪問某遠程Cache行中的數(shù)據(jù)的頻率達到遷移閾值時，遷移輸出單元輸出該遠程Cache行，并通過遷移互連遷移這個頻繁訪問的Cache行數(shù)據(jù)到該PE本地的遷移查找表中。其中，一段時間由總訪問次數(shù)確定，當(dāng)訪問次數(shù)達M次，當(dāng)前時間段結(jié)束，進入下一時間段，同時訪問次數(shù)重新計數(shù)。當(dāng)該PE再次訪問已遷移的數(shù)據(jù)時，只需一個時鐘周期就可在本地的遷移查找表中完成訪問。

在采用實時動態(tài)遷移機制的分布式Cache中，PE發(fā)出訪問請求后，并不直接訪問Cache，而是首先根據(jù)訪問信息訪問本地遷移查找表，在遷移查找表中命中時，直接完成訪問；在遷移查找表不命中時，才通過四級全互連訪問Cache。目的Cache在響應(yīng)訪問請求的同時，對應(yīng)的訪問記錄表實時記錄目的Cache行在一段時間內(nèi)被陣列內(nèi)的16個PE訪問的頻率。

根據(jù)Cache中遷移記錄表統(tǒng)計的PE訪問該Cache中數(shù)據(jù)塊的頻率，可將數(shù)據(jù)塊的狀態(tài)劃分為頻繁訪問和非頻繁訪問兩種。在一段時間內(nèi)，如果數(shù)據(jù)塊被訪問頻率小于遷移閾值B，則此數(shù)據(jù)塊處于非頻繁訪問狀態(tài)；如果數(shù)據(jù)塊被訪問頻率達到遷移閾值B，則此數(shù)據(jù)塊處于頻繁訪問狀態(tài)。

為了降低分布式Cache在遠程訪問下的訪問延遲，采用實時動態(tài)遷移機制，動態(tài)調(diào)度處于頻繁訪問狀態(tài)的數(shù)據(jù)塊。遠程Cache根據(jù)遷移記錄表得到PEi頻繁訪問的Cache行信息，并輸出該Cache行數(shù)據(jù)到遷移輸出單元，通過遷移互連最終寫入PEi本地的遷移查找表中。遷移后PEi僅需一個時鐘周期直接在本地遷移查找表中完成訪問，無需再訪問遠程Cache。對于已經(jīng)遷移到本地遷移查找表的Cache行數(shù)據(jù)，如果在一段時間內(nèi)不再被PEi頻繁訪問，則該數(shù)據(jù)塊處于非頻繁訪問狀態(tài)，需建立取消遷移鏈路，通過遷移互連把該數(shù)據(jù)塊中的臟數(shù)據(jù)遷回原靜態(tài)映射位置對應(yīng)的遠程Cache中，并將取消遷移操作完成的反饋信號返回到本地的遷移查找表，以便下一個頻繁訪問的數(shù)據(jù)塊可正常遷入。動態(tài)遷移數(shù)據(jù)通路如圖3所示，其中虛線框內(nèi)表示數(shù)據(jù)塊動態(tài)遷移過程。

3.2 遷移互連

遷移互連由mig_connect和find_ca_connect兩部分組成。其中，mig_connect的主要功能是建立遷移與取消遷移鏈路。

（1）遷移鏈路：PEi對應(yīng)的mig_connect_i接收來自15個遠程遷移輸出單元的遷移使能及Cache行，并采用最遠優(yōu)先響應(yīng)的原則仲裁出一路遠程Cache行及對應(yīng)的地址信息，發(fā)至PEi的本地遷移查找表中，遷移查找表接收完遠程Cache行數(shù)據(jù)后，結(jié)合其對應(yīng)的地址信息，將遷移完成的反饋信號通過mig_connect_i返回給該遠程Cache行遷移前的靜態(tài)映射位置，完成遷移鏈路。遠程Cache接收到遷移完成的反饋信號后，將對應(yīng)Cache行的狀態(tài)更新為已遷移，同時訪問記錄單元不再對該Cache行的訪問頻率計數(shù)。

（2）取消遷移鏈路：PEi本地的遷移查找表中的遠程數(shù)據(jù)塊不再被頻繁訪問時，遷移查找表發(fā)出取消遷移使能，通過mig_connect_i通知對應(yīng)的遠程Cache將該Cache行狀態(tài)更新為未遷移，對應(yīng)的訪問記錄單元對該Cache行的訪問頻率重新開始計數(shù)，同時該遠程Cache通過mig_connect_i返回取消遷移操作完成的反饋信號，遷移查找表收到該反饋信號后，更新表內(nèi)訪問計數(shù)器為0，數(shù)據(jù)區(qū)無效，數(shù)據(jù)區(qū)臟位為0。

Fig.3 Dynamically scheduled data path圖3 動態(tài)調(diào)度數(shù)據(jù)通路

find_ca_connect的主要功能是確保PE可正確訪問已遷移的Cache行數(shù)據(jù)，包括以下兩種情況：

（1）PEi頻繁訪問某遠程Cache行，且遷移操作未完成時已將訪問請求發(fā)送至該遠程Cache行的原靜態(tài)映射位置。當(dāng)遠程命中訪問達B次時，遷移該遠程Cache行到本地的遷移查找表中，同時將遠程Cache對應(yīng)的數(shù)據(jù)行狀態(tài)更新為已遷移狀態(tài)，已發(fā)送至該遠程Cache行的原靜態(tài)映射位置的第B+1次命中訪問請求在等待遷移操作完成后，轉(zhuǎn)發(fā)至find_ca_connect_i，經(jīng)過仲裁后傳到PEi的遷移查找表完成響應(yīng)，并通過find_ca_connect_i將響應(yīng)完成的反饋信號返回給遠程Cache，最終由遠程Cache反饋給PEi完成訪問。

（2）其他遠程PE訪問已遷移的Cache行。當(dāng)某遠程Cache行已遷移至PEi的遷移查找表且有效時，其遠程Cache內(nèi)對應(yīng)的數(shù)據(jù)行狀態(tài)已更新為已遷移狀態(tài)，此時若PEj也發(fā)出訪問該Cache行的請求，首先訪問該Cache行的靜態(tài)映射地址，由于目的Cache行狀態(tài)為已遷移，該Cache接收來自PEj的訪問請求后，根據(jù)遷移輸出單元的地址信息，將訪問請求轉(zhuǎn)發(fā)至find_ca_connect_i，經(jīng)過仲裁后傳到PEi的遷移查找表完成響應(yīng)，并通過find_ca_connect_i將響應(yīng)完成的反饋信號返回給遠程Cache，最終由遠程Cache反饋給PEj完成訪問。

3.3 動態(tài)遷移閾值B

在本文提出的數(shù)據(jù)Cache實時動態(tài)遷移機制中，主要的遷移依據(jù)為PE在一段時間內(nèi)對一個遠程數(shù)據(jù)Cache的訪問次數(shù)，并采用記錄表的形式記錄PE訪問遠程數(shù)據(jù)的頻率。當(dāng)PEi訪問遠程Cache中的某行數(shù)據(jù)時，記錄本次訪問的計數(shù)器加1。統(tǒng)計一段時間內(nèi)，遷移記錄表中各PE訪問遠程Cache行數(shù)據(jù)的頻率，如果PEi在一段時間內(nèi)訪問遠程Cache行數(shù)據(jù)達到遷移閾值B次，即PEi在這段時間內(nèi)頻繁訪問該遠程Cache行數(shù)據(jù)，則遷移該Cache行到PEi的本地遷移查找表中。在遷移之后的每次訪問中，PEi每次僅需一個時鐘周期就可得到遠程數(shù)據(jù)，而無需消耗較多延遲通過訪問遠程Cache獲取。因此，當(dāng)分布式Cache遠程訪問延遲很大時，可以采用實時動態(tài)遷移機制來降低訪問延遲。針對遷移閾值B，本文構(gòu)建了一種數(shù)學(xué)模型，計算公式如下：

其中，不等式左邊代表未采用遷移機制的分布式Cache在一段時間內(nèi)對一個遠程Cache行進行M次訪問的總延遲，遠程訪問情況下首次不命中訪問平均需24個時鐘周期，命中訪問平均需5個時鐘周期。不等式右邊表示基于動態(tài)遷移機制的分布式Cache在一段時間內(nèi)對一個遠程Cache行進行M次訪問的總延遲，基于遷移機制的分布式Cache首次不命中訪問遠程Cache行平均需26個時鐘周期，遷移機制啟動前，命中訪問平均需7個時鐘周期。當(dāng)遠程命中訪問達B次時，啟動遷移機制，遷移該Cache行到本地的遷移查找表中，遷移后需通過遷移互連經(jīng)歷5個時鐘周期完成第B+1次命中訪問，之后的命中訪問僅需1個時鐘周期。在本文中，Cache從產(chǎn)生遷移使能到接收遷移查找表返回的遷移操作完成的反饋信號共需19個時鐘周期，因此，遷移代價S=19，代入上述公式可得式（2）：

由式（2）可知，遷移閾值B的選取與一段時間內(nèi)的訪問次數(shù)M有關(guān)。隨著M增大，B可變范圍逐漸增大，并且盡早采用實時動態(tài)遷移機制，整體性能提升越明顯。當(dāng)遷移閾值B選取過大時，實時動態(tài)遷移機制的啟用要求過高，使得性能的提升受到限制；當(dāng)遷移閾值B選取過小時，實時動態(tài)遷移機制啟用過早，可能存在后期訪問頻率更大的遠程Cache行來不及被遷移的情況，同時還可能造成遷移和取消遷移操作的頻繁發(fā)生，增大了遷移代價，削弱了遷移優(yōu)勢。因此遷移閾值B的選取與實際訪問頻率和訪問順序有關(guān)。

3.4 遷移取消方法

采用實時動態(tài)遷移機制的分布式Cache，將一段時間內(nèi)頻繁訪問的遠程Cache行數(shù)據(jù)遷移到距離PE最近的本地的遷移查找表中，降低訪問延遲。但由于遷移查找表容量較小，為了進一步降低訪問延遲，當(dāng)遷移查找表中已經(jīng)遷移的Cache行不再被頻繁訪問時，建立取消遷移鏈路，將遷移查找表中已經(jīng)遷移的Cache行置為無效，以便于下一個頻繁訪問的Cache行遷入。根據(jù)取消遷移的數(shù)據(jù)行的狀態(tài)，可分為以下兩種情況執(zhí)行取消遷移操作。

（1）當(dāng)遷移查找表中需取消遷移的數(shù)據(jù)行臟位為0時，將遷移查找表中的數(shù)據(jù)行置為無效，并輸出遷移取消使能，通知訪問記錄單元對原Cache中靜態(tài)映射位置的Cache行正常計數(shù)，完成取消遷移操作。

（2）當(dāng)遷移查找表需取消遷移的數(shù)據(jù)行臟位為1時，不僅置遷移查找表中的遠程數(shù)據(jù)行為無效，還需寫回遷移查找表中的臟數(shù)據(jù)行至遠程Cache行的原靜態(tài)映射位置，更新臟位為0，完成取消遷移操作。

因此一個PE頻繁訪問并遷移N個不同的遠程Cache行數(shù)據(jù)的執(zhí)行時間如式（3）所示：

其中，假設(shè)平均訪問每個遠程Cache行n次，一個PE的N次遷移操作必然產(chǎn)生N-1次取消遷移操作。在本文中，當(dāng)臟位為0時，遷移查找表輸出遷移取消使能到收到取消遷移完成的反饋信號需4個時鐘周期，因此取消遷移代價Q=4；當(dāng)臟位為1時，從產(chǎn)生寫回臟數(shù)據(jù)行的使能到整個取消遷移操作完成需19個時鐘周期，因此取消遷移的代價Q=19。

3.5 遷移一致性策略

PE發(fā)出遠程訪問請求時，首先在本地的遷移查找表中判斷此次訪問是否命中，若命中則直接在遷移查找表中對數(shù)據(jù)進行操作，無需訪問遠程Cache。因此，為保證分布式Cache與遷移查找表的數(shù)據(jù)一致性，基于實時動態(tài)遷移機制的數(shù)據(jù)訪問需：

（1）遷移過程中，陣列處理器中的所有PE不能訪問正在遷移的Cache行數(shù)據(jù)，直到遷移完成；遷移操作完成后，如果PE發(fā)出訪問請求并在本地的遷移查找表中命中時，若為讀訪問，則遷移查找表數(shù)據(jù)行臟位保持；若為寫訪問，則更新遷移查找表數(shù)據(jù)行臟位為1。

（2）取消遷移過程中，除了將已遷移的Cache行置為無效之外，為保證一致性，需把遷移查找表中的臟數(shù)據(jù)行寫回原Cache中的靜態(tài)映射位置，并更新臟位為0。與遷移操作相同，為保證其他PE能夠正確取數(shù)，在取消遷移過程中，其他PE不能訪問正在執(zhí)行取消遷移操作的Cache行，直到取消遷移完成，即遷移查找表中所有臟數(shù)據(jù)均被寫回原靜態(tài)映射位置。

（3）若某遠程Cache行數(shù)據(jù)已遷移至PEi的遷移查找表且有效，PEj也發(fā)出訪問該Cache行的請求，為保證PEj能正確地取得最新數(shù)據(jù)，PEj通過遷移互連至PEi的本地的遷移查找表中訪問該Cache行的最新數(shù)據(jù)。

4 基于FPGA的硬件測試與性能分析

4.1 FPGA硬件測試平臺

本文提出的數(shù)據(jù)Cache實時動態(tài)遷移機制以陣列處理器為硬件驗證平臺，其中陣列處理器簇內(nèi)16個PE通過二維mesh結(jié)構(gòu)的四級全互連完成4×4個分布式L1級Cache的數(shù)據(jù)通信。通過編寫典型訪問情況下的測試激勵，使用QuestaSim對基于實時動態(tài)遷移機制的分布式Cache進行功能仿真后，與陣列處理器和Xilinx定制存儲器IP互連，通過Xilinx的Zynq系列xc7z045-2-ffg900開發(fā)板進行硬件測試，具體參數(shù)如表1所示。

Table 1 Structural parameters of distributed Cache using migration mechanism表1 采用遷移機制的分布式Cache結(jié)構(gòu)參數(shù)

通過Xilinx ISE對設(shè)計進行綜合，綜合結(jié)果如表2所示。

Table 2 FPGA synthesis result表2 FPGA綜合結(jié)果

4.2 算法映射與功能驗證

Fig.4 Functional simulation of real-time dynamic migration mechanism of data Cache圖4 數(shù)據(jù)Cache實時動態(tài)遷移機制功能仿真

本文基于簇內(nèi)分布式Cache結(jié)構(gòu)，采用改進的數(shù)據(jù)Cache實時動態(tài)遷移機制，在PE遠程訪問次數(shù)大于遷移閾值B的情況下，功能仿真結(jié)果如圖4所示。當(dāng)PE訪問某遠程數(shù)據(jù)塊（mig_tag_tmp[11:0]）達到遷移閾值B時，將該頻繁訪問的遠程數(shù)據(jù)塊遷移到本地的遷移查找表中，遷移后僅需一個時鐘周期就可完成訪問。遷移后的遠程數(shù)據(jù)塊不再被該PE頻繁訪問時（mig_tag_tmp[17:13]<遷移閾值B），建立取消遷移鏈路（mig_cancel_en置1），將該遠程數(shù)據(jù)塊遷回對應(yīng)的遠程Cache（mig_tag_tmp[11:0]），并將該遷移查找表置為無效（mig_tag_tmp[12]置0）。一段時間后該PE將遷移下一個頻繁訪問的遠程數(shù)據(jù)塊（mig_tag_tmp[11:0]），并將遷移查找表置為有效（mig_tag_tmp[12]置1）。

為進一步驗證改進的數(shù)據(jù)Cache實時動態(tài)遷移機制的正確性和可行性，本文將分布式Cache與陣列處理器平臺互連，并在該平臺上映射運動補償算法?；陉嚵刑幚砥鞯倪\動補償算法如下所示。

算法1Motion compensation

圖5統(tǒng)計了不同參數(shù)下，8×8運動補償算法的執(zhí)行時間。為了靈活、高效地表示視頻場景中的不同紋理細節(jié)、運動變化的視頻內(nèi)容或者視頻對象，HEVC（high efficiency video coding）將圖像劃分成不同尺寸的編碼塊[13]。運動補償算法以8×8的編碼塊通過遠程訪問讀取參考像素值，與原始像素值進行殘差操作，并將結(jié)果輸出至遠程存儲中。因此，一段時間內(nèi)訪問次數(shù)M取15時，算法執(zhí)行時間最短。動態(tài)遷移閾值B選取較小，可較早地啟用實時動態(tài)遷移機制，有效減少算法的執(zhí)行時間，但過早地執(zhí)行遷移操作可能引起頻繁的遷移及取消遷移，增大遷移代價，削弱遷移優(yōu)勢。

Fig.5 8×8 motion compensation algorithm execution time statistics圖5 8×8運動補償算法執(zhí)行時間統(tǒng)計

4.3 訪存性能分析

在可重構(gòu)陣列處理器的分布式Cache結(jié)構(gòu)下，采用改進的實時動態(tài)遷移機制的分布式Cache比未采用該機制的分布式Cache訪問延遲平均多2個時鐘周期，但遷移機制啟動后，平均每次遠程命中訪問僅需1個時鐘周期，遠程命中訪問時間平均降低了80%。

由表達式（2）可知，遷移閾值B的選取與一段時間內(nèi)的訪問次數(shù)M有關(guān)。圖6（為了更清楚地顯示延遲降低率的變化曲線，在圖中將延遲降低率擴大3倍表示）統(tǒng)計了在遷移閾值B一定，訪問次數(shù)M變化的情況下，兩種訪問機制對同一個遠程Cache塊的總訪問延遲的變化情況。其中，M次訪問均為讀訪問，分布式Cache讀不命中訪問需25個時鐘周期，讀命中訪問需7個時鐘周期，實時動態(tài)遷移機制下讀不命中訪問需27個時鐘周期，命中訪問需9個時鐘周期。根據(jù)表達式（1）左側(cè)可知，分布式Cache總訪問延遲周期數(shù)為25+7×(M-1)，根據(jù)表達式（1）右側(cè)可知，遷移機制下總訪問延遲周期數(shù)為27+9×B+5+(M-2-B)+S，此時遷移閾值B取2，遷移代價S=19。分析可知，隨著訪問次數(shù)M的增大，相比未采用實時動態(tài)遷移機制的分布式Cache，采用該機制的分布式Cache在相同訪問頻率下，延遲降低率逐漸增大，整體性能提升越大，采用實時動態(tài)遷移機制優(yōu)勢越明顯。

Fig.6 Statistics of total access delay with parameter M圖6 總訪問延遲隨參數(shù)M 變化統(tǒng)計

由表達式（2）可知，隨著訪問次數(shù)M的增大，遷移閾值B的取值范圍也增大，但訪問同一遠程數(shù)據(jù)塊時，在訪問次數(shù)M一定的情況下，遷移閾值B增大，總訪問延遲與未采用動態(tài)遷移機制的分布式Cache訪問延遲相比，延遲降低率逐漸減小，如圖7所示。此時M取20，未采用實時動態(tài)遷移機制的分布式Cache總訪問延遲為120個時鐘周期。當(dāng)遷移閾值B選取過大時，實時動態(tài)遷移機制的啟用要求過高，使得性能的提升受到限制。因此，在一段時間內(nèi)頻繁訪問一個遠程數(shù)據(jù)塊時，盡早啟用動態(tài)遷移機制，性能提升越明顯。

Fig.7 Statistics of total access delay with migration threshold B圖7 總訪問延遲隨遷移閾值B 變化統(tǒng)計

當(dāng)一段時間內(nèi)訪問多個遠程Cache時，訪問順序及遷移閾值B的選取影響遷移鏈路與取消遷移鏈路的建立與撤銷，進而影響總訪問延遲。選取4個之前沒有被訪問過的遠程Cache行R1、R2、R3、R4，分別進行40次讀寫訪問，未采用動態(tài)遷移機制的分布式Cache的40次讀操作總訪問延遲為352個時鐘周期，寫操作總訪問延遲為240個時鐘周期。本文在采用動態(tài)遷移機制的基礎(chǔ)上，進一步優(yōu)化了訪存順序以降低訪存延遲，優(yōu)化前后讀、寫操作總訪問延遲統(tǒng)計分別如圖8、圖9所示。取M=20，前20次訪問為時間段1，后20次訪問為時間段2。

Fig.8 Statistics of total access latency of read operations before and after optimization圖8 優(yōu)化前后讀操作總訪問延遲統(tǒng)計

Fig.9 Statistics of total access latency of write operations before and after optimization圖9 優(yōu)化前后寫操作總訪問延遲統(tǒng)計

（1）優(yōu)化前的訪問順序為時間段1內(nèi)R1、R2分別訪問1次，R3訪問5次，R4訪問13次，時間段2內(nèi)的20次訪問均訪問R4。與未采用遷移機制的分布式Cache相比，讀、寫操作總訪問延遲分別降低達32.10%和15.00%。

（2）優(yōu)化1的訪問順序為時間段1內(nèi)R1、R2分別訪問1次，R4訪問13次，R3訪問5次，時間段2內(nèi)訪問順序不變，這種訪問順序可使最被頻繁訪問的遠程Cache行R4最先被遷移，不必等R3被取消遷移后在時間段2內(nèi)才被遷移。與優(yōu)化前相比，避免了多次遷移及遷移取消操作帶來的訪存開銷，與未采用遷移機制的分布式Cache相比，讀、寫操作總訪問延遲分別降低達38.92%和21.25%。

（3）優(yōu)化2的訪問順序為時間段1內(nèi)R1訪問1次，R4訪問13次，R3訪問5次，其中第B次和第B+1次命中訪問R4之間訪問1次R2，時間段2內(nèi)訪問順序不變，由于遷移R4與訪問R2并不沖突，與優(yōu)化1相比，遷移R4的代價被覆蓋，進一步降低了總訪問延遲。與未采用遷移機制的分布式Cache相比，讀、寫操作總訪問延遲分別降低達45.45%和30.83%。

表3分析了優(yōu)化前讀訪問延遲變化，當(dāng)B取2時，遠程Cache行R3在時間段1內(nèi)首先達到遷移閾值，但R3遷移時，第B+1次命中訪問請求已到達R3原靜態(tài)映射的遠程Cache，此時通過遷移互連將訪問請求發(fā)送至本地遷移查找表中響應(yīng)，之后遷移后的R3僅被本地PE直接訪問1次，不再被頻繁訪問，因此在時間段1結(jié)束時，遷移取消R3，因取消遷移的數(shù)據(jù)塊不臟，無需寫回，故取消遷移代價為4。但由于遷移取消R3與訪問R4不沖突，因此取消遷移的代價被覆蓋。在時間段2內(nèi)R4重新計數(shù)達到遷移閾值，遷移后每次訪問僅需1個時鐘周期；當(dāng)B取3時，與B取2情況類似，第B+1次命中訪問請求通過遷移互連響應(yīng)，之后R3不再被本地PE直接訪問；當(dāng)B取4時，完成R3遷移，但遷移后的R3不再以任何方式被訪問，并且因為遷移R3與訪問R4不沖突，所以遷移R3的代價被覆蓋；當(dāng)B取5時，R4在時間段1內(nèi)已達到遷移閾值，且遷移后被頻繁訪問，因此在時間段1結(jié)束后不執(zhí)行取消遷移，在時間段2內(nèi)PE仍可直接從本地的遷移查找表中訪問R4；B取6、7時，與B取5情況類似，僅較晚啟動遷移機制。

Table 3 Analysis of changes in read access latency before optimization表3 優(yōu)化前讀訪問延遲變化分析

表4分析了優(yōu)化前寫訪問延遲變化，與優(yōu)化前讀訪問延遲變化類似，區(qū)別在于當(dāng)B取2、3時，對已遷移的R3執(zhí)行了寫操作，R3成臟數(shù)據(jù)塊，在取消遷移時，需寫回至原靜態(tài)映射位置，統(tǒng)計得取消遷移操作需19個時鐘周期，由于遷移取消R3與訪問R4不沖突，但下一次訪問R4時需等待遷移取消操作完成，因此遷移取消R3的代價與一次寫訪問R4的訪問延遲重疊，因此看起來遷移代價減少為13個時鐘周期。當(dāng)B取4時，遷移后的R3不再以任何方式被訪問，因此遷移取消時無需寫回R3的數(shù)據(jù)。

Table 4 Analysis of changes in write access latency before optimization表4 優(yōu)化前寫訪問延遲變化分析

文獻[14]提出了自適應(yīng)選擇性復(fù)制（adaptive selective replication，ASR），通過動態(tài)監(jiān)視工作負載，選擇性復(fù)制數(shù)據(jù)，減少緩存訪問時間。文獻[15]設(shè)計的多層次分布式存儲結(jié)構(gòu)由私有存儲層和共享存儲層兩層結(jié)構(gòu)組成，并基于目錄協(xié)議的Cache一致性策略進行通信。兩種存儲結(jié)構(gòu)下的遠程Cache訪問延遲如表5所示。文獻[16]通過實現(xiàn)L1 Cache的偽隨機替換策略來提高系統(tǒng)訪存的整體性能，在此機制下進行FPGA實現(xiàn)最高可達160 MHz的工作頻率。文獻[17]設(shè)計的遷移機制僅遷移一個頻繁訪問的遠程數(shù)據(jù)，電路工作頻率較高，但訪存位寬較小，程序訪問局部性不高。本文與文獻[16]、文獻[17]性能對比結(jié)果如表6所示。

Table 5 Comparison of average remote access delay表5 平均遠程訪問延遲對比

Table 6 Comparison of performance表6 性能對比

5 結(jié)論

針對陣列處理器中遠程訪問情況下的長延遲問題，設(shè)計一種實時動態(tài)遷移機制，以處理器對遠程數(shù)據(jù)的訪問頻率為依據(jù)，實現(xiàn)對遠程數(shù)據(jù)的動態(tài)調(diào)度。當(dāng)處理器PEi頻繁訪問遠程Cache行時，啟用遷移機制，通過遷移互連將遠程Cache行數(shù)據(jù)遷移至距離PEi最近的本地遷移查找表中，相比于不采用遷移機制的分布式Cache，平均遠程命中訪問延遲降低了80%。為進一步提高遷移機制的性能，在保證Cache數(shù)據(jù)一致性的情況下，對于遷移后不再被頻繁訪問的Cache行，通過取消遷移的操作，將其遷回至原靜態(tài)映射位置。與同類結(jié)構(gòu)相比，平均遠程訪問延遲降低了46.5%，并且工作頻率與峰值帶寬均有提高。通過運動補償算法的實現(xiàn)，以及對遠程Cache行的多種訪問模式進行訪存分析，對所提出的動態(tài)遷移機制進行全面驗證測試。