高體復(fù)習(xí)筆記

1、高體復(fù)習(xí)筆記PAGE PAGE Version 0.5 整理人張棟；最后整理日期 2003-6-25高體復(fù)習(xí)筆記10208830張棟說(shuō)明：這份筆記是我復(fù)習(xí)高體期間整理的，目前還很不完善，很多題目沒(méi)有想到，也有很多列在上面的要點(diǎn)沒(méi)有時(shí)間寫上去，因?yàn)槲野ㄕ磉@份筆記在內(nèi)復(fù)習(xí)高體的時(shí)間只有不過(guò)一天。盼望有人能將之補(bǔ)充完整，或者基于此筆記整理一份更詳細(xì)的以餉師弟師妹，甚謝甚謝！（如有人愿補(bǔ)充，請(qǐng)?jiān)陧?yè)腳處注明版本號(hào)、整理人及修改日期以防沖突。）名詞解釋BHTBTAC/BTB要點(diǎn)：用一個(gè)緩沖站來(lái)存儲(chǔ)分支后面的下一條指令地址，這種緩沖站叫做分支目標(biāo)緩沖站（BTB）或分支目標(biāo)高速緩存（BTAC）Reorde

2、r Buffer要點(diǎn)：按FIFO即指令發(fā)射的次序存放指令每個(gè)表項(xiàng)包括：PC，目標(biāo)寄存器，結(jié)果，意外狀態(tài)當(dāng)指令執(zhí)行完成時(shí)，將結(jié)果放在ROB像保留站為其他介于執(zhí)行、完成、提交的指令提供操作數(shù)將結(jié)果用ROB的編號(hào)來(lái)標(biāo)記指令提交-將ROB頂部的數(shù)值放到寄存器中這樣就易于實(shí)現(xiàn)錯(cuò)誤預(yù)測(cè)路徑或一次意外中的推測(cè)指令推測(cè)錯(cuò)誤時(shí)只需從ROB中去掉該指令并從正確的后繼開(kāi)始執(zhí)行。Rename Register/重命名要點(diǎn)：指令中的寄存器被數(shù)值或指向保留站的指針代替，這一過(guò)程稱為寄存器換名；消除了WAR/WAR冒險(xiǎn)，保留站比寄存器多，所以可以完成優(yōu)化編譯器所不能完成的調(diào)度顯式寄存器重命名要點(diǎn)：顯式寄存器重命名使用比IS

3、A所說(shuō)明的寄存器數(shù)量要大的物理寄存器堆使用變換表（translation table）完成ISA reg-物理寄存器的映射，當(dāng)寄存器寫時(shí)為寫的每一條指令從freelist里分配新的物理寄存器，指令不active時(shí)回收。Trace CacheSuperScalar/MultiScalarCMP/SMT/SMP/Cluster/ MPPDSM要點(diǎn)：物理上分開(kāi)的存儲(chǔ)器能夠作為邏輯上共享的地址空間進(jìn)行尋址，任何一個(gè)處理器能夠通過(guò)引用地址的方式，訪問(wèn)任意節(jié)點(diǎn)上的存儲(chǔ)器。SIMD/MIMD要點(diǎn)：同一條指令被多個(gè)使用不同數(shù)據(jù)流的處理器執(zhí)行。MIMD要點(diǎn)：其中每個(gè)處理器取用自己的指令并對(duì)自己的數(shù)據(jù)進(jìn)行操作。U

4、MA/NUMA/NORMA要點(diǎn)：不同處理器訪問(wèn)memory的時(shí)間相同/不同Multicomputer要點(diǎn)：沒(méi)有遠(yuǎn)程內(nèi)存訪問(wèn)，通過(guò)send/recv進(jìn)行網(wǎng)絡(luò)訪問(wèn)精確中斷 （M,N）預(yù)測(cè)器要點(diǎn)：使用前m個(gè)分支行為去從2m個(gè)分支預(yù)測(cè)中進(jìn)行選擇，每一個(gè)預(yù)測(cè)分支對(duì)應(yīng)于單個(gè)分支的n位預(yù)測(cè)器。trace scheduling 要點(diǎn)：trace scheduling分作兩步：蹤跡選擇。從一個(gè)基本塊中發(fā)現(xiàn)（靜態(tài)分析預(yù)測(cè)）執(zhí)行代碼序列中最可能執(zhí)行的代碼序列；蹤跡壓縮。將蹤跡擠壓成一些VLIW指令，蹤跡調(diào)度把操作盡可能早地提前執(zhí)行。結(jié)構(gòu)冒險(xiǎn)/數(shù)據(jù)冒險(xiǎn)/資源冒險(xiǎn)三種數(shù)據(jù)相關(guān)：RAW/WAR/WAWDelay Slot

