基于存儲(chǔ)資源迭代重用的低成本寄存器重命名方法

鄢傳欽，孟建熠

(浙江大學(xué)超大規(guī)模集成電路設(shè)計(jì)研究所，浙江杭州310027)

0 引言

寄存器重命名是超標(biāo)量流水線中實(shí)現(xiàn)處理器內(nèi)核指令動(dòng)態(tài)調(diào)度的關(guān)鍵技術(shù)，解決了指令之間的反相關(guān)(WAR)和輸出相關(guān)(WAW)問(wèn)題［1］。隨著超標(biāo)量處理器指令級(jí)并行性的不斷挖掘和流水線進(jìn)一步加深，指令發(fā)射窗口進(jìn)一步增大［2］，停留在流水線中的“飛行”指令也隨之增加，因此，必須增加物理寄存器的數(shù)量來(lái)完成指令的調(diào)度［3］，然而寄存器資源的增大給處理器帶來(lái)了寄存器的訪問(wèn)延遲、面積、功耗等一系列問(wèn)題［4，5］。這些問(wèn)題的存在使得通過(guò)簡(jiǎn)單地增加物理寄存器的資源來(lái)提高處理器的性能變得舉步維艱［6］，因此，提高物理寄存器的利用效率以達(dá)到提高處理器性能的同時(shí)節(jié)省資源變得尤為重要。

傳統(tǒng)的寄存器重命名方法［7］為了降低設(shè)計(jì)的復(fù)雜度，在譯碼階段為指令分配物理寄存器，在指令退休寫(xiě)回時(shí)釋放寄存器資源。其問(wèn)題在于物理寄存器的使用效率太低，一旦發(fā)生物理寄存器的結(jié)構(gòu)沖突，流水線必須停頓直到資源沖突消除。

文獻(xiàn)［4，5］提出了一種通過(guò)兩級(jí)映射推遲物理寄存器的分配的重命名方法。這種方法在譯碼階段通過(guò)第一級(jí)映射為指令分配虛擬寄存器。在指令發(fā)［5］或執(zhí)行完成［4］時(shí)通過(guò)第二級(jí)映射為指令分配真實(shí)的物理寄存器。兩級(jí)映射的方法雖然能夠通過(guò)推遲實(shí)際物理寄存器的分配來(lái)提高利用效率，卻很大程度上增加了硬件設(shè)計(jì)的復(fù)雜度。

本文提出一種迭代重用物理寄存器的方法，增加指令分發(fā)時(shí)實(shí)際可分配的物理寄存器數(shù)量，并通過(guò)在指令發(fā)射隊(duì)列中引入物理寄存器占用的相關(guān)性信息，在發(fā)生物理寄存器結(jié)構(gòu)沖突的情況下解除流水線的停頓，有效地提高了流水線的執(zhí)行效率。該方法不但提高了物理寄存器的利用率，達(dá)到節(jié)省物理寄存器資源的目的，同時(shí)避免了文獻(xiàn)［4，5］兩級(jí)映射方法帶來(lái)的硬件設(shè)計(jì)復(fù)雜度。

1 物理寄存器性能研究

重命名映射表和用作重命名的物理寄存器共同完成了ISA寄存器［8］的重命名，解決指令之間的數(shù)據(jù)相關(guān)。重命名映射表記錄了最新的ISA寄存器到物理寄存器的映射關(guān)系，典型的重命名映射表通過(guò)譯碼得到的ISA寄存器號(hào)來(lái)索引物理寄存器，因此，重命名映射表同ISA寄存器一一對(duì)應(yīng)。而物理寄存器則擔(dān)負(fù)著指令執(zhí)行結(jié)果的緩存，操作數(shù)的旁路以及結(jié)果的按序回寫(xiě)。為便于對(duì)物理寄存器進(jìn)行獨(dú)立的研究，本文的研究將基于獨(dú)立的物理寄存器結(jié)構(gòu)［1］。

