EPIC微體系結(jié)構(gòu)的存儲(chǔ)級(jí)并行執(zhí)行模型的研究

1、EPIC微體系結(jié)構(gòu)的存儲(chǔ)級(jí)并行執(zhí)行模型的研究簡(jiǎn)介 這是一種可以有效提高存儲(chǔ)級(jí)并行(Memory Level Parallelism, MLP)的指令優(yōu)化鎖步執(zhí)行模型 OLSM (Optimized LockStepexecution Model)執(zhí)行模型, 并建立了一種能體現(xiàn)OLSM模型思想的層次存儲(chǔ)結(jié)構(gòu).OLSM允許顯示并行指令計(jì)算( Explicit Parallel Instruction Computing, EPIC)微處理器實(shí)現(xiàn)一定程度的亂序執(zhí)行,解決了傳統(tǒng)超長(zhǎng)指令字(Very Long Instruction Word, VLIW)鎖步執(zhí)行的缺陷, 可以充分利用結(jié)構(gòu)中的大量計(jì)算和

2、存儲(chǔ)資源,最大化隱藏存儲(chǔ)延遲、提高M(jìn)LP. 顯式并行指令計(jì)算（EPIC）技術(shù): 指令中設(shè)計(jì)了屬性字段,用于指明哪些指令可以并行執(zhí)行。這些屬性信息并不是在指令執(zhí)行過程中由處理機(jī)判定后獲得的，而是由編譯程序在編譯時(shí)通過對(duì)源代碼的分析獲取指令級(jí)的并行性信息，并填寫到執(zhí)行代碼中。這就是所謂顯式并行的概念。 超長(zhǎng)指令字:是將水平型微碼和超標(biāo)量處理相結(jié)合。在編譯時(shí)，將多個(gè)能并行執(zhí)行的不相關(guān)或無關(guān)的操作組合在一起，形成一條有多個(gè)操作碼字段的超長(zhǎng)指令字。運(yùn)行時(shí)，直接控制機(jī)器中多個(gè)相互獨(dú)立的功能部件并行操作，來實(shí)現(xiàn)同時(shí)執(zhí)行多條指令。一 、引言 EPIC體系結(jié)構(gòu)的本質(zhì)是VLIW, 同時(shí)還吸取了超標(biāo)量處理器的許多新

3、思想. 通過指令集顯式表達(dá)并行性信息, 如每個(gè)指令可以有多個(gè)操作( MultiOP) ,程序執(zhí)行計(jì)劃( PlanOf Execution, POE) 通過指令集傳遞給硬件, 這樣既保持了VLIW由編譯器靜態(tài)構(gòu)造POE的特點(diǎn), 同時(shí)又具有一定的動(dòng)態(tài)特性, 使處理器硬件更簡(jiǎn)單。 VLIW結(jié)構(gòu)中, 多操作指令直接利用操作的非原子性特點(diǎn): 操作的執(zhí)行時(shí)間至少為1個(gè)時(shí)鐘周期,同一發(fā)射組的各個(gè)操作需要同時(shí)寫結(jié)果, 因此, 即使指令存在反相關(guān)也可以調(diào)度到同一個(gè)多操作( 指令組) 中. 另外, 同一指令的兩個(gè)操作也可以存在反相關(guān), 例如, 寄存器原子交換可以實(shí)現(xiàn)成兩個(gè)復(fù)制操作、互相寫. EPIC結(jié)構(gòu)中, 某些

4、操作可能需要多個(gè)時(shí)鐘周期才能完成, 編譯器必須能夠理解這些延遲, 才能獲得正確和高質(zhì)量的代碼調(diào)度. 最佳情況是, 編譯器知道操作發(fā)射后讀操作數(shù)和寫結(jié)果的確切時(shí)刻, 這樣就可以將代碼調(diào)度成: 每個(gè)操作的目的寄存器的舊值在操作發(fā)射之前, 到操作執(zhí)行完之間的時(shí)間段仍可用( 一般來說這是違背順序語(yǔ)義的) . 只在操作結(jié)束時(shí)保留這些操作的結(jié)果寄存器, 這樣可以減少臨時(shí)寄存器的壓力. 1.1、UAL( Unit AssumedLatency) 延遲語(yǔ)義 RISC和超標(biāo)量處理器都采用UAL延遲語(yǔ)義,這是一種順序模型, 不能把延遲暴露出來. 程序的虛調(diào)度時(shí)間( 指令執(zhí)行的時(shí)間單位) 假定每個(gè)操作的延遲都為1,