5、的三種調(diào)度：從前，從目標(biāo)（只是taken時(shí)有效），跳下（not taken時(shí)有效）Cancelling Branch要點(diǎn)：錯(cuò)誤預(yù)測(cè)時(shí)延遲槽指令squash訪問(wèn)的局部性時(shí)間/空間局部性TLB循環(huán)展開(kāi) vs 軟件流水循環(huán)展開(kāi)：從減少循環(huán)開(kāi)銷方面軟件流水：減少循環(huán)執(zhí)行時(shí)間軟件流水要點(diǎn)：使用軟件調(diào)度的方法對(duì)循環(huán)進(jìn)行重構(gòu)，消除/降低每個(gè)loop內(nèi)的相關(guān)。最大化結(jié)果，比展開(kāi)代碼空間小，每個(gè)循環(huán)填充和排出流水線一次記住Loop Unrooling和Software Pipelining的對(duì)比圖保留站CDBSpeculation要點(diǎn)：動(dòng)態(tài)branch預(yù)測(cè)來(lái)選擇要執(zhí)行的指令或?qū)?shù)據(jù)值進(jìn)行預(yù)測(cè)；允許控制相關(guān)解決前

6、指令的執(zhí)行；（要求能夠消除錯(cuò)誤speculative序列時(shí)所產(chǎn)生的效果）動(dòng)態(tài)調(diào)度能夠處理不同的基本塊的組合其執(zhí)行的本質(zhì)是數(shù)據(jù)流執(zhí)行：當(dāng)操作數(shù)可用時(shí)開(kāi)始操作。VLIW要點(diǎn)：VLIW使用多個(gè)互相不相關(guān)的功能部件，不是努力去發(fā)射多個(gè)互不相關(guān)的指令到功能部件中，而是把多個(gè)操作封裝到一條非常長(zhǎng)的指令中。決定哪幾條指令可以同時(shí)發(fā)射的任務(wù)交由編譯器完成。相關(guān)技術(shù)：全局調(diào)度去發(fā)現(xiàn)可以并行發(fā)射的指令，例如循環(huán)展開(kāi)并對(duì)代碼調(diào)度進(jìn)行優(yōu)化。指令窗口要點(diǎn)：為了同時(shí)執(zhí)行而被檢測(cè)的指令集合，限制了可以檢測(cè)的指令數(shù)目，也限制了可發(fā)射指令的最大指令條數(shù)。義務(wù)失效/沖突失效/容量失效Victim Cache偽相聯(lián)/偽命中Non-

7、blocking Cache/Lockup-free Cache要點(diǎn)：CPU在等待cache返回缺失數(shù)據(jù)的同時(shí)可以繼續(xù)cache訪問(wèn)。需要多端口，嚴(yán)重增加了cache控制的復(fù)雜性。提前重啟要點(diǎn)：一旦塊中所需字到達(dá)，就立即把它送到CPU，使CPU繼續(xù)執(zhí)行。關(guān)鍵字先送要點(diǎn)：首先向存儲(chǔ)器請(qǐng)求缺失的字，然后一旦它到了就把它發(fā)送到CPU中，讓CPU繼續(xù)執(zhí)行，同時(shí)裝入塊中其他字。局部失效率/總失效率要點(diǎn)：這一級(jí)cache的miss數(shù)除以對(duì)這一級(jí)cache的訪問(wèn)總數(shù) vs CPU產(chǎn)生的訪問(wèn)總數(shù)。hit under miss/hit under multiple miss/miss under miss流緩沖

8、器（stream buffer）cache技術(shù)中的讀比寫優(yōu)先要點(diǎn)：帶write buffer的write through：讀失效時(shí)查看write buffer，如果沒(méi)有沖突而且存儲(chǔ)器系統(tǒng)可以訪問(wèn)，就然讀失效繼續(xù)。Write back：把臟塊拷貝到一個(gè)緩沖區(qū)后就去讀下層存儲(chǔ)器，然后在將該臟塊寫入下層存儲(chǔ)器，而不是相反。比較共享存儲(chǔ)和消息傳遞模型要點(diǎn)：共享存儲(chǔ)易于在小規(guī)模機(jī)器上實(shí)現(xiàn)，易于編程，低時(shí)延，易于使用硬件控制的cache技術(shù)。消息傳遞使用硬件少，易于設(shè)計(jì)?？坍嫴⑿袡C(jī)器的三個(gè)要點(diǎn)要點(diǎn)：命名、同步、時(shí)延和帶寬SCSI要點(diǎn)：即小型計(jì)算機(jī)系統(tǒng)接口。SCSI協(xié)議包括控制器和SCSI設(shè)備之間進(jìn)行特定動(dòng)

