計算機(jī)體系結(jié)構(gòu)

1、Chapter 1計算題l 需求篩選的依據(jù)是成本性能比l 直接實現(xiàn)一般指用硬件實現(xiàn)，而間接實現(xiàn)是指用軟件實現(xiàn)l 軟件和硬件要綜合考慮，要以價格性能比高低為取舍原則。l 常用的基本功能或產(chǎn)量很大的功能才適宜于用硬件實現(xiàn)。l 設(shè)計者最終要用成本性能比作為軟、硬件實現(xiàn)功能的取舍標(biāo)準(zhǔn)；消費者要用價格性能比作為選購計算機(jī)系統(tǒng)的取舍標(biāo)準(zhǔn)。l 設(shè)計人員的參考原則:n 考慮用戶應(yīng)用領(lǐng)域n 設(shè)計周期長的硬件不宜采用n 常用的功能盡量采用硬件實現(xiàn)n 實現(xiàn)功能的成本性能比(或價格性能比)要低n 超前設(shè)計l 某一計算機(jī)用于商業(yè)外貿(mào)的事務(wù)處理，有大量的字符串處理操作。由于這種商務(wù)處理很普遍，有較大的市場，故而設(shè)計人員決

2、定在下一代計算機(jī)的CPU中加入字符串操作的功能。經(jīng)測試應(yīng)用軟件調(diào)查發(fā)現(xiàn)，字符串操作的使用占整個程序運行時間的50%。而增加此功能如用軟件(如微程序)實現(xiàn)，則快5倍，增加CPU成本1/5倍；如果用硬件實現(xiàn)，則快100倍，CPU成本增加到5倍。問設(shè)計人員提出增加此功能是否恰當(dāng)？如恰當(dāng)則此功能應(yīng)該用軟件實現(xiàn)還是用硬件實現(xiàn)？設(shè)CPU成本占整機(jī)成本的1/3解： 首先來計算機(jī)在兩種情況下提高的性能和成本性能比。 設(shè)： S為CPU未增加字符串功能時的CPU平均速度，Told為此時運行程序的時間，Tnew為增加字符串功能后程序運行的時間，則l Amdahl定律 (性能遞減規(guī)則)n 某部件應(yīng)用越頻繁，當(dāng)提高該部

3、件性能時，整機(jī)性能也提高的越多。但不管該部件性能提高多大，整機(jī)的性能加速不可能大于在原機(jī)器中除該部件外所有其它部件運行時間的百分比的倒數(shù)1/(1-F)n 計算機(jī)性能的改善程度受其采用的快速部件(被提高性能的部件)在原任務(wù)中使用所占的時間百分比的限制nl 采用新器件使某一功能性能提高10倍，但該功能的使用只占原程序運行時間的40%。請計算新計算機(jī)性能改善了多少？ll 高頻事件高速處理(大概率事件優(yōu)先的原則)l 局部性原理n 最重要的是90/10局部性規(guī)則n 時間局部性n 空間局部性l 適應(yīng)計算機(jī)發(fā)展趨勢l 在指令系統(tǒng)中指令的確定是屬于計算機(jī)系統(tǒng)結(jié)構(gòu)的，而指令操作的實現(xiàn)，如取指令、取操作數(shù)、運算、

