并行計(jì)算總復(fù)習(xí).doc

并行計(jì)算總復(fù)習(xí)題型：1 問答題；2 算法描述；3 走例子說明對(duì)算法的理解第二章SIMD 和 MIMD 所代表的計(jì)算模型是什么？主要區(qū)別和各自的系統(tǒng)結(jié)構(gòu)示意圖。SPMD的含義是什么？若按通訊方式對(duì)并行算法進(jìn)行分類有幾種分類方法，各自的特點(diǎn)是什么？在理想并行計(jì)算模型中（parallel random access machine(PRAM), EREW, CREW, 和CRCW表示的意思是什么？能畫出多處理機(jī)系統(tǒng)中處理單元的基本互連結(jié)構(gòu)圖， Mash, hypercube, W 網(wǎng)絡(luò)， 對(duì)靜態(tài)網(wǎng)絡(luò)的測(cè)度：直徑，連通性，二分寬度(bisection width), cost.能說出一種解決多處理器系統(tǒng)中cache和內(nèi)存數(shù)據(jù)一致性問題的方法。能給出store-and-forward routing 和cut-through routing的思想通訊費(fèi)用是如何計(jì)算的？延遲時(shí)間， ts, th, tw對(duì)Mesh 的X-Y_routing和對(duì)Hypercube的E-Cube routing的路由規(guī)則。如何把linear array, mesh 和hypercube 相互嵌入？G(i,d)函數(shù)的計(jì)算。把復(fù)雜網(wǎng)絡(luò)嵌入的簡(jiǎn)單網(wǎng)絡(luò)，能說明些什么問題？其意義是什么？一般對(duì)簡(jiǎn)單網(wǎng)絡(luò)的帶寬是怎么要求的？第三章dependency graph 的定義及畫法。對(duì)同一問題dependency graph 的畫法是否唯一？并行算法的粒度定義是什么？把processes 影射到processors的基本原則是什么？減少通訊，,在并行算法設(shè)計(jì)時(shí)，有幾種把計(jì)算分解的技術(shù)？能舉例說明。能說明data parallel model, task graph model 和work pool model 的含義。第四章Basic communication operations能畫出下列操作的示意圖one to all broadcast; all to one reductionall to all broadcast; all to all reductionscatter, gather, all reduce, prefix sum，all to all personalized communication. Circular shift,能寫出在hypercube上的one to all broadcast/ all to one reductionall-to-all personal broadcast;all-to-all broadcast;算法以及時(shí)間復(fù)雜性的分析。能舉出2種以上在并行編程中的應(yīng)用列子。第五章并行算法的分析測(cè)度并行算法并行加速比S，效率E和費(fèi)用cost的計(jì)算公式。說明在什么情況下可能出現(xiàn)超線性加速比？何謂費(fèi)用最佳的并行算法cost-optimal？設(shè)計(jì)費(fèi)用最佳的并行算法的思路是什么？Amdahl定理的含義？如何證明？第六章MPI是什么的縮寫，MPI是語言還是一個(gè)函數(shù)庫？能說出三個(gè)MPI的基本函數(shù),并作出解釋。MPI程序的基本結(jié)構(gòu)是什么？MPI程序中容易出現(xiàn)什么形式的死鎖？MPI是通過什么方法，實(shí)現(xiàn)在Mesh上的并行算法？能讀懂MPI程序。第七章Pthead的定義是什么？在pthread中，thread之間的同步，對(duì)關(guān)鍵區(qū)域的共享使用時(shí)是如何實(shí)現(xiàn)的？Mutex 的屬性類型以及使用，條件變量和mutex_lock的一起使用。 Open MP 是什么形式的API?如何實(shí)現(xiàn)并發(fā)程序設(shè)計(jì)的？能看懂Open MP程序第八章并發(fā)實(shí)現(xiàn)矩陣與向量的乘法能給出如何實(shí)現(xiàn)矩陣轉(zhuǎn)置的算法。能寫出Cannon， Fox和簡(jiǎn)單矩陣乘法算法。第九章奇、偶排序的并行算法， 能敘述雙調(diào)（Bitonic）排序的思路以及畫法。知道該算法是如何在超立方體上實(shí)現(xiàn)的。第十章最小生成樹和最短路徑算法的并行實(shí)現(xiàn)；圖的連通分支的并發(fā)實(shí)現(xiàn)；尋找圖的極大獨(dú)立集算法的思想第12章Dynam