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

1、第1章計算機系統(tǒng)結(jié)構(gòu)的根本概念層次機構(gòu)：根據(jù)計算機語言從低級到高級的次序,把計算機系統(tǒng)按功能劃分成多級層次結(jié)構(gòu),每一層以一種不同的語言為特征.這些層次依次為：微程序機器級,傳統(tǒng)機器語言機器級,匯編語言機器級,高級語言機器級,應(yīng)用語言機器級等.虛擬機：用軟件實現(xiàn)的機器.譯：先用轉(zhuǎn)換程序把高一級機器上的程序轉(zhuǎn)換為低一級機器上等效的程序,然后再在這低一級機器上運行,實現(xiàn)程序的功能.解釋：對于高一級機器上的程序中的每一條語句或指令,都是轉(zhuǎn)去執(zhí)行低一級機器上的一段等效程序.執(zhí)行完后,再去高一級機器取下一條語句或指令,再進行解釋執(zhí)行,如此反復(fù),直到解釋執(zhí)行完整個程序.計算機系統(tǒng)結(jié)構(gòu)：傳統(tǒng)機器程序員所看到的

2、計算機屬性,即概念性結(jié)構(gòu)與功能特性.在計算機技術(shù)中,把這種本來存在的事物或?qū)傩?但從某種角度看又好似不存在的概念稱為透明性.計算機組成：計算機系統(tǒng)結(jié)構(gòu)的邏輯實現(xiàn),包含物理機器級中的數(shù)據(jù)流和限制流的組成以及邏輯設(shè)計等.計算機實現(xiàn)：計算機組成的物理實現(xiàn),包括處理機、主存等部件的物理結(jié)構(gòu),器件的集成度和速度,模塊、插件、底板的劃分與連接,信號傳輸,電源、冷卻及整機裝配技術(shù)等.系統(tǒng)加速比：對系統(tǒng)中某局部進行改良時,改良后系統(tǒng)性能提升的倍數(shù).Amdahl定律：當(dāng)對一個系統(tǒng)中的某個部件進行改良后,所能獲得的整個系統(tǒng)性能的提升,受限于該部件的執(zhí)行時間占總執(zhí)行時間的百分比.程序的局部性原理：程序執(zhí)行時所訪問的

3、存儲器地址不是隨機分布的,而是相對地簇聚.包括時間局部性和空間局部性.CPI:每條指令執(zhí)行的平均時鐘周期數(shù).測試程序套件：由各種不同的真實應(yīng)用程序構(gòu)成的一組測試程序,用來測試計算機在各個方面的處理性能.存儲程序計算機：馮諾依曼結(jié)構(gòu)計算機.其根本點是指令驅(qū)動.程序預(yù)先存放在計算機存儲器中,機器一旦啟動,就能根據(jù)程序指定的邏輯順序執(zhí)行這些程序,自動完成由程序所描述的處理工作.系列機：由同一廠家生產(chǎn)的具有相同系統(tǒng)結(jié)構(gòu)、但具有不同組成和實現(xiàn)的一系列不同型號的計算機.軟件兼容：一個軟件可以不經(jīng)修改或者只需少量修改就可以由一臺計算機移植到另一臺計算機上運行.差異只是執(zhí)行時間的不同.向上下兼容：按某檔計算機

4、編制的程序,不加修改就能運行于比它高低檔的計算機.向后前兼容：按某個時期投入市場的某種型號計算機編制的程序,不加修改地就能運行于在它之后前投入市場的計算機.兼容機：由不同公司廠家生產(chǎn)的具有相同系統(tǒng)結(jié)構(gòu)的計算機.模擬：用軟件的方法在一臺現(xiàn)有的計算機稱為宿主機上實現(xiàn)另一臺計算機稱為虛擬機的指令系統(tǒng).仿真：用一臺現(xiàn)有計算機稱為宿主機上的微程序去解釋實現(xiàn)另一臺計算機稱為目標(biāo)機的指令系統(tǒng).并行性：計算機系統(tǒng)在同一時刻或者同一時間間隔內(nèi)進行多種運算或操作.只要在時間上相互重疊,就存在并行性.它包括同時性與并發(fā)性兩種含義.時間重疊：在并行性概念中引入時間因素,讓多個處理過程在時間上相互錯開,輪流重疊地使用同

5、一套硬件設(shè)備的各個局部,以加快硬件周轉(zhuǎn)而贏得速度.資源重復(fù)：在并行性概念中引入空間因素,以數(shù)量取勝.通過重復(fù)設(shè)置硬件資源,大幅度地提升計算機系統(tǒng)的性能.資源共享：這是一種軟件方法,它使多個任務(wù)按一定時間順序輪流使用同一套硬件設(shè)備.耦合度：反映多機系統(tǒng)中各計算機之間物理連接的緊密程度和交互作用水平的強弱.緊密耦合系統(tǒng)：又稱直接耦合系統(tǒng).在這種系統(tǒng)中,計算機之間的物理連接的頻帶較高,一般是通過總線或高速開關(guān)互連,可以共享主存.(磁松散耦合系統(tǒng)：又稱間接耦合系統(tǒng),一般是通過通道或通信線路實現(xiàn)計算機之間的互連,可以共享外存設(shè)備盤、磁帶等).計算機之間的相互作用是在文件或數(shù)據(jù)集一級上進行.異構(gòu)型多處理機

6、系統(tǒng)：由多個不同類型、至少擔(dān)負(fù)不同功能的處理機組成,它們根據(jù)作業(yè)要求的順序,利用時間重疊原理,依次對它們的多個任務(wù)進行加工,各自完成規(guī)定的功能動作.同構(gòu)型多處理機系統(tǒng)：由多個同類型或至少擔(dān)負(fù)同等功能的處理機組成,它們同時處理同一作業(yè)中能并行執(zhí)行的多個任務(wù).試用實例說明計算機系統(tǒng)結(jié)構(gòu)、計算機組成與計算機實現(xiàn)之間的相互關(guān)系.答：如在設(shè)計主存系統(tǒng)時,確定主存容量、編址方式、尋址范圍等屬于計算機系統(tǒng)結(jié)構(gòu).確定主存周期、邏輯上是否采用并行主存、邏輯設(shè)計等屬于計算機組成.選擇存儲芯片類型、微組裝技術(shù)、線路設(shè)計等屬于計算機實現(xiàn).計算機組成是計算機系統(tǒng)結(jié)構(gòu)的邏輯實現(xiàn).計算機實現(xiàn)是計算機組成的物理實現(xiàn).一種體系

