天津師范大學(xué)——系統(tǒng)結(jié)構(gòu)期末復(fù)習(xí)(共15頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第一章1.計算機系統(tǒng)結(jié)構(gòu)的定義：計算機系統(tǒng)結(jié)構(gòu)主要研究軟硬件功能分配和對軟硬件界面的確定3.透明性概念：本來存在的事物或?qū)傩?，從某種角度看似乎不存在4.計算機系統(tǒng)的多層次模型：第6級 專用應(yīng)用語言機器 特定應(yīng)用用戶（使用特定應(yīng)用語言）（經(jīng)應(yīng)用程序翻譯成高級語言）第5級 通用高級語言機器 高級語言程序員（使用通用高級語言）（經(jīng)編譯程序翻譯成匯編語言）第4級 匯編語言機器 匯編語言程序員（使用匯編語言）（經(jīng)匯編程序翻譯成機器語言、操作系統(tǒng)原語）第3級 操作系統(tǒng)語言機器 操作系統(tǒng)用戶（使用操作系統(tǒng)原語）（經(jīng)原語解釋子程序翻譯成機器語言）第2級 傳統(tǒng)機器語言機器 傳統(tǒng)機器程序

2、員（使用二進制機器語言）（由微程序解釋成微指令序列）第1級 微指令語言機器 微指令程序員（使用微指令語言）（由硬件譯碼器解釋成控制信號序列）第0級 硬聯(lián)邏輯 硬件設(shè)計員第0級由硬件實現(xiàn)，第1級由微程序?qū)崿F(xiàn)，第2級至第6級由軟件實現(xiàn)，由軟件實現(xiàn)的機器稱為：虛擬機從學(xué)科領(lǐng)域來劃分：第0和第1級屬于計算機組織與結(jié)構(gòu)，第3至第5級是系統(tǒng)軟件，第6級是應(yīng)用軟件。它們之間仍有交叉。第0級要求一定的數(shù)字邏輯基礎(chǔ)；第2級涉及匯編語言程序設(shè)計的內(nèi)容；第3級與計算機系統(tǒng)結(jié)構(gòu)密切相關(guān)。在特殊的計算機系統(tǒng)中，有些級別可能不存在。5. 計算機運算速度評價的主要方法：1）時鐘頻率（2）指令執(zhí)行速度MIPS及KIPS、GI

3、PS、TIPS 書P15-16（3）等效指令速度。（CPI (Cycles Per Instruction) 為每條指令所需的平均時鐘周期數(shù)，IPC為每個時鐘周期平均執(zhí)行的指令條數(shù)。）例子：如果浮點開平方操作FPSQR的比例為2%，它的CPI為100 ，其他浮點操作的比例為23% ，它的CPI4.0，其余指令的CPI1.33 ，計算該處理機的 等效CPI。如果FPSQR操作的CPI也為4.0，重新計算等效CPI。解： 等效CPI1100 2 4 231.33 753.92 等效CPI24 251.33 752.00 由于改進了僅占2 的FPSQR操作的CPI，使等效速度提高了近一倍。6.Amd

4、ahl定律的內(nèi)容及計算（公式： ）書P9-10內(nèi)容：系統(tǒng)中某一部件由于采用某種更快的執(zhí)行方式后整個系統(tǒng)性能的提高與這種執(zhí)行方式的使用頻率或占總執(zhí)行時間的比例有關(guān)。其中：Sn全局加速比；To原執(zhí)行時間（old）；Tn新執(zhí)行時間（new）；Se被改進部分的局部加速比；Fe被改進部分原執(zhí)行時間占原來總時間的百分比。8.CPU性能公式：CPU時間=（ICCPI）/頻率 書P10-119.存儲器訪問的局部性原理實質(zhì)：根據(jù)程序運行的最近情況，可以較為精確的預(yù)測出最近的將來將要訪問哪些指令和數(shù)據(jù)。(1) 時間局部性：最近訪問過的代碼在很短的時間內(nèi)有可能被再次訪問；主要對應(yīng)于循環(huán)語句；（2）空間局部性：與剛被

5、訪問過的指令或數(shù)據(jù)相鄰的指令或數(shù)據(jù)有可能馬上被訪問；主要對應(yīng)于順序執(zhí)行的語句。 訪問的局部性原理是構(gòu)成層次化存儲系統(tǒng)的理論基礎(chǔ)。10. 計算機系統(tǒng)結(jié)構(gòu)的通用分類：（1） 佛林（Flynn）分類法：按照指令流和數(shù)據(jù)流的多倍性特征對計算機系統(tǒng)進行分類。具體內(nèi)容：書7頁有圖 （1）單指令流單數(shù)據(jù)流SISD（2）單指令流多數(shù)據(jù)流SIMD（3）多指令流單數(shù)據(jù)流SIMD （4）多指令流多數(shù)據(jù)流SIMD（2） 馮澤云分類法：用最大并行度來對計算機系統(tǒng)進行分類。（3） Handler分類法練習(xí)題一、題4 （P32）二、題12 （P33）答案： 一4：(N/M)3Ks 3：(N/M)2Ks 2：(N/M)Ks

