本书以理论与实际相结合的方式对并行算法及其应用进行了简明扼要的分析和介绍。全书共分三部分，基础理论部分主要介绍并行计算平台、并行算法概论、并行程序开发环境等；基础应用部分包含矩阵运算、快速傅里叶变换、卷积运算、数字滤波、离散余弦变换、哈达玛变换、2D离散小波变换、数字图像处理等方面的并行算法设计、分析与测试；实际应用部分主要介绍并行算法在电磁散射和无线电波中的应用。
　　本书可作为计算机及相关专业的本科生和研究生的教材，也可供从事计算机科学研究与教学的人员参考。

无

计算机单机技术发展的有限性和科学工程计算需求的无限性，决定了计算机的发展必然走上多机并行的道路。从计算机的发展历史来看，CPU的发展是呈指数级增长的。但与此同时，对计算机处理能力的需求也呈指数级的增长，在人工智能与模式识别、计算流体力学、计算结构力学、能源、气象等大规模科学计算领域和信息处理、高性能数据库等领域，已出现了需求的增长超出计算机处理能力增长的情况，导致计算机单机的处理速度已远远不能满足需要。
　　我国在国家“863计划”、“八五”计划 、“九五”计划中都对高性能计算给予了高度重视。2000年，863专家小组成员在其报告—“智能计算机”中再次肯定了国家“超级863计划”在高性能计算方面将要进行的工作和投资力度。
　　目前，高性能计算机是我国在并行处理技术各领域中发展最为显著的一个领域，已研制出神州、银河、曙光系列等高性能计算机，其中涉及的部分并行技术（如机群操作系统、虫洞通信芯片设计、并行优化编译等）已达到国际先进水平。
　　并行处理技术虽然在近些年来得到了巨大发展，在硬件方面（如并行计算机制造、硬件级别的指令并行等方面）突破较大，但在软件方面的发展则不尽人意，存在许多问题亟待解决，其中包括并行系统软件、并行算法以及并行应用程序等。由于算法是软件的核心，因此研究与并行处理系统相适应的并行算法对推动并行处理技术的发展具有重要作用。
　　本书是以我们在“九五”期间完成的一项国家课题—《并行算法及其在电子系统中的应用》为基础编写的，并且，在自编讲义的基础上，经过编者多次研究生教学实践、充实、修改而成。全书共分为三个部分：基础理论，主要介绍并行计算平台、并行算法概述、并行程序开发环境等；基础应用，主要包含矩阵运算、快速傅里叶变换、卷积运算、数字滤波、离散余弦变换、哈达玛变换、2D离散小波变换、数字图像处理等方面的并行算法设计、分析与测试；实际应用，主要介绍并行算法在电磁散射中的应用和无线电波参数联合估计中的应用。
　　感谢课题组的全体成员，特别是吴跃、刘辉、黄天云、庞朝阳、郑文学、陈平安、李静、张文斌、彭文钦、陈瀚、潘晔、郑婵等在本书的编写过程中所做的工作。
　　由于作者水平有限，书中难免有错误和不妥之处，恳请读者批评、指正。

孙世新
2004年8月

第一篇　 基 础 理 论
第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