并行算法及其應用

前言
 作者簡介
 第一篇  基 礎 理 論
 第1章  并行計算平臺  2
 1.1  并行計算機分類  2
 1.2  并行計算機的處理機互連方式  6
 1.2.1  總線結(jié)構(gòu)  7
 1.2.2  一維陣列結(jié)構(gòu)  7
 1.2.3  網(wǎng)格結(jié)構(gòu)  8
 1.2.4  超立方體結(jié)構(gòu)  8
 1.2.5  蝶網(wǎng)結(jié)構(gòu)  9
 1.3  并行計算模型  10
 1.3.1  各種并行計算模型的特點  11
 1.3.2  LogP模型和LogGP模型  12
 1.3.3  BSP模型  15
 1.3.4  BSP模型和LogP模型的比較  16
 參考文獻  17
 第2章  并行算法概述  18
 2.1  目標和分類  18
 2.1.1  目標  18
 2.1.2  分類  19
 2.2  設計方法  19
 2.3  性能度量  26
 2.3.1  階的表示  26
 2.3.2  運行時間  27
 2.3.3  并行度  27
 2.3.4  成本  28
 2.3.5  加速比和效率  28
 2.3.6  并行算法的可擴展性分析  29
 2.4  并行加速比模型  30
 2.4.1  Amdahl加速比模型  30
 2.4.2  Gustafson加速比模型  30
 參考文獻  31
 第3章  并行程序開發(fā)  32
 3.1  并行程序開發(fā)環(huán)境  32
 3.1.1  并行編程語言  32
 3.1.2  消息傳遞環(huán)境  33
 3.1.3  一些常用并行程序開發(fā)環(huán)境  35
 3.2  并行程序設計  35
 3.2.1  概述  35
 3.2.2  數(shù)據(jù)并行方法  36
 3.2.3  消息傳遞方法  36
 3.2.4  兩種方法的實現(xiàn)途徑  37
 3.2.5  兩種方法的比較  37
 3.3  并行編程面臨的挑戰(zhàn)  39
 3.4  PVM并行程序開發(fā)環(huán)境簡介  41
 3.4.1  進程控制函數(shù)  41
 3.4.2  消息緩沖區(qū)管理函數(shù)  41
 3.4.3  數(shù)據(jù)打包/解包函數(shù)  42
 3.4.4  數(shù)據(jù)發(fā)送/接收函數(shù)  44
 3.4.5  PVM控制臺  45
 參考文獻  46
 第4章  并行計算系統(tǒng)實例  47
 4.1  PC機群集  47
 4.2  曙光1000A  47
 4.3  曙光2000  48
 4.4  工作站群集系統(tǒng)  51
 4.5  曙光3000  51
 4.6  曙光4000  52
 參考文獻  52
 第二篇  基 礎 應 用
 第5章  矩陣運算的并行算法  54
 5.1  矩陣乘法并行算法  54
 5.1.1  并行算法設計  55
 5.1.2  實驗結(jié)果  60
 5.2  QR分解并行算法  61
 5.2.1  Givens約化的并行處理  62
 5.2.2  群集系統(tǒng)中Givens約化的并行算法設計  64
 5.2.3  算法分析  65
 5.2.4  實驗結(jié)果  66
 5.3  矩陣求逆并行算法  68
 5.3.1  并行算法設計  69
 5.3.2  算法分析  69
 5.3.3  實驗結(jié)果  70
 參考文獻  70
 第6章  快速傅里葉變換的并行算法  71
 6.1  問題描述  71
 6.2  FFT并行求解過程分析  73
 6.3  并行算法描述  74
 6.3.1  主進程的算法描述  74
 6.3.2  子進程的算法描述  75
 6.4  算法分析  76
 6.4.1  串行算法分析  76
 6.4.2  并行算法分析  76
 6.5  算法的測試  77
 參考文獻  80
 第7章  卷積的并行算法  81
 7.1  卷積運算概論  81
 7.2  基于SIMD模型的卷積并行算法  82
 7.2.1  一些假設  82
 7.2.2  基本數(shù)據(jù)變換操作  84
 7.2.3  一維卷積設計與分析  85
 7.2.4  二維卷積設計與分析  86
 7.2.5  小結(jié)  87
 7.3  網(wǎng)絡并行環(huán)境下的卷積并行算法  87
 7.3.1  并行算法設計  88
 7.3.2  并行算法分析  91
 7.3.3  算法測試與分析  95
 7.3.4  結(jié)論與算法程序的改進  98
 參考文獻  99
 第8章  數(shù)字濾波的并行算法  100
 8.1  基于邏輯環(huán)的IIR并行算法設計  100
 8.1.1  IIR并行處理分析  100
 8.1.2  并行算法設計  103
 8.1.3  加速比和效率分析  105
 8.1.4  測試結(jié)果及分析  107
 8.2  基于LogP模型的FIR并行算法設計與實現(xiàn)  108
 8.2.1  FIR分塊并行算法  109
 8.2.2  分塊長度討論  111
 8.2.3  提前發(fā)送數(shù)據(jù)塊的并行算法設計與分析  112
 8.2.4  實驗結(jié)果與結(jié)論  114
 參考文獻  116
 第9章  離散余弦變換的并行算法  118
 9.1  問題描述  118
 9.2  并行求解分析  118
 9.3  并行算法設計  120
 9.4  算法分析  120
 9.5  并行程序優(yōu)化  122
 9.6  測試結(jié)果及分析  123
 9.7  動態(tài)負載平衡探討  124
 9.7.1  動態(tài)負載平衡簡介  124
 9.7.2  基于任務池的DCT并行計算實現(xiàn)  125
 9.7.3  任務池實現(xiàn)的優(yōu)化  126
 參考文獻  126
 第10章  哈達瑪變換的并行算法  127
 10.1  問題求解分析  127
 10.2  并行算法設計  129
 10.3  計算與通信重疊的探討  131
 10.4  測試結(jié)果及分析  133
 參考文獻  135
 第11章  2D離散小波變換的并行算法  136
 11.1  小波變換的數(shù)學模型  136
 11.1.1  連續(xù)小波變換  136
 11.1.2  一維離散小波變換  137
 11.1.3  二維離散小波變換  139
 11.1.4  精確重構(gòu)條件和小波基  140
 11.2  網(wǎng)格多處理機上的2D離散小波變換  141
 11.2.1  并行算法設計  142
 11.2.2  并行算法中通信量的減少  143
 11.2.3  算法分析  144
 11.3  實驗結(jié)果  146
 參考文獻  147
 第12章  數(shù)字圖像處理的并行算法  148
 12.1  圖像二值化  148
 12.1.1  圖像二值化算法  148
 12.1.2  并行算法設計  149
 12.1.3  算法分析  150
 12.1.4  算法測試與結(jié)論  153
 12.2  圖像中值濾波  154
 12.2.1  圖像中值濾波算法  154
 12.2.2  并行算法設計  154
 12.2.3  算法分析  156
 12.2.4  算法測試與結(jié)論  158
 12.3  圖像銳化  159
 12.3.1  圖像銳化算法  159
 12.3.2  并行算法設計  160
 12.3.3  算法分析  160
 12.3.4  算法測試與結(jié)論  162
 12.4  圖像平滑  163
 12.4.1  圖像平滑算法  163
 12.4.2  并行算法設計  164
 12.4.3  算法分析  164
 12.4.4  算法測試與結(jié)論  166
 12.5  圖像邊緣檢測  167
 12.5.1  圖像邊緣檢測算法  167
 12.5.2  并行算法設計  168
 12.5.3  算法分析  168
 12.5.4  算法測試與結(jié)論  170
 12.6  結(jié)論與改進  171
 參考文獻  172
 第三篇  實 際 應 用
 第13章  并行算法在電磁散射中的應用  174
 13.1  復雜目標電磁散射問題  174
 13.1.1  串行快速多極子算法  176
 13.1.2  串行多層快速多極子算法  176
 13.2  并行快速多極子算法設計與分析  177
 13.3  并行多層快速多極子算法設計與分析  178
 13.4  測試結(jié)果及結(jié)論  181
 13.4.1  并行快速多極子算法測試結(jié)果  181
 13.4.2  并行多層快速多極子算法驗證測試  181
 13.4.3  結(jié)論  182
 參考文獻  183
 第14章  并行算法在無線電波參數(shù)聯(lián)合估計中的應用  184
 14.1  參數(shù)聯(lián)合估計算法的數(shù)學模型與求解  184
 14.1.1  數(shù)學模型  184
 14.1.2  模型求解  185
 14.2  參數(shù)聯(lián)合估計的串行算法  186
 14.3  參數(shù)聯(lián)合估計的并行算法設計  188
 14.3.1  復數(shù)矩陣乘法的并行算法設計  189
 14.3.2  復數(shù)矩陣求逆的并行算法設計  189
 14.3.3  復共軛對稱矩陣的特征值與特征向量求解的并行算法設計  190
 14.3.4  并行算法設計  194
 14.4  試驗結(jié)果及結(jié)論  195
 參考文獻  196