一種緩存數(shù)據(jù)流信息的處理器前端設(shè)計

劉炳濤　王　達(dá)　葉笑春　張　浩　范東睿　張志敏

1(中國科學(xué)院計算技術(shù)研究所　北京　100190)2　　　(中國科學(xué)院大學(xué)　北京　100049) (liubingtao@ict.ac.cn)

?

一種緩存數(shù)據(jù)流信息的處理器前端設(shè)計

劉炳濤1,2王達(dá)1葉笑春1張浩1范東睿1張志敏1

1(中國科學(xué)院計算技術(shù)研究所北京100190)2(中國科學(xué)院大學(xué)北京100049) (liubingtao@ict.ac.cn)

摘要為了能夠同時發(fā)掘程序的線程級并行性和指令級并行性，動態(tài)多核技術(shù)通過將數(shù)個小核重構(gòu)為一個較強(qiáng)的虛擬核來適應(yīng)程序多樣的需求.通常這種虛擬核性能弱于占有等量芯片資源的原生核，一個重要的原因就是取指、譯碼和重命名等流水線的前端各階段具有串行處理的特征較難經(jīng)重構(gòu)后協(xié)同工作.為解決此問題，提出了新的前端結(jié)構(gòu)——數(shù)據(jù)流緩存，并給出與之配合的向量重命名機(jī)制.數(shù)據(jù)流緩存利用程序的數(shù)據(jù)流局部性，存儲并重用指令基本塊內(nèi)的數(shù)據(jù)依賴等信息.處理器核利用數(shù)據(jù)流緩存能更好地發(fā)掘程序的指令級并行性并降低分支預(yù)測錯誤的懲罰，而動態(tài)多核技術(shù)中的虛擬核通過使用數(shù)據(jù)流緩存旁路傳統(tǒng)的流水線前端各階段，其前端難協(xié)同工作的問題得以解決.對SPEC CPU2006中程序的實驗證明了數(shù)據(jù)流緩存能夠以有限代價覆蓋大部分程序超過90%的動態(tài)指令，然后分析了添加數(shù)據(jù)流緩存對流水線性能的影響.實驗證明，在前端寬度為4條指令、指令窗口容量為512的配置下，采用數(shù)據(jù)流緩存的虛擬核性能平均提升9.4%，某些程序性能提升高達(dá)28%.

關(guān)鍵詞處理器微結(jié)構(gòu)；指令緩存；數(shù)據(jù)流；指令重命名；數(shù)據(jù)流局部性

因為結(jié)構(gòu)復(fù)雜度增長和功耗墻[1]等問題，單核處理器頻率和性能的增長在21世紀(jì)初遇到瓶頸.處理器結(jié)構(gòu)設(shè)計師們轉(zhuǎn)而通過增加片上集成的處理器核數(shù)來維持處理器符合摩爾定律的性能增長[2].如今多核處理器已經(jīng)逐漸占據(jù)了桌面和移動處理市場.

片上多核處理器(chip multi-processor, CMP)通過發(fā)掘程序的線程級并行性(thread-level parall-elism, TLP)來提供更高的處理能力.但利用程序的TLP有其局限性：1)歷史遺留的大量串行程序并沒有合理的并行化方案；2)通用處理領(lǐng)域大部分的計算并沒有足夠的TLP可供發(fā)掘；3)Hill與Marty[3]指出，根據(jù)阿姆達(dá)法則，隨著程序中并行部分的加速，串行部分漸漸成為繼續(xù)降低程序運(yùn)行時間的瓶頸.這些都表明處理器的單線程處理能力仍然非常重要.

芯片資源總量固定的情況下，核數(shù)增加會提升處理器發(fā)掘TLP的能力，同時單核分得資源減少，降低處理器發(fā)掘指令級并行性(instruction-level parallelism, ILP)的能力.為了在多核設(shè)計中兼顧發(fā)掘程序的TLP與ILP，學(xué)術(shù)界提出了動態(tài)多核(dynamic multi-core, DMC)技術(shù)[3].DMC處理器可以動態(tài)地將數(shù)個較弱的原生核(native core, N-Core)合并為一個較強(qiáng)的虛擬核(virtual core, V-Core)，增加處理器發(fā)掘ILP的能力.DMC技術(shù)按應(yīng)用的需求重構(gòu)多核的組織形式，打破了處理器發(fā)掘ILP與發(fā)掘TLP之間不可調(diào)和的邊界.采用DMC技術(shù)的處理器，其適應(yīng)性和通用性強(qiáng)于固定搭配處理器核的其他類型的多核處理器.

用多個小的N-Core通過DMC技術(shù)動態(tài)重構(gòu)出的V-Core，其性能通常要弱于用等量芯片資源直接實現(xiàn)的一個大的N-Core.一個重要的原因在于V-Core取得指令的能力弱于其執(zhí)行指令的能力.首先，取指、譯碼和重命名等流水線前端各階段具有串行處理的特點，較難協(xié)同工作來成倍增加指令的供給帶寬.而流水線后端的發(fā)射、執(zhí)行、寫回等階段因具有并行處理的特點，相對較易經(jīng)重構(gòu)后協(xié)同工作增加指令處理能力.其次，傳統(tǒng)的流水線從存儲器中取得的有效指令數(shù)目與執(zhí)行單元處理的有效指令數(shù)目相等，前后端耦合工作.流水線的以上2個特點，決定了DMC處理器中不同粒度的V-Core與N-Core不能全部做到流水線前后端匹配，并導(dǎo)致了DMC處理器不能在各種動態(tài)組織形式下都達(dá)到極優(yōu)性能.

為了解決DMC處理器中存在的上述問題，我們提出了一種新的處理器前端設(shè)計，稱作數(shù)據(jù)流緩存(dataflow cache, DF-Cache)，并給出了與之配合的向量重命名(vector renaming, VR)機(jī)制.DF-Cache利用數(shù)據(jù)流局部性(dataflow locality)，其操作的基本單元是經(jīng)譯碼和重命名處理后的指令基本塊，包含了數(shù)據(jù)依賴等信息.當(dāng)指令基本塊在DF-Cache中命中時，經(jīng)向量重命名后，流水線可以立即將其指令交付發(fā)射隊列，旁路了流水線前端各階段.DF-Cache的作用體現(xiàn)在如下2點：1)DF-Cache提升了流水線的指令供給帶寬并降低了指令供給延遲，進(jìn)而提升了處理器發(fā)掘程序ILP的能力，同時降低分支預(yù)測錯誤帶來的懲罰；2)DMC處理器中的V-Core利用DF-Cache旁路流水線前端各階段，并不需要取指、譯碼和重命名等流水線階段經(jīng)合并后協(xié)同工作.當(dāng)DF-Cache對動態(tài)指令的覆蓋率很高時，處理器執(zhí)行的大部分指令并非直接取自前端，流水線前端的處理能力不再限制流水線后端對指令的執(zhí)行，前后端不匹配的問題得以解決.

對SPEC CPU2006中程序的實驗證明了DF-Cache能夠以有限代價覆蓋大部分程序超過90%的動態(tài)指令；另外，我們分析了添加DF-Cache對流水線性能的影響.實驗證明，在前端寬度為4、指令窗口大小為512的配置下，采用DF-Cache的V-Core程序執(zhí)行性能平均提升9.4%，某些程序執(zhí)行性能提升高達(dá)28%.

1相關(guān)工作

DF-Cache通過發(fā)掘數(shù)據(jù)流局部性來提升流水線前端指令供給能力，進(jìn)而解決DMC處理器中V-Core前后端能力失配的問題.相關(guān)工作分為如下2節(jié).

1.1流水線前端的指令供給與數(shù)據(jù)流局部性

為了使處理器的指令窗口有足夠負(fù)載，很多研究著眼于提高流水線前端的指令供給能力.這些研究通常采用的方法是通過使用各種緩存結(jié)構(gòu)來旁路相應(yīng)流水線階段的操作，從而達(dá)到降低延遲、提高帶寬的目的.

傳統(tǒng)的指令緩存(instruction cache, ICache)利用計算的時間局部性，實現(xiàn)了容量大、延遲低的指令存儲結(jié)構(gòu)，從而降低取指延遲[4].DF-Cache也是一種指令的緩存，降低指令進(jìn)入發(fā)射隊列之前的總的前端延遲.與ICache的不同有2點：1)DF-Cache緩存的是動態(tài)指令的數(shù)據(jù)流圖，可以直接供后端使用，而ICache緩存的是統(tǒng)一編址內(nèi)存空間內(nèi)的靜態(tài)指令;2)DF-Cache的操作單元是以分支等控制指令分割的指令基本塊，而ICache操作單元是以地址索引的數(shù)條指令組成的緩存行.

