高體復習筆記

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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