7、結(jié)構(gòu)可以有多種組成.一種組成可以有多種實現(xiàn).計算機系統(tǒng)結(jié)構(gòu)的Flynn分類法是按什么來分類的？共分為哪幾類？答：Flynn分類法是根據(jù)指令流和數(shù)據(jù)流的多倍性進行分類.把計算機系統(tǒng)的結(jié)構(gòu)分為:(1) 單指令流單數(shù)據(jù)流SISD(2) 單指令流多數(shù)據(jù)流SIMD(3) 多指令流單數(shù)據(jù)流MISD(4) 多指令流多數(shù)據(jù)流MIMD計算機系統(tǒng)設(shè)計中經(jīng)常使用的4個定量原理是什么？并說出它們的含義.答：(1)以經(jīng)常性事件為重點.在計算機系統(tǒng)的設(shè)計中,對經(jīng)常發(fā)生的情況,賦予它優(yōu)先的處理權(quán)和資源使用權(quán),以得到更多的總體上的改良.(2)Amdahl定律.加快某部件執(zhí)行速度所獲得的系統(tǒng)性能加速比,受限于該部件在系統(tǒng)中所占

8、的重要性.(3)CPU性能公式.執(zhí)行一個程序所需的CPU時間=ICXCPIx時鐘周期時間.(4)程序的局部性原理.程序在執(zhí)行時所訪問地址的分布不是隨機的,而是相對地簇聚.分別從執(zhí)行程序的角度和處理數(shù)據(jù)的角度來看,計算機系統(tǒng)中并行性等級從低到高可分為哪幾級？答：從處理數(shù)據(jù)的角度來看,并行性等級從低到高可分為：(1)字串位串：每次只對一個字的一位進行處理.這是最根本的串行處理方式,不存在并行性；(2)字串位并：同時對一個字的全部位進行處理,不同字之間是串行的.已開始出現(xiàn)并行性；(3)字并位串：同時對許多字的同一位(稱為位片)進行處理.這種方式具有較高的并行性；(4)全并行：同時對許多字的全部位或局

9、部位進行處理.這是最高一級的并行.從執(zhí)行程序的角度來看,并行性等級從低到高可分為：(1)指令內(nèi)部并行：單條指令中各微操作之間的并行；(2)指令級并行：并行執(zhí)行兩條或兩條以上的指令；(3)線程級并行：并行執(zhí)行兩個或兩個以上的線程,通常是以一個進程內(nèi)派生的多個線程為調(diào)度單位；(4)任務(wù)級或過程級并行：并行執(zhí)行兩個或兩個以上的過程或任務(wù)(程序段),以子程序或進程為調(diào)度單元；(5)作業(yè)或程序級并行：并行執(zhí)行兩個或兩個以上的作業(yè)或程序.某臺主頻為400MHz的計算機執(zhí)行標(biāo)準(zhǔn)測試程序,程序中指令類型、執(zhí)行數(shù)量和平均時鐘周期數(shù)如下:指令類型指令執(zhí)行數(shù)量平均時鐘周期數(shù)整數(shù)450001數(shù)據(jù)傳送750002浮點8

