(完整word版)并行計(jì)算總復(fù)習(xí)之秘笈

1、并行計(jì)算總復(fù)習(xí)第一章：1并行計(jì)算與串行計(jì)算在算法和編程上有哪些顯著差異？ 答：并行算法設(shè)計(jì)與并行計(jì)算機(jī)處理器的拓?fù)溥B接相關(guān)并行算法設(shè)計(jì)和采用的并行計(jì)算模型有關(guān)。并行計(jì)算有獨(dú)自的通訊函數(shù)并行算法設(shè)計(jì)時(shí)，如何將問題分解成獨(dú)立的子問題是科學(xué)研究問題，并非所有的問 題都可以進(jìn)行分解。2多核與多處理機(jī)的異同點(diǎn)？多處理機(jī)：把多個(gè)處理器通過網(wǎng)絡(luò)互連形成一個(gè)新機(jī)器。可以是專用，也可以是通用。 拓?fù)溥B接是可以改變的。多核：在過去單個(gè)處理器芯片上實(shí)現(xiàn)多個(gè)執(zhí)行核”。但這些執(zhí)行核都有獨(dú)立的執(zhí)行命令集 合和體系結(jié)構(gòu)。這些獨(dú)立的執(zhí)行核+超線程SMT技術(shù)組成多核處理器3對(duì)單處理器速度提高的主要限制是什么？答：晶體管的集成密

2、度，功耗和 CPU表面溫度等第二章1 SIMD和MIMD所代表的計(jì)算模型是什么？主要區(qū)別和各自的 系統(tǒng)結(jié)構(gòu)示意圖SPMD的 含義是什么？SIMD指單指令多數(shù)據(jù)流模型；MIMD指多指令多數(shù)據(jù)流模型；SPMD指單程序多數(shù)據(jù)流模型，在SIMD中把指令改為程序表示每個(gè)處理器并行的執(zhí)行程序。SIMDMIMD硬件較少處理器較多處理器內(nèi)存一個(gè)尋址系統(tǒng)，存儲(chǔ) 量小多個(gè)尋址系統(tǒng)，存儲(chǔ) 量大耗費(fèi)較高，難開發(fā)易于開發(fā)（多個(gè)商業(yè) 組件可用）加速高取決于應(yīng)用PE: Processing tlemeaitPEPE 1is. ccmlnsl LinilPE4 卜contro unit -bFigure 2.3 A typi

3、cal SIMD architecture (a) and a typical MIMD architecture (b).2若按通訊方式對(duì)并行算法進(jìn)行分類有幾種分類方法，各自的特點(diǎn)是什么？ 基于共享地址空間：并行平臺(tái)支持一個(gè)公共的數(shù)據(jù)空間，所有處理器都可以訪問這些空 間。處理器通過修改存儲(chǔ)在共享地址空間的數(shù)據(jù)來實(shí)現(xiàn)交互?；谙鬟f：消息傳遞平臺(tái)有 p個(gè)處理節(jié)點(diǎn)構(gòu)成，每個(gè)節(jié)點(diǎn)有自己的獨(dú)立地址空間 運(yùn)行在不同節(jié)點(diǎn)上的進(jìn)程之間的交互必須用消息來完成，稱為消息傳遞。這種消息交換用來 傳遞數(shù)據(jù)、操作以及使多個(gè)進(jìn)程間的行為同步。3在理想并行計(jì)算模型中(并行隨機(jī)訪問計(jì)算機(jī) parallel random

4、 access machine(PRAM), EREW, ERCW CREW,和CRCW表示的意思是什么？EREW:互斥讀互斥寫，這一類的PRAM獨(dú)占訪問內(nèi)存單元，不允許并發(fā)的讀寫操作。最弱 的PRAM模型，對(duì)內(nèi)存訪問提供最小的并發(fā)性。CREW:并發(fā)讀互斥寫。對(duì)內(nèi)存單元允許多讀，但對(duì)內(nèi)存位置多寫是串行的ERCW :互斥讀并發(fā)寫。對(duì)內(nèi)存單元允許多寫，但多讀是串行的。CRCW:并發(fā)讀并發(fā)寫。對(duì)內(nèi)存單元允許多讀多寫。最強(qiáng)大4能畫出多處理機(jī)系統(tǒng)中處理單元的基本互連結(jié)構(gòu)圖，Mesh, hypercube,1網(wǎng)絡(luò)，注意對(duì)頂點(diǎn)編號(hào)的要求。Figure 2.15 Linear arrays: (a) with

5、 no wraparound links; (b) with wraparound link.Figure 2J6 Two and three dimensional meshes: (a) 2-D mesh with no wraparound; (b) 2-D mesh with wraparound link (2-D torus); and (c) a 3-D mesh with no wraparoundMesh:二維網(wǎng)格中每個(gè)維有sqrt (p)個(gè)節(jié)點(diǎn)，p為處理器的數(shù)目。hypercube:p為處理器數(shù)目，超立方體結(jié)構(gòu)有l(wèi)ogP維，每維上有兩個(gè)節(jié)點(diǎn)O-D hypercube2-D

6、hypercubeLEO3D hyjKrcxilKl-D liyjxrculK4-1 hypcreLLbi：Figure 2J7 Construction of hypercubes from hypercubes of lower dimerision.超立方體的節(jié)點(diǎn)編號(hào)很有用，有兩個(gè)p/2各節(jié)點(diǎn)的子立方體的編號(hào)，就可以一個(gè)前面加0 一個(gè)前面加1實(shí)現(xiàn)，這樣標(biāo)號(hào)0110的節(jié)點(diǎn)和標(biāo)號(hào)0101的節(jié)點(diǎn)相隔兩個(gè)鏈路因?yàn)樗麄冇袃晌徊煌再|(zhì)以此類推門網(wǎng)絡(luò)：000OOJ()1()01110010J11()1110000010100111U0J01U01|Figure 2J2 A complete omeg