5、 即假定每條指令發(fā)射前, 上一指令已經(jīng)完成. 如果以前的指令延遲大于1, 處理器必須能夠保證后續(xù)相關(guān)指令獲得正確的值, 通常辦法是, 停頓后續(xù)的相關(guān)指令. 圖1( a) 是一段用UAL延遲語(yǔ)義調(diào)度的代碼,其相關(guān)語(yǔ)義如圖1( b) . 1.2、NUAL延遲語(yǔ)義 NUAL( Non Unit Assumed Latency) 延遲語(yǔ)義是指, 結(jié)構(gòu)中 ( a) 至少有一個(gè)操作的延遲為L(zhǎng), L1; ( b) 當(dāng)前操作完成前, 可發(fā)射后面的L- 1條指令, 且程序語(yǔ)義正確. 用NUAL語(yǔ)義調(diào)度上述相同代碼, 其相關(guān)語(yǔ)義見圖2. T1 和T2 連續(xù)發(fā)射兩條指令, 盡管第一條指令在T10才產(chǎn)生出結(jié)果. EQ

6、( equals) 是最嚴(yán)格的NUAL形式, 即讀操作數(shù)的準(zhǔn)確時(shí)間就在發(fā)射時(shí)刻, 產(chǎn)生結(jié)果的時(shí)刻也在指定的延遲時(shí)間點(diǎn)上. 另一種NUAL 是LEQ( lessor equals) , 寫結(jié)果事件的時(shí)刻范圍在1個(gè)時(shí)鐘周期到假定的延遲之間, 可以簡(jiǎn)化精確中斷的實(shí)現(xiàn). 使用LEQ延遲語(yǔ)義調(diào)度的代碼即使實(shí)際操作比假定時(shí)間快, 程序也是正確的, 可實(shí)現(xiàn)二進(jìn)制兼容.目前, VLIW和EPIC都主要使用NUAL延遲語(yǔ)義, 允許結(jié)構(gòu)在性能、硬件簡(jiǎn)單性以及不同硬件實(shí)現(xiàn)間的兼容性方面進(jìn)行折衷.二、基本NUAL執(zhí)行模型 2.1、延遲緩沖執(zhí)行模型 由于每個(gè)時(shí)鐘周期都可能發(fā)射新操作, 對(duì)于EQ操作, 為了不違背EQ語(yǔ)義

7、, 不能過早寫結(jié)果, 也不能因?yàn)橥韺懚枞δ芰魉€. 解決這個(gè)問題的一種方法是功能部件的輸出使用延遲緩沖區(qū), 使寫事件延遲一定的時(shí)間. 2.2、延遲停頓執(zhí)行模型 NUAL操作在指定時(shí)間內(nèi)不能按時(shí)完成, 最簡(jiǎn)單的控制辦法是在產(chǎn)生結(jié)果前停止推進(jìn)指令執(zhí)行的虛時(shí)間, 暫停指令發(fā)射, 也不再讀、寫結(jié)構(gòu)寄存器, 這就是延遲停頓( latency stalling) . 假設(shè)一個(gè)操作的調(diào)度延遲為P, 在功能部件中執(zhí)行的實(shí)際延遲為V, 則最大需要停頓(V-P)個(gè)時(shí)鐘周期, 這就保證了消費(fèi)者肯定可以取得正確的操作數(shù). 這種方法的優(yōu)點(diǎn)是不需要檢查源和目的操作數(shù)的使用情況, 不需要記錄寄存器使用蹤跡, 簡(jiǎn)化了硬件