10、0004分支15002求該計算機的有效CPI、MIPS和程序執(zhí)行時間.解：(1)CPI=(45000X1+75000X2+8000X4+1500X(2)MIPS速率=f(3)程序執(zhí)行時間=(45000X1+75000X2+8000X4+1500X2)/400=575s40%,那么采將計算機系統(tǒng)中某一功能的處理速度加快10倍,但該功能的處理時間僅為整個系統(tǒng)運行時間的用此增強功能方法后,能使整個系統(tǒng)的性能提升多少？解由題可知：可改良比例=40%=部件加速比=10根據(jù)Amdahl定律可知：采用此增強功能方法后,能使整個系統(tǒng)的性能提升到原來的倍.計算機系統(tǒng)中有三個部件可以改良,這三個部件的部件加速比為

11、：部件加速比1=30；部件加速比2=20；部件加速比3=10(1) 如果部件1和部件2的可改良比例均為30%,那么當(dāng)部件3的可改良比例為多少時,系統(tǒng)加速比才可以到達10?(2) 如果三個部件的可改良比例分別為30%、30%和20%,三個部件同時改良,那么系統(tǒng)中不可加速部分的執(zhí)行時間在總執(zhí)行時間中占的比例是多少？解：(1)在多個部件可改良情況下,Amdahl定理的擴展：S1=30,S2=20,S3=10,Sn=10,F12得F33的可改良比例為36%.3個部件改良后的加速比分別為S=30,S2=20,S3=10,因此3個部件改良后的執(zhí)行時間為：那么系統(tǒng)中不可改良局部的執(zhí)行時間在總執(zhí)行時間中占的比

12、例是：假設(shè)某應(yīng)用程序中有4類操作,通過改良,各操作獲得不同的性能提升.具體數(shù)據(jù)如下表所示：操作類型程序中的數(shù)量(百萬條指令)改良前的執(zhí)行時間(周期)改良后的執(zhí)行時間(周期)操彳11021操彳2302015操彳335103操彳41541(1)改良后,各類操作的加速比分別是多少？(2)各類操作單獨改良后,程序獲得的加速比分別是多少?(3) 4類操作均改良后,整個程序的加速比是多少？解：根據(jù)Amdahl定彳tSn1(1Fe)s可得操作類型各類操作的指令條數(shù)在程序中所占的比例Fi各類操作的加速比Si各類操作單獨改良后,程序獲得的加速比操彳112操彳2操彳3操彳4144類操作均改良后,整個程序的加速比:

13、第2章指令集結(jié)構(gòu)的分類2.1 解釋以下術(shù)語堆棧型機器：CPU中存儲操作數(shù)的單元是堆棧的機器.累加器型機器：CPU中存儲操作數(shù)的單元是累加器的機器.通用存放器型機器：CPU中存儲操作數(shù)的單元是通用存放器的機器.CISC:復(fù)雜指令集計算機RISC:精簡指令集計算機尋址方式：指令系統(tǒng)中如何形成所要訪問的數(shù)據(jù)的地址.一般來說,尋址方式可以指明指令中的操作數(shù)是一個常數(shù)、一個存放器操作數(shù)或者是一個存儲器操作數(shù).數(shù)據(jù)表示：硬件結(jié)構(gòu)能夠識別、指令系統(tǒng)可以直接調(diào)用的那些數(shù)據(jù)結(jié)構(gòu).2.2 區(qū)別不同指令集結(jié)構(gòu)的主要因素是什么？根據(jù)這個主要因素可將指令集結(jié)構(gòu)分為哪3類？答：區(qū)別不同指令集結(jié)構(gòu)的主要因素是CPU中用來存

14、儲操作數(shù)的存儲單元.據(jù)此可將指令系統(tǒng)結(jié)構(gòu)分為堆棧結(jié)構(gòu)、累加器結(jié)構(gòu)和通用存放器結(jié)構(gòu).2.3 常見的3種通用存放器型指令集結(jié)構(gòu)的優(yōu)缺點有哪些？答：指令系統(tǒng)結(jié)構(gòu)類型優(yōu)點缺點存放器-存放器型0,3指令字長固定,指令結(jié)構(gòu)簡潔,是一種簡單的代碼生成模型,各種指令的執(zhí)行時鐘周期數(shù)相近.與指令中含存儲器操作數(shù)的指令系統(tǒng)結(jié)構(gòu)相比,指令條數(shù)多,目標(biāo)代碼不夠緊湊,因而程序占用的空間比擬大.存放器-存儲器型1,2可以在ALU指令中直接對存儲器操作數(shù)進行引用,而不必先用load指令進行加載.容易對指令進行編碼,目標(biāo)代碼比擬緊湊.由于有一個操作數(shù)的內(nèi)容將被破壞,所以指令中的兩個操作數(shù)不對稱.在一條指令中同時對存放器操作數(shù)

15、和存儲器操作數(shù)進行編碼,有可能限制指令所能夠表示的存放器個數(shù).指令的執(zhí)行時鐘周期數(shù)因操作數(shù)的來源存放器或存儲器不同而差異比擬大.存儲器-存儲器型2,2或3,3目標(biāo)代碼最緊湊,不需要設(shè)置存放器來保存變量.指令字長變化很大,特別是3操作數(shù)指令.而且每條指令完成的工作也差異很大.對存儲器的頻繁訪問會使存儲器成為瓶頸.這種類型的指令系統(tǒng)現(xiàn)在已不用了.2.4 指令集應(yīng)滿足哪幾個根本要求？答：對指令集的根本要求是：完整性、規(guī)整性、高效率和兼容性.完整性是指在一個有限可用的存儲空間內(nèi),對于任何可解的問題,編制計算程序時,指令集所提供的指令足夠使用.規(guī)整性主要包括對稱性和均勻性.對稱性是指所有與指令集有關(guān)的存

16、儲單元的使用、操作碼的設(shè)置等都是對稱的.均勻性是指對于各種不同的操作數(shù)類型、字長、操作種類和數(shù)據(jù)存儲單元,指令的設(shè)置都要同等對待.高效率是指指令的執(zhí)行速度快、使用頻度高.2.5 指令集結(jié)構(gòu)設(shè)計所涉及的內(nèi)容有哪些？答：1指令集功能設(shè)計：主要有RISC和CISC兩種技術(shù)開展方向；2尋址方式的設(shè)計：設(shè)置尋址方式可以通過對基準(zhǔn)程序進行測試統(tǒng)計,觀察各種尋址方式的使用頻率,根據(jù)適用頻率設(shè)置必要的尋址方式.3操作數(shù)表示和操作數(shù)類型：主要的操作數(shù)類型和操作數(shù)表示的選擇有：浮點數(shù)據(jù)類型、整型數(shù)據(jù)類型、字符型、十進制數(shù)據(jù)類型等等.4尋址方式的表示：可以將尋址方式編碼于操作碼中,也可以將尋址方式作為一個單獨的域來

17、表示.5指令集格式的設(shè)計：有變長編碼格式、固定長度編碼格式和混合型編碼格式3種.2.6 簡述CISC指令集結(jié)構(gòu)功能設(shè)計的主要目標(biāo).從當(dāng)前的計算機技術(shù)觀點來看,CISC指令集結(jié)構(gòu)的計算機有什么缺點？答：主要目標(biāo)是增強指令功能,把越來越多的功能交由硬件來實現(xiàn),并且指令的數(shù)量也是越來越多.缺點：1CISC結(jié)構(gòu)的指令集中,各種指令的使用頻率相差懸殊.2CISC結(jié)構(gòu)指令的復(fù)雜性帶來了計算機體系結(jié)構(gòu)的復(fù)雜性,這不僅增加了研制時間和本錢,而且還容易造成設(shè)計錯誤.3CISC結(jié)構(gòu)指令集的復(fù)雜性給VLSI設(shè)計增加了很大負(fù)擔(dān),不利于單片集成.4CISC結(jié)構(gòu)的指令集中,許多復(fù)雜指令需要很復(fù)雜的操作,因而運行速度慢.5

18、在CISC結(jié)構(gòu)的指令集中,由于各條指令的功能不均衡性,不利于采用先進的計算機體系結(jié)構(gòu)技術(shù)如流水技術(shù)來提升系統(tǒng)的性能.2.7 簡述RISC指令集結(jié)構(gòu)的設(shè)計原那么.答1選取使用頻率最高的指令,并補充一些最有用的指令；2每條指令的功能應(yīng)盡可能簡單,并在一個機器周期內(nèi)完成；3所有指令長度均相同；4只有Load和Store操作指令才訪問存儲器,其它指令操作均在存放器之間進行；5以簡單有效的方式支持高級語言.2.8 指令中表示操作數(shù)類型的方法有哪幾種？答：操作數(shù)類型有兩種表示方法：1操作數(shù)的類型由操作碼的編碼指定,這是最常見的一種方法；2數(shù)據(jù)可以附上由硬件解釋的標(biāo)記,由這些標(biāo)記指定操作數(shù)的類型,從而選擇適

19、當(dāng)?shù)倪\算.2.9 表示尋址方式的主要方法有哪些？簡述這些方法的優(yōu)缺點.答：表示尋址方式有兩種常用的方法：1將尋址方式編于操作碼中,由操作碼在描述指令的同時也描述了相應(yīng)的尋址方式.這種方式譯碼快,但操作碼和尋址方式的結(jié)合不僅增加了指令的條數(shù),導(dǎo)致了指令的多樣性,而且增加了CPU寸指令譯碼的難度.2為每個操作數(shù)設(shè)置一個地址描述符,由該地址描述符表示相應(yīng)操作數(shù)的尋址方式.這種方式譯碼較慢,但操作碼和尋址獨立,易于指令擴展.2.10 通常有哪幾種指令格式,請簡述其適用范圍.答：1變長編碼格式.如果系統(tǒng)結(jié)構(gòu)設(shè)計者感興趣的是程序的目標(biāo)代碼大小,而不是性能,就可以采用變長編碼格式.2固定長度編碼格式.如果感

20、興趣的是性能,而不是程序的目標(biāo)代碼大小,那么可以選擇固定長度編碼格式.3混合型編碼格式.需要兼顧降低目標(biāo)代碼長度和降低譯碼復(fù)雜度時,可以采用混合型編碼格式.2.11 根據(jù)CPU性能公式簡述RISC指令集結(jié)構(gòu)計算機和CISC指令集結(jié)構(gòu)計算機的性能特點.答：CPU性能公式：CPU時間=ICXCPIXT其中,IC為目標(biāo)程序被執(zhí)行的指令條數(shù),CPI為指令平均執(zhí)行周期數(shù),T是時鐘周期的時間.相同功能的CISC目標(biāo)程序的指令條數(shù)ICcisc少于RISC的ICrisc,但是CISC的CPIcisc和Tcisc都大于RISC的CPIrisc和Trisc,因此,CISC目標(biāo)程序的執(zhí)行時間比RISC的更長.第3章