Loop Cache[5]利用回跳分支指令發(fā)現(xiàn)計算中的循環(huán)，然后對循環(huán)指令進(jìn)行緩存降低取指延遲.Loop Cache在Intel的Nehalem架構(gòu)處理器中已有應(yīng)用[6]，Nehalem中的loop stream detector存儲譯碼后的28條微指令，可以旁路譯碼等流水線階段.相較Loop Cache，DF-Cache系統(tǒng)發(fā)掘了動態(tài)指令流中的數(shù)據(jù)流局部性，不局限于特殊指令或單個循環(huán)，可以加速多個或多重的循環(huán)代碼的取指.

Trace Cache[7]比Loop Cache更進(jìn)一步.它緩存譯碼后的指令，用首指令地址與后續(xù)數(shù)個分支的結(jié)果進(jìn)行索引.如果與多個分支預(yù)測的結(jié)果匹配，Trace Cache可以在1個周期內(nèi)跨越多個分支提供指令，大大提升前端帶寬.Trace Cache已在商業(yè)處理器中得到應(yīng)用，Intel的Sandy-Bridge架構(gòu)處理器中的decoded uop cache即是一種Trace Cache，可以覆蓋80%的處理器動態(tài)指令[8].DF-Cache相比較Trace Cache有2點改進(jìn)：1)DF-Cache相比較Trace Cache多緩存了基本塊內(nèi)的指令依賴信息，所以流水線利用DF-Cache能夠旁路了重命名階段前半部分消除名相關(guān)的工作;2)DF-Cache 的操作單元是指令基本塊，相比較Trace Cache，在存儲空間使用效率[9]和與分支預(yù)測相關(guān)的操作上更具優(yōu)勢.實驗證明，DF-Cache以更小的硬件代價實現(xiàn)了更高的指令覆蓋率.

Swanson等人[10]提出了數(shù)據(jù)流局部性的概念，將其解釋為程序中動態(tài)數(shù)據(jù)依賴的可預(yù)測性.為了發(fā)掘這種局部性，WaveScalar提出了新的指令集和微結(jié)構(gòu).DF-Cache則僅在微結(jié)構(gòu)上做改進(jìn)，不需要修改指令集，而對數(shù)據(jù)流局部性的發(fā)掘更有針對性.

Oberoi與Sohi[11]提出并行化流水線前端的方案.其中稱為Fragment Buffers的結(jié)構(gòu)可以緩存取得的指令并重用.根據(jù)測試程序的不同，可以使用16個這種緩沖區(qū)覆蓋程序20%～70%的指令.這種緩沖區(qū)的管理方式與DF-Cache類似，不過緩存的內(nèi)容卻不同，F(xiàn)ragment Buffers并沒有為了發(fā)掘數(shù)據(jù)流局部性做針對性的設(shè)計.

總而言之，提高指令供給能力的研究通常是通過有選擇的緩存前端流水線各階段的結(jié)果來加速后續(xù)的重復(fù)操作，指令覆蓋率是衡量其效果的重要指標(biāo).首先，DF-Cache的設(shè)計符合該邏輯；其次，DF-Cache針對發(fā)掘數(shù)據(jù)流局部性而設(shè)計，與以往研究不同.結(jié)構(gòu)上體現(xiàn)于2點：1)DF-Cache緩存并重用了重命名階段的數(shù)據(jù)依賴信息，據(jù)我們所知，這是之前研究所沒有的；2)緩存的粒度為指令基本塊，提高前端能力的同時可以高效地利用片上資源，與預(yù)測執(zhí)行等技術(shù)更直接銜接.

1.2動態(tài)多核技術(shù)

在多核處理器善于發(fā)掘TLP的基礎(chǔ)上，DMC技術(shù)合并N-Core構(gòu)建較強(qiáng)的V-Core來適應(yīng)程序?qū)LP發(fā)掘的需求.

Core Fusion[12]可以將寬度為2的N-Core“融合(FUSE)”為寬度為4或8的V-Core，它提出了詳細(xì)的重構(gòu)方案.前端的Fetch和Decode階段通過同步措施協(xié)同工作，然而Rename階段卻沒有融合.當(dāng)處理器數(shù)個N-Core按照V-Core的模式工作時，N-Core自身的重命名部件被旁路，而由單獨(dú)的SMU負(fù)責(zé)V-Core的重命名和指令分發(fā)工作.當(dāng)融合出的V-Core的寬度大于8時，SMU便難以實現(xiàn).Fetch與Decode的同步開銷增長亦不容忽略.Core Fusion融合得出的V-Core前端不具可擴(kuò)展性，導(dǎo)致Core Fusion的能融合的N-Core數(shù)目和獲得的V-Core的寬度受到限制，V-Core的性能也要弱于占用等量芯片資源的N-Core.

CLP(composable lightweight processor)[13]通過特殊的廣播與收集措施完成V-Core中指令的取指與提交.因為沒有核間共享的結(jié)構(gòu)，其可擴(kuò)展性要強(qiáng)于Core Fusion.但是CLP依賴非傳統(tǒng)ISA的EDGE指令集來實現(xiàn)分布式的指令處理結(jié)構(gòu)，需要編譯器的支持，其適應(yīng)性不如DF-Cache.

WiDGET[14]區(qū)別線程管理和計算資源分配，將計算資源從流水線中解耦合出來形成資源池，按應(yīng)用需求分配計算資源給硬件線程形成V-Core.該DMC技術(shù)只重構(gòu)計算資源，流水線的串行部分在形成V-Core時沒有任何改變，其目的在于實現(xiàn)與功耗成比例的計算，其V-Core不具有可擴(kuò)展性，流水線的寬度沒有改變，所以無法動態(tài)調(diào)整芯片發(fā)掘TLP和發(fā)掘ILP的能力.

Dynamic Core Morphing[15]通過動態(tài)組合2個非對稱核后端的計算資源，使其適應(yīng)應(yīng)用的需求，達(dá)到更好的功耗計算比.該DMC技術(shù)重構(gòu)的多種V-Core不能都達(dá)到前后端匹配，影響處理器總體能達(dá)到的性能.

從以上研究可以看出，目前已有的DMC技術(shù)并沒有提出合理的流水線前端的重構(gòu)方案.Core-Fusion的前端融合缺乏可擴(kuò)展性，CLP為了構(gòu)建V-Core借助于非傳統(tǒng)ISA，WiDGET和MorphCore等則不考慮對流水線前端做動態(tài)改變.DF-Cache加入流水線后可以部分替代傳統(tǒng)的流水線前端，通過發(fā)掘數(shù)據(jù)流局部性為流水線后端提供指令，從而解決DMC中各種V-Core前端能力不足的問題.

2數(shù)據(jù)流緩存的原理與擴(kuò)展的流水線結(jié)構(gòu)

以存儲程序為特征的馮-諾依曼體系結(jié)構(gòu)將程序指令存放在統(tǒng)一編址的存儲空間內(nèi)，我們稱之為靜態(tài)指令.程序要被處理器執(zhí)行，首先需要從內(nèi)存中將靜態(tài)指令取出，然后經(jīng)過譯碼和重命名變?yōu)檫m合執(zhí)行單元使用的微指令的形式，我們稱之為動態(tài)指令.提高靜態(tài)指令到動態(tài)指令的轉(zhuǎn)換效率和提高動態(tài)指令的執(zhí)行效率是馮氏結(jié)構(gòu)的2個基本問題.DF-Cache嘗試解決上述第1個問題.我們分別從計算模型和處理器微結(jié)構(gòu)2個角度闡述DF-Cache的原理及優(yōu)勢.

1) 從計算的角度看.DF-Cache充分利用計算的數(shù)據(jù)流局部性，提高了處理器前端指令供給能力.

靜態(tài)指令與動態(tài)指令的數(shù)量有量級上的差距，從側(cè)面說明動態(tài)指令流有很好的時間局部性.利用這種局部性，從內(nèi)存到發(fā)射隊列間的整個指令轉(zhuǎn)換過程有可以優(yōu)化的環(huán)節(jié).比如ICache，它通過緩存并重用從內(nèi)存中取得的指令，使得處理器執(zhí)行的動態(tài)指令數(shù)量遠(yuǎn)大于從內(nèi)存中取得的靜態(tài)指令數(shù)量.DF-Cache更進(jìn)一步將緩存從取指階段推進(jìn)到重命名階段之后，即指令轉(zhuǎn)換的最后一個環(huán)節(jié).而DF-Cache利用的數(shù)據(jù)流局部性，則是計算的時間局部性在傳統(tǒng)的ISA格局下一種特殊的表現(xiàn)形式.

