第五章程序的執(zhí)行14

1、第五章第五章 程序的執(zhí)行程序的執(zhí)行程序執(zhí)行和指令執(zhí)行概述 數(shù)據(jù)通路基本結(jié)構(gòu)和工作原理流水線方式下指令的執(zhí)行 程序的執(zhí)行機制程序的執(zhí)行機制 分以下三個部分介紹 第一講：程序執(zhí)行概述- 程序及指令的執(zhí)行過程 - CPU的基本功能和基本組成 第二講：數(shù)據(jù)通路基本結(jié)構(gòu)和工作原理- 數(shù)據(jù)通路基本結(jié)構(gòu)- 數(shù)據(jù)通路的時序控制 - 數(shù)據(jù)通路基本工作原理 第三講：流水線方式下指令的執(zhí)行 - 指令流水線的基本原理 - 適合流水線的指令集特征 - CISC和RISC風(fēng)格指令集 - 指令流水線的實現(xiàn) - 高級流水線實現(xiàn)技術(shù) 程序及指令的執(zhí)行過程程序及指令的執(zhí)行過程 程序和指令的關(guān)系 程序由一條一條指令組成，指令按順序

2、存放在內(nèi)存連續(xù)單元 程序的執(zhí)行：周而復(fù)始地執(zhí)行一條一條指令正常情況下，指令按其存放順序執(zhí)行遇到需改變程序執(zhí)行流程時，用相應(yīng)的轉(zhuǎn)移指令（包括無條件轉(zhuǎn)移指令、條件轉(zhuǎn)移指令、調(diào)用指令和返回指令等）來改變程序執(zhí)行流程 程序的執(zhí)行流的控制將要執(zhí)行的指令所在存儲單元的地址由程序計數(shù)器PC給出，通過改變PC的值來控制執(zhí)行順序 指令周期：CPU取出并執(zhí)行一條指令的時間程序及指令的執(zhí)行過程程序及指令的執(zhí)行過程CPU運行程序的過程就是執(zhí)行一條一條指令的過程CPU執(zhí)行指令的過程中，包含CPU操作、訪問內(nèi)存或I/O端口的操作兩類訪存或I/O：涉及存儲系統(tǒng)、總線和I/O接口等內(nèi)容（以后章節(jié)內(nèi)容）CPU內(nèi)部操作：涉及CP

3、U內(nèi)部數(shù)據(jù)通路（本章節(jié)內(nèi)容）機器指令的執(zhí)行過程機器指令的執(zhí)行過程 CPU執(zhí)行指令的過程-取指令-PC+“1”-指令譯碼-進行主存地址運算-取操作數(shù)-進行算術(shù) / 邏輯運算-存結(jié)果-以上每步都需檢測“異?！?若有異常，則自動切換到異常處理程序-檢測是否有“中斷”請求，有則轉(zhuǎn)中斷處理指令執(zhí)行過程問題：“取指令”一定在最開始做嗎？PC+“1”一定在譯碼之前做嗎？“譯碼”須在指令執(zhí)行前做嗎？異常是在CPU內(nèi)部發(fā)生的，中斷是由外部事件引起的取指階段執(zhí)行執(zhí)行階段階段“1”：指一條指令的長度，定長指令字每次都一樣；變長指令字每次可能不同定長指令字通常在譯碼前做，變長指令字在譯碼后做！機器指令的執(zhí)行過程機器指

4、令的執(zhí)行過程 取指令：從PC所指單元取出指令送指令寄存器（IR），并增量PC。 如add函數(shù)，開始PC（IA-32的EIP）中存放的是0 x0848394，CPU根據(jù)PC取指令送IR，每次總是取最長指令字節(jié)數(shù)，假定最長指令是4個字節(jié)，即IR為32位，此時，也即55 89 E5 8BH被取到IR中。 指令譯碼：不同指令其功能不同，因而需要不同的操作控制信號。 CPU根據(jù)不同操作碼譯出不同控制信號。對于上述取到IR中的55 89 E5 8BH譯碼時，可根據(jù)高5位01010譯碼得到push指令的控制信號。 源操作數(shù)地址計算并取操作數(shù)：根據(jù)尋址方式確定源操作數(shù)地址計算方式，若是存儲器數(shù)據(jù)，則需一次或多