6、1：Ks二、Amdahl定律公式，Sn=20/(20-19Fe)用三點作圖法作出關(guān)系曲線第二章4.操作碼優(yōu)化表示（哈弗曼及擴展編碼方法）：計算 書P91-956.CISC與RISC的概念與區(qū)別：CISC（復(fù)雜指令系統(tǒng)計算機）：增強指令功能，設(shè)置功能復(fù)雜的指令；面向目標(biāo)代碼、面向高級語言、面向操作系統(tǒng)；用一條指令代替一串指令RISC（精簡指令系統(tǒng)計算機）：簡化指令功能，只保留功能簡單的指令；較復(fù)雜的功能用子程序來實現(xiàn)CISC與RISC區(qū)別：CISCRISC指令系統(tǒng)復(fù)雜龐大簡單精簡指令數(shù)大于200小于100指令格式一般大于4一般小于4尋址方式一般大于4一般小于4指令字長不固定固定32位訪存指令不限

7、制Load Store質(zhì)量使用頻率相差很大相差不大指令執(zhí)行時間相差很大一個機器周期之內(nèi)優(yōu)化編譯實現(xiàn)難容易代碼程度較短較長控制邏輯實現(xiàn)微程序硬連接7.RISC的特點：(1) 簡單而統(tǒng)一格式的指令譯碼。(2) 大部分指令可以單周期執(zhí)行完成。(3) 只有LOAD和STORE指令可以訪問存儲器。(4) 簡單的尋址方式。 (5) 采用延遲轉(zhuǎn)移技術(shù) 。(6) 采用LOAD延遲技術(shù)。9.RISC的關(guān)鍵技術(shù)：延時轉(zhuǎn)移技術(shù)（重點看一下）、指令取消技術(shù)、重疊寄存器窗口技術(shù)、指令流調(diào)整技術(shù)、以硬件為主固件為輔10.減少指令平均執(zhí)行周期CPI是RISC 思想的精華練習(xí)題：1、假定要將某一執(zhí)行部件的執(zhí)行速度提高到原來的

8、10倍，改進后被改進部件執(zhí)行時間占系統(tǒng)總運行時間的50。問： (1)改進后獲得的加速比時多少？(2)改進前該部件的之下時間占總之下時間的百分比時多少？2、有一臺計算機系統(tǒng)可以按功能分為四級，自下向上表示為、。每一級的功能各不相同，每一級的指 令都比其下一級的指令在功能上強M倍，即第I級的一條指令能夠完成第I1級的M 條指令的計算量?，F(xiàn)若需第I 級的N條指令解釋第I1級的一條指令，而有一段第級的程序需要運行Ks，問在第、各級一段功能等效 的程序各需多長時間？3、某模型機共有9條指令，使用頻度分別為：0.30 、0.24 、0.06 、0.07 、0.07 、0.02 、0.03 、0.20 、0

9、.01 。該機 具有若干通用寄存器，主存為16位字長，字節(jié)編址，采用按整數(shù)邊界存取，任何指令必須在一個主存周期中取得， 短指令為寄存器寄存器型，長指令為寄存器主存型，主存地址應(yīng)當(dāng)能夠變址尋址。 (1)、設(shè)計優(yōu)化實用的操作碼編碼；(2)、最多可以使用多少個通用寄存器(3)、畫出兩種指令格式，指出主存變址尋 址的最大相對位移量為多少？第三章 看書1.存儲器的主要性能指標(biāo)：速度 容量 價格 2.存儲系統(tǒng)（或存儲體系、存儲層次）的定義兩個或兩個以上速度、容量和價格各不相同的存儲器用硬件、軟件、或軟件與硬件相結(jié)合的方法連接起來成為一個 系統(tǒng)。這個系統(tǒng)對應(yīng)用程序員透明，并且，從應(yīng)用程序員看，它是一個存儲器

10、，這個存儲器的速度接近速度最快的那個存儲器，存儲容量與容量最大的那個存儲器相等，單位容量的價格接近最便宜的那個存儲器。3.命中率與存儲系統(tǒng)等效訪問速度和效率的計算 書133頁4.虛擬存儲器是由主存儲器和磁盤存儲器共同組成。4.Cache存儲系統(tǒng)：由Cache和主存儲器構(gòu)成5.虛擬存儲器的三種地址映像與變換方式：頁式虛擬存儲器、段式虛擬存儲器、段頁式虛擬存儲器6.cache地址映象：全相聯(lián)映象、直接相聯(lián)映象、組相聯(lián)映象、位選擇組相聯(lián)映象、段相聯(lián)映象7. 堆棧型替換算法的定義與堆棧模擬圖的應(yīng)用：定義：對任意一個程序的頁地址流作兩次主存頁面數(shù)分配，分別分配m個主存頁面和n個主存頁面，并且有mn。如果

