13并行計(jì)算補(bǔ)考資料

1、UMA UMA是Uniform Memory Access （均勻存儲訪問）模型的縮寫。在這種并行機(jī)中所 有的處理器均勻共享物理存儲器。所有處理器訪問任何存儲字需要相同的時(shí)間（此即為均勻 存儲訪問名稱的來源）。每臺處理器可以有私有高速緩存。UMA的結(jié)構(gòu)如下圖所示。其中P 表示處理器，SM表示共享存儲器。NUMA NUMA是Non-Uniform Memory Access （非均勻存儲訪問）模型的縮寫。在NUMA 中，共享存儲器在物理上是分布的，所有的本地存儲器構(gòu)成了全局地址空間。NUMA與UMA 的區(qū)別在于處理器訪問本地存儲器和群內(nèi)共享存儲器比訪問遠(yuǎn)程存儲器或全局共享存儲器 快（此即非均勻存

2、儲訪問名稱的由來）。下圖中（a）表示共享本地存儲器的NUMA結(jié)構(gòu)，（b） 為層次式機(jī)群NUMA結(jié)構(gòu)。LM表示本地存儲器，GSM表示全局共享存儲器，P表示處理器， CSM表示群內(nèi)共享存儲器，CIN表示機(jī)群互連網(wǎng)絡(luò)。COMA COMA是Cache-Only Memory Architecture （全高速緩存存儲結(jié)構(gòu)）模型的縮寫。 COMA實(shí)際是NUMA的一種特例，將NUMA中的分布存儲器換成高速緩存就得到了 COMA。在COMA 中，每個(gè)結(jié)點(diǎn)上沒有存儲層次結(jié)構(gòu)，所有的高速緩存構(gòu)成了全局地址空間。訪問遠(yuǎn)程高速緩 存要借助分布的高速緩存目錄。COMA結(jié)構(gòu)如下圖所示。D表示高速緩存目錄，C表示高速緩

3、存，P表示處理器。CC-NUMA CC-NUMA 是 Cache-Coherent Non-Uniform Memory AccessC 高速緩存一致性非 均勻存儲訪問）模型的縮寫。CC-NUMA結(jié)構(gòu)的并行機(jī)實(shí)際上是將一些SMP機(jī)作為結(jié)點(diǎn)互 連起來而構(gòu)成的并行機(jī)。這樣可以改善SMP機(jī)的可擴(kuò)展性。絕大多數(shù)商用CC-NUMA多處 理機(jī)系統(tǒng)使用基于目錄的高速緩存一致性協(xié)議；它的存儲器在物理上是分布的，所有的局部 存儲器構(gòu)成了共享的全局地址空間（所以它實(shí)際上是一個(gè)DSM系統(tǒng)），因此它保留了 SMP 易于編程的優(yōu)點(diǎn)。它最顯著的優(yōu)點(diǎn)是程序員無需明確地在結(jié)點(diǎn)上分配數(shù)據(jù)，系統(tǒng)的硬件和軟 件開始時(shí)自動(dòng)在各結(jié)點(diǎn)分

4、配數(shù)據(jù)。在程序運(yùn)行過程中，高速緩存一致性硬件會自動(dòng)地將數(shù)據(jù) 移至需要它的地方。CC-NUMA注重開拓?cái)?shù)據(jù)的局部性和增強(qiáng)系統(tǒng)的可擴(kuò)展性。在實(shí)際應(yīng)用 中，大多數(shù)的數(shù)據(jù)訪問都可在本結(jié)點(diǎn)內(nèi)完成，網(wǎng)絡(luò)上傳輸?shù)闹饕歉咚倬彺鏌o效性信息而不 是數(shù)據(jù)。CC-NUMA和COMA的共同特點(diǎn)是它們都對高速緩存一致性提供硬件支持，而在另一 種訪存模型 NCC-NUMA（Non-Cache Coherent Non-Uniform Memory Access）中，則沒有對 高速緩存的一致性提供硬件支持。NORMA NORMA是No-Remote Memory Access（非遠(yuǎn)程存儲訪問）模型的縮寫。在NORMA 中，

