陳利軍，高秀峰，崔 靜，李 芳

(軍械工程學院 信息工程系，河北 石家莊 050003)

標量處理機流水線性能分析研究

陳利軍，高秀峰，崔 靜，李 芳

(軍械工程學院 信息工程系，河北 石家莊 050003)

目前標量處理機提高指令執(zhí)行速度的途徑除提高處理機工作頻率外，常采用流水線技術和資源重復技術等。為研究這些技術對標量處理機性能的影響和這些技術使用中潛在的問題，利用一款具有32位精簡指令集的虛擬處理器WinDLX對這些技術進行仿真研究。對WinDLX虛擬處理器的寄存器、指令集等結構特征進行詳細介紹，然后對標量流水線處理機的工作原理、潛在問題和WinDLX對這些問題的解決辦法進行說明。在此基礎上，通過一個矩陣乘法運算程序分析了設置相關專用通路和提前形成條件碼兩種針對數(shù)據(jù)相關的解決辦法及其實際效果。該實例揭示了提高標量處理機指令執(zhí)行速度的有效途徑，為設計和改進流水線結構及提高流水線的執(zhí)行效率提供了參考依據(jù)。

標量處理機；流水線；WinDLX；虛擬處理器；精簡指令集

0 引 言

標量處理機是目前最為通用的一種處理機，在標量處理機中只有標量數(shù)據(jù)表示和標量指令系統(tǒng)。為提高標量處理機的指令執(zhí)行速度，除提高處理機的工作頻率，采用更好的算法和設計更好的功能部件外，最常用的途徑就是開發(fā)指令級并行技術。指令級并行技術分為時間上的并行和空間上的并行。時間上的并行即流水線技術，空間上的并行即資源重復技術。在流水線處理機中由于指令并行執(zhí)行，因此會出現(xiàn)指令順序執(zhí)行不會出現(xiàn)的一些問題，這些問題必須通過合理有效的辦法加以解決才能發(fā)揮出流水線應有的效能[1]。為研究流水線處理機的潛在問題及其解決辦法，文中利用WinDLX虛擬處理器進行了仿真研究。

1 WinDLX虛擬處理器的結構特征

1.1 WinDLX處理器的基本結構

WinDLX處理器是一種虛擬處理器，具有32位微處理機系統(tǒng)結構和多元未飽和型指令集。該處理器不僅體現(xiàn)了當今多種機器(AMD29K、DEC station 3100、HP850、IBM801、Intel i860等)指令集結構的共同特點，而且還體現(xiàn)了未來一些機器的指令集結構的特點。

WinDLX處理器有32個32位的通用寄存器R0,R1,…,R31和一套浮點寄存器，浮點寄存器既可作為32個32位單精度寄存器使用F0,F1,…,F31，也可作為16個雙精度寄存器使用F0,F2,…,F30。處理器支持的數(shù)據(jù)類型包括8位、16位和32位整型以及64位IEEE754浮點數(shù)。WinDLX內(nèi)存采用32位地址字節(jié)尋址，指令采用32位定長指令。

WinDLX處理器的指令集屬于簡單的Load/Store指令集，指令注重流水效率和簡化譯碼。WinDLX提供了寄存器尋址、立即值尋址、偏移尋址和寄存器間接尋址4種方式，指令操作分為Load/Store操作、ALU操作、分支和跳轉操作以及浮點操作。所有的ALU指令都是寄存器—寄存器型指令，其運算包含了簡單的算術和邏輯運算。浮點操作指令的操作數(shù)來源于浮點寄存器，能完成浮點加、減、乘、除操作。

1.2 WinDLX平臺構成

WinDLX是一個基于Windows的模擬器，具有Register，Code，Pipeline，Clock Cycle Diagram，Statistics和Breakpoints共6個模塊。在WinDLX中將每條指令分為取指(IF)、譯碼(ID)、執(zhí)行(EX)、訪存(MEM)和寫回(WB)5個功能段，此外對于浮點操作還專門設置了浮點加、浮點乘和浮點除部件。在WinDLX中，“Clock Cycle Diagram”時鐘周期圖模塊能準確地描繪出指令在DLX流水線中的調(diào)度及功能段的使用情況。通過該模塊能有效地分析出指令流水過程中出現(xiàn)的結構相關、數(shù)據(jù)相關和控制相關。