11、在任何時刻t，主存頁面數(shù)集合Bt都滿足關(guān)系： Bt（m） Bt（n） 則這類算法稱為堆棧型替換算法。堆棧模擬圖的應(yīng)用（計算題）例題：一個虛擬存儲系統(tǒng)，采用最久沒有使用算法，實存共5頁，為2道程序分享，頁地址流分別如下P1= 1 2 3 4 1 3 2 1P2= 1 2 3 4 2 2 3 3試作2個實存分配方案，分別使2道程序滿足(1)命中率相同；(2)命中次數(shù)之和最大。結(jié)論如下(1)命中率相同的方案是n1=3而n2=2；(2)命中次數(shù)之和最大的方案是n1= 4而n2= 1。8.Cache存儲系統(tǒng)工作：基于程序局部性訪問原理，是對主存信息的拷貝9.組相聯(lián)地址映像及其變換（180頁圖）10.ca

12、che系統(tǒng)的加速比：書P9310.Cache與主存不一致性產(chǎn)生的原因及更新方法：造成Cache與主存的不一致的原因：(1) 由于CPU寫Cache，沒有立即寫主存(2) 由于IO處理機或IO設(shè)備寫主存Cache的更新算法：(1) 寫直達法，又稱寫通過法，WT（Writethrough）：CPU在執(zhí)行寫操作時，把數(shù)據(jù)同時寫入Cache和主存。(2) 寫回法，又稱為抵觸修改法，WB（WriteBack）：CPU的數(shù)據(jù)只寫入Cache，不寫入主存。僅當(dāng)替換時， 才把修改過的Cache塊寫回到主存。習(xí)題：Cache存儲系統(tǒng)中，Cache的訪問周期為10ns，主存儲器的訪問周期為60ns,每個數(shù)據(jù)在Ca

13、che中平均重復(fù)使用4次。當(dāng)塊的大小為1個字時，存儲系統(tǒng)的訪問效率只有0.5，現(xiàn)在要提高增加塊的大小，使存儲系統(tǒng)的訪問效率達到0.94。1、當(dāng)存儲系統(tǒng)的訪問效率為0.5時，計算命中率和等效訪問周期；2、為了使存儲系統(tǒng)的訪問效率達到0.94，命中率和等效訪問周期應(yīng)當(dāng)為多少？3、為了使存儲系統(tǒng)的訪問效率從0.5提高到0.94，塊的大小至少要增加到幾個字？第四章1.IO系統(tǒng)的特點及其相應(yīng)解決方法輸入輸出系統(tǒng)的特點集中反映在異步性，實時性，和與設(shè)備無關(guān)性三項基本要求上，它們對輸入輸出系統(tǒng)的組織產(chǎn)生決定性影響。實時性反映了不同種類設(shè)備對于CPU響應(yīng)時間的區(qū)別，采用層次結(jié)構(gòu)的方法來解決 設(shè)備無關(guān)性表明了標(biāo)

14、準(zhǔn)接口非標(biāo)準(zhǔn)設(shè)備驅(qū)動軟件的實現(xiàn)途徑，采用分類處理的方法來解決。 異步性反映了設(shè)備相對于CPU的獨立性，采用自治控制的方法來解決。2.輸入輸出系統(tǒng)的組織方式1. 自治控制：輸入輸出系統(tǒng)是獨立于CPU之外的自治系統(tǒng)，處理機與外圍設(shè)備之間要有恰當(dāng)?shù)姆止ぁ?. 層次結(jié)構(gòu)：最內(nèi)層是輸入輸出處理機、輸入輸出通道等中間層是標(biāo)準(zhǔn)接口。標(biāo)準(zhǔn)接口通過設(shè)備控制器與輸入輸出設(shè)備連接。3. 分類組織：面向字符的設(shè)備，如字符終端、打字機等，面向數(shù)據(jù)塊的設(shè)備，如磁盤、磁帶、光盤等。2.3種基本I/O方式：程序控制輸入輸出方式、中斷輸入輸出方式、直接存儲器訪問方式2. 輸入輸出系統(tǒng)的特點：輸入輸出系統(tǒng)是處理機與外界數(shù)據(jù)交換的

15、通道。輸入輸出系統(tǒng)最典型地反映著硬件與軟件的相互結(jié)合。3. 中斷的定義：當(dāng)出現(xiàn)來自系統(tǒng)外部，機器內(nèi)部，甚至處理機本身的任何例外的，或者雖然是事先安排的，但出現(xiàn)在現(xiàn)行程序的什么地方是事先不知道的事件時，CPU暫停執(zhí)行現(xiàn)行程序，轉(zhuǎn)去處理這些事件，等處理完成后再返回來繼續(xù)執(zhí)行原先的程序。4. 中斷源：引起中斷的各種事件 安排中斷優(yōu)先順序主要由下列因素來決定：中斷源的急迫性。設(shè)備的工作速度。數(shù)據(jù)恢復(fù)的難易程度。要求處理機 提供的服務(wù)量。 要求：響應(yīng)速度快，靈活性好。 通過軟件設(shè)置中斷屏蔽碼改變中斷服務(wù)順序。4.中斷處理的流程表示通常用硬件實現(xiàn) 現(xiàn)行指令結(jié)束，且沒有更緊急的服務(wù)請求 ；關(guān)CPU中斷 ；保