為了保證流水線效率的充分發(fā)揮，超標(biāo)量流水線中的物理寄存器的數(shù)量必須達(dá)到流水線中“飛行”指令的數(shù)量。隨著流水線的加深和指令發(fā)射寬度的增大，物理寄存器的數(shù)量也將隨之增加。而當(dāng)物理寄存器的數(shù)量受到訪問(wèn)延遲、面積、功耗、讀寫(xiě)端口壓力各方面的限制時(shí)，其數(shù)量必將無(wú)法滿足充分發(fā)揮流水線效率的條件，物理寄存器的數(shù)量將在很大程度上影響處理器的性能。表1是一個(gè)8級(jí)流水線四發(fā)射超標(biāo)量嵌入式處理器的IPC(instructions per cycle)與物理寄存器數(shù)量變化的關(guān)系。實(shí)驗(yàn)使用嵌入式powerstone測(cè)試程序，測(cè)試結(jié)果是處理器執(zhí)行各個(gè)程序的IPC平均值。處理器采用保留站和重排序緩存的大小分別為64個(gè)，并且保證足夠大的指令和數(shù)據(jù)cache，這樣整個(gè)執(zhí)行內(nèi)核的性能影響將主要來(lái)自物理寄存器的結(jié)構(gòu)沖突。表1數(shù)據(jù)顯示，當(dāng)物理寄存器數(shù)量較少時(shí)，IPC值隨隨著物理寄存器數(shù)量的增加而線性增長(zhǎng);當(dāng)物理寄存器數(shù)量達(dá)到一定數(shù)量之后，IPC變化趨于平緩并接近極限性能，處理器性能對(duì)物理寄存器數(shù)量的依賴性變?nèi)?。要使CPU的性能接近極限，物理寄存器的數(shù)量需要達(dá)到44個(gè)以上，這無(wú)疑將是一個(gè)很大的資源消耗，對(duì)處理器的面積、功耗、寄存器訪問(wèn)延遲將會(huì)是不小的壓力。而反之減少物理寄存器的資源，結(jié)構(gòu)沖突加劇造成的流水線停頓必然將成為處理器性能的瓶頸。本文重點(diǎn)研究一種低硬件成本的寄存器重命名方法。

表1 傳統(tǒng)方法寄存器數(shù)量與IPC性能分析Tab 1 Number of registers and the IPC performance analysis in traditional method

2 物理寄存器迭代重用方法

傳統(tǒng)的寄存器重命名只要發(fā)生物理寄存器的資源沖突，流水線即產(chǎn)生停頓，即使指令發(fā)射隊(duì)列仍有空閑表項(xiàng)。因此，如果能夠做到即使發(fā)生資源沖突時(shí)處理器仍然發(fā)射指令，那么處理器內(nèi)核流水線的指令級(jí)并行性將進(jìn)一步得到提升。另一方面，傳統(tǒng)的寄存器重命名方法中，物理寄存器被分配時(shí)即被占用，而實(shí)際有效占用時(shí)間應(yīng)是從指令執(zhí)行完成到結(jié)果寫(xiě)回。當(dāng)資源發(fā)生沖突時(shí)，后續(xù)的指令剛開(kāi)始譯碼，它們實(shí)際上并不真正占用物理寄存器的存儲(chǔ)空間，此時(shí)后續(xù)的指令應(yīng)仍能繼續(xù)先分配并發(fā)射執(zhí)行。本文的核心思想是將重命名寄存器資源沖突的判斷條件從原先的分配即產(chǎn)生占用沖突，變?yōu)閷?shí)際動(dòng)態(tài)結(jié)果存儲(chǔ)時(shí)才算占用沖突，從而降低沖突概率?；谶@一原理，本文通過(guò)物理寄存器迭代重用的方法，消除處理器因物理寄存器資源沖突導(dǎo)致的流水線停頓。