7、a network connecting eight inputs and eight outputs.設(shè)p個(gè)處理器processor （輸入），p個(gè)存儲(chǔ)區(qū)bank （輸出）；該網(wǎng)絡(luò)有sqrt （p）級(jí) 輸入：i ；輸出：jj=2i，0=i=p/2-1;j=2i+1-p,p/2=i=p-1.數(shù)據(jù)選路時(shí)，假設(shè)從s （二進(jìn)制表示）傳送到t,從最高位起開始比較，相同的位走直通，不 同的位走交叉。5知道對(duì)靜態(tài)網(wǎng)絡(luò)的常用測(cè)度：直徑，連通性，二分寬度（bisection width）, cost.直徑：網(wǎng)絡(luò)中兩個(gè)處理節(jié)點(diǎn)之間的最長距離稱為網(wǎng)絡(luò)直徑。（越小越好）連通性：網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)間路徑多重性的度量。

8、連通性的一個(gè)度量是把一個(gè)網(wǎng)絡(luò)分 成兩個(gè)不連通的網(wǎng)絡(luò)需要?jiǎng)h除的最少弧數(shù)目。（越大越好）二分寬度：把網(wǎng)絡(luò)分成兩個(gè)相等網(wǎng)絡(luò)時(shí)必須刪去的最小通信鏈路數(shù)目。（越大越好）cost：網(wǎng)絡(luò)中所需的通信鏈路的數(shù)量或線路數(shù)量。6能說出一種解決多處理器系統(tǒng)中 cache和內(nèi)存數(shù)據(jù)一致性問題的方法。（偵聽和基于目錄） 用無效協(xié)議維持一致性，并用基于目錄的系統(tǒng)來實(shí)現(xiàn)一致性協(xié)議?；谀夸洠簽槿謨?nèi)存增加一個(gè)目錄，維護(hù)一個(gè) bitmap，表示已緩存的處理器及相應(yīng)的數(shù)據(jù)項(xiàng)狀態(tài)。 三狀態(tài)協(xié)議含有無效、臟以及共享三種狀態(tài)。工作原理：當(dāng)一個(gè)處理器 P1修改了共享數(shù)據(jù)，P1修改bitmap,state為dirty,它自己可以繼續(xù) 修

9、改。當(dāng)另一處理器P2需要讀該數(shù)據(jù)，目錄告訴它p1目前擁有該數(shù)據(jù)，并通知p1更新狀態(tài), 并把數(shù)據(jù)送給P2.優(yōu)點(diǎn)：減少數(shù)據(jù)無謂的移動(dòng)和更新（把空間分的更細(xì)） 缺點(diǎn)：連接復(fù)雜性高0（mp）7能給出store-and-forward routing和cut-through routing的思想。通訊費(fèi)用是如何計(jì)算的？延遲時(shí)間，ts, th, twstore-a nd-forward routi ng:在此過程中，消息穿過有多個(gè)鏈路的路徑時(shí)，路徑上的每個(gè)中間節(jié)點(diǎn)接受和存儲(chǔ)完整的消息后，就把消息轉(zhuǎn)發(fā)給下一個(gè)節(jié)點(diǎn)。T = ts+(m tw+ th) l，th為消息頭導(dǎo)致的開銷。i為鏈路數(shù)。m為消息字長。cu