4、送結(jié)果等具體操作及排序方式是屬于計算機(jī)組成的，而實現(xiàn)這些指令功能的具體電路、器件的設(shè)計及裝配技術(shù)是計算機(jī)物理實現(xiàn)的l 計算機(jī)的性能是指在計算機(jī)上完成用戶的應(yīng)用任務(wù)所需的時間長短l 響應(yīng)(實耗)時間是指計算機(jī)系統(tǒng)完成某一任務(wù)(程序)所花費的時間n 速度，即用響應(yīng)時間的倒數(shù)n 用速度來評價性能，我們稱“高”為性能好；如果用響應(yīng)時間來評價性能，我們稱“短”為性能好l 計算機(jī)整機(jī)性能分成兩部分：一是CPU執(zhí)行程序的時間，二是等待時間。提高計算機(jī)性能就是提高CPU性能和減少等待時間。l CPU時間也包含兩部分，即用戶CPU時間(user CPU time)和系統(tǒng)CPU時間(system CPU time

5、)l CPUtime =整個程序的總時鐘數(shù)×時鐘周期l 每條指令的平均時鐘周期數(shù)(Clock cycles Per Instruction)，簡稱為CPIl 指令數(shù)×CPI代替總時鐘數(shù)l 設(shè)條件轉(zhuǎn)移指令的實現(xiàn)有兩種方案可以選擇。機(jī)器A：用兩條指令完成。由比較指令建立條件碼，再在轉(zhuǎn)移指令中測試條件碼。機(jī)器B：只用一條指令。比較和轉(zhuǎn)移一起執(zhí)行。對于這兩種機(jī)器來說，條件轉(zhuǎn)移指令用2個時鐘，所有其它指令花費一個時鐘。在機(jī)器A上有20%的執(zhí)行指令是條件轉(zhuǎn)移指令，因此每個轉(zhuǎn)移都需要比較，有20%是比較指令。由于機(jī)器A在轉(zhuǎn)移指令中沒有比較功能，這樣時鐘頻率比機(jī)器B快25%，問哪個機(jī)器快？

6、解：忽略所有等待及系統(tǒng)時間，我們可以用CPU時間來比較機(jī)器的性能。 機(jī)器A： CPIA20%×2 80%×11.2 CPUtimeA指令數(shù)A×1.2×時鐘周期A 1.2IA A機(jī)器B： 無比較指令，則指令數(shù)要比機(jī)器A少20%，只有機(jī)器A指令數(shù)的80%，即指令數(shù)B=80%指令數(shù)A。在機(jī)器A的指令中有20%指令是轉(zhuǎn)移指令，它占機(jī)器B的指令數(shù)的百分比是20%80%=25%。因此機(jī)器B的CPIB25%×275%×11.25。同時A機(jī)器時鐘比B機(jī)器快25%，故時鐘周期B(1+25%)A1.25ACPUtimeB指令數(shù)B×CPIB

7、15;時鐘周期B 0.80IA×1.25×1.25A 1.25IAA 從計算中我們看出機(jī)器A雖然比機(jī)器B多執(zhí)行了20%的指令，但由于它的時鐘周期短，同時CPI也小，反而比機(jī)器B快l 某臺計算機(jī)的指令集原來進(jìn)行存儲器訪問的指令只有Load/Store，其它指令只能在寄存器之間操作。這種機(jī)器我們稱為Load/Store型機(jī)器。現(xiàn)測得這臺Load/Store計算機(jī)指令的使用頻率和時鐘數(shù)如表1-5所示。在ALU操作中，有25%的操作數(shù)是由Load指令取得?，F(xiàn)在ALU操作中使其有一個操作數(shù)可以在存儲器內(nèi)，即register-memory指令，這條指令執(zhí)行的時鐘數(shù)是2。假設(shè)擴(kuò)展指令集后

8、使轉(zhuǎn)移指令增加1個時鐘數(shù)，但不影響時鐘周期，問這樣改變后計算機(jī)性能是否提高？ ll 對于例1-6的計算機(jī)，我們采用優(yōu)化編譯來改善其性能。編譯可以減少50%的ALU指令，但它不能減少Load，Store和Branch指令，忽略系統(tǒng)因素，并假設(shè)時鐘周期是20ns(50MHz頻率)，請問優(yōu)化編譯后的MIPS和沒有優(yōu)化編譯時的MIPS各為多少？MIPS的變化和執(zhí)行時間的變化是否一致？ll 基準(zhǔn)程序的一般設(shè)計原則n 具有代表性 n 不能對基準(zhǔn)程序進(jìn)行優(yōu)化。n 復(fù)現(xiàn)性。n 可移植性。n 緊湊性。n 成本-效率要高l 性能報告相關(guān)參數(shù)的計算l 哈夫曼壓縮的基本思想是：出現(xiàn)頻率最大的事件用最少的位（或最短的時