這種方法通過(guò)增加物理寄存器中的指令信息，讓每一個(gè)物理寄存器被迭代利用為n個(gè)物理寄存器，也就是說(shuō)每一個(gè)物理寄存器可以被分配給n條指令。假設(shè)物理寄存器的個(gè)數(shù)為m，物理寄存器迭代使用的次數(shù)為n，理論上能夠分配到物理寄存器的指令數(shù)將為n×m條，只要指令發(fā)射隊(duì)列的容量足夠大，這n×m條指令都將被譯碼并寫(xiě)入指令發(fā)射隊(duì)列等待發(fā)射。如圖1所示，假設(shè)指令x的目的寄存器r0被映射為物理寄存器PR1，隨著程序的執(zhí)行，最后指令z的目的寄存器被映射為PRm。那么當(dāng)下一條指令y進(jìn)入譯碼段時(shí)，迭代重用方法因?yàn)橹赜肞R1的存儲(chǔ)空間，將繼續(xù)為指令y分配物理寄存器，從而避免了傳統(tǒng)方法下的流水線停頓。

圖1 重命名映射表與物理寄存器結(jié)構(gòu)Fig 1 Renaming table and physical register architecture

由于指令的亂序發(fā)射和執(zhí)行，物理寄存器迭代重用的方法還必須解決2個(gè)特殊情況。如圖表1所示，指令x先于y執(zhí)行，物理寄存器PR1被分配給指令x和y共用，在一般情況下指令x將在y之前完成并寫(xiě)回ISA寄存器，而當(dāng)指令y完成時(shí)物理寄存器若已經(jīng)釋放，指令x和y的寫(xiě)回都不會(huì)出現(xiàn)錯(cuò)誤。但是如果x是一條長(zhǎng)延遲的指令，那么指令y將有可能先于x完成，將結(jié)果寫(xiě)入PR1，并更新指令發(fā)射隊(duì)列中的相關(guān)性信息。因此，等到指令x完成時(shí)，指令x的執(zhí)行結(jié)果將覆蓋同樣存儲(chǔ)在PR1的指令y的執(zhí)行結(jié)果，而當(dāng)指令y寫(xiě)回時(shí)，寫(xiě)入ISA寄存器的值為指令x的結(jié)果，程序執(zhí)行出現(xiàn)錯(cuò)誤。另一種情況是雖然指令x在指令y之前完成，但是，如果在指令x未寫(xiě)回之前指令y也完成了，那么指令x的結(jié)果將被指令y所覆蓋，于是造成指令x的寫(xiě)回錯(cuò)誤。

為了解決這些問(wèn)題，本文在指令發(fā)射隊(duì)列中增加了物理寄存器共用的相關(guān)性信息，在指令分配物理寄存器并寫(xiě)入指令發(fā)射隊(duì)列的同時(shí)，檢查被分配的物理寄存器是否已經(jīng)被先前的指令分配，如果存在，則將物理寄存器的相關(guān)性信息寫(xiě)入指令隊(duì)列的表項(xiàng)，表示該指令與之前的指令共用同一個(gè)物理寄存器，這個(gè)相關(guān)性將在指令結(jié)果寫(xiě)回時(shí)解除。當(dāng)存在物理寄存器相關(guān)性的指令從指令發(fā)射隊(duì)列發(fā)射時(shí)，指令發(fā)射隊(duì)列將保存該指令的所有信息，直到指令執(zhí)行完成時(shí)再一次檢查物理寄存器的相關(guān)性信息，如果此時(shí)相關(guān)性已經(jīng)解除，指令結(jié)果被寫(xiě)入對(duì)應(yīng)的物理寄存器，并將該指令從指令隊(duì)列中釋放。相反如果此時(shí)相關(guān)性未解除，說(shuō)明該物理寄存器仍然被更老的指令所占用，因此，指令結(jié)果不能寫(xiě)入該物理寄存器，指令必須重新發(fā)射執(zhí)行，這樣就保證了所有存儲(chǔ)在物理寄存器中的指令結(jié)果在寫(xiě)回之前都不會(huì)被其他指令覆蓋。結(jié)合圖1和圖2分析，指令x和指令y占用的物理寄存器均為PR1，因此，當(dāng)指令y寫(xiě)入指令發(fā)射隊(duì)列時(shí)，將更新PR—dep和PR—RDY域，表示指令 y同指令 x具有物理寄存器的相關(guān)性，這個(gè)相關(guān)性將在指令x寫(xiě)回ISA寄存器時(shí)解除。

