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

1、高體復(fù)習(xí)筆記PAGE PAGE Version 0.5 整理人張棟；最后整理日期 2003-6-25高體復(fù)習(xí)筆記10208830張棟說明：這份筆記是我復(fù)習(xí)高體期間整理的，目前還很不完善，很多題目沒有想到，也有很多列在上面的要點(diǎn)沒有時間寫上去，因為我包括整理這份筆記在內(nèi)復(fù)習(xí)高體的時間只有不過一天。盼望有人能將之補(bǔ)充完整，或者基于此筆記整理一份更詳細(xì)的以餉師弟師妹，甚謝甚謝?。ㄈ缬腥嗽秆a(bǔ)充，請在頁腳處注明版本號、整理人及修改日期以防沖突。）名詞解釋BHTBTAC/BTB要點(diǎn)：用一個緩沖站來存儲分支后面的下一條指令地址，這種緩沖站叫做分支目標(biāo)緩沖站（BTB）或分支目標(biāo)高速緩存（BTAC）Reorde

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

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

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

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

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

7、blocking Cache/Lockup-free Cache要點(diǎn)：CPU在等待cache返回缺失數(shù)據(jù)的同時可以繼續(xù)cache訪問。需要多端口，嚴(yán)重增加了cache控制的復(fù)雜性。提前重啟要點(diǎn)：一旦塊中所需字到達(dá)，就立即把它送到CPU，使CPU繼續(xù)執(zhí)行。關(guān)鍵字先送要點(diǎn)：首先向存儲器請求缺失的字，然后一旦它到了就把它發(fā)送到CPU中，讓CPU繼續(xù)執(zhí)行，同時裝入塊中其他字。局部失效率/總失效率要點(diǎn)：這一級cache的miss數(shù)除以對這一級cache的訪問總數(shù) vs CPU產(chǎ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：讀失效時查看write buffer，如果沒有沖突而且存儲器系統(tǒng)可以訪問，就然讀失效繼續(xù)。Write back：把臟塊拷貝到一個緩沖區(qū)后就去讀下層存儲器，然后在將該臟塊寫入下層存儲器，而不是相反。比較共享存儲和消息傳遞模型要點(diǎn)：共享存儲易于在小規(guī)模機(jī)器上實現(xiàn)，易于編程，低時延，易于使用硬件控制的cache技術(shù)。消息傳遞使用硬件少，易于設(shè)計?？坍嫴⑿袡C(jī)器的三個要點(diǎn)要點(diǎn)：命名、同步、時延和帶寬SCSI要點(diǎn)：即小型計算機(jī)系統(tǒng)接口。SCSI協(xié)議包括控制器和SCSI設(shè)備之間進(jìn)行特定動

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

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

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

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

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

14、致系統(tǒng)性能降低僅提高影響多發(fā)射機(jī)制處理器的某一方面因素就可以提高整體性能要點(diǎn)：許多因素限制這多發(fā)射機(jī)器的性能，提高某一方面因素后，常常會發(fā)現(xiàn)其他方面限制系統(tǒng)性能的因素嚴(yán)重起來使用硬件預(yù)取總能提高性能簡答raid05要點(diǎn)：RAID 0：無冗余RAID 1：磁盤映像，完全復(fù)制，一次邏輯寫需要兩次物理寫，容量開銷100RAID 3：加位交叉奇偶校驗磁盤。RAID 5：將奇偶校驗信息均勻的分布到各個磁盤中。一次邏輯寫對應(yīng)2次物理讀+2次物理寫。使得cpu從i/o事務(wù)中解脫出來的方法減少轉(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ù)測，delayed slot試述cache和tlb重疊訪問方式及其適用情況跳轉(zhuǎn)預(yù)測的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階段檢測所有結(jié)構(gòu)冒險）局限：沒有前遞硬件，只有寫回re

16、g file以后才能從reg中讀，不能讀流水線中間結(jié)果指令調(diào)度局限在基本塊內(nèi)（沒有指令窗口），對于branch只能stall，不能跨越basic block功能部件少（結(jié)構(gòu)冒險）存在結(jié)構(gòu)冒險就暫停發(fā)射stall至WAR冒險解決-為什么不讀后續(xù)指令？防止WAW冒險不同：控制&緩沖器分布于功能部件（Tomasulo）與集中于記分板使用編譯優(yōu)化減少cache失效的方法要點(diǎn)：合并數(shù)組、循環(huán)交換、循環(huán)合并、塊化交互或事務(wù)處理的三部分要點(diǎn)：報交時間：用戶輸入命令的時間系統(tǒng)響應(yīng)時間：用戶報交和系統(tǒng)應(yīng)答之間的時間思考時間：從系統(tǒng)應(yīng)答到用戶輸入下一命令的時間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ī)范和定時需求規(guī)范。動態(tài)調(diào)度的優(yōu)點(diǎn)和核心思想優(yōu)點(diǎn)：處理某些在編譯階段無法知道的相關(guān)，并簡化編譯器設(shè)計允許在別的流水線機(jī)器上編譯的指令不經(jīng)重編也能有效運(yùn)行。思想：允許暫停之后的指令被執(zhí)行，允許亂序執(zhí)行，使用寄存器換名消除WAW和WAR冒險。記分板的核心思想：允許暫停之后的指令提前處理（允許亂序執(zhí)行，ID階段檢測所有結(jié)構(gòu)冒險）記分板的對WAR冒險的解決：排隊等待操作以及它們操作數(shù)的拷貝只在讀操作數(shù)階段才讀取寄存器記分板

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

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