10、t-through rout ing:在此過程中，消息被分成固定大小的單元，稱為數(shù)據(jù)片。首先從源節(jié)點(diǎn)向目的節(jié)點(diǎn)發(fā)送跟蹤程序以建立兩點(diǎn)間的連接。連接完成后，數(shù)據(jù)片就一個(gè)接一個(gè)的 發(fā)送。中間節(jié)點(diǎn)無需等待所有消息到達(dá)就可以發(fā)送數(shù)據(jù)片。當(dāng)某一數(shù)據(jù)片被中間節(jié)點(diǎn)接收后，該數(shù)據(jù)片被傳到下一節(jié)點(diǎn)。與store-a nd-forward rout ing不同，每個(gè)中間節(jié)點(diǎn)無需用緩沖區(qū)空間存儲(chǔ)完整的信息。因此，中間節(jié)點(diǎn)只需要使用更少的內(nèi)存和帶寬，速度也快得多。T = ts + m tw + th*l，th為消息頭導(dǎo)致的開銷。I為鏈路數(shù)。m為消息字長。Tcomm= ts+lth+mtw ；1) startuptim

11、e (Ts):在數(shù)據(jù)包上加上必要的頭、尾信息，錯(cuò)誤檢測(cè)矯正信息、執(zhí)行路由算法時(shí) 間以及建立節(jié)點(diǎn)與路由器之間的接口。2) per-hop time (Th): node latency from u to v;3 )per-word-transfer time(Tw)(每個(gè)字的傳輸時(shí)間)，如果通道帶寬為r個(gè)字符每秒，每個(gè)字符 的傳輸時(shí)間為Tw=1/r8 對(duì) Mesh 的 X-Y_routing 和對(duì) Hypercube 的 E-Cube routing的路由規(guī)則。Mesh的X-Y_routing :消息首先沿X為出發(fā)，直到到達(dá)目標(biāo)節(jié)點(diǎn)的列，再沿丫維到達(dá)目的節(jié)點(diǎn)。其路徑長度為L = |Sx-Dx|

12、+|Sy-Dy|;Sx, Sy為源節(jié)點(diǎn)坐標(biāo)；Dx，Dy為目標(biāo)節(jié)點(diǎn)坐標(biāo)。 Hypercube的E-Cube routing:考慮節(jié)點(diǎn)數(shù)為p的d維超立方體。令 Ps和Pd分別為源節(jié)點(diǎn)和 目標(biāo)節(jié)點(diǎn)的編號(hào)。在E-Cube算法中，節(jié)點(diǎn)Ps計(jì)算Ps (+) Pd的值并沿k維發(fā)送消息，其中k 是Ps (+) Pd中的最低非零有效位的位置。每個(gè)中間節(jié)點(diǎn)Ps收到信息，計(jì)算出Ps (+) Pd，再將消息沿著與最低非零有效位對(duì)應(yīng)的維轉(zhuǎn)發(fā)，直到消息到達(dá)目標(biāo)節(jié)點(diǎn)。9如何把linear array, mesh和hypercube相互嵌入？ G(i,d)函數(shù)的計(jì)算。 linear array 嵌入至U hypercube：

13、含2d個(gè)節(jié)點(diǎn)的linear array可以嵌入到d維超立方體中，只需把linear array中的節(jié)點(diǎn)i映射到hypercube的節(jié)點(diǎn)G (i,x)上。函數(shù)G (i，x)定義如下：G (0， 1) =0;G (1,1) =1;G (i，x+1) = G (i，x)iG(i,r-1)|G(j,s-1)-mesh 嵌入至U linear array1ccUl10把復(fù)雜網(wǎng)絡(luò)嵌入的簡(jiǎn)單網(wǎng)絡(luò)，能說明些什么問題？其意義是什么？ 一般對(duì)簡(jiǎn)單網(wǎng)絡(luò)的帶寬 是怎么要求的？意義：高維上的網(wǎng)絡(luò)一般布線復(fù)雜，有線的交叉和長短不一等問題。而加寬通訊帶寬后的低 維互連網(wǎng)絡(luò)，可以取代高維復(fù)雜網(wǎng)絡(luò)。如果帶寬增加到可以抵消互連擁

14、塞，就可按稠密網(wǎng)絡(luò) 一樣運(yùn)行。AVV*第二早11 depe ndency graph的定義及畫法。對(duì)同一問題 depe nde ncy graph的畫法是否唯一？depe nde ncy graph表示任務(wù)間的依賴關(guān)系和任務(wù)的執(zhí)行次序關(guān)系。是一種有向無環(huán)圖，節(jié)點(diǎn)表 示任務(wù)，邊表示節(jié)點(diǎn)間的依賴性。邊 表示u任務(wù)執(zhí)行完后v任務(wù)才能執(zhí)行。.不唯一 13并行算法的粒度定義是什么？粒度大小在理論上和在實(shí)際上對(duì)并行算法的影響。分解問題得到的任務(wù)數(shù)量和大小決定了分解的粒度，將任務(wù)分解成大量的細(xì)小任務(wù)稱為細(xì)粒 度，而將任務(wù)分解成少量的大任務(wù)稱為粗粒度。14在進(jìn)程調(diào)度中，把processes影射到process

