RISC-DSP處理器中指令數(shù)據(jù)相關(guān)性的提前判斷方法

蔡衛(wèi)光 姚慶棟 劉 鵬

(浙江大學信息與電子工程學系 杭州 310027)

1 引言

流水線技術(shù)通過多條指令重疊執(zhí)行的方式提高了處理器性能，但也導致了不同流水級之間的指令相關(guān)性問題。隨著流水線深度的提高和功能單元數(shù)量的增加，指令相關(guān)性對性能的影響也更加嚴重。

先前對指令相關(guān)性的研究主要包括：采用指令緩沖區(qū)[1]使流水線具有一定的亂序執(zhí)行能力，減少數(shù)據(jù)相關(guān)引起的停頓。采用2 bit著色法[2]標識處理器狀態(tài)，確定控制相關(guān)發(fā)生的時刻。利用操作表(operation table)技術(shù)[3]對指令流進行分析以確定實際執(zhí)行時的指令相關(guān)，并根據(jù)流水線結(jié)構(gòu)進行指令調(diào)度。雖然這些工作針對指令相關(guān)性問題采取了各種措施，但其目標主要是提高指令執(zhí)行效率，并未對相關(guān)檢測電路的結(jié)構(gòu)進行詳細的研究。

文獻[4]通過指令分層次譯碼減少了數(shù)據(jù)相關(guān)檢測電路的延時，但其流水線較短且主要針對譯碼級實現(xiàn)，限制了在其它流水級的應用。超標量處理器中數(shù)據(jù)相關(guān)檢測有基于保留站的廣播方式[5]和基于計數(shù)器的方法[6]，前者需要較多的寄存器號碼比較邏輯，后者需要在譯碼時確定指令的執(zhí)行周期數(shù)并維護多個計數(shù)器。并發(fā)推測多線程(Simultaneous Speculative Threading, SST)處理器通過記分牌在前行與后行線程之間傳遞指令相關(guān)信息[7]，但需要多個指令隊列與寄存器文件。這些方法的復雜度較高，限制了在其它結(jié)構(gòu)處理器中的應用。

嵌入式系統(tǒng)中通常允許定制指令，如MIPS的CorExtend技術(shù)[6]等。操作數(shù)較多的定制指令會增加硬件實現(xiàn)的復雜度，如工作頻率和數(shù)據(jù)帶寬等[8]。文獻[9]通過基于哈希映射的影子寄存器結(jié)構(gòu)提高寄存器文件帶寬，但并未分析對相關(guān)檢測邏輯的影響。

本文的研究主要針對這幾個方面，一是指令操作數(shù)較多增加了相關(guān)檢測電路的延時，影響了處理器工作頻率；二是指令執(zhí)行周期數(shù)在實際運行時才能確定，無法在譯碼時獲得；三是要求相關(guān)檢測邏輯對處理器結(jié)構(gòu)和資源的影響較小。本文的內(nèi)容安排如下：第1節(jié)介紹研究背景，第2節(jié)針對典型流水線結(jié)構(gòu)對常規(guī)檢測算法進行說明，第3節(jié)通過流水線狀態(tài)推測下一周期中的指令分布，給出了相關(guān)檢測的提前判定算法及其優(yōu)化方法，第4節(jié)以媒體處理器MediaDSP64(以下簡稱MD64)為例，進行了算法實現(xiàn)和電路綜合，給出了實驗結(jié)果和分析，最后在第5節(jié)給出結(jié)論。

2 相關(guān)研究

MD64是一種 RISC-DSP結(jié)構(gòu)的媒體處理器[10,11]，它也是多核片上系統(tǒng)和片上互連網(wǎng)絡研究中的面向計算的處理器核。不僅支持 RISC，DSP和SIMD指令集，還能夠在單個定制指令中實現(xiàn)多個復雜操作。支持兩個操作數(shù)同時來自存儲器，從而克服了定制指令不能訪問存儲器的不足[9]。在400～500 MHz的頻率下，達到 3200～4000 16×16 MMAC/s (Mega MAC per second)的運算能力。

