第1章計算機系統構造的根本概念

1.1解釋以下術語

層次機構按照計算機語言從低級到高級的次序把計算機系統按功能劃分成多級層次構造，

每一層以一種不同的語言為特征。這些層次依次為：微程序機器級，傳統機器語言機器級，

匯編語言機器級，高級語言機器級,應用語言機器級等。

虛擬機：用軟件實現的機器。

翻譯：先用轉換程序把高一級機器上的程序轉換為低一級機器上等效的程序，然后再在這低

一級機器上運行，實現程序的功能。

解釋：對于高一級機器上的程序牛的每一條語句或指令，都是轉去執行低一級機器上的一段

等效程序。執行完后，再去高一級機器取下一條語句或指令，再進展解釋執行，如此反復，

直到解釋執行完整個程序。

計算機系統構造：傳統機器程序員所看到的計算機屬性，即概念性構造與功能特性。

在計算機技術中，把這種本來存在的事物或屬性，但從某種角度看又好似不存在的概念稱為

透明性。

計算機組成：計算機系統構造的邏輯實現，包含物理機器級中的數據流和控制流的組成以及

邏輯設計等。

計算機實現：計算機組成的物理實現，包括處理機、主存等部件的物理構造，器件的集成度

和速度，模塊、插件、底板的劃分與連接，信號傳輸，電源、冷卻及整機裝配技術等。

系統加速比：對系統中某局部進展改良時，改良后系統性能提高的倍數。

Amdahl定律：當對一個系統中的某個部件進展改良后，所能獲得的整個系統性能的提高，

受限于該部件的執行時間占總執行時間的百分比。

程序的局部性原理：程序執行時所訪問的存儲器地址不是隨機分布的，而是相對地簇聚。包

括時間局部性和空間局部性。

CPI:每條指令執行的平均時鐘周期數。

測試程序套件：由各種不同的真實應用程序構成的一組測試程序，用來測試計算機在各個方

面的處理性能。

存儲程序計算機：馮?諾依曼構造計算機。其根本點是指令驅動。程序預先存放在計算機存

儲器中，機器一旦啟動，就能按照程序指定的邏輯順序執行這些程序，自動完成由程序所描

述的處理工作。

系列機：由同一廠家生產的具有一樣系統構造、但具有不同組成和實現的一系列不同型號的

計算機。

軟件兼容：一個軟件可以不經修改或者只需少量修改就可以由一臺計算機移植到另一臺計算

機上運行。差異只是執行時間的不同。

向上（:下〕兼容：按某檔計算機編制的程序，不加修改就能運行于比它高〔低）檔的計算機。

向后〔前〕兼容：按某個時期投入市場的某種型號計算機編制的程序，不加修改地就能運行

于在它之后〔前〕投入市場的計算機。

兼容機：由不同公司廠家生產的具有一樣系統構造的計算機。

模擬：用軟件的方法在一臺現有的計算機（稱為宿主機〕上實現另一臺計算機〔稱為虛擬機〕

的指令系統。

仿真：用一臺現有計算機（稱為宿主機）上的微程序去解釋實現另一臺計算機〔稱為目標機〕

的指令系統。

并行性：計算機系統在同一時刻或者同一時間間隔內進展多種運算或操作。只要在時間上相

互重疊，就存在并行性。它包括同時性與并發性兩種含義。

時間重疊：在并行性概念中引入時間因素，讓多個處理過程在時間上相互錯開，輪流重疊地

使用同一套硬件設備的各個局部，以加快硬件周轉而贏得速度。

資源重復：在并行性概念中引入空間因素，以數量取勝。通過重復設置硬件資源，大幅度地

提高計算機系統的性能。

資源共享：這是一種軟件方法，它使多個任務按一定時間順序輪流使用同一套硬件設備。

相合度：反映多機系統中各計算機之間物理連接的嚴密程度和交互作用能力的強弱。

嚴密耦合系統：又稱直接耦合系統。在這種系統中，計算機之間的物理連接的頻帶較高，一

般是通過總線或高速開關互連，可以共享主存。

松散耦合系統：又稱間接耦合系統，一般是通過通道或通信線路實現計算機之間的互連，可

以共享外存設備(磁盤、磁帶等計算機之間的相互作用是在文件或數據集一級上進展。

異構型多處理機系統：由多個不同類型、至少擔負不同功能的處理機組成，它們按照作業要

求的順序，利用時間重疊原理，依次對它們的多個任務進展加工，各自完成規定的功能動作。

同構型多處理機系統：由多個同類型或至少擔負同等功能的處理機組成，它們同時處理同一

作業中能并行執行的多個任務。

1.2試用實例說明計算機系統構造、計算機組成與計算機實現之間的相互關系。

答：如在設計主存系統時，確定主存容量、編址方式、尋址范圍等屬于計算機系統構造。

確定主存周期、邏輯上是否采用并行主存、邏輯設計等屬于計算機組成。選擇存儲芯片類型、

微組裝技術、線路設計等屬于計算機實現。

計算機組成是計算機系統構造的邏輯實現。計算機實現是計算機組成的物理實現。一種

體系構造可以有多種組成。一種組成可以有多種實現。

1.3計算機系統構造的Flynn分類法是按什么來分類的？共分為哪幾類？

答：Flynn分類法是按照指令流和數據流的多倍性進展分類。把計算機系統的構造分為：

(1)單指令流單數據流SISD

(2)單指令流多數據流SIMD

(3)多指令流單數據流MISD

(4)多指令流多數據流MIMD

1.4計算機系統設計中經常使用的4個定量原理是什么？并說出它們的含義。

答:(1)以經常性事件為重點。在計算機系統的設計中，對經常發生的情況，賦予它

優先的處理權和資源使用權，以得到更多的總體上的改良。〔2〕Amdahl定律。加快某部件

執行速度所獲得的系統性能加速比，受限于該部件在系統中所占的重要性。［3)CPU性能