9、作的一系列狀態(tài)。包括：n位計(jì)數(shù)器辨析/Pitfalls/Fallcies使用相同指令體系結(jié)構(gòu)的的處理器的相對(duì)性能可以用時(shí)鐘頻率或者一套benchmark suite的性能來(lái)來(lái)比較。MIPS/MFLOPS是比較機(jī)器間性能的準(zhǔn)確指標(biāo)要點(diǎn)：MIPS=Extime=為何要用幾何平均值來(lái)測(cè)定性能合成的基準(zhǔn)測(cè)試程序能夠預(yù)測(cè)真實(shí)程序的性能要點(diǎn)：易被優(yōu)化與真實(shí)程序可被優(yōu)化方式不同好的benchmark永遠(yuǎn)有效易被編譯選項(xiàng)和預(yù)處理器優(yōu)化易被體系結(jié)構(gòu)開(kāi)發(fā)人員特定優(yōu)化實(shí)際需求隨時(shí)變化設(shè)計(jì)一種“高級(jí)”指令集特性來(lái)支持一種高級(jí)語(yǔ)言體系結(jié)構(gòu)要點(diǎn)：復(fù)雜、得不償失，只能在有限環(huán)境中應(yīng)用?？梢栽O(shè)計(jì)一個(gè)沒(méi)有缺陷的系統(tǒng)結(jié)構(gòu)要點(diǎn)：體

10、系結(jié)構(gòu)是軟/硬件權(quán)衡，技術(shù)隨著時(shí)間變化而變換。當(dāng)初正確的可能到后來(lái)看起來(lái)是錯(cuò)誤的。高的流水級(jí)數(shù)提高性能要點(diǎn)：load delay更長(zhǎng)轉(zhuǎn)移延遲更長(zhǎng)轉(zhuǎn)移預(yù)測(cè)失敗的損失latch和時(shí)鐘扭斜的影響superscalar和vliw的主要區(qū)別在于后者能夠并行發(fā)射更多的指令 預(yù)測(cè)錯(cuò)誤之間的指令數(shù)目比預(yù)測(cè)錯(cuò)誤率更能體現(xiàn)預(yù)測(cè)性能要點(diǎn)：basic block大小是我們所關(guān)心的前者蘊(yùn)涵了后者mips r4000的8級(jí)流水線是由mips r3000的4級(jí)流水線逐級(jí)細(xì)分而來(lái)不惜成本可以完全解決資源沖突完美無(wú)缺的體系結(jié)構(gòu)是計(jì)算機(jī)系統(tǒng)成功的保證計(jì)算機(jī)的最好設(shè)計(jì)式不考慮實(shí)現(xiàn)優(yōu)化最初目標(biāo)n路組相聯(lián)一定優(yōu)于直接映射cache要點(diǎn)

11、：N個(gè)比較器與一個(gè)增加了額外的多路選擇延遲判斷命中/失效時(shí)才能得到數(shù)據(jù)虛擬cache總是比物理cache要好要點(diǎn)：同義問(wèn)題，兩個(gè)不同的虛擬地址可以映射到同一物理地址對(duì)于更新，必須更新具有同一物理地址的cache表項(xiàng)或允許存儲(chǔ)不一致需要大量硬件，特別是需要對(duì)物理標(biāo)簽進(jìn)行相聯(lián)查找已確定是否出現(xiàn)多次命中；或者通過(guò)軟件強(qiáng)制實(shí)現(xiàn)：alias boundary，即VA和PA相同的低位空間 cache大小兩條指令之間有dependence一定會(huì)發(fā)生hazardcache在任何情況下都可以加速應(yīng)用要點(diǎn)：cache是利用了時(shí)間/空間局部性降低了局部性的程序很難利用cache，例如流媒體，實(shí)時(shí)應(yīng)用Global O

