計算機系統(tǒng)結(jié)構(gòu)課后習題集答案解析

第1章計算機系統(tǒng)構(gòu)造的根本概念

1.1解釋以下術語

層次機構(gòu)按照計算機語言從低級到高級的次序把計算機系統(tǒng)按功能劃分成多級層次構(gòu)造，

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

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

虛擬機：用軟件實現(xiàn)的機器。

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

一級機器上運行，實現(xiàn)程序的功能。

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

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

直到解釋執(zhí)行完整個程序。

計算機系統(tǒng)構(gòu)造：傳統(tǒng)機器程序員所看到的計算機屬性，即概念性構(gòu)造與功能特性。

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

透明性。

計算機組成：計算機系統(tǒng)構(gòu)造的邏輯實現(xiàn)，包含物理機器級中的數(shù)據(jù)流和控制流的組成以及

邏輯設計等。

計算機實現(xiàn)：計算機組成的物理實現(xiàn)，包括處理機、主存等部件的物理構(gòu)造，器件的集成度

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

系統(tǒng)加速比：對系統(tǒng)中某局部進展改良時，改良后系統(tǒng)性能提高的倍數(shù)。

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

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

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

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

CPI:每條指令執(zhí)行的平均時鐘周期數(shù)。

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

面的處理性能。

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

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

述的處理工作。

系列機：由同一廠家生產(chǎn)的具有一樣系統(tǒng)構(gòu)造、但具有不同組成和實現(xiàn)的一系列不同型號的

計算機。

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

機上運行。差異只是執(zhí)行時間的不同。

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

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

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

兼容機：由不同公司廠家生產(chǎn)的具有一樣系統(tǒng)構(gòu)造的計算機。

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

的指令系統(tǒng)。

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

的指令系統(tǒng)。

并行性：計算機系統(tǒng)在同一時刻或者同一時間間隔內(nèi)進展多種運算或操作。只要在時間上相

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

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

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

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

提高計算機系統(tǒng)的性能。

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

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

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

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

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

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

異構(gòu)型多處理機系統(tǒng)：由多個不同類型、至少擔負不同功能的處理機組成，它們按照作業(yè)要

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

同構(gòu)型多處理機系統(tǒng)：由多個同類型或至少擔負同等功能的處理機組成，它們同時處理同一

作業(yè)中能并行執(zhí)行的多個任務。

1.2試用實例說明計算機系統(tǒng)構(gòu)造、計算機組成與計算機實現(xiàn)之間的相互關系。

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

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

微組裝技術、線路設計等屬于計算機實現(xiàn)。

計算機組成是計算機系統(tǒng)構(gòu)造的邏輯實現(xiàn)。計算機實現(xiàn)是計算機組成的物理實現(xiàn)。一種

體系構(gòu)造可以有多種組成。一種組成可以有多種實現(xiàn)。

1.3計算機系統(tǒng)構(gòu)造的Flynn分類法是按什么來分類的？共分為哪幾類？

答：Flynn分類法是按照指令流和數(shù)據(jù)流的多倍性進展分類。把計算機系統(tǒng)的構(gòu)造分為：

(1)單指令流單數(shù)據(jù)流SISD

(2)單指令流多數(shù)據(jù)流SIMD

(3)多指令流單數(shù)據(jù)流MISD

(4)多指令流多數(shù)據(jù)流MIMD

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

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

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

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

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

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

1.5分別從執(zhí)行程序的角度和處理數(shù)據(jù)的角度來看，計算機系統(tǒng)中并行性等級從低到高

可分為哪幾級？

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

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

在并行性；

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

并行性；

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

并行性；

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

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

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

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

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

線程為調(diào)度單位；

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

程序或進程為調(diào)度單元；

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

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

均時鐘周期數(shù)如下：

指令類型指令執(zhí)行數(shù)量平均時鐘周期數(shù)

整數(shù)450001

數(shù)據(jù)傳送750002

浮點80004

分支15002

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

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

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

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

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

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

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

根據(jù)Amdahl定律可知：

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

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

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

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

少時，系統(tǒng)加速比才可以到達10?

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

