并行計算-練習(xí)題

2014年《并行計算系統(tǒng)》復(fù)習(xí)題（15分）給出五種并行計算機體系結(jié)構(gòu)的名稱，并分別畫出其典型結(jié)構(gòu)。①并行向量處理機（PVP）②對稱多機系統(tǒng)（SMP）③大規(guī)模并行處理機（MPP）④分布式共享存儲器多機系統(tǒng)（DSM）⑤工作站機群（COW）（10分）給出五種典型的訪存模型，并分別簡要描述其特點。①均勻訪存模型（UMA）：物理存儲器被所有處理機均勻共享所有處理機訪存時間相同適于通用的或分時的應(yīng)用程序類型②非均勻訪存模型（NUMA）：是所有處理機的本地存儲器的集合訪問本地LM的訪存時間較短訪問遠程LM的訪存時間較長③Cache一致性非均勻訪存模型（CC-NUMA）：DSM結(jié)構(gòu)④全局Cache訪存模型（COMA）：是NUMA的一種特例，是采用各處理機的Cache組成的全局地址空間遠程Cache的訪問是由Cache目錄支持的⑤非遠程訪存模型（NORMA）：在分布式存儲器多機系統(tǒng)中，如果所有存儲器都是專用的，而且只能被本地存儲機訪問，則這種訪問模型稱為NORAM絕大多數(shù)的NUMA支持NORAM在DSM中，NORAM的特性被隱匿的3.（15分）對于如下的靜態(tài)互連網(wǎng)絡(luò)，給出其網(wǎng)絡(luò)直徑、節(jié)點的度數(shù)、對剖寬度，說明該網(wǎng)絡(luò)是否是一個對稱網(wǎng)絡(luò)。網(wǎng)絡(luò)直徑：8節(jié)點的度數(shù)：2對剖寬度：2該網(wǎng)絡(luò)是一個對稱網(wǎng)絡(luò)4.（15分）設(shè)一個計算任務(wù)，在一個處理機上執(zhí)行需10個小時完成，其中可并行化的部分為9個小時，不可并行化的部分為1個小時。問：（1）該程序的串行比例因子是多少，并行比例因子是多少？串行比例因子：1/10并行比例因子:9/10如果有10個處理機并行執(zhí)行該程序，可達到的加速比是多少？10/(9/10+1)=5.263（3）如果有20個處理機并行執(zhí)行該程序，可達到的加速比是多少？10/(9/20+1)=6.897（15分）什么是并行計算系統(tǒng)的可擴放性？可放性包括哪些方面？可擴放性研究的目的是什么？一個計算機系統(tǒng)（硬件、軟件、算法、程序等）被稱為可擴放的，是指其性能隨處理機數(shù)目的增加而按比例提高。例如，工作負載能力和加速比都可隨處理機的數(shù)目的增加而增加?？蓴U放性包括:1.機器規(guī)模的可擴放性系統(tǒng)性能是如何隨著處理機數(shù)目的增加而改善的2.問題規(guī)模的可擴放性系統(tǒng)的性能是如何隨著數(shù)據(jù)規(guī)模和負載規(guī)模的增加而改善3.技術(shù)的可擴放性系統(tǒng)的性能上如何隨著技術(shù)的改變而改善可擴放性研究的目的:確定解決某類問題時何種并行算法與何種并行體系結(jié)構(gòu)的組合，可以有效的利用大量的處理器；對于運用于某種并行機上的某種算法，根據(jù)在小規(guī)模處理機的運行性能預(yù)測移植到大規(guī)模處理機上的運行性能;對固定問題規(guī)模，確定最優(yōu)處理機數(shù)和可獲得的最大的加速比（15分）給出五個基本的并行計算模型，并說明其各自的優(yōu)缺點。①PRAM：SIMD-SM優(yōu)點：適于表示和分析并行計算的復(fù)雜性；隱匿了并行計算機的大部底層細節(jié)（如通信、同步），從而易于使用。缺點：不適于MIMD計算機，存在存儲器競爭和通信延遲問題。②APRAM:MIMD-SM優(yōu)點：保存了PRAM的簡單性；可編程性和可調(diào)試性（correctness）好；易于進行程序復(fù)雜性分析。缺點：不適于具有分布式存儲器的MIMD計算機。③BSP：MIMD-DM優(yōu)點:把計算和通信分割開來；使用hashing自動進行存儲器和通信管理；提供了一個編程環(huán)境。缺點：顯式的同步機制限制并行計算機數(shù)據(jù)的增加；在一個Superstep中最多只能傳遞h各報文。④LogP：MIMD-DM優(yōu)點：可捕捉并行計算機的（同步）通信瓶頸（通過發(fā)送或接收L/g個報文）；可隱匿拓撲結(jié)構(gòu)，路由算法和網(wǎng)絡(luò)協(xié)議的細節(jié)；可用于共享變量，報文傳遞和數(shù)據(jù)并行處理等方案。缺點：受限于網(wǎng)絡(luò)的通信能力（當進行處理機數(shù)量擴充時）；難以計算同步開銷和進行算法描述和設(shè)計。⑤C3模型優(yōu)點：考慮了一對一和一對多的通信方案細節(jié)；反應(yīng)了受擁塞影響的計算性能。缺點：模型的參數(shù)較復(fù)雜；算法的設(shè)計與分析和計算機的結(jié)構(gòu)狀況有關(guān)。（15分）說明并行算法的基本設(shè)計過程。①劃分（P）目的開發(fā)并行性的可行性方法數(shù)據(jù)分解+功能分解規(guī)劃常用的數(shù)據(jù)，通信頻率的進程分為一組判據(jù)（Checklist的設(shè)計問題）②通信（C）目的根據(jù)任務(wù)執(zhí)行的需要交換數(shù)據(jù)后；協(xié)調(diào)任務(wù)的執(zhí)行通信要求在域分解中的確定通信要求在功能分解時，容易確定通信需求通信模式局部通信結(jié)構(gòu)化靜態(tài)同步全局通信非結(jié)構(gòu)化動態(tài)異步判據(jù)（測試表的設(shè)計問題）③組合（A）目的按性能要求和時間的代價來