16、存斷點，主要保存PC中的內(nèi)容表示可以用硬件實現(xiàn)，也可以用軟件實現(xiàn) 撤消中斷源的中斷請求 ；保存硬件現(xiàn)場，主要是PSW及SP等 ；識別中斷源 ；改變設(shè)備的屏蔽狀態(tài)表示通常用硬件實現(xiàn) 進入中斷服務(wù)程序入口表示可以用硬件實現(xiàn)，也可以用軟件實現(xiàn) 保存軟件現(xiàn)場，在中斷程序中使用的通用寄存器等表示通常用軟件實現(xiàn) 開CPU中斷，可以響應(yīng)更高級別的中斷請求 ；中斷服務(wù)，執(zhí)行中斷服務(wù)程序 ；關(guān)CPU中斷表示可以用硬件實現(xiàn)，也可以用軟件實現(xiàn) 恢復(fù)軟件現(xiàn)場 ；恢復(fù)屏蔽狀態(tài) ；恢復(fù)硬件現(xiàn)場 ；開CPU中斷 表示通常用軟件實現(xiàn) 返回到中斷點必須用硬件實現(xiàn)的有：保存中斷點和進 入中斷服務(wù)程序入口。必須用軟件實現(xiàn)的有：中斷

17、服務(wù)和返回到中斷點。5. 中斷響應(yīng)時間：從中斷源向處理機發(fā)出中斷服務(wù)請求開始，到處理機開始執(zhí)行這個中斷源的中斷服務(wù)程序時為止5. 中斷屏蔽的兩種方法：方法一：每級中斷源設(shè)置一個中斷屏蔽位。方法二：改變處理機優(yōu)先級使用中斷屏蔽位實現(xiàn)中斷屏蔽的計算：有四個中斷源D1、D2、D3和D4，它們的中斷優(yōu)先級從高到低分別是1級、2級、3級和4級。這些中斷源的正常中斷屏蔽碼和改變后的中斷屏蔽碼見下表。每個中斷源一位，共4位屏蔽碼。1表示不允許中斷，0表示允許中斷中斷源名稱 中斷優(yōu)先級 正常中斷屏蔽碼D1 D2 D3 D4 改變后的中斷屏蔽碼D1 D2 D3 D4D1 1 1111 1000D2 2 0111

18、 1100D33 0011 1110D4400011111解：如果4個中斷源都使用正常的中斷屏蔽碼，處理機的中斷服務(wù)順序?qū)?yán)格按照中斷源的中斷優(yōu)先級進行。如果改變中斷屏蔽碼，當(dāng)D1、D2、D3和D4這4個中斷源同時請求中斷服務(wù)時，處理機實際為各個中斷源服務(wù)的先后次序就會改變。處理機響應(yīng)的順序是D1、D2、D3、D4實際服務(wù)的順序是D4、D3、D2、D1例題2：某處理機共有4個中斷源D1、D2、D3和D4，它們的硬件中斷優(yōu)先級從低到高分別為1級、2級、3級和4級。處理機本身的優(yōu)先級最低，為0級。在中斷源D1、D2、D3、D4的中斷向量中，程序員為它們設(shè)置的優(yōu)先級分別為4級、3級、2級、1級。解：

19、在處理機狀態(tài)字中設(shè)置3個中斷屏蔽位。000為處理機本身的優(yōu)先級，001100分別表示4個中斷源的中斷優(yōu)先級。當(dāng)4個中斷源同時請求中斷服務(wù)時，8.通道的種類及其工作方式字節(jié)多路通道 為多臺低中速的外圍設(shè)備服務(wù)，有多個子通道，每個子通道連接一個控制器選擇通道 為高速外圍設(shè)備服務(wù)，只有一個以成組方式工作的子通道 數(shù)組多路通道 字節(jié)多路通道和選擇通道的結(jié)合。 每次為一臺高速設(shè)備傳送一個數(shù)據(jù)，并輪流為多臺外圍設(shè)備服務(wù)。 從磁盤存儲器讀出文件的的過程分為三步：定位、找扇區(qū)、讀出數(shù)據(jù)。數(shù)組多路通道的實際工作方式是：在為一臺高速設(shè)備傳送數(shù)據(jù)的同時，有多臺高速設(shè)備可以在定位或者在找扇區(qū)。與選擇通道相比，數(shù)組多路