5、所有的存儲器都是處理器私有的，僅能由其處理器訪問。各處理器之間通過消息傳遞方 式通信。MPP多采用這種結(jié)構(gòu)。均勻訪存模型（UMA）：均勻訪存模型（UMA）中所有的物理存儲器均被共享，即處 理器訪問他們的時(shí)間是一樣的。這種系統(tǒng)因?yàn)楦叨鹊馁Y源共享也被稱為緊耦合系統(tǒng)。非均勻訪存模型（NUMA）：非均勻訪存模型（NUMA）的特點(diǎn)是：被共享的存儲物 理上是分布的，所有這些存儲器的集合就是全局地址空間。所以處理處理訪問這些存儲器的 時(shí)間是不一樣的，顯然訪問本地存儲器要比訪問全局共享存儲器或者遠(yuǎn)程存儲器要快些。另 外，存儲器分層次，分為本地存儲器，群內(nèi)共享存儲器，全局共享存儲器。全高速緩存訪存模型（COMA

6、）：是非均勻訪存模型（NUMA）的一種特例，其中處理 各個(gè)節(jié)點(diǎn)無存儲層次之分，各個(gè)節(jié)點(diǎn)的高速緩存構(gòu)成了全部地址空間。一致性高速緩存非均勻存儲訪問模型（CC-NUMA）：每一個(gè)節(jié)點(diǎn)都是一個(gè)對稱多處理 機(jī)，實(shí)際上是一個(gè)分布式多處理共享系統(tǒng)，在商業(yè)中大多數(shù)訪問都在本地中進(jìn)行，而網(wǎng)絡(luò)上 傳輸?shù)臄?shù)據(jù)大多數(shù)用于高速緩存的無效性。非遠(yuǎn)程存儲訪問模型（NORMA）：非遠(yuǎn)程存儲訪問模型（NORMA）特點(diǎn)是：存儲器保 存在本地或者是全局的共享分布式物理結(jié)構(gòu)上，而并非是在遠(yuǎn)程地區(qū)存儲。五種并行計(jì)算機(jī)體系結(jié)構(gòu)1.并行向量處理機(jī)（PVP）貌型結(jié)杓I女又開關(guān)工 工Z3大規(guī)模并行處理機(jī)-CMPP） |SM2對稱多機(jī)系統(tǒng)（S

7、MP）4分布式共享存儲器多機(jī)系統(tǒng)（DSM）C2us1:c3mDesigned lletzwork |5工作站機(jī)群（COW）五種典型的訪存模型答：（1）均勻訪存模型（UMA）：均勻訪存模型（UMA）中所有的物理存儲器均被共享， 即處理器訪問他們的時(shí)間是一樣的。這種系統(tǒng)因?yàn)楦叨鹊馁Y源共享也被稱為緊耦合系統(tǒng)。（2）非均勻訪存模型（NUMA）：非均勻訪存模型（NUMA）的特點(diǎn)是：被共享的存 儲物理上是分布的，所有這些存儲器的集合就是全局地址空間。所以處理處理訪問這些存儲 器的時(shí)間是不一樣的，顯然訪問本地存儲器要比訪問全局共享存儲器或者遠(yuǎn)程存儲器要快 些。另外，存儲器分層次，分為本地存儲器，群內(nèi)共享存儲

8、器，全局共享存儲器。（3）全高速緩存訪存模型（COMA）：是非均勻訪存模型（NUMA）的一種特例，其 中處理各個(gè)節(jié)點(diǎn)無存儲層次之分，各個(gè)節(jié)點(diǎn)的高速緩存構(gòu)成了全部地址空間。（4）一致性高速緩存非均勻存儲訪問模型（CC-NUMA）：每一個(gè)節(jié)點(diǎn)都是一個(gè)對稱多 處理機(jī)，實(shí)際上是一個(gè)分布式多處理共享系統(tǒng)，在商業(yè)中大多數(shù)訪問都在本地中進(jìn)行，而網(wǎng) 絡(luò)上傳輸?shù)臄?shù)據(jù)大多數(shù)用于高速緩存的無效性。（5）非遠(yuǎn)程存儲訪問模型（NORMA）：非遠(yuǎn)程存儲訪問模型（NORMA）特點(diǎn)是：存 儲器保存在本地或者是全局的共享分布式物理結(jié)構(gòu)上，而并非是在遠(yuǎn)程地區(qū)存儲。對于如下的靜態(tài)互連網(wǎng)絡(luò)，給出其網(wǎng)絡(luò)直徑、節(jié)點(diǎn)的度數(shù)、對剖寬度，說明