公式。執行一個程序所需的CPU時間:QCQ/x時鐘周期時間。［4)程序的局部性原理。

程序在執行時所訪問地址的分布不是隨機的，而是相對地簇聚。

1.5分別從執行程序的角度和處理數據的角度來看，計算機系統中并行性等級從低到高

可分為哪幾級？

答：從處理數據的角度來看，并行性等級從低到高可分為：

〔1〕字串位串：每次只對一個字的一位進展處理。這是最根本的串行處理方式，不存

在并行性；

〔2)字串位并：同時對一個字的全部位進展處理，不同字之間是串行的。已開場出現

并行性；

(3)字并位串：同時對許多字的同一位〔稱為位片)進展處理。這種方式具有較高的

并行性；

〔4〕全并行：同時對許多字的全部位或局部位進展處理。這是最高一級的并行。

從執行程序的角度來看，并行性等級從低到高可分為：

〔1〕指令內部并行：單條指令中各微操作之間的并行；

〔2〕指令級并行：并行執行兩條或兩條以上的指令;

(3)線程級并行：并行執行兩個或兩個以上的線程，通常是以一個進程內派生的多個

線程為調度單位；

14)任務級或過程級并行：并行執行兩個或兩個以上的過程或任務(程序段)，以子

程序或進程為調度單元；

(5)作業或程序級并行：并行執行兩個或兩個以上的作業或程序。

1.6某臺主頻為400MHz的計算機執行標準測試程序，程序中指令類型、執行數量和平

均時鐘周期數如下：

指令類型指令執行數量平均時鐘周期數

整數450001

數據傳送750002

浮點80004

分支15002

求該計算機的有效CPI、MIPS和程序執行時間。

解：(1〕CPI=(45000x1+75000x2+8000x4+1500x2)/129500=1.776

(2)MIPS速率:f/CPI=400/1.776=225.225MIPS

(3)程序執行時間二(45000x1+75000x2+8000x4+1500^2)/400=575s

1.7將計算機系統中某一功能的處理速度加快10倍，但該功能的處理時間僅為整個系

統運行時間的40%,那么采用此增強功能方法后，能使整個系統的性能提高多少？

解由題可知：可改良比例=40%=0.4部件加速比=10

根據Amdahl定律可知：

采用此增強功能方法后，能使整個系統的性能提高到原來的1.5625倍。

1.8計算機系統中有三個部件可以改良，這三個部件的部件加速比為：

部件加速比1=30;部件加速比2=20;部件加速比3=10

(1)如果部件1和部件2的可改良比例均為30%,那么當部件3的可改良比例為多

少時，系統加速比才可以到達10?

(2)如果三個部件的可改良比例分別為30%、30%和20%,三個部件同時改良，那

么系統中不可加速局部的執行時間在總執行時間中占的比例是多少？

解:(1)在多個部件可改良情況下，Amdahl定理的擴展：

Si=30,S2=20,S3=10,Sn=10,Fi=0.3,F2=0.3,得：

得F3=0.36,即部件3的可改良比例為36%o

⑵設系統改良前的執行時間為T,那么3個部件改良前的執行時間為:(0.3+0.3+0.2)

T=0.8T,不可改良局部的執行時間為0.2K

3個部件改良后的加速比分別為Si=30,S2=20,S3=10,因此3個部件改良后的執

行時間為：

改良后整個系統的執行時間為：Tn=0.045T+0.2T=0.245T

那么系統中不可改良局部的執行時間在總執行時間中占的比例是：

1.9假設某應用程序中有4類操作，通過改良，各操作獲得不同的性能提高。具體數據

如下表所示：

程序中的數量改良前的執行時間改良后的執行時間

操作類型

〔百萬條指令)〔周期)〔周期)

操作11021

操作2302015

操作335103

操作41541

(1)改良后，各類操作的加速比分別是多少？

〔2〕各類操作單獨改良后，程序獲得的加速比分別是多少？

(3)4類操作均改良后，整個程序的加速比是多少？

解：根據Amdahl定律S?=----!~~—可得

(1-Fe)+生

Se

各類操作的指令條數在各類操作單獨改良后，

操作類型各類操作的加速比Si

程序中所占的比例R程序獲得的加速比

操作111.1%21.06

操作233.3%1.331.09

操作338.9%3.331.37

操作416.7%41.14

4類操作均改良后，整個程序的加速比:

笫2章指令集構造的分類

2.1解釋以下術語

堆棧型機器：CPU中存儲操作數的單元是堆棧的機器。

累加器型機器：CPU中存儲操作數的單元是累加器的機器。

通用存放器型機器：CPU中存儲操作數的單元是通用存放器的機器。

CISC:復雜指令集計算機

RISC:精簡指令集計算機

尋址方式：指令系統中如何形成所要訪問的數據的地址。一般來說，尋址方式可以指明

指令中的操作數是一個常數、一個存放器操作數或者是一個存儲器操作數。

數據表示：硬件構造能夠識別、指令系統可以直接調用的那些數據構造。

2.2區別不同指令集構造的主要因素是什么？根據這個主要因素可將指令集構造分為哪