5、次訪存；若為間接尋址或兩操作數(shù)都在存儲器的雙目運算，則需多次訪存；若是寄存器數(shù)據(jù)，則直接從寄存器取數(shù)。 執(zhí)行數(shù)據(jù)操作：在ALU或加法器等運算部件中對取出的源操作數(shù)進行運算。 目的操作數(shù)地址計算并存結(jié)果：根據(jù)尋址方式確定目的操作數(shù)地址計算方式，若是存儲器數(shù)據(jù)，則需要一次或多次訪存（間接尋址時）；若是寄存器數(shù)據(jù)，則在進行數(shù)據(jù)操作時直接存結(jié)果到寄存器。 指令地址計算并將其送PC。順序執(zhí)行時，PC加上當(dāng)前指令長度；遇到轉(zhuǎn)移類指令時，則需要根據(jù)條件碼、操作碼和尋址方式等確定下條指令地址。 回顧：馮回顧：馮.諾依曼結(jié)構(gòu)模型機諾依曼結(jié)構(gòu)模型機 控制器CPU PC輸入設(shè)備輸出設(shè)備 MAR MDRALU標(biāo)志寄存

6、器 IR地址數(shù)據(jù)控制GPRs0123存儲器01234567 不同廚師會做的菜不一樣，同一個菜譜的做法也可能不同如同不同架構(gòu)支持的指令集不同，同一種指令的實現(xiàn)方式和功能也可能不同程序的執(zhí)行機制程序的執(zhí)行機制 分以下三個部分介紹 第一講：程序執(zhí)行概述- 程序及指令的執(zhí)行過程 - CPU的基本功能和基本組成 第二講：數(shù)據(jù)通路基本結(jié)構(gòu)和工作原理- 數(shù)據(jù)通路基本結(jié)構(gòu)- 數(shù)據(jù)通路的時序控制 - 數(shù)據(jù)通路基本工作原理 第三講：流水線方式下指令的執(zhí)行 - 指令流水線的基本原理 - 適合流水線的指令集特征 - CISC和RISC風(fēng)格指令集 - 指令流水線的實現(xiàn) - 高級流水線實現(xiàn)技術(shù) 數(shù)據(jù)通路的位置數(shù)據(jù)通路的位

7、置 計算機的五大組成部分： 什么是數(shù)據(jù)通路（DataPath）? 指令執(zhí)行過程中，數(shù)據(jù)所經(jīng)過的路徑，包括路徑中的部件。它是指令的執(zhí)行部件。 控制器（Control）的功能是什么？ 對指令進行譯碼，生成指令對應(yīng)的控制信號，控制數(shù)據(jù)通路的動作。能對執(zhí)行部件發(fā)出控制信號，是指令的控制部件。ControlMemoryCPUInputOutputDatapathDatapath數(shù)據(jù)通路的基本結(jié)構(gòu)數(shù)據(jù)通路的基本結(jié)構(gòu) 數(shù)據(jù)通路由兩類元件組成 組合邏輯元件（也稱操作元件） 時序邏輯元件（也稱狀態(tài)元件，存儲元件） 元件間的連接方式 總線連接方式 分散連接方式 數(shù)據(jù)通路如何構(gòu)成？ 由“操作元件”和“存儲元件”通過

8、總線方式或分散方式連接而成 數(shù)據(jù)通路的功能是什么？ 進行數(shù)據(jù)存儲、處理、傳送因此，數(shù)據(jù)通路是由操作元件和存儲元件通過總線方式或分散方式連接而成的進行數(shù)據(jù)存儲、處理、傳送的路徑。 操作元件：組合邏輯電路操作元件：組合邏輯電路 加法器(Adder)多路選擇器 (MUX)32AB32Y32SelectMUX3232AB32SumCarryAdderCarryIn操作元件：組合邏輯電路操作元件：組合邏輯電路 加法器(Adder)多路選擇器 (MUX)算邏部件(ALU)32AB32Y32SelectMUX3232AB32ResultZeroOPALU3232AB32SumCarryAdderCarryI