8、設(shè)計(jì). 另外, 這種方法可保證NUAL操作的完成時(shí)間不會(huì)比假定的短,這也是必須的, 因?yàn)樵谌魏握{(diào)度虛時(shí)間點(diǎn)上, 讀或?qū)懯录鄬?duì)于寫事件進(jìn)行了重新排序后, 程序正確性就可能得不到保證. 調(diào)度得很好、很緊湊的代碼總希望事件在與之相關(guān)的寫事件后立即發(fā)生. 延遲停頓在實(shí)現(xiàn)上除了需要保證正確性外, 還要使插入的停頓盡可能少. Rau曾提出了一種修改延遲停頓的簡(jiǎn)單方法, 該方法可以保證在虛時(shí)間上與編譯器調(diào)度一致。 虛時(shí)間停頓后, 處理其它可以按時(shí)完成的操作方法有兩種: ( 1) 凍結(jié)功能流水線上的可按時(shí)完成操作, 但不阻塞不可按時(shí)完成的NUAL操作. 由于不再發(fā)射新指令, 中斷也不能使用該凍結(jié)的功能部件,

9、 因此, 這種方法可能存在死鎖; ( 2) 許可按時(shí)完成的操作繼續(xù)前進(jìn), 而不考慮虛時(shí)間是否推進(jìn). 這種方法的優(yōu)點(diǎn)是, 當(dāng)前不能完成的操作可以充分利用停頓虛時(shí)間停頓周期, 來減少它完成的時(shí)間, 甚至可能完全消除其延遲, 從而使該操作成為可按時(shí)完成操作. 延遲停頓的缺點(diǎn)是, 即使不存在相關(guān)性, 指令的發(fā)射也可能停頓. 不能按時(shí)完成操作的其它處理方法還有許多, 這些方法性能很可能更高, 但代價(jià)也更大. 例如, 某些鎖步方法, 只在必須的時(shí)候才停止發(fā)射指令, 性能高了, 代價(jià)也大了. 傳統(tǒng)的順序鎖步( in order interlock) 模型, 常用于順序性ISA結(jié)構(gòu), 對(duì)操作的虛擬完成時(shí)間沒有

10、任何控制, 因而不能支持NUAL, 這是與延遲停頓方法的根本區(qū)別. 2.3、基本鎖步執(zhí)行模型 NUAL鎖步與延遲停頓的方法相似, 區(qū)別在于需要記錄不能按時(shí)完成操作的軌跡. 延遲停頓需要停止發(fā)射指令( 寫目的的虛時(shí)間點(diǎn)) , 而NUAL鎖步僅僅把目的寄存器標(biāo)識(shí)為無效, 然后繼續(xù)發(fā)射新指令, 操作完成時(shí), 寄存器再標(biāo)識(shí)為有效. 準(zhǔn)備發(fā)射指令時(shí), 只在讀到一個(gè)無效寄存器( 如寫后讀互鎖) 或第二個(gè)操作準(zhǔn)備寫一個(gè)無效寄存器( 寫后寫互鎖)時(shí), 才停止指令發(fā)射和虛時(shí)間推進(jìn). 一旦寄存器可用, 立即恢復(fù)指令發(fā)射. NUAL鎖步確保了對(duì)寄存器的所有讀、寫事件的相對(duì)順序, 即程序正確性語(yǔ)義。 盡管NUAL鎖步

11、有許多優(yōu)點(diǎn), 但延遲停頓對(duì)嵌入式處理器來說也是必不可少, 畢竟簡(jiǎn)單性對(duì)這類處理器來說至關(guān)重要, 并且重新編譯程序也是可以接受的. 原則上用MultiOp和NUAL語(yǔ)義可以實(shí)現(xiàn)亂序執(zhí)行, 但會(huì)破壞EPIC設(shè)計(jì)思想, 需要避免。 對(duì)于原子操作, NUAL鎖步模型與順序鎖步模型相同, 即操作的目的寄存器在指令發(fā)射時(shí)標(biāo)識(shí)為無效, 如果指令需要讀或?qū)懸粋€(gè)無效寄存器, 那么指令不再發(fā)射. 2.4、執(zhí)行模型比較 NUALEQ語(yǔ)義提供給編譯器的信息最確定,因而優(yōu)化的機(jī)會(huì)最大 實(shí)際上, 與短延遲操作存在反相關(guān)的長(zhǎng)延遲EQ操作甚至可以在后者之前發(fā)射. 相反, LEQ語(yǔ)義中, 如果操作之間存在反相關(guān),則不能在反相關(guān)