3類？

答：區別不同指令集構造的主要因素是CPU中用來存儲操作數的存儲單元。據此可將

指令系統構造分為堆棧構造、累加器構造和通用存放器構造。

2.3常見的3種通用存放器型指令集構造的優缺點有哪些？

答:

指令系統構造類型優點缺點

指令字長固定，指令構造簡

與指令中含存儲器操作數的指令系統構造相比，

存放器-存放器型潔，是一種簡單的代碼生成

指令條數多，目標代碼不夠緊湊，因而程序占用

(0,3)模型，各種指令的執行時鐘

的空間比擬大。

周期數相近。

由于有一個操作數的內容將被破壞，所以指令中

可以在ALU指令中直接對存

的兩個操作數不對稱。在一條指令中同時對存放

儲器操作數進展引用，而不

存放器-存儲器型器操作數和存儲器操作數進展編碼，有可能限制

必先用load指令進展加載。

[1,2)指令所能夠表示的存放器個數。指令的執行時鐘

容易對指令進展編碼，目標

周期數因操作數的來源〔存放器或存儲器)不同

代碼比擬緊湊。

而差異比擬大。

指令字長變化很大，特別是3操作數指令。而且

存儲器-存儲器型目標代碼最緊湊，不需要設每條指令完成的工作也差異很大。對存儲器的頻

(2,2)或[3,3)置存放器來保存變量。繁訪問會使存儲器成為瓶頸。這種類型的指令系

統現在已不用了。

2.4指令集應滿足哪幾個根本要求？

答：對指令集的根本要求是：完整性、規整性、高效率和兼容性。

完整性是指在一個有限可用的存儲空間內，對于任何可解的問題，編制計算程序時，指

令集所提供的指令足夠使用。

規整性主要包括對稱性和均勻性。對稱性是指所有與指令集有關的存儲單元的使用、操

作碼的設置等都是對稱的。均勻性是指對于各種不同的操作數類型、字長、操作種類和數據

存儲單元，指令的設置都要同等對待。

高效率是指指令的執行速度快、使用頻度高。

2.5指令集構造設計所涉及的內容有哪些？

答：（1）指令集功能設計：主要有RISC和CISC兩種技術開展方向；（2）尋址方式

的設計：設置尋址方式可以通過對基準程序進展測試統計，觀察各種尋址方式的使用頻率，

根據適用頻率設置必要的尋址方式。（3）操作數表示和操作數類型：主要的操作數類型和

操作數表示的選擇有：浮點數據類型、整型數據類型、字符型、十進制數據類型等等。（4）

尋址方式的表示：可以將尋址方式編碼于操作碼中，也可以將尋址方式作為一個單獨的域來

表示。（5）指令集格式的設計：有變長編碼格式、固定長度編碼格式和混合型編碼格式3

種。

2.6簡述CISC指令集構造功能設計的主要目標。從當前的計算機技術觀點來看，CISC

指令集構造的計算機有什么缺點？

答：主要目標是增強指令功能，把越來越多的功能交由硬件來實現，并且指令的數量也

是越來越多。

缺點：（1）CISC構造的指等集中，各種指令的使用頻率相差懸殊。［2）CISC構造指

令的復雜性帶來了計算機體系構造的復雜性，這不僅增加了研制時間和本錢，而且還容易造

成設計錯誤。（3〕CISC構造指令集的復雜性給VLSI設計增加了很大負擔，不利于單片集

成。（4）CISC構造的指令集中，許多復雜指令需要很復雜的操作，因而運行速度慢。（5）在

CISC構造的指令集中，由于各條指令的功能不均衡性，不利于采用先進的計算機體系構造

技術〔如流水技術）來提高系統的性能。

2.7簡述RISC指令集構造的設計原那么。

答（1〕選取使用頻率最高的指令，并補充一些最有用的指令；［2）每條指令的功能應

盡可能簡單，并在一個機器周期內完成；［3［所有指令長度均一樣；［4）只有Load和Store

操作指令才訪問存儲器，其它指令操作均在存放器之間進展；（5）以簡單有效的方式支持

高級語言。

2.8指令中表示操作數類型的方法有哪幾種？

答：操作數類型有兩種表示方法：（1）操作數的類型由操作碼的編碼指定，這是最常

見的一種方法；〔2〕數據可以附上由硬件解釋的標記，由這些標記指定操作數的類型，從

而選擇適當的運算。

2.9表示尋址方式的主要方法有哪些？簡述這些方法的優缺點。

答：表示尋址方式有兩種常用的方法：（1）將尋址方式編于操作碼中，由操作碼在描

述指令的同時也描述了相應的尋址方式。這種方式譯碼快，但操作碼和尋址方式的結合不僅

增加了指令的條數，導致了指令的多樣性，而且增加了CPU對指令譯碼的難度。［2）為每

個操作數設置一個地址描述符，莊該地址描述符表示相應操作數的尋址方式。這種方式譯碼

較慢，但操作碼和尋址獨立，易于指令擴展。

2.10通常有哪幾種指令格式，請簡述其適用范圍。

答：（1）變長編碼格式。如果系統構造設計者感興趣的是程序的目標代碼大小，而不

是性能，就可以采用變長編碼格式。〔2〕固定長度編碼格式。如果感興趣的是性能，而不

是程序的目標代碼大小，那么可以選擇固定長度編碼格式。（3）混合型編碼格式。需要兼

顧降低目標代碼長度和降低譯碼復雜度時，可以采用混合型編碼格式。

