基于結(jié)果冗余解決數(shù)據(jù)相關(guān)的新技術(shù)探討

摘 要：本文由流水線技術(shù)的相關(guān)問(wèn)題引出基于結(jié)果冗余避免暫停的值預(yù)測(cè)技術(shù)和指令用技術(shù)，并通過(guò)實(shí)例將這兩種技術(shù)和重定向技術(shù)比較，驗(yàn)證二者的優(yōu)越性。最后對(duì)兩種技術(shù)進(jìn)行了比較、總結(jié)，并提出兩種技術(shù)可改進(jìn)性的看法。

關(guān)鍵詞：結(jié)果冗余；值預(yù)測(cè)技術(shù)；指令用技術(shù)

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-7712 （2013） 18-0000-02

流水線技術(shù)是把一個(gè)重復(fù)的時(shí)序過(guò)程分解為若干個(gè)子過(guò)程，而每一個(gè)子過(guò)程都可以有效的在其專用功能段上與其他子過(guò)程并行執(zhí)行。

流水線技術(shù)在一定程度上能提高指令的執(zhí)行速度，但如果處理不好，指令的運(yùn)行將達(dá)不到預(yù)期的結(jié)果，因?yàn)榱魉€的各個(gè)段之間存在較強(qiáng)的依賴關(guān)系。這些依賴關(guān)系主要體現(xiàn)在數(shù)據(jù)相關(guān)、控制相關(guān)和資源相關(guān)三種相關(guān)。微處理器硬件資源的豐富和分支預(yù)測(cè)技術(shù)的進(jìn)步比較有效的解決了控制相關(guān)和資源相關(guān)的問(wèn)題，而數(shù)據(jù)相關(guān)是提高指令級(jí)并行的重要技術(shù)手段之一。

一、目前解決數(shù)據(jù)相關(guān)的技術(shù)

在指令的執(zhí)行過(guò)程中，經(jīng)常出現(xiàn)這樣一種情況：后續(xù)指令的操作數(shù)或變址偏移量正好是或依賴于前面指令的執(zhí)行結(jié)果，那么必須進(jìn)入等待狀態(tài)，直到前面指令執(zhí)行完成并將結(jié)果存儲(chǔ)到通用寄存器中，這種現(xiàn)象稱為數(shù)據(jù)相關(guān)性。數(shù)據(jù)相關(guān)性極大地影響了程序的執(zhí)行效率和穩(wěn)定性。

目前，消除數(shù)據(jù)相關(guān)主要通過(guò)數(shù)據(jù)重定向技術(shù)來(lái)實(shí)現(xiàn)。數(shù)據(jù)重定向技術(shù)也稱數(shù)據(jù)旁路技術(shù)。因?yàn)橥谀硹l指令產(chǎn)生結(jié)果之前，其它指令未必真正需要其計(jì)算結(jié)果，通過(guò)設(shè)置相關(guān)的專用通路，直接把前一條指令的ALU計(jì)算機(jī)結(jié)果作為下一條指令的輸入數(shù)據(jù)開(kāi)始計(jì)算，這樣就不用必須等待前一條指令完全執(zhí)行完成后將計(jì)算結(jié)果寫(xiě)回寄存器組，使原本需要暫停等待的操作變得可以繼續(xù)執(zhí)行，縮短了時(shí)間提高了效率。

雖然重定向技術(shù)在一定程度上減少了指令間相互等待的時(shí)間，提高了并行速度，但仍然有其局限性。它并不能使有數(shù)據(jù)相關(guān)的串行化指令并行執(zhí)行，串行化指令仍需等待，對(duì)于有豐富流水線資源能同時(shí)發(fā)射多條指令的處理器而言，其發(fā)揮空間受到限制。

二、基于結(jié)果冗余的兩種方法的提出

（一）理論背景

程序執(zhí)行過(guò)程中各指令可產(chǎn)生三種類型的結(jié)果：首次生成的新結(jié)果；與之前結(jié)果值相同的結(jié)果；可由其他結(jié)果推導(dǎo)生成的結(jié)果。這三種結(jié)果對(duì)應(yīng)三種指令名稱：獨(dú)特型指令、重復(fù)型指令和可推導(dǎo)型指令，重復(fù)型指令和可推導(dǎo)型指令的集合又稱為冗余指令。

經(jīng)實(shí)驗(yàn)統(tǒng)計(jì)[1]，：只有很少量的指令（<5%）能生產(chǎn)出新的結(jié)果，絕大部分指令（80%～90%）生產(chǎn)的是重復(fù)的結(jié)果，另有一部分指令（<5%）生產(chǎn)的結(jié)果是可推導(dǎo)的，即程序中存在大量的執(zhí)行結(jié)果冗余。因此，我們可以利用結(jié)果冗余，提出解決數(shù)據(jù)相關(guān)的技術(shù)：值預(yù)測(cè)技術(shù)和指令重用技術(shù)。