20、通道的數(shù)據(jù)傳輸率和通道的硬件利用都很高，控制硬件的復(fù)雜度也高。9.通道傳輸時間與流量的計算公式字節(jié)多路通道的數(shù)據(jù)傳送過程:一個字節(jié)多路通道連接 P臺設(shè)備，每臺設(shè)備都傳送 個字節(jié)選擇通道的數(shù)據(jù)傳送過程：選擇通道連接 P 臺設(shè)備，每臺設(shè)備都傳送 個字節(jié)數(shù)組多路通道的數(shù)據(jù)傳送過程:數(shù)組多路通道連接P 臺設(shè)備，每臺設(shè)備都傳送 個字節(jié)10. 通道流量分析：書P243 練習(xí)題：1、某處理機有4個中斷源，分別為D1、D2、D3、D4。要求處理機響應(yīng)中斷源的中斷請求次序從高到低依次為D1、D2、D3、D4，而處理機實際為各個中斷源服務(wù)的先后次序為D3、D2、D1、D4。每個中斷源有四位中斷屏蔽碼，其中“0”表

21、示開放中斷，“1”表示該中斷被屏蔽。（1） 試設(shè)計各中斷源的中斷優(yōu)先級和中斷屏蔽碼； （2） 如果處理機在運行主程序時，同時有D1、D2兩個中斷源請求中斷服務(wù)，而在運行中斷源D2的中斷服務(wù)程序的過程中，中斷源D3、D4又同時請求中斷服務(wù)，試畫出處理機響應(yīng)各個中斷源的中斷服務(wù)請求和實際運行中斷服務(wù)程序過程的示意圖。 2 、如果某通道在數(shù)據(jù)傳送過程中，選擇設(shè)備需要9.8us，傳送一個字節(jié)需要0.2us，某個低速設(shè)備每隔500us發(fā)出一個字節(jié)傳送請求，問該通道至多可接幾臺這種低速設(shè)備？對于如下A-F六種高速設(shè)備，一次通訊傳送的字節(jié)數(shù)不少于1024 個字節(jié)，問哪些設(shè)備可以掛接在此通道上，那些不能？ 3

22、 、書p251 第五章1.指令重疊的執(zhí)行方式：1.順序執(zhí)行方式2.一次重疊執(zhí)行方式3.二次重疊執(zhí)行方式2.采用先行控制方式的處理機結(jié)構(gòu)3.各緩沖棧的作用1.先行指令緩沖棧：處于主存儲器與指令分析器之間，用它來平滑主存儲器取指令和指令分析器使用指令之間的速度差異2.先行操作棧： 處于指令分析器和運算控制器之間，使指令分析器和運算器能夠各自獨立工作。采用先進先出方式工作，由指令寄存器堆和控制邏輯組成。3.先行讀數(shù)棧 處于主存儲器與運算器之間，平滑運算器與主存儲器的工作。每個緩沖寄存器由地址寄存器、操作數(shù)寄存器和標(biāo)志三部分組成。也可以把地址寄存器和操作數(shù)寄存器合為一個。 當(dāng)收到從指令分析器中送來的有

23、效地址時，就向主存申請讀操作數(shù)。讀出的操作數(shù)存放在操作數(shù)寄存器中或覆蓋掉地址寄存器中的地址。4.后行寫數(shù)棧 每個后行緩沖寄存器由地址寄存器、數(shù)據(jù)寄存器和標(biāo)志三部分組成。指令分析器遇到向主存寫結(jié)果的指令時，把形成的有效地址送入后行寫數(shù)棧的地址寄存器中，并用該地址 寄存器的編號替換指令的目的地址部分，形成RR*指令送入先行操作棧。當(dāng)運算器執(zhí)行這條RR*型寫數(shù)指令時，只要把寫到主存的數(shù)據(jù)送到后行寫數(shù)棧的數(shù)據(jù)寄存器中即可。3. 先行控制技術(shù)的關(guān)鍵是緩沖技術(shù)和預(yù)處理技術(shù)4. 線性流水線：每一個流水段都流過一次，而且僅流過一次5. 非線性流水線：某些流水段之間有反饋回路或前饋回路。4.流水線的三個主要性能

24、指標(biāo)的定義及計算 書P285-294主要指標(biāo)：吞吐率、加速比和效率5. 非線性流水線的無沖突調(diào)度算法 書P294-300線性流水線能用流水線連接圖唯一表示，對于非線形流水線，連接圖不能唯一表示工作流程，需要引入流水線預(yù)約表啟動距離：連續(xù)輸入兩個任務(wù)之間的時間間隔例題：一條4功能段的非線性流水線，每個功能段的延遲時間都相等，它的預(yù)約表如下：(1)寫出流水線的禁止向量和初始沖突向量。(2)畫出調(diào)度流水線的狀態(tài)圖。(3)求最小啟動循環(huán)和最小平均啟動距離。(4)求平均啟動距離最小的恒定循環(huán)。解：(1)禁止向量為： (2，4，6)初始沖突向量：S = (2)構(gòu)造狀態(tài)圖S邏輯右移2、4、6位時，不作任何處

