并行处理基本原理PDF电子书下载

第1章 并行机和并行计算 1

1.1 并行体系结构的发展历程 1

1.1.1 串行计算机中的并行性 2

1.1.2 向量或SIMD计算机 5

1.1.3 多处理机或MIMD计算机 7

1.2 互连网络 9

1.3 体系结构并行性的应用 10

1.4 SIMD和MIMD程序设计 10

1.5 算法并行性 13

1.6 小结 15

1.7 参考文献注解 16

1.8 练习题 16

2.1 描述算法并行性的参数 18

第2章 并行计算基础 18

2.2 前缀问题 19

2.3 并行前缀算法 20

2.3.1 高／低并行前缀算法 20

2.3.2 奇／偶并行前缀算法 22

2.3.3 Ladner和Fischer并行前缀算法 24

2.4 大规模问题求解算法的特性 27

2.5 编程实现并行前缀算法 28

2.6 并行算法的加速比和效率 29

2.7 性能分析 33

2.7.1 影响性能的因素 33

2.7.2 一个简单的性能模型——Amdahl定律 35

2.7.3 平均执行速度 36

2.8 小结 36

2.10 练习题 37

2.9 参考文献注解 37

第3章 向量算法与体系结构 41

3.1 向量和矩阵算法 41

3.2 向量体系结构——单指令多数据流体系结构 47

3.3 SIMD指令集 50

3.3.1 SIMD计算机的寄存器和存储器 52

3.3.2 向量、控制器与协同指令 53

3.3.3 数据相关条件操作 56

3.3.4 向量长度和分段处理 59

3.3.5 在PE之间路由数据 60

3.4 互素存储器系统 62

3.5 用PE索引来解决存储布局问题 64

3.6 SIMD语言结构——Fortran 90 67

3.6.1 数组和数组分片 67

3.6.2 数组赋值和数组表达式 68

3.6.3 Fortran 90数组内置函数 70

3.6.4 Fortran 90中SIMD操作举例 71

3.7 流水SIMD向量计算机 74

3.7.1 流水SIMD处理机的结构 75

3.7.2 流水SIMD计算机的存储器接口 78

3.7.3 流水SIMD计算机的性能 80

3.8 向量体系结构小结 83

3.9 参考文献注解 83

3.10 练习题 84

第4章 MIMD计算机或多处理机 93

4.1 共享存储器和消息传递体系结构 94

4.1.1 混合类型多处理机体系结构 95

4.1.2 共享存储器和消息传递的特点 96

4.1.3 消息传递体系结构中的网络拓扑结构 97

4.1.5 实际系统的分类 99

4.1.4 直接和间接网络 99

4.2 共享存储器多处理机程序设计总览 100

4.2.1 数据共享和进程管理 101

4.2.2 同步 102

4.2.3 原子性与同步 103

4.2.4 作业分配 105

4.2.5 多个进程执行一个程序 106

4.3 共享存储器程序设计的选择与领域 107

4.3.1 进程管理——启动、停止和层次 108

4.3.2 并行进程对数据的访问 109

4.3.3 作业分配 111

4.3.4 多处理机的同步 115

4.4.1 OpenMP语言扩展 120

4.4 共享存储器多处理机程序设计语言 120

4.4.2 OpenMP Fortran语言的应用程序接口（API） 123

4.4.3 OpenMP Fortran实例与讨论 130

4.5 流水MIMD——多线程 136

4.6 小结 139

4.7 参考文献注解 140

4.8 练习题 141

第5章 分布式存储器多处理机 148

5.1 处理机／存储器对中的分布式数据和操作 148

5.2 使用消息传递机制编程 150

5.2.1 通信串行进程语言 152

5.2.2 分布式存储器编程实例：矩阵乘法 155

5.3 通信的特征 157

5.3.1 点对点通信 158

5.3.2 在分布式存储器程序中的变量分类 160

5.3.3 高级通信操作 162

5.3.4 使用高级通信进行分布高斯消元法 164

5.3.5 进程拓扑与处理机拓扑 168

5.4 消息传递接口（MPI） 170

5.4.1 MPI中的基本概念 171

5.4.2 MPI程序实例——矩阵乘法 174

5.5 管理通信的硬件——分布式高速缓存 180

5.5.1 高速缓存一致性 181

5.5.2 共享存储器的一一致性 183

5.6 小结——共享存储器多处理机与分布式存储器多处理机 185

5.7 参考文献注解 187

5.8 练习题 188

6.1 网络特性 192

第6章 互连网络 192

6.2 置换 196

6.3 静态网络 199

6.3.1 网格 199

6.3.2 环 201

6.3.3 树 202

6.3.4 立方体网络 205

6.3.5性能 210

6.4动态网络 211

6.4.1总线（bus） 211

6.4.2交叉开关 211

6.4.3多级互连网络 212

6.4.4组合网络——互斥自由同步 219

6.4.5性能 223