15、ors的基本原則是什么？減少通訊,1）設(shè)法將相互獨(dú)立的任務(wù)映射到不同的進(jìn)程中以獲得最大并發(fā)度；2）確保關(guān)鍵路徑上的任務(wù)一旦可執(zhí)行就去執(zhí)行它們，以使得總計(jì)算時(shí)間最短3）映射相互交互的任務(wù)到同一進(jìn)程以便最小化進(jìn)程間的交互。15在并行算法設(shè)計(jì)時(shí)，有幾種把計(jì)算分解的技術(shù)？能給出名稱并能舉例說明。 Recursive decomposition遞歸分解）：可能產(chǎn)生太多任務(wù)使程序變慢mnjl.SmnilTi他or快速排序 Data decompositi on : based on the in depe ndency of data 基于數(shù)據(jù)獨(dú)立性分解）：根據(jù)對(duì)輸出 數(shù)據(jù)的劃分來劃分任務(wù)。例如：矩陣相乘

16、 Exploration decomposition （探索分解）：對(duì)應(yīng)于人工智能中基于解空間探索方法的問題求解， 例如迷宮游戲 Speculative decomposition （投機(jī)分解）：用于分支語句中，在未能決定分支轉(zhuǎn)向時(shí)，并行 的計(jì)算多個(gè)分支，當(dāng)最終決定轉(zhuǎn)向時(shí)，正確的分支對(duì)應(yīng)的計(jì)算將被利用，其他的被丟棄?；旌戏纸?，將前面的分解方法組合應(yīng)用，在計(jì)算的不同階段使用不同的分解方法。例如，快速排序，先數(shù)據(jù)分解然后再使用遞歸分解16為了解決由于數(shù)據(jù)分布密度不均勻問題，能說出 3種以上可以幫助使并行任務(wù)的負(fù)載接近 平衡的方法或思路。循環(huán)塊分配、隨機(jī)塊分配、圖劃分17 能說明 data para

17、llel model, task graph model和 work pool model 的含義。 data parallel model （數(shù)據(jù)并行模型）：任務(wù)被靜態(tài)或半靜態(tài)的映射到進(jìn)程，并且每個(gè)任務(wù)都 對(duì)不同的數(shù)據(jù)進(jìn)行相似的操作。這種并行性是把同樣的操作并發(fā)的運(yùn)用到不同的數(shù)據(jù)項(xiàng)上產(chǎn) 生的結(jié)果，因此稱為數(shù)據(jù)并行。 task graph model （任務(wù)圖模型）：使用任務(wù)之間的相互關(guān)系來提高本地性或減少交互開銷。 如果某一問題中，與任務(wù)對(duì)應(yīng)的數(shù)據(jù)量遠(yuǎn)大于與任務(wù)相對(duì)應(yīng)的計(jì)算，則通常用任務(wù)圖模型來 解決此類問題。 work pool model （工作池模型）：動(dòng)態(tài)映射任務(wù)到進(jìn)程以保持負(fù)載平衡

18、，在這種映射中，任 何任務(wù)可能由任何進(jìn)程執(zhí)行。進(jìn)程可以產(chǎn)生工作并把它添加到工作池中。第四章18 Basic com muni cati on operati ons對(duì)偶的概念是什么？在對(duì)通訊原語研究中，為什么強(qiáng)調(diào)操作對(duì)之間的對(duì)偶性？能給出 3個(gè)以 上的對(duì)偶原語。通信操作的對(duì)偶是原始操作的逆操作，可以通過逆轉(zhuǎn)原操作中的通信方向和消息序列來完 成。強(qiáng)調(diào)對(duì)偶的意義在于，研究一個(gè)問題，其對(duì)偶問題的解可以類似解決。 on e-to-all broadcast / all-to-one reduct ion, all-to-all broadcast / all-to-all reducti on, sc

19、atter / gather19能畫出下列操作的示意圖，并能解釋通信原語所完成的任務(wù)是什么one to all broadcast; all to one reducti onall to all broadcast; all to all reducti onscatter, gather, all reduce, prefix sumall to all pers on alized com muni cati on. Circular shift one to all broadcast; all to one reduct ion一個(gè)進(jìn)程發(fā)送相同的數(shù)據(jù)給其他所有的進(jìn)程；來自所有進(jìn)程的數(shù)