9、該網(wǎng)絡(luò)是否是一 個(gè)對稱網(wǎng)絡(luò)。對剖寬度8對稱，因?yàn)閺娜我夤?jié)點(diǎn)上觀看網(wǎng)絡(luò)都是一樣的。設(shè)一個(gè)計(jì)算任務(wù)，在一個(gè)處理機(jī)上執(zhí)行需10個(gè)小時(shí)完成，其中可并行化的部分為9個(gè)小時(shí)， 不可并行化的部分為1個(gè)小時(shí)。問：（1）該程序的串行比例因子是多少，并行比例因子是多少？（2）如果有10個(gè)處理機(jī)并行執(zhí)行該程序，可達(dá)到的加速比是多少?（3）如果有20個(gè)處理機(jī)并行執(zhí)行該程序，可達(dá)到的加速比是多少?答：（1） 0.1 0.9-Ws+Wps=-(2)1 + 9 _ x =土26+110-Ws+Wp s=- -WsP=畀=6.89+120什么是并行計(jì)算系統(tǒng)的可擴(kuò)放性？可放性包括哪些方面？可擴(kuò)放性研究的目的是什么？答：一個(gè)計(jì)算

10、機(jī)系統(tǒng)（硬件、軟件、算法、程序等）被稱為可擴(kuò)放的，是指其性能隨處 理機(jī)數(shù)目的增加而按比例提高。例如，工作負(fù)載能力和加速比都可隨處理機(jī)的數(shù)目的增加而 增加。主要包括：并行計(jì)算要調(diào)整的是處理數(shù)p和問題規(guī)模W。兩者可按照不同的比例調(diào)整， 此比例關(guān)系（可能是線性的，多項(xiàng)式的或者指數(shù)型的）反映了可擴(kuò)放的程度。研究目的是：確定解決某類問題用什么并行算法與何種并行體系組織結(jié)合，可以有效的 利用大量處理器。對于運(yùn)行于某體系結(jié)構(gòu)的并行機(jī)上的某種算法，當(dāng)移植到大規(guī)模處理機(jī)上 后運(yùn)行的性能。對于固定的問題規(guī)模，確定在某類并行機(jī)上最優(yōu)的處理器數(shù)與可獲得的最大 加速比。用于指導(dǎo)改進(jìn)算法和并行體系結(jié)構(gòu)，以使并行算法盡可能

11、的充分利用可擴(kuò)充的大 量處理器。五個(gè)基本的并行計(jì)算模型，并說明其各自的優(yōu)缺點(diǎn)。（1）PRAM : SIMD-SM 模型優(yōu)點(diǎn)：適于表示和分析并行計(jì)算的復(fù)雜性；隱匿了并行計(jì)算機(jī)的大部底層細(xì)節(jié)（如通信、同步），從而易于使用。缺點(diǎn)：不適于MIMD計(jì)算機(jī)，存在存儲器競爭和通信延遲問題。（2）APRAM:MIMD-SM 優(yōu)點(diǎn)：保存了 PRAM的簡單性；可編程性和可調(diào)試性（correctness）好；易于進(jìn)行程序復(fù)雜性分析。缺點(diǎn)：不適于具有分布式存儲器的MIMD計(jì)算機(jī)。（3）BSP: MIMD-DM 優(yōu)點(diǎn):把計(jì)算和通信分割開來；使用hashing自動(dòng)進(jìn)行存儲器和通信管理；提供了一個(gè)編程環(huán)境。缺點(diǎn)：顯式的同步機(jī)制限制并行計(jì)算機(jī)數(shù)據(jù)的增加；在一個(gè)Superstep中最多只能傳遞h各報(bào)文。（4）LogP: MIMD-DM 優(yōu)點(diǎn)：可捕捉并行計(jì)算機(jī)的（同步）通信瓶頸（通過 S/R L/g報(bào)文）;可隱匿拓?fù)浣Y(jié)構(gòu)，路由算法和網(wǎng)絡(luò)協(xié)議的細(xì)節(jié)；可用于共享變量，報(bào)文傳遞和數(shù)據(jù)并行處理等方案。缺點(diǎn)：受限于網(wǎng)絡(luò)的通信能力（當(dāng)進(jìn)行處理機(jī)數(shù)量擴(kuò)充時(shí)）；難以計(jì)算同步開銷和進(jìn)行算法描述和設(shè)計(jì)。（5）C3模型