并行算法及其应用

前言
 作者简介
 第一篇  基 础 理 论
 第1章  并行计算平台  2
 1.1  并行计算机分类  2
 1.2  并行计算机的处理机互连方式  6
 1.2.1  总线结构  7
 1.2.2  一维阵列结构  7
 1.2.3  网格结构  8
 1.2.4  超立方体结构  8
 1.2.5  蝶网结构  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章  并行程序开发  32
 3.1  并行程序开发环境  32
 3.1.1  并行编程语言  32
 3.1.2  消息传递环境  33
 3.1.3  一些常用并行程序开发环境  35
 3.2  并行程序设计  35
 3.2.1  概述  35
 3.2.2  数据并行方法  36
 3.2.3  消息传递方法  36
 3.2.4  两种方法的实现途径  37
 3.2.5  两种方法的比较  37
 3.3  并行编程面临的挑战  39
 3.4  PVM并行程序开发环境简介  41
 3.4.1  进程控制函数  41
 3.4.2  消息缓冲区管理函数  41
 3.4.3  数据打包/解包函数  42
 3.4.4  数据发送/接收函数  44
 3.4.5  PVM控制台  45
 参考文献  46
 第4章  并行计算系统实例  47
 4.1  PC机群集  47
 4.2  曙光1000A  47
 4.3  曙光2000  48
 4.4  工作站群集系统  51
 4.5  曙光3000  51
 4.6  曙光4000  52
 参考文献  52
 第二篇  基 础 应 用
 第5章  矩阵运算的并行算法  54
 5.1  矩阵乘法并行算法  54
 5.1.1  并行算法设计  55
 5.1.2  实验结果  60
 5.2  QR分解并行算法  61
 5.2.1  Givens约化的并行处理  62
 5.2.2  群集系统中Givens约化的并行算法设计  64
 5.2.3  算法分析  65
 5.2.4  实验结果  66
 5.3  矩阵求逆并行算法  68
 5.3.1  并行算法设计  69
 5.3.2  算法分析  69
 5.3.3  实验结果  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  基本数据变换操作  84
 7.2.3  一维卷积设计与分析  85
 7.2.4  二维卷积设计与分析  86
 7.2.5  小结  87
 7.3  网络并行环境下的卷积并行算法  87
 7.3.1  并行算法设计  88
 7.3.2  并行算法分析  91
 7.3.3  算法测试与分析  95
 7.3.4  结论与算法程序的改进  98
 参考文献  99
 第8章  数字滤波的并行算法  100
 8.1  基于逻辑环的IIR并行算法设计  100
 8.1.1  IIR并行处理分析  100
 8.1.2  并行算法设计  103
 8.1.3  加速比和效率分析  105
 8.1.4  测试结果及分析  107
 8.2  基于LogP模型的FIR并行算法设计与实现  108
 8.2.1  FIR分块并行算法  109
 8.2.2  分块长度讨论  111
 8.2.3  提前发送数据块的并行算法设计与分析  112
 8.2.4  实验结果与结论  114
 参考文献  116
 第9章  离散余弦变换的并行算法  118
 9.1  问题描述  118
 9.2  并行求解分析  118
 9.3  并行算法设计  120
 9.4  算法分析  120
 9.5  并行程序优化  122
 9.6  测试结果及分析  123
 9.7  动态负载平衡探讨  124
 9.7.1  动态负载平衡简介  124
 9.7.2  基于任务池的DCT并行计算实现  125
 9.7.3  任务池实现的优化  126
 参考文献  126
 第10章  哈达玛变换的并行算法  127
 10.1  问题求解分析  127
 10.2  并行算法设计  129
 10.3  计算与通信重叠的探讨  131
 10.4  测试结果及分析  133
 参考文献  135
 第11章  2D离散小波变换的并行算法  136
 11.1  小波变换的数学模型  136
 11.1.1  连续小波变换  136
 11.1.2  一维离散小波变换  137
 11.1.3  二维离散小波变换  139
 11.1.4  精确重构条件和小波基  140
 11.2  网格多处理机上的2D离散小波变换  141
 11.2.1  并行算法设计  142
 11.2.2  并行算法中通信量的减少  143
 11.2.3  算法分析  144
 11.3  实验结果  146
 参考文献  147
 第12章  数字图像处理的并行算法  148
 12.1  图像二值化  148
 12.1.1  图像二值化算法  148
 12.1.2  并行算法设计  149
 12.1.3  算法分析  150
 12.1.4  算法测试与结论  153
 12.2  图像中值滤波  154
 12.2.1  图像中值滤波算法  154
 12.2.2  并行算法设计  154
 12.2.3  算法分析  156
 12.2.4  算法测试与结论  158
 12.3  图像锐化  159
 12.3.1  图像锐化算法  159
 12.3.2  并行算法设计  160
 12.3.3  算法分析  160
 12.3.4  算法测试与结论  162
 12.4  图像平滑  163
 12.4.1  图像平滑算法  163
 12.4.2  并行算法设计  164
 12.4.3  算法分析  164
 12.4.4  算法测试与结论  166
 12.5  图像边缘检测  167
 12.5.1  图像边缘检测算法  167
 12.5.2  并行算法设计  168
 12.5.3  算法分析  168
 12.5.4  算法测试与结论  170
 12.6  结论与改进  171
 参考文献  172
 第三篇  实 际 应 用
 第13章  并行算法在电磁散射中的应用  174
 13.1  复杂目标电磁散射问题  174
 13.1.1  串行快速多极子算法  176
 13.1.2  串行多层快速多极子算法  176
 13.2  并行快速多极子算法设计与分析  177
 13.3  并行多层快速多极子算法设计与分析  178
 13.4  测试结果及结论  181
 13.4.1  并行快速多极子算法测试结果  181
 13.4.2  并行多层快速多极子算法验证测试  181
 13.4.3  结论  182
 参考文献  183
 第14章  并行算法在无线电波参数联合估计中的应用  184
 14.1  参数联合估计算法的数学模型与求解  184
 14.1.1  数学模型  184
 14.1.2  模型求解  185
 14.2  参数联合估计的串行算法  186
 14.3  参数联合估计的并行算法设计  188
 14.3.1  复数矩阵乘法的并行算法设计  189
 14.3.2  复数矩阵求逆的并行算法设计  189
 14.3.3  复共轭对称矩阵的特征值与特征向量求解的并行算法设计  190
 14.3.4  并行算法设计  194
 14.4  试验结果及结论  195
 参考文献  196