2.11根據CPU性能公式簡述RISC指令集構造計算機和CISC指令集構造計算機

的性能特點。

答：CPU性能公式：CPU時間=ICxCPIxT

其中，IC為目標程序被執行的指令條數，CPI為指令平均執行周期數，丁是時鐘周期的

時間。

一樣功能的CISC目標程序的指令條數ICcisc少于RISC的ICRISC，但是CISC的

CPIcisc和Tcisc都大于RISC的CPgsc和TRISC，因此,CISC目標程序的執行時間比RISC

的更長。

第3章流水線技術

3.1解釋以下術語

流水線：將一個重復的時序過程，分解成為假設干個子過程，而每一個子過程都可有效地在

其專用功能段上與其它子過程同時執行。

單功能流水線：指流水線的各段之間的連接固定不變、只能完成一種固定功能的流水線。

多功能流水線：指各段可以進展不同的連接，以實現不同的功能的流水線。

靜態流水線：指在同一時間內，多功能流水線中的各段只能按同一種功能的連接方式工作的

流水線。當流水線要切換到另一種功能時，必須等前面的任務都流出流水線之后，才能改變

連接。

動態流水線：指在同一時間內，多功能流水線中的各段可以按照不同的方式連接，同時執行

多種功能的流水線。它允許在某些段正在實現某種運算時，另一些段卻在實現另一種運算。

部件級流水線：把處理機中的部件進展分段，再把這些部件分段相互連接而成。它使得運算

操作能夠按流水方式進展。這種流水線也稱為運算操作流水線。

處理機級流水線：又稱指令流水線。它是把指令的執行過程按照流水方式進展處理，即把一

條指令的執行過程分解為假設干個子過程，每個子過程在獨立的功能部件中執行。

處理機間流水線：又稱為宏流水線。它是把多個處理機串行連接起來，對同一數據流進展處

理，每個處理機完成整個任務中的一局部。前一個處理機的輸出結果存入存儲器中，作為后

一個處理機的輸入。

線性流水線：指各段串行連接、沒有反應回路的流水線。數據通過流水線中的各段時，每一

個段最多只流過一次。

非線性流水線：指各段除了有串行的連接外，還有反應回路的流水線。

順序流水線：流水線輸出端任務流出的順序與輸入端任務流入的順序完全一樣。

亂序流水線：流水線輸出端任務流出的順序與輸入端任務流入的順序可以不同，允許后進入

流水線的任務先完成。這種流水線又稱為無序流水線、錯序流水線、異步流水線。

吞吐率：在單位時間內流水線所完成的任務數量或輸出結果的數量。

流水線的加速比.使用順序處理方式處理一批任務所用的時間與按流水處理方式處理同一批

任務所用的時間之比。

流水線的效率：即流水線設備的利用率，它是指流水線中的設備實際使用時間與整個運行時

間的比值。

數據相關：考慮兩條指令/和/在/的前面，如果下述條件之一成立，那么稱指令/與指

令/數據相關：

〔1〕指令/使用指令/.產生的結果；

〔2〕指令/與指令片數據相關，而指令攵又與指令/數據相關。

名相關：如果兩條指令使用了一樣的名，但是它們之間并沒有數據流動，那么稱這兩條指令

存在名相關。

控制相關：是指由分支指令引起的相關。它需要根據分支指令的執行結果來確定后面該執行

哪個分支上的指令。

反相關：考慮兩條指令/和在/的前面，如果指令/所寫的名與指令/所讀的名一樣，那

么稱指令/和/發生了反相關。

輸出相關：考慮兩條指令/.和/,/.在/的前面，如果指令/和指令/所寫的名一樣，那么稱指

令/和/發生了輸出相關。

換名技術：名相關的兩條指令之間并沒有數據的傳送，只是使用了一樣的名。可以把其中一

條指令所使用的名換成別的，以此來消除名相關。

構造沖突：因硬件資源滿足不了指令重疊執行的要求而發生的沖突。

數據沖突：當指令在流水線中重疊執行時，因需要用到前面指令的執行結果而發生的沖突。

控制沖突：流水線遇到分支指令或其它會改變PC值的指令所引起的沖突。

定向：用來解決寫后讀沖突的。在發生寫后讀相關的情況下，在計算結果尚未出來之前，后

面等待使用該結果的指令并不見得是馬上就要用該結果。如果能夠將該計算結果從其產生的

地方直接送到其它指令需要它的地方，那么就可以防止停頓。

寫后讀沖突：考慮兩條指令i和j,且i在j之前進入流水線，指令j用到指令i的計算結果，

而且在i將結果寫入存放器之前就去讀該存放器，因而得到的是舊值C

讀后寫沖突：考慮兩條指令i和j,且i在j之前進入流水線，指令j的目的存放器和指令i

的源操作數存放器一樣，而且j在i讀取該存放器之前就先對它進展了寫操作，導致i讀到

的值是錯誤的。

寫后寫沖突：考慮兩條指令i和j，且i在j之前進入流水線，，指令j和指令i的結果單元〔存

放器或存儲器單元）一樣，而且j在i寫入之前就先對該單元進展了寫入操作，從而導致寫

入順序錯誤。這時在結果單元中留下的是i寫入的值，而不是j寫入的。

鏈接技術：具有先寫后讀相關的兩條指令，在不出現功能部件沖突和Vi沖突的情況下，可

以把功能部件鏈接起來進展流水處理，以到達加快執行的目的。

分段開采：當向量的長度大于向量存放器的長度時，必須把長向量分成長度固定的段，然后

