并行算法第三章并行算法的設計基礎

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

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

3、復雜度11 時間復雜度12 計算復雜度對計算時間的影響13 并行計算性能評估中的幾個參數14并行計算性能評估中的幾個參數15 3.3 并行算法中的同步與通信161.如何將問題劃分成子問題？如何將問題劃分成子問題？2.各處理器完成什么任務？各處理器完成什么任務？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.各處理器完成什么任務？各處理器完成什么任務？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內存儲器內存儲器I/O接口接口1輸入輸入/輸出輸出設備設備I/O接口接口n輸入輸入/輸出輸出設備設備I/O接口接口外存儲器外存儲器26 PRAM模型27 PRAM模型Control UnitInterconnection NetworkPLMPLMPLMPLMShared Memory28 PRA