并行計(jì)算復(fù)習(xí)資料答案

1、（1）比較PVP, SMP, MPP, DSM, Cluster, ConstellationPVP:并行向量處理機(jī)系統(tǒng)中包含了少量的高性能專門設(shè)計(jì)定制的向量處理器VP（Vector Processor），每個(gè)至少具有1Gflops的處理能力。系統(tǒng)中使用了專門設(shè)計(jì)的高帶寬的交叉開(kāi)關(guān)網(wǎng)絡(luò)向VP連向共享存儲(chǔ)模塊，存儲(chǔ)器可以M/s字節(jié)的速度向處理器提供數(shù)據(jù)。這樣的機(jī)器通常不使用高速緩存，而是使用大量的向量寄存器和指令緩沖器。SMP: 對(duì)稱多處理機(jī)SMP系統(tǒng)使用商品微處理器（具有片上或外置高速緩存），他們經(jīng)由高速總線（或交叉開(kāi)關(guān)）連向共享存儲(chǔ)器。這種機(jī)器主要應(yīng)用于商務(wù)，例如數(shù)據(jù)庫(kù)、在線事務(wù)處理系統(tǒng)和數(shù)

2、據(jù)倉(cāng)庫(kù)等。重要的是系統(tǒng)是對(duì)稱的，每個(gè)處理器可等同地方問(wèn)共享存儲(chǔ)，限制系統(tǒng)中的處理器不能太多（一般小于64個(gè)），同時(shí)總線和交叉開(kāi)關(guān)互連一旦做成也難于擴(kuò)展。MPP：大規(guī)模并行處理機(jī)MMP一般是指超大型（Very Large-Scale）計(jì)算機(jī)系統(tǒng)，他具有如下特征：處理結(jié)點(diǎn)采用商用微處理器；系統(tǒng)中有物理上的分布式存儲(chǔ)器；采用高通信帶寬和低延遲的互聯(lián)網(wǎng)絡(luò)（專門設(shè)計(jì)和定制的）；能擴(kuò)放至成百上千乃至上萬(wàn)個(gè)處理器；它是一種異步的MIMD機(jī)器，程序系由多個(gè)進(jìn)程組成，每個(gè)都有其私有地址空間，進(jìn)程間采用傳遞消息相互作用。MMP的主要應(yīng)用是科學(xué)計(jì)算、工程模擬和信號(hào)處理等以計(jì)算為主的領(lǐng)域。DSM：分布式共享存儲(chǔ)高速緩

3、存目錄DIR用以支持分布高速緩存的一致性。DSM和SMP的主要差別是，DSM在物理上有分布在各個(gè)節(jié)點(diǎn)中的局存，從而形成了一個(gè)共享的存儲(chǔ)器。對(duì)用戶而言，系統(tǒng)硬件和軟件提供了一個(gè)單地址的編程空間。DSM相對(duì)于MPP的優(yōu)越性是編程較容易。Cluster/Cow：工作站機(jī)群COW的重要界限和特征是：COW的每一個(gè)節(jié)點(diǎn)都是一個(gè)完整的工作站（不包括監(jiān)視器、鍵盤、鼠標(biāo)等），這樣的節(jié)點(diǎn)有時(shí)叫做“無(wú)頭工作站”，一個(gè)節(jié)點(diǎn)也可以是一臺(tái)PC或SMP；各節(jié)點(diǎn)通過(guò)一種低成本的商品（標(biāo)準(zhǔn)）網(wǎng)絡(luò)（如以太網(wǎng)、FDDI和ATM開(kāi)關(guān)等）互連（有的商用機(jī)群也使用定做的網(wǎng)絡(luò)）；各節(jié)點(diǎn)內(nèi)總是有本地磁盤，而MPP節(jié)點(diǎn)內(nèi)卻沒(méi)有；節(jié)點(diǎn)內(nèi)的網(wǎng)絡(luò)