循環分段處理，每一次循環只處理一個向量段。

半性能向量長度：向量處理機的性能為其最大性能段的一半時所需的向量長度。

向量長度臨界值：向量流水方式的處理速度優于標量串行方式的處理速度時所需的向量長度

的最小值。

3.2指令的執行可采用順序執行、重疊執行和流水線三種方式，它們的主要區別是什

么？各有何優缺點。

答：（1）指令的順序執行是指指令與指令之間順序串行。即上一條指令全部執行完后，

才能開場執行下一條指令。

優點：控制簡單，節省設備。缺點：執行指令的速度慢，功能部件的利用率低。

〔2〕指令的重疊指令是在相鄰的指令之間，讓第k條指令與取第k+l條指令同時進展。

重疊執行不能加快單條指令的執行速度，但在硬件增加不多的情況下，可以加快相鄰兩條指

令以及整段程序的執行速度。與順序方式相比，功能部件的利用率提高了，控制變復雜了。

〔3〕指令的流水執行是把一個指令的執行過程分解為假設干個子過程，每個子過程由

專門的功能部件來實現。把多個處理過程在時間上錯開，依次通過各功能段，每個子過程與

其它的子過程并行進展。依靠提高吞吐率來提高系統性能。流水線中各段的時間應盡可能相

等

3.3簡述先行控制的根本思想。

答：先行控制技術是把緩沖技術和預處理技術相結合。緩沖技術是在工作速度不固定的

兩個功能部件之間設置緩沖器，用以平滑它們的工作。預處理技術是指預取指令、對指令進

展加工以及預取操作數等。

采用先行控制方式的處理機內部設置多個緩沖站，用于平滑主存、指令分析部件、運算

器三者之間的工作。這樣不僅使它們都能獨立地工作，充分忙碌而不用相互等待，而且使指

令分析部件和運算器分別能快速地取得指令和操作數，大幅度地提高指令的執行速度和部件

的效率。這些緩沖站都按先進先出的方式工作，而且都是由一組假設干個能快速訪問的存儲

單元和相關的控制邏輯組成。

采用先行控制技術可以實現多條指令的重疊解釋執行。

3.4設一條指令的執行過程分成取指令、分析指令和執行指令三個階段，每個階段所需

的時間分別為Z、M和2M。分別求出以下各種情況下，連續執行N條指令所需的時間。

(1)順序執行方式；

(2〕只有“取指令〃與“執行指令〃重疊；

〔3〕“取指令"、"分析指令〃與“執行指令〃重疊。

解：[1)每條指令的執行時間為：可+句+2乂=4軌

連續執行N條指令所需的時間為：4NZ

12)連續執行N條指令所需的時間為：4可+3(N-1)M=[3N+1)M

〔3〕連續執行N條指令所需的時間為：4儀+2(N-1)At=(2N+2)M

3.5簡述流水線技術的特點。

答.流水技術有以下特點：

(1)流水線把一個處理過程分解為假設干個子過程，每個子過程由一個專門的功能

部件來實現。因此，流水線實際上是把一個大的處理功能部件分解為多個獨立的功能部件，

并依靠它們的并行工作來提高吞吐率。

〔2〕流水線中各段的時間應盡可能相等，否那么將引起流水線堵塞和斷流。

(3)流水線每一個功能部件的前面都要有一個緩沖存放器，稱為流水存放器。

(4)流水技術適合于大量重復的時序過程，只有在輸入端不斷地提供任務，才能充

分發揮流水線的效率。

15)流水線需要有通過時間和排空時間。在這兩個時間段中，流水線都不是滿負荷

工作。

3.6解決流水線瓶頸問題有哪兩種常用方法？

答：細分瓶頸段與重復設置瓶頸段

3.7減少流水線分支延遲的靜態方法有哪些？

答:(1)預測分支失敗：沿失敗的分支繼續處理指令，就好象什么都沒發生似的。當

確定分支是欠敗時，說明預測正確，流水線正常流動；當確定分支是成功時，流水線就把在

分支指令之后取出的指令轉化為空操作，并按分支目標地址重新取指令執行。

(2)預測分支成功：當流水線ID段檢測到分支指令后，一旦計算出了分支目標地址，

就開場從該目標地址取指令執行。