12、解決之前發(fā)射. 另外, EQ功能流水部件需要延遲緩沖區(qū)和一個(gè)用于選擇流水線或延遲緩沖區(qū)的開關(guān), 而LEQ操作產(chǎn)生結(jié)果的時(shí)刻比預(yù)計(jì)時(shí)間早, 于是結(jié)果不需保存到延遲緩沖區(qū). 如果應(yīng)用本身對(duì)延遲增長(zhǎng)不十分敏感, 那么使用EQ比較有利, 但會(huì)增加寄存器的使用壓力. 如果實(shí)際延遲與假定延遲之間的比值較大, 延遲停頓模型的性能會(huì)很差. 如果調(diào)度存在某些難以克服的問題, 如事件之間存在相關(guān)且事件的調(diào)度順序不能改變, 那么NUAL鎖步模型比延遲停頓模型性能上要好得多. 鎖步模型中, 程序中復(fù)雜的控制流可能導(dǎo)致實(shí)際處理過程不流暢, 這是因?yàn)榫幾g代碼調(diào)度不太可能同時(shí)使所有路徑都最優(yōu), 而只能保證某些可能性最大的路

13、徑比可能性小的路徑要優(yōu), 實(shí)際上, 很多情況在編譯時(shí)是很難確定的. 這樣, 編譯器能開發(fā)的理論ILP往往比硬件實(shí)際執(zhí)行時(shí)的ILP要高得多。三、基本EPIC執(zhí)行模型 基本EPIC結(jié)構(gòu)采用鎖步模型, 假定所有非存儲(chǔ)操作的延遲為1個(gè)時(shí)鐘周期, 通過延遲緩沖區(qū)和停止存在相關(guān)的操作來維護(hù)程序正確性. 具體執(zhí)行模式為: 任意指令I(lǐng)j 能夠發(fā)射的前提條件是指令I(lǐng)j之前的所有指令都已經(jīng)或者能夠與指令I(lǐng)j 同時(shí)發(fā)射. 為了能夠盡可能提高性能, 如果指令不能寫結(jié)果則需要進(jìn)入緩沖區(qū), 等待寫結(jié)果的時(shí)機(jī). 因此, 基本的EPIC模型實(shí)際上是帶延遲緩沖的鎖步模型. 能夠同時(shí)發(fā)射的指令一定屬于同一個(gè)指令組,我們稱這些并行

14、發(fā)射的指令為一個(gè)發(fā)射組或執(zhí)行組( executing group) , 即一個(gè)MultiOp. 編譯器保證同一指令組中各指令之間不存在寫后讀相關(guān)( ReadAfter Write, RAW) 和寫后寫相關(guān)( Write AfterWrite, WAW) , 同一發(fā)射組內(nèi)部不需要檢查RAW和WAW寄存器相關(guān)性, 簡(jiǎn)化了沖突檢查邏輯. 假定某EPIC微處理器共有11條流水線( 4條存儲(chǔ)流水線, 2條整數(shù)流水線, 2條浮點(diǎn)流水線和3條分支流水線) . 主流水線采用8站, 分別為FETCH、PREDICT、ISSUE、RENAME、REG、EXE、COMMIT 和WRB. 整個(gè)流程上可以分為前端和后端

15、, 前端包括FETCH和PREDICT, 完成取指令流任務(wù); 后端包括ISSUE、RENAME、REG、EXE、COMMIT 和WRB, 分別實(shí)現(xiàn)指令發(fā)射、寄存器換名、讀操作數(shù)、執(zhí)行、提交和寫回. 指令后端流水線在執(zhí)行( EXE) 階段之前( 不包括EXE) 都是順序的, 即順序發(fā)射. 從發(fā)射組的角度看, 順序流出發(fā)射組, 多條流水線中的同一個(gè)發(fā)射組中的多條指令在EXE階段之前都是同步前進(jìn)的, 而且不同發(fā)射組的指令在EXE階段之前沒有交叉, 保持嚴(yán)格的先后順序. 但是, 發(fā)射組進(jìn)入EXE階段之后, 由于存儲(chǔ)操作的延遲不確定, 同一發(fā)射組的指令到達(dá)COMMIT站的時(shí)機(jī)也不確定, 因此EXE站需要