4、接口是松散耦合到I/O總線上的，而MPP內(nèi)的網(wǎng)絡(luò)接口是連到處理節(jié)點(diǎn)的存儲(chǔ)總線上的，因而可謂是緊耦合式的；一個(gè)完整的操作系統(tǒng)駐留在每個(gè)節(jié)點(diǎn)中，而MPP中通常只有一個(gè)微核，COW的操作系統(tǒng)是工作站UNIX，加上一個(gè)附加的軟件層，以支持單一系統(tǒng)映像、并行度、通信和負(fù)載平衡等?，F(xiàn)今，MPP和COW之間的界限越來(lái)越模糊。機(jī)群相對(duì)于MPP有性能/價(jià)格比高的優(yōu)勢(shì)，所以在發(fā)展可擴(kuò)放并行計(jì)算機(jī)方面呼聲很高。（2）比較UMA, NUMA, CC_NUMA, CORMA, NORMA Coherent：一致的這里的DSM不太正確的感覺(jué)。（3）HPC, HPCC, Distributed computing, Clo

5、ud computingHPC：高性能計(jì)算，High Performance ComputingHPCC：高性能計(jì)算和通信計(jì)劃，High Performance Computing & CommunicationDistributed computing：分布式計(jì)算Cloud computing:云計(jì)算（4）列出常用靜態(tài)和動(dòng)態(tài)網(wǎng)絡(luò)的主要參數(shù) （節(jié)點(diǎn)度、 直徑、 對(duì)剖帶寬和鏈路數(shù)） 以及復(fù)雜度、網(wǎng)絡(luò)性能、擴(kuò)展性和容錯(cuò)性等。常用的標(biāo)準(zhǔn)互聯(lián)網(wǎng)絡(luò)有哪些？并行機(jī)規(guī)模：并行機(jī)包含的結(jié)點(diǎn)總數(shù)，或者包含的CPU總數(shù)；結(jié)點(diǎn)度：互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中聯(lián)入或聯(lián)出的一個(gè)結(jié)點(diǎn)的邊的條數(shù)，稱為該結(jié)點(diǎn)的度；結(jié)點(diǎn)距離：兩

6、個(gè)結(jié)點(diǎn)之間跨越的圖的邊的條數(shù)；網(wǎng)絡(luò)直徑：網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)之間的最長(zhǎng)距離；點(diǎn)對(duì)點(diǎn)帶寬：圖中邊對(duì)應(yīng)的物理聯(lián)接的物理帶寬；點(diǎn)對(duì)點(diǎn)延遲：圖中任意兩個(gè)結(jié)點(diǎn)之間的一次零長(zhǎng)度消息傳遞必須花費(fèi)的時(shí)間。延遲與結(jié)點(diǎn)間距離相關(guān)，其中所有結(jié)點(diǎn)之間的最小延遲稱為網(wǎng)絡(luò)的最小延遲，所有結(jié)點(diǎn)之間的最大延遲稱為網(wǎng)絡(luò)的最大延遲；折半寬度：對(duì)分網(wǎng)絡(luò)成兩個(gè)部分（它們的結(jié)點(diǎn)個(gè)數(shù)至多相差1）所必須去掉的邊的網(wǎng)絡(luò)帶寬的總和；總通信帶寬：所有邊的帶寬之和標(biāo)準(zhǔn)互連網(wǎng)絡(luò)有：光線分布式數(shù)據(jù)接口（FDDI）快速以太網(wǎng)（Ethernet）Myrinet 可擴(kuò)放一致性接口（SCI）InfiniBand HiPPI（5）比較并行計(jì)算模型 PRAM、BS

7、P 和 logP。評(píng)述它們的差別、相對(duì)優(yōu)點(diǎn)以及在模型化真實(shí)并行計(jì)算機(jī)和應(yīng)用時(shí)的局限性。 BSP和logP相互比較：1. 現(xiàn)今最流行的并行計(jì)算模型是BSP和logP，已經(jīng)證明兩者本質(zhì)上是等效的，且可以互相模擬；2. BSP為算法和程序提供了更多的方便，而logP卻提供了較好的機(jī)器資源的控制；3. BSP所引起的精確度方面的損失比起其所提供的更結(jié)構(gòu)化的編程風(fēng)格的優(yōu)點(diǎn)來(lái)是小的；4. BSP模型在簡(jiǎn)明性、性能的可預(yù)測(cè)性、可移植性和結(jié)構(gòu)化可編程性等方面更受人歡迎和喜愛(ài)。三者關(guān)系： LogP和PRAM模型是并行計(jì)算模型的兩個(gè)極端.BSP模型可以看成是上述兩個(gè)模型的折衷.相比之下,LogP模型過(guò)于復(fù)雜,缺乏

