第五章程序執(zhí)行-1-4

第五章

程序的執(zhí)行

程序執(zhí)行和指令執(zhí)行概述

數(shù)據(jù)通路基本結構和工作原理

流水線方式下指令的執(zhí)行

程序的執(zhí)行機制分以下三個部分介紹第一講：程序執(zhí)行概述程序及指令的執(zhí)行過程CPU的基本功能和基本組成第二講：數(shù)據(jù)通路基本結構和工作原理數(shù)據(jù)通路基本結構數(shù)據(jù)通路的時序控制數(shù)據(jù)通路基本工作原理

第三講：流水線方式下指令的執(zhí)行指令流水線的基本原理適合流水線的指令集特征CISC和RISC風格指令集指令流水線的實現(xiàn)高級流水線實現(xiàn)技術

程序及指令的執(zhí)行過程程序和指令的關系程序由一條一條指令組成，指令按順序存放在內(nèi)存連續(xù)單元程序的執(zhí)行：周而復始地執(zhí)行一條一條指令正常情況下，指令按其存放順序執(zhí)行遇到需改變程序執(zhí)行流程時，用相應的轉移指令（包括無條件轉移指令、條件轉移指令、調(diào)用指令和返回指令等）來改變程序執(zhí)行流程程序的執(zhí)行流的控制將要執(zhí)行的指令所在存儲單元的地址由程序計數(shù)器PC給出，通過改變PC的值來控制執(zhí)行順序指令周期：CPU取出并執(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)部操作：涉及CPU內(nèi)部數(shù)據(jù)通路（本章節(jié)內(nèi)容）機器指令的執(zhí)行過程CPU執(zhí)行指令的過程取指令PC+“1”指令譯碼進行主存地址運算取操作數(shù)進行算術/邏輯運算存結果以上每步都需檢測“異?！比粲挟惓?，則自動切換到異常處理程序檢測是否有“中斷”請求，有則轉中斷處理指令執(zhí)行過程問題：“取指令”一定在最開始做嗎？PC+“1”一定在譯碼之前做嗎？“譯碼”須在指令執(zhí)行前做嗎？異常是在CPU內(nèi)部發(fā)生的，中斷是由外部事件引起的取指階段執(zhí)行階段“1”：指一條指令的長度，定長指令字每次都一樣；變長指令字每次可能不同定長指令字通常在譯碼前做，變長指令字在譯碼后做！機器指令的執(zhí)行過程取指令：從PC所指單元取出指令送指令寄存器（IR），并增量PC。如add函數(shù)，開始PC（IA-32的EIP）中存放的是0x0848394，CPU根據(jù)PC取指令送IR，每次總是取最長指令字節(jié)數(shù)，假定最長指令是4個字節(jié)，即IR為32位，此時，也即5589E58BH被取到IR中。指令譯碼：不同指令其功能不同，因而需要不同的操作控制信號。CPU根據(jù)不同操作碼譯出不同控制信號。對于上述取到IR中的5589E58BH譯碼時，可根據(jù)高5位01010譯碼得到push指令的控制信號。源操作數(shù)地址計算并取操作數(shù)：根據(jù)尋址方式確定源操作數(shù)地址計算方式，若是存儲器數(shù)據(jù)，則需一次或多次訪存；若為間接尋址或兩操作數(shù)都在存儲器的雙目運算，則需多次訪存；若是寄存器數(shù)據(jù)，則直接從寄存器取數(shù)。執(zhí)行數(shù)據(jù)操作：在ALU或加法器等運算部件中對取出的源操作數(shù)進行運算。目的操作數(shù)地址計算并存結果：根據(jù)尋址方式確定目的操作數(shù)地址計算方式，若是存儲器數(shù)據(jù)，則需要一次或多次訪存（間接尋址時）；若是寄存器數(shù)據(jù)，則在進行數(shù)據(jù)操作時直接存結果到寄存器。指令地址計算并將其送PC。順序執(zhí)行時，PC加上當前指令長度；遇到轉移類指令時，則需要根據(jù)條件碼、操作碼和尋址方式等確定下條指令地址。

回顧：馮.諾依曼結構模型機控制器CPUPC輸入設備輸出設備MARMDRALU標志寄存器

IR地址數(shù)據(jù)控制GPRs0123存儲器01234567