MD64結(jié)構(gòu)如圖1所示。流水線前端為按序單發(fā)射取指，后端則將復雜指令分解成兩個微操作送入相應的子流水線執(zhí)行。微操作之間允許部分亂序執(zhí)行，而精確中斷由基于影子寄存器的檢查點(checkpoint)機制實現(xiàn)。在由DA，AC和DM級組成的訪存子流水線內(nèi)與EX級內(nèi)，用戶可以添加專用硬件實現(xiàn)特殊功能，如針對媒體處理中比特流緩沖區(qū)的管理指令和變長碼的解碼指令等。這些指令的執(zhí)行周期需要在運行時確定，例如變長碼的解碼指令其執(zhí)行周期就和具體的碼流有關(guān)。

原先處理器關(guān)鍵路徑由3個部分串聯(lián)組成，分別是數(shù)據(jù)相關(guān)檢測、控制信號生成和流水級控制，其延時約為3.53 ns。其中檢測電路的延時占有較大比例(1/3左右)，主要原因有兩點。一是單條定制指令包含多個操作導致其操作數(shù)個數(shù)增加，需要檢測的路徑也隨之增加。二是流水線深度增加導致執(zhí)行中的指令也隨之增加，需要對更多的指令進行檢測。因此，為了提高工作頻率并避免對結(jié)構(gòu)進行較大改動，指令相關(guān)檢測成為電路設計的關(guān)鍵問題。

圖1 MD64流水線結(jié)構(gòu)

3 指令相關(guān)檢測

以數(shù)據(jù)相關(guān)為例，如圖2所示，檢測單元與功能單元分布在各個流水級內(nèi)，指令在WB流水級將其結(jié)果寫入寄存器文件。針對流水級S(i)內(nèi)的指令I(lǐng)(i)，檢測單元 HDU(i)判斷其是否存在數(shù)據(jù)相關(guān)性的公式如式(1)，式(2)所示。其中FU_Set表示功能單元集合，Src_Set表示源操作數(shù)集合，Dst_Set表示目的操作數(shù)集合。

圖2 典型流水線結(jié)構(gòu)

式(1)表示 HDU(i)所負責檢測的功能單元中，包含I(i)所需要使用的功能單元。式(2)表示I(i)的源操作數(shù)集合與后續(xù)流水級中指令的目的操作數(shù)集合存在交集?？梢酝ㄟ^檢查指令的依賴關(guān)系集合Dep_Set是否為空來判斷相關(guān)性，如式(3)所示，功能單元的使用信息等已隱藏在其操作數(shù)集合中。

4 提前判定算法

4.1 依賴關(guān)系集合的提前判定

該方法的基本思想是計算下一周期內(nèi)的依賴關(guān)系集合，并將其結(jié)果存儲在流水線界面寄存器內(nèi)。下個周期可以直接使用該結(jié)果，從而隱藏檢測電路的延時。本文將流水線的運行狀態(tài)分為3種，即正常運行狀態(tài)(RUN)、滑行狀態(tài)(SLIP)和停頓狀態(tài)(STALL)。正常運行狀態(tài)下每條指令在一個時鐘周期后進入相鄰的后一個流水級，停頓狀態(tài)下指令的位置保持不變?；袪顟B(tài)下，滑行點將不斷插入nop指令并將其送入相鄰的后一個流水級，滑行點之前的流水級為停頓狀態(tài)，之后的流水級為正常運行狀態(tài)。在分析的范圍內(nèi)假定流水線滿足規(guī)整性，即指令只有一個入口(來自流水線前端)和出口(WB級)。如圖 3所示，T0表示當前周期的指令分布，而T1表示下一周期的分布。本節(jié)將以S(i)級為例，給出不同狀態(tài)下其依賴關(guān)系集合的提前計算公式。

圖3 不同流水線狀態(tài)下的指令傳遞

當T0時刻為正常運行狀態(tài)時，T1時刻的指令分布如T1(RUN)所示。T1時刻S(i)內(nèi)指令的依賴關(guān)系集合如式(4)所示。

若在T0時刻計算該集合需考慮指令的位置變化，例如指令I(lǐng)(i-1)在T0時刻還位于S(i-1)內(nèi)。將其變成基于流水級的形式后如式(5)所示，即在T0時刻將S(i)到S(i+n-1)內(nèi)的指令對S(i-1)內(nèi)的指令進行檢測，其結(jié)果相當于T1時刻對S(i)內(nèi)指令的檢測結(jié)果。