20、據(jù)通過一個(gè)相關(guān)的操作符組合起來，并被累加到一個(gè)目標(biāo)進(jìn)程的緩沖區(qū)中。Cfhc4o-all Bf&adcasJiMaM MM： :： J J （ 0 ）: j ：（JS- 0All-w-?ne RcduccionvFigure- 4.1broadcast and all-lo S1,S2,Sp1,其中iSi =遲 nj蘭 all to all pers on alized com muni cati on：每個(gè)節(jié)點(diǎn)發(fā)送一個(gè)大小為m的不同消息給其他每個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都發(fā)送不同的消息給不同 的節(jié)點(diǎn)，而在多對(duì)多廣播中，每個(gè)節(jié)點(diǎn)發(fā)送相同的消息給所有其他節(jié)點(diǎn)。J.F-1M卜Mp.ijMpj p.|%Mi.i

21、Mpi.iM 1.0M l.lMit.i%MpinAll-kFull perxonalLreLl.Mfl.l/AcommuTBicuiln 0- i xlz+ ty -a-1J_.A (1 !* - *眇Figure 416All to-311 personalized communication. Circular shift,循環(huán)q移位定義：在一個(gè)p節(jié)點(diǎn)的總體中，節(jié)點(diǎn)i發(fā)送一個(gè)數(shù)據(jù)包給節(jié)點(diǎn)（i+q） mod p,其中 Ovqvp。移位操作在某些矩陣計(jì)算及字符串、圖像模式匹配上都有應(yīng)用20能寫出在hypercube上的 one to all broadcast/1.2,prncrriure

22、GENER AL-ONE.TO-ALL.BClJ, myJd. Aoj/rtv, X) h-eiia工4.5.阻ufFMdfJ ；三XORSource = 5mask := 2 - 1!hir jt := 0 do /* Ouier loop */ft.:= wsJvJl XOR 2J ; /* Set bit i of 附sk lo 0 */ if (myAirtfiafJif AND musk I () thens11).ifAND 2) = (1 then: my virtualXOR 2；send X io tXOR Anw/txiL/* Concn YiFMtge to【be luh

23、el of ihe physical 血口創(chuàng) km */IL11ehv：= 腫丁衛(wèi)帀卵審XORB.receive X fromXOR wintry/* Conc ert 訐皿曲他厲卍 to the Isibel of the physiciil wnirce */14.15.16.Cndrkr.rndforie hiJ GCNERAI JJNE.TCXAIJ；all to one reduction P114P115L-3.procedure ALL_TO-ONE_REDUCE(Cin彈冋他H myjd XOR；：可以技仕思少殲6.7r8.9.sendffttrtiicr.receh f 4甘

24、心曲、J tYcwn fnclfor;end ALL-TO-ALL_PFiRSONAL all-to-all broadcast; P118L procedure ALL-TOLL-BC-HCUBEtflprjsA ah譏 nmd卄2. beuin3. mw/ :=制、犢.4 for / := 0 to E = 1.cost-optimal:如果在并行計(jì)算機(jī)上，求解問題的成本作為屬于數(shù)據(jù)大小的函數(shù)，與在單片機(jī) 上的已知最快串行算法有著同樣的漸進(jìn)增長，那么稱并行系統(tǒng)是成本最優(yōu)的。設(shè)計(jì)費(fèi)用最優(yōu)的并行算法思路： 把數(shù)據(jù)劃分為p個(gè)部分 用p個(gè)處理器分別來處理這p個(gè)部分 用并行算法將p個(gè)結(jié)果合并 根據(jù)費(fèi)

25、用最優(yōu)得出p的值使p滿足n = $ qplogp)22 Amdahl定理的含義？如何證明？Amdahl定理：一個(gè)規(guī)模為 W的問題的串行部分為 Ws那么，不管用多少處理器，W/Ws都是其加速比的上界。證明：因?yàn)閃 = Wp+WsTs = WTp=Ws+Wp/p又因?yàn)镾= Ts/Tp則 S= W/(Ws+Wp/p)= (W/Ws)/(1+Wp/pWs)因?yàn)閜-無窮大,則S- W/Ws第六章23 MPI是什么的縮寫，MPI是語言還是一個(gè)函數(shù)庫？MPI: the Message Pass ing In terface MPI is a fun cti on library，used with othe

26、rprogram ming Ian guages24能說出三個(gè)MPI的基本函數(shù),并作出解釋MPI_I nitMPI_Fi nalize MPI_Comm_size MPI_Comm_ra nk MPI_se nd MPI_Recv初始化MPI終止MPI確定進(jìn)程個(gè)數(shù)確定被叫進(jìn)程的標(biāo)號(hào) 發(fā)送接收25 MPI程序的基本結(jié)構(gòu)是什么？ 一般的 MPI程序都有MPI說明有哪些? 異步模式，松散同步模式啟動(dòng)和終止MPIMPIni t(i nt *argc, char *argv) MPI_Fi nalize()獲取信息MPI_Comm_size(MPI_Comm comm, i nt *size)MPI_C

