分布與并行計(jì)算思考題答案整理.文檔

#11.簡(jiǎn)述SMP和CC-NUMA系統(tǒng)的-般結(jié)構(gòu)及典型特征。(并行計(jì)算/SMP和CC-NUMA)答：SMP系統(tǒng)屬尸共亨存儲(chǔ)器系統(tǒng).能獲取很鬲的并行性。使用總線或交叉開關(guān)將處理器偏速緩存」K)和存儲(chǔ)器相連。它具有共亨:存儲(chǔ)器系統(tǒng)的優(yōu)點(diǎn)，但可擴(kuò)展性有限。具有對(duì)稱性，任何-?個(gè)處理器可訪問任何存儲(chǔ)單元和任何I/O設(shè)備。所有處理器祁可以訪問同一個(gè)系統(tǒng)物理存儲(chǔ)器.這就恿味肴SMP系統(tǒng)只運(yùn)行操作系統(tǒng)的一個(gè)拷貝，具有單-?地址空間。山商速緩存支持?jǐn)?shù)據(jù)局部性。商速緩存一致性和低時(shí)延的存儲(chǔ)為通信。CC-NLWA系統(tǒng)是SMP系統(tǒng)的擴(kuò)展，它將兒個(gè)SMP結(jié)點(diǎn)用互聯(lián)網(wǎng)絡(luò)連接起來構(gòu)成一個(gè)更大的系統(tǒng).繼承fSMP結(jié)構(gòu)的優(yōu)點(diǎn)。大多數(shù)商用CC-NUMA系統(tǒng)采用基于目錄的扁速緩存-?致性協(xié)議。它捉高了系統(tǒng)的可擴(kuò)展性.通過増加結(jié)點(diǎn).可以増加處理器數(shù).加大存儲(chǔ)容:a,捉高"()能力。由于程序可利用數(shù)據(jù)的局部性.在大部分時(shí)間內(nèi)能同時(shí)訪問多個(gè)局部存儲(chǔ)器，從而緩解了爭(zhēng)用和帯寬問題。系統(tǒng)也采用了分布式存儲(chǔ)益模式?所有結(jié)點(diǎn)中的處理器都可以訪問全部的系統(tǒng)存儲(chǔ)器，但每個(gè)處理器訪問木結(jié)點(diǎn)內(nèi)的心儲(chǔ)器所需耍的時(shí)問.可能比訪問某些遠(yuǎn)程結(jié)點(diǎn)內(nèi)的〃儲(chǔ)器所花的時(shí)何耍少得餌。換句話說.也就是訪問存儲(chǔ)益的時(shí)間是不i致的.這也就是非均勻存儲(chǔ)訪問(NUMA)。CacheCoherent是指不需耍軟件來保持多個(gè)數(shù)據(jù)拷貝的-致性，和SMP—樣，這些都由碩件實(shí)現(xiàn)。并行編程I.forall(1in(1..3)){printf(^Hello%i\nv,i):}上述程序段是使用Peril-L來描述的程序段?根據(jù)Peril-L的講義特點(diǎn)回答下面問題。⑴、請(qǐng)寫出該程序段可能輸出結(jié)果類型.并說明原因。⑵.根據(jù)上而的結(jié)果，請(qǐng)増加?些機(jī)制使得該程序輸出確保有意義。⑶.請(qǐng)?jiān)倭谐鰞蓚€(gè)Peril-L的其他機(jī)制。:(1)A:B：C:Hello2Hello3Helllello3Hello1Hello21Helloo2Hello3Hello11由于Peril-L中伽all是多個(gè)線程并發(fā)執(zhí)行，并且相互之間完全沒佇約束，所以各個(gè)線程的執(zhí)行時(shí)完全獨(dú)立，所以最終的輸出.有可能是有序的，也有可能是完全混介在一起的。(只要輸出結(jié)果包括有序和混合并且符合程序就可以。)(2)可以增加排他塊機(jī)制,保證某個(gè)進(jìn)程在運(yùn)行時(shí)其他進(jìn)程不會(huì)執(zhí)行.從而使進(jìn)程執(zhí)行有序。程序如下：forall(iin(1..3)){exclusive{printfCHello%i\nv,i);}}⑶Peril-L還有很多機(jī)制，包barrier障柵同步.全間變St和間部變?nèi)缱冎返谋镜鼗?ocalizc().同步存儲(chǔ)器FE變雖等。barrier障柵同步:動(dòng)能是強(qiáng)迫線裡停止宜至所有線程到達(dá)barrier.全局變就和同部變最：全局變杲加卜?劃線。變就的木地化localize()：全局變就訪問的代價(jià)比木地變就髙很多.通過本地化可以提高程序的效率。同步存儲(chǔ)益FE變竝：通過滿空變最實(shí)現(xiàn)線程間的同步。2.使用無限并行性方法對(duì)某個(gè)字符串按照字母順序排序?；卮鹣率鰡栴}。⑴、無限并行性使用的求解方式是何種排序方法?請(qǐng)簡(jiǎn)述該排序思想。⑵、說明該排序毎法為何可以應(yīng)用于并行排序算法。答：⑴使用的是奇偶交替排序算法。奇偶排序是冒泡排序的并行化版也其基木思想是將冒泡扌II：序中的每輪操作分解成奇數(shù)位上的比較交換和偶數(shù)位上的比較交換兩部分.然后循壞的拙序?直到所有奇數(shù)位和偶數(shù)位上都有序，則整個(gè)序列有序。(2)從排序過程可以看出，在每輪的操作中，各次數(shù)據(jù)比校交換都是獨(dú)立的，因此每輪操作都町以并行化，這就足該算法可以應(yīng)用于并行算法的原因。注：1?分布式教材為：需要的同學(xué)可以借閱或購(gòu)買黃愷,徐志偉可擴(kuò)展并行計(jì)算-技術(shù)、結(jié)構(gòu)與編程，機(jī)械工業(yè)出版社AndrewS.Tancnbaum^MaartenvanSteen,分布式系統(tǒng)原理與范型，淸華大學(xué)出版社CalvinLin,LawrenceSnyder,并行程序設(shè)計(jì)原理，機(jī)械工