（二）值預(yù)測(cè)技術(shù)

值預(yù)測(cè)技術(shù)是一種推斷技術(shù)。值預(yù)測(cè)技術(shù)首先要借助存儲(chǔ)值預(yù)測(cè)表來(lái)存儲(chǔ)指令的預(yù)測(cè)值。在取指階段，用先行指令的地址PC索引值預(yù)測(cè)表；在譯碼階段從值預(yù)測(cè)表中獲取先行指令的預(yù)測(cè)值，然后立刻將該預(yù)測(cè)值送至正在等待該操作數(shù)的后繼指令，后續(xù)指令就利用這個(gè)預(yù)測(cè)值進(jìn)行運(yùn)算，這樣即使兩條指令存在數(shù)據(jù)相關(guān)性仍能并發(fā)執(zhí)行。當(dāng)先行指令計(jì)算出結(jié)果后，將該結(jié)果與之前的預(yù)測(cè)值進(jìn)行對(duì)比，若結(jié)果與預(yù)測(cè)值不符，則說(shuō)明之前的預(yù)測(cè)值是錯(cuò)誤的，必須取消所有使用預(yù)測(cè)值的運(yùn)算指令，并重新發(fā)射新的后繼指令，將正確的結(jié)果作為新指令執(zhí)行的操作數(shù)。若結(jié)果與預(yù)測(cè)值相同，則說(shuō)明之前的運(yùn)算都是基于正確的操作數(shù)進(jìn)行的，無(wú)需回退，可以繼續(xù)后繼指令的執(zhí)行，從而實(shí)現(xiàn)存在數(shù)據(jù)相關(guān)性的兩條指令的并發(fā)執(zhí)行。因此，值預(yù)測(cè)技術(shù)先推斷先行指令的結(jié)果，后使先行指令與后繼指令并行執(zhí)行，從而消除了數(shù)據(jù)相關(guān)、提高了指令級(jí)并行。

其流水線結(jié)構(gòu)如下圖：

例1 假設(shè)有相關(guān)指令：I1：DECR1；I2：FADDR2，R1；

根據(jù)值預(yù)測(cè)技術(shù)，I1和I2同時(shí)取指，同時(shí)根據(jù)I1的地址PC索引值預(yù)測(cè)表；在兩條指令譯碼的同時(shí)，把值預(yù)測(cè)表中的值送到等待該操作數(shù)的I2指令；兩條指令并行執(zhí)行，得出I1與I2的值；執(zhí)行后把I1的結(jié)果與預(yù)測(cè)值比較，如果是相同的，則I2的值就可確認(rèn)，如果不相同，則用I1的值重新計(jì)算I2。下圖顯示了重定向技術(shù)與值預(yù)測(cè)技術(shù)預(yù)測(cè)正確情況下的流程：

可見(jiàn)，在預(yù)測(cè)成功的前提下，值預(yù)測(cè)技術(shù)比重定向技術(shù)更有消除數(shù)據(jù)相關(guān)的潛力，它能使存在數(shù)據(jù)相關(guān)性的兩條指令實(shí)現(xiàn)真正的并發(fā)執(zhí)行，實(shí)現(xiàn)無(wú)縫連接，極大地提高了執(zhí)行效率。

（三）指令重用技術(shù)

指令重用技術(shù)是一種非推斷執(zhí)行技術(shù)。指令重用技術(shù)借助重用緩沖器，存儲(chǔ)某初次執(zhí)行的指令的結(jié)果。當(dāng)同樣的指令再次出現(xiàn)（即指令的PC和操作數(shù)均相同）時(shí)，不必再次對(duì)其執(zhí)行運(yùn)算，而是在取指的同時(shí)直接賦值；在譯碼的同時(shí)用生用檢驗(yàn)機(jī)制檢查指令當(dāng)前操作數(shù)的值與以前執(zhí)行過(guò)的操作數(shù)是否相同，如果相同，等待結(jié)果確認(rèn)后就可退出流水線，如果不同，則執(zhí)行指令。

仍然以例1為例，可得到下面的比較表：

三、值預(yù)測(cè)技術(shù)與指令重用技術(shù)的比較