16、設(shè)計(jì)采用亂序執(zhí)行( out of order executing) 的策略. 為了支持精確中斷, 同一發(fā)射組需要實(shí)現(xiàn)指令順序提交( in order committing) . 因此, 基本EPIC執(zhí)行模型的特點(diǎn)是: ( 1) 順序發(fā)射, 亂序執(zhí)行, 順序提交, 順序?qū)懟?即各主流水站嚴(yán)格鎖步, 同一發(fā)射組的指令必須按序提交, 以支持精確中斷. ( 2) 各功能流水線的COMMIT 站為等深度的FIFO緩沖區(qū), 數(shù)據(jù)旁路和數(shù)據(jù)相關(guān)性判定必須針對(duì)每項(xiàng)有效緩沖區(qū). 3.1 基本EPIC執(zhí)行模型的存儲(chǔ)層次 各指令流水線中, 只有存儲(chǔ)操作的延遲不確定.Cache命中時(shí), 可以在1個(gè)時(shí)鐘周期內(nèi)提供數(shù)據(jù),

17、 與整數(shù)運(yùn)算的操作延遲相匹配; Cache不命中時(shí), 存儲(chǔ)訪問處理時(shí)間可能比較長(zhǎng). 為了使系統(tǒng)性能最大化,各流水線附帶一個(gè)延遲寫結(jié)果緩沖區(qū), 一旦結(jié)果有效, 將結(jié)果寫入延遲緩沖區(qū). 只有同一發(fā)射組的所有指令的結(jié)果都生產(chǎn)出來后, 指令組才在同一時(shí)刻提交, 因此各功能流水線的COMMIT站實(shí)際上采用等深度的緩沖隊(duì)列. 存儲(chǔ)層次及各流水線的基本結(jié)構(gòu)見圖3. 存儲(chǔ)操作在EXE站完成對(duì)L1數(shù)據(jù)Cache( L1D) 的訪問, 失效時(shí)還需要訪問L2Cache, 甚至主存, 取得結(jié)果后, 填充L1D, 然后進(jìn)入COMMIT. L1D與L2Cache保持嚴(yán)格的低、高級(jí)關(guān)系. 圖3中SBI( SystemBus

18、Interface) 為總線接口部件. 3.2 基本EPIC執(zhí)行模型的MLP分析 通過EXE站亂序執(zhí)行來盡可能地隱藏訪問延遲, 要求有足夠的存儲(chǔ)指令發(fā)送到存儲(chǔ)部件. 因此,數(shù)據(jù)Cache系統(tǒng)的實(shí)際MLP水平極大程度上受限于延遲緩沖區(qū)的深度(d)和存儲(chǔ)流水線數(shù)目(w), 即 MLPI -Cache與指令Cache的設(shè)計(jì)有關(guān), 在EPIC結(jié)構(gòu)中主要強(qiáng)調(diào)預(yù)取指令流. 盡管預(yù)取本身并不是開發(fā)MLP的途徑, 但從L2Cache處理角度看, 指令預(yù)取將產(chǎn)生大量的未完成訪存操作, 因此對(duì)MLP有一定作用. 衡量程序性能的重要參數(shù)是平均MLP, 用MLPBasemean表示. 由于EPIC鎖步的本性, 要使流

19、水線因?yàn)榇鎯?chǔ)數(shù)據(jù)供應(yīng)不上導(dǎo)致停頓的前提是: 首次訪問未完成存儲(chǔ)操作的目的寄存器. 該首次訪問的時(shí)刻即為L(zhǎng)oad-to-Use時(shí)刻. Load-to-Use的平均時(shí)間間距可以反映微處理器結(jié)構(gòu)、代碼優(yōu)化及程序行為特性, 用Dist 表示. 影響MLPBasemean的因素有Dist、存儲(chǔ)資源的使用率等.四、OLSM執(zhí)行模型 上節(jié)我們已經(jīng)提到, 基本EPIC鎖步模型中EXE站亂序執(zhí)行策略要求有足夠的存儲(chǔ)指令發(fā)送到存儲(chǔ)部件, 才有可能提高M(jìn)LP. 由于RENAME、REG以及進(jìn)入COMMIT站都是鎖步的, 要使每條存儲(chǔ)流水線都有一條以上的存儲(chǔ)指令, 實(shí)際上既受延遲緩沖區(qū)深度的影響, 也與程序本身的特點(diǎn)

