利用Tomasulo算法處理數(shù)據(jù)相關(guān)的流水線CPU設(shè)計

李山山， 劉敬晗

(清華大學(xué) 計算機(jī)系， 北京 100084)

0 引 言

計算機(jī)組成和系統(tǒng)結(jié)構(gòu)是計算機(jī)專業(yè)重要的核心基礎(chǔ)課之一[1]，但是課程內(nèi)的計算機(jī)高層次設(shè)計中采用的策略、結(jié)構(gòu)、原理以及工作過程等內(nèi)容，相對比較抽象和空洞，是比較難講清楚的，學(xué)生經(jīng)常反映學(xué)起來難懂和乏味[2]。為了幫助學(xué)生更好地理解這些內(nèi)容，一些學(xué)校加入了一些更加直觀的實踐手段，如采用模擬實驗系統(tǒng)進(jìn)行課程實驗[3]。但是采用軟件模擬手段的實驗內(nèi)容大多是驗證性質(zhì)的，學(xué)生缺少參與度，因此缺乏對計算機(jī)硬件設(shè)計層次的理解。如果讓學(xué)生自己在硬件上設(shè)計并實現(xiàn)一個具有相應(yīng)功能的處理器則能更好地提高學(xué)生對相關(guān)理論點(diǎn)的理解和掌握程度，因此我們在計算機(jī)組成與系統(tǒng)結(jié)構(gòu)課程的實驗中加強(qiáng)了設(shè)計實踐環(huán)節(jié)，包括流水線、多核、指令調(diào)度算法等實驗內(nèi)容，都需要學(xué)生在實際硬件上設(shè)計實現(xiàn)的，切實提高了實驗教學(xué)的水平和理論教學(xué)層次。

本文提供了課程實驗的一個樣例，實現(xiàn)了利用Tomasulo算法處理數(shù)據(jù)相關(guān)的四級流水線CPU。該樣例不僅包括了計算機(jī)組成原理的基礎(chǔ)知識，如CPU的結(jié)構(gòu)、數(shù)據(jù)通路等，更加突出了流水線、Tomasulo算法等系統(tǒng)結(jié)構(gòu)的內(nèi)容。文中首先介紹了開展實驗的環(huán)境以及相關(guān)技術(shù)基礎(chǔ)，然后介紹了該CPU的指令系統(tǒng)，接著描述了整個CPU的結(jié)構(gòu)以及內(nèi)部主要部分的功能，然后從功能和性能兩方面對CPU進(jìn)行了測試，最后對Tomasulo算法的優(yōu)缺點(diǎn)以及其適用的范圍做盡量深入的分析。

1 實驗環(huán)境及技術(shù)介紹

由于有了可編程芯片和硬件設(shè)計語言，使得計算機(jī)系統(tǒng)硬件設(shè)計實驗變得更加方便可行，也有了很多這類的實驗平臺[4-5]。本實驗使用的硬件是開放式CPU設(shè)計與測試平臺，它是專門為系統(tǒng)結(jié)構(gòu)相關(guān)課程實驗設(shè)計的，能夠支持下載到FPGA中的處理器的調(diào)試。軟件方面使用Quartus進(jìn)行處理器設(shè)計，另外使用DebugController的程序來支持對外部存儲器的讀寫操作，還能夠監(jiān)控處理器的狀態(tài)和調(diào)試正在執(zhí)行的程序，比如設(shè)置斷點(diǎn)，對地址總線、數(shù)據(jù)總線進(jìn)行監(jiān)控等等。該實驗平臺提供了最大的自由度，讓同學(xué)可以自由設(shè)計處理器，并在測試平臺上調(diào)試和運(yùn)行[6]。

流水線技術(shù)是多條指令同時執(zhí)行的一種實現(xiàn)技術(shù)，是現(xiàn)代計算機(jī)系統(tǒng)結(jié)構(gòu)的基本技術(shù)之一[7]。流水線的每一個步驟完成一條指令的一部分，各部分相連接形成流水線。指令從一端進(jìn)入，經(jīng)過這些流水節(jié)拍的處理，從另一端流出，流水線的吞吐量取決于指令流出流水線的速度。

