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

第五章

程序的執(zhí)行

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

數(shù)據(jù)通路基本結(jié)構(gòu)和工作原理

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

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

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

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

回顧：馮.諾依曼結(jié)構(gòu)模型機(jī)控制器CPUPC輸入設(shè)備輸出設(shè)備MARMDRALU標(biāo)志寄存器

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

bits5

bits按指令格式的復(fù)雜度來(lái)分早期CISC設(shè)計(jì)風(fēng)格的主要特點(diǎn)(1)指令系統(tǒng)復(fù)雜

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

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

除了專門的存儲(chǔ)器讀寫指令外，運(yùn)算指令也能訪問(wèn)存儲(chǔ)器

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

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

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

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

ofCycle4EndofCycle5End

ofCycle

6End

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

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

Hazards：指流水線遇到無(wú)法正確執(zhí)行后續(xù)指令或執(zhí)行了不該執(zhí)行的指令結(jié)構(gòu)冒險(xiǎn)

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

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

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

(changesinprogramflow，改變控制流):現(xiàn)象：轉(zhuǎn)移或異常改變執(zhí)行流程，后繼指令在目標(biāo)地址產(chǎn)生前已被取出采用靜態(tài)或動(dòng)態(tài)分支預(yù)測(cè)編譯程序優(yōu)化指令順序(分支延遲)流水線的沖突/冒險(xiǎn)(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ù)冒險(xiǎn)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