9、間）來表示（或處理），而頻率較小的事件用較多的位（較長的時間）來表示（或處理），從而達(dá)到平均位數(shù)（或時間）縮短的目的l 操作碼的信息源熵(entropy 系統(tǒng)包含的平均信息量)公式 H=pilog2pi式中pi為事件出現(xiàn)的頻率lChapter 2l 計算機(jī)的三種機(jī)器結(jié)構(gòu)n 堆棧u 優(yōu)點：賦值表達(dá)式簡單，指令長度較短，代碼密度高；u 缺點：不能隨機(jī)訪問存儲器，代碼效率低。n 累加器u 優(yōu)點：機(jī)器內(nèi)部狀態(tài)最少，指令長度最短（9bytes）；u 缺點：僅一個暫存器，和存儲器的通信頻繁。n 通用寄存器u 優(yōu)點：最一般的指令模型，第一類，寄存器利用率最高，代碼長度MAX15字節(jié)。第二類，和累加器形式相似

10、，暫存器個數(shù)多；u 缺點：寄存器要顯示說明，導(dǎo)致指令字較長。l 在ALU指令中不對內(nèi)存進(jìn)行操作的計算機(jī)稱為載入-存儲(Load-Store)或者寄存器-寄存器(register-register)機(jī)器。ALU指令中有一個內(nèi)存操作數(shù)的指令稱為寄存器-存儲器(register- memory)指令。有多個內(nèi)存操作數(shù)的指令稱為存儲器-存儲器(memory-memory)指令。l 我們是在確定了計算機(jī)應(yīng)有的功能后，并確定了哪些功能是由硬件來實現(xiàn)(直接提供指令)，哪些功能是由軟件實現(xiàn)(由基本指令組合實現(xiàn))后，再來進(jìn)行指令集的設(shè)計。l 最常用的指令操作：存儲器訪問(memory references)、算

11、術(shù)邏輯單元(ALU operation)操作和轉(zhuǎn)移指令(branch)操作三類。l 控制操作、算術(shù)操作和數(shù)據(jù)傳輸三大類指令是最常用的，可以認(rèn)為也是各種計算機(jī)必不可少的指令。l 假定反向條件轉(zhuǎn)移指令90%是成功的，用表2-4平均數(shù)計算正向條件轉(zhuǎn)移的成功率。ll 正向條件轉(zhuǎn)移大部分是不成功的，它滿足條件的概率較低l 在字單元地址內(nèi)有兩種字節(jié)排列次序：第一種為低位收尾(little endian)，其字節(jié)次序是低字節(jié)在最低位的排列；第二種為高位收尾(big endian)，其字節(jié)次序是高字節(jié)在最低位的排列l(wèi) 假設(shè)訪問的數(shù)據(jù)字節(jié)數(shù)是S，而訪問的字節(jié)地址是A，那么A mod S =0，則稱為地址A所訪問

12、的S字節(jié)是對齊的。l 只要是跨CPU字地址的寄存器總線訪問一定要兩個總線訪問周期才能完成l 寄存器分配策略1. 假設(shè)計算機(jī)具有無窮多個寄存器，根據(jù)需要分配寄存器的變量個數(shù)，以出現(xiàn)時間先后為序建立一個寄存器變量圖。圖中每個變量用小圓圈表示，圈內(nèi)標(biāo)上變量名，每個變量稱為一個節(jié)點。2. 用弧連接各相鄰節(jié)點。連接的原則是可能同時出現(xiàn)的變量節(jié)點作為相鄰節(jié)點，用弧連接起來。從變量角度來講，線段連接的是時空上重疊出現(xiàn)的變量生存范圍。此時稱整個圖為相干圖。3. 編譯程序給相干圖著色。著色的顏色數(shù)應(yīng)小于等于能分配給變量的寄存器數(shù)，著色的條件是相鄰節(jié)點不可以用同樣的顏色。這種限制使兩個同時出現(xiàn)的變量不會爭用同一個