比較程序存儲的靜態(tài)指令代碼和執(zhí)行的動態(tài)指令流，我們可以發(fā)現(xiàn)，以分支等控制指令為邊界劃分的指令基本塊在內(nèi)容上是一一對應(yīng)的.單個靜態(tài)的指令基本塊通常對應(yīng)1個或數(shù)個動態(tài)的指令基本塊實例，而這些實例內(nèi)的指令依賴等信息完全相同.所以動態(tài)指令流中地址連續(xù)的指令之間的重命名結(jié)果可以緩存并重用，這就是數(shù)據(jù)流局部性的具體體現(xiàn).著眼于此，我們的緩存結(jié)構(gòu)將由控制指令分割的指令基本塊作為操作單元.DF-Cache緩存指令基本塊內(nèi)的各種信息，包括譯碼后的微指令和微指令間依賴等.指令轉(zhuǎn)換工作剩余部分則還有分支等控制指令的預(yù)測和驗證，以及基本塊間的操作數(shù)依賴表示.這2點是指令轉(zhuǎn)換過程中沒有可重復(fù)性的部分.當(dāng)指令基本塊在DF-Cache中命中時，通過復(fù)用存儲的基本塊內(nèi)數(shù)據(jù)流信息，傳統(tǒng)處理器前端的取指、譯碼和重命名的解決名相關(guān)部分等都被旁路，降低了前端的延遲，提高指令供給帶寬.

2) 從微結(jié)構(gòu)的角度看.DF-Cache加入流水線后，解耦合了流水線的前端和后端.這解決了DMC技術(shù)中前端難以重構(gòu)和前后端能力失配的問題.

DMC技術(shù)[12]中多個N-Core的前端很難通過合并達(dá)到更高的指令供給能力.流水線的后端天然有并行處理的特點，發(fā)射隊列與執(zhí)行單元的動態(tài)組合問題可類比于傳統(tǒng)單核處理器中分簇(clustered)后端的設(shè)計問題.然而流水線的前端負(fù)責(zé)指令轉(zhuǎn)換，串行處理的特點導(dǎo)致其很難協(xié)同工作.尤其是重命名階段，針對指令的重命名多采用級聯(lián)比較器和多路器的設(shè)計[16]，串聯(lián)多個重命名部件導(dǎo)致一個超長的重命名延遲是無法接受的.所以像Core Fusion中的SMU[12]部件，重構(gòu)的V-Core常另外設(shè)計結(jié)構(gòu)替代單核內(nèi)的重命名部件.即便如此，因為指令重命名串行處理每條指令的特點，目前已知的前端設(shè)計方法不具有可擴(kuò)展性，很難匹配V-Core的流水線后端增長的帶寬需求.

DF-Cache作為一種存儲主體基于RAM的結(jié)構(gòu)，通過整合多個核的DF-Cache可以實現(xiàn)更高的動態(tài)指令覆蓋率，提供更高的讀寫帶寬，具有可擴(kuò)展性.利用DF-Cache進(jìn)行指令轉(zhuǎn)換的帶寬和延遲由向量化重命名決定，它與基本塊的數(shù)量相關(guān)，而不與指令數(shù)量直接相關(guān).另一方面，DF-Cache位于流水線前端與后端的結(jié)合處，DF-Cache命中時取指、譯碼和重命名階段被旁路，這些流水線階段的能力并不直接決定流水線轉(zhuǎn)化指令的能力.如果對動態(tài)指令流有很高的覆蓋率，DF-Cache可以滿足后端對指令供給的需求.這樣前后端的處理能力不匹配對V-Core的整體效率沒有影響.另外，不同于執(zhí)行單元數(shù)量和流水線寬度的設(shè)計考量，DF-Cache不存在過度設(shè)計，它所要考慮的是對動態(tài)指令的覆蓋率，與程序的ILP大小、流水線的執(zhí)行能力強(qiáng)弱不直接相關(guān).

Fig. 2　The logic function and organization of UB.圖2　UB的邏輯功能與結(jié)構(gòu)

添加DF-Cache后的流水線結(jié)構(gòu)如圖1所示.虛線上方為DF-Cache對一個傳統(tǒng)流水線的擴(kuò)展.DF-Cache命中的指令基本塊，不經(jīng)過取指和譯碼階段，而后端的執(zhí)行和提交階段為2條流水線所共用.

Fig. 1　Pipeline augmented with DF-Cache.圖1　DF-Cache擴(kuò)展的流水線

從圖1可以看出，如果DF-Cache覆蓋了動態(tài)指令流，那么計算就在DF-Cache和執(zhí)行單元之間構(gòu)成了封閉循環(huán)，指令快速地填充到發(fā)射隊列，后端執(zhí)行單元被最大限度地使用.

基本指令塊被緩存的信息集合稱為config.指令轉(zhuǎn)換時如果命中這個config，后端分配物理寄存器和發(fā)射隊列空間給基本塊的實例，我們稱其為屬于該config的1個幀(frame).config對應(yīng)靜態(tài)的指令基本塊，而frame對應(yīng)動態(tài)的指令基本塊.config存放微指令的編碼以及基本塊內(nèi)指令間的相對數(shù)據(jù)依賴等信息，frame存放指令的操作數(shù)等信息.

DF-Cache含有2個組件：微指令緩沖區(qū)(uop buffer, UB)和幀更新緩沖區(qū)(frame update buffer, FUB)，分別存放config和frame，如圖1所示.

DF-Cache的功能主要有3個：1)UB命中時，它替代取指和譯碼階段以及重命名階段的部分功能，完成指令的獲??；2)與發(fā)射隊列(issue queue, IQ)并列的FUB，與指針追蹤部件配合，完成指令的喚醒和選擇；3)指令從UB到FUB的填充，由VR部件負(fù)責(zé).本節(jié)分別介紹這3個功能的實現(xiàn).

2.1微指令緩沖區(qū)UB

UB存儲譯碼后的指令基本塊,邏輯功能如圖2所示,物理實現(xiàn)示意如圖3所示.

Fig. 3　Implementation of UB.圖3　UB的邏輯物理實現(xiàn)

UB由主微指令緩沖區(qū)(main-UB)和宏微指令緩沖區(qū)(mega-UB)組成.main-UB存儲微指令相關(guān)的信息，比如微指令編碼、微指令間寄存器依賴等，如圖2(c)所示；main-UB由RAM實現(xiàn)，mega-UB存儲基本塊的宏信息，比如首指令的PC值(idxPC)、最后的控制指令的PC值(brPC)等，如圖2(d)所示；mega-UB是基于CAM結(jié)構(gòu)的全相連Cache，用idxPC做索引標(biāo)簽(tag)，UB的各字段組成及大小評估如圖3所示.

讀取緩存的微指令是UB在流水線中的關(guān)鍵路徑操作，主要有2步：1)通過idxPC檢索mega-UB，獲得微指令在main-UB中的存儲地址(mainUBPtr)；2)在main-UB中取出微指令.main-UB對指令基本塊分行存儲，各行之間通過指針組成鏈表.只有首行的微指令讀取需要檢索mega-UB，后續(xù)的微指令通過追蹤指針(NextRowPtr)訪問main-UB即可獲得.

圖2(a)展示了地址從0x10c50到0x10c60的指令基本塊.首指令地址0x10c50作為該指令基本塊的索引，通過檢索mega-UB的idxPC字段確認(rèn)DF-Cache是否命中，并獲得基本塊在main-UB中的首行存儲地址，進(jìn)而在main-UB中讀取微指令.同時，0x10c60作為brPC從mega-UB中讀出，分支預(yù)測器(BPred)使用brPC做分支預(yù)測，獲得下一個基本指令塊的idxPC，繼續(xù)檢索mega-UB，循環(huán)往復(fù).

DF-Cache的取指方式與ICache相比，有3個特點值得注意：

1) 基于傳統(tǒng)的取指邏輯，BPred必須在ICache取到控制指令后才可以利用其PC值作出分支預(yù)測.而mega-UB與BPred的互動不需要訪問main-UB.這縮短了分支預(yù)測之間的間隔，理論上每個周期都可以從新的指令基本塊開始取指，多個指令基本塊的微指令讀取周期可以重疊(overlap).

2) 獲得同樣多的指令，mega-UB的訪問次數(shù)不會多于ICache.因為mega-UB只有遇到控制指令時才進(jìn)行檢索，而ICache在這種情況下也必須進(jìn)行tag比較.同時ICache在遇到Cache行分界時都要進(jìn)行檢索，其訪問次數(shù)應(yīng)大于mega-UB.