不同廚師會做的菜不一樣，同一個菜譜的做法也可能不同如同不同架構支持的指令集不同，同一種指令的實現(xiàn)方式和功能也可能不同程序的執(zhí)行機制分以下三個部分介紹第一講：程序執(zhí)行概述程序及指令的執(zhí)行過程CPU的基本功能和基本組成第二講：數(shù)據(jù)通路基本結構和工作原理數(shù)據(jù)通路基本結構數(shù)據(jù)通路的時序控制數(shù)據(jù)通路基本工作原理

第三講：流水線方式下指令的執(zhí)行指令流水線的基本原理適合流水線的指令集特征CISC和RISC風格指令集指令流水線的實現(xiàn)高級流水線實現(xiàn)技術

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

操作元件：組合邏輯電路加法器(Adder)多路選擇器(MUX)32AB32Y32SelectMUX3232AB32SumCarryAdderCarryIn操作元件：組合邏輯電路加法器(Adder)多路選擇器(MUX)算邏部件(ALU)32AB32Y32SelectMUX3232AB32ResultZeroOPALU3232AB32SumCarryAdderCarryIn操作元件：組合邏輯電路加法器(Adder)多路選擇器(MUX)算邏部件(ALU)32AB32Y32SelectMUX3232AB32ResultZeroOPALU3232AB32SumCarryAdderCarryIn3Decoderout0out1out7out2譯碼器(Decoder)操作元件：組合邏輯電路加法器(Adder)多路選擇器(MUX)算邏部件(ALU)32AB32Y32SelectMUX3232AB32ResultZeroOPALU3232AB32SumCarryAdderCarryIn3Decoderout0out1out7out2譯碼器(Decoder)控制信號組合邏輯元件的特點：其輸出只取決于當前的輸入。即：若輸入一樣，則其輸出也一樣定時：所有輸入到達后，經(jīng)過一定的邏輯門延時，輸出端改變，并保持到下次改變，不需要時鐘信號來定時狀態(tài)元件：時序邏輯電路狀態(tài)（存儲）元件的特點：具有存儲功能，在時鐘控制下輸入被寫到電路中，直到下個時鐘到達輸入端狀態(tài)由時鐘決定何時被寫入，輸出端狀態(tài)隨時可以讀出定時方式：規(guī)定信號何時寫入狀態(tài)元件或何時從狀態(tài)元件讀出邊沿觸發(fā)（edge-triggered）方式：狀態(tài)單元中的值只在時鐘邊沿改變。每個時鐘周期改變一次。上升沿（risingedge）觸發(fā)：在時鐘正跳變時進行讀/寫。下降沿（fallingedge）觸發(fā)：在時鐘負跳變時進行讀/寫。最簡單的狀態(tài)單元（回顧：數(shù)字邏輯電路課程內(nèi)容）：D觸發(fā)器：一個時鐘輸入、一個狀態(tài)輸入、一個狀態(tài)輸出時鐘周期上升沿下降沿數(shù)據(jù)通路中的狀態(tài)元件有兩種：寄存器(組)+存儲器數(shù)據(jù)通路與時序控制Clk寄存器的輸入可變化SetupHold............SetupHold數(shù)據(jù)通路由“…+狀態(tài)元件

+操作元件(組合電路)+狀態(tài)元件

+…”組成只有狀態(tài)元件能存儲信息，操作元件須從狀態(tài)元件接收輸入，并將輸出寫入狀態(tài)元件。其輸入為前一時鐘生成的數(shù)據(jù)，輸出為當前時鐘所用的數(shù)據(jù)現(xiàn)代計算機的時鐘周期ClkClk程序的執(zhí)行機制分以下三個部分介紹第一講：程序執(zhí)行概述程序及指令的執(zhí)行過程CPU的基本功能和基本組成第二講：數(shù)據(jù)通路基本結構和工作原理數(shù)據(jù)通路基本結構數(shù)據(jù)通路的時序控制數(shù)據(jù)通路基本工作原理

第三講：流水線方式下指令的執(zhí)行

指令流水線的基本原理適合流水線的指令集特征CISC和RISC風格指令集指令流水線的實現(xiàn)高級流水線實現(xiàn)技術