(3〕延遲分支：主要思想是從邏輯上“延長〃分支指令的執行時間。把延遲分支看成是

由原來的分支指令和假設干個延遲槽構成。不管分支是否成功，都要按順序執行延遲槽中的

指令。

3種方法的共同特點：它們對分支的處理方法在程序的執行過程中始終是不變的。它們

要么總是預測分支成功，要么總是預測分支失敗。

3.8簡述延遲分支方法中的三種調度策略的優缺點。

調度策略對調度的要求對流水線性能改善的影響

從前調度分支必須不依賴于被調度的指令總是可以有效提高流水線性能

如果分支轉移失敗，必須保證被調度的指令對程分支轉移成功時，可以提高流水線性能。

從目標處調度

序的執行沒有影響，可能需要復制被調度指令但由于復制指令，可能加大程序空間

如果分支轉移成功，必須保證被調度的指令對程分支轉移失敗時，可以提高流水線性能

從失敗處調度

序的執行沒有影響

3.9列舉出下面循環中的所有相關，包括輸出相關、反相關、真相關。

for（i=2;i<100;i=i+1）

a[i]=b[i]+a[i];/*s1*/

c[i+1]=a[i]+d[i];/*s27

a[i-1]=2*b[i];/*s37

b[i+1]=2*b[i];/*s4*/

解：展開循環兩次：

a[i]=b[i]+a[i];/*s1*/

c[i+1]=a[i]+d[i];/*s2*/

a[i-1]=2*b[i];/*s3*/

b[i+1]=2*b[i];/*s4*/

a[i+1]=b[i+1]+a[i+1];/*sr*/

c[i+2]=a[i+1]+d[i+1];/*s2T

a[i]=2*b[i+1];/*s3*7

b[i+2]=2*b[i+1];/*s4*/

輸出相關：無

反相關：無

真相關：S1&S2

由于循環引入的相關：S4&S4'（真相關）、S1,&S4〔真相關）、S3'&S4〔真相關）、S1&S3,

（輸出相關、反相關）、S2&S3'1反相關〕。

3.10簡述三種向量處理方式，它們對向量處理機的構造要求有何不同？

答（1）橫向處理方式：假設向量長度為N,那么水平處理方式相當于執行N次循環。

假設使用流水線，在每次循環中可能出現數據相關和功能轉換，不適合對向量進展流水處理。

（2）縱向處理方式：將整個向量按一樣的運算處理完畢之后，再去執行其他運算。適合對向

量進展流水處理，向量運算指令的源/目向量都放在存儲器內，使得流水線運算部件的輸入、

輸出端直接與存儲器相聯，構成M-M型的運算流水線。（3）縱橫處理方式：把長度為N的

向量分為假設干組，每組長度為n,組內按縱向方式處理，依次處理各組，組數為「N/n」,

適合流水處理。可設長度為n的向量存放器，使每組向量運算的源/目向量都在向量存放器

中，流水線的運算部件輸入、輸出端與向量存放器相聯，構成R-R型運算流水線。

3.11可采用哪些方法來提高向量處理機的性能？

答：可采用多種方法：

(1)設置多個功能部件，使它們并行工作；

(2)采用鏈接技術，加快一串向量指令的執行；

(3)采用循環開采技術，加快循環的處理；

(4)采用多處理機系統，進一步提高性能。

3.12有一指令流水線如下所示

(1)求連續輸入10條指令，該流水線的實際吞吐率和效率；

(2)該流水線的',瓶頸〃在哪一段？請采取兩種不同的措施消除此~瓶頸〃。對于你所

給出的兩種新的流水線連續輸入10條指令時，其實際吞吐率和效率各是多少？

解:C1)

⑵瓶頸在3、4段。

■變成八級流水線

(細分)

■重復設置部件

3.13有一個流水線由4段組或，其中每當流經第3段時，總要在該段循環一次，然后

才能流到第4段。如果每段經過一次所需要的時間都是△/，問：

(1)當在流水線的輸入端連續地每時間輸入任務時，該流水線會發生什么情況？

(2)此流水線的最大吞吐率為多少？如果每2△/輸入一個任務，連續處理10個任務

時的實際吞吐率和效率是多少？

(3)當每段時間不變時，如何提高該流水線的吞吐率？仍連續處理10個任務時，其

吞吐率提高多少？

解：［1)會發生流水線阻塞情況。

第1個任務S1S2S3S3S4

第2個任務S1S2stallS3S3S4

第3個任務S1stallS2stallS3S3S4

第4個任務S1stallS2stallS3S3S4

⑵

[3)重復設置部件

吞吐率提高倍數=還=1.64

%3A/

3.14有一條靜態多功能流水線由5段組成，加法用1、3、4、5段，乘法用1、2、5

段，第3段的時間為2M,其余各段的時間均為鈍，而且流水線的輸出可以直接返回輸入端

或

暫存于相應的流水存放器中。現要在該流水線上計算：畫出其時空圖，并計

算其吞吐率、加速比和效率。

解：首先，應選擇適合于流水線工作的算法。對于此題，應先計算Ai+Bi、A2+B2、

A3+B3和A4+B4；再計算(Ai+Bi)X(A2+B2)和(A3+B3)X(A4+B4);然后求總的結果。

其次，畫出完成該計算的時空圖，如下圖，圖中陰影局部表示該段在工作。

CXD

BiB2B3B4BD

由圖可見，它在18個時間中，給出了7個結果。所以吞吐率為：

如果不用流水線，由于一次求積需3At,一次求和需5At,那么產生上述7個結果共

需〔4x5+3x3)A/=29Ato所以加速比為:

該流水線的效率可由陰影區的面積和5個段總時空區的面積的比值求得：

3.15動態多功能流水線由6個功能段組成，如以下圖：

其中，S1、S4、S5、S6組成乘法流水線，S1、S2、S3、S6組成加法流水線，各個

功能段時間均為50ns,假設該流水線的輸出結果可以直接返回輸入端，而且設置有足夠的

緩沖存放器，假設以最快的方式用該流水計算:之XiyR

i=l

(1)畫出時空圖；

(2)計算實際的吞吐率、加速比和效率。

解：機器一共要做10次乘法，4次加法。

3.16在MIPS流水線上運行如下代碼序列：

LOOP:LWR1,0(R2)

DADDIUR1,R1,#1

SWR1,0(R2)

DADDIUR2,R2,#4

DSUBR4,R3,R2

BNEZR4,LOOP

其中：R3的初值是R2+396。假設：在整個代碼序列的運行過程中.所有的存儲器訪問都

是命中的，并且在一個時鐘周期中對同一個存放器的讀操作和寫操作可以通過存放器文件

“定向〃。問：

(1)在沒有任何其它定向(或旁路)硬件的支持下，請畫出該指令序列執行的流水線