25、理，邏輯右移1、3、5和大于等于7時：S右移1位之后： ，S右移3位之后： ，S右移5位之后： ，S右移7位或大于7位后還原到它本身。右移5位之后：，右移3位之后：，右移5位之后：。簡單循環(huán)：狀態(tài)圖中各種沖突向量只經(jīng)過一次的啟動循環(huán)。(3)最小的啟動循環(huán)為 （1，7）和（3，5）,平均啟動距離為4。(4) 啟動距離最小的恒定循環(huán)為（5）6.數(shù)據(jù)相關(guān)與控制相關(guān)的概念數(shù)據(jù)相關(guān)：在執(zhí)行本條指令的過程中，如果用到的指令、操作數(shù)、變址量等是前面指令的執(zhí)行結(jié)果，這種相關(guān)稱為數(shù)據(jù)相關(guān)?？刂葡嚓P(guān)：由條件分支指令、轉(zhuǎn)子程序指令、中斷等引起的相關(guān)。7.超標(biāo)量處理機的概念有兩條或兩條以上能同時工作的指令流水線，超標(biāo)

26、量處理機采用的是空間并行性。（先行指令窗口：能夠從指令Cache中預(yù)取多條指令，能夠?qū)Υ翱趦?nèi)的指令進行數(shù)據(jù)相關(guān)性分析和功能部件沖突檢測，保存暫時不能進入操作部件的指令。先行指令窗口的作用類似于先行指令緩沖棧，典型大小為28條指令。超流水線處理機：在一個周期內(nèi)分時發(fā)射多條指令的處理機，超流水線處理機采用的是時間并行性。）超標(biāo)量超流水線處理機：一個時鐘周期發(fā)射m次，每次發(fā)射n條指令三種處理機的性能關(guān)系：超標(biāo)量處理機的相對性能最高，其次超標(biāo)量超流水處理機，超流水線處理機的相對性能最低9.順序與亂序的概念 多流水線的調(diào)度主要有三種方法：順序發(fā)射順序完成、順序發(fā)射亂序完成、亂序發(fā)射亂序完成 指令發(fā)射順序

27、是按照程序中指令排列順序進行的稱為順序發(fā)射。指令完成順序是按照程序中指令排列順序進行的稱為順序完成習(xí)題：1、 一個15000條指令的程序在一臺時鐘頻率為25MHZ的線性流水線處理機上運行，假設(shè)該流水線分為相等的5段，并且每個時鐘周期發(fā)射一條指令，忽略由于轉(zhuǎn)移指令和數(shù)據(jù)相關(guān)造成的損失。（1） 、使用該流水線執(zhí)行這個程序，并用流過延遲時間與其相等的一個等效非流水線處理機執(zhí)行同一程序。兩者相比較，加速比是多少？（2）、計算該流水線的效率和吞吐率。解：(1)等效非流水線處理機執(zhí)行一條指令需要5個時鐘周期，依照加速比的定義：S=n*k/(k+n-1)=15000*5/(5+15000-1)=75000/

28、15004=4.9986(2)流水線的效率：E=n*k/(k*(k+n-1)=15000/15004=0.9997吞吐率：TP=n*f/(k+n-1)=15000*25M/(k+n-1)=24.99MIPS2、一個5段流水線處理機的預(yù)約表如下：1、列出禁止向量和沖突向量2、畫出狀態(tài)轉(zhuǎn)移圖3、列出所有簡單循環(huán)，指出最小啟動循環(huán)及其啟動距離4、計算該流水線的最大吞吐率5、指出最小恒定循環(huán)，計算相對應(yīng)的吞吐率解：(1)禁止向量（3，4，5），沖突向量（11100）(2)狀態(tài)轉(zhuǎn)移圖(3)簡單循環(huán)(1,1,6),(2.6),(6),(1,6),最小啟動循環(huán)（1，1，6），啟動距離2.67(4)最大吞吐率

29、:設(shè)該流水線時鐘周期為t，則Tp=3/8t(5)最小恒定循環(huán)為6，相對應(yīng)的吞吐率Tp=1/6t第七章1.互連網(wǎng)絡(luò)主要特性（了解）特性：(1)網(wǎng)絡(luò)規(guī)模：網(wǎng)絡(luò)中結(jié)點的個數(shù) (2)結(jié)點度：與結(jié)點相連接的邊數(shù)稱為結(jié)點度，進入結(jié)點的邊數(shù)叫入度， 從結(jié)點出來的邊數(shù)則叫出度 (3)距離：兩個結(jié)點之間相連的最少邊數(shù) (4) 網(wǎng)絡(luò)直徑：網(wǎng)絡(luò)中任意兩個結(jié)點間距離的最大值。用結(jié)點間的連接邊數(shù)2.互聯(lián)網(wǎng)絡(luò)傳輸?shù)男阅軈?shù)：(1)頻帶寬度 (Bandwidth)：傳輸信息的最大速率(2)傳輸時間 (Transmission time)：等于消息長度除以頻寬。(3)飛行時間 (Time of flight)：第一位信息到達