9、n操作元件：組合邏輯電路操作元件：組合邏輯電路 加法器(Adder)多路選擇器 (MUX)算邏部件(ALU)32AB32Y32SelectMUX3232AB32ResultZeroOPALU3232AB32SumCarryAdderCarryIn3Decoderout0out1out7out2 譯碼器(Decoder)操作元件：組合邏輯電路操作元件：組合邏輯電路 加法器(Adder)多路選擇器 (MUX)算邏部件(ALU)32AB32Y32SelectMUX3232AB32ResultZeroOPALU3232AB32SumCarryAdderCarryIn3Decoderout0out1ou

10、t7out2 譯碼器(Decoder)控制信號控制信號組合邏輯元件的特點：其輸出只取決于當(dāng)前的輸入。即：若輸入一樣，則其輸出也一樣定時：所有輸入到達后，經(jīng)過一定的邏輯門延時，輸出端改變，并保持到下次改變，不需要時鐘信號來定時狀態(tài)元件：時序邏輯電路狀態(tài)元件：時序邏輯電路 狀態(tài)（存儲）元件的特點： 具有存儲功能，在時鐘控制下輸入被寫到電路中，直到下個時鐘到達 輸入端狀態(tài)由時鐘決定何時被寫入，輸出端狀態(tài)隨時可以讀出 定時方式：規(guī)定信號何時寫入狀態(tài)元件或何時從狀態(tài)元件讀出 邊沿觸發(fā)（edge-triggered）方式：-狀態(tài)單元中的值只在時鐘邊沿改變。每個時鐘周期改變一次。上升沿（rising edg

11、e） 觸發(fā)：在時鐘正跳變時進行讀/寫。下降沿（falling edge）觸發(fā)：在時鐘負跳變時進行讀/寫。 最簡單的狀態(tài)單元（回顧：數(shù)字邏輯電路課程內(nèi)容）： D觸發(fā)器：一個時鐘輸入、一個狀態(tài)輸入、一個狀態(tài)輸出時鐘周期上升沿下降沿數(shù)據(jù)通路中的狀態(tài)元件有兩種：寄存器(組) + 存儲器數(shù)據(jù)通路與時序控制數(shù)據(jù)通路與時序控制Clk寄存器的輸入可變化SetupHold.Setup Hold數(shù)據(jù)通路由“ + 狀態(tài)元件 + 操作元件( 組合電路) + 狀態(tài)元件 + ” 組成只有狀態(tài)元件能存儲信息，操作元件須從狀態(tài)元件接收輸入，并將輸出寫入狀態(tài)元件。其輸入為前一時鐘生成的數(shù)據(jù)，輸出為當(dāng)前時鐘所用的數(shù)據(jù)現(xiàn)代計算機現(xiàn)

12、代計算機的時鐘周期的時鐘周期ClkClk程序的執(zhí)行機制程序的執(zhí)行機制 分以下三個部分介紹 第一講：程序執(zhí)行概述- 程序及指令的執(zhí)行過程 - CPU的基本功能和基本組成 第二講：數(shù)據(jù)通路基本結(jié)構(gòu)和工作原理- 數(shù)據(jù)通路基本結(jié)構(gòu)- 數(shù)據(jù)通路的時序控制 - 數(shù)據(jù)通路基本工作原理 第三講：流水線方式下指令的執(zhí)行 - 指令流水線的基本原理 - 適合流水線的指令集特征 - CISC和RISC風(fēng)格指令集 - 指令流水線的實現(xiàn) - 高級流水線實現(xiàn)技術(shù) Laundry Example Four loads of clothes to wash, dry, and fold wash takes 30 minute

