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

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