2 流水線處理機潛在的問題

在流水線中，由于處理機被分為若干個功能段，如取指、分析和執(zhí)行功能段，指令在這些功能段中流水前進[2-3]。

在這樣的流水線中由于多個功能段同時工作，因此會出現(xiàn)指令順序執(zhí)行中不會出現(xiàn)的一些問題。比較明顯的就是訪存沖突問題。例如，取指功能段需要訪問主存取指令，分析功能段需要從主存中取操作數(shù)，執(zhí)行功能段需要向主存寫回運算結果。當這3個功能段同時工作時，就會出現(xiàn)訪存沖突[4]。為了解決該問題，標量處理機采用了先行控制技術。通過增設先行指令緩沖棧、先行讀數(shù)棧和后行寫數(shù)棧，實現(xiàn)對指令流和數(shù)據(jù)流的預處理和緩沖，盡量使取指、分析和執(zhí)行部件獨立工作而不會出現(xiàn)訪存沖突[5]。

WinDLX處理器的指令集屬于簡單的Load/Store指令集，只有Load/Store指令要訪存，而所有的ALU指令都是寄存器—寄存器型指令，不需要訪存，這樣就能極大降低訪存沖突。

除訪存沖突問題外，在流水線實際運行中還會出現(xiàn)結構相關、數(shù)據(jù)相關和控制相關等問題[6-7]。

結構相關是指指令在并行解釋過程中，前、后指令要求使用同一個功能部件所引起的資源沖突。

數(shù)據(jù)相關是指后續(xù)指令若用到前面指令的執(zhí)行結果，則必須等待前面指令執(zhí)行完成、寫入結果后，后續(xù)指令才能執(zhí)行。

控制相關是指流水線遇到分支或轉移指令，導致流入流水線的指令作廢而產(chǎn)生的相關。

流水線中的這幾種相關通常同時存在，一旦出現(xiàn)相關，必然會影響指令的執(zhí)行速度，降低流水線的執(zhí)行效率。

3 WinDLX針對相關問題的解決辦法

3.1 結構相關的解決方法

在標量流水線處理機中，針對結構相關可通過資源重復技術加以解決，即通過重復設置易發(fā)生使用沖突的功能部件，讓同時解釋執(zhí)行的多條流水指令獨立使用重復設置的多個功能部件，從而解決該問題。WinDLX提供對浮點運算部件的重復設置功能，每個運算部件最多可重復設置8套[8]。

3.2 數(shù)據(jù)相關的解決方法

針對數(shù)據(jù)相關，標量流水線處理機通過建立相關專用通路加以解決。相關專用通路的基本原理是數(shù)據(jù)重定向。圖1為4條指令組成的完成1個簡單算術四則運算的程序段。

圖1 算術四則運算程序

該程序段執(zhí)行時的數(shù)據(jù)流程如圖2所示。

圖2 原數(shù)據(jù)流程

圖中，F(xiàn)1，F(xiàn)2，F(xiàn)3代表浮點寄存器，A和B代表主存單元，F(xiàn)ADD和FMUL代表運算部件，帶有箭頭的線表示數(shù)據(jù)傳送路徑。

由圖2看出，指令k,k+1,k+2和k+3依次存在“先寫后讀”相關性；指令k,k+1,k+2依次存在“寫—寫”相關性。這些相關性的出現(xiàn)必然造成流水線中后續(xù)相關指令的等待，降低流水線的執(zhí)行效率。

對于“先寫后讀”相關性，可設置A→FADD，F(xiàn)ADD→FMUL和FMUL→B這3條專用通路，同時撤消F1→FADD與F1→FMUL的通路。

對于“寫—寫”相關性，可撤消A→F1及FADD→F1的通路。

通過以上專用通路的設置，解決了數(shù)據(jù)相關性的問題。

設置了相關專用通路后的數(shù)據(jù)流程如圖3所示。

圖3 重定向后的數(shù)據(jù)流程

相關專用通路的設置解決了因數(shù)據(jù)相關性而產(chǎn)生的指令等待，保證了最終寫入數(shù)據(jù)的正確性，從而提高了流水線的執(zhí)行效率[9]。