30、接收方所花費的時間。(4)傳輸時延 (Transport latency)：等于飛行時間與傳輸時間之和。(5)發(fā)送方開銷 (Sender overhead)：處理器把消息放到互連網(wǎng)絡(luò)的時間。(6)接收方開銷 (Receiver overhead)：處理器把消息從網(wǎng)絡(luò)取出來的時間。3.互連網(wǎng)絡(luò)的種類：1 靜態(tài)互連網(wǎng)絡(luò)2 循環(huán)互連網(wǎng)絡(luò)3 多級互連網(wǎng)絡(luò)4 全排列互連網(wǎng)絡(luò)5 全交叉開關(guān)網(wǎng)絡(luò)4.6種基本互連函數(shù)的定義與計算（計算）書P395例6.2：假設(shè)16個處理機的編號分別為0、1、15，采用單級互連網(wǎng)絡(luò)?；ミB函數(shù)分別為：(1)Cube3(2)PM2+3(3)PM2-0(4)Shuffle(5)But

31、terfly (6)Reversal第12號處理機分別與哪一個處理機相連？解：(12)10下= (1100)2下1100最高位取反得0100，4號處理機(12 + 8) MOD 16 = 4，4號處理機12 1 = 11，11號處理機1100循環(huán)左移1位得到1001, 9號處理機1100的最高最低位交換0101, 5號處理機1100的位序反過來為0011, 3號處理機13.多級立方體網(wǎng)的構(gòu)成及工作原理 習(xí)題1：有編號為031共32個處理機，分別計算下列互連函數(shù)（E：交換函數(shù)；S：混洗函數(shù)；B：蝶式函數(shù)；PM2I：移數(shù)函數(shù)；自變量為10進制處理機編號）。第八章并行性的兩種類型和三種技術(shù)途徑兩種并

32、行性概念：(1)同時性并行Simultaneity：兩個或兩個以上事件 在同一時刻發(fā)生。(2)并發(fā)性并行Concurrency：兩個或兩個以上事件在 同一時間間隔內(nèi)發(fā)生。三條技術(shù)途徑：(1)資源重復(fù)：重復(fù)設(shè)置多個部件來提高速度。(2)時間重疊：流水線(3)資源共享：分時系統(tǒng)，分布式系統(tǒng)并行處理機的定義：多個處理部件PU按照一定方式互連，在同一個控 制部件CU控制下，對各自的數(shù)據(jù)完成同一條指令規(guī)定 的操作。從CU看，指令是串行執(zhí)行的，從PU看，數(shù)據(jù) 是并行處理的。并行處理機也稱為陣列處理機，按照按照佛林分類法，它屬于SIMD處理機。并行處理機的兩種分類及其結(jié)構(gòu)分類：分布存儲器并行處理機和共享存儲

33、器并行處理機 分布式存儲器并行處理機的結(jié)構(gòu)框圖 共享存儲器并行處理機的結(jié)構(gòu)框圖第九章多處理機的定義與特點多處理機定義：兩個或兩個以上處理機(包括PU和CU)，通過高 速互連網(wǎng)絡(luò)連接起來，在統(tǒng)一的操作系統(tǒng)管理下， 實現(xiàn)指令以上級（任務(wù)級、作業(yè)級）并行。多處理機系統(tǒng)的特點1. 結(jié)構(gòu)靈活并行處理機：專用，PE數(shù)多，固定有限通信多處理機： 通用，PE數(shù)少，高速靈活通信2. 程序并行性并行處理機的并行性存在于指令內(nèi)部，識別比較容易。 多處理機的并行性存在于指令外部，在多個任務(wù)之間，識 別難度較大。一個簡單的例子：Y = A+B*C*D/E+F，用兩個處理機計算：CPU1：B*C， A+F， A+B*C*

34、D/E+FCPU2：D/E， B*C*D/E，3. 并行任務(wù)派生并行處理機把同種操作集中，由指令直接啟動各PE同時工 作。多處理機用專門的指令來表示并發(fā)關(guān)系，一個任務(wù)執(zhí)行時 能夠派生出與它并行的另一些任務(wù)。如果沒有空閑處理機，任務(wù)進入排隊器等待。4. 進程同步并行處理機僅一個CU，自然是同步的。多處理機中，各處理機執(zhí)行不同的指令，工作進度不會也不必保持相同。先做完的要停下等待。有數(shù)據(jù)相關(guān)和控制相關(guān)也要停下等待。要采取同步措施來保持程序要求的正確順序5. 資源分配和進程調(diào)度并行處理機的PE是固定的，用屏蔽來改變實際參加操 作的PE數(shù)目。多處理機執(zhí)行并發(fā)任務(wù)，需用處理機的數(shù)目不固定， 各處理機進出