13、s dry takes 40 minutes fold takes 20 minutesABCD一個日常生活中的例子一個日常生活中的例子洗衣服洗衣服Sequential Laundry（串行方式）串行方式）串行方式下 4 批衣服需花費 6 小時（4x(30+40+20)=360分鐘）N批衣服，需花費的時間為Nx(30+40+20) = 90N如果用流水線方式洗衣服，則花多少時間呢? ABCD3040 20 3040 20 3040 20 3040 206 PM7891011MidnightTaskOrderTimePipelined Laundry: (Start work ASAP)串行為9

14、0分鐘x4=6小時N批則為90 xN分鐘ABCD6 PM7891011MidnightTaskOrderTime3040404040 20流水線方式下，需30+4x40+20=210分 (3.5小時)如果有N批衣服呢？30+Nx40+20分鐘假定每一步時間均衡，則比串行方式提高約3倍！流水方式下，所用時間主要與最長階段的時間有關(guān)！指令流水線的基本概念指令流水線的基本概念 五段流水線 取指令(IF)：根據(jù)PC的值從存儲器取出指令。 指令譯碼(ID)：產(chǎn)生指令執(zhí)行所需的控制信號。 取操作數(shù)(OF)：讀取存儲器操作數(shù)或寄存器操作數(shù)。 執(zhí)行(EX)：對操作數(shù)完成指定操作。 寫回(WB)：將操作結(jié)果寫入

15、存儲器或寄存器。單周期數(shù)據(jù)通路中指令的執(zhí)行單周期數(shù)據(jù)通路中指令的執(zhí)行假定：最復(fù)雜指令執(zhí)行過程 取指：200ps；譯碼和讀操作數(shù)：50ps；ALU操作：100ps；讀存儲器：200ps；結(jié)果寫寄存器：50ps。 200+50+100+200=550單周期：每條指令在單個時鐘周期內(nèi)完成，故CPI=1，時鐘周期=600ps每秒執(zhí)行指令條數(shù)：1/600ps=1/(60010-15)=1.671012 CPI=1，指令延時為600ps指令吞吐率為1.67GIPS指令串行執(zhí)行，程序執(zhí)行時間為：指令條數(shù)600ps流水線數(shù)據(jù)通路中指令的執(zhí)行流水線數(shù)據(jù)通路中指令的執(zhí)行假定：最復(fù)雜指令執(zhí)行過程 取指：200ps；

16、譯碼和讀操作數(shù)：50ps；ALU操作：100ps；讀存儲器：200ps；結(jié)果寫寄存器：50ps。 取指令譯碼/讀數(shù)ALU運算讀/寫存儲器寫結(jié)果最長段為200ps 指令延時為：250ps5=1.25ns 指令吞吐率為4GIPS流水線指令集的設(shè)計流水線指令集的設(shè)計 具有什么特征的指令集有利于流水線執(zhí)行呢？ 長度盡量一致，有利于簡化取指令和指令譯碼操作-MIPS指令32位，下址計算方便: PC+4-X86指令從1字節(jié)到17字節(jié)不等，使取指部件極其復(fù)雜 格式少，且源寄存器位置相同，有利于在指令未知時就可取操作數(shù)-MIPS指令的rs和rt位置一定，在指令譯碼時就可讀rs和rt的值若位置隨指令不同而不同，

17、則需先確定指令類型才能取寄存器編號 load / Store指令才能訪問存儲器，有利于減少操作步驟，規(guī)整流水線-lw/sw指令的地址計算和運算指令的執(zhí)行步驟規(guī)整在同一個周期-X86運算類指令操作數(shù)可為內(nèi)存數(shù)據(jù)，需計算地址、訪存、執(zhí)行 內(nèi)存中”對齊”存放，有利于減少訪存次數(shù)和流水線的規(guī)整總之，規(guī)整、簡單和一致等特性有利于指令的流水線執(zhí)行oprsrtrdshamtfunc0611162126316 bits6 bits5 bits5 bits5 bits5 bits按指令格式的復(fù)雜度來分按指令格式的復(fù)雜度來分早期CISC設(shè)計風(fēng)格的主要特點 (1) 指令系統(tǒng)復(fù)雜 變長操作碼 / 變長指令字 / 指令