13、寄存器。沒有線段相連的節(jié)點，可以是同一種顏色，即允許不重疊出現(xiàn)的變量使用同一個寄存器。著色后每一種顏色對應(yīng)一個活動變量或一個寄存器。根據(jù)相干圖分配物理寄存器。l RISC設(shè)計思想是：指令集設(shè)計時根據(jù)Amdahl定律選擇使用概率高的指令構(gòu)成指令集，這些大概率指令一般是簡單指令，因此控制器可以設(shè)計的簡單、高速，且占CPU集成電路芯片的面積少，空出較多的集成電路芯片面積用來增加寄存器數(shù)量。在編譯的配合下減少訪存次數(shù)，減少指令間的各種相關(guān)和競爭，盡可能得到最佳指令序列，從而提高計算機(jī)系統(tǒng)的整體性能。l 某應(yīng)用程序，簡單的基本指令占80%，而復(fù)雜指令占20%，在傳統(tǒng)CISC計算機(jī)上運行，簡單指令的CPI

14、=4，復(fù)雜指令的CPI=8，而在RISC計算機(jī)上運行只有簡單指令，其CPI=1，復(fù)雜指令用簡單指令合成實現(xiàn)。假設(shè)平均每條復(fù)雜指令需14條基本指令組合，請比較個計算機(jī)系統(tǒng)運行該應(yīng)用程序的性能。解：設(shè)CISC計算機(jī)的時鐘周期為 TCISC，RISC計算機(jī)的時鐘周期為TRISC，則： CISC計算機(jī)的平均 CPI=0.8×4+0.2×8=4.8RISC計算機(jī)的指令數(shù)增加為 IRISC=0.8ICISC+0.2ICISC×14=3.6ICISC因 CPUtime=I×CPI×T故 CPUtime-CISC=ICISC ×4.8×TC

15、ISC=4.8ICISC×TCISC CPUtime-RISC=IRISC×1×TRISC=3.6ICISC×TRISC 若TCISC=TRISC ，則RISC計算機(jī)比CISC計算機(jī)性能提高33%。實際上，減少TRISC比減少TCISC要來的容易。Chapter 3畫圖題l 處理器可分為兩部分n 數(shù)據(jù)通路n 控制器ll 一條指令的執(zhí)行分為以下五個步驟：n 1. 取指令(instruction fetch) 。n 2. 指令譯碼/寄存器讀出(instruction decode/register fetch)。n 3. 執(zhí)行/有效地址計算(executio

16、n/effective address)。u a. 訪存指令(access instruction)u b. ALU指令(ALU instruction )u c. 無條件轉(zhuǎn)移/條件轉(zhuǎn)移指令(jump instruction / branch)n 4. 存儲器訪問/完成轉(zhuǎn)移(memory access/branch completion)u a. 訪存指令(access instruction)u b. 轉(zhuǎn)移指令(branch instruction)n 5. 寫回(write-back）。llChapter 4計算題 簡答題l 流水線（pipeline）是指在程序執(zhí)行時多條指令重疊進(jìn)行的操作

17、的一種準(zhǔn)并行處理實現(xiàn)技術(shù)l 流水線的特點：n 一條流水線由多個流水級組成；n 每個流水級有專門的功能部件對指令進(jìn)行某種加工；n 各流水級所需時間是一樣的（同時）；n 流水線工作階段可分為建立、滿載和排空三個階段；n 單位時間內(nèi)流出流水線的指令數(shù)即吞吐率。l 流水線設(shè)計最難的任務(wù)是確定每個流水級功能部件處理事件的時間l 每條指令平均執(zhí)行時間=l 流水線深度是指流水線中總的流水級的數(shù)目。在這種條件下，流水線計算機(jī)的加速比(speedup)就等于流水級的深度。l 流水線只能減少每條指令的平均執(zhí)行時間，一條指令的實際執(zhí)行時間要經(jīng)過所有流水級，其實際執(zhí)行時間有可能比未流水時還要長l 流水線有多種分類方法

18、n 按處理的級別分類u 操作部件級u 指令級u 處理器級n 按完成的功能分類u 單功能流水線u 多功能流水線n 按連接的方式分類u 靜態(tài)流水線u 動態(tài)流水線靜態(tài)流水線是指在同一個時間內(nèi)，多功能結(jié)構(gòu)只能按一種功能的連接方式工作，這對于大量數(shù)據(jù)進(jìn)行相同處理來說，具有很好的效果。但是遇到不同功能交替處理時，流水線就失去了其優(yōu)點，運算速度與順序處理方式?jīng)]有什么區(qū)別。 動態(tài)流水線是指在同一個時間內(nèi)，可以有多種功能的連接方式同時工作。如圖4-5中多個功能段，其中一些功能段正在實現(xiàn)乘法運算，同時其它功能段還可以進(jìn)行浮點加減運算，這種方式的流水工作效率最高，但是控制也變得更復(fù)雜。n 按處理的數(shù)據(jù)類型分類u 標(biāo)