6.5小结 226

6.7练习题 227

6.6参考文献注解 227

第7章 数据相关性与并行性 230

7.1发现（串行）代码中的并行操作 230

7.2具有复杂名称的变量 233

7.2.1嵌套循环 235

7.2.2关于数组访问不确定性问题的变化 237

7.3样本编译技术 240

7.3.1循环变换 241

7.3.2循环重构 243

7.3.3循环替换变换 245

7.3.4消除反相关和输出相关的变换 248

7.4.1数据流基本概念 250

7.4数据流原理 250

7.4.2数据流计算的图形化表示 251

7.4.3数据流的条件 253

7.4.4数据流迭代 255

7.4.5数据流函数的应用与递归 257

7.4.6数据流中的结构值——数组 258

7.5数据流体系结构 264

7.5.1MIT静态数据流体系结构 264

7.5.2动态数据流计算机 267

7.5.3数据流机器的一些问题 270

7.6脉动阵列 270

7.7小结 275

7.8参考文献注解 276

7.9练习题 276

8.1同步传输信息的特点 280

第8章 同步实现与数据共享 280

8.2 不同类别的协同计算同步 281

8.2.1 一个生产者和一个或多个消费者 282

8.2.2 全局归约 282

8.2.3 全局前缀 284

8.2.4 划分结构的协同更新 286

8.2.5 管理共享作业集 286

8.2.6 协同的列表操作 287

8.2.7 使用Fetch Add并行访问队列 288

8.2.8 直方图——细粒度数据相关同步 290

8.3 等待机制 291

8.3.1 硬件等待 291

8.3.2 软件等待 292

8.3.3 多级等待 292

8.4 用原子读写操作实现互斥 293

8.5 证明同步实现的正确性 296

8.5.1 使用锁实现Produce/Consume 296

8.5.2 时间逻辑 297

8.5.3 正确性证明 299

8.6 另一种同步实现——障碍 301

8.6.1 障碍同步的特点 301

8.6.2 障碍实现的特点 302

8.7 小结 306

8.8 参考文献注解 306

8.9 练习题 307

第9章 并行处理机性能 310

9.1 Amdahl定律回顾 311

9.1.1 工作粒度对Amdahl定律的影响 311

9.1.2 Amdahl定律参数的最小方差估计 312

9.2.1 流水线向量机的性能 313

9.2 参数化的执行时间 313

9.2.2 流水线多处理机的性能 315

9.2.3 多流水线多处理机系统 321

9.3 障碍同步的性能 325

9.3.1 障碍性能的说明 326

9.3.2 障碍性能测量的手段 327

9.3.3 障碍同步性能测量举例 329

9.4 并行循环静态调度和动态调度的统计模型 333

9.4.1 动态调度模型 334

9.4.2 静态调度模型 338

9.4.3 实验结果的比较 340

9.5 小结 343

9.6 参考文献注解 343

9.7 练习题 344

第10章 并行程序的时间特性 345

10.1 高速缓存行为的时间特性 346

10.1.1 高速缓存特性的时间局部性度量标准 349

10.1.2 冒泡排序程序局部性度量标准的应用举例 350

10.2 分布式高速缓存多处理机中的读共享 352

10.2.1 共享数据读取的一个简单例子 353

10.2.2 KSR-1体系结构 354

10.2.3 读多重性度量标准 356

10.2.4 实验 357

10.2.5 编程控制的邮寄存储和预取 359

10.3 消息传递多处理机系统中的消息等待 361

10.4 小结 366

10.5 参考文献注解 367

10.6 练习题 367

11.1.1 数据相关性和输入输出 371

11.1 并行I/O问题 371

第11章 并行输入输出 371

11.1.2 输入输出格式转换 373

11.1.3 输入输出延迟和带宽需求的数值例子 374

11.2 并行输入输出的硬件 376

11.2.1 主存方面的传输控制 377

11.2.2 输入输出通道的并发 378

11.2.3 并行外围设备 379

11.3 并行访问磁盘阵列——RAID 379

11.4 共享存储器多处理机中的并行格式化I/O 384

11.4.1 使用C中的I/O例程fread()和sscanf()实现并行输入 385

11.4.2 使用C中的I/O例程sprintf()和fwrite()实现并行输出 388

11.5 多处理机中的聚合I/O——MPI-IO 389

11.5.1 MPI-2中的I/O概念 390

11.5.2 MPI-IO示例 392

11.7 参考文献注解 399

11.6 小结 399

11.8 练习题 400

附录A MPI消息传递库程序 401

A.1 点对点通信程序 401

A.2 聚合通信程序 404

A.3 MPI数据类型和构造器 407

A.4 通信器、进程组和拓扑 410

A.5 MPI环境和错误处理 415

A.6 小结与MPI-2扩展 416

附录B 同步机制 418

B.1 硬件级同步 418

B.2 语言级同步 420

B.3 等待机制 424

参考文献 425