12、ptimization的代碼調(diào)度范圍通常比Inter Procedure Optimization要大要點(diǎn)：Global是指跨越基本塊的代碼調(diào)度，Inter Procedure是指跨越過(guò)程的代碼調(diào)度多發(fā)射處理機(jī)的發(fā)射速率可以任意擴(kuò)大要點(diǎn)：程序代碼中固有的對(duì)指令級(jí)并行的限制；（相關(guān)；可開(kāi)發(fā)并行性限制）在已有的硬件架構(gòu)中使用多發(fā)機(jī)制的困難性；（硬件資源需求；應(yīng)該評(píng)估硬件機(jī)制和編譯器方法兩者性能及成本上的優(yōu)劣，并做更好的結(jié)合。）每一個(gè)超標(biāo)量或VLIW機(jī)器具體實(shí)現(xiàn)時(shí)所面對(duì)的限制性因素。對(duì)于supersaclar的主要問(wèn)題是指令發(fā)射邏輯部件的設(shè)計(jì)；對(duì)VLIW則存在技術(shù)上和邏輯設(shè)計(jì)上的問(wèn)題。技術(shù)上代碼膨脹

13、需要展開(kāi)循環(huán)來(lái)填充長(zhǎng)指令字，未被填滿的指令，功能部件在譯碼時(shí)仍然會(huì)被翻譯由于要把指令壓縮到主存中并在指令讀出到cache或進(jìn)行譯碼時(shí)才擴(kuò)展它們，而VLIW時(shí)靜態(tài)調(diào)度的系統(tǒng)結(jié)構(gòu)，在操作上鎖定，任何一個(gè)功能部件的暫停均會(huì)導(dǎo)致處理器的暫停。增加了內(nèi)存結(jié)構(gòu)復(fù)雜性和存儲(chǔ)訪問(wèn)延遲。VLIW的主要邏輯問(wèn)題時(shí)二進(jìn)制代碼兼容問(wèn)題。需要代碼重新編譯。SuperScalar vs VLIW的優(yōu)勢(shì)：可以更容易的開(kāi)發(fā)不規(guī)則結(jié)構(gòu)代碼中的并行性對(duì)內(nèi)存結(jié)構(gòu)要求更少在評(píng)估系統(tǒng)或檢查性-價(jià)時(shí)忽略軟件要點(diǎn)：目前軟件代價(jià)已經(jīng)成為計(jì)算機(jī)系統(tǒng)成本中很重要的一部分cache的設(shè)計(jì)空間正交性認(rèn)為增加指令發(fā)射速率并犧牲時(shí)鐘頻率來(lái)減少CPI會(huì)導(dǎo)

14、致系統(tǒng)性能降低僅提高影響多發(fā)射機(jī)制處理器的某一方面因素就可以提高整體性能要點(diǎn)：許多因素限制這多發(fā)射機(jī)器的性能，提高某一方面因素后，常常會(huì)發(fā)現(xiàn)其他方面限制系統(tǒng)性能的因素嚴(yán)重起來(lái)使用硬件預(yù)取總能提高性能簡(jiǎn)答raid05要點(diǎn)：RAID 0：無(wú)冗余RAID 1：磁盤映像，完全復(fù)制，一次邏輯寫需要兩次物理寫，容量開(kāi)銷100RAID 3：加位交叉奇偶校驗(yàn)磁盤。RAID 5：將奇偶校驗(yàn)信息均勻的分布到各個(gè)磁盤中。一次邏輯寫對(duì)應(yīng)2次物理讀+2次物理寫。使得cpu從i/o事務(wù)中解脫出來(lái)的方法減少轉(zhuǎn)移延遲的基本方法，包括使用條件和效果bank interleaved原理試述解決結(jié)構(gòu)、數(shù)據(jù)、控制相關(guān)的方法要點(diǎn)：結(jié)構(gòu)

15、增加關(guān)鍵路徑上的硬件資源數(shù)據(jù)前遞，編譯器調(diào)度控制跳轉(zhuǎn)預(yù)測(cè)，delayed slot試述cache和tlb重疊訪問(wèn)方式及其適用情況跳轉(zhuǎn)預(yù)測(cè)的advantage要點(diǎn)：降低stall，更大的basic block-調(diào)度優(yōu)化Loop Unrolling技術(shù)及其優(yōu)缺點(diǎn)優(yōu)點(diǎn)：增大基本塊有利于代碼調(diào)度減少了branch指令缺點(diǎn)：code density降低代碼體增大register占用多硬件提高ilp的核心思想要點(diǎn)：亂序執(zhí)行寄存器換名記分板的核心思想、局限性，在控制上和Tomasulo的不同核心思想：允許暫停后的指令提前處理（允許亂序執(zhí)行-亂序完成，ID階段檢測(cè)所有結(jié)構(gòu)冒險(xiǎn)）局限：沒(méi)有前遞硬件，只有寫回re

