摘 要：介紹了重排序緩沖器實(shí)現(xiàn)思想與硬件結(jié)構(gòu)，并提出了增加結(jié)果鎖存器和將重排序緩沖器由集中式改為分布式的設(shè)計，來降低重排序緩沖器設(shè)計復(fù)雜度的方案。
關(guān)鍵詞：重排序緩沖器；寄存器重命名；超標(biāo)量；亂序執(zhí)行；低復(fù)雜度
?
隨著科技的發(fā)展，人們對計算機(jī)處理速度的要求越來越高。為了提高微處理器的性能，人們提出了超標(biāo)量流水線技術(shù)。超標(biāo)量技術(shù)是指CPU在每個時鐘周期內(nèi)可以完成一條以上指令的并行執(zhí)行技術(shù)[1]。實(shí)現(xiàn)多指令并行執(zhí)行的關(guān)鍵在于亂序執(zhí)行。亂序執(zhí)行是指不按照指令原始順序執(zhí)行的技術(shù)。而實(shí)現(xiàn)指令亂序執(zhí)行的關(guān)鍵是用到了寄存器重命名技術(shù)。寄存器重命名是用一個或者多個虛擬寄存器來代替真實(shí)的數(shù)據(jù)寄存器的硬件猜測方法。重排序緩沖器ROB(Reorder Buffer)是超標(biāo)量處理器中基于寄存器重命名技術(shù)的一種實(shí)現(xiàn)結(jié)構(gòu)，在MIPS R10000、Intel Pentium系列處理器和IBM Power系列處理器中得到了廣泛的應(yīng)用。
本文在介紹重排序緩沖器原理和實(shí)現(xiàn)的基礎(chǔ)上，分析了重排序緩沖器的復(fù)雜度問題，即重排序緩沖器是一個占用大量寄存器資源并且有多個并行讀寫端口的復(fù)雜器件，耗費(fèi)大量的功耗，容易出現(xiàn)不必要的延時。文中通過適當(dāng)?shù)母倪M(jìn)方法，優(yōu)化了重排序緩沖器的結(jié)構(gòu)和性能。
1 超標(biāo)量處理器中的寄存器重命名技術(shù)
1.1?超標(biāo)量處理器
現(xiàn)今的超標(biāo)量處理器都是通過一個時鐘周期內(nèi)發(fā)射多條指令并且亂序執(zhí)行這些指令來實(shí)現(xiàn)多指令并行技術(shù)的。
一般流水線技術(shù)的局限在于采用了按序發(fā)射指令的機(jī)制，指令必須按照原來的順序執(zhí)行。即如果流水線中出現(xiàn)停頓，那么后續(xù)指令則無法前行。因此，若2條緊挨著的指令存在相關(guān)關(guān)系就會引起停頓。對于有多個功能部件的機(jī)器，會造成這些功能的閑置。亂序執(zhí)行技術(shù)允許指令不按照原來的發(fā)射順序執(zhí)行，哪條指令的操作數(shù)已經(jīng)就緒，就可以提前執(zhí)行。這樣可有效提高指令的執(zhí)行效率。
1.2?寄存器重命名
亂序執(zhí)行帶來的數(shù)據(jù)相關(guān)和控制相關(guān)的問題，實(shí)質(zhì)上是由于使用了共同的寄存器資源保存了不同的變量值所引發(fā)的[2]。若采用更名的方法，用2個不同的寄存器來保存這2個變量，出現(xiàn)相關(guān)的2條指令就能并發(fā)執(zhí)行，不會引起性能的損失。Tomasulo算法就是一種基于寄存器重命名的動態(tài)調(diào)度算法，并在超標(biāo)量流水線中得到廣泛應(yīng)用。
2?重排序緩沖器的分析及相關(guān)問題的提出
2.1?重排序緩沖器的原理
亂序執(zhí)行會帶來數(shù)據(jù)沖突和控制沖突，數(shù)據(jù)沖突問題可以單純地采用保留站的調(diào)度技術(shù)予以解決，控制沖突的解決則要利用分支預(yù)測技術(shù)，而分支預(yù)測常常會帶來預(yù)測的失敗。如果僅僅允許亂序執(zhí)行而不順序?qū)懟氐脑挘蜁霈F(xiàn)不可恢復(fù)的預(yù)測失敗。因此，在Tomasulo算法的基礎(chǔ)上，又采用了一種基于硬件的猜測技術(shù)—重排序緩沖器。
重排序緩沖器本質(zhì)上也是一種寄存器重命名技術(shù)，重排序緩沖器提供了額外的寄存器，就像Tomasulo算法中的保留站擴(kuò)展了寄存器堆一樣。重排序緩沖器在指令執(zhí)行結(jié)束和指令提交之間保存指令的執(zhí)行結(jié)果。因此，重排序緩沖器可以為指令提供源操作數(shù)，就像Tomasulo算法中的保留站一樣提供操作數(shù)[3]。在Tomasulo算法中，一旦一條指令寫入它的執(zhí)行結(jié)果，任何后邊的指令都可以在寄存器堆中讀取該結(jié)果，在指令提交之前，數(shù)據(jù)寄存器不用得到更新，由重排序緩沖器在指令執(zhí)行完畢和提交之前提供操作數(shù)。如圖1所示，重排序機(jī)制類似于一種旁路機(jī)制，這樣可將在重排序緩沖器中保存的某個指令的結(jié)果送到等待它的執(zhí)行單元中，不用經(jīng)過數(shù)據(jù)寄存器[4]。
相比提供操作數(shù)，重排序緩沖器另一個最大的作用是保證指令有序提交和異常行為恢復(fù)執(zhí)行[4]。提交階段必須按一開始程序的最初順序提交結(jié)果到指定的存儲單元。在指令譯碼之后、亂序發(fā)射之前，每條指令已經(jīng)在重排序緩沖器中按序申請到存儲單元。當(dāng)指令執(zhí)行完畢，重排序緩沖器就可以保證最終結(jié)果順序提交。一旦出現(xiàn)中斷或異常行為，則廢除未提交的剩余所有執(zhí)行結(jié)果，進(jìn)入中斷處理或從正確的指令處重新開始執(zhí)行。如圖2所示。
?
2.2?重排序緩沖器的硬件實(shí)現(xiàn)
重排序緩沖器是用于亂序執(zhí)行后恢復(fù)指令原來順序的一種硬件結(jié)構(gòu)，以達(dá)到指令結(jié)果順序提交的目的。可以把重排序緩沖器看作是一個包含頭指針和尾指針的堆棧FIFO[5]。每條指令進(jìn)入流水線的時候，按照程序的最先順序都在重排序緩沖器中依次占據(jù)了一列條目，等指令執(zhí)行完畢，按照先入先出的順序依次提交指令。當(dāng)發(fā)生中斷或者異常行為時，也能恢復(fù)原來的執(zhí)行順序。重排序緩沖器主要由下列幾個字段構(gòu)成：
(1) 指令字段：記錄指令；
(2) 目標(biāo)寄存器字段：記錄指令結(jié)果要寫入的數(shù)據(jù)寄存器的地址；
(3) 數(shù)值字段：記錄指令的最后結(jié)果，如果結(jié)果還沒有得出，則記錄得出該結(jié)果的指令在ROB中的地址；
(4) 完成字段：記錄指令是否執(zhí)行完畢。
重排序緩沖器在超標(biāo)量流水線中的實(shí)現(xiàn)如圖3所示。運(yùn)算單元FU(Floating Unit)計算出結(jié)果后，將其寫到重排序緩沖器中。同時通過前置定向總線FB(Forwarding? Bus)送給發(fā)射隊列IQ(Instruction Queue)中正在等待該操作數(shù)的指令。重排序緩沖器中存儲的結(jié)果將在指令退休時送給相應(yīng)的數(shù)據(jù)寄存器ARF(Architecture Register Files)中。在指令發(fā)射時，操作數(shù)的值按照具體情況，既可以從數(shù)據(jù)寄存器中獲得，也可以從重排序緩沖器中獲得，如果值還沒有計算出來，指令要在發(fā)射隊列中等待，直到前置定向總線將運(yùn)算結(jié)果送到發(fā)射隊列指定的位置。
?
?
3?重排序緩沖器的復(fù)雜性和優(yōu)化方案
3.1?重排序緩沖器的復(fù)雜性
這類的重排序緩沖器通常以允許多端口同時讀寫的寄存器堆的方式實(shí)現(xiàn)。在一個N指令發(fā)射的超標(biāo)量流水線中重排序緩沖器至少需要2N個讀端口，以供N條指令可以在一個時鐘周期內(nèi)讀取所需要的2N個操作數(shù)。至少需要N個寫端口，以供N條指令一個時鐘周期內(nèi)將結(jié)果寫入重排序緩沖器中。
多端口寄存器堆的實(shí)現(xiàn)會加劇設(shè)計的復(fù)雜度，并且實(shí)際的端口數(shù)有時還會因?yàn)槌霈F(xiàn)雙倍位寬的操作數(shù)而加倍。在通常情況下，可以采用雙重排序緩沖器并行存在的方式，以減少每個重排序緩沖器端口的數(shù)量。但是，雙倍位寬和單倍位寬的數(shù)據(jù)常常一起存在，倘若采用雙ROB的形式將不可避免的帶來極大地浪費(fèi)。
另外，隨著端口數(shù)的增加，寄存器堆的面積也呈快速增長趨勢，這必將導(dǎo)致時序的延遲和功耗的增加。因此，合理地優(yōu)化重排序緩沖器的結(jié)構(gòu)設(shè)計日益成為人們關(guān)心的焦點(diǎn)。
3.2 重排序緩沖器結(jié)構(gòu)的優(yōu)化
一個優(yōu)化的方法是去除重排序緩沖器上原操作數(shù)讀端口用以簡化寄存器堆的設(shè)計。當(dāng)指令的結(jié)果從運(yùn)算單元送到重排序緩沖器中的同時，通過前置定向總線送到指令發(fā)射單元中等待該操作數(shù)的指令隊列。之后，該操作數(shù)提交給數(shù)據(jù)寄存器，指令分配單元無法再從重排序緩沖器中讀此操作數(shù)。當(dāng)操作數(shù)需要第二次被提取時，而該操作數(shù)還沒有被提交給數(shù)據(jù)寄存器時，常常會因?yàn)闊o法讀重排序緩沖器中的值，出現(xiàn)延遲，造成流水線的阻塞。因此，可以參考計算機(jī)中緩存Cache的設(shè)計方法，如圖4所示，加一個存儲單元數(shù)遠(yuǎn)少于重排序緩沖器的數(shù)據(jù)鎖存器RL(Retention Latches)以存儲指令結(jié)果，這樣執(zhí)行結(jié)束的指令結(jié)果在寫入重排序緩沖器的同時也并行寫入了數(shù)據(jù)鎖存器。為了在增加數(shù)據(jù)鎖存器的基礎(chǔ)上而不增加設(shè)計的復(fù)雜度，數(shù)據(jù)鎖存器的存儲量應(yīng)該盡可能的小，不妨采用LRU算法進(jìn)行鎖存器內(nèi)部數(shù)據(jù)的替換管理。LRU是廣泛應(yīng)用于計算機(jī)緩存Cache中的一種數(shù)據(jù)替換算法，為了減少替換那些可能不久要用到的信息，需要記錄數(shù)據(jù)塊的使用次數(shù)來預(yù)測未來的使用情況[6]。這樣在指令被重排序緩沖器提交給數(shù)據(jù)寄存器之前，數(shù)據(jù)鎖存器可以有效解決操作數(shù)延遲獲得的問題。
?
另一個優(yōu)化的方法，從Tomasulo算法的分布式保留站中得到啟發(fā)，將重排序緩沖器由集中式改為分布式，如圖5所示。這樣可以將一個多端口讀寫的重排序緩沖器簡化成多個單端口讀寫的重排序緩沖器。這種方法簡化了原來集中式寄存器堆多端口同時讀寫的復(fù)雜度，但也帶來了因?yàn)槎鄠€分散的重排序緩沖器中指令提交的排序問題。為此，可以在譯碼時給每一條指令加上標(biāo)志位，指明該指令在程序中的順序，并且標(biāo)注該指令發(fā)送給哪一個運(yùn)算單元。這樣，在每個緩沖器提交指令或者預(yù)測失敗時，便能在多緩沖器間協(xié)調(diào)讀取指令或者結(jié)果。
?
3.3?性能分析
根據(jù)對各種模型的分析，列出表1中的順序執(zhí)行、改進(jìn)前的硬件猜測法以及改進(jìn)后的硬件猜測法3種實(shí)現(xiàn)形式，采用Verilog HDL語言對結(jié)構(gòu)進(jìn)行描述，采用Synopsy公司的Design Compiler工具在0.18 μm的CMOS工藝下進(jìn)行綜合和時序分析，得出性能的比較如表1所列。
?
從表1中可以看出，在普通的順序執(zhí)行算法下，硬件路徑延遲較大，但是面積最小；改進(jìn)前的硬件猜測算法路徑延遲最小，但是面積最大，帶來了設(shè)計上復(fù)雜度和功耗損失較大的問題；采用改進(jìn)后的硬件猜測算法以后，雖然路徑延遲比改進(jìn)前大，但是面積相對減少很多，并且路徑的延遲相比順序執(zhí)行仍然減少了不少。因此，采用改進(jìn)后的硬件猜測算法在減少面積的情況下得到了可觀的效果。
超標(biāo)量處理器中的重排序緩沖器對于實(shí)現(xiàn)指令的亂序執(zhí)行和順序提交起著重要的作用。隨著對指令并行度要求的不斷提高，重排序緩沖器的設(shè)計結(jié)構(gòu)會越來越復(fù)雜。本文提出了幾點(diǎn)改進(jìn)方法，通過減少單個緩沖器上讀端口的數(shù)目，有效地降低了重排序緩沖器的設(shè)計復(fù)雜度，這對將來的超標(biāo)量處理器的設(shè)計有著深遠(yuǎn)影響。
參考文獻(xiàn)
[1]?STEVEN W, NADER B. Modeled and measured instruction fetching performance for superscalar microprocessors. IEEE transaction on parallel and distributed, 1998,9(6).
[2]?JOHN P,MIKKO H L.現(xiàn)代處理器設(shè)計——超標(biāo)量處理器基礎(chǔ)[M].北京：電子工業(yè)出版社,2004.
[3]?JOHN L H,DAVID A P.計算機(jī)系統(tǒng)結(jié)構(gòu)——量化研究方法(第3版)[M].北京：電子工業(yè)出版社，2004.
[4]?鄧正宏，康慕寧，羅旻. 超標(biāo)量微處理器的研究和應(yīng)用[J].微電子學(xué)與計算機(jī)，2004，21(9)：59-63.
[5]?TAREK M T, WILLS D S. An instruction throughput model of Superscalar Processors[J]. IEEE Transactions On Computers,2008,57(3).
[6]?李學(xué)干. 計算機(jī)系統(tǒng)結(jié)構(gòu)[M]. 西安：西安交通大學(xué)出版社,2007.