并行算法及其應(yīng)用

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