19、量流水線u 向量流水線n 從流水線結(jié)構(gòu)上分類u 線性流水線u 非線性流水線l 假定RISC流水線計算機(jī)，時鐘周期是10ns，ALU操作和條件轉(zhuǎn)移要4個時鐘周期，而存儲器訪問操作要5個時鐘周期。這三種指令操作的使用概率相應(yīng)是40%，20%和40%。假設(shè)由于時鐘上升和建立，流水線機(jī)器周期要增加1ns的開銷。忽略任何其它延時影響，問5級流水線機(jī)器可以獲得的加速比是多少？解：非流水線計算機(jī)平均每條指令執(zhí)行時間為： Timeup×CPI10×(40%+20%)×4+40%×510×4.4=44ns 流水線計算機(jī)每條指令平均執(zhí)行時間為： Timep(10+

20、1)×5/511ns 則流水線計算機(jī)的Speedup為：Speedup=44/11=4倍l 假定機(jī)器指令執(zhí)行需要5個功能單元，這5個單元的操作所需時間分別是10，8，10，10，7ns。假定流水要增加1ns的開銷。求出流水相對于單周期指令機(jī)器的加速比 解：非流水計算機(jī)執(zhí)行所有指令都用單個時鐘，它的每條指令平均時間直接是一個時鐘周期。時鐘周期等于每一步的執(zhí)行時間之和，即 timeup=10+8+10+10+7=45ns 在流水線機(jī)器上的時鐘周期必須是流水線中執(zhí)行時間最長的流水部件的執(zhí)行時間，再加上1ns的開銷，總共是 timep=10+1=11ns Speedup=45/11=4.1(

21、倍) 一般認(rèn)為，流水線改善了CPI，也可以把它看作是提高了時鐘頻率。l 流水線競爭有三種n 結(jié)構(gòu)競爭（structure hazard）(資源競爭)：由資源缺乏引起n 數(shù)據(jù)競爭（data hazard）：由指令間數(shù)據(jù)相關(guān)而引起n 控制競爭（control hazard）：由程序指針PC值的改變而引起l 計算存儲器結(jié)構(gòu)競爭的代價。假定程序中存儲器數(shù)據(jù)訪問有40%。計算機(jī)流水線忽略結(jié)構(gòu)沖突的理想CPI等于1。又假設(shè)有結(jié)構(gòu)競爭的計算機(jī)時鐘頻率是沒有結(jié)構(gòu)競爭時的1.05倍。不考慮其它性能損失。流水線有結(jié)構(gòu)競爭和無結(jié)構(gòu)競爭哪一個執(zhí)行速度快？快多少？解： 有許多方法可以解這個問題，最簡單的方法是計算平均指