21、流水線技術(shù)解釋以下術(shù)語流水線：將一個重復(fù)的時序過程,分解成為假設(shè)干個子過程,而每一個子過程都可有效地在其專用功能段上與其它子過程同時執(zhí)行.單功能流水線：指流水線的各段之間的連接固定不變、只能完成一種固定功能的流水線.多功能流水線：指各段可以進行不同的連接,以實現(xiàn)不同的功能的流水線.靜態(tài)流水線：指在同一時間內(nèi),多功能流水線中的各段只能按同一種功能的連接方式工作的流水線.當(dāng)流水線要切換到另一種功能時,必須等前面的任務(wù)都流出流水線之后,才能改變連接.動態(tài)流水線：指在同一時間內(nèi),多功能流水線中的各段可以根據(jù)不同的方式連接,同時執(zhí)行多種功能的流水線.它允許在某些段正在實現(xiàn)某種運算時,另一些段卻在實現(xiàn)另一

22、種運算.部件級流水線：把處理機中的部件進行分段,再把這些部件分段相互連接而成.它使得運算操作能夠按流水方式進行.這種流水線也稱為運算操作流水線.處理機級流水線：又稱指令流水線.它是把指令的執(zhí)行過程根據(jù)流水方式進行處理,即把一條指令的執(zhí)行過程分解為假設(shè)干個子過程,每個子過程在獨立的功能部件中執(zhí)行.處理機間流水線：又稱為宏流水線.它是把多個處理機串行連接起來,對同一數(shù)據(jù)流進行處理,每個處理機完成整個任務(wù)中的一局部.前一個處理機的輸出結(jié)果存入存儲器中,作為后一個處理機的輸入.線性流水線：指各段串行連接、沒有反應(yīng)回路的流水線.數(shù)據(jù)通過流水線中的各段時,每一個段最多只流過一次.非線性流水線：指各段除了有

23、串行的連接外,還有反應(yīng)回路的流水線.順序流水線：流水線輸出端任務(wù)流出的順序與輸入端任務(wù)流入的順序完全相同.亂序流水線：流水線輸出端任務(wù)流出的順序與輸入端任務(wù)流入的順序可以不同,允許后進入流水線的任務(wù)先完成.這種流水線又稱為無序流水線、錯序流水線、異步流水線.吞吐率：在單位時間內(nèi)流水線所完成的任務(wù)數(shù)量或輸出結(jié)果的數(shù)量.流水線的加速比：使用順序處理方式處理一批任務(wù)所用的時間與按流水處理方式處理同一批任務(wù)所用的時間之比.流水線的效率：即流水線設(shè)備的利用率,它是指流水線中的設(shè)備實際使用時間與整個運行時間的比值.數(shù)據(jù)相關(guān)：考慮兩條指令i和j,i在j的前面,如果下述條件之一成立,那么稱指令j與指令i數(shù)據(jù)相

24、關(guān)：1指令j使用指令i產(chǎn)生的結(jié)果；(2)指令j與指令k數(shù)據(jù)相關(guān),而指令k又與指令i數(shù)據(jù)相關(guān).名相關(guān)：如果兩條指令使用了相同的名,但是它們之間并沒有數(shù)據(jù)流動,那么稱這兩條指令存在名相關(guān).限制相關(guān)：是指由分支指令引起的相關(guān).它需要根據(jù)分支指令的執(zhí)行結(jié)果來確定后面該執(zhí)行哪個分支上的指令.反相關(guān)：考慮兩條指令i和j,i在j的前面,如果指令j所寫的名與指令i所讀的名相同,那么稱指令i和j發(fā)生了反相關(guān).輸出相關(guān)：考慮兩條指令i和j,i在j的前面,如果指令j和指令i所寫的名相同,那么稱指令i和j發(fā)生了輸出相關(guān).換名技術(shù)：名相關(guān)的兩條指令之間并沒有數(shù)據(jù)的傳送,只是使用了相同的名.可以把其中一條指令所使用的名換

25、成別的,以此來消除名相關(guān).結(jié)構(gòu)沖突：因硬件資源滿足不了指令重疊執(zhí)行的要求而發(fā)生的沖突.數(shù)據(jù)沖突：當(dāng)指令在流水線中重疊執(zhí)行時,因需要用到前面指令的執(zhí)行結(jié)果而發(fā)生的沖突.限制沖突：流水線遇到分支指令或其它會改變PC值的指令所引起的沖突.定向：用來解決寫后讀沖突的.在發(fā)生寫后讀相關(guān)的情況下,在計算結(jié)果尚未出來之前,后面等待使用該結(jié)果的指令并不見得是馬上就要用該結(jié)果.如果能夠?qū)⒃撚嬎憬Y(jié)果從其產(chǎn)生的地方直接送到其它指令需要它的地方,那么就可以防止停頓.寫后讀沖突：考慮兩條指令i和j,且i在j之前進入流水線,指令j用到指令i的計算結(jié)果,而且在i將結(jié)果寫入存放器之前就去讀該存放器,因而得到的是舊值.讀后寫沖

26、突：考慮兩條指令i和j,且i在j之前進入流水線,指令j的目的存放器和指令i的源操作數(shù)存放器相同,而且j在i讀取該存放器之前就先對它進行了寫操作,導(dǎo)致i讀到的值是錯誤的.寫后寫沖突：考慮兩條指令i和j,且i在j之前進入流水線,指令j和指令i的結(jié)果單元(存放器或存儲器單元)相同,而且j在i寫入之前就先對該單元進行了寫入操作,從而導(dǎo)致寫入順序錯誤.這時在結(jié)果單元中留下的是i寫入的值,而不是j寫入的.鏈接技術(shù)：具有先寫后讀相關(guān)的兩條指令,在不出現(xiàn)功能部件沖突和Vi沖突的情況下,可以把功能部件鏈接起來進行流水處理,以到達加快執(zhí)行的目的.分段開采：當(dāng)向量的長度大于向量存放器的長度時,必須把長向量分成長度固

27、定的段,然后循環(huán)分段處理,每一次循環(huán)只處理一個向量段.半性能向量長度：向量處理機的性能為其最大性能R的一半時所需的向量長度.向量長度臨界值：向量流水方式的處理速度優(yōu)于標(biāo)量串行方式的處理速度時所需的向量長度的最小值.答：(1)指令的順序執(zhí)行是指指令與指令之間順序串行.即上一條指令全部執(zhí)行完后,才能開始執(zhí)行下一條指令.優(yōu)點：限制簡單,節(jié)省設(shè)備.缺點：執(zhí)行指令的速度慢,功能部件的利用率低.(2)指令的重疊指令是在相鄰的指令之間,讓第k條指令與取第k+l條指令同時進行.重疊執(zhí)行不能加快單條指令的執(zhí)行速度,但在硬件增加不多的情況下,可以加快相鄰兩條指令以及整段程序的執(zhí)行速度.與順序方式相比,功能部件的利