當T0時刻為停頓狀態(tài)時，T1時刻的指令分布如圖3中T1(STALL)所示，與T0時刻的分布完全相同，提前計算依賴關(guān)系的公式如式(6)所示。

當T0時刻為滑行狀態(tài)時，需要確定滑行點的位置。以滑行點位于S(i)流水級為例，T1時刻的分布如T1(SLIP1)所示。此時S(i-1)和之前流水級保持停頓，S(i+1)和之后流水級保持正常運行，S(i)內(nèi)不斷插入nop指令，所以Dep_Set(SLIP1)為空集φ。

當滑行點位于S(i+1)與S(i+n)之間時，以位于S(i+1)內(nèi)為例，T1時刻的指令分布如T1(SLIP2)所示。S(i+1)內(nèi)不斷插入nop指令，由于nop指令對檢測結(jié)果無影響，所以從S(i+1)向后傳遞的nop指令則可作為普通指令對待。此時其計算公式如式(7)所示

當滑行點位于S(i-1)或S(i-1)之前時，T1時刻的分布如T1(SLIP3)所示。此時對S(i)的檢測與正常運行時的效果相同，Dep_Set(SLIP3)的計算公式與Dep_Set(RUN)相同。

4.2 電路實現(xiàn)與優(yōu)化

若直接按照式(5)，式(6)和式(7)計算結(jié)果，再根據(jù)運行狀態(tài)選擇正確的值存儲在界面寄存器中，則需要的檢測路徑較多，且檢測對象和檢測范圍也不同，通常這意味著較大的電路延時和資源占用?？梢栽诠介g共享檢測路徑進行優(yōu)化，定義目的操作數(shù)集合Dst_SubSet如式(8)所示。

該公式需要對源操作數(shù)集合與目的操作數(shù)集合單獨進行操作。然而在傳統(tǒng)設計中寄存器號碼采用二進制編碼表示，難以表達集合操作的概念。因此在MD64中使用獨位碼(One-Hot Code)表示指令的Src_Set和 Dst_Set。其位寬與寄存器文件容量相等，每比特對應一個寄存器。若指令使用到該寄存器，則將相應的比特設為高電平。于是“并集”操作轉(zhuǎn)換為電路上的“邏輯或”操作，“交集”操作轉(zhuǎn)換為“邏輯與”操作，從而直接實現(xiàn)上述算法。

5 實驗結(jié)果與分析

基于TSMC 0.13 μm (generic and worst case)的工藝條件，我們在MD64內(nèi)實現(xiàn)了該算法。綜合結(jié)果表明采用該算法后檢測電路自身的延時有所增加，原因在于需考慮多種流水線運行狀態(tài)。新方法并未直接降低檢測電路延時，而是將該延時隱藏。相當于將原先關(guān)鍵路徑分為兩個周期(如圖4所示)。

圖4 RF級提前檢測結(jié)構(gòu)

圖5列出了檢測電路所在流水級的關(guān)鍵路徑延時，共有RF，AC和DS這3個流水級需要檢測。其中RF級檢測路徑最多，需要對DA到EX共5個流水級內(nèi)的指令進行檢測。RUN狀態(tài)下對RF級的提前檢測需用到ID級指令，而ID級需先對指令譯碼和獨位碼編碼，所以其延時最長，如圖4所示。在AC級與DS級的檢測電路內(nèi)，流水線狀態(tài)信號生成的延時已經(jīng)超過了檢測操作本身的延時。

圖5 優(yōu)化前后的延時對比

表1列出了RF級檢測電路延時的詳細信息。RF級需檢測的源操作數(shù)集合最多包含6個寄存器，目的操作數(shù)集合為2個寄存器，因此ID級內(nèi)指令譯碼和獨位碼編碼的延時較大(1.66 ns)。在相關(guān)檢測部分，采用獨位碼不僅減少了單個指令的檢測路徑，并能夠在流水級之間共享檢測路徑，從而減少了電路復雜度和驅(qū)動的延時。

表1 RF級檢測電路延時信息

電路資源對比如表2所示，檢測電路本身的資源占用有較大下降，但獨位碼編碼器和獨位碼在流水線中的傳遞需要較多的資源(6574門)，整體上增加了3771門。采用隨機激勵進行的峰值功耗分析表明，采用提前判斷算法后相關(guān)檢測電路的功耗從原先的4.15 μW/MHz上升到 5.51 μW/MHz(包括獨位碼編碼器的功耗)。這些資源和功耗的增加對整個處理器的影響很小。