么系統(tǒng)中不可加速局部的執(zhí)行時間在總執(zhí)行時間中占的比例是多少？

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

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

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

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

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

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

行時間為：

改良后整個系統(tǒng)的執(zhí)行時間為：Tn=0.045T+0.2T=0.245T

那么系統(tǒng)中不可改良局部的執(zhí)行時間在總執(zhí)行時間中占的比例是：

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

如下表所示：

程序中的數(shù)量改良前的執(zhí)行時間改良后的執(zhí)行時間

操作類型

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

操作11021

操作2302015

操作335103

操作41541

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

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

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

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

(1-Fe)+生

Se

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

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

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

操作111.1%21.06

操作233.3%1.331.09

操作338.9%3.331.37

操作416.7%41.14

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

笫2章指令集構(gòu)造的分類

2.1解釋以下術語

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

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

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

CISC:復雜指令集計算機

RISC:精簡指令集計算機

尋址方式：指令系統(tǒng)中如何形成所要訪問的數(shù)據(jù)的地址。一般來說，尋址方式可以指明

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

數(shù)據(jù)表示：硬件構(gòu)造能夠識別、指令系統(tǒng)可以直接調(diào)用的那些數(shù)據(jù)構(gòu)造。

2.2區(qū)別不同指令集構(gòu)造的主要因素是什么？根據(jù)這個主要因素可將指令集構(gòu)造分為哪

3類？

答：區(qū)別不同指令集構(gòu)造的主要因素是CPU中用來存儲操作數(shù)的存儲單元。據(jù)此可將

指令系統(tǒng)構(gòu)造分為堆棧構(gòu)造、累加器構(gòu)造和通用存放器構(gòu)造。

2.3常見的3種通用存放器型指令集構(gòu)造的優(yōu)缺點有哪些？

答:

指令系統(tǒng)構(gòu)造類型優(yōu)點缺點

指令字長固定，指令構(gòu)造簡

與指令中含存儲器操作數(shù)的指令系統(tǒng)構(gòu)造相比，

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

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

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

的空間比擬大。

周期數(shù)相近。

由于有一個操作數(shù)的內(nèi)容將被破壞，所以指令中

可以在ALU指令中直接對存

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

儲器操作數(shù)進展引用，而不

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

必先用load指令進展加載。

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

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

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

代碼比擬緊湊。

而差異比擬大。

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

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

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

統(tǒng)現(xiàn)在已不用了。

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

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

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

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

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

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

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

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

2.5指令集構(gòu)造設計所涉及的內(nèi)容有哪些？

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

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

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

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

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

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

種。

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

指令集構(gòu)造的計算機有什么缺點？

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

是越來越多。

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

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

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

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

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

技術〔如流水技術）來提高系統(tǒng)的性能。

2.7簡述RISC指令集構(gòu)造的設計原那么。

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

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

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

高級語言。

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

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

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

而選擇適當?shù)倪\算。

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

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

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

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

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

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

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

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

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

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

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

2.11根據(jù)CPU性能公式簡述RISC指令集構(gòu)造計算機和CISC指令集構(gòu)造計算機

的性能特點。

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

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

時間。

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

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

的更長。

第3章流水線技術

3.1解釋以下術語

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

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

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

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

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

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

連接。

動態(tài)流水線：指在同一時間內(nèi)，多功能流水線中的各段可以按照不同的方式連接，同時執(zhí)行

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

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

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

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

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

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

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

一個處理機的輸入。

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

個段最多只流過一次。

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

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

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

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

吞吐率：在單位時間內(nèi)流水線所完成的任務數(shù)量或輸出結(jié)果的數(shù)量。

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

任務所用的時間之比。

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

間的比值。

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

令/數(shù)據(jù)相關：

〔1〕指令/使用指令/.產(chǎn)生的結(jié)果；

〔2〕指令/與指令片數(shù)據(jù)相關，而指令攵又與指令/數(shù)據(jù)相關。

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

存在名相關。

控制相關：是指由分支指令引起的相關。它需要根據(jù)分支指令的執(zhí)行結(jié)果來確定后面該執(zhí)行