28、用率提升了,限制變復(fù)雜了.(3)指令的流水執(zhí)行是把一個指令的執(zhí)行過程分解為假設(shè)干個子過程,每個子過程由專門的功能部件來實現(xiàn).把多個處理過程在時間上錯開,依次通過各功能段,每個子過程與其它的子過程并行進行.依靠提升吞吐率來提升系統(tǒng)性能.流水線中各段的時間應(yīng)盡可能相等答：先行限制技術(shù)是把緩沖技術(shù)和預(yù)處理技術(shù)相結(jié)合.緩沖技術(shù)是在工作速度不固定的兩個功能部件之間設(shè)置緩沖器,用以平滑它們的工作.預(yù)處理技術(shù)是指預(yù)取指令、對指令進行加工以及預(yù)取操作數(shù)等.采用先行限制方式的處理機內(nèi)部設(shè)置多個緩沖站,用于平滑主存、指令分析部件、運算器三者之間的工作.這樣不僅使它們都能獨立地工作,充分忙碌而不用相互等待,而且使指

29、令分析部件和運算器分別能快速地取得指令和操作數(shù),大幅度地提升指令的執(zhí)行速度和部件的效率.這些緩沖站都按先進先出的方式工作,而且都是由一組假設(shè)干個能快速訪問的存儲單元和相關(guān)的限制邏輯組成.采用先行限制技術(shù)可以實現(xiàn)多條指令的重疊解釋執(zhí)行.t、At和2At.分別求出以下各種情況下,連續(xù)執(zhí)行N條指令所需的時間.(1)順序執(zhí)行方式；(2)只有“取指令與“執(zhí)行指令重疊；(3)“取指令、“分析指令與“執(zhí)行指令重疊.解：(1)每條指令的執(zhí)行時間為：t+At+2At=4At連續(xù)執(zhí)行N條指令所需的時間為：4NAt(2)連續(xù)執(zhí)行N條指令所需的時間為：4At+3(N-1)At=(3N+1)At(3)連續(xù)執(zhí)行N條指令所

30、需的時間為：4At+2(N-1)At=(2N+2)At簡述流水線技術(shù)的特點.答：流水技術(shù)有以下特點：(1)流水線把一個處理過程分解為假設(shè)干個子過程,每個子過程由一個專門的功能部件來實現(xiàn).因此,流水線實際上是把一個大的處理功能部件分解為多個獨立的功能部件,并依靠它們的并行工作來提升吞吐率.(2)流水線中各段的時間應(yīng)盡可能相等,否那么將引起流水線堵塞和斷流.(3)流水線每一個功能部件的前面都要有一個緩沖存放器,稱為流水存放器.(4)流水技術(shù)適合于大量重復(fù)的時序過程,只有在輸入端不斷地提供任務(wù),才能充分發(fā)揮流水線的效率.(5)流水線需要有通過時間和排空時間.在這兩個時間段中,流水線都不是滿負(fù)荷工作.

31、答：細(xì)分瓶頸段與重復(fù)設(shè)置瓶頸段流水線分支延遲的靜態(tài)方法有哪些？答：(1)預(yù)測分支失敗：沿失敗的分支繼續(xù)處理指令,就好象什么都沒發(fā)生似的.當(dāng)確定分支是失敗時,說明預(yù)測正確,流水線正常流動；當(dāng)確定分支是成功時,流水線就把在分支指令之后取出的指令轉(zhuǎn)化為空操作,并按分支目標(biāo)地址重新取指令執(zhí)行.(2)預(yù)測分支成功：當(dāng)流水線ID段檢測到分支指令后,一旦計算出了分支目標(biāo)地址,就開始從該目標(biāo)地址取指令執(zhí)行.(3)延遲分支：主要思想是從邏輯上“延長分支指令的執(zhí)行時間.把延遲分支看成是由原來的分支指令和假設(shè)干個延遲槽構(gòu)成.不管分支是否成功,都要按順序執(zhí)行延遲槽中的指令.3種方法的共同特點：它們對分支的處理方法在程

32、序的執(zhí)行過程中始終是不變的.它們要么總是預(yù)測分支成功,要么總是預(yù)測分支失敗.延遲分支方法中的三種調(diào)度策略的優(yōu)缺點.調(diào)度策略對調(diào)度的要求對流水線性能改善的影響從前調(diào)度分支必須不依賴于被調(diào)度的指令總是可以有效提升流水線性能從目標(biāo)處調(diào)度如果分支轉(zhuǎn)移失敗,必須保證被調(diào)度的指令對程序的執(zhí)行沒有影響,可能需要復(fù)制被調(diào)度指令分支轉(zhuǎn)移成功時,可以提升流水線性能.但由于復(fù)制指令,可能加大程序空間從失敗處調(diào)度如果分支轉(zhuǎn)移成功,必須保證被調(diào)度的指令對程序的執(zhí)行沒有影響分支轉(zhuǎn)移失敗時,可以提升流水線性能列舉出下面循環(huán)中的所有相關(guān),包括輸出相關(guān)、反相關(guān)、真相關(guān)for(i=2;i<100;i=i+1)ai=bi+a

33、i;/*s1*/ci+1=ai+di;/*s2*/ai-1=2*bi;/*s3*/bi+1=2*bi;/*s4*/;/*s1*/;/*s2*/;/*s3*/解：展開循環(huán)兩次：ai=bi+aici+1=ai+diai-1=2*bibi+1=2*biai+1=bi+1+ai+1ci+2=ai+1+di+1ai=2*bi+1bi+2=2*bi+1輸出相關(guān)：無反相關(guān)：無真相關(guān)：S1&S2由于循環(huán)引入的相關(guān)：S4&S4'相關(guān)、反相關(guān))、S2&S3'(反相關(guān))/*s4*/*si/*s2/*S3/*s4真相關(guān)、*/*/*/*/Si'&S4真相關(guān)、S3&

34、#39;&S4真相關(guān)、S1&S3'輸出簡述三種向量處理方式,它們對向量處理機的結(jié)構(gòu)要求有何不同？答1橫向處理方式：假設(shè)向量長度為N,那么水平處理方式相當(dāng)于執(zhí)行環(huán)中可能出現(xiàn)數(shù)據(jù)相關(guān)和功能轉(zhuǎn)換,不適合對向量進行流水處理ON次循環(huán).假設(shè)使用流水線,在每次循縱向處理方式：將整個向量按相同的運算處理完畢之后,再去執(zhí)行其他運算.適合對向量進行流水處理,向量運算指令的源使得流水線運算部件的輸入、輸出端直接與存儲器相聯(lián),構(gòu)成M-M型的運算流水線.為N的向量分為假設(shè)干組,每組長度為n,組內(nèi)按縱向方式處理,依次處理各組,組數(shù)為/目向量都放在存儲器內(nèi),3縱橫處理方式：把長度N/n,適合流水處

