MPI与OpenMP并行程序设计 C语言版PDF电子书下载

第1章动机和历史 1

1.1概述 1

目 录 1

1.2现代科学方法 2

1.3超级计算的进化 3

1.4现代并行计算机 4

1.4.1 Cosmic Cube并行计算机 4

1.4.2商品化的并行计算机 5

1.4.3 Beowulf系统 6

1.4.4先进战略计算计划 6

1.5寻找并行性 7

1.5.1数据相关图 7

1.5.2数据并行性 8

1.5.4流水线 9

1.5.3功能并行性 9

1.5.5计算规模的考虑因素 11

1.6数据聚类 11

1.7为并行计算机编程 13

1.7.1扩展编译器 13

1.7.2扩展串行编程语言 14

1.7.3增加并行编程层 14

1.7.4创造一个并行语言 15

1.7.5现状 16

1.8本章小结 16

1.9主要术语 16

1.10参考文献 17

1.11练习题 18

16.9本章小结 3 18

2.2互连网络 21

第2章并行体系结构 21

2.1概述 21

2.2.1共享介质与开关介质 22

2.2.2开关网络的拓扑结构 22

2.2.3二维网格形网络 23

2.2.4二叉树形网络 23

2.2.5超树形网络 24

2.2.6蝶形网络 25

2.2.7超立方体网络 26

2.2.8混洗－交换网络 27

2.2.9小结 28

2.3阵列处理机 29

2.3.1体系结构与数据并行 29

2.3.2阵列处理机的性能 30

2.3.3处理器互连网络 31

2.3.4处理器的启动与阻塞 32

2.3.6阵列处理机的缺点 33

2.4多处理器 33

2.3.5其他体系结构特点 33

2.4.1集中式多处理器 34

2.4.2分布式多处理器 35

2.5多计算机 38

2.5.1非对称多计算机 39

2.5.2对称多计算机 40

2.5.3怎样的模型对商用集群 41

来说是最佳的 41

2.5.4集群与工作站网络之间 42

的差异 42

2.6弗林分类法 42

2.6.3 MISD 43

2.6.1 SISD 43

2.6.2 SIMD 43

2.7本章小结 45

2.6.4 MIMD 45

2.8主要术语 46

2.9参考文献 47

2.10练习题 47

第3章并行算法设计 50

3.1概述 50

3.2任务／通道模型 50

3.3 Foster的设计方法论 51

3.3.1划分 52

3.3.2通信 53

3.3.3聚集 54

3.3.4 映射 55

3.4.1简介 58

3.4边界值问题 58

3.4.2划分 59

3.4.3通信 59

3.4.4聚集与映射 60

3.4.5分析 60

3.5找出最大值 60

3.5.1简介 60

3.5.2划分 61

3.5.3通信 61

3.5.4聚集与映射 64

3.6.1简介 65

3.6.2划分 65

3.5.5分析 65

3.6 n-body问题 65

3.6.3通信 66

3.6.4聚集与映射 67

3.6.5分析 67

3.7增加数据输入 68

3.7.1简介 68

3.7.2通信 69

3.7.3分析 69

3.8本章小结 70

3.9主要术语 70

3.10参考文献 71

3.11练习题 71

4.2消息传递模型 74

4.1概述 74

第4章消息传递编程 74

4.3 MPI接口 76

4.4电路可满足性问题 76

4.4.1 MPI Init函数 80

4.4.2 MPI_Comm_rank和 80

MPI Comm size函数 80

4.4.3 MPI Finalize函数 81

4.4.4编译MPI程序 81

4.4.5运行MPI程序 81

4.5聚合通信简介 83

MPI Reduce函数 84

4.6检测并行性能 86

4.6.2 MPI Barrier函数 87

函数 87

4.6.1 MPI Wtime和MPIWtick 87

4.7本章小结 88

4.8主要术语 89

4.10练习题 89

4.9参考文献 89

第5章Eratosthenes筛法 93

5.1概述 93

5.2串行算法 93

5.3并行性的来源 94

5.4数据分解方法 95

5.4.1交叉数据分解 95

5.4.2按块数据分解 95

5.4.3用于按块分解的宏 96

5.4.4局部下标还是全局下标 97

5.4.5块分解的结果 97

5.5开发并行算法 97

函数MPI_Bcast 98

5.7并行程序的说明 99

5.6并行筛法算法的分析 99

5.8测试 104

5.9改进 105

5.9.1删除偶数 105

5.9.2消除广播 106

5.9.3循环的重新组织 106

5.9.4测试 106

5.10本章小结 108

5.11主要术语 108

5.12参考文献 108

5.13练习题 108

第6章Floyd算法 111

6.1概述 111

6.2全点对最短路径问题 111

6.3运行时创建数组 112

6.4.1划分 113

6.4设计并行算法 113

6.4.2通信 114

6.4.3聚合和映射 115

6.4.4矩阵的输入／输出 116