時空圖。假設采用排空流水線的策略處理分支指令，且所有的存儲器訪問都命中

Cache,那么執行上述循環需要多少個時鐘周期？

(2)假設該流水線有正常的定向路徑，請畫出該指令序列執行的流水線時空圖。假設

采用預測分支失敗的策略處理分支指令，且所有的存儲器訪問都命中Cache，那

么執行上述循環需要多少個時鐘周期？

(3)假設該流水線有正常的定向路徑和一個單周期延遲分支，請對該循環中的指令進

展調度，你可以重新組織指令的順序，也可以修改指令的操作數，但是注意不能

增加指令的條數。請畫出該指令序列執行的流水線時空圖，并計算執行上述循環

所需要的時鐘周期數。

解：

存放器讀寫可以定向，無其他旁路硬件支持。排空流水線。

第i次迭代G=0..98)開場周期:1+0x17)

總的時鐘周期數：［98x17)+18=1684

有正常定向路徑，預測分支失敗。

第i次迭代。=0..98〕開場周期:1+O10)

總的時鐘周期數：［98x10)+11=991

有正常定向路徑。單周期延遲分支。

LOOP:LWR1,0(R2)

DADDIUR2,R2,#4

DADDIUR1,R1,#1

DSUBR4,R3,R2

BNEZR4,LOOP

SWR1,-4(R2)

第i次迭代(i=0..98)開場周期：1+(ix6〕

總的時鐘周期數:(98x6)+10=598

3.17假設各種分支指令數占所有指令數的百分比方下.

條件分支20%(其中的60%是分支成功的〕

跳轉和調用5%

現有一條段數為4的流水線，無條件分支在第二個時鐘周期完畢時就被解析出來，而

條件分支要到第三個時鐘周期完畢時才能夠被解析出來。第一個流水段是完全獨立于指令類

型的，即所有類型的指令都必須經過第一個流水段的處理。請問在沒有任何控制相關的情況

下，該流水線相對于存在上述控制相關情況下的加速比是多少？

解：沒有控制相關時流水線的平均CPI=1

存在控制相關時：由于無條件分支在第二個時鐘周期完畢時就被解析出來，而條件分支

要到第3個時鐘周期完畢時才能被解析出來。所以：

(1)假設使用排空流水線的策略，那么對于條件分支，有兩個額外的stall,對無條件

分支，有一個額外的stall:

CPI=1+20%*2+5%*1=1.45

加速比S=CPI/1=1.45

(2)假設使用預測分支成功策略，那么對于不成功的條件分支，有兩個額外的stall,

對無條件分支和成功的條件分支，有一個額外的stall1:

CPI=1+20%*(60%*1+40%*2)+5%*1=1.33

加速比S=CPI/1=1.33

(3〕假設使用預測分支失敗策略，那么對于成功的條件分支，有兩個額外的stall;對

無條件分支，有一個額外的stall;對不成功的條件分支，其目標地址已經由PC值給出，

不必等待，所以無延遲：

CPI=1+20%*(60%*2+40%*0)+5%*1=1.29

加速比S=CPI/1=1.29

3.18在CRAY」機器上，按照鏈接方式執行下述4條向量指令(括號中給出了相應功

能部件的執行時間〕，如果向量存放器和功能部件之間的數據傳送需要1拍，試求此鏈接流

水線的通過時間是多少拍？如果向量長度為64,那么需多少拍才能得到全部結果？

Vo-存儲器〔從存儲器中取數：1拍)

V2^V0+Vi〔向量加：3拍)

V3—V2VA31按(A3)左移：4拍〕

V5^V3AV4〔向量邏輯乘：2拍)

解：通過時間就是每條向量指令的第一個操作數執行完畢需要的時間，也就是各功能流

水線由空到滿的時間，具體過程如以下圖所示。要得到全部結果：在流水線充滿之后，

向量中后繼操作數繼續以流水方式執行，直到整組向量執行完畢。

3.19某向量處理機有16個向量存放器，其中Vo~V5中分別放有向量A、B、C、D、E、

F,向量長度均為8,向量各元素均為浮點數；處理部件采用兩條單功能流水線，加法功能

部件時間為2拍乘法功能部件時間為3拍。采用類似于CARY-1的鏈接技術，先計算〔A+B〕

*C,在流水線不停流的情況下,接著計算(D+E)*FO

(1)求此鏈接流水線的通過時間？〔設存放器入、出各需1拍)

(2)假設每拍時間為50ns,完成這些計算并把結果存進相應存放器，此處理部件的

實際吞吐率為多少MFLOPS?

解：11)我們在這里假設A+B的中間結果放在V6中,(A+B)xC地最后結果放在V7

中，D+E地中間結果放在V8中,(D+E)xF的最后結果放在V9中。具體實現參考以

下圖：

通過時間應該為前者(CA+B)xC)通過的時間：

T通過=(1+2+1)+(1+3+1)二91拍)

(2)在做完(A+B)xC之后，作(C+D)xE就不需要通過時間了。

V6-A+B

V7—V6xC

V8-D+E

T=T通過+(8—1)+8=24(拍)=1200(屆)

32

TP=—=26.67MFLOFS

T

V9—V8xF

7章互連網絡

7.1解釋以下術語

線路交換：在線路交換中，源結點和目的結點之間的物理通路在整個數據傳送期間一直保持

連接。