35、理.可設(shè)長度為n的向量存放器,使每組向量運算的源/目向量都在向量存放器中,流水線的運算部件輸入、輸出端與向量答:存器相聯(lián),構(gòu)成R-R型運算流水線.可采用多種方法：(1)(2)(3)(4)設(shè)置多個功能部件,使它們并行工作；采用鏈接技術(shù),加快一串向量指令的執(zhí)行；采用循環(huán)開采技術(shù),加快循環(huán)的處理；采用多處理機系統(tǒng),進一步提iWj性能.有一指令流水線如下所示1求連續(xù)輸入10條指令,該流水線的實際吞吐率和效率；瓶頸.對于你所給出的兩種新的流水2該流水線的瓶頸在哪一段？請采取兩種不同的舉措消除此線,連續(xù)輸入10條指令時,其實際吞吐率和效率各是多少?解：14段.細(xì)分2瓶頸在3、變成八級流水線重復(fù)設(shè)置部件有一

36、個流水線由4段組成,其中每當(dāng)流經(jīng)第3段時,總要在該段循環(huán)一次,然后才能流到第4段.如果每段經(jīng)過一次所需要的時間都是t,問:(1)(2)當(dāng)在流水線的輸入端連續(xù)地每t時間輸入任務(wù)時,該流水線會發(fā)生什么情況?此流水線的最大吞吐率為多少？如果每2t輸入一個任務(wù),連續(xù)處理10個任務(wù)時的實際吞吐率和效(3)率是多少？當(dāng)每段時間不變時,如何提升該流水線的吞吐率？仍連續(xù)處理10個任務(wù)時,其吞吐率提升多少?第1個任務(wù)S1S2S3S3S4第2個任務(wù)S1S2stallS3S3S4第3個任務(wù)S1stallS2stallS3S3S4解：1會發(fā)生流水線阻塞情況.第4個任務(wù)S1stallS2stallS3S3S4(2)(3

37、)重復(fù)設(shè)置部件5吞吐率提升倍數(shù)=1023t靜態(tài)多功能流水線由5段組成,加法用1、3、4、5段,乘法用1、2、5段,第3段的時間為2At,其余各段的時間均為t,而且流水線的輸出可以直接返回輸入端或暫存于相應(yīng)的流水存放器中.現(xiàn)要在該流水線上計算,畫出其時空圖,并計算其吞吐率、加速比和效率.解：首先,應(yīng)選擇適合于流水線工作的算法.對于此題,應(yīng)先計算A1+B1、A2+B2、A3+B3和A4+B4；再入A1A2A3A4ACAXBB1B2B3B4BDCXD由圖可見,它在18個At時間中,給出了7個結(jié)果.所以吞吐率為：如果不用流水線,由于一次求積需3At,一次求和需5At,那么產(chǎn)生上述7個結(jié)果共需(4X5+

38、3X3)At=29Ato所以加速比為：該流水線的效率可由陰影區(qū)的面積和5個段總時空區(qū)的面積的比值求得：其中,S1、S4、S5、S6組成乘法流水線,S1、S2、S3、S6組成加法流水線,各個功能段時間均為50ns,假設(shè)該流水線的輸出結(jié)果可以直接返回輸入端,而且設(shè)置有足夠的緩沖存放器,假設(shè)以最快的方式用該流水計算：5XiyiZii1(1)畫出時空圖；(2)計算實際的吞吐率、加速比和效率.解：機器一共要做10次乘法,4次加法.在MIPS流水線上運行如下代碼序列：LOOP:LWR1,0(R2)DADDIUR1,R1,#1SWR1,0(R2)DADDIUR2,R2,#4DSUBR4,R3,R2其中：R3

39、的初值是R2+396BNEZR4,LOOP假設(shè)：在整個代碼序列的運行過程中,所有的存儲器訪問都是命中的,并且在一個時鐘周期中對同一個存放器的讀操作和寫操作可以通過存放器文件定向.問:(1)在沒有任何其它定向(或旁路)硬件的支持下,請畫出該指令序列執(zhí)行的流水線時空圖.假設(shè)采用排空流水線的策略處理分支指令,且所有的存儲器訪問都命中Cache,那么執(zhí)行上述循環(huán)需要多少個時鐘周期？(2)假設(shè)該流水線有正常的定向路徑,請畫出該指令序列執(zhí)行的流水線時空圖.假設(shè)采用預(yù)測分支失敗的策略處理分支指令,且所有的存儲器訪問都命中Cache,那么執(zhí)行上述循環(huán)需要多少個時鐘周期？(3)假設(shè)該流水線有正常的定向路徑和一個

40、單周期延遲分支,請對該循環(huán)中的指令進行調(diào)度,你可以重新組織指令的順序,也可以修改指令的操作數(shù),但是注意不能增加指令的條數(shù).請畫出該指令序列執(zhí)行的流水線時空圖,并計算執(zhí)行上述循環(huán)所需要的時鐘周期數(shù).解：存放器讀寫可以定向,無其他旁路硬件支持.排空流水線.第i次迭代(i=0.98)開始周期：1+(ix17)總的時鐘周期數(shù)：(98X17)+18=1684有正常定向路徑,預(yù)測分支失敗.第i次迭代(i=0.98)開始周期：1+(ix10)總的時鐘周期數(shù)：(98X10)+11=991有正常定向路徑.單周期延遲分支.LOOP:LWR1,0(R2)DADDIUDADDIUR2,R2,#4R1,R1,#1DSU

41、BR4,R3,R2BNEZR4,LOOPSW第i次迭代(i二R1,-4(R2)=0.98)開始周期：1+(iX6)總的時鐘周期數(shù)：(98X6)+10=598假設(shè)各種分支指令數(shù)占所有指令數(shù)的百分比方下:條件分支20%(其中的60%是分支成功的)跳轉(zhuǎn)和調(diào)用5%現(xiàn)有一條段數(shù)為4的流水線,無條件分支在第二個時鐘周期結(jié)束時就被解析出來,而條件分支要到第三個時鐘周期結(jié)束時才能夠被解析出來.第一個流水段是完全獨立于指令類型的,即所有類型的指令都必須經(jīng)過第一個流水段的處理.請問在沒有任何限制相關(guān)的情況下,該流水線相對于存在上述限制相關(guān)情況下的加速比是多少？解：沒有限制相關(guān)時流水線的平均CPI=1存在限制相關(guān)時

42、：由于無條件分支在第二個時鐘周期結(jié)束時就被解析出來,而條件分支要到第3個時鐘周期結(jié)束時才能被解析出來.所以：(1)假設(shè)使用排空流水線的策略,那么對于條件分支,有兩個額外的stall,對無條件分支,有一個額外的stall:(2)假設(shè)使用預(yù)測分支成功策略,那么對于不成功的條件分支,有兩個額外的stall,對無條件分支和成功的條件分支,有一個額外的stall1:(3)假設(shè)使用預(yù)測分支失敗策略,那么對于成功的條件分支,有兩個額外的stall；對無條件分支,有一個額外的stall；對不成功的條件分支,其目標(biāo)地址已經(jīng)由PC值給出,不必等待,所以無延遲：在CRAY-1機器上,根據(jù)鏈接方式執(zhí)行下述4條向量指令

