計算機系統(tǒng)的體系結(jié)構(gòu)第七章

第七章課后題多處理機在結(jié)構(gòu)、程序并行性、算法、進程同步、資源分配和調(diào)試上與并行處理機有什么差別？答：多處理機與并行處理機的主要差別是并行性的等級不同。（1）結(jié)構(gòu)靈活性。多處理機制結(jié)構(gòu)靈活性高于并行處理機。（2）程序并行性。多處理是指令、任務、作業(yè)并行，并行性的識別較難;并行處理機是操作級并行，并行性的識別較易。（3）并行任務派生。并行處理機工作能否并行工作由指令決定，多處理機必須有專門指令指明程序能否并行執(zhí)行，派生的任務數(shù)是動態(tài)變化的。（4）進程同步。并行處理機的進程同步是自然的，而多處理機必須采取同步措施。（5）資源分配和任務調(diào)度。多處理機的資源分配和任務調(diào)度比并行處理機復雜得多。多處理機有哪些基本特點？發(fā)展這種系統(tǒng)的主要目的可能有哪些？多處理著重解決哪些技術(shù)問題？答：。多處理機的基本特點：多處理機具有兩臺以上的處理機,在操作系統(tǒng)控制下通過共享的主存或輸入/輸出子系統(tǒng)或高速通訊網(wǎng)絡(luò)進行通訊.結(jié)構(gòu)上多個處理機用多個指令部件分別控制,通過機間互連網(wǎng)絡(luò)通訊;算法上不只限于處理向量數(shù)組,還要實現(xiàn)更多通用算法中的并行;系統(tǒng)管理上要更多地依靠軟件手段,有效解決資源分配和管理,特別是任務分配,處理機調(diào)度,進程的同步和通訊等問題.。使用多處理機的目的：一是用多臺處理進行多任務處理協(xié)同求解一個大而復雜的問題來提高速度,二是依靠冗余的處理機及其重組來提高系統(tǒng)的可靠性,適應性和可用性.。多處理著重要解決的技術(shù)問題：（1）硬件結(jié)構(gòu)上，如何解決好處理機、存儲器模塊及I/O子系統(tǒng)間的互連。（2）如何最大限度開發(fā)系統(tǒng)的并行性，以實現(xiàn)多處理要各級的全面并行。

3）如何選擇任務和子任務的大小，即任務的粒度，使并行度高，輔助開銷小。（4）如何協(xié)調(diào)好多處理機中各并行執(zhí)行任務和進程間的同步問題。（5）如何將任務分配到多處理機上，解決好處理機調(diào)度、任務調(diào)度、任務調(diào)度和資源分配，防止死鎖。（6）一旦某個處理發(fā)生故障，如何對系統(tǒng)進行重新組織，而不使其癱瘓。（7）多處理機機數(shù)增多后，如何能給編程者提供良好的編程環(huán)境，減輕程序的復雜性。3?分別畫出4*9的一級交叉開關(guān)以及用兩級2x3的交叉開關(guān)組成的4x9的Delta網(wǎng)絡(luò)，比較一下交叉開關(guān)設(shè)備量的多少？解答：4*9的一級交叉開關(guān)如下圖所示：輸入端輸出端012輸入端輸出端0123115678一級T交叉開關(guān)兩級2x3的交叉開關(guān)組成的4x9的Delta網(wǎng)絡(luò)如下圖所示:

