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

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

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

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

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

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

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

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

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

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

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