表2 指令發(fā)射隊(duì)列結(jié)構(gòu)Tab 2 Architecture of instruction issue queue

通過(guò)以上的分析知道，只要存在物理寄存器的結(jié)構(gòu)沖突，使用物理寄存器迭代重用方法的性能都將好于傳統(tǒng)方法。相對(duì)于兩級(jí)映射的方法，迭代重用方法不需要管理兩級(jí)映射表，不會(huì)增加硬件設(shè)計(jì)的復(fù)雜度。

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

本文基于CSKY嵌入式處理器執(zhí)行內(nèi)核的模型對(duì)物理寄存器迭代重用的方法進(jìn)行實(shí)驗(yàn)分析。為了盡量排除因?yàn)樘幚砥髌渌K造成的性能影響，整個(gè)處理器模型假設(shè)所有的指令都取自指令cache，所有的跳轉(zhuǎn)預(yù)測(cè)都能預(yù)測(cè)正確，指令發(fā)射隊(duì)列和重排序緩存的資源保證充足，在物理寄存器發(fā)生結(jié)構(gòu)沖突之前不會(huì)因?yàn)槠渌馁Y源沖突造成性能損失。

通過(guò)對(duì)迭代重用方法中迭代次數(shù)n的實(shí)驗(yàn)研究發(fā)現(xiàn)，當(dāng)?shù)螖?shù)兩次之后，在擁有相同的物理寄存器數(shù)量的條件下，處理器的性能不再有大的提升。這是因?yàn)殡m然可以分配到物理寄存器的指令數(shù)量增加了，但是如果迭代次數(shù)過(guò)大，由于指令發(fā)射隊(duì)列的資源有限，同樣會(huì)造成指令發(fā)射隊(duì)列的結(jié)構(gòu)沖突，后續(xù)的指令即使能分配到物理寄存器卻同樣會(huì)因?yàn)橹噶畎l(fā)射隊(duì)列已滿而停留在指令譯碼階段，多次迭代并不能體現(xiàn)出其優(yōu)勢(shì)，因此，在實(shí)驗(yàn)中選擇2次迭代重用。

同時(shí)使用powerstone中的8個(gè)測(cè)試程序(blit，crc，des，engine，g3fax，jpeg，pocsag，ucbqsort)作為基準(zhǔn)程序?qū)鹘y(tǒng)的寄存器重命名方法和物理寄存器迭代重用的方法進(jìn)行測(cè)試，統(tǒng)計(jì)出測(cè)試程序的指令數(shù)和每種方法下執(zhí)行完測(cè)試程序需要的周期數(shù)，并計(jì)算出處理器執(zhí)行各個(gè)測(cè)試程序的IPC值，最后使用IPC的平均值作為處理器性能的評(píng)價(jià)標(biāo)準(zhǔn)。

通過(guò)理論分析可知，當(dāng)PR—NUM增加到64個(gè)時(shí)，處理器將不會(huì)再由于物理寄存器的結(jié)構(gòu)沖突而造成性能損失，此時(shí)2種方法的IPC均達(dá)到極限值。從實(shí)驗(yàn)結(jié)果得到，PR—NUM 為64個(gè)時(shí)，IPC值為2.07。

圖1中，CONV_IPC和REUSE_IPC分別代表傳統(tǒng)方法和迭代重用方法的性能。

通過(guò)對(duì)圖3中傳統(tǒng)方法性能分析可以看到:對(duì)于傳統(tǒng)寄存器重命名方法，當(dāng)物理寄存器的個(gè)數(shù)達(dá)到44個(gè)時(shí)，IPC值約等于2，已經(jīng)接近極限性能。在此之后，物理寄存器數(shù)量的增加并不能在很大程度上提高處理器的性能，幾乎達(dá)到瓶頸。因此，綜合成本、功耗、面積、性能等方面的考慮，處理器物理寄存器數(shù)量的最優(yōu)解為44個(gè)。

