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

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

1 引言

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

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

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

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

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

2 相關(guān)研究

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

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

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

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

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

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

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

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

4 提前判定算法

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

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

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

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

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

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

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

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

當(dāng)滑行點(diǎn)位于S(i-1)或S(i-1)之前時(shí)，T1時(shí)刻的分布如T1(SLIP3)所示。此時(shí)對(duì)S(i)的檢測(cè)與正常運(yùn)行時(shí)的效果相同，Dep_Set(SLIP3)的計(jì)算公式與Dep_Set(RUN)相同。

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

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

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

5 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

表1 RF級(jí)檢測(cè)電路延時(shí)信息

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

表2 電路資源對(duì)比

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

6 總結(jié)

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

本文將流水線運(yùn)行方式歸納為3種狀態(tài)。根據(jù)當(dāng)前時(shí)刻指令分布和功能單元的信號(hào)，由當(dāng)前流水線狀態(tài)推測(cè)下一周期內(nèi)的指令分布，在本周期內(nèi)判斷出下一周期的指令相關(guān)性，從而能夠隱藏相關(guān)檢測(cè)電路的延時(shí)。在MediaDSP64處理器上的實(shí)驗(yàn)表明，流水線關(guān)鍵路徑延時(shí)下降了約30%，資源占用增加了約3800門。對(duì)于VLIW結(jié)構(gòu)和超標(biāo)量結(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ìng)爭(zhēng)檢測(cè)方法[J]. 浙江大學(xué)學(xué)報(bào) (工學(xué)版), 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號(hào)處理器設(shè)計(jì)和性能分析[J].計(jì)算機(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ù)字信號(hào)處理器[P]. 中國(guó)專利, 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.