Tomasulo算法是Robert Tomasulo在1967年提出了的寄存器重命名(Register Renaming)的技術(shù)[8]。Tomasulo算法是一種動態(tài)調(diào)度算法，將寄存器換名技術(shù)融入了記分板方案中來避免寫寫沖突和讀寫沖突，從而使指令在有沖突存在的情況下仍能繼續(xù)執(zhí)行。

在Tomasulo算法中，保留站中緩存了即將要發(fā)射的指令所需要的操作數(shù)，其工作的基本思想是盡可能早地取得并緩存一個操作數(shù)，從而避免必須讀操作數(shù)時才去寄存器中讀取的情況，即將執(zhí)行的指令會在保留站中取得所需要的操作數(shù)。當(dāng)出現(xiàn)多個操作數(shù)時對應(yīng)的寄存器也將換成保留站的名字，這一過程也叫做寄存器換名技術(shù)[9]。發(fā)射邏輯部件與保留站換名技術(shù)的結(jié)合，消除了寫寫沖突和讀寫沖突。在算法中，沖突檢測和執(zhí)行控制是分散的，每一個功能部件的保留站控制該部件中指令的執(zhí)行。結(jié)果將從保留站所緩存的地方直接送到功能部件中，而不是通過寄存器傳送，為此使用了一條結(jié)果總線。該總線允許所有等待該操作數(shù)的功能部件可以同時取到該數(shù)據(jù)。Tomasulo算法的整體結(jié)構(gòu)簡圖[8]如圖1所示。

保留站中保存著已經(jīng)發(fā)射并等待到功能部件中去執(zhí)行的指令，還有指令所需要的原操作數(shù)以及控制該指令在部件中執(zhí)行所需要的信息。在讀寫數(shù)緩沖站中保存著從內(nèi)存讀出或要保存到存儲器去的數(shù)據(jù)或數(shù)據(jù)地址。所有從功能部件和存儲器中出來的結(jié)果均被送到公共數(shù)據(jù)總線上，并到達(dá)所有需要該操作數(shù)的地方。除了讀數(shù)緩沖站，所有緩沖站和保留站均設(shè)置有標(biāo)志域，用于沖突控制機(jī)制。

指令執(zhí)行會經(jīng)過的以下三個階段[10]：

(1) 發(fā)射。從指令隊列中取得一條指令，根據(jù)指令和當(dāng)前保留站或緩沖站的狀態(tài)決定是否發(fā)射，同時在發(fā)射階段進(jìn)行寄存器換名工作。

圖1 Tomasulo算法的整體結(jié)構(gòu)簡圖

(2) 執(zhí)行。若還有操作數(shù)沒有準(zhǔn)備好，則監(jiān)視CDB等待源操作數(shù)。當(dāng)操作數(shù)計算出來之后，就放到相應(yīng)的保留站中，當(dāng)指令所需要的原操作數(shù)均出現(xiàn)之后，就可以執(zhí)行該運(yùn)算。執(zhí)行過程中必須檢測寫寫沖突。

(3) 寫回結(jié)果。當(dāng)結(jié)果出來之后，送至CDB，進(jìn)而寫回到寄存器中，或被其他保留站讀取。

2 指令系統(tǒng)

實驗使用的指令系統(tǒng)必須能夠適應(yīng)處理器的體系結(jié)構(gòu)[11]。指令系統(tǒng)參考了MIPS等精簡的指令集[12]的設(shè)計，適合流水和動態(tài)調(diào)度的架構(gòu)，共有25條，基本功能完善，每條指令的指令碼都是16 b，具體指令如表1所示。

3 處理器結(jié)構(gòu)