LaundryExampleFourloadsofclothestowash,dry,andfoldwashtakes 30minutesdrytakes40minutesfoldtakes 20minutesABCD一個日常生活中的例子—洗衣服SequentialLaundry（串行方式）串行方式下4批衣服需花費6小時（4x(30+40+20)=360分鐘）N批衣服，需花費的時間為Nx(30+40+20)=90N如果用流水線方式洗衣服，則花多少時間呢?ABCD3040203040203040203040206PM7891011MidnightTaskOrderTimePipelinedLaundry:(StartworkASAP)串行為90分鐘x4=6小時N批則為90xN分鐘ABCD6PM7891011MidnightTaskOrderTime304040404020流水線方式下，需30+4x40+20=210分(3.5小時)如果有N批衣服呢？30+Nx40+20分鐘假定每一步時間均衡，則比串行方式提高約3倍！流水方式下，所用時間主要與最長階段的時間有關！指令流水線的基本概念五段流水線

取指令(IF)：根據(jù)PC的值從存儲器取出指令。

指令譯碼(ID)：產(chǎn)生指令執(zhí)行所需的控制信號。

取操作數(shù)(OF)：讀取存儲器操作數(shù)或寄存器操作數(shù)。

執(zhí)行(EX)：對操作數(shù)完成指定操作。

寫回(WB)：將操作結果寫入存儲器或寄存器。單周期數(shù)據(jù)通路中指令的執(zhí)行假定：最復雜指令執(zhí)行過程①取指：200ps；②譯碼和讀操作數(shù)：50ps；③ALU操作：100ps；④讀存儲器：200ps；⑤結果寫寄存器：50ps。

200+50+100+200=550單周期：每條指令在單個時鐘周期內(nèi)完成，故CPI=1，時鐘周期=600ps每秒執(zhí)行指令條數(shù)：1/600ps=1/(600×10-15)=1.67×1012

CPI=1，指令延時為600ps指令吞吐率為1.67GIPS指令串行執(zhí)行，程序執(zhí)行時間為：指令條數(shù)×600ps流水線數(shù)據(jù)通路中指令的執(zhí)行假定：最復雜指令執(zhí)行過程①取指：200ps；②譯碼和讀操作數(shù)：50ps；③ALU操作：100ps；④讀存儲器：200ps；⑤結果寫寄存器：50ps。取指令譯碼/讀數(shù)ALU運算讀/寫存儲器寫結果最長段為200ps

指令延時為：250ps×5=1.25ns指令吞吐率為4GIPS流水線指令集的設計具有什么特征的指令集有利于流水線執(zhí)行呢？長度盡量一致，有利于簡化取指令和指令譯碼操作MIPS指令32位，下址計算方便:PC+4X86指令從1字節(jié)到17字節(jié)不等，使取指部件極其復雜格式少，且源寄存器位置相同，有利于在指令未知時就可取操作數(shù)MIPS指令的rs和rt位置一定，在指令譯碼時就可讀rs和rt的值若位置隨指令不同而不同，則需先確定指令類型才能取寄存器編號load/Store指令才能訪問存儲器，有利于減少操作步驟，規(guī)整流水線lw/sw指令的地址計算和運算指令的執(zhí)行步驟規(guī)整在同一個周期X86運算類指令操作數(shù)可為內(nèi)存數(shù)據(jù)，需計算地址、訪存、執(zhí)行內(nèi)存中”對齊”存放，有利于減少訪存次數(shù)和流水線的規(guī)整總之，規(guī)整、簡單和一致等特性有利于指令的流水線執(zhí)行oprsrtrdshamtfunc0611162126316bits6bits5bits5bits5

bits5

bits按指令格式的復雜度來分早期CISC設計風格的主要特點(1)指令系統(tǒng)復雜

變長操作碼/變長指令字/指令多/尋址方式多/指令格式多(2)指令周期長

絕大多數(shù)指令需要多個時鐘周期才能完成(3)各種指令都能訪問存儲器

除了專門的存儲器讀寫指令外，運算指令也能訪問存儲器

