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

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

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

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

1 引言

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

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

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

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

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

（3）采用運(yùn)動(dòng)補(bǔ)償算法對所提出的動(dòng)態(tài)遷移機(jī)制進(jìn)行驗(yàn)證，并分析訪存性能。

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

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

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

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

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

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

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

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

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

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

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

3.2 遷移互連

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

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

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

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

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

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

（2）其他遠(yuǎn)程PE訪問已遷移的Cache行。當(dāng)某遠(yuǎn)程Cache行已遷移至PEi的遷移查找表且有效時(shí)，其遠(yuǎn)程Cache內(nèi)對應(yīng)的數(shù)據(jù)行狀態(tài)已更新為已遷移狀態(tài)，此時(shí)若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)完成的反饋信號返回給遠(yuǎn)程Cache，最終由遠(yuǎn)程Cache反饋給PEj完成訪問。

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

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

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

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

3.4 遷移取消方法

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

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

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

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

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

3.5 遷移一致性策略

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

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

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

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

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

4.1 FPGA硬件測試平臺

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

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

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

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

4.2 算法映射與功能驗(yàn)證

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

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

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

算法1Motion compensation

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

Fig.5 8×8 motion compensation algorithm execution time statistics圖5 8×8運(yùn)動(dòng)補(bǔ)償算法執(zhí)行時(shí)間統(tǒng)計(jì)

4.3 訪存性能分析

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

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

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

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

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

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

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

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

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

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

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

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

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時(shí)，對已遷移的R3執(zhí)行了寫操作，R3成臟數(shù)據(jù)塊，在取消遷移時(shí)，需寫回至原靜態(tài)映射位置，統(tǒng)計(jì)得取消遷移操作需19個(gè)時(shí)鐘周期，由于遷移取消R3與訪問R4不沖突，但下一次訪問R4時(shí)需等待遷移取消操作完成，因此遷移取消R3的代價(jià)與一次寫訪問R4的訪問延遲重疊，因此看起來遷移代價(jià)減少為13個(gè)時(shí)鐘周期。當(dāng)B取4時(shí)，遷移后的R3不再以任何方式被訪問，因此遷移取消時(shí)無需寫回R3的數(shù)據(jù)。

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

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

Table 5 Comparison of average remote access delay表5 平均遠(yuǎn)程訪問延遲對比

Table 6 Comparison of performance表6 性能對比

5 結(jié)論

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