23輸出端282a23輸出端282a2*3*3的DMt日網(wǎng)絡(luò)輸入端2A2*3A3有Delta網(wǎng)絡(luò)由5個2*3的交叉開關(guān)組成，其交叉開關(guān)的結(jié)點數(shù)由一級網(wǎng)絡(luò)的36個減少到現(xiàn)在Delta網(wǎng)絡(luò)中的2*3*5=30個。剖析：第一級有2個2*3的交叉開關(guān)，第2級有3個2*3的交叉開關(guān)，級間采用混洗拓撲。4.說明4＊4交叉開關(guān)組成的兩級16*16交叉開關(guān)網(wǎng)絡(luò)雖節(jié)省了設(shè)備，但它是一個阻塞式網(wǎng)絡(luò)。答：16*16交叉開關(guān)網(wǎng)絡(luò)需要256個開關(guān)結(jié)點，每個結(jié)點中選1的多路裁決和選擇電路。采用4x4的交叉開關(guān)構(gòu)成的二級交叉開關(guān)網(wǎng)絡(luò)，共需要16x8=128個開關(guān)結(jié)點，每個結(jié)點只需要4中選1的多路裁決和選擇電路，節(jié)省了設(shè)備。但它是一個阻塞式網(wǎng)絡(luò)。因為第1級每4個輸入端中只能有一個連到第2級的一個輸入端，而第2級的這個輸入端本可以對應4個輸出端的某一個。這就意味著，當?shù)?級4個輸入端中的某一個連到了最終的某個輸出端時，第1級同組內(nèi)其它3個輸入端由于有路徑?jīng)_突，就不能同時將信息傳送到第2級輸出相應的另外3個輸出端上，而采用16x16的一級交叉開關(guān)就不存在這種問題。5?由霍納法則給定的表達式如下：E=a(b+c(d+e(f+gh)))利用減少樹高的辦法來加速運算，要求畫出樹形流程圖;確定Tp、P、Sp、Ep諸值。解答：(1)對于原式，單處理機串行運算樹形流程圖如左下圖所示，多處理機并行運算樹形流程圖如右下圖所示。(2)P臺處理機運算的級數(shù)Tp=4。所需處理機數(shù)目P=3。加速比Sp=?序運算的級數(shù)T1/P臺處理機運算的級數(shù)Tp=7/4。效率Ep=加速比Sp/所需處理機數(shù)目P=7/12。6、求A1、A2……A8的累加和，有如下程序：A1=A1+A2A3=A3+A4A5=A5+A6A7=A7+A8A1=A1+A3A5=A5+A7A1=A1+A5（1）寫出用FORK、JOIN語句表示其并行任務的派生和匯合關(guān)系的程序，以假想使此程序能在多處理機上運行。（2）畫出該程序在有3臺處理機制系統(tǒng)上運行的時間關(guān)系示意圖。（3）畫出該程序在有2臺處理機制系統(tǒng)上運行的時間關(guān)系示意圖。解答：（1）用FORK、JOIN語句表示其并行任務的派生和匯合關(guān)系的程序如下。FORK20FORK30FORK4010A1=A1+A2JOIN4GOTO8020A3=A3+A4JOIN4GOTO8030A5=A5+A6JOIN4GOTO8040A7=A7+A8JOIN480FORK60

A1=A1+A3JOIN2GOTO7060A5=A5+A7JOIN270A1=A1+A5(2)在有3臺處理機制多處理機系統(tǒng)上運行的資源時間圖如下圖所示。假設(shè)標號為50和60的兩個并發(fā)進程中，標號為60的進程最后完成。處理機30J0IN430J0IN4CPU320J0IN440J0IN4J0IN220J0IN440J0IN4J0IN2CPU2FORK60；FORK4010FORK60；FORK4010J0IN4J0IN2CPU1FORK30FORK20time程序在多處理機上運行的資源時間圖在有2臺處理機制多處理機系統(tǒng)上運行的資源時間圖如下圖所示。假設(shè)標號為50和60的兩個并發(fā)進程中，標號為50的進程最后完成。'20J0IN430J0IN4lI|60J0IN2II；FORK40III10J0IN440J0IN4III50J0IN2IIi78F0RK30F0RK60GOTO70F0RK20處理機CPU2CPU1程序在多處理機上運行的資源時間圖剖析：GOTO70語句的問題關(guān)鍵是70語句是在50語句還是60語句所在CPU上執(zhí)行的。也就是說50語句和60語句誰先執(zhí)行完。7、若有如下程序：V=U/BW=A*UX=W-VY=W*UZ=X/Y試用FORK、JOIN語句改寫成可在多處理機上并行執(zhí)行的程序。假設(shè)現(xiàn)有兩臺處理機，且除法速度最慢，加、減法速度最快，請畫出該程序運行時的資源時間圖。解答：用FORK、JOIN語句改寫成可在多處理機上并行執(zhí)行的程序如下：S1U=A+BFORKS3S2V=U/B