在處理器實現(xiàn)過程中，由于采用了Tomasulo算法，最終版本的處理器實現(xiàn)了順序發(fā)射指令而亂序執(zhí)行，可以同時容納4個ALU運(yùn)算操作、2個乘除法操作、2個內(nèi)存讀和2個內(nèi)存寫操作。處理器整體結(jié)構(gòu)如圖2所示。

主要部分說明如下：

Decoder。指令譯碼，產(chǎn)生操作數(shù)、操作碼及控制信號。

指令隊列。由7個指令項組成，存儲準(zhǔn)備發(fā)射的指令。

Issue control?？刂浦噶畎l(fā)射。指令發(fā)射到哪個站，告訴指令發(fā)射到哪里去，表明該條指令的跳轉(zhuǎn)指令種類等。

寄存器堆。每項都是19位，前3位是數(shù)據(jù)來源的保留站或buffer的編號，后16位是數(shù)據(jù)，與數(shù)據(jù)總線上的數(shù)據(jù)進(jìn)行同步。

ALU保留站。有4個保留站項組成，存儲操作數(shù)。

表1 指令系統(tǒng)

圖2 處理器結(jié)構(gòu)簡圖

Store/Load buffer訪存時的暫存數(shù)據(jù)。

MUL 保留站?？刂葡蚰囊粋€空閑保留站內(nèi)發(fā)射指令；對于處于忙狀態(tài)的保留站，把數(shù)據(jù)總線上的數(shù)據(jù)寫回。

LS control logic?？刂谱x寫緩沖站工作。

ALU。完成主要算術(shù)邏輯運(yùn)算操作。

Wirteback control logic：寫回控制邏輯，優(yōu)先順序是：先乘法器的運(yùn)算結(jié)果，其次是ALU的運(yùn)算結(jié)果，最后是緩沖器的結(jié)果。

內(nèi)存訪問仲裁。用來處理指令中的內(nèi)存讀寫和取指操作時的內(nèi)存訪問之間的沖突用的。

mul 乘法器。完成乘法操作。

4 處理器測試

4.1 功能檢測

功能檢測主要是測試CPU的功能是否和預(yù)期的相符。由于使用了Tomasulo算法，其特色為使用寄存器換名技術(shù)，順序發(fā)射指令但是亂序執(zhí)行，寫回結(jié)果的順序不定，在程序最終的時候才能確定最后的結(jié)果[13]。因此在運(yùn)行的過程當(dāng)中情況是很復(fù)雜的。

首先測試了所有指令單條運(yùn)行，使用DebugController跟蹤指令運(yùn)行，驗證指令運(yùn)行正確，本測試結(jié)果正確，對此，本文不做進(jìn)一步討論。

接著由于Tomasulo算法解決了相關(guān)性，避免了沖突，因此需要對相關(guān)性進(jìn)行測試，采用了以下測試樣例，其中包括了相關(guān)性的分析(圖3的箭頭標(biāo)明了有相關(guān)性的指令)。

可以看出，這幾條指令之間存在著WRW、RAW、WAR三種不同的相關(guān)性[14]。使用DebugController跟蹤這段指令的運(yùn)行，可以觀察寄存器、保留站和數(shù)據(jù)總線及其標(biāo)記位的變化，變化過程如圖4所示。

圖4 指令的執(zhí)行過程

圖中標(biāo)示了哪些保留站或者寄存器的數(shù)據(jù)是可用的，且對應(yīng)的編號表示在等待那個站的輸出結(jié)果。ALU0的編號為000，ALU1的編號為001；databus即數(shù)據(jù)總線中的標(biāo)記位表示當(dāng)前總線上的數(shù)據(jù)來自哪一個保留站，當(dāng)寄存器和保留站檢測到這個編號等于自己等待的編號時，就將數(shù)據(jù)寫入并且將標(biāo)記位置為有效。保留站中的數(shù)字表示當(dāng)前站中存放的是那一條指令，*表示該站中的源操作數(shù)已經(jīng)準(zhǔn)備好。從圖中可以看出，這種方式正確的解決了指令之間的各種相關(guān)性，保證了最后寫回結(jié)果是正確的，但是在程序中位于前面的指令即先發(fā)射的指令未必先完成，從寄存器的數(shù)據(jù)中可以看出，同時一些中間結(jié)果是沒有寫回寄存器的，而是寫回了保留站中，寄存器中只寫入最新的數(shù)據(jù)。