表2 電路資源對比

在相關(guān)檢測的延時被隱藏后，先前流水線關(guān)鍵路徑的延時從3.53 ns下降到2.47 ns，減少了約30%，達到了設計目標的要求。

6 總結(jié)

隨著流水線深度與寬度的增加，相關(guān)檢測電路的延時成為制約處理器時鐘頻率提升的關(guān)鍵因素。特別是對于媒體處理器與可配置結(jié)構(gòu)的處理器，指令的操作數(shù)較多，且存在執(zhí)行周期數(shù)動態(tài)可變的特性。這對檢測電路的設計提出了更高的要求。

本文將流水線運行方式歸納為3種狀態(tài)。根據(jù)當前時刻指令分布和功能單元的信號，由當前流水線狀態(tài)推測下一周期內(nèi)的指令分布，在本周期內(nèi)判斷出下一周期的指令相關(guān)性，從而能夠隱藏相關(guān)檢測電路的延時。在MediaDSP64處理器上的實驗表明，流水線關(guān)鍵路徑延時下降了約30%，資源占用增加了約3800門。對于VLIW結(jié)構(gòu)和超標量結(jié)構(gòu)的處理器，本文提出的方法也具有一定的參考意義。

[1] Lu Jia-jing, Zhou Xiao-fang, and Wang Jun-yu. A novel dynamic scheduling algorithm of data hazard for embedded processor [C]. Proceedings of the 7th IEEE International Conference on ASIC. Shanghai, China, IEEE, 2007: 28-31.

[2] Chang Meng-chou and Shiau Da-sen. Design of an asynchronous pipelined processor [C]. International Conference on Communications Circuits and Systems. Seoul,Korea, IEEE, 2008: 1093-1096.

[3] Shrivastava A, Earlie E, and Dutt N D,et al.. Retargetable pipeline hazard detection for partially bypassed processors [J].IEEE Transactions on Very Large Scale Integration Systems,2006, 14(8): 791-801.

[4] 余巧艷, 劉鵬. 一種面向 DSP深度壓縮指令的數(shù)據(jù)競爭檢測方法[J]. 浙江大學學報 (工學版), 2005, 39(10): 1501-1506.Yu Qiao-yan and Liu Peng. Data hazard checking method for heavily compressed DSP instruction [J].Journal of Zhejiang University(Engineering Science), 2005, 39(10): 1501-1506.

[5] 胡偉武, 張福新, 李祖松. 龍芯2號處理器設計和性能分析[J].計算機研究與發(fā)展, 2006, 43(6): 959-966.Hu Wei-wu, Zhang Fu-xin, and Li Zu-song. Design and performance analysis of the godson-2 processor [J].Journal of Computer Research and Development, 2006, 43(6): 959-966.

[6] MIPS Technology. MIPS32 74K Processor Core Family Software User's Manual. 2008. 12.

[7] Shailender C, Robert C, and Magnus E,et al.. Simultaneous speculative threading: a novel pipeline architecture implemented in SUN's ROCK processor [C]. The 36th International Symposium on Computer Architecture. Austin,USA, IEEE, 2009: 484-495.

[8] Iqbal M A and Awan U S. Run-time reconfigurable instruction set processor design: RT-RISP [C]. The 2nd International Conference on Computer Control and Communication. Karachi, Pakistan, IEEE, 2009: 1-6.

[9] Jason C, Han Guo-ling, and Zhang Zhi-ru. Architecture and compiler optimizations for data bandwidth improvement in configurable processors [J].IEEE Transactions on Very Large Scale Integration Systems, 2006, 14(9): 986-997.

[10] Shi Ce, Wang Wei-dong, and Zhou Li,et al.. 32b RISC/DSP media processor: MediaDSP3201 [C]. Proceedings of SPIE-IS& T Electronic Imaging. San Jose, USA, SPIE, 2005: 43-52.

[11] 劉鵬, 姚慶棟, 李東曉等. 32位媒體數(shù)字信號處理器[P]. 中國專利, 200410016753.8, 2007-01-31.Liu Peng, Yao Qing-dong, and Li Dong-xiao,et al.. 32 bit media DSP processor [P]. China patent, 200410016753.8,2007-01-31.