20、密切相關(guān). 基本EPIC模型的另一個(gè)問題是: 數(shù)據(jù)相關(guān)性控制和數(shù)據(jù)旁路邏輯極復(fù)雜. 在基本EPIC模型中,COMMIT站采用3深度緩沖區(qū), 意味著緩沖區(qū)每一項(xiàng)都有可能成為結(jié)果數(shù)據(jù)的“ 寄存塢” , 取源操作數(shù)的旁路邏輯需要1200個(gè)比較器, 代價(jià)極大, 電路時(shí)延很難控制. 相關(guān)性控制與旁路邏輯息息相關(guān), 旁路所在的流水站肯定是相關(guān)性控制所覆蓋的流水站.3深度延遲緩沖區(qū)旁路相當(dāng)于有3站COMMIT, 無論如何控制WAW和RAW, 記分牌邏輯都是復(fù)雜的, 且極不規(guī)整。 各流水線有如下幾個(gè)基本特點(diǎn): ( 1) 整數(shù)操作可以在EXE站完成運(yùn)算. ( 2) 大部分存儲(chǔ)操作可以在EXE站完成運(yùn)算. ( 3

21、) 少數(shù)存儲(chǔ)操作盡管不能在EXE站完成所有運(yùn)算, 但可以在COMMIT 站判定是否異常( 數(shù)據(jù)Cache或TLB不命中、指令非法或數(shù)據(jù)錯(cuò)) . 根據(jù)上述特點(diǎn), 作如下修正: REG站登記記分牌, 在COMMIT站, 只檢查指令是否產(chǎn)生異常, 只有產(chǎn)生異?；蚪Y(jié)果已經(jīng)生產(chǎn)出來的指令才可以清記分牌, 不保證COMMIT 指令的數(shù)據(jù)可以立即通過WRB站寫回結(jié)構(gòu)寄存器. 此模型去掉了基本EPIC模型中的延遲緩沖區(qū), 同時(shí)可確保指令后端各流水站都是鎖步執(zhí)行的, 這就是基于NUAL語(yǔ)義的優(yōu)化的鎖步執(zhí)行模型( Optimize Lock Step Execution Model, OLSM) , 其硬件( 緩

22、沖區(qū)、記分牌及其它硬件) 代價(jià)很少, 控制非常簡(jiǎn)單. 在OLSM模型中, 存儲(chǔ)層次及各流水線結(jié)構(gòu)如圖4所示. 如果L1D命中, L1D可以直接提供數(shù)據(jù),如果L1D不命中, L1D并不直接訪問L2Cache, 而是在指令提交后, 由控制流水線控制是否訪問L2Cache, 此時(shí)L2Cache作為數(shù)據(jù)的提供者, 直接寫回?cái)?shù)據(jù)(寄存器), 同時(shí)填充L1D. 基本的NUAL鎖步執(zhí)行模型與延遲緩沖區(qū)模型相比, 前者邏輯更簡(jiǎn)單, 但后者性能占優(yōu), 因?yàn)楹笳呖砷_發(fā)的MLP更高. NUAL OLSM模型既保持了基本的NUAL鎖步執(zhí)行模型硬件的簡(jiǎn)單性, 同時(shí)克服了基本EPIC模型中不能充分開發(fā)MLP的問題, 其思想基礎(chǔ)是: 存儲(chǔ)操作的某些異?？梢援惒教幚? COMMIT異常處理與數(shù)據(jù)寫回在時(shí)間點(diǎn)上是可以分切的, 指令提交不應(yīng)該賦予其它更多含義, 如數(shù)據(jù)返回. OLSM模型的基本特點(diǎn)是: (1)順序發(fā)射, 順序執(zhí)行, 順序提交, 亂序?qū)懟?寄存器). (2)各主流