22、令的運行時間 TaverI×CPI× 兩機(jī)器和時鐘關(guān)系 f有結(jié)構(gòu)競爭1.05×f理想 有結(jié)構(gòu)競爭理想/1.05無結(jié)構(gòu)競爭，即沒有插入Stall，由于理想CPI1，故平均指令執(zhí)行時間 Ta無結(jié)構(gòu)競爭I×CPI×理想I×理想有結(jié)構(gòu)競爭平均指令執(zhí)行時間為 Ta有結(jié)構(gòu)競爭I×CPI×(1+0.4×1)I×理想/1.051.3I×理想很明顯，無結(jié)構(gòu)競爭的計算機(jī)運行速度要快，且要快1.3倍。l 允許結(jié)構(gòu)競爭存在n 減少成本n 降低單元電路的延時時間n 減少電路的復(fù)雜程度l 現(xiàn)代許多RISC計算機(jī)，

23、浮點操作都沒有采用完全流水方式。假設(shè)在5級RISC流水處理器中，浮點乘法操作沒用流水方式實現(xiàn)，有4個時鐘的等待時間。已知浮點乘法指令使用頻率為14%，且假設(shè)浮點乘法指令在程序中完全均勻分布，請分析結(jié)構(gòu)競爭對性能影響的程度。分兩種極端情況分析： 1. 浮點乘法操作均勻分布，這是最佳情況，此時每7條指令有一個浮點乘法操作，大于5，故所有浮點乘法都可以和其它指令重疊執(zhí)行，這種情況始終沒有關(guān)于浮點乘法器的結(jié)構(gòu)競爭，也不需插入Stall，性能沒有損失。 2. 浮點乘法操作成串出現(xiàn)，且中間沒有其它指令間隔，這是最差的情況。這時局部相當(dāng)于每條指令都是浮點乘法操作(即100%)，結(jié)構(gòu)競爭最嚴(yán)重。在這種情況下，

24、14%的浮點乘法都要延時4個時鐘才能進(jìn)入浮點乘法執(zhí)行部件。假定理想CPI1，此時的CPI為 CPI14×14%1.6l 旁路技術(shù)l 插入Stalll 假定30%的指令是Load指令，其中一半情況是緊跟Load后面的指令依賴Load指令的結(jié)果。如果出現(xiàn)數(shù)據(jù)競爭要停頓一個流水節(jié)拍。那么相對于理想流水線機(jī)器（CPI=1），實際流水線性能損失多少？忽略其它流水停頓。解： 當(dāng)有數(shù)據(jù)競爭時，Load后面的指令其CPI=2，這種情況Load指令的一半，即15%，而其余指令的CPI值仍為1，沒有變化，故實際機(jī)器的CPI為 CPI(100%15%)×115%×21.15由于指令總數(shù)

25、和時鐘周期均未變化，故實際機(jī)器性能損失 (1.151)115%即與理想機(jī)器相比性能損失了15%。l 靜態(tài)調(diào)度（避免插入Stall的性能損失）l 假定由Load指令引起的數(shù)據(jù)競爭有一個流水節(jié)拍的停頓，采用指令調(diào)度方法生成代碼，避免下列語句序列出現(xiàn)流水等待 abc defl 指令從ID級流入EX級，一般稱指令發(fā)射(instruction issue)。一條指令已建立了這一過程，稱為已發(fā)射(issued)l 把碰到轉(zhuǎn)移指令到轉(zhuǎn)移行為明確之間的時間間隔稱為轉(zhuǎn)移的延時時間，后繼指令組成的轉(zhuǎn)移延時時間稱為轉(zhuǎn)移延時槽l 對延時槽的處理有三種編譯調(diào)度方法n 取自轉(zhuǎn)移指令前。這是最佳選擇。n 取自目標(biāo)指令。一般用于轉(zhuǎn)移成功概率高的地方，如循環(huán)語句。n 取自轉(zhuǎn)移指令后。一般用于