3) mega-UB與BPred以及后續(xù)提到的向量重命名邏輯三者配合，可以比較自然地實現(xiàn)基于檢查點(checkpoint)的預(yù)測執(zhí)行.每次mega-UB的檢索，都是進(jìn)行了一次分支預(yù)測，產(chǎn)生了一個新的frame到FUB中，同時進(jìn)行一次向量重命名.此時建立checkpoint，存儲當(dāng)前節(jié)點的結(jié)構(gòu)寄存器映射以及一個最新的frame相關(guān)信息.將來控制指令執(zhí)行后，如果發(fā)現(xiàn)分支預(yù)測錯誤可以進(jìn)行回卷.首先丟掉(flush)后續(xù)預(yù)測執(zhí)行的frame；錯誤的分支預(yù)測指令所在的frame因為沒有提交(commit)，其所在的config引用計數(shù)(refCNT)就不為0，從而config也不會被替換掉，利用checkpoint中的信息做現(xiàn)場恢復(fù)，利用正確執(zhí)行方向的idxPC檢索mega-UB恢復(fù)執(zhí)行.

圖2(b)展示了我們?nèi)绾卫靡蕾囍羔?depen-dence pointer)[17-18]表示指令的操作數(shù)依賴.依賴指針是前向的(forward)數(shù)據(jù)流依賴表示，例如指令B依賴指令A(yù)，那么在指令A(yù)的操作數(shù)寄存器旁并列存放著指向指令B的源操作數(shù)物理寄存器的指針，當(dāng)指令A(yù)的操作數(shù)更新后，指令追蹤部件負(fù)責(zé)將操作數(shù)傳遞給指令B.指令依賴指針與RAM的實現(xiàn)相結(jié)合用來實現(xiàn)可擴(kuò)展的發(fā)射隊列.指令基本塊作為整體，對結(jié)構(gòu)寄存器文件的讀寫集合存儲在結(jié)構(gòu)寄存器讀寫向量內(nèi)，用來做向量重命名.

圖2(c)展示了基本塊內(nèi)的微指令和依賴信息在main-UB中的存儲情況.FUB分為3個塊(bank)，依次存儲微指令的2個源操作數(shù)和1個目的操作數(shù)，bank由bid索引.指令間的相對依賴由uopid和bid組成的依賴指針鏈表示.arch項記錄了這個操作數(shù)是來自或?qū)懭肽膫€結(jié)構(gòu)寄存器.

圖2(d)列舉了mega-UB的字段.idxPC用來做緩存的檢索，判斷緩存是否命中；brPC提供給分支預(yù)測器使用；LRUPtrs為記錄基本塊訪問的時間先后順序的雙向鏈表指針，用來維護(hù)LRU(least recently used)信息；mainUBPtr是基本塊在main-UB的首行地址；uopCNT記錄了基本塊內(nèi)的微指令數(shù)目，這個字段用來在FUB中分配連續(xù)的空間；refCNT記錄屬于此config的frame實例數(shù)量；rdVec和wrVec這2個字段用來做向量重命名.

DF-Cache未命中時，由ICache負(fù)責(zé)取指，同時DF-Cache采集指令基本塊的信息，并逐步完成基本塊內(nèi)的指令依賴表示.整個基本塊取指譯碼完成后，嘗試在DF-Cache中存儲該指令基本塊.

DF-Cache滿時，包括2種情況:mega-UB溢出和main-UB溢出.DF-Cache使用LRU策略進(jìn)行替換，在mega-UB中LRUPtrs組成的雙向鏈表尾逐個向前清理，直到mega-UB中有空閑條目，main-UB中有足夠空行.

DF-Cache中條目的構(gòu)建與替換不是流水線的關(guān)鍵路徑操作，限于篇幅限制不再繼續(xù)展開.

對動態(tài)指令的覆蓋率決定了DF-Cache的實際應(yīng)用效果.著眼于應(yīng)用的數(shù)據(jù)流局部性特征，我們對不同設(shè)計參數(shù)配置的UB進(jìn)行實驗，考察DF-Cache的指令覆蓋率.同時，DF-Cache的面積、功耗與延遲作為約束，也決定了其是否有實現(xiàn)的價值.詳細(xì)分析見3.1節(jié)的實驗部分.

2.2向量重命名VR

傳統(tǒng)的重命名部件的操作對象是單條指令.1)為每條指令分配存儲操作數(shù)的物理寄存器和發(fā)射隊列空間；2)解決名相關(guān)依賴，比對指令的操作數(shù)編碼和寄存器重命名表(register aliasing table, RAT)，獲得每個操作數(shù)依賴的物理寄存器編號或者從寄存器文件中讀出操作數(shù)的值，并更新RAT；3)將指令和操作數(shù)等寫入發(fā)射隊列.

向量重命名與傳統(tǒng)重命名結(jié)果相同，但過程不同.我們將指令的寄存器依賴分為2類：位于基本塊內(nèi)的和位于基本塊間的依賴.1)DF-Cache存儲了基本塊內(nèi)的依賴，只要將config中存儲的依賴關(guān)系加上frame在FUB中的偏移，即可得到絕對依賴關(guān)系;2)向量重命名部件對數(shù)個基本塊的讀寫向量進(jìn)行處理，分析基本塊間的依賴得出操作數(shù)傳遞路徑，并將其補(bǔ)充到發(fā)射隊列里，完成基本塊間的指令依賴表示.指令進(jìn)入發(fā)射隊列后，不再有塊內(nèi)和塊間的區(qū)分，被獨(dú)立地調(diào)度執(zhí)行.

DF-Cache連續(xù)命中時，向量重命名部件可在2個流水的時鐘周期內(nèi)完成數(shù)個基本塊的重命名和發(fā)射隊列的填充操作.

周期1.VR完成基本塊內(nèi)的重命名，并為基本塊間的重命名做準(zhǔn)備.VR的操作對象是被分支預(yù)測選中且在DF-Cache中命中的數(shù)個指令基本塊.首先，每個frame獲得唯一的frameID并從main-UB向FUB中復(fù)制微指令，即在FUB中分配一塊連續(xù)的物理寄存器和發(fā)射隊列空間并對應(yīng)uopid復(fù)制基本塊內(nèi)指令的相對依賴指針和立即數(shù)操作數(shù).其次，main-UB中的結(jié)構(gòu)寄存器讀寫字段也被讀取，VR將表示塊間依賴的讀寫向量和對應(yīng)的物理寄存器的地址存儲到向量重命名部件內(nèi)，為第2周期的工作做準(zhǔn)備.圖4展示了第1周期操作的結(jié)果.

周期2.VR完成基本塊間的重命名.利用讀寫向量和對應(yīng)的物理寄存器地址，VR將塊間寄存器依賴補(bǔ)充到指令窗口中，同時更新RAT.更新依賴時，結(jié)構(gòu)寄存器的寫向量的物理寄存器依賴指針地址作為更新地址，對應(yīng)的讀向量的物理寄存器地址作為更新值.我們以圖4(a)的基本塊為例子，假設(shè)分支預(yù)測器給出連續(xù)3個0x10c60的分支都是預(yù)測命中，那么我們要將該config的3個frame更新到指令窗口中.假設(shè)3個frame在VR的第1周期內(nèi)分得的frameID分別是0x0a，0x0b，0x0c.第2周期的向量重命名過程和指令窗口更新結(jié)果如圖5所示.

Fig. 4　First cycle of VR.圖4　向量重命名第1周期

Fig. 5　Second cycle of VR.圖5　向量重命名第2周期

向量重命名要求獲得每個frame的結(jié)構(gòu)寄存器讀寫向量，并且有對應(yīng)物理寄存器的地址.依賴的發(fā)現(xiàn)和表示過程舉例說明.首先是R0結(jié)構(gòu)寄存器，如圖5(a)所示的虛豎線，從上到下依次為1 10 10 10 1.VR從讀向量為1的位置入手，其獲得的操作數(shù)來自離它最近的前面一個標(biāo)記為1的位置*FUB采用單鏈的指針追蹤實現(xiàn)喚醒和選擇，使得發(fā)射隊列可擴(kuò)展.如果采用廣播的形式完成喚醒，要考察標(biāo)記為1的最近的寫，通過減少參數(shù)傳遞的跳數(shù)，縮短指令喚醒的延遲..比如BB0的讀向量的R0位置的1和對應(yīng)的物理寄存器地址2:0a:3說明，BB0的第4條微指令的第2個源操作數(shù)來自RAT記錄的R0.如果RAT中R0位置是有效的，那么將結(jié)構(gòu)寄存器的值拷貝到FUB的BK2的0a:3地址的data字段；如果R0的位置是無效的，而是記錄1個物理寄存器的地址，物理寄存器地址(2:0a:3)拷貝到R0所記錄的物理寄存器的依賴指針里，延續(xù)依賴鏈.再比如BB1的讀向量的R1位置的1和對應(yīng)的物理寄存器地址1:0b:0說明，BB1的第1條微指令的第1個源操作數(shù)來自BB0的第4條微指令的第1個源操作數(shù)(1:0a:3)，將(1:0b:0)寫入到(1:0a:3)位置的物理寄存器的依賴指針內(nèi)，延續(xù)依賴鏈.最后，見圖5(a)中的RAT′，將每個最后寫結(jié)構(gòu)寄存器的物理寄存器的地址更新到RAT表中.更新后的FUB見圖5(b).