哪個分支上的指令。

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

么稱指令/和/發(fā)生了反相關。

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

令/和/發(fā)生了輸出相關。

換名技術：名相關的兩條指令之間并沒有數(shù)據(jù)的傳送，只是使用了一樣的名?？梢园哑渲幸?/p>

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

構(gòu)造沖突：因硬件資源滿足不了指令重疊執(zhí)行的要求而發(fā)生的沖突。

數(shù)據(jù)沖突：當指令在流水線中重疊執(zhí)行時，因需要用到前面指令的執(zhí)行結(jié)果而發(fā)生的沖突。

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

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

面等待使用該結(jié)果的指令并不見得是馬上就要用該結(jié)果。如果能夠?qū)⒃撚嬎憬Y(jié)果從其產(chǎn)生的

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

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

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

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

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

的值是錯誤的。

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

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

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

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

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

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

循環(huán)分段處理，每一次循環(huán)只處理一個向量段。

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

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

的最小值。

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

么？各有何優(yōu)缺點。

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

才能開場執(zhí)行下一條指令。

優(yōu)點：控制簡單，節(jié)省設備。缺點：執(zhí)行指令的速度慢，功能部件的利用率低。

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

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

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

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

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

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

等

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

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

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

展加工以及預取操作數(shù)等。

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

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

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

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

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

采用先行控制技術可以實現(xiàn)多條指令的重疊解釋執(zhí)行。

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

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

(1)順序執(zhí)行方式；

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

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

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

連續(xù)執(zhí)行N條指令所需的時間為：4NZ

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

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

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

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

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

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

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

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

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

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

分發(fā)揮流水線的效率。

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

工作。

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

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

3.7減少流水線分支延遲的靜態(tài)方法有哪些？

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

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

分支指令之后取出的指令轉(zhuǎn)化為空操作，并按分支目標地址重新取指令執(zhí)行。

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

就開場從該目標地址取指令執(zhí)行。

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

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

指令。

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

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

3.8簡述延遲分支方法中的三種調(diào)度策略的優(yōu)缺點。

調(diào)度策略對調(diào)度的要求對流水線性能改善的影響

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

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

從目標處調(diào)度

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

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

從失敗處調(diào)度

序的執(zhí)行沒有影響

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

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*/

解：展開循環(huán)兩次：

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

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

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

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

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

假設使用流水線，在每次循環(huán)中可能出現(xiàn)數(shù)據(jù)相關和功能轉(zhuǎn)換，不適合對向量進展流水處理。

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

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

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

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

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

中，流水線的運算部件輸入、輸出端與向量存放器相聯(lián)，構(gòu)成R-R型運算流水線。

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

答：可采用多種方法：

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

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

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

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

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

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

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

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

解:C1)

⑵瓶頸在3、4段。

■變成八級流水線

(細分)

■重復設置部件

3.13有一個流水線由4段組或，其中每當流經(jīng)第3段時，總要在該段循環(huán)一次，然后

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

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

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

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

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

吞吐率提高多少？

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

第1個任務S1S2S3S3S4

第2個任務S1S2stallS3S3S4

第3個任務S1stallS2stallS3S3S4

第4個任務S1stallS2stallS3S3S4

⑵

[3)重復設置部件

吞吐率提高倍數(shù)=還=1.64

%3A/

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

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

或

暫存于相應的流水存放器中?，F(xiàn)要在該流水線上計算：畫出其時空圖，并計

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

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

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

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

CXD

BiB2B3B4BD

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

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

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

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

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

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

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

緩沖存放器，假設以最快的方式用該流水計算:之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)在沒有任何其它定向(或旁路)硬件的支持下，請畫出該指令序列執(zhí)行的流水線

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

Cache,那么執(zhí)行上述循環(huán)需要多少個時鐘周期？

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

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

么執(zhí)行上述循環(huán)需要多少個時鐘周期？

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

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

增加指令的條數(shù)。請畫出該指令序列執(zhí)行的流水線時空圖，并計算執(zhí)行上述循環(huán)

所需要的時鐘周期數(shù)。