16、g file以后才能從reg中讀，不能讀流水線中間結(jié)果指令調(diào)度局限在基本塊內(nèi)（沒(méi)有指令窗口），對(duì)于branch只能stall，不能跨越basic block功能部件少（結(jié)構(gòu)冒險(xiǎn)）存在結(jié)構(gòu)冒險(xiǎn)就暫停發(fā)射stall至WAR冒險(xiǎn)解決-為什么不讀后續(xù)指令？防止WAW冒險(xiǎn)不同：控制&緩沖器分布于功能部件（Tomasulo）與集中于記分板使用編譯優(yōu)化減少cache失效的方法要點(diǎn)：合并數(shù)組、循環(huán)交換、循環(huán)合并、塊化交互或事務(wù)處理的三部分要點(diǎn)：報(bào)交時(shí)間：用戶輸入命令的時(shí)間系統(tǒng)響應(yīng)時(shí)間：用戶報(bào)交和系統(tǒng)應(yīng)答之間的時(shí)間思考時(shí)間：從系統(tǒng)應(yīng)答到用戶輸入下一命令的時(shí)間I/O控制結(jié)構(gòu)方式要點(diǎn)：輪詢中斷DMAI/O控制器I/

17、O處理器總線仲裁方式分類要點(diǎn)：菊花鏈、并行仲裁、輪詢總線主設(shè)備/從設(shè)備/協(xié)議要點(diǎn)：主設(shè)備具有控制總線能力，發(fā)起總線事務(wù)。從設(shè)備是被總線事務(wù)激活的模塊?？偩€協(xié)議是在總線事務(wù)中事件序列的規(guī)范和定時(shí)需求規(guī)范。動(dòng)態(tài)調(diào)度的優(yōu)點(diǎn)和核心思想優(yōu)點(diǎn)：處理某些在編譯階段無(wú)法知道的相關(guān)，并簡(jiǎn)化編譯器設(shè)計(jì)允許在別的流水線機(jī)器上編譯的指令不經(jīng)重編也能有效運(yùn)行。思想：允許暫停之后的指令被執(zhí)行，允許亂序執(zhí)行，使用寄存器換名消除WAW和WAR冒險(xiǎn)。記分板的核心思想：允許暫停之后的指令提前處理（允許亂序執(zhí)行，ID階段檢測(cè)所有結(jié)構(gòu)冒險(xiǎn)）記分板的對(duì)WAR冒險(xiǎn)的解決：排隊(duì)等待操作以及它們操作數(shù)的拷貝只在讀操作數(shù)階段才讀取寄存器記分板

18、的對(duì)WAW冒險(xiǎn)的解決：暫停等待到其他指令的完成。記分板的局限性：沒(méi)有前遞硬件，只有寫回reg file以后才能從reg中讀取操作數(shù)，不能讀流水線中間結(jié)果。指令窗口小，調(diào)度局限在基本塊內(nèi)部， 對(duì)于branch只能stall。功能部件少導(dǎo)致結(jié)構(gòu)冒險(xiǎn)存在結(jié)構(gòu)冒險(xiǎn)就暫停發(fā)射指令暫停執(zhí)行到WAR解決設(shè)計(jì)記分板和tomasulo的結(jié)構(gòu)、原理、步驟，以及對(duì)tomasulo推測(cè)式和精確中斷的支持。（推測(cè)式亂序執(zhí)行、按序提交、指令提交前保證不會(huì)出現(xiàn)意外）。比較記分板和Tomasulo算法結(jié)構(gòu)：原理：步驟：區(qū)別：Tomasulo算法寄存器換名機(jī)制消除WAW和WAR冒險(xiǎn) vs 記分板使用編譯器來(lái)做寄存器換名。Tom

19、asulo算法冒險(xiǎn)檢測(cè)和執(zhí)行控制分散于功能部件的保留站 vs記分板集中于記分板Tomasulo算法使用CDB將結(jié)果從保留站緩存的地方直接送到功能部件（廉價(jià)的前遞方法）vs 記分板從寄存器傳送（無(wú)前遞）。Tomasulo算法中L/S也像其他部件一樣使用保留站。對(duì)specalation和precise interrupt的支持：需要從指令的實(shí)際完成中將提高cache性能的途徑要點(diǎn)：降低失效率通過(guò)增大塊大小來(lái)降低失效通過(guò)增加相聯(lián)度來(lái)降低失效使用Victim Cache通過(guò)偽相聯(lián)通過(guò)硬件預(yù)取指令和數(shù)據(jù)通過(guò)軟件預(yù)取數(shù)據(jù)減少失效通過(guò)編譯優(yōu)化降低失效損失在失效時(shí)讀比寫優(yōu)先子塊放置提前重啟和關(guān)鍵字先送用Non-blocking