6.5点对点通信 117

6.5.1函数MPI Send 118

6.5.2函数MPI Recv 119

6.5.3死锁 120

6.6并行程序的说明 121

6.7分析和测试 123

6.8本章小结 124

6.10参考文献 125

6.11练习题 125

6.9主要术语 125

第7章性能分析 128

7.1概述 128

7.2加速比和效率 128

7.3 Amdahl定律 130

7.3.1 Amdahl定律的局限 131

7.3.2 Amdahl效应 132

7.4 Gustafson-Barsis定律 132

7.5 Karp-Flatt量度 134

7.6等效指标 136

7.7本章小结 139

7.8主要术语 140

7.9参考文献 141

7.10练习题 141

8.1概述 143

8.2串行算法 143

第8章矩阵向量乘法 143

8.3数据分解方式 144

8.4矩阵按行分解 145

8.4.1设计与分析 145

8.4.2复制分块的向量 146

8.4.3函数MPI_Allgatherv 147

8.4.4被复制向量的输入／输出 149

8.4.5编写并行程序 149

8.4.6测试 150

8.5矩阵按列分解 151

8.5.1设计与分析 151

8.5.2读取按列分解的矩阵 152

8.5.3函数MPI_Scatterv 153

8.5.4打印输出按列分块矩阵 154

8.5.5函数MPI_Gatherv 154

8.5.6分发中间结果 155

8.5.7函数MPI_Alltoallv 156

8.5.8编写并行程序 156

8.5.9测试 158

8.6棋盘式分解 159

8.6.1设计与分析 159

8.6.2创建通信域 162

8.6.3函数MPI_Dims_create 162

8.6.4函数MPI_Cart_create 163

8.6.5读取棋盘式矩阵 163

8.6.6函数MPI_Cart_rank 164

8.6.7函数MPI_Cart_coords 165

8.6.8函数MPI_Comm_split 165

8.6.9测试 166

8.7本章小结 167

8.8主要术语 168

8.9参考文献 168

8.10练习题 169

第9章文档分类 173

9.1概述 173

9.2并行算法设计 173

9.2.3管理者／工人模式 174

9.2.2聚集和映射 174

9.2.1划分与通信 174

9.2.4管理进程 175

9.2.5 MPI Abort函数 176

9.2.6工人进程 177

9.2.7建立一个只有工人的 178

通信域 178

9.3非阻塞通信 179

9.3.1管理进程的通信 180

9.3.2 MPI_Irecv函数 180

9.3.3 MPI_Wait函数 180

9.3.4工人的通信 180

9.4文档分类的并行程序 181

9.3.6 MPI_Probe函数 181

9.3.7 MPI_Get_count函数 181

9.3.5 MPI_Isend函数 181

9.5.1按组分配文档 187

9.5算法改进 187

9.5.2流水线处理 187

9.5.3 MPI_Testsome函数 189

9.6本章小结 189

9.8参考文献 190

9.9练习题 190

9.7主要术语 190

第10章蒙特卡洛法 193

10.1概述 193

10.1.1为什么蒙特卡洛法 195

能奏效 195

10.1.2蒙特卡洛法与并行计算 196

10.2串行随机数生成器 196

10.2.1线性同余法 197

10.2.2滞后形斐波那契生成器 197

10.3.1管理者－工人方法 198

10.3.2蛙跳方法 198

10.3并行随机数产生器 198

10.3.3序列分割 199

10.3.4参数化 199

10.4其他的随机数分布 200

10.4.1逆分布累积分布 200

函数变换 200

10.4.2 Box-Muller变换 201

10.4.3拒绝法 202

10.5.1中子输运 204

10.5应用示例 204

10.5.2 二维板上一个点的 206

温度 206

10.5.3二维易辛模型 207

10.5.4房间分配问题 209

10.5.5车库停车问题 212

10.5.6交通环路 213

10.6本章小结 216

10.7主要术语 216

10.8参考文献 217

10.9练习题 218

11.2矩阵相乘的串行算法 220

11.2.1基于行的迭代算法 220

11.1概述 220

第11章矩阵乘法 220

11.2.2基于块的递归算法 222

11.3行块分解并行算法 224

11.3.1确定原始任务 224

11.3.2聚合 224

11.3.3通信和进一步的聚合 225

11.3.4分析 226

11.4 Cannon算法 227

11.4.1组合 227

11.4.2通信 228

11.4.3分析 229

11.5本章小结 230

11.7参考文献 231

11.8练习题 231

11.6主要术语 231

12.2基本术语 233

第12章线性方程组求解 233

12.1概述 233

12.3回代法 234

12.3.1 串行算法 234

12.3.2面向行的并行算法 236

12.3.3面向列的并行算法 236

12.3.4对比 237

12.4高斯消去法 237

12.4.1串行算法 237

12.4.2并行算法 239

12.4.3面向行的算法 240

12.4.4面向列的算法 242

12.4.5对比 242