VR大部分的邏輯操作可以向量化地并行進(jìn)行.以圖5(a)的向量重命名的位矩陣為例.VR可以分別操作各個結(jié)構(gòu)寄存器對應(yīng)的縱向位向量而互不影響，而針對單個橫向的讀位向量分別查詢距離最近的1并負(fù)責(zé)更新FUB中的依賴，也可以并行進(jìn)行.假設(shè)1個周期可以預(yù)測并寫入到FUB中n個基本指令塊，而結(jié)構(gòu)寄存器有m個，那么需要(n+1)m個判斷位是否為1并查詢長度為(2n+1)的向量中最后的1的邏輯部件.硬件開銷基本固定，與各基本塊內(nèi)的指令數(shù)和單周期內(nèi)重命名的總指令數(shù)不直接相關(guān).

2.3幀更新緩沖區(qū)FUB

FUB的設(shè)計類似于RUU[19]，流水線并沒有單獨(dú)的物理寄存器文件，物理寄存器的地址與frame在FUB中的地址信息frameID相關(guān)聯(lián)，F(xiàn)UB除了存儲操作數(shù)的依賴信息并調(diào)度微指令外，還存儲操作數(shù).

與RUU不同的是，F(xiàn)UB由RAM而不是CAM組成，數(shù)塊RAM加上指令追蹤部件實現(xiàn)可擴(kuò)展的發(fā)射隊列.我們采用了類似ForwardFlow[18]中Dataflow Queue的設(shè)計.

在2.2節(jié)中已經(jīng)提到了FUB的部分實現(xiàn)，F(xiàn)UB由main-FUB和mega-FUB組成.main-FUB作為指令窗口的組成部分*另一部分是標(biāo)量重命名所使用的發(fā)射隊列，如圖1中IQ所示，同樣采用類似DataflowQueue的設(shè)計.除了填充指令方式不同，IQ與FUB在指令喚醒和選擇上是統(tǒng)一的.，與依賴追蹤部件協(xié)同完成指令的喚醒(wakeup)和發(fā)射(issue).mega-FUB用frameID索引，記錄屬于frame整體的信息，比如frame屬于哪個config以及該frame還有多少條uop沒有發(fā)射等，這些信息用來協(xié)助管理UB和FUB.

依賴追蹤部件沿依賴鏈逐個傳遞操作數(shù)，同時它負(fù)責(zé)喚醒指令并提供可以發(fā)射的指令給選擇邏輯(select logic).在更新操作數(shù)后，追蹤部件會將指令的2個源操作數(shù)讀出，如果操作數(shù)都準(zhǔn)備好，負(fù)責(zé)將這條指令交給選擇邏輯等待發(fā)射，發(fā)射如果不能立刻完成，依賴追蹤部件會阻塞在這條指令上，直到發(fā)射完成.在更新操作數(shù)后如果另外1個源操作數(shù)沒準(zhǔn)備好，依賴追蹤部件會繼續(xù)沿依賴鏈傳遞操作數(shù).這種指令依賴追蹤與RAM結(jié)合的設(shè)計保證發(fā)射窗口有可擴(kuò)展性，實現(xiàn)較大的指令窗口同時對性能沒有太大影響[17-18,20].

每個指令追蹤部件皆負(fù)責(zé)一段RAM的更新，不屬于其管理范圍的操作數(shù)會傳遞給負(fù)責(zé)該操作數(shù)的指令追蹤部件處理.每個指令追蹤部件有輔助的FIFO緩存屬于該部件但無法立刻追蹤的操作數(shù).RAM的分段越多，F(xiàn)UB的讀寫帶寬越大.總的指令追蹤部件數(shù)量與RAM的分段數(shù)相同，并且決定了FUB單周期內(nèi)能提供給選擇邏輯進(jìn)行發(fā)射的微指令數(shù).

3實驗結(jié)果與分析

3.1數(shù)據(jù)流緩存的動態(tài)指令覆蓋率與實現(xiàn)代價評估

DF-Cache能以有限的代價覆蓋足夠的動態(tài)指令才有應(yīng)用價值.我們首先考察DF-Cache在不同設(shè)計參數(shù)下對指令的覆蓋率，然后分析DF-Cache的訪問延遲、面積和功耗，并與32KB的ICache進(jìn)行比較.

我們使用SPEC CPU2006[21]中的部分程序作為測試程序集，使用ref等級的輸入數(shù)據(jù)，如表1所示.我們用ESESC模擬器[22]運(yùn)行測試程序集，每個程序我們運(yùn)行20億條動態(tài)指令,分析DF-Cache對動態(tài)指令流的覆蓋率.

Table 1　Selected SPEC CPU2006 Benchmarks And Input

在使用CACTI對不同參數(shù)的DF-Cache設(shè)計的面積、功耗和延遲進(jìn)行分析后，我們認(rèn)為mega-UB容量為256個條目、main-UB容量為512個數(shù)據(jù)行的配置較為合理，并將其作為3.2節(jié)實驗的DF-Cache配置.該配置下DF-Cache對測試程序的平均動態(tài)指令覆蓋率大于90%，其功耗、面積和訪問延遲都要優(yōu)于32 KB的ICache.

3.1.1數(shù)據(jù)流緩存的動態(tài)指令覆蓋率

DF-Cache采用LRU替換策略，指令基本塊能否在DF-Cache中持續(xù)命中，取決于其數(shù)據(jù)流局部性.數(shù)據(jù)流局部性的衡量標(biāo)準(zhǔn)即1個靜態(tài)指令基本塊的相鄰2個動態(tài)實例之間間隔的指令基本塊種類數(shù).舉例說明，假設(shè)mega-UB的條目數(shù)為4，遇到某個config的第1個frame時，該config被放到隊列頭，如果該config的第2個frame到來前遇到的基本塊不超過3種，那么該config沒有被替換，第2個frame仍能夠命中.程序中屬于相同config的frame之間間隔的config種類少，表明該程序有好的數(shù)據(jù)流局部性，用較小的mega-UB容量即可覆蓋較多的動態(tài)指令.mega-UB中條目越多則動態(tài)指令覆蓋率越高.另外，mega-UB是基于CAM的全相連Cache，條目增多會增加功耗并增大訪問延遲.

mega-UB中每個條目對應(yīng)單個指令基本塊，而main-UB中每個數(shù)據(jù)行存儲8個譯碼后的微指令，main-UB中每個數(shù)據(jù)行只能屬于單個指令基本塊，所以main-UB的行數(shù)應(yīng)該大于等于mega-UB的條目數(shù).

參照圖3，mega-UB與main-UB的寬度是確定的，分別為25 B與64 B.需要考量的是部件的高度，即mega-UB中的條目數(shù)與main-UB中的數(shù)據(jù)行數(shù).mega-UB的實現(xiàn)分為4種：CAM128，CAM256，CAM512，CAM1024.CAM代表了其硬件結(jié)構(gòu)，數(shù)字代表了其含有的條目數(shù).main-UB的實現(xiàn)分為3種：RAM256，RAM512，RAM1024.兩者叉積構(gòu)成DF-Cache的各種配置，例如CAM128與RAM256的組合記為mega-UB128 main-UB256.圖6展示了有代表性的DF-Cache配置對測試程序的覆蓋率結(jié)果.

Fig. 6　Instruction coverage by DF-Cache of different configurations.圖6　不同配置DF-Cache的指令覆蓋率

從圖6可以看出，不同的程序表現(xiàn)出不同的特征.第1類程序包括gcc，namd，gobmk，h264ref等，這些應(yīng)用的數(shù)據(jù)流局部性較差，對mega-UB的容量敏感.體現(xiàn)出這些應(yīng)用的計算比較復(fù)雜，其控制流很可能與輸入數(shù)據(jù)相關(guān)，通常其分支預(yù)測準(zhǔn)確性也較低.第2類程序包括milc，libquantum，lbm，astar等，這些程序數(shù)據(jù)流局部性好、控制流簡單，較小的mega-UB即可覆蓋接近100%的動態(tài)指令.第3類程序包括其他的測試程序，當(dāng)mega-UB的容量超過某值后，即可有較高動態(tài)指令覆蓋率.從設(shè)計空間探索的角度看，我們所取的4個配置樣本點無法完全滿足第1類程序的數(shù)據(jù)流局部性要求，能滿足第2類程序的數(shù)據(jù)流局部性要求，能覆蓋到第3類程序的數(shù)據(jù)流局部性臨界點.