WinDLX由于所有的ALU指令都是寄存器—寄存器型指令，因此數(shù)據(jù)相關基本都是涉及通用寄存器的數(shù)據(jù)相關，針對通用寄存器數(shù)據(jù)相關采用相關專用通路是有效的解決辦法。在WinDLX中通過Configuration-EnableForwarding菜單項可設置或取消流水線中的相關專用通路。

3.3 控制相關的解決方法

針對控制相關，通?？梢圆扇∞D移預測技術等方法加以解決。轉移預測主要是對條件轉移指令轉移成功還是轉移不成功進行預測，讓預測分支進入流水線[10-11]。

在WinDLX中，解決控制相關的主要辦法是從硬件上提前得到轉移的目標地址。WinDLX中將計算PC值的多路選擇器MUX提前到IF段，保證對PC的寫操作只在一個流水段內(nèi)出現(xiàn)，避免了在遇到分支轉移時，流水線中的轉移成功和轉移不成功2條分支指令都試圖在不同的流水段寫PC值從而引發(fā)沖突[12]。

4 求階乘程序的對比分析

圖4 矩陣A×B

由于兩個原始矩陣各有20個分量，運行結果有20個分量，共計60個分量，超出了WinDLX32個通用寄存器的數(shù)量，因此該程序采用存儲器來存放原始矩陣和結果矩陣的各個分量[13]。

首先通過循環(huán)程序?qū)B續(xù)的40個存儲單元賦初值，然后通過三重循環(huán)嵌套實現(xiàn)矩陣乘法運算并將各結果分量存入存儲器，最后通過系統(tǒng)調(diào)用Trap5實現(xiàn)對運行結果的顯示。其中對40個連續(xù)的存儲單元賦初值的循環(huán)程序如圖5所示。

圖5 對存儲單元循環(huán)賦初值

在WinDLX的流水線時鐘周期圖中可以看到，由于addir4,r4,1指令與subir5,r4,40指令存在針對r4寄存器的先寫后讀相關；subir5,r4,40指令與beqzr5,mul指令存在針對r5寄存器的先寫后讀相關，在未設置數(shù)據(jù)專用通路的情況下，造成了后續(xù)指令的讀操作數(shù)延遲R-Stall。在實現(xiàn)矩陣乘法運算的三重循環(huán)嵌套中也存在類似問題。程序在未設置數(shù)據(jù)專用通路的情況下最終執(zhí)行時間為52s，程序總執(zhí)行周期數(shù)為4 730，先寫后讀相關(RAW)共2 161次，占總周期數(shù)的45.7%。

如果改進處理機結構，增設數(shù)據(jù)專用通路，則addir4,r4,1指令與subir5,r4,40指令之間由于相關性造成的R-Stall延遲得到解決，subir5,r4,40指令與beqzr5,mul指令之間相關性造成的R-Stall延遲得到部分解決。整個程序的執(zhí)行周期數(shù)為3 150，先寫后讀相關(RAW)降到570次，占總周期數(shù)的18.1%。

設置相關專用通路只讓subir5,r4,40指令與beqzr5,mul指令之間的相關性問題得到了部分解決而不是全部解決，因為beqzr5,mul指令屬于一般條件轉移指令，該指令在指令譯碼功能段(ID)就要真正用到r5進行判斷，而不像subir5,r4,40指令在執(zhí)行功能段(intEX)才會真正用到r4。因此即便是設置了相關專用通路，只要subir5,r4,40指令與beqzr5,mul指令相鄰，它們之間的R-Stall延遲不可避免。

為了完全解決這種一般條件轉移指令造成的先寫后讀相關，可以對程序進行優(yōu)化，提前形成條件碼[14]。在該例中，可以將addir4,r4,1指令與subir5,r4,40指令提前，如圖6所示。

圖6 優(yōu)化后的程序

這樣beqzr5,mul指令的判斷條件會提前得到，該數(shù)據(jù)相關性問題會得到徹底解決。對矩陣乘法運算中的三重循環(huán)嵌套也采用類似辦法優(yōu)化代碼，最后程序的執(zhí)行時間僅需32s，整個程序的執(zhí)行周期數(shù)為2 990，先寫后讀相關(RAW)降到400次，占總周期數(shù)的13.38%。

5 結束語