43、括號中給出了相應(yīng)功能部件的執(zhí)行時間,如果向量存放器和功能部件之間的數(shù)據(jù)傳送需要1拍,試求此鏈接流水線的通過時間是多少拍？如果向量長度為64,那么需多少拍才能得到全部結(jié)果？V0-存儲器從存儲器中取數(shù)：7拍V2V0+Vi向量加：3拍V322VA3按A3左移：4拍V5-V3AV4向量邏輯乘：2拍解：通過時間就是每條向量指令的第一個操作數(shù)執(zhí)行完畢需要的時間,也就是各功能流水線由空到滿的時間,具體過程如以下圖所示.要得到全部結(jié)果,在流水線充滿之后,向量中后繼操作數(shù)繼續(xù)以流水方式執(zhí)行,直到整組向量執(zhí)行完畢.某向量處理機有16個向量存放器,其中VoV5中分別放有向量A、B、C、D、E、F,向量長度均為8,向

44、量各元素均為浮點數(shù)；處理部件采用兩條單功能流水線,加法功能部件時間為2拍,乘法功能部件時間為3拍.采用類似于CARY-1的鏈接技術(shù),先計算A+B*C,在流水線不停流的情況下,接著計算D+E*F.1求此鏈接流水線的通過時間？設(shè)存放器人、出各需1拍2假設(shè)每拍時間為50ns,完成這些計算并把結(jié)果存進相應(yīng)存放器,此處理部件的實際吞吐率為多少MFLOPS?解：1我們在這里假設(shè)A+B的中間結(jié)果放在V6中,A+B義C地最后結(jié)果放在V7中,D+E地中間結(jié)果放在V8中,D+EXF的最后結(jié)果放在V9中.具體實現(xiàn)參考以下圖：通過時間應(yīng)該為前者A+BXC通過的時間：T通過=1+2+1+1+3+1=9拍2在做完A+BX

45、C之后,作C+DXE就不需要通過時間了.V6A+BV7V6XCV8D+EV9V8XFTT通過+8D824拍1200ns32TP-26.67MFLOPST7章互連網(wǎng)絡(luò)線路交換：在線路交換中,源結(jié)點和目的結(jié)點之間的物理通路在整個數(shù)據(jù)傳送期間一直保持連接.分組交換：把信息分割成許多組又稱為包,將它們分別送入互連網(wǎng)絡(luò).這些數(shù)據(jù)包可以通過不同的路徑傳送,到目的結(jié)點后再拼合出原來的數(shù)據(jù),結(jié)點之間不存在固定連接的物理通路.靜態(tài)互連網(wǎng)絡(luò)：各結(jié)點之間有固定的連接通路、且在運行中不能改變的網(wǎng)絡(luò).動態(tài)互連網(wǎng)絡(luò)：由交換開關(guān)構(gòu)成、可按運行程序的要求動態(tài)地改變連接狀態(tài)的網(wǎng)絡(luò).互連網(wǎng)絡(luò)：一種由開關(guān)元件根據(jù)一定的拓?fù)浣Y(jié)構(gòu)和限

46、制方式構(gòu)成的網(wǎng)絡(luò),用來實現(xiàn)計算機系統(tǒng)中結(jié)點之間的相互連接.在拓?fù)渖?互連網(wǎng)絡(luò)是輸入結(jié)點到輸出結(jié)點之間的一組互連或映象.互連函數(shù)：用變量x表示輸入,用函數(shù)fx表示輸出.那么fx表示：在互連函數(shù)f的作用下,輸入端x連接到輸出端fx.它反映了網(wǎng)絡(luò)輸入端數(shù)組和輸出端數(shù)組之間對應(yīng)的置換關(guān)系或排列關(guān)系,所以互連函數(shù)有時也稱為置換函數(shù)或排列函數(shù).網(wǎng)絡(luò)直徑：指互連網(wǎng)絡(luò)中任意兩個結(jié)點之間距離的最大值.結(jié)點度：指互連網(wǎng)絡(luò)中結(jié)點所連接的邊數(shù)通道數(shù).等分帶寬：把由N個結(jié)點構(gòu)成的網(wǎng)絡(luò)切成結(jié)點數(shù)相同N/2的兩半,在各種切法中,沿切口邊數(shù)的最小值.對稱網(wǎng)絡(luò)：從任意結(jié)點來看,網(wǎng)絡(luò)的結(jié)構(gòu)都是相同的.答：總線互連的復(fù)雜性最低,本