18、多 / 尋址方式多 / 指令格式多 (2) 指令周期長 絕大多數(shù)指令需要多個時鐘周期才能完成 (3) 各種指令都能訪問存儲器 除了專門的存儲器讀寫指令外，運算指令也能訪問存儲器 (4) 采用微程序控制 (5) 有專用寄存器 (6) 難以進行編譯優(yōu)化來生成高效目標(biāo)代碼例如，VAX-11/780小型機16種尋址方式；9種數(shù)據(jù)格式；303條指令；一條指令包括12個字節(jié)的操作碼和下續(xù)N個操作數(shù)說明符。一個說明符的長度達1 10個字節(jié)。按指令格式的復(fù)雜度來分，有兩種類型計算機：復(fù)雜指令集計算機CISC (Complex Instruction Set Computer)精簡指令集計算機RISC (Red

19、uce Instruction Set Computer)復(fù)雜指令集計算機復(fù)雜指令集計算機CISC 對CISC進行測試，發(fā)現(xiàn)一個事實： 在程序中各種指令出現(xiàn)的頻率懸殊很大，最常使用的是一些簡單指令，這些指令占程序的80%，但只占指令系統(tǒng)的20%。而且在微程序控制的計算機中，占指令總數(shù)20%的復(fù)雜指令占用了控制存儲器容量的80%。 1982年美國加州伯克利大學(xué)的RISC，斯坦福大學(xué)的MIPS，IBM公司的IBM801相繼宣告完成，這些機器被稱為第一代RISC機。uCISC的缺陷 日趨龐大的指令系統(tǒng)不但使計算機的研制周期變長，而且難以保證設(shè)計的正確性，難以調(diào)試和維護，并且因指令操作復(fù)雜而增加機器周

20、期，從而降低了系統(tǒng)性能。u1975年IBM公司開始研究指令系統(tǒng)的合理性問題，John Cocks提出精簡指令系統(tǒng)計算機 RISC ( Reduce Instruction Set Computer )。RISC設(shè)計風(fēng)格的主要特點設(shè)計風(fēng)格的主要特點 (1) 簡化的指令系統(tǒng) 指令少 / 尋址方式少 / 指令格式少 / 指令長度一致 (2) 以RR方式工作 除Load/Store指令可訪存外，其余指令都只訪問寄存器 (3) 指令周期短 以流水線方式工作， 因而除Load/Store指令外，其他簡單指令都只需一個或一個不到的時鐘周期就可完成 (4) 采用大量通用寄存器，以減少訪存次數(shù) (5) 采用硬連

21、線路控制器，不用或少用微程序控制 (6) 采用優(yōu)化的編譯系統(tǒng)，力求有效地支持高級語言程序MIPS是典型的RISC處理器，82年以來新的指令集大多采用RISC體系結(jié)構(gòu)x86因為“兼容”的需要，保留了CISC的風(fēng)格，同時也借鑒了RISC思想 指令流水線的實現(xiàn)指令流水線的實現(xiàn)假定：最復(fù)雜指令執(zhí)行過程 取指：200ps；譯碼和讀操作數(shù)：50ps；ALU操作：100ps；讀存儲器：200ps；結(jié)果寫寄存器：50ps。 取指令I(lǐng)Fetch讀數(shù)/譯碼Reg/DecALU運算Exec讀/寫存儲器Mem寫結(jié)果Write可以分5個流水段，最長階段為200ps 指令流水線的執(zhí)行舉例指令流水線的執(zhí)行舉例End ofC

22、ycle 4End ofCycle 5End ofCycle 6End ofCycle 7ClockCycle 1Cycle 2Cycle 3Cycle 4Cycle 5Cycle 6Cycle 7Cycle 8IfetchReg/DecExecMemWr0: LoadIfetchReg/DecExecMemWr4: R-typeIfetchReg/DecExecMemWr8: StoreIfetchReg/DecExecMemWr 12: Beq 周期4結(jié)束: Load 的 Mem, R-type 的 Exec, Store 的 Reg, Beq 的 Ifetch周期5結(jié)束: Load 的