觀察經(jīng)過幾何平均的覆蓋率，可以看到mega-UB256 main-UB512的DF-Cache配置對動態(tài)指令的覆蓋率超過了90%.該數(shù)據(jù)已經(jīng)超過了SandyBridge中decoded uop cache的80%的指令覆蓋率.

3.1.2數(shù)據(jù)流緩存的實現(xiàn)代價分析

CACTI通過對存儲器件進(jìn)行建?？梢苑治銎涿娣e、功耗和訪問延遲.我們首先分析DF-Cache的組件mega-UB和main-UB，然后計算得出不同配置的DF-Cache估計的實現(xiàn)代價.

mega-UB和main-UB的物理實現(xiàn)如圖3所示，我們對RAM，CAM，ICache用CACTI5.3版本進(jìn)行評估，配置間有差異的輸入?yún)?shù)如表2所示，另外所有配置使用65nm工藝，有1個讀寫端口，bank數(shù)為1.

Table 2　CACTI Inputs

訪問延遲、功耗與面積的評估結(jié)果分別如圖7～9所示：

Fig. 7　Latency and cycle of CAM，RAM and ICache.圖7　CAM，RAM，ICache的延遲與周期

Fig. 8　Energy per access of CAM，RAM and ICache.圖8　CAM，RAM，ICache的單次訪問功耗

Fig. 9　Area of CAM，RAM and ICache.圖9　CAM，RAM，ICache的面積

mega-UB使用CAM實現(xiàn)，其訪問延遲、單次讀寫功耗和面積開銷的變化曲線都比較陡峭，說明其可擴(kuò)展性較差.但CAM256的各項數(shù)據(jù)仍在可接受的范圍內(nèi).

main-UB使用RAM實現(xiàn)，它在功耗和面積方面都要大大優(yōu)于同樣容量的ICache，這是因為它使用從mega-UB中獲得的RAM地址直接被訪問，沒有普通Cache的標(biāo)簽陣列(tag array).

從UB中取微指令分2種情況：如果是基本塊的首行，首先訪問mega-UB，然后從main-UB中取得微指令；否則，利用基本塊每行末尾的指針取得后續(xù)行的微指令.前者的代價較大，我們稱之為最差情況(worst case)，而后者為最好情況(best case).

UB的各項指標(biāo)計算如下：訪問延遲為2個組件訪問延遲的和(worst case)或main-UB的訪問延遲(best case).周期等于mega-UB和main-UB周期較大者(訪問mega-UB與訪問main-UB流水實現(xiàn)).讀寫事件動態(tài)功耗為2個組件功耗的和(worst case)或main-UB的功耗(best case).面積開銷為2個組件面積開銷的和.UB各種配置的評估結(jié)果如圖10～12所示.

Fig. 10　Latency and cycle of UB.圖10　UB的延遲與周期

Fig. 11　Energy per access of UB.圖11　UB的單次訪問功耗

Fig. 12　Area of UB.圖12　UB的面積

可以看出，mega-UB256 main-UB512的配置在訪問延遲和單次讀寫功耗以及面積開銷方面都要優(yōu)于同樣存儲32KB指令數(shù)據(jù)的4-Way ICache.其功耗開銷在最差情況也不大于ICache，而最優(yōu)情況下只有ICache的一半.面積開銷只有ICache的40%.

前面2.1節(jié)簡單提到，mega-UB與main-UB是松散耦合的，與傳統(tǒng)的ICache不同.從該點出發(fā)，DF-Cache可以在結(jié)構(gòu)上進(jìn)行優(yōu)化進(jìn)而提高性能.首先，mega-UB和main-UB可以通過地址緩存隊列連接，mega-UB負(fù)責(zé)不斷將預(yù)測獲得的指令基本塊首數(shù)據(jù)行地址放到隊列中，而main-UB可以從隊列中取得基本塊首數(shù)據(jù)行地址，自由地完成后續(xù)的微指令取出操作.其次，main-UB基于RAM實現(xiàn)，其訪問延遲和功耗低，可以倍頻工作，或者多個讀寫端口同時訪問多個基本塊，提高指令供給的寬度.最后，對在存儲空間內(nèi)連續(xù)的數(shù)個基本塊，可以在main-UB中鏈接起來，使得main-UB有連續(xù)跨基本塊預(yù)取指的能力，而不完全依賴mega-UB.

通過以上分析可以看出，DF-Cache的結(jié)構(gòu)和工作方式與傳統(tǒng)的ICache相比，在性能、面積和功耗上都有優(yōu)勢.另外考慮到DF-Cache旁路了譯碼和重命名階段，DF-Cache可以降低處理器的動態(tài)功耗.在ESESC中集成的mcpat工具里添加DF-Cache和向量重命名部件的延遲、面積和功耗模型，并在ESESC的時序模型中添加必要的性能計數(shù)器，即可以實時分析得到添加了DF-Cache的處理器運(yùn)行特定測試程序時的動態(tài)功耗.本文重點在于DF-Cache加入流水線對功能和性能的影響，其具體的功耗優(yōu)勢不再繼續(xù)展開.本節(jié)通過分析說明了，DF-Cache能以可接受的代價實現(xiàn)較高的動態(tài)指令覆蓋率.

3.2加入數(shù)據(jù)流緩存對流水線的影響

DF-Cache加入流水線的作用可概括如下：首先它提升了指令供給帶寬并降低了指令供給延遲；其次，DF-Cache解耦合了流水線的前后端，DF-Cache負(fù)責(zé)向后端供應(yīng)指令，可以解決DMC處理器中V-Core流水線前端能力較弱的問題.本節(jié)，我們從上述2個方面分析DF-Cache對流水線的影響.

表3展示了ESESC模擬處理器核的基準(zhǔn)配置的全部參數(shù)設(shè)置，我們記該配置為F4-B128.F4表示流水線寬度為每周期4條指令，B128表示指令窗口容量為128.

Table 3　Base Configuration F4-B128

表4列舉了我們選擇進(jìn)行實驗的10種處理器核配置.僅與基準(zhǔn)配置不同的參數(shù)設(shè)置在表4中進(jìn)行了列舉，包括流水線寬度、指令窗口大小、功能部件配備和是否搭配有DF-Cache.

Table 4　Selected Configurations in Sample Space

F4-B128，F(xiàn)6-B256，F(xiàn)8-B512模擬的是有不同ILP發(fā)掘能力的N-Core，其前端指令供給能力與后端的執(zhí)行能力匹配較好.F4-B256，F(xiàn)4-B512模擬的是通過DMC技術(shù)重構(gòu)得來的V-Core，因為流水線前端各階段的融合效果差，它們的指令供給能力要弱于指令執(zhí)行能力.D4-B128，D4-B256，D4-B512，D6-B256，D8-B512這5個D系列配置，與F系列的配置一一對應(yīng)，僅額外添加了DF-Cache.要考察前端結(jié)構(gòu)對流水線的影響，我們需要控制非相關(guān)變量.因而忽略流水線后端V-Core融合導(dǎo)致的額外開銷，操作數(shù)傳遞延遲設(shè)置為0.舉例說明，F(xiàn)4-B256，D4-B256，F(xiàn)6-B256，D6-B256雖屬不同結(jié)構(gòu)，卻擁有相同性能的后端.這使得模擬獲得的實驗數(shù)據(jù)能夠體現(xiàn)出不同前端結(jié)構(gòu)帶來的影響，有可比較性.

與Core Fusion等DMC設(shè)計的實驗類似，我們關(guān)注V-Core執(zhí)行單線程程序發(fā)掘ILP的能力，暫時不考慮多道程序和多線程程序在DMC中的執(zhí)行.我們使用ESESC的TASS采樣模式運(yùn)行了每個測試程序10億條動態(tài)指令，TASS采樣設(shè)置RWDT各階段的比例為250:245:2:13.模擬的結(jié)果如圖13所示.IPC數(shù)值已經(jīng)歸一化到F4-B128，方便比較.

Fig. 13　One billion uops simulation result.圖13　10億條動態(tài)指令模擬結(jié)果

簡要分析沒有DF-Cache的F系列配置的測試結(jié)果反映出的程序與處理器結(jié)構(gòu)的特點.

