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

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