并行計算總復習.doc

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