首先，比較F4-B128，F(xiàn)6-B256，F(xiàn)8-B512這3個N-Core的數(shù)據(jù)，可以看到大部分的測試程序隨著處理器核發(fā)掘ILP的能力上升而執(zhí)行性能有所提升.bzip和libquantum提升較小，說明程序本身蘊(yùn)含的ILP較有限或者長延時指令較多，對指令窗口大小不敏感.gcc，namd，soplex，povray，h264ref則含有較高的ILP.再對比圖6我們可以看到，程序的數(shù)據(jù)流局部性與指令級并行性之間沒有明顯的相關(guān)關(guān)系，計算的這2個特性分別對應(yīng)了微結(jié)構(gòu)上流水線前端轉(zhuǎn)化指令的能力和流水線后端執(zhí)行指令的能力.流水線前后端相匹配，且滿足程序的2個特性才可以有比較高的執(zhí)行效率.

其次，分別比較F4-B256和F6-B256，以及F4-B512和F8-B512這2組V-Core對比N-Core的數(shù)據(jù).例如gcc，milc，namd，povray等測試程序，可以明顯看到DMC重構(gòu)得到的V-Core因為其前端相對較弱，影響到了流水線對這些程序的執(zhí)行效果.占用相同資源的N-Core性能強(qiáng)于重構(gòu)得來的V-Core.

3.2.1數(shù)據(jù)流緩存對流水線性能影響

DF-Cache將前端的譯碼和重命名信息進(jìn)行緩存，當(dāng)指令基本塊在其中命中時，通過向量重命名后，可以快速填充到后端發(fā)射隊列中.所以DF-Cache可以提升前端帶寬、降低前端延遲.但是，傳統(tǒng)的處理器取指、譯碼和重命名等功能已經(jīng)流水化實現(xiàn)，并且分支預(yù)測部件的正確率都很高，DF-Cache能發(fā)揮多少作用值得商榷，本節(jié)通過對比D系列N-Core相對F系列N-Core的測試數(shù)據(jù)來研究DF-Cache的加入對流水線性能的影響.

擁有不同ILP發(fā)掘能力的N-Core在有或無DF-Cache的情況下的執(zhí)行性能對比如圖14所示：

Fig. 14　The influence of DF-Cache on the pipeline of N-Core.圖14　DF-Cache對N-Core流水線性能影響

Fig. 15　Performance data of D8-B512 and F8-B512.圖15　D8-B512與F8-B512的性能數(shù)據(jù)

1) DF-Cache提升了部分程序的性能，例如gcc，gobmk，povray，sjeng，h264ref，omnetpp.同時參照圖6和圖13可以得出，這些程序能夠被DF-Cache加速存在3個因素：①程序本身要含有足夠的ILP.DF-Cache提高指令供給，從而使得后端的計算能力得到更好的利用.而bzip2與libquantum因為程序自身或處理器后端能力原因?qū)е翴LP較低，所以DF-Cache對其提升有限.②這些程序的數(shù)據(jù)流局部性較差.與直覺相反，DF-Cache覆蓋率較低的程序反而受到的DF-Cache加速效果更好，這是因為這些程序局部性較差，從而指令供給能力提升的空間也大.③程序的分支預(yù)測準(zhǔn)確率也影響DF-Cache的效果.

2) mcf，milc，soplex，libquantum，astar的部分測試結(jié)果要比沒有DF-Cache的情況更差.這主要有2個原因：①如上段所述，數(shù)據(jù)流局部性好的程序前端帶寬提升的空間非常有限，前后端匹配的流水線已經(jīng)能非常好地利用后端的計算資源，DF-Cache的加入能提供的正面效果較弱.②通過分析程序的執(zhí)行過程，我們發(fā)現(xiàn)發(fā)射隊列的快速填充導(dǎo)致了不在關(guān)鍵路徑上的指令搶占了屬于關(guān)鍵路徑上的指令的執(zhí)行時機(jī)，我們稱這種降低程序執(zhí)行效率的現(xiàn)象為關(guān)鍵路徑遮擋.如果指令調(diào)度器實現(xiàn)了優(yōu)先關(guān)鍵路徑指令的調(diào)度算法，該問題即可解決.

圖15重點展示了D8-B512和F8-B512的性能對比數(shù)據(jù)和F8-B512執(zhí)行的ILP絕對數(shù)值以及分支預(yù)測準(zhǔn)確率.可以看到DF-Cache對流水線的加速效果與程序的ILP呈較明顯的正相關(guān)關(guān)系，而與程序的分支預(yù)測正確率呈較明顯的反相關(guān)關(guān)系.舉例說明，povray程序有高的ILP而分支預(yù)測準(zhǔn)確率低，其受到DF-Cache加速效果最明顯，達(dá)到8.1%；bzip2雖然有低的分支預(yù)測準(zhǔn)確率，但其ILP有限，DF-Cache基本沒有加速其執(zhí)行；libquantum的分支預(yù)測準(zhǔn)確率高但I(xiàn)LP低，DF-Cache的加入反而影響其執(zhí)行，原因見上段的2點.所有程序中，soplex與astar屬于偏離上述相關(guān)關(guān)系的測試程序，經(jīng)過對它們執(zhí)行過程的詳細(xì)分析其性能表現(xiàn)與關(guān)鍵路徑遮擋現(xiàn)象有關(guān)，指令調(diào)度策略屬于流水線的后端執(zhí)行能力研究的范圍，與前端指令供給不相關(guān)，在此不再做展開.

總而言之，帶有DF-Cache的處理器前端，能夠更有效地發(fā)掘計算的數(shù)據(jù)流局部性、增強(qiáng)流水線的指令轉(zhuǎn)化能力.1)它提升指令供給帶寬，增強(qiáng)處理器發(fā)掘ILP的能力；2)它縮短指令供給延遲，降低了分支預(yù)測錯誤帶來的懲罰.

3.2.2數(shù)據(jù)流緩存解耦合流水線前后端

由3.2節(jié)開始對F系列的V-Core和N-Core數(shù)據(jù)的對比可知，V-Core前端能力較弱影響其性能.這是目前大部分DMC技術(shù)需要解決的問題.

首先，我們對比D系列的V-Core與F系列的V-Core的性能數(shù)據(jù)，分析研究DF-Cache加入流水線后解耦合前后端的作用與效果.如圖16所示，除了bzip2，libquantum等ILP較差的程序外，V-Core運(yùn)行的所有程序在DF-Cache的幫助下，IPC都有很大提升.D4-B256相對于F4-B256性能平均提升了5.5%，D4-B512相對于F4-B512性能平均提升了9.4%，尤其是povray性能高達(dá)28%，這說明DF-Cache為后端提供了更多的動態(tài)指令，能夠較大提升流水線性能.

Fig. 16　The influence of DF-Cache on the pipeline of V-Core.圖16　DF-Cache對V-Core流水線性能影響

然后，我們對比具有基本相同硬件開銷的集成了DF-Cache的V-Core與沒有集成DF-Cache的N-Core的數(shù)據(jù).參照圖13，可以看出D4-B256和F6-B256，以及D4-B512和F8-B512性能差距較小，平均性能差距小于5%.

而Core Fusion等DMC設(shè)計其合并后的V-Core性能要大大弱于同寬度的N-Core*例如Core Fusion的8發(fā)射V-Core在運(yùn)行SPEC整型程序時性能只達(dá)到6發(fā)射N-Core的76%，當(dāng)然Core Fusion全面建模了后端，我們對V-Core后端的估計相對樂觀..這說明V-Core流水線后端的指令執(zhí)行能力在DF-Cache的幫助下得到了充分利用.

通過上面2段對DF-Cache加入流水線后性能下限和上限的分析，我們可以看到V-Core不再受限于能力失配的前端，性能更接近其后端的指令執(zhí)行能力.DMC技術(shù)在DF-Cache的幫助下有更高的實用價值.

4結(jié)束語

數(shù)據(jù)流緩存嘗試發(fā)掘程序的數(shù)據(jù)流局部性.通過緩存并重用指令基本塊內(nèi)的數(shù)據(jù)流信息，數(shù)據(jù)流緩存可以旁路取指、譯碼和重命名等流水線前端階段，解耦合流水線的指令供給和指令執(zhí)行功能.

通過分析程序的數(shù)據(jù)流局部性，我們證明了數(shù)據(jù)流緩存能夠以有限的代價覆蓋90%以上的動態(tài)指令.在流水線寬度為4條指令、指令窗口大小為512條指令的虛擬核的配置下，采用數(shù)據(jù)流緩存提升了SPEC CPU2006平均9.4%的執(zhí)行性能.