解：

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

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

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

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

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

總的時鐘周期數(shù)：［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〕

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

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

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

跳轉(zhuǎn)和調(diào)用5%

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

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

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

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

解：沒有控制相關時流水線的平均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;對不成功的條件分支，其目標地址已經(jīng)由PC值給出，

不必等待，所以無延遲：

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

加速比S=CPI/1=1.29

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

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

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

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

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

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

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

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

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

向量中后繼操作數(shù)繼續(xù)以流水方式執(zhí)行，直到整組向量執(zhí)行完畢。

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

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

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

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

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

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

實際吞吐率為多少MFLOPS?

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

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

下圖：

通過時間應該為前者(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章互連網(wǎng)絡

7.1解釋以下術語

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

連接。

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

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

通路。

靜態(tài)互連網(wǎng)絡：各結(jié)點之間有固定的連接通路、且在運行中不能改變的網(wǎng)絡。

動態(tài)互連網(wǎng)絡：由交換開關構(gòu)成、可按運行程序的要求動態(tài)地改變連接狀態(tài)的網(wǎng)絡。

互連網(wǎng)絡：一種由開關元件按照一定的拓撲構(gòu)造和控制方式構(gòu)成的網(wǎng)絡，用來實現(xiàn)計算機系

統(tǒng)中結(jié)點之間的相互連接。在拓撲上，互連網(wǎng)絡是輸入結(jié)點到輸出結(jié)點之間的一組互連或映

象。

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

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

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

網(wǎng)絡直徑：指互連網(wǎng)絡中任意兩個結(jié)點之間距離的最大值。

結(jié)點度：指互連網(wǎng)絡中結(jié)點所連接的邊數(shù)(通道數(shù)

等分帶寬：把由N個結(jié)點構(gòu)成的網(wǎng)絡切成結(jié)點數(shù)一樣(N/2)的兩半，在各種切法中，沿切

口邊數(shù)的最小值。

對稱網(wǎng)絡：從任意結(jié)點來看，網(wǎng)絡的構(gòu)造都是一樣的。

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

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

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

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

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

是采用模塊化構(gòu)造，可擴展性較好。不過，其時延隨網(wǎng)絡級數(shù)的增加而上升。另外，由于其

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

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

自變量是十進制數(shù)表示的處理機編號?，F(xiàn)有32臺處理機，其編號為0,1,2,…，31。

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

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

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

從5號處理機發(fā)送數(shù)據(jù)到7號處理機，最短路徑要經(jīng)過幾步？請列出經(jīng)過的處理機編號。

13)采用移數(shù)網(wǎng)絡構(gòu)成互連網(wǎng)，網(wǎng)絡直徑是多少？結(jié)點度是多少？與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個結(jié)點的均勻洗牌交換網(wǎng)的網(wǎng)絡直徑為2n-1,32個結(jié)點的均勻洗牌交換網(wǎng)的

網(wǎng)絡直徑為9o

從5號處理機發(fā)送數(shù)據(jù)到7號處理機，最短路徑要經(jīng)過6步：

00101-00100-01000^010010010^10011-00111

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

理機。

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

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

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

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

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

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

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

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

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

開關組成的Omega網(wǎng)絡的開關狀態(tài)的種樹為：

一種網(wǎng)絡開關狀態(tài)實現(xiàn)Omega網(wǎng)絡的一種無沖突的置換連接，所以，一次使用Omega

網(wǎng)絡可以實現(xiàn)的無沖突的置換連接有NW2種。

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

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

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

網(wǎng)絡的8個輸出端0~7。如果處理機P6要把數(shù)據(jù)播送給處理機Po~P4,處理機P3要把數(shù)據(jù)

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

播送的Omega網(wǎng)絡的開關狀態(tài)度。

解：Omega網(wǎng)絡使用的2x2開關有4種狀態(tài)：直送、穿插、上播、下播。置換連接只

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

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

送連接。實際上，它們的播送要求沒有沖突，因此，可以同時實現(xiàn)，同時實現(xiàn)的Omega網(wǎng)

絡開關狀態(tài)圖如下所示。

7.9試