二者都是基于結(jié)果冗余的解決數(shù)據(jù)相關(guān)問(wèn)題的技術(shù)，通過(guò)這兩種技術(shù)，后繼指令不必等先行指令執(zhí)行出結(jié)果后再發(fā)射和執(zhí)行，提高了指令級(jí)并行，緩解了數(shù)據(jù)流限制。但二者還是存在明顯不同：（1）前者先推斷使用預(yù)測(cè)值，在計(jì)算得到先行指令結(jié)果后再檢驗(yàn)預(yù)測(cè)值的正確性；而后者是非推斷執(zhí)行的，在使用重用結(jié)果前就進(jìn)行檢驗(yàn)。（2）前者適用的情況更多。比如，操作數(shù)還未到位的情況，以及兩條指令結(jié)果相同但操作數(shù)不同的情況，值預(yù)測(cè)技術(shù)能預(yù)測(cè)出這兩種情況的結(jié)果，但不能用指令重用技術(shù)。（3）前者預(yù)測(cè)失敗會(huì)帶來(lái)?yè)p失，但后者不會(huì)出現(xiàn)任何因預(yù)測(cè)錯(cuò)誤帶來(lái)的損失。因?yàn)橹噶钪赜迷趫?zhí)行前就進(jìn)行了驗(yàn)證；值預(yù)測(cè)技術(shù)是在執(zhí)行后才檢驗(yàn)出的，如果出錯(cuò)，則要重新執(zhí)行，因此對(duì)資源需求也較大。（4）前者會(huì)增加分支預(yù)測(cè)錯(cuò)誤的損失，當(dāng)它出現(xiàn)錯(cuò)誤時(shí)不僅會(huì)造成更多的錯(cuò)誤預(yù)測(cè)，還會(huì)延遲分支預(yù)測(cè)；而后者由于在較早時(shí)間就能檢驗(yàn)到分支錯(cuò)誤，因此能減少損失。（5）通過(guò)實(shí)例的流水線執(zhí)行情況來(lái)看兩個(gè)技術(shù)的執(zhí)行延遲，明顯指令重用技術(shù)減少了執(zhí)行時(shí)間，縮短了一個(gè)周期，因此它的執(zhí)行延遲被降低了；但值預(yù)測(cè)技術(shù)較重定向技術(shù)的執(zhí)行延遲是沒(méi)有變化的。

四、結(jié)論

值預(yù)測(cè)技術(shù)和指令重用技術(shù)是對(duì)解決數(shù)據(jù)相關(guān)問(wèn)題技術(shù)的擴(kuò)展，但這兩種技術(shù)對(duì)硬件提出了更高的要求，當(dāng)流水線規(guī)模較小，或數(shù)據(jù)相關(guān)不嚴(yán)重時(shí)用這兩種方法的硬件性價(jià)并不劃算；指令重用技術(shù)空閑的執(zhí)行周期可能導(dǎo)致競(jìng)爭(zhēng)資源，將會(huì)引發(fā)其他的數(shù)據(jù)相關(guān)；而且指令重用技術(shù)存在著預(yù)測(cè)失敗的風(fēng)險(xiǎn)，所以對(duì)某些特定指令用重定位的代價(jià)可能更小。

針對(duì)值預(yù)測(cè)的失敗風(fēng)險(xiǎn)，本人認(rèn)為可以通過(guò)改進(jìn)值預(yù)測(cè)表的形成以及值預(yù)測(cè)表的大小來(lái)提高預(yù)測(cè)成功率。一、指令產(chǎn)生結(jié)果的歷史信息具有一定的分析利用價(jià)值，需要更大的存儲(chǔ)空間進(jìn)行存儲(chǔ)，因此，值預(yù)測(cè)器的存儲(chǔ)空間需要增大。二、多條指令會(huì)在同一時(shí)鐘周期查詢和更新值預(yù)測(cè)器，為了減少?zèng)_突的產(chǎn)生，需要為值預(yù)測(cè)器設(shè)計(jì)多端口訪問(wèn)機(jī)制，以滿足多條指令的需求。要實(shí)現(xiàn)上述功能，可以嘗試通過(guò)減少值歷史表的表項(xiàng)數(shù)量、限制訪問(wèn)端口數(shù)量等方法來(lái)提高值預(yù)測(cè)機(jī)制的可用性。

參考文獻(xiàn)：

[1]Sazeides Y，Smith J E.The predictability of data Values.In：Proceedings of the 30th International Symposium on Microarchi-tecture.Dec.1997.248.

[2]鄭緯民，湯志忠.計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，1998.

[3]肖勇.值預(yù)測(cè)技術(shù)研究[D].國(guó)防科學(xué)技術(shù)大學(xué)，2005.

[4]冀蓉，張民選，鄧讓鈺.推測(cè)執(zhí)行中值預(yù)測(cè)與指令重用技術(shù)的研究與分析[J].計(jì)算機(jī)工程與科學(xué)，2005，11.

[作者簡(jiǎn)介]鄭富煌（1982-），男，福建仙游人，福建對(duì)外經(jīng)濟(jì)貿(mào)易職業(yè)技術(shù)學(xué)院信息技術(shù)系，福州大學(xué)物理與信息工程學(xué)院電子與通信工程專業(yè)，研究方向：電子與通信工程。