內(nèi)存讀取要處理兩方面的內(nèi)容：一個方面是load和store指令之間的相關(guān)，另外一個方面是指令讀取和load/store指令之間的沖突。為了消除訪問內(nèi)存時的相關(guān)與冒險，使用讀寫隊列的思想，控制store和load按照程序原來的順序執(zhí)行。而其他的運(yùn)算操作則可以亂序執(zhí)行。觀察下面的指令，其中包括有先后順序的load/store指令：

;TEST4 LOAD R3,R1

SET R1,0X20 STORE R2,R3

SET R2,0X21 LOAD R3,R2

SET R4,0X22 STORE R4,R3

最后結(jié)果正確，在0X20/0X21/0X22的位置寫入了相同的數(shù)，都和原來0X20位置的數(shù)相同。用DebugController跟蹤指令運(yùn)行，可以看到地址總線上的數(shù)依次為:0x1，0x2，0x3，0x4,0x5,0x5,0x6,0x6,0x7,0x8,0x8,0x8,0x9,0x20,0xa,0x21,0x21,0xb,0x22。

下劃線的部分表示store/load指令執(zhí)行時占用了地址和數(shù)據(jù)總線，可以看出其順序和程序中指令的順序相同。同時在存在內(nèi)存讀寫操作需要占用總線時，PC保持原來的數(shù)不變，保證了在總線歸還給指令讀寫時能夠正確地按照既定順序執(zhí)行。在此基礎(chǔ)上又進(jìn)行了其他一些情況的測試，運(yùn)行結(jié)果均正確。

從以上的幾項檢測結(jié)果可以看出，處理器工作基本正確，另外由于算法的特色之一是亂序執(zhí)行，寫回結(jié)果的順序和程序的順序不一致，而且一些運(yùn)算中間結(jié)果未必寫回，當(dāng)幾條指令都要改變一個目的寄存器時，可能只是最后一條指令執(zhí)行了寫回寄存器的操作，因此調(diào)試過程的中間結(jié)果可能是不正確的，這給調(diào)試帶來了困難。

4.2 性能評測

這一部分主要是針對算法的特點(diǎn)，在以上功能正確完善的基礎(chǔ)上作一些性能上的評測，和其他一些CPU的結(jié)構(gòu)作比較(比如一般的多周期CPU，五段流水線的CPU等)，希望能夠根據(jù)一些量化的結(jié)果說明這種體系結(jié)構(gòu)的優(yōu)缺點(diǎn)，主要量化指標(biāo)是CPI以及流水線暫停的比率。

首先給出一些運(yùn)算、訪存等操作，不一定有特定的意義，只是為了測試設(shè)計的性能如何，給出量化的結(jié)果。將下面的測試程序循環(huán)100次，觀察總共用了多少個時鐘周期。

;TEST6 LOAD R4,R5

SET R5,0X200 STORE R5,R2

SET R6,0X300 LOAD R3,R5

SET R1,0X1F STORE R5,R1

SET R4,0XFF LOAD R2,R5

SET R2,0X3C STORE R6,R2

AND R1,R2 STORE R6,R3

OR R2,R1 STORE R6,R4

MVRR R3,R2 SET R5,0

SUB R3,R2 SET R4,0

AND R4,R3 SET R3,0

NOT R4 SET R2,0

STORE R5,R3 SET R1,0

1: BEQZ R0,1B

將上述程序循環(huán)執(zhí)行100次，指令數(shù)為3704，測試結(jié)果為：Stall_time=2502,Total_time=6206,CPI=6206/3704≈1.68。