27、omm_ra nk(MPI_Comm comm, i nt *rank)發(fā)送和接收消息一MPI_Se nd()MPI_Recv()26 MPI程序中容易出現(xiàn)什么形式的死鎖? 發(fā)送與接受順序上的死鎖27 MPI是通過什么方法，實(shí)現(xiàn)在 Mesh上的并行算法？能讀懂 MPI程序MPI_Cart_create(comm,2,10,1,1,&comm_2d)從最初申請(qǐng)到的并發(fā)進(jìn)程集合組成 2維網(wǎng)格int MPI_Comm_ra nk(MPI_comm_old, MPI_Comm_new)把過去的id變換成新的2維網(wǎng)格下的id值int MPI_Cart_ra nk(MPI_Comm comm_cart,

28、i nt *coords, int *rank)基于2維網(wǎng)格后的2維坐標(biāo)，得到2維網(wǎng)格下的進(jìn)程id)int MPI_Cart_coord(MPI_Comm comm_cart, i nt rank, int maxdims, int *coord in ate) 根據(jù)在新的2維環(huán)境下進(jìn)程的id，返回在2維網(wǎng)格下的坐標(biāo)，coordinate是數(shù)組 第七章28 Pthead的定義是什么？ Pthread程序一般要包含哪些語句？IEEE指定的一個(gè)標(biāo)準(zhǔn)的線程 API，POSIX API。 POSIX也稱為Pthread 線程的創(chuàng)建、終止 pthread_create pthread_exit等待所有線

29、程運(yùn)行完畢以便完成結(jié)果的合并pthread_join 29在pthread中thread之間的同步，對(duì)關(guān)鍵區(qū)域的共享使用時(shí)是如何實(shí)現(xiàn)的？使用mutex-lock(互斥鎖)使得各個(gè)線程互斥的訪問關(guān)鍵區(qū)域。要訪問關(guān)鍵區(qū)域，線程必須首 先獲得互斥鎖并鎖定pthread_mutex_lock()，離開關(guān)鍵區(qū)域后，要進(jìn)行解鎖 pthread_mutex_unlock()，mutex-lock被一個(gè)線程鎖定后，不允許其他的線程進(jìn)入關(guān)鍵區(qū)域。30 Mutex的屬性類型以及使用，條件變量和mutexock的一起使用。能用Pthread語句寫 出簡(jiǎn)單的多線程之間對(duì)共享資源的共享的代碼。一正?；コ怄i：在任意時(shí)刻，

30、只允許一個(gè)線程鎖定互斥鎖，已獲得互斥鎖的線程若試圖再次 鎖定它，將導(dǎo)致死鎖。遞歸互斥鎖：允許單一的線程多次鎖定互斥鎖，線程每鎖定一個(gè)互斥鎖時(shí)，鎖計(jì)數(shù)器加1,每次解鎖計(jì)數(shù)器減1,如果任何其他線程想成功鎖定一個(gè)遞歸互斥鎖，鎖計(jì)數(shù)器必須為0.錯(cuò)誤檢查互斥鎖：一個(gè)線程只能鎖定一個(gè)互斥鎖一次，當(dāng)線程試圖鎖定一個(gè)已經(jīng)鎖定的互 斥鎖時(shí)，錯(cuò)誤檢查互斥鎖將返回一個(gè)錯(cuò)誤而不是死鎖。31 Open MP是什么形式的API?如何實(shí)現(xiàn)并發(fā)程序設(shè)計(jì)的？ OpenMP是一種可以用FORTRAN,(以及C+在共享地址空間計(jì)算機(jī)上進(jìn)行編程的指令性的 API。OpenM命令提供對(duì)并發(fā)，同步以及數(shù)據(jù)處理的支持，但不需要顯式設(shè)置互斥

31、鎖、條件 變量、數(shù)據(jù)范圍以及初始化。使用parallel命令來創(chuàng)建一組線程#pragma omp parallel clause list/parallel segme nt每個(gè)線程執(zhí)行parallel segment中內(nèi)容Parallel和命令for、sections 起使用實(shí)現(xiàn)迭代和任務(wù)的并發(fā)。 for命令用來在多個(gè)線程間分割并行迭代空間，一般形式如下：#pragma omp for clause list/* for loop*/ sections命令用于對(duì)非循環(huán)的并行任務(wù)分配，形式如下：#pragma omp sect ions clause list#pragma omp sect

32、ion taskA();#pragma omp sect iontaskB();每個(gè)段(即為相應(yīng)的任務(wù))分配給一個(gè)線程32能用Open MP寫出矩陣與向量，矩陣之間和易于并行計(jì)算的程序代碼。 矩陣乘#pragma omp parallel default(private) shared (a, b, c, dim) nu m_threads(4) #pragma omp for schedule(static) for (i = 0; i dim; i+) for (j = 0; j dim; j+) c(i,j) = 0;for (k = 0; k dim; k+) c(i,j) += a(

33、i, k) * b(k, j);第八章并發(fā)實(shí)現(xiàn)矩陣與向量的乘法能給出如何實(shí)現(xiàn)矩陣轉(zhuǎn)置的算法。能寫出 Cannon,Fox和簡(jiǎn)單矩陣乘法算法。33并發(fā)實(shí)現(xiàn)矩陣與向量的乘法。A X帶狀劃分的矩陣-向量乘法?劃分（行帶狀劃分）:Pi存放xi和a （i,0） ,a （i,1），,a （i,n-1）,并輸出yi ?算法：對(duì)p=n情形 每個(gè)Pi向其他處理器播送xi（多到多播送）; 每個(gè)Pi計(jì)算；?注：對(duì)pn情形,算法中Pi要播送X中相應(yīng)的n/p個(gè)分量棋盤劃分的矩陣-向量乘法?劃分（塊棋盤劃分）:Pi,j存放ai,j, xi置入Pi,i中?算法：對(duì)卩=門2情形 每個(gè)Pi,i向Pj,i播送xi（一到多播送）;