通過上述程序可以看到，設置相關專用通路和提前形成條件碼是WinDLX解決數(shù)據(jù)相關的有效途徑，能極大提高流水線的執(zhí)行效率。WinDLX同時支持資源重復設置，對浮點加法器、浮點乘法器和浮點除法器可進行重復設置。在浮點運算程序中通過重復設置浮點運算部件可極大提高流水線的執(zhí)行效率。由此可見，WinDLX虛擬處理器為設計、研究和改進標量處理機流水線結構提供了一個方便、直觀的平臺，研究該平臺有助于對計算機系統(tǒng)結構的學習和理解。

[1]HennessyJL,PattersonDA.Computerarchitecture-aquantitativeapproach[M].4thed.SanFrancisco:MorganKauf-mannPublishers,2007.

[2] 張晨曦.計算機系統(tǒng)結構[M].第4版.北京：高等教育出版社，2006.

[3]SherwoodT,PerelmanE,HamerlyG,etal.Discoveringandexploitingprogramphases[J].IEEEMicro,2003,23(6):84-93.

[4] 薛 楊.流水線技術性能評價與最佳段數(shù)選擇[J].吉林省教育學院學報，2011,27(10)：141-144.

[5] 劉 博，張盛兵,黃嵩人.靜態(tài)超標量MCU-DSP內(nèi)核的Load先行訪存調(diào)度[J].計算機應用研究，2013，30(2)：450-453.

[6] 王曉勇，張盛兵，黃嵩人.一種多發(fā)射DSP的數(shù)據(jù)相關控制[J].微型電腦應用，2011，27(11)：56-58.

[7] 柴曉東.指令流水線阻塞問題分析[J].濮陽職業(yè)技術學院學報，2014,27(5)：143-144.

[8] 潘琢金，鄭彩平,楊 華.流水線前端資源分配及其性能影響研究[J].計算機工程，2010,36(14)：275-277.

[9] 朱博元，劉高輝,李政運,等.RISC指令集眾核處理器功能驗證與實現(xiàn)[J].計算機工程與應用，2014,50(21)：54-58.

[10]HoCY,ChngKF,YauCH,etal.Astudyofdynamicbranchpredictors:counterversusperceptron[C]//Procoftheinternationalconferenceoninformationtechnology.[s.l.]:[s.n.],2007:528-563.

[11]JimenezDA,LinC.Dynamicbranchpredictionwithperceptron[C]//Procofthe7thinternationalsymposiumonhighperformancecomputerarchitecture.[s.l.]:[s.n.],2001:197-206.

[12] 賴兆磬，潘 明，許 勇，等.嵌入式五級流水線CPU核的設計與實現(xiàn)[J].微計算機信息，2008，24(29)：32-34.

[13]JohnsonhaughR,SchaeferM.Algorithms[M].Beijing:TsinghuaUniversityPress,2007：195-197.

[14]PanY,MitraT.Characterizingembeddedapplicationsforinstruction-setextensibleprocessors[C]//Procofthe2004internationalconferenceoncompliers.[s.l.]:ACM,2004:67-78.

Analysis and Research on Pipelining of Scalar Processor

CHEN Li-jun,GAO Xiu-feng,CUI Jing,LI Fang

(Department of Information Engineering,Ordnance Engineering College,Shijiazhuang 050003,China)

Now,besides increasing the operation frequency,the pipelining and the resource replication are used to accelerate the scalar processor.In order to study these technologies’ effect and potential problems to the scalar processor,it uses the WinDLX virtual processor which has 32bit reduced instruction set.The structure characteristics of the WinDLX virtual processor like registers and instruction set are introduced.Then the operational principle of the scalar processor’s pipelining,the potential problems and the settlements by WinDLX are discussed.After that,a matrix multiplication program is used to analyze the solutions to data correlation,one is correlation special channel,the other is early formation condition code.This example reveals an effective way to improve the execution speed of the scalar processor instructions,which provides a reference for the design and improvement of the pipeline structure and the improvement of the efficiency of the pipeline.

scalar processor;pipelining;WinDLX;virtual processor;RIS

2016-03-25

2016-06-28

時間：2016-09-19

國家自然科學基金資助項目(61271152)

陳利軍(1973-)，男，碩士，副教授，研究方向為計算機系統(tǒng)結構、嵌入式系統(tǒng)應用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160919.0843.068.html

TP391.9

A

1673-629X(2016)11-0082-04

10.3969/j.issn.1673-629X.2016.11.018