對(duì)于圖2中迭代重用方法性能分析發(fā)現(xiàn)，當(dāng)PR—NUM達(dá)到20個(gè)之后，處理器的性能提升開(kāi)始變得平緩。每增加4個(gè)寄存器，IPC增量幾乎不到 5%。當(dāng) PR—NUM達(dá)到32個(gè)時(shí)，IPC值將達(dá)到2.0。因此，要達(dá)到傳統(tǒng)寄存器重命名方法物理寄存器數(shù)量最優(yōu)解時(shí)相同的性能，對(duì)于迭代重用寄存器重命名方法，其物理寄存器數(shù)量則為32個(gè)，相對(duì)于傳統(tǒng)的重命名方法，節(jié)省了物理寄存器27.3%的資源，相比兩級(jí)映射方法節(jié)省26%［4］的資源略好。

從2種方法的分析看到:如果物理寄存器的數(shù)量未達(dá)到最理想時(shí)，在具有相同物理寄存器數(shù)量的條件下，物理寄存器迭代重用的方法的性能都將優(yōu)于傳統(tǒng)方法，而物理寄存器數(shù)量越少，物理寄存器迭代重用方法的優(yōu)勢(shì)就越大。這是因?yàn)楫?dāng)物理寄存器數(shù)量越少時(shí)，處理器因?yàn)槲锢砑拇嫫鞯慕Y(jié)構(gòu)沖突的概率越高，所造成的性能損失也就越大，而物理寄存器迭代重用方法則在很大程度上緩解了這樣的結(jié)構(gòu)沖突造成的性能損失。

圖2 傳統(tǒng)方法與迭代重用方法性能比較Fig 2 Performance comparison between the conventional method and the iteratively reuse method

4 結(jié)論

本文通過(guò)研究傳統(tǒng)寄存器重命名方法存在的物理寄存器占用時(shí)間過(guò)長(zhǎng)的缺點(diǎn)，提出了一種物理寄存器迭代重用重命名方法。這種方法將通過(guò)縮短物理寄存器使用的時(shí)間，通過(guò)在物理寄存器中增加有限的指令信息和指令間的物理寄存器共用的相關(guān)性信息，迭代重用物理寄存器的存儲(chǔ)空間，提高了物理寄存器的利用效率，減小了重命名寄存器的資源沖突。

［1］Sima D.The design space of register renaming techniques［J］.IEEE Micro，2000，20(5):70－83.

［2］Farkas K I，Jouppi N P，Chow P.Register file design considerations in dynamically scheduled processors［C］∥The Second International Symposium on High-Performance Computer Architecture，1996:40－51.

［3］Lipasti M H，Mestan B R，Gunadi E.Physical register inlining［C］∥Proceedings of the31st Annual International Symposium on Computer Architecture，2004:325－335.

［4］Monreal T，Gonzalez A，Valero M，et al.Delaying physical register allocation through virtual-physical registers［C］∥Proceedings of the 32nd International Symposium on Microarchitecture，1999:186－192.

［5］Gao Song.Reducing register pressure through LAER algorithm［C］∥27th Australasian Computer Science Conference，2004:55－64.

［6］Balasubramonian R，Dwarkadas S，Albonesi D H.Reducing the compIexity of the register fiIe in dynamic superscalar processors［C］∥ Proceedings of the 34th IEEE/ACM International Symposium on Microarchitecture，Austin，2001:237－248.

［7］Smith JE，Sohi G S.The microarchitecture of superscalar processors［C］∥Proceedings of the IEEE，1995:1609－1624.

［8］Bishop B，Kelliher T P，Irwin M J.The design of a register renaming unit［C］∥Proceedings of the Ninth Great Lakes Symposium on VLSI，1999:34－37.