暫停率即Stall的周期占總周期數(shù)目的百分比為2502/6206≈40.3%。這個數(shù)目在一定程度上反映了程序自身的相關(guān)度。從結(jié)果中看出，暫停率較大，原因為程序本身的相關(guān)性導(dǎo)致，還有就是內(nèi)存讀寫數(shù)據(jù)和取指爭用數(shù)據(jù)總線。在流水段分為4級(要包括從內(nèi)存中取指的周期)且指令相關(guān)性較大的情況下CPI為1.68，相當(dāng)于一個半周期左右執(zhí)行一條指令，對于現(xiàn)在我們簡化的Tomasulo算法來說，性能還是可以的。

所設(shè)計的處理器對于動態(tài)調(diào)度，亂序執(zhí)行的方法處理指令和功能部件之間的相關(guān)性是很有優(yōu)勢的。下面是兩條向寄存器中置立即數(shù)的指令：

;TEST7

MLRD R2,3

MHRD R2,1 ;SET R2,0X103

MHRD R1,1

MLRD R1,1 ;SET R1,0X101

HALT

結(jié)果如下：stall_time=2,total_time=9,CPI=9/4=2.25。

流水線的暫停率為22.2%。

圖5是針對此程序的CPI數(shù)值以及暫停次數(shù)的比較，1是Tomasulo算法的處理器，2至4為以前設(shè)計的多周期無流水線、5級流水線無旁路，以及五級流水加旁路[15]的四種體系結(jié)構(gòu)的處理器。

圖5 四種體系結(jié)構(gòu)處理相關(guān)性的性能比較

這個測試程序很短，但也可以看出在相關(guān)性的處理問題上，Tomasolu算法的性能至少和帶有旁路的5段流水線CPU等同，同時針對于這一個測試程序來說，其CPI也是最少的。

通過以上的測試可以看出：Tomasolu算法指令相關(guān)性的處理，指令并行性的利用，指令隊列預(yù)取策略等方面是很有優(yōu)勢的；這種結(jié)構(gòu)適于處理大量運(yùn)算，能夠挖掘出較高指令并行度的程序；同時根據(jù)實際情況，指令隊列以及保留站的具體數(shù)目要做合適的調(diào)整和選擇。不足和復(fù)雜的地方在于異常和中斷發(fā)生后的處理比順序執(zhí)行的指令麻煩；緩存占用很多，是以空間換時間的做法；同時由于判斷邏輯較復(fù)雜，不容易達(dá)到較高的時鐘頻率。

5 結(jié) 語

計算機(jī)組成與系統(tǒng)結(jié)構(gòu)的硬件實驗是實驗教學(xué)過程中的一個難點(diǎn)，需要以一個處理器為基礎(chǔ)，實驗工作量比較大。本文探索了一個具體的實驗樣例，實現(xiàn)了一個采用Tomasolu算法的四級流水線處理器，并對設(shè)計進(jìn)行了功能和性能測試，對以后的課程實驗提供了很好的基礎(chǔ)，實驗教學(xué)應(yīng)用價值很高。

[1] 袁春風(fēng)，陳貴海，黃宜華,等. “計算機(jī)組織與系統(tǒng)結(jié)構(gòu)”課程的教學(xué)現(xiàn)狀和改革思路[J]. 計算機(jī)教育，2009，16:153-156.

YUAN Chun-feng,CHEN Gui-hai,HUANG Yi-hua,etal. The Situation of Teaching and the Thinking for Reform on Computer Organization and Architecture Course[J]. Computer Education,2009,16:153-156.

[2] 張晨曦，李江峰，劉 依. 組成原理與系統(tǒng)結(jié)構(gòu)模擬實驗系統(tǒng)的設(shè)計與開發(fā)[J]. 計算機(jī)工程與科學(xué)，2011，33(A1):1-4.

ZHANG Chen-xi,LI Jiang-feng,LIU Yi. Design and Implementation of a Simulator-Based Experiment System for Computer Organization and Architecture Course[J]. Computer Engineering&Science,2011,33(A1):1-4.