(4)采用微程序控制(5)有專用寄存器(6)難以進行編譯優(yōu)化來生成高效目標代碼例如，VAX-11/780小型機16種尋址方式；9種數(shù)據(jù)格式；303條指令；一條指令包括1～2個字節(jié)的操作碼和下續(xù)N個操作數(shù)說明符。一個說明符的長度達1～10個字節(jié)。按指令格式的復雜度來分，有兩種類型計算機：復雜指令集計算機CISC(ComplexInstructionSetComputer)精簡指令集計算機RISC(Reduce

InstructionSetComputer)復雜指令集計算機CISC對CISC進行測試，發(fā)現(xiàn)一個事實：在程序中各種指令出現(xiàn)的頻率懸殊很大，最常使用的是一些簡單指令，這些指令占程序的80%，但只占指令系統(tǒng)的20%。而且在微程序控制的計算機中，占指令總數(shù)20%的復雜指令占用了控制存儲器容量的80%。1982年美國加州伯克利大學的RISCⅠ，斯坦福大學的MIPS，IBM公司的IBM801相繼宣告完成，這些機器被稱為第一代RISC機。CISC的缺陷日趨龐大的指令系統(tǒng)不但使計算機的研制周期變長，而且難以保證設計的正確性，難以調(diào)試和維護，并且因指令操作復雜而增加機器周期，從而降低了系統(tǒng)性能。1975年IBM公司開始研究指令系統(tǒng)的合理性問題，JohnCocks提出精簡指令系統(tǒng)計算機RISC(ReduceInstructionSetComputer)。RISC設計風格的主要特點(1)簡化的指令系統(tǒng)指令少/尋址方式少/指令格式少/指令長度一致(2)以RR方式工作除Load/Store指令可訪存外，其余指令都只訪問寄存器(3)指令周期短以流水線方式工作，

因而除Load/Store指令外，其他簡單指令都只需一個或一個不到的時鐘周期就可完成(4)采用大量通用寄存器，以減少訪存次數(shù)(5)采用硬連線路控制器，不用或少用微程序控制(6)采用優(yōu)化的編譯系統(tǒng)，力求有效地支持高級語言程序MIPS是典型的RISC處理器，82年以來新的指令集大多采用RISC體系結構x86因為“兼容”的需要，保留了CISC的風格，同時也借鑒了RISC思想指令流水線的實現(xiàn)假定：最復雜指令執(zhí)行過程①取指：200ps；②譯碼和讀操作數(shù)：50ps；③ALU操作：100ps；④讀存儲器：200ps；⑤結果寫寄存器：50ps。取指令IFetch讀數(shù)/譯碼Reg/DecALU運算Exec讀/寫存儲器Mem寫結果Write可以分5個流水段，最長階段為200ps

指令流水線的執(zhí)行舉例End

ofCycle4EndofCycle5End

ofCycle

6End

ofCycle7ClockCycle1Cycle2Cycle3Cycle4Cycle5Cycle6Cycle7Cycle8IfetchReg/DecExecMemWr0:LoadIfetchReg/DecExecMemWr4:R-typeIfetchReg/DecExecMemWr8:

StoreIfetchReg/DecExecMemWr12:Beq周期4結束:Load的Mem,R-type的Exec,Store的Reg,Beq的Ifetch周期5結束:Load的Wr,R-type的Mem,Store的Exec,Beq的Reg周期6結束:R-type的Wr,Store的Mem,Beq的Exec周期7結束:Store的Wr,Beq的Mem考察以下幾個點的情況：指令流水線的執(zhí)行舉例lw指令與beq、sub、or指令關于$8數(shù)據(jù)相關sub與or關于$9數(shù)據(jù)相關可通過轉發(fā)解決數(shù)據(jù)相關可通過前半周期寫后半周期讀解決數(shù)據(jù)相關Load-use數(shù)據(jù)相關不能通過轉發(fā)解決指令lw與beq是load-use數(shù)據(jù)相關

Hazards：指流水線遇到無法正確執(zhí)行后續(xù)指令或執(zhí)行了不該執(zhí)行的指令結構冒險

(hardwareresourceconflicts，硬件資源沖突):現(xiàn)象：同一個部件同時被不同指令所使用

一個部件每條指令只能使用1次，且只能在特定周期使用設置多個部件，以避免沖突。如指令存儲器IM和數(shù)據(jù)存儲器DM分開數(shù)據(jù)冒險

(datadependencies，數(shù)據(jù)相關):現(xiàn)象：后面指令用到前面指令結果數(shù)據(jù)時，前面指令的結果還沒產(chǎn)生轉發(fā)(Forwarding/Bypassing旁路)或前半周期讀后半周期寫Load-use冒險不能通過轉發(fā)解決，需阻塞(stall)一個時鐘周期編譯程序優(yōu)化指令順序控制(分支)冒險

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

lw $2,b lw $3,c

lw $5,e add $1,$2,$3 lw $6,f

sw $1,a sub $4,$5,$6 sw $4,d

Slowcode:

lw $2,b lw $3,c add $1,$2,$3

sw $1,a lw