計算機系統(tǒng)結構系統(tǒng)結構課程總復習-1229new

1、計算機體系結構計算機體系結構要點復習要點復習Computer Architecture u1960s, (大型機大型機)u1970s, (小型機小型機)u1980s, (桌面計算機桌面計算機)u1990s, Internet and the World Wide Web PDA（個人數(shù)字助理）（個人數(shù)字助理）(機頂盒機頂盒)u2000s, embedded computers(嵌入式計算機嵌入式計算機)Computer Architecture Desktop Computing(桌面計算機桌面計算機) 最早最大的市場最早最大的市場 性價比突出性價比突出Servers(服務器服務器) 提供更大

2、規(guī)模更可靠的文件與計算服務提供更大規(guī)模更可靠的文件與計算服務 availability(可用性）可用性） scalability(可擴充性可擴充性) throughput(吞吐量吞吐量)Embedded Computers(嵌入式計算機嵌入式計算機) 在市場中增長最快在市場中增長最快 設計原則：以最低價格滿足實際的性能需求設計原則：以最低價格滿足實際的性能需求 Real time(soft & hard)(實時性實時性) 最大化存儲需求和最小化功耗需求最大化存儲需求和最小化功耗需求 處理器核心與處理器核心與ASIC的異構的異構 DSP定量分析 可改進比例：該部件的原執(zhí)行時間在原系統(tǒng)總執(zhí)

3、行時間中所占的比例，它總是小于等于.部件加速比：部件改進前后執(zhí)行時間之比，一般情況下它大于。系統(tǒng)加速比 = =改進前改進后系統(tǒng)性能系統(tǒng)性能改進后改進前總執(zhí)行時間總執(zhí)行時間CPU的性能1. 將程序執(zhí)行的時間進行分解 程序執(zhí)行的 CPU時間 = 總時鐘周期數(shù) / 時鐘頻率 CPI = 總時鐘周期數(shù) / IC CPU時間 = CPI IC / 時鐘頻率 IC：程序執(zhí)行過程中所處理的指令數(shù)。2. 將總時鐘周期數(shù)進一步分解 總時鐘周期數(shù)= CPI IC 對許多CPU來說，不同的指令運行時所用的周期數(shù)是不同的，如果計算機系統(tǒng)有 n 種指令，其中 CPIi ： 第 i 種指令所用的時鐘周期數(shù)； ICi ：在

4、程序運行過程中第 i 種指令被運行的次數(shù)；CPU時間 = (CPIi ICi) / 時鐘頻率CPI = (CPIi ICi) / IC = (CPIi ICi / IC)其中：(ICi / IC) 反映了第 i 種指令在程序中所占的比例。 i=1i=1nnni=1CPU時間時間(CPU執(zhí)行周期數(shù)存儲器停頓周期數(shù)執(zhí)行周期數(shù)存儲器停頓周期數(shù)) 時鐘周期時間時鐘周期時間存儲器停頓周期數(shù)存儲器停頓周期數(shù)訪存次數(shù)訪存次數(shù)失效率失效率失效開銷失效開銷于是于是 CPU時間時間ICCPI流水線流水線訪存次數(shù)訪存次數(shù)/指令數(shù)指令數(shù) 失效率失效率失效開銷失效開銷時鐘周期時間時鐘周期時間 CPI流水線流水線= CP

5、I理想理想+停頓停頓結構相關結構相關+停頓停頓數(shù)據(jù)相關數(shù)據(jù)相關+停頓停頓控制相關控制相關提高指令級并行的最基本方法提高指令級并行的最基本方法: (1) 指令調度指令調度 (2) 循環(huán)展開循環(huán)展開 一般由編譯器來完成一般由編譯器來完成。指令調度：指令調度：通過改變指令在程序中的位置，將相關指令通過改變指令在程序中的位置，將相關指令 之間的距離加大到不小于指令執(zhí)行延遲的時之間的距離加大到不小于指令執(zhí)行延遲的時 鐘數(shù)，使相關指令成為實際上的無關指令。鐘數(shù)，使相關指令成為實際上的無關指令。循環(huán)展開：循環(huán)展開：通過多次復制循環(huán)體通過多次復制循環(huán)體(并改變循環(huán)結束條件并改變循環(huán)結束條件)來減少循環(huán)控制對性

6、能的影響來減少循環(huán)控制對性能的影響(循環(huán)控制指令引起的循環(huán)控制指令引起的停頓停頓)。指令級并行指令級并行例：例： for (i=999; i=0; i=i-1) xi = xi + s;考慮對應的考慮對應的 DLX 匯編語言實現(xiàn)匯編語言實現(xiàn).約定：約定：x0 的內存地址為的內存地址為 8(R2) （為簡單起見）（為簡單起見） R1的初值為的初值為x999的地址的地址 F2中存放的值為常量中存放的值為常量 s 不考慮分支轉移的延遲時間不考慮分支轉移的延遲時間LOOP:LD F0, 0(R1)ADDDF4, F0, F2SD F4, 0(R1)DADDUI R1, R1, #-8BNER1, R2

7、,LOOP 指令級并行指令級并行實際運行：實際運行：(1)LOOP:LD F0, 0(R1)(2)(空轉空轉)(3)ADDDF4, F0, F2(4)(空轉空轉)(5)(空轉空轉)(6)SDF4, 0(R1)(7)DADDUI R1, R1, #-8(8) (空轉空轉) (9)BNER1, R2,LOOP 一共一共 9 個時鐘周期，其中有個時鐘周期，其中有 4 個空轉周期。個空轉周期。 指令級并行指令級并行指令調度：指令調度：(1)LOOP:LDF0, 0(R1)(2)(空轉空轉)(3)ADDDF4, F0, F2(4) (空轉空轉)(5) DADDUI R1, R1, #-8(6) SDF4

8、, 8(R1)(7) BNER1, R2,LOOP 一共一共 7 個時鐘周期，其中有個時鐘周期，其中有 2 個空轉周期。個空轉周期。這種指令調度由編譯器完成的，其基本思想是將指令這種指令調度由編譯器完成的，其基本思想是將指令序列中的序列中的“無關無關”指令調入空轉周期指令調入空轉周期。 指令級并行指令級并行循環(huán)展開循環(huán)展開4次，每次迭代分配不同的寄存器：次，每次迭代分配不同的寄存器：(1)LOOP:LDF0, 0(R1)(2)(空轉空轉)(3)ADDD F4, F0, F2(4)(空轉空轉)(5)(空轉空轉)(6)SDF4, 0(R1)(7)LDF6, -8(R1)(8)(空轉空轉)(9)AD

9、DD F8, F6, F2(10)(空轉空轉)(11)(空轉空轉)(12)SDF8, -8(R1)指令級并行指令級并行(13)LDF10, -16(R1)(14)(空轉空轉)(15)ADDD F12, F10, F2(16)(空轉空轉)(17)(空轉空轉)(18)SDF12, -16(R1)(19)LDF14, -24(R1)(20)(空轉空轉)(21)ADDD F16, F14, F2(22)(空轉空轉)(23)(空轉空轉)(24)SDF16, -24(R1)(25)DADDUI R1, R1, #-32(26)(空轉空轉) (27)BNE R1, R2,LOOP 一共一共 27 個時鐘周期

10、，平均每次循環(huán)使用個時鐘周期，平均每次循環(huán)使用27 / 4 6.7個周期。個周期。 循環(huán)展開循環(huán)展開+指令調度指令調度(循環(huán)展開調度循環(huán)展開調度)：(1)LOOP:LDF0,0(R1)(2)LDF6,-8(R1)(3)LDF10,-16(R1)(4)LDF14,-24(R1)(5)ADDD F4,F0,F2(6)ADDD F8,F6,F2(7)ADDD F12,F10,F2(8)ADDD F16,F14,F2 指令級并行指令級并行(9)SDF4, 0(R1)(10)SDF8, -8(R1)(11)SDF12, -16(R1)(12)DADDUI R1, R1, #-32(13)SDF16, 8

11、(R1)(14)BNER1, R2,LOOP 一共一共 14 個時鐘周期，平均每次循環(huán)使用個時鐘周期，平均每次循環(huán)使用14 / 4 3.5個周期。所有個周期。所有“空轉空轉”消失，即數(shù)據(jù)相關被消除，消失，即數(shù)據(jù)相關被消除，達到完全指令級并行。達到完全指令級并行。 結論：結論：由編譯器所完成的循環(huán)展開和指令調度由編譯器所完成的循環(huán)展開和指令調度(靜態(tài)靜態(tài)調度調度)，能有效提高指令級并行。，能有效提高指令級并行。指令級并行指令級并行InstructionInstructionLatency producing result using result in cyclesFP ALU opAnothe

12、r FP ALU op 3FP ALU opStore double2Load double FP ALU op1Load double Store double0指令級并行指令級并行指令運行過程指令運行過程 (1)指令流出指令流出(發(fā)射發(fā)射)(IS)：如果指令如果指令所需的功能部件所需的功能部件空閑空閑，并且其他正在運行的指令與它，并且其他正在運行的指令與它不發(fā)生目的不發(fā)生目的寄存器沖突寄存器沖突，則記分牌將向該功能部件流出指令，則記分牌將向該功能部件流出指令，功能部件被置成準備運行該指令狀態(tài)功能部件被置成準備運行該指令狀態(tài)(記錄于記分記錄于記分牌牌)解決了解決了結構相關結構相關和和寫后寫相

13、關寫后寫相關。動態(tài)算法之一：記分牌動態(tài)算法之一：記分牌 (2)讀操作數(shù)讀操作數(shù)(RO)：如果前面已流出的正在運行的如果前面已流出的正在運行的指令指令不對本指令的源操作數(shù)寄存器進行寫操作不對本指令的源操作數(shù)寄存器進行寫操作，或者一個正在工作的功能部件或者一個正在工作的功能部件已完成對該寄存器已完成對該寄存器的寫操作的寫操作，則進行讀操作數(shù)，并完成該步驟，則進行讀操作數(shù)，并完成該步驟(離開離開掛起狀態(tài)掛起狀態(tài))。 有可能有多個功能部件掛起在這一步。有可能有多個功能部件掛起在這一步。 解決解決寫后讀相關寫后讀相關。動態(tài)算法之一：記分牌動態(tài)算法之一：記分牌 (3)執(zhí)行執(zhí)行(EX)：對浮點運算來講，這一

14、步可能要花多對浮點運算來講，這一步可能要花多個時鐘周期，由于功能部件獨立，不會發(fā)生沖突。個時鐘周期，由于功能部件獨立，不會發(fā)生沖突。 (4)寫結果寫結果(WR)：記分牌知道功能部件執(zhí)行完成后，記分牌知道功能部件執(zhí)行完成后，檢查目標寄存器，如果前面檢查目標寄存器，如果前面沒有指令讀該寄存器沒有指令讀該寄存器或或已完成對該寄存器的讀操作已完成對該寄存器的讀操作，則完成這一步驟，則完成這一步驟，否則將該功能部件掛起在這一步。否則將該功能部件掛起在這一步。 有可能有多個功能部件掛起在這一步。有可能有多個功能部件掛起在這一步。 解決解決讀后寫相關讀后寫相關。動態(tài)算法之一：記分牌動態(tài)算法之一：記分牌MIP

15、S計分板的數(shù)據(jù)結構計分板的數(shù)據(jù)結構(1) 指令狀態(tài)表：指令狀態(tài)表：表示正在執(zhí)行的各指令處于四步中的表示正在執(zhí)行的各指令處于四步中的 哪一步。哪一步。動態(tài)算法之一：記分牌動態(tài)算法之一：記分牌(2)功能狀態(tài)表：功能狀態(tài)表：表示各功能部件的狀態(tài)，每個功能部表示各功能部件的狀態(tài)，每個功能部 件一共有九個域：件一共有九個域：Busy: 該功能部件是否在工作該功能部件是否在工作(被分配被分配)Op: 該功能部件當前操作該功能部件當前操作Fi: 目的寄存器編號目的寄存器編號Fj, Fk: 源寄存器編號源寄存器編號Qj, Qk: 向源寄存器寫結果的功能部件向源寄存器寫結果的功能部件 Rj, Rk:源寄存器是否

16、源寄存器是否就緒并且還未被使用就緒并且還未被使用 Yes: 就緒并且還沒有被使用過就緒并且還沒有被使用過 (后面指令不可改寫它后面指令不可改寫它) No: (1) 未就緒未就緒 (前面指令可改寫它前面指令可改寫它) (2)已被使用過已被使用過 (后面指令可改寫它后面指令可改寫它) (3)結果寄存器狀態(tài)表：結果寄存器狀態(tài)表：表示每個寄存器是當前哪一表示每個寄存器是當前哪一 個功能部件的目的寄存器個功能部件的目的寄存器 (不是則為空不是則為空)。動態(tài)算法之一：記分牌動態(tài)算法之一：記分牌指令運行過程指令運行過程 (1)指令流出（發(fā)射指令流出（發(fā)射/指派）指派）(IS)： 取一條浮點指令，如果有相應的

17、空閑保留站，并取一條浮點指令，如果有相應的空閑保留站，并且操作數(shù)就緒且操作數(shù)就緒(在寄存器中在寄存器中)，就將指令和操作數(shù)一，就將指令和操作數(shù)一起發(fā)射到保留站；如果沒有空閑的保留站，則發(fā)生起發(fā)射到保留站；如果沒有空閑的保留站，則發(fā)生結構相關，停頓指令；如果操作數(shù)不在寄存器中，結構相關，停頓指令；如果操作數(shù)不在寄存器中，則需要跟蹤將要產生該操作數(shù)的功能單元，寄存器則需要跟蹤將要產生該操作數(shù)的功能單元，寄存器重命名在此步進行，以消除讀后寫和寫后寫相關。重命名在此步進行，以消除讀后寫和寫后寫相關。 如果是訪存指令，有空的緩沖則流出。否則等待。如果是訪存指令，有空的緩沖則流出。否則等待。解決了結構相關

18、、讀后寫、寫后寫。解決了結構相關、讀后寫、寫后寫。 動態(tài)算法之二：動態(tài)算法之二：Tomasulo算法算法(2)執(zhí)行執(zhí)行(EX)： 如果操作數(shù)未就緒，監(jiān)視公共數(shù)據(jù)總線等待如果操作數(shù)未就緒，監(jiān)視公共數(shù)據(jù)總線等待結果結果(某個操作完成后會以廣播方式通知所某個操作完成后會以廣播方式通知所有等待該結果的保留站有等待該結果的保留站)，當兩個操作數(shù)都，當兩個操作數(shù)都就緒則開始運行。如果對某個功能單元而言，就緒則開始運行。如果對某個功能單元而言，有多條指令在同一個時鐘周期內就緒，保留有多條指令在同一個時鐘周期內就緒，保留站可以任意選擇。站可以任意選擇。 如果是訪存指令，首先當基址寄存器可用時如果是訪存指令，首

19、先當基址寄存器可用時計算有效地址，之后地址被置于訪存緩存中；計算有效地址，之后地址被置于訪存緩存中；其次當存儲單元可用時，其次當存儲單元可用時，load立即執(zhí)行，而立即執(zhí)行，而store則要等待被保存的值。則要等待被保存的值。解決了寫后讀相關。解決了寫后讀相關。動態(tài)算法之二：動態(tài)算法之二：Tomasulo算法算法(3)寫結果寫結果(WB)：結果計算完，寫入公共數(shù)據(jù)總線，廣播至所有等結果計算完，寫入公共數(shù)據(jù)總線，廣播至所有等待該結果的保留站和目的寄存器待該結果的保留站和目的寄存器(如果存在如果存在)。Store指令被緩存在指令被緩存在store緩存中，直到將要保存的緩存中，直到將要保存的值和保存

20、地址都可用時為止，當存儲單元可用時，值和保存地址都可用時為止，當存儲單元可用時， store立即執(zhí)行。立即執(zhí)行。動態(tài)算法之二：動態(tài)算法之二：Tomasulo算法算法數(shù)據(jù)結構數(shù)據(jù)結構(1)指令狀態(tài)表：指令狀態(tài)表： 表示正在執(zhí)行的各指令處于三步表示正在執(zhí)行的各指令處于三步 中的哪一步。中的哪一步。(2)寄存器狀態(tài)表：寄存器狀態(tài)表：表示各寄存器分別是哪一個保表示各寄存器分別是哪一個保 留站的目的寄存器。留站的目的寄存器。(3)保留站：保留站：一共有六個域一共有六個域Busy: 該保留站是否空閑該保留站是否空閑Op: 對操作數(shù)對操作數(shù)S1、S2的操作的操作Vj,Vk: 操作數(shù)值操作數(shù)值Qj,Qk: 將

21、產生操作數(shù)值的保留站號，為空表將產生操作數(shù)值的保留站號，為空表 示操作數(shù)值已在示操作數(shù)值已在Vj、Vk中或不需要。中或不需要。注：對每個操作數(shù)而言，注：對每個操作數(shù)而言，V或或Q字段只有一個有效字段只有一個有效動態(tài)算法之二：動態(tài)算法之二：Tomasulo算法算法(4)取緩沖：取緩沖：一共有兩個域一共有兩個域Busy: 該保留站是否空閑該保留站是否空閑Address: 存儲器地址值存儲器地址值(5)存緩沖：存緩沖：一共有四個域一共有四個域Busy: 該保留站是否空閑該保留站是否空閑Address: 存儲器地址值存儲器地址值Vj: 操作數(shù)值操作數(shù)值Qj: 將產生操作數(shù)值的保留站號，將產生操作數(shù)值的

22、保留站號，為空表示操作數(shù)值已在為空表示操作數(shù)值已在Vj中中。動態(tài)算法之二：動態(tài)算法之二：Tomasulo算法算法基本思想：基本思想：基于該分支指令的歷史記錄基于該分支指令的歷史記錄-根據(jù)該分支根據(jù)該分支指令在最近一次或幾次的運行情況指令在最近一次或幾次的運行情況(分支成功或失敗分支成功或失敗)，來預測該分支指令的本次運行情況來預測該分支指令的本次運行情況(分支成功或失敗分支成功或失敗)。實現(xiàn)方法：實現(xiàn)方法：建立一片緩沖區(qū)，記錄各運行過的分支指建立一片緩沖區(qū)，記錄各運行過的分支指令的運行情況令的運行情況(分支成功或失敗分支成功或失敗)。緩沖區(qū)如何尋址緩沖區(qū)如何尋址-根據(jù)分支指令根據(jù)分支指令地址的

23、低位地址的低位，究竟，究竟 多少位取決于緩沖區(qū)大小。多少位取決于緩沖區(qū)大小。緩沖區(qū)的內容緩沖區(qū)的內容 -預測位，其長度預測位，其長度(多少位多少位)決定能決定能 記錄該指令前多少次運行情況。記錄該指令前多少次運行情況。進一步減少分支延遲：分支預測緩沖進一步減少分支延遲：分支預測緩沖分支指令的執(zhí)行過程：分支指令的執(zhí)行過程：(1) 現(xiàn)場保留?，F(xiàn)場保留。(2) 按預測方向取后繼指令。按預測方向取后繼指令。(3) 得到分支結果后得到分支結果后如果預測成功，繼續(xù)運行；如果預測成功，繼續(xù)運行；如果預測失敗，恢復保留的現(xiàn)場，從分支處重新如果預測失敗，恢復保留的現(xiàn)場，從分支處重新執(zhí)行；執(zhí)行；(4) 修改預測位。修改預測位。進一步減少分支延遲：分支預測緩沖進一步減少分支延遲：分支預測緩沖分支指令無延遲的前提：分支指令無延遲的前提：(1) 分支預測成功分支預測成功(2) 分支預測和目標地址計算都在分支預測和目標地址計算都在 IF 階段就能完成。階段就能完成?；舅枷耄夯舅枷耄涸O立一個緩沖區(qū)設立一個緩沖區(qū)(稱為分支目標緩沖區(qū)，稱為分支目標緩沖區(qū)，或或BTB )，其中存放最近一次運行時分支成功的分支，其中存放最近一次運