分組交換：把信息分割成許多組(又稱為包〕，將它們分別送入互連網絡。這些數據包可以

通過不同的路徑傳送，到目的結點后再拼合出原來的數據，結點之間不存在固定連接的物理

通路。

靜態互連網絡：各結點之間有固定的連接通路、且在運行中不能改變的網絡。

動態互連網絡：由交換開關構成、可按運行程序的要求動態地改變連接狀態的網絡。

互連網絡：一種由開關元件按照一定的拓撲構造和控制方式構成的網絡，用來實現計算機系

統中結點之間的相互連接。在拓撲上，互連網絡是輸入結點到輸出結點之間的一組互連或映

象。

互連函數：用變量X表示輸入，用函數f(x)表示輸出。那么f(x)表示：在互連函數f的作用

下，輸入端X連接到輸出端f(x)。它反映了網絡輸入端數組和輸出端數組之間對應的置換關

系或排列關系，所以互連函數有時也稱為置換函數或排列函數。

網絡直徑：指互連網絡中任意兩個結點之間距離的最大值。

結點度：指互連網絡中結點所連接的邊數(通道數

等分帶寬：把由N個結點構成的網絡切成結點數一樣(N/2)的兩半，在各種切法中，沿切

口邊數的最小值。

對稱網絡：從任意結點來看，網絡的構造都是一樣的。

7.2試比擬可用于動態互連的總線、穿插開關和多級互連網絡的硬件復雜度和帶寬。

答：總線互連的復雜性最低，本錢也是最低。其缺點是每臺處理機可用的帶寬較窄。

穿插開關是最昂貴的，因為其硬件復雜性以M上升，所以其本錢最高。但是穿插開關

的帶寬和尋徑性能最好。當網絡的規模較小時，它是一種理想的選擇。

多級互連網絡的復雜度和帶寬介于總線和穿插開關之間，是一種折中方案。其主要優點

是采用模塊化構造，可擴展性較好。不過，其時延隨網絡級數的增加而上升。另外，由于其

硬件復雜度比總線高很多，其本錢也不低。

7.3設E為交換函數，S為均勻洗牌函數，B為蝶式函數，PM2I為移數函數，函數的

自變量是十進制數表示的處理機編號。現有32臺處理機，其編號為0,1,2,…，31。

11)分別計算以下互連函數

E2112)S(8)B(9)PM2I+3〔28〕Eo(S⑷〕S〔Eo〔18)〕

〔2)用Eo和S構成均勻洗牌交換網(每步只能使用Eo和S一次〕，網絡直徑是多少？

從5號處理機發送數據到7號處理機，最短路徑要經過幾步？請列出經過的處理機編號。

13)采用移數網絡構成互連網，網絡直徑是多少？結點度是多少？與2號處理機距離

最遠的是幾號處理機？

解：[1)共有32個處理機，表示處理機號的二進制地址應為5位。

E2〔12〕=E2C01100)=01000⑻

S⑻=SC01000)=10000〔16)

B⑼=B(01001)=11000〔24)

PM2l+3〔28〕=28+23mod32=4

Eo(S⑷)=E0(S(00100))=01001⑼

S(Eo(18))=S(Eo(10010D=S(10011)=00111⑺

12[2n個結點的均勻洗牌交換網的網絡直徑為2n-1,32個結點的均勻洗牌交換網的

網絡直徑為9o

從5號處理機發送數據到7號處理機，最短路徑要經過6步：

00101-00100-01000^010010010^10011-00111

〔3〕網絡直徑是3,結點度是9,與2號處理機距離最遠的是13、15、21、23號處

理機。

7.7具有N=2n個輸入端的Omega網絡，采用單元控制。

(1)N個輸入總共應有多少種不同的排列？

[2)該Omega網絡通過一次可以實現的置換總共可有多少種是不同的？

13)假設N=8,計算一次通過能實現的置換數占全部排列的百分比。

解：11[N個輸入的不同排列數為N!。

12[N個輸入端、輸出端的Omega網絡有n=log2N級開關級，每級開關級有N/2個

2x2的4功能開關，總共有3/2〕log2N個開關。置換連接是指網絡的輸入端與輸出端的

一對一連接，故只考慮2x2開關的2個功能狀態，即直送與穿插。網絡采用單元控制，因

此，每個開關都根據連接要求處于2個功能狀態中的一種狀態，所以，由(N/2)log2N個

開關組成的Omega網絡的開關狀態的種樹為：

一種網絡開關狀態實現Omega網絡的一種無沖突的置換連接，所以，一次使用Omega

網絡可以實現的無沖突的置換連接有NW2種。

13[假設N=8,那么一次通過能實現的置換數占全部排列的百分比為：

7.8用一個N=8的三級Omega網絡連接8個處理機(P0-P7),8個處理機的輸出端

分別依序連接Omega網絡的8人輸入端0~7,8個處理機的輸入端分別依序連接Omega

網絡的8個輸出端0~7。如果處理機P6要把數據播送給處理機Po~P4,處理機P3要把數據

播送給處理機P5~P7,那么，Omega網絡能否同時為它們的播送要求實現連接？畫出實現

播送的Omega網絡的開關狀態度。

解：Omega網絡使用的2x2開關有4種狀態：直送、穿插、上播、下播。置換連接只

使用直送和穿插狀態，播送連接還需要使用上播和下播狀態。分別畫出實現處理機P6和P3

的播送連接要求使用的開關狀態，如果沒有開關狀態和開關輸出端爭用沖突，就可以使用播

送連接。實際上，它們的播送要求沒有沖突，因此，可以同時實現，同時實現的Omega網

絡開關狀態圖如下所示。

7.9試