47、錢也是最低.其缺點是每臺處理機可用的帶寬較窄.交叉開關(guān)是最昂貴的,由于其硬件復(fù)雜性以n2上升,所以其本錢最高.但是交叉開關(guān)的帶寬和尋徑性能最好.當(dāng)網(wǎng)絡(luò)的規(guī)模較小時,它是一種理想的選擇.多級互連網(wǎng)絡(luò)的復(fù)雜度和帶寬介于總線和交叉開關(guān)之間,是一種折中方案.其主要優(yōu)點是采用模塊化結(jié)構(gòu),可擴展性較好.不過,其時延隨網(wǎng)絡(luò)級數(shù)的增加而上升.另外,由于其硬件復(fù)雜度比總線高很多,其本錢也不低.,31.(1)分別計算以下互連函數(shù)E2(12)S(8)B(9)PM2I+3(28)E0(S(4)S(E0(18)(2)用Eo和S構(gòu)成均勻洗牌交換網(wǎng)(每步只能使用Eo和S一次),網(wǎng)絡(luò)直徑是多少？從5號處理機發(fā)送數(shù)據(jù)到7號處理

48、機,最短路徑要經(jīng)過幾步？請列出經(jīng)過的處理機編號.(3)采用移數(shù)網(wǎng)絡(luò)構(gòu)成互連網(wǎng),網(wǎng)絡(luò)直徑是多少？結(jié)點度是多少？與2號處理機距離最遠(yuǎn)的是幾號處理機？解：(1)共有32個處理機,表示處理機號的二進制地址應(yīng)為5位.E2(12)=E2(01100)=01000(8)S(8)=S(01000)=10000(16)B(9)=B(01001)=11000(24)PM2I+3(28)=28+23mod32=4E0(S(4)=E0(S(00100)=01001(9)S(E0(18)=S(E0(10010)=S(10011)=00111(7)(2)2n個結(jié)點的均勻洗牌交換網(wǎng)的網(wǎng)絡(luò)直徑為2n-1,32個結(jié)點的均勻洗牌

49、交換網(wǎng)的網(wǎng)絡(luò)直徑為9.從5號處理機發(fā)送數(shù)據(jù)到7號處理機,最短路徑要經(jīng)過6步：00101f00100f01000f01001f10010f10011f00111(3)網(wǎng)絡(luò)直徑是3,結(jié)點度是9,與2號處理機距離最遠(yuǎn)的是13、15、21、23號處理機.具有N=2n個輸入端的Omega網(wǎng)絡(luò),采用單元限制.(1)N個輸入總共應(yīng)有多少種不同的排列?(2)該Omega網(wǎng)絡(luò)通過一次可以實現(xiàn)的置換總共可有多少種是不同的？(3)假設(shè)N=8,計算一次通過能實現(xiàn)的置換數(shù)占全部排列的百分比.解：(1)N個輸入的不同排列數(shù)為N!o(2)N個輸入端、輸出端的Omega網(wǎng)絡(luò)有n=log2N級開關(guān)級,每級開關(guān)級有N/2個2X2

50、的4功能開關(guān),總共有(N/2)10g2N個開關(guān).置換連接是指網(wǎng)絡(luò)的輸入端與輸出端的一對一連接,故只考慮2X2開關(guān)的2個功能狀態(tài),即直送與交叉.網(wǎng)絡(luò)采用單元限制,因此,每個開關(guān)都根據(jù)連接要求處于2個功能狀態(tài)中的一種狀態(tài),所以,由(N/2)log2N個開關(guān)組成的Omega網(wǎng)絡(luò)的開關(guān)狀態(tài)的種樹為：一種網(wǎng)絡(luò)開關(guān)狀態(tài)實現(xiàn)Omega網(wǎng)絡(luò)的一種無沖突的置換連接,所以,一次使用Omega網(wǎng)絡(luò)可以實現(xiàn)的無沖突的置換連接有NN/2種.(3)假設(shè)N=8,那么一次通過能實現(xiàn)的置換數(shù)占全部排列的百分比為：N=8的三級Omega網(wǎng)絡(luò)連接8個處理機(PoP7),8個處理機的輸出端分別依序連接Omega網(wǎng)絡(luò)的8個輸入端07,

51、8個處理機的輸入端分別依序連接Omega網(wǎng)絡(luò)的8個輸出端07.如果處理機P6要把數(shù)據(jù)播送給處理機PoP4,處理機P3要把數(shù)據(jù)播送給處理機P5P7,那么,Omega網(wǎng)絡(luò)能否同時為它們的播送要求實現(xiàn)連接？畫出實現(xiàn)播送的Omega網(wǎng)絡(luò)的開關(guān)狀態(tài)圖.解：Omega網(wǎng)絡(luò)使用的2X2開關(guān)有4種狀態(tài)：直送、交叉、上播、下播.置換連接只使用直送和交叉狀態(tài),播送連接還需要使用上播和下播狀態(tài).分別畫出實現(xiàn)處理機P6和P3的播送連接要求使用的開關(guān)狀態(tài),如果沒有開關(guān)狀態(tài)和開關(guān)輸出端爭用沖突,就可以使用播送連接.實際上,它們的播送要求沒有沖突,因此,可以同時實現(xiàn),同時實現(xiàn)的Omega網(wǎng)絡(luò)開關(guān)狀態(tài)圖如下所示.試證實多級O

52、mega網(wǎng)絡(luò)采用不同大小構(gòu)造塊構(gòu)造時所具有的以下特性：(1)一個kxk開關(guān)模塊的合法狀態(tài)(連接)數(shù)目等于kko(2)試計算用2X2開關(guān)模塊構(gòu)造的64個輸入端的Omega網(wǎng)絡(luò)一次通過所能實現(xiàn)置換的百分比.(3)采用8X8開關(guān)模塊構(gòu)造64個輸入端的Omega網(wǎng)絡(luò),重復(fù)(2).(4)采用8X8開關(guān)模塊構(gòu)造512個輸入端的Omega網(wǎng)絡(luò),重復(fù)(2).解：(1)一個kxk開關(guān)的合法狀態(tài)或合法連接有：一個輸入端連接一個輸出端,即一對一的置換連接；一個輸入端連接多個或全部輸出端,即一對多的選播連接或一對全體的播送連接.兩個或兩個以上的輸入端連接一個輸出端是非法連接.因此,某個輸出端可被連接到任意一個輸入端的

53、連接有k種,無論這個輸出端是被置換連接還是被播送連接.k個輸出端被連接到輸入端的合法連接的數(shù)量為：kk次x次=k工工Vk個(2)用kxk開關(guān)模塊構(gòu)造N個輸入端的Omega網(wǎng)絡(luò)時,開關(guān)級數(shù)為n=logkN,每級開關(guān)模塊數(shù)為N/k,網(wǎng)絡(luò)的開關(guān)模塊總數(shù)為(N/k)logkNo一個kxk開關(guān)一對一連接的合法狀態(tài)只有k種,所有開關(guān)都是一對一連接的合法狀態(tài)才能實現(xiàn)一種一次使用網(wǎng)絡(luò)的無沖突置換連接.因此,由(N/k)logkN個k冰開關(guān)組成的Omega網(wǎng)絡(luò)一次使用的無沖突置換連接函數(shù)為：網(wǎng)絡(luò)可以實現(xiàn)的置換連接數(shù)即為N個輸出端的不同排序的排序數(shù),即為N!,所以,Omega網(wǎng)使用一次實現(xiàn)的無沖突置換連接數(shù)占可以

54、實現(xiàn)的置換連接數(shù)的比例為：假設(shè)采用2X2開關(guān)模塊構(gòu)造的64個輸入端的Omega網(wǎng)絡(luò),即有k=2,N=64,那么Omega網(wǎng)使用一次實現(xiàn)置換連接的比例為：(3)假設(shè)采用8X8開關(guān)模塊構(gòu)造64個輸入端的Omega網(wǎng)絡(luò),即有k=8,N=64,那么Omega網(wǎng)使用一次實現(xiàn)置換連接的比例為：(4)假設(shè)采用8X8開關(guān)模塊構(gòu)造512個輸入端的Omega網(wǎng)絡(luò),即有k=8,N=512,那么Omega網(wǎng)使用一次實現(xiàn)置換連接的比例為：第8章多處理機集中式共享多處理機：也稱為對稱式共享存儲器多處理SMPo它一般由幾十個處理器構(gòu)成,各處理器共享一個集中式的物理存儲器,這個主存相對于各處理器的關(guān)系是對稱的,分布式共享多處理機：它的共享存儲器分布在各臺處理機中,每臺處理機都帶有自己的本地存儲器,組成一個“處理機-存儲器單元.但是這些分布在各臺處理機中的實際存儲器又合在一起統(tǒng)一編址,在邏輯上組成一個共享存儲器.這些處理機存儲器單元通過互連網(wǎng)絡(luò)連接在一起,每臺處理機除了能訪問本地存儲器外,還能通過互連網(wǎng)絡(luò)直接訪問在其他處理機存儲器單元中的遠(yuǎn)程存儲器通信延遲：通信延遲=發(fā)送開銷+跨越時間+傳輸時間+接收開銷.計算/通信比：反映并行程序性能的一個重要的度量.在并行計算中,每次數(shù)據(jù)通信要進行的計算與通信開銷的比值.多Cache一致性：多處理機中,當(dāng)共享數(shù)據(jù)進入Cache,就可能