34、 按行方向進(jìn)行乘-加與積累運(yùn)算，最后一列Pi,n-1收集的結(jié)果為yi;?注：對(duì)p n2情形,p個(gè)處理器排成p p的二維網(wǎng)孔，算法中Pi,i向Pj,i播送X中相應(yīng)的n/ ； p個(gè)分量34能給出如何實(shí)現(xiàn)矩陣轉(zhuǎn)置的算法 算法：按mesh連接進(jìn)行塊轉(zhuǎn)置（不同處理器間）進(jìn)行塊內(nèi)轉(zhuǎn)置（同一處理器內(nèi)）35能寫出Cannon, Fox和簡(jiǎn)單矩陣乘法算法。Cannon P255初始時(shí)，把子矩陣Aij和Bij分配給處理器Pij 矩陣A的第i行循環(huán)左移i步，矩陣B的第j列循環(huán)上移j步；t=p ; 各處理器A塊與B塊進(jìn)行乘-加運(yùn)算；t-; if （t0） ,A矩陣每行循環(huán)左移1步，B矩陣每列循環(huán)上移1步上面算法中，每

35、個(gè)進(jìn)程Pij中一共進(jìn)行了 . p次Aik與Bkj （ 0豈k豈.p -1）的相乘，從而完 成矩陣A和B的乘法運(yùn)算Fox課件初始時(shí)，把子矩陣Aij和Bij分配給進(jìn)程Pij （同Cannon） Ai,i向所在行的其他處理器進(jìn)行一到多播送； 各處理器將收到的A塊與原有的B塊進(jìn)行乘-加運(yùn)算； B塊向上循環(huán)移動(dòng)一步； 如果Ai,j是上次第i行播送的塊，本次選擇 A（j*）mod萬向所在行的其他處理器進(jìn)行一 到多播送； 轉(zhuǎn)執(zhí)行p -1次；第九章36奇、偶排序的并行算法，能敘述雙調(diào)（Bitonic）排序的思路以及畫法。知道該算法是如何在超立方體上實(shí)現(xiàn)的。奇-偶排序的并行算法考慮每個(gè)進(jìn)程一個(gè)元素的情況。在奇數(shù)

36、排序階段，每個(gè)奇數(shù)下標(biāo)的進(jìn)程將其元素與其右邊的相鄰元素進(jìn)行比較-交換；同樣，在偶數(shù)排序階段，每個(gè)偶數(shù)下標(biāo)的進(jìn)程將其元素與其右邊的相鄰元素進(jìn)行比較-交換。1.procedure ODOEVEN_FAR(n)2.begin3.id ；= process1 s labelfor i ：= 1 to rt do6.begin6.if i odd then7if b odd pare-exchange_tnin(id + 1);9else10.- 1；11.if i is eventhen12.If id is even pare-exchange-min(id +

37、 1);U.else15compare-exchange_mcix(id 1 )：16.end for17.end ODD-EVEN_fR雙調(diào)排序 an-1 ; 令子序列si = minaO,an/2,mina1,an/2+1,，min1an!21s2 = maxaO,an/2,maxa1,an/2+1,maxn/2-1,an-1則si與s2都是雙調(diào)序列且si中每個(gè)元素都小于s2中元素。這樣原問題s排序就化簡(jiǎn)為兩 個(gè)較小的雙調(diào)序列排序，并將結(jié)果連接起來。上述一個(gè)雙調(diào)序列劃分成兩個(gè)較小雙調(diào)序列的MOOoooi、fBj-5Criaj吒,flJ0ui91?mmJ1211丿gJ10rJJ.AH廠iqa