35、任務(wù)的時刻不相同，所需共享資源的品種、數(shù)量隨時變化。多處理機基本模型及其結(jié)論多處理機運算的基本模型目標(biāo)：由M個任務(wù)組成的程序，在N臺處理機組成的系統(tǒng)上運行，求最短執(zhí)行時間？基本模型僅考慮由兩臺處理機組成的系統(tǒng)。假設(shè)：1、每個任務(wù)的執(zhí)行時間R；2、不在同一個處理機上的兩個任務(wù)需要相互通訊，每次通訊時間為C。總處理時間R*Max(MK，K)C*(MK)*K其中：R：每個任務(wù)的執(zhí)行時間，C：通信開銷，K：任務(wù)分配參數(shù)。通信時間C(M-K)K是一個開口向下的二次函數(shù)，任務(wù)執(zhí)行時間是兩根相交的直線，最小值發(fā)生在中間即 K=M/2令：通訊時間執(zhí)行時間則 R*M/2=C*M/2*(M-M/2)則 R/C=M

36、/2當(dāng)通信時間比較大時(R/CM/2)，總時間的最小值發(fā)生在中點 (K=M/2)?？倳r間最短的結(jié)論：1、當(dāng)R/CM/2時，把所有任務(wù)分配給同一臺處理機，K0；2、當(dāng)R/CM/2時，把任務(wù)平均分配給兩臺處理機，KM/2。N臺處理機系統(tǒng)的基本模型要解決的問題：把M個任務(wù)分配給N臺處理機，求總處理時間的最小值。T=Rmax(Ki)+C/2Ki(M-Ki)與兩臺處理機的情況類似，實際的最小值發(fā)生在極端分配 情況下：或者將所有的任務(wù)集中在一臺處理機上，或者將任務(wù)平均分配給所有處理機。M不是N的整數(shù)倍，如何平均分配？：例1：個任務(wù)平均分給臺處理機：例2： 11個任務(wù)平均分給臺處理機：M個任務(wù)分配給N臺處理

37、機的最佳分配方法：1、 M是N的整數(shù)倍，平分2、 M是N的整數(shù)倍， 臺處理機，每臺 個任務(wù)如果M/N0，則：另外有1臺處理機分得剩下的 個任務(wù)；剩下的 臺處理機不分配任何任務(wù)。例如：101個任務(wù)平均分給50臺處理機：有33臺處理機，每臺分給3個任務(wù)；另有臺處理機分給個任務(wù)；剩下的16臺處理機不分配任務(wù)。假設(shè)Ki 個任務(wù)分給了第臺處理機：第一項求出N臺處理機中最大執(zhí)行時間；第二項計算出Ki 與（MKi ）任務(wù)之間兩兩通信的開銷 時間，它是關(guān)于Ki 的二次函數(shù)。Ki最多有3個取值： 、 和0當(dāng)M 是N 的倍數(shù)時，單臺處理機執(zhí)行全部M個任務(wù)的總時間：總處理時間RM使兩者差為0，得到R/C=M/2結(jié)論

38、：當(dāng)R/CM/2時采用平均分配方法， 當(dāng)R/CM/2時采用集中分配方法?？偨Y(jié)上面幾個模型，可以得出如下結(jié)論：(1)多處理機系統(tǒng)結(jié)構(gòu)所需的額外開銷，包括調(diào)度，對 共享資源的競爭、同步、處理機之間通信等。(2)當(dāng)處理機臺數(shù)增加時，額外開銷時間也增加。有 時，額外開銷的增加可能比處理機數(shù)目的線性增加更 快。(3)R/C比值越大，越有利于計算過程。如果采用粗粒 度，能夠獲得較大的R/C比值；但是并行程度將大為降 低。 (4)為了使價格和性能都比較合理，處理機數(shù)目存在一 個極大值，這個值主要依賴于機器的系統(tǒng)結(jié)構(gòu)、基本 技術(shù)（尤其是通信技術(shù)）和具體的應(yīng)用問題。粒度與并行的關(guān)系并行性在很大程度上依賴于R/C

39、比值，R/C是衡量任務(wù)粒度(Granularity)的尺度，其中：R: 程序執(zhí)行時間，C: 通信開銷細粒度并行：R/C小，通信開銷大,并行度低。粗粒度并行：R/C大，通信開銷小,并行性高。多機任務(wù)平均分配的方法（沒找到）多處理機Cache間不一致的原因、兩種協(xié)議、監(jiān)聽協(xié)議的兩種方法、寫一次協(xié)議的內(nèi)容出現(xiàn)不一致性問題的原因有三個：共享可寫的數(shù)據(jù)、進程遷移、I/O傳輸有兩類解決Cache不一致性問題的協(xié)議：在總線互連的多處理機系統(tǒng)中，通常采用監(jiān)聽協(xié)議。在其他多處理機系統(tǒng)中，通常采用基于目錄協(xié)議。使用監(jiān)聽協(xié)議，有兩種方法：方法一：寫無效（Write Invalidate）策略，在本地 Cache的數(shù)據(jù)塊修改時使遠程數(shù)據(jù)塊都無效。方法二：寫更新（Write Update）策略，在本地Cache 數(shù)據(jù)塊修改時通過總線把新的數(shù)據(jù)塊廣播給含該塊的所 有其他Cache采用寫無效或?qū)懜虏呗耘cCache