并行算法第三章并行算法的設(shè)計基礎(chǔ)

1、 第三章第三章并行算法的設(shè)計基礎(chǔ)并行算法的設(shè)計基礎(chǔ)3.1 3.1 并行算法的基礎(chǔ)知識并行算法的基礎(chǔ)知識3.2 3.2 并行算法的復(fù)雜性度量并行算法的復(fù)雜性度量3.3 3.3 并行算法中的同步與通信并行算法中的同步與通信3.4 3.4 并行計算模型并行計算模型3 3.1 并行算法的基礎(chǔ)知識4 并行算法的分類數(shù)值計算數(shù)值計算：基于代數(shù)關(guān)系運(yùn)算的一類：基于代數(shù)關(guān)系運(yùn)算的一類非數(shù)值計算非數(shù)值計算：基于比較關(guān)系運(yùn)算的一類：基于比較關(guān)系運(yùn)算的一類同步算法同步算法：算法的多個進(jìn)程的執(zhí)行必須相互等待：算法的多個進(jìn)程的執(zhí)行必須相互等待異步算法異步算法：算法的多個進(jìn)程的執(zhí)行不需要相互等待：算法的多個進(jìn)程的執(zhí)行不需

2、要相互等待 分布算法分布算法：由通信鏈路連接的多個節(jié)點，協(xié)同完成問題由通信鏈路連接的多個節(jié)點，協(xié)同完成問題 求解的一類并行算法求解的一類并行算法確定算法確定算法：算法的每一步都能明確地指明下一步應(yīng)該如：算法的每一步都能明確地指明下一步應(yīng)該如 何行進(jìn)的一類算法何行進(jìn)的一類算法隨機(jī)算法隨機(jī)算法：算法的每一步隨機(jī)地從指定范圍內(nèi)選取若：算法的每一步隨機(jī)地從指定范圍內(nèi)選取若 干參數(shù)，由其來確定算法下一步的走向干參數(shù)，由其來確定算法下一步的走向5 并行算法的特點6 并行算法的表達(dá)7 3.2并行算法的復(fù)雜性度量時間復(fù)雜度時間復(fù)雜度問題的規(guī)模問題的規(guī)?？臻g復(fù)雜度空間復(fù)雜度8 時間復(fù)雜度9 時間復(fù)雜度10 時間

3、復(fù)雜度11 時間復(fù)雜度12 計算復(fù)雜度對計算時間的影響13 并行計算性能評估中的幾個參數(shù)14并行計算性能評估中的幾個參數(shù)15 3.3 并行算法中的同步與通信161.如何將問題劃分成子問題？如何將問題劃分成子問題？2.各處理器完成什么任務(wù)？各處理器完成什么任務(wù)？3.如何實現(xiàn)各處理器對共享變量的訪問？如何實現(xiàn)各處理器對共享變量的訪問？ 思考？思考？17共享共享變量變量S18并行算法中的同步 Begin (1)S=0;(2)for all Pi where 0ip-1 do (2.1) L=0; (2.2) for (j=i;jn;j+=p) L=L+aj; (2.3) lock(S); S=S+L

4、; (2.4) unlock(S); End19 并行算法的通訊20 并行算法的通訊1.如何將問題劃分成子問題？如何將問題劃分成子問題？2.各處理器完成什么任務(wù)？各處理器完成什么任務(wù)？3. 處理器之間是否存在通信？處理器之間是否存在通信？思考？思考？A劃分為劃分為B=A1.n,(i-1)r+1.irX劃分為劃分為w=X(i-1)r+1;ir 計算計算Z=BW21矩陣向量相乘矩陣向量相乘Y=AX22 并行算法的通訊233.4 并行計算模型24并行計算模型25串行計算模型總線總線CPU內(nèi)存儲器內(nèi)存儲器I/O接口接口1輸入輸入/輸出輸出設(shè)備設(shè)備I/O接口接口n輸入輸入/輸出輸出設(shè)備設(shè)備I/O接口接口外存儲器外存儲器26 PRAM模型27 PRAM模型Control UnitInterconnection NetworkPLMPLMPLMPLMShared Memory28 PRA