8、有效的分析和性能預(yù)測(cè)的模型,而PRAM則過(guò)于簡(jiǎn)單,無(wú)法真實(shí)地描述物理機(jī)器。BSP模型較好地綜合了其它兩個(gè)模型優(yōu)點(diǎn),在面向物理機(jī)器實(shí)現(xiàn)方面優(yōu)于PRAM模型,而和LogP模型相比,又更加便于進(jìn)行算法設(shè)計(jì)和性能預(yù)測(cè)。（6）比較在 PRAM 模型和 BSP 模型上，計(jì)算兩個(gè) N 階向量?jī)?nèi)積的算法及其復(fù)雜度。PRAM點(diǎn)積：BSP點(diǎn)積 每個(gè)處理器處理A的N/P個(gè)數(shù)值和B的N/P個(gè)數(shù)值，共N/P次乘法和N/P-1次加法(7)什么是加速比（speed up） 、并行效率（efficiency）和可擴(kuò)展性（scalability）? 如何描述在不同約束下的加速比？加速比：串行執(zhí)行時(shí)間為 Ts ，使用 q 個(gè)處理

9、機(jī)并行執(zhí)行的時(shí)間為 Tp (q)，則加速比為Sp(q)=Ts/Tp(q)。簡(jiǎn)單的說(shuō)，并行系統(tǒng)的加速比是指對(duì)于一個(gè)給定的應(yīng)用，并行算法（或并行程序） 的執(zhí)行速度相對(duì)于串行算法（或串行程序）的執(zhí)行速度快了多少倍。并行效率：設(shè)q個(gè)處理機(jī)的加速比為Sp（q），則并行算法的效率Ep（q）Sp（q）/q。反映了并行系統(tǒng)中處理器的利用程度。分母要固定，體現(xiàn)時(shí)間不變由于存儲(chǔ)容量變大，所以可以利用更多的資源得出更精確的解，這時(shí)會(huì)增加并行工作量P129（8）如何進(jìn)行并行計(jì)算機(jī)性能評(píng)測(cè)？什么是基準(zhǔn)測(cè)試程序？（9）什么是可擴(kuò)放性測(cè)量標(biāo)準(zhǔn)？等效率函數(shù)的涵義是什么？等效率測(cè)度：效率：加速比/處理器數(shù) 簡(jiǎn)單情況下能得分析結(jié)

10、果 等速度測(cè)度 速度：每秒處理的數(shù)據(jù)量 便于通過(guò)實(shí)驗(yàn)數(shù)據(jù)得到結(jié)果 平均時(shí)延測(cè)度（Latency Metrics） 時(shí)延：理想并行時(shí)間與實(shí)際并行時(shí)間的差距 便于通過(guò)實(shí)驗(yàn)數(shù)據(jù)得到結(jié)果（10）什么是分治策略的基本思想？舉例說(shuō)明如何應(yīng)用平衡樹(shù)方法、倍增技術(shù)和流水線技術(shù)。劃分通信組合映射如何將全局通信轉(zhuǎn)換為局部通信： 可以使用分治策略來(lái)提高并行性。 表面容積效應(yīng)： 通訊量與任務(wù)子集的表面成正比，計(jì)算量與任務(wù)子集的體積成正比； 增加重復(fù)計(jì)算有可能減少通訊量 重復(fù)計(jì)算：  重復(fù)計(jì)算減少通訊量，但增加了計(jì)算量，應(yīng)保持恰當(dāng)?shù)钠胶猓?#160;重復(fù)計(jì)算的目標(biāo)應(yīng)減少算法的總運(yùn)算時(shí)間 映射的策略是什么 可并發(fā)執(zhí)行的任務(wù)放在不同的處理器上，增強(qiáng)并行度 需要頻繁通信的任務(wù)置于