數(shù)據(jù)流緩存能夠縮短指令供給延遲，提高指令供給帶寬，降低分支預(yù)測錯誤帶來的懲罰，通過解放后端來增強(qiáng)處理器核發(fā)掘ILP的能力.另外，數(shù)據(jù)流緩存替代流水線前端供給指令，解決動態(tài)多核技術(shù)中虛擬核的前端難以協(xié)作工作的問題，提升了動態(tài)多核技術(shù)中虛擬核的性能，增強(qiáng)動態(tài)多核技術(shù)的實用性.

參考文獻(xiàn)

[1]Agarwal V, Hrishikesh M S, Keckler S W, et al. Clock rate versus IPC: The end of the road for conventional microarchitectures[C] //Proc of the 27th Int Symp on Computer Architecture. New York: ACM, 2000: 248-259

[2]Borkar S, Dubey P, Kahn K, et al. Platform 2015: Intel processor and platform evolution for the next decade[J/OL].[2015-03-04]. http://www.researchgate.net/publication/247190040

[3]Hill M D, Marty M R. Amdahl’s law in the multicore era[J]. Computer, 2008, 41(7): 33-38

[4]Hennessy J, Patterson D. Computer Architecture: A Quantitative Approach[M]. San Francisco, CA: Morgan Kaufmann, 2011

[5]Lee L H, Moyer B, Arends J. Instruction fetch energy reduction using loop caches for embedded applications with small tight loops[C] //Proc of the 1999 Int Symp on Low Power Electronics and Design. New York: ACM, 1999: 267-269

[6]Singhal R. Inside Intel next generation Nehalem microarchitecture[C/OL] //Proc of the 20th Symp of Hot Chips. [2015-03-04]. http://www.cs.uml.edu/～bill/cs515/Intel_Nehalem_Processor.pdf

[7]Rotenberg E, Bennett S, Smith J E. Trace cache: A low latency approach to high bandwidth instruction fetching[C] //Proc of the 29th Int Symp on Microarchitecture. Los Alamitos, CA: IEEE Computer Society, 1996: 24-35

[8]Lempel O. 2nd generation Intel core processor family: Intel core i7, i5 and i3[C/OL] //Proc of the 23rd Symp of Hot Chips. [2015-03-04]. http://www.hotchips.org/wp-content/uploads/hc_archives/hc23/HC23.19.9-Desktop-CPUs/HC23.19.911-Sandy-Bridge-Lempel-Intel-Rev 07.pdf

[9]Black B, Rychlik B, Shen J P. The block-based trace cache[C] //Proc of the 26th Int Symp on Computer Architecture. Los Alamitos, CA: IEEE Computer Society, 1999: 196-207

[10]Swanson S, Schwerin A, Mercaldi M, et al. The WaveScalar architecture[J]. ACM Trans on Computer Systems, 2007, 25(2): article 4

[11]Oberoi P S, Sohi G S. Parallelism in the front-end[C] //Proc of the 30th Int Symp on Computer Architecture. New York: ACM, 2003: 230-240

[12]Ipek E, Kirman M, Kirman N, et al. Core fusion: Accommodating software diversity in chip multiprocessors[C] //Proc of the 34th Int Symp on Computer Architecture. New York: ACM, 2007: 186-197

[13]Kim C, Sethumadhavan S, Govindan M S, et al. Composable lightweight processors[C] //Proc of the 40th Int Symp on Microarchitecture. Los Alamitos, CA: IEEE Computer Society, 2007: 381-394

[14]Watanabe Y, Davis J D, Wood D A. WiDGET: Wisconsin decoupled grid execution tiles[C] //Proc of the 37th Int Symp on Computer Architecture. New York: ACM, 2010: 2-13

[15]Rodrigues R, Annamalai A, Koren I, et al. Performance per Watt benefits of dynamic core morphing in asymmetric multicores[C] //Proc of Int Conf on Parallel Architectures and Compilation Techniques. Los Alamitos, CA: IEEE Computer Society, 2011: 121-130

[16]Yeager K C. The MIPS R10000 superscalar microprocessor[J]. IEEE Micro, 1996, 16(2): 28-40

[17]Raasch S E, Binkert N L, Reinhardt S K. A scalable instruction queue design using dependence chains[C] //Proc of the 29th Int Symp on Computer Architecture. Los Alamitos, CA: IEEE Computer Society, 2002: 318-329

[18]Gibson D, Wood D. ForwardFlow: A scalable core for power-constrained CMPs[C] //Proc of the 37th Int Symp on Computer Architecture. New York: ACM, 2010: 14-25

[19]Sohi G S, Vajapeyam S. Instruction issue logic for high-performance, interruptible pipelined computers[C] //Proc of the 14th Int Symp on Computer Architecture. New York: ACM, 1987: 27-34

[20]Kim I, Lipasti M H. Half-price architecture[C] //Proc of the 30th Int Symp on Computer Architecture. New York: ACM, 2003: 28-38

[21]Henning J L. SPEC CPU2006 benchmark descriptions[J]. ACM SIGARCH Computer Architecture News, 2006, 34(4): 1-17

[22]Ardestani E K, Renau J. ESESC: A fast multicore simulator using time-based sampling[C] //Proc of the 19th IEEE Int Symp on High Performance Computer Architecture. Los Alamitos, CA: IEEE Computer Society, 2013: 448-459

Liu Bingtao, born in 1983. PhD candidate. Student member of China Computer Federation. His main research interests include processor microarchitecture, recon-figurable computing and heterogeneous computing.

Wang Da, born in 1981. PhD, associate professor. Member of China Computer Federation. Her main research interests include IC testing and analysis, micro architecture design, many-core processor, and VLSI design and testing.

Ye Xiaochun, born in 1981. PhD, associate professor. Member of China Computer Federation. His main research interests include high-performance computer archi-tecture, software simulation, algorithm paralleling and optimizing.

Zhang Hao, born in 1981. PhD, associate professor. Member of China Computer Federation. Associate chief architect of the Godson-T many core processor. His research interests include high throughput CPU microarchitectures and application analysis.

Fan Dongrui, born in 1979. PhD, professor and PhD supervisor. Member of China Computer Federation. His main research interests include many-core processor design, high throughput processor design and low power micro-architecture.

Zhang Zhimin, born in 1963. Professor and PhD supervisor. His main research interests include SoC design and computer architecture.

A Dataflow Cache Processor Frontend Design

Liu Bingtao1,2, Wang Da1, Ye Xiaochun1, Zhang Hao1, Fan Dongrui1, and Zhang Zhimin1

1(InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100190)2(UniversityofChineseAcademyofSciences,Beijing100049)

AbstractIn order to exploit both thread-level parallelism (TLP) and instruction-level parallelism (ILP) of programs, dynamic multi-core technique can reconfigure multiple small cores to a more powerful virtual core. Usually a virtual core is weaker than a native core with equivalent chip resource. One important reason is that the fetch, decode and rename frontend stages are hard to cooperate after reconfiguration because of their serialized processing nature. To solve this problem, we propose a new frontend design called the dataflow cache with a corresponding vector renaming (VR) mechanism. By caching and reusing the data dependencies and other information of the instruction basicblock, the dataflow cache exploits the dataflow locality of programs. Firstly, the processor core can exploit better instruction-level parallelism and lower branch misprediction penalty with dataflow cache; Secondly, the virtual core in dynamic multi-core can solve its frontend problem by using dataflow cache to bypass the traditional frontend stages. By experimenting on the SPEC CPU2006 programs, we prove that dataflow cache can cover 90% of the dynamic instructions with limited cost. Then, we analyze the performance effect of adding the dataflow cache to pipeline. At last, experiments show that with a frontend of 4-instruction wide and an instruction window of 512-entry, the performance of the virtual core with dataflow cache is improved up to 9.4% in average with a 28% maximum for some programs.

Key wordsprocessor microarchitecture; instruction cache (ICache); dataflow; instruction renaming; dataflow locality

收稿日期：2015-04-23；修回日期：2015-07-14

基金項目：國家“九七三”重點基礎(chǔ)研究發(fā)展計劃基金項目(2011CB302501)；國家“八六三”高技術(shù)研究發(fā)展計劃基金項目(2015AA011204,2012AA010901)；“核高基”國家科技重大專項基金項目(2013ZX0102-8001-001-001)；國家自然科學(xué)基金重點項目(61332009,61173007)

中圖法分類號TP303

This work was supported by the National Basic Research Program of China (973 Program) (2011CB302501), the National High Technology Research and Development Program of China (863 Program) (2015AA011204,2012AA010901), the National Science and Technology Major Projects of Hegaoji (2013ZX0102-8001-001-001), and the Key Program of the National Natural Science Foundation of China (61332009,61173007).