[3] 熊亮春，計算機(jī)體系結(jié)構(gòu)模擬器的設(shè)計與實現(xiàn)[D].上海: 同濟(jì)大學(xué)，2008.

[4] 孫 振，肖 儂，賴明澈,等. 計算機(jī)系統(tǒng)結(jié)構(gòu)遠(yuǎn)程實驗平臺的設(shè)計與實現(xiàn)[J]. 中國科技論文，2011(1):74-78.

SUN Zhen,XIAO Nong,LAI Ming-che,etc. Design and implementation of remote experiment system for computer architecture courses[J]. China Sciencepaper,2011(1):74-78.

[5] 何克東，王恒才. 高性能CPU設(shè)計實驗平臺及其應(yīng)用[J]. 實驗室研究與探索，2007(12):212-214.

HE Ke-dong,WANG Heng-cai. High-powered Experiment Platform for CPU Design and its Application[J]. Research and Exploration in Laboratory,2007(12):212-214.

[6] 湯志忠，楊春武. 開放式實驗CPU設(shè)計[M]. 北京：清華大學(xué)出版社，2007.

[7] 蔡啟先，王智文，何海釗. 計算機(jī)系統(tǒng)結(jié)構(gòu)課程流水線技術(shù)教學(xué)研究與實踐[J]. 黑龍江科技信息，2008(14):177-179.

CAI Qi-xian,WANG Zhi-wen,HE Hai-zhao. Research and Practice on Pipeline Teaching in Computer Architeture Course[J]. Heilongjiang Science and Technology Information,2008(14):177-179.

[8] John L.Hennessy, David A. Patterson. Computer Architecture: A Quantitative Approach [M]. 5版. 北京：機(jī)械工業(yè)出版社. 2012.

[9] 翟召岳. 基于32位超標(biāo)量處理器的保留站設(shè)計[J]. 大眾科技，2013，11:3-7.

ZHAI Shao-yue. Reservation station design based on 32 bits superscalar processors[J]. Popular Science&Technology,2013,11:3-7.

[10] 王 磊. Tomasulo算法與記分牌調(diào)度算法研究[J]. 自動化技術(shù)與應(yīng)用，2013(6):23-26.

WANG Lei. The Tomasulo Algorithmand Scoreboard Scheduling Algorithm[J]. Techniques of Automation and Applications,2013(6):23-26.

[11] 于 洋，肖鐵軍，丁 偉. 面向教學(xué)的16位CISC微處理器的設(shè)計[J]. 計算機(jī)工程與設(shè)計，2010(31):3584-3587.

YU Yang,XIAO Tie-jun,DING Wei. Design of 16 bit CISC microprocessor for teaching[J]. Computer Engineering and Design,2010(31):3584-3587.

[12] 劉 明，蔡啟先，余祖峰. 改進(jìn)MIPS 指令集模擬方法的研究[J]. 廣西工學(xué)院學(xué)報，2009(12):54-57.

LIU Ming,CAI Qi-xian,YU Zu-feng. Research on Improved MIPS instruction set simulation[J]. Journal of Guangxi University of Technology,2009(12):54-57.

[13] 趙慶敏，邱 嵐，杜宏露，等. 超標(biāo)量技術(shù)及結(jié)構(gòu)研究與應(yīng)用[J]. 微計算機(jī)應(yīng)用，2007(2):208-210.

ZHAO Qing-min,QIU Lan,DU Hong-lu,etal. Research and Application on Superscalar Processor[J]. Microcomputer Applications,2007(2):208-210.

[14] 鄧正宏，康慕寧，羅 旻. 超標(biāo)量微處理器研究與應(yīng)用[J]. 微電子學(xué)與計算機(jī)，2004(9):59-63.

DENG Zheng-hong,KANG Mu-ning,LUO Ming. Research and Application on Superscalar Microprocessors[J]. Microelectronics & Computer,2004(9):59-63.

[15] 秘海曉. 基于FPGA的32位五級流水線CPU的研究與設(shè)計[D]. 天津：河北工業(yè)大學(xué)， 2012.