23、Wr, R-type 的 Mem, Store 的 Exec, Beq 的 Reg周期6結(jié)束: R-type 的 Wr, Store 的 Mem, Beq 的 Exec周期7結(jié)束: Store 的 Wr, Beq 的 Mem考察以下幾個點的情況：考察以下幾個點的情況：指令流水線的執(zhí)行舉例指令流水線的執(zhí)行舉例lw指令與beq、sub、or指令關(guān)于$8數(shù)據(jù)相關(guān)sub與or關(guān)于$9數(shù)據(jù)相關(guān)可通過轉(zhuǎn)發(fā)解決數(shù)據(jù)相關(guān)可通過前半周期寫后半周期讀解決數(shù)據(jù)相關(guān)Load-use數(shù)據(jù)相關(guān)不能通過轉(zhuǎn)發(fā)解決指令lw與beq是load-use數(shù)據(jù)相關(guān) Hazards：指流水線遇到無法正確執(zhí)行后續(xù)指令或執(zhí)行了不該執(zhí)行的指令

24、 結(jié)構(gòu)冒險 (hardware resource conflicts，硬件資源沖突): 現(xiàn)象：同一個部件同時被不同指令所使用 - 一個部件每條指令只能使用1次，且只能在特定周期使用- 設(shè)置多個部件，以避免沖突。如指令存儲器IM 和數(shù)據(jù)存儲器DM分開 數(shù)據(jù)冒險 (data dependencies，數(shù)據(jù)相關(guān)): 現(xiàn)象：后面指令用到前面指令結(jié)果數(shù)據(jù)時，前面指令的結(jié)果還沒產(chǎn)生- 轉(zhuǎn)發(fā)(Forwarding/Bypassing旁路) 或 前半周期讀后半周期寫- Load-use冒險不能通過轉(zhuǎn)發(fā)解決，需阻塞(stall)一個時鐘周期- 編譯程序優(yōu)化指令順序 控制 (分支) 冒險 (changes in

25、program flow，改變控制流): 現(xiàn)象：轉(zhuǎn)移或異常改變執(zhí)行流程，后繼指令在目標(biāo)地址產(chǎn)生前已被取出- 采用靜態(tài)或動態(tài)分支預(yù)測- 編譯程序優(yōu)化指令順序(分支延遲)流水線的沖突流水線的沖突/ /冒險冒險( (hazard) )情況情況本本PPT內(nèi)容只需大概了解內(nèi)容只需大概了解以下源程序可生成兩種不同的代碼，優(yōu)化的代碼可避免Load阻塞a = b + c;d = e f;假定 a, b, c, d ,e, f 在內(nèi)存編譯器優(yōu)化指令順序解決數(shù)據(jù)冒險編譯器優(yōu)化指令順序解決數(shù)據(jù)冒險Fast code:lw $2, blw $3, clw $5, e add $1, $2, $3lw $6, fsw

26、$1, asub $4, $5, $6sw$4, d Slow code:lw$2, blw $3, cadd $1, $2, $3sw $1, alw $5, e lw $6, fsub $4, $5, $6sw$4, d調(diào)整后調(diào)整后編譯器的優(yōu)化很重要！如果硬件不支持阻塞處理的話，則編譯器可以將順序調(diào)整和插入NOP指令結(jié)合起來，在找不到可插入的指令時，插入NOP指令！編譯器優(yōu)化以避免阻塞的情況調(diào)查編譯器優(yōu)化以避免阻塞的情況調(diào)查% % l lo oa ad ds s s st ta al ll li in ng g p pi ip pe el li in ne e0 0% %2 20 0% %4 40 0% %6 60 0% %8 80 0% %t te ex xs sp pi ic ce eg gc cc c2