12.4.6面向行的流水线算法 243

12.5迭代法 244

12.6.1串行算法 247

12.6共轭梯度法 247

12.6.2并行算法 249

12.7本章小结 250

12.8主要术语 251

12.9参考文献 251

12.10练习题 252

第13章有限差分方法 254

13.1概述 254

13.2偏微分等式 255

13.2.1偏微分方程的分类 255

13.2.2差分商 256

13.3.1导出方程 257

13.3弦振荡问题 257

13.3.2串行程序 259

13.3.3并行程序设计 260

13.3.4等效分析 261

13.3.5冗余计算 262

13.4稳定状态热量分布问题 263

13.4.1方程的导出 263

13.4.2串行程序导出 264

13.4.3并行程序设计 265

13.4.4等效分析 266

13.4.5实现细节 267

13.5本章小结 267

13.6主要术语 268

13.7参考文献 268

13.8练习题 269

第14章排序 271

14.1概述 271

14.2快速排序 271

14.3并行快速排序算法 272

14.3.1排序完毕的定义 273

14.3.2算法开发 273

14.3.3分析 273

14.4超级快速排序 274

14.4.1算法描述 274

14.4.2等效分析 275

14.5.2等效分析 277

14.5规则取样并行排序 277

14.5.1算法描述 277

14.6本章小结 279

14.8参考文献 280

14.9练习题 280

14.7主要术语 280

第15章快速傅立叶变换 283

15.1概述 283

15.2傅立叶分析 283

15.3离散傅立叶变换 285

15.3.1离散傅立叶逆变换 286

15.3.2应用示例：多项式乘法 286

15.4快速傅立叶变换 288

15.5.1分割与通信 291

15.5并行程序设计 291

15.5.3等效分析 292

15.5.2聚合与映射 292

15.6本章小结 294

15.7主要术语 294

15.8参考文献 294

15.9练习题 294

第16章组合搜索 296

16.1概述 296

16.2回溯搜索 297

16.2.1示例 297

16.2.2 时间和空间复杂性 298

16.3并行回溯算法 298

16.4分布式终止检测 302

16.5分支定界法 304

16.5.1示例 304

16.5.2串行算法 306

16.5.3分析 308

16.6并行分支定界法 308

16.6.1存储和共享待解的 308

子问题 308

16.6.2效率 309

16.6.3停机条件 309

16.7搜索博弈树 312

16.7.1最大最小算法 312

16.7.2 Alpha-Beta剪枝 313

16.7.3 Alpha-Beta剪枝法 315

的改进 315

16.8.2并行子树估值 316

16.8.1并行渴望搜索 316

16.8并行Alpha-Beta搜索 316

16.8.3分布式树搜索 317

16.10主要术语 319

16.11参考文献 320

16.12练习题 320

第17章共事存储编程 323

17.1概述 323

17.2共享存储模型 324

17.3对for循环的并行化 325

17.3.1 paralldfor编译 325

指导语句 325

函数 327

17.3.3 omp_set_hum_threads 327

函数 327

17.3.2 omp_get_num_procs 327

17.4声明私有变量 328

17.4.1 private子句 328

17.4.2 firstprivate子句 329

17.4.3 lastprivate子句 330

17.5 临界区 330

critical编译指导语句 331

17.6归约操作 332

17.7性能改善 333

17.7.1循环转化 333

17.7.2条件执行循环 334

17.7.3循环调度 335

17.8更普遍的数据并行 336

17.8.1 parallel编译指导语句 338

17.8.2 omp_get_thread_num 339

函数 339

17.8.3 omp_get_num_threads 340

函数 340

17.8.4编译指导语句for 340

17.8.5 single编译指导语句 342

17.8.6 nowait子句 342

17.9功能并行 343

17.9.1 parallel sections编译指导语句 343

17.9.2 section编译指导语句 344

17.9.3 sections编译指导语句 344

17.10本章小结 345

17.13练习题 347

17.12参考文献 347

17.11主要术语 347

第18章融合OpenMP和MPI 350

18.1概述 350

18.2共轭梯度算法 351

18.2.1 MPI程序 351

18.2.2函数级程序轮廓刻画 354

18.2.3对函数matrix_vector_ 355

product进行并行化 355

18.2.4测试程序 355

18.3 Jacobi方法 356

18.3.1 MPI程序轮廓刻画 356

18.3.2对函数find_steady_state并行化 357

18.3.3测试程序 359

18.5练习题 360

18.4本章小结 360

附录A MPI函数 362

附录B工具函数 393

B.1 MyMPI.h头文件 393

B.2 MyMPI.c源文件 394

附录C调试MPI程序 412

C.1概述 412

C.2 MPI程序常见错误 412

C.2.1死锁错误 412

C.2.2导致不准确结果的错误 413

C.2.3组通信的优点 413

C.3实用调试策略 413

附录D复数回顾 415

附录E OpenMP函数 418

参考文献 420