38、14JA14k14ufPi12011125LdU40tr40Jri20J23IrJ351 inn巧35fJ丿kJujri40a t ni一1上23Jj門h狎VJdO11U1ur 18U18J閒k$95uriJr90 mqL?20勺y40Ly、rJ、?5IlliaIzaJ將任意序列轉(zhuǎn)化為雙調(diào)序列并最終完成排序/ /label：進(jìn)程標(biāo)號(hào)d:超立方體維數(shù)1. procedure BfTONICSORTC/aZjci, d)2. beg in3. for i ：- 0 to 1 do4. for j ：= i downto 0 do5. if (i + l)si bit of label 豐 jth

39、bit of label then6. comp_exchange_max 0);7. eke8, comp - exchange9. end BITONICSORTWiiesoooo00010010001101000101011001111000100110101011HOT noi1110nil BM2 BM4 BM8 BM16e BMP BM2 BM4 BM2 BM2 BN141 BM2G BN1811 BM2 BM4 BM2第十章37最小生成樹和最短路徑算法的并行實(shí)現(xiàn)；P319 P321最小生成樹Prim算法：設(shè)G( V，E)為加權(quán)無向連通圖，A=( ai，j)為加權(quán)鄰接矩陣。用 Vt

40、來保存最小生成樹構(gòu) 造過程中的頂點(diǎn)。維護(hù)一個(gè)數(shù)組 d,對(duì)于每個(gè)頂點(diǎn)v (V -Vt)，dv中保存從Vt中的任何頂 點(diǎn)到頂點(diǎn)v的邊中最小的權(quán)值。 任選一點(diǎn)r加入Vt，dr=O 對(duì)于所有v (V -VT)，若邊(r，v)存在，則令dv=w(r,v)，否則令dv=: while Vt =V do找到一個(gè)頂點(diǎn) u滿足 du=mindv| v (V -VT);將u加入到集合Vt ；對(duì)于所有v (V -Vt)，更新dv的值；en dwhile并行形式：令p為進(jìn)程數(shù)，將集合V劃分為p個(gè)子集，每個(gè)子集分配給不同的進(jìn)程。每個(gè)進(jìn)程Pi存儲(chǔ)數(shù) 組d中與Vi對(duì)應(yīng)的部分。在while循環(huán)的每次迭代中，每個(gè)進(jìn)程 Pi計(jì)算

41、di u=mind i v|v (V -Vt) Vi，對(duì)所有的di u進(jìn)行多對(duì)一規(guī)約操作得到全局最小值，并存儲(chǔ)在P0中。此時(shí)進(jìn)程P0中保存新的頂點(diǎn)u,它將被插入到Vt中。進(jìn)程P0使用一對(duì)多廣播將u廣播給所 有的進(jìn)程。負(fù)責(zé)頂點(diǎn)u的進(jìn)程將u標(biāo)記為屬于集合Vt，最后每個(gè)進(jìn)程對(duì)自己本地的頂點(diǎn)更新 dv的值。單源最短路徑Dijkstra算法與最小生成樹算法Prim十分相似，不同點(diǎn)是Dijkstra存儲(chǔ)的數(shù)組lu,它是從頂點(diǎn)s經(jīng)Vt中的 頂點(diǎn)到達(dá)點(diǎn)u的最小成本，而Prim存儲(chǔ)du，它是連接Vt中的某個(gè)頂點(diǎn)與u的最小成本。 并行形式也一樣。全源最短路徑Floyd算法 使用遞歸公式.)if k = 0= J

42、rning護(hù)鳳嚴(yán)+d亍 *211,.&7.8.求解全部頂點(diǎn)對(duì)間的最短路徑procedure FLOYDJLLPAIRS_SP(.4)beginfor A； ：= 1 to ti dofor i ：= 1 to n do for j ：= 1 fo n do 唸:=min (靈f 雖嚴(yán) + end FLOYD JLL_RIRSSP并行形式: 用2維塊映射劃分矩陣D (k)，矩陣D(k)分為大小為(n/. p) (n/ p)的p個(gè)塊，每塊分配給一個(gè)進(jìn)程L procedure FL0YD_2DB,0CK(/?Mj,)2. bcinMfor k := I to do4. begin5.

43、each process /y； ihai lias a segment of the A1h tov. of f)*k 1broadcasts it to theprocesses;6. each process lr( ihat lias a segment of the A11 cohinin of 1 bmadcasis it to thepruceses；7. each proc亡合咅 wsits(o receive the needed semenis;8. each j?rccess j computes its part of the 1)1 matrix;勺一end10. end FL()YD_