JOIN2GOTOS4'S3W=A*UJOIN2S4'FORKS5S4X=W-VJOIN2GOTOS6S5Y=W*UJOIN2S6Z=X/Y該程序在有2臺處理機的多處理機系統(tǒng)上運行時的資源時間圖如下所示1S31S3JI0N2S5JI0N2S6*i*/S1S2G0T0S4，|S4IlliJI0N2+F0RKS3/JI0N2F0RKS5-8?分別確定下列各計算機系統(tǒng)中，計算點積S=(8)工(i=l)ai*所需的時間(盡可能給出時空圖示意)：通用PE的串行SISD系統(tǒng);具有一個加法器和乘法器的多功能并行流水SISD系統(tǒng);⑶有8個處理器的SIMD系統(tǒng)；有8個處理器的MIMD系統(tǒng)。設(shè)訪存取指和取數(shù)的時間可以忽略不計；加與乘分別需要2拍和4拍；在SIMD和MIMD系統(tǒng)中處理器(機)之間每進行一次數(shù)據(jù)傳送的時間為1拍，而在SISD的串行或流水系統(tǒng)中都可忽略;在SIMD系統(tǒng)中PE之間采用線性環(huán)形互連拓撲,即每個PE與其左右兩個相鄰的PE直接相連，而在MIMD中每個PE都可以和其它PE有直接的通路。解答:(1)利用通用PE的串行SISD系統(tǒng)計算點積所需時間為46拍，時空圖如下圖所示：部件a1*b1a2*b2+a3*b3+a4*b4+a5*b5+a6*b6+a7*b7+a8*b8+2tir(2)利用具有一個加法器和乘法器的多功能并行流水SISD系統(tǒng)計算點積所需時間為15拍，時空圖如下圖所示：

[利用有8個處理器的SIMD系統(tǒng)計算點積所需時間為14拍，時空圖如下圖所示：upload=gif]uploadimages/200448921199442_as4408a.gif[/upload]利用有8個處理器的MIMD系統(tǒng)計算點積所需時間為14拍,時空圖如下圖所示：

處理機丿ICPU1a1*b1IICPU2a2*b2CPU3a3*b3ICPU4a4*b4ICPUSa5*b5i1+2I11CPU6a6*b6113+41111CPU7a7*b7111115+61111LCPUSa8*b8II1II17+811i|ii5~81~8F0RK1~7JOINSF0RK1~3JOIN4FORK1J0IN218101112139?設(shè)程序有T個任務，在A、B兩臺處理機組成的多處理機上運行。每個任務在A處理機上執(zhí)行的時間為E,在B處理機上執(zhí)行的時間為2E，不考慮機間通訊時間，問如何分配任務，可使系統(tǒng)總執(zhí)行時間最短？總執(zhí)行時間最短為多少？解：設(shè)為A處理機分配I個任務，為B處理機分配T-I個任務，則系統(tǒng)總執(zhí)行時間最短為IE=2(T-I)E。解得：l=2T/3。所以，總執(zhí)行時間最短為2TE/3。10.簡述多處理機操作系統(tǒng)3種不同類型的構(gòu)形,列出每種構(gòu)形有優(yōu)點和缺點以及設(shè)計中的問題.

婁型構(gòu)型優(yōu)點缺點適用場合主從型管理程序只在一臺指定的處理上運行硬件結(jié)構(gòu)簡單，控制簡單對主機的可靠性宴求高，靈活性差工件負荷固定，從處理機的能力明顯低于主處理機各自獨立型控制功能芬散到多臺處理機，共同完成對整個系統(tǒng)的控制。每臺處理