作者：刘轶、杨海龙
页数：317
出版社：清华大学出版社
出版日期：2024
ISBN：9787302660965
电子书格式：pdf/epub/txt
内容简介
介本书是针对“并行程序设计”“并行计算”等课程编写的教材，内容包括并行计算基础知识、共享内存系统的OpenMP和Pthreads多线程编程、消息传递系统的MPI编程、Slurm作业管理系统、GPU等异构系统的CUDA/OpenCL/OpenACC/Athread编程、常用的并行设计与性能优化方法、典型并行应用算法等，另外，还特别增加了针对我国自主研发的申威处理器编程的相关内容。本书涵盖并行程序设计最常用的编程语言/接口、设计与性能优化方法、基础应用算法等内容，一方面反映了OpenMP、MPI等成熟编程语言/接口的新特性，以及GPU异构编程等新型编程接口；另一方面在典型并行应用算法部分尝试用计算机专业人员易于理解的方式介绍典型算法，特别是以线性方程组迭代求解方法中的共轭梯度法为例。本书每章都设置了以编程为主的习题，鼓励读者通过编写程序掌握相关方法。本书适合作为计算机和信息类专业高年级本科生和研究生的教材，也可供高性能计算和并行计算领域的科研人员参考。
作者简介
刘轶，博士，北京航空航天大学计算机学院教授、博士生导师。现为北京航空航天大学计算机学院中德联合软件研究所所长。主要研究方向为计算机系统结构及高性能计算、计算机网络。近年来主持／参加了多项 重大／重点研究项目，在多核／众核处理器并行编程、高性能计算系统模拟与容错技术等方面开展研究工作。近年来在 期刊、学报及IEEE 会议上发表论文数十篇，拥有发明专利20余项。获北京市科技进步一等奖一项、教学成果一等奖一项。近年来主讲课程包括：计算机学院本科生“计算机网络”、研究生“并行程序设计”和高等理工学院研究生“并行计算”。
本书特色
本书注重并行编程能力训练，在介绍并行编程语言/接口时，同步给出了很多示例代码和例子程序，帮助读者更清晰地了解如何在程序中使用这些编程接口，进而编写出满足需求的并行程序。
本书内容涵盖了主流的并行编程语言/接口，包括多线程编程接口OpenMP和Pthreads、消息传递接口MPI，以及CUDA、OpenCL、OpenAcc等异构编程接口。
本书介绍了面向我国自主申威处理器架构的Athread编程接口，可以帮助读者学习掌握如何在我国自主超算系统上编写并行程序。
通俗易懂，偏重实践，手把手教你编写并行程序。
目录
第 1 章
并行程序设计概述
.
………………………………………………………………1
1.1 并行性概述 ……………………………………………………………………………………..1
1.2 如何衡量计算速度 …………………………………………………………………………..3
1.3 并行计算系统基本知识 ……………………………………………………………………6
1.3.1 弗林分类 ……………………………………………………………………………..6
1.3.2 共享内存系统与消息传递系统 ……………………………………………..8
1.3.3 几种常见的并行计算系统 …………………………………………………..10
1.3.4 互连网络 ……………………………………………………………………………15
1.3.5 多级存储体系结构 ……………………………………………………………..16
1.4 并行编程语言/接口分类 ………………………………………………………………17
1.5 浮点数格式 ……………………………………………………………………………………19
1.6 例子程序 ……………………………………………………………………………………….21
1.6.1 矩阵相乘 ……………………………………………………………………………21
1.6.2 规约和扫描 ………………………………………………………………………..22
1.7 小结 ………………………………………………………………………………………………26
题 ………………………………………………………………………………………………27
第 2 章
共享内存系统并行编程
.
…………………………………………………….28
2.1 共享内存系统中的并行模型 …………………………………………………………..28
2.1.1 多线程并行概述 …………………………………………………………………29
2.1.2 同步与互斥的概念 ……………………………………………………………..30
2.2 OpenMP编程 ………………………………………………………………………………..31
2.2.1 概述 …………………………………………………………………………………..31
2.2.2 OpenMP的基本命令 ……………………………………………………………33
并行程序设计
X
2.2.3 共享工作构造及其组合 …………………………………………………………………….35
2.2.4 线程间同步与互斥 ……………………………………………………………………………40
2.2.5 常用子句 ………………………………………………………………………………………….43
2.2.6 OpenMP 示例程序：级数法计算圆周率 …………………………………………….51
2.2.7 task 工作构造 ……………………………………………………………………………………52
2.3 Pthreads编程 ……………………………………………………………………………………………….57
2.3.1 Pthreads 简介 …………………………………………………………………………………….57
2.3.2 线程的创建和止 ……………………………………………………………………………57
2.3.3 线程互斥 ………………………………………………………………………………………….63
2.3.4 Pthreads 示例程序：级数法计算圆周率 ……………………………………………..67
2.3.5 线程同步 ………………………………………………………………………………………….69
2.3.6 Pthreads 示例程序：生产者–消费者 …………………………………………………..76
2.3.7 线程死锁与锁粒度 ……………………………………………………………………………79
2.4 面向多核系统的新型编程语言/接口 …………………………………………………………..82
2.4.1 Cilk与Cilk++ …………………………………………………………………………………….82
2.4.2 TBB ………………………………………………………………………………………………….85
2.5 小结 …………………………………………………………………………………………………………….88
题 …………………………………………………………………………………………………………….88
第 3 章
消息传递系统并行编程
.
…………………………………………………………………90
3.1 MPI 简介 …………………………………………………………………………………………………….90
3.1.1 MPI 是什么？ …………………………………………………………………………………..90
3.1.2 MPI 的并行模式 ……………………………………………………………………………….91
3.1.3 一个简单的MPI 程序 ………………………………………………………………………..92
3.1.4 MPI 基本环境 …………………………………………………………………………………..93
3.1.5 通信子、进程组、进程号 …………………………………………………………………95
3.1.6 MPI 数据类型 …………………………………………………………………………………..96
3.1.7 MPI 通信简介 …………………………………………………………………………………..98
3.2 点对点通信 ………………………………………………………………………………………………….99
3.2.1 标准通信模式 …………………………………………………………………………………100
3.2.2 缓存通信模式 …………………………………………………………………………………104
3.2.3 同步通信模式 …………………………………………………………………………………106
3.2.4 就绪通信模式 …………………………………………………………………………………106
3.2.5 四种通信模式小结 ………………………………………………………………………….107
3.2.6 组合发送接收 …………………………………………………………………………………108
3.2.7 非阻塞通信 …………………………………………………………………………………….109
3.3 集合通信 ……………………………………………………………………………………………………117
3.3.1 集合通信概述 …………………………………………………………………………………117
3.3.2 数据广播MPI_Bcast ………………………………………………………………………..118
3.3.3 数据分发MPI_Scatter ………………………………………………………………………119
3.3.4 数据收集MPI_Gather ………………………………………………………………………121
3.3.5 组收集MPI_Allgather ………………………………………………………………………123
3.3.6 全互换MPI_Alltoall …………………………………………………………………………124
3.3.7 规约MPI_Reduce …………………………………………………………………………….126
3.3.8 组规约MPI_Allreduce ………………………………………………………………………130
3.3.9 扫描MPI_Scan …………………………………………………………………………………130
3.3.10 栅栏MPI_Barrier ……………………………………………………………………………131
3.4 一个MPI示例程序 ……………………………………………………………………………………132
3.4.1 数值积分的计算 ……………………………………………………………………………..132
3.4.2 基于数值积分的圆周率计算程序 …………………………………………………….133
3.4.3 MPI墙钟时间 ………………………………………………………………………………….134
3.5 进程组和通信子 …………………………………………………………………………………………135
3.5.1 组管理 ……………………………………………………………………………………………136
3.5.2 通信子管理 …………………………………………………………………………………….138
3.5.3 组间通信子 …………………………………………………………………………………….140
3.6 MPI与多线程 ……………………………………………………………………………………………141
3.6.1 如何在MPI程序中使用多线程 …………………………………………………………141
3.6.2 MPI+OpenMP示例程序 ……………………………………………………………………142
3.6.3 分析和讨论 …………………………………………………………………………………….144
3.7 进程拓扑 ……………………………………………………………………………………………………145
3.7.1 进程拓扑简介 …………………………………………………………………………………145
3.7.2 创建进程拓扑 …………………………………………………………………………………146
3.7.3 进程拓扑相关的通信函数 ……………………………………………………………….149
3.8 PGAS编程及语言 ……………………………………………………………………………………..150
3.9 作业管理系统及使用 ………………………………………………………………………………….156
3.9.1 作业管理系统简介 ………………………………………………………………………….156
3.9.2 Slurm简介 ……………………………………………………………………………………….156
3.9.3 在Slurm中以作业方式执行程序 ……………………………………………………….158
3.9.4 Slurm的作业脚本 …………………………………………………………………………….160
3.9.5 在Slurm中以其他方式执行程序 ……………………………………………………….161
3.9.6 Slurm常用命令 ………………………………………………………………………………..162
3.10 小结 …………………………………………………………………………………………………………166
题 ………………………………………………………………………………………………………….167
第 4 章
异构系统并行编程
.
……………………………………………………………………….169
4.1 异构系统编程概述 ……………………………………………………………………………………..169
4.2 面向NVIDIA GPU的CUDA编程 ……………………………………………………………..170
4.2.1 CUDA概述 ……………………………………………………………………………………..170
4.2.2 Hello World程序：CUDA程序的基本形态 ……………………………………….172
4.2.3 两个整数相加程序：CPU-GPU数据交换 …………………………………………173
4.2.4 向量求和程序：CUDA多线程 …………………………………………………………176
4.2.5 CUDA线程组织 ………………………………………………………………………………177
4.2.6 CUDA内存层次与变量修饰符 …………………………………………………………181
4.2.7 函数修饰符 …………………………………………………………………………………….184
4.2.8 CUDA流 …………………………………………………………………………………………185
4.2.9 性能化 ………………………………………………………………………………………..192
4.2.10 CUDA统一内存空间 ……………………………………………………………………..197
4.2.11 使用多GPU ……………………………………………………………………………………198
4.3 OpenCL编程 ……………………………………………………………………………………………..200
4.3.1 OpenCL概述 ……………………………………………………………………………………200
4.3.2 OpenCL程序的执行流程及相关API …………………………………………………202
4.3.3 OpenCL示例程序一：向量求和 ……………………………………………………….211
4.3.4 OpenCL的执行模型与线程组织 ……………………………………………………….215
4.3.5 OpenCL的内存层次结构 ………………………………………………………………….218
4.3.6 OpenCL示例程序二：矩阵相乘 ……………………………………………………….220
4.4 面向申威处理器的Athread编程 …………………………………………………………………222
4.4.1 申威处理器及其编程简介 ……………………………………………………………….222
4.4.2 Hello World程序：Athread程序的基本形态 ………………………………………223
4.4.3 Athread变量的局存储空间属性 …………………………………………………….225
4.4.4 Athread主–从核编程接口 …………………………………………………………………225
4.4.5 Athread寄存器通信 ………………………………………………………………………….229
4.4.6 Athread版的Cannon并行矩阵相乘 ……………………………………………………230
4.5 OpenACC编程 …………………………………………………………………………………………..234
4.5.1 OpenACC概述 …………………………………………………………………………………234
4.5.2 OpenACC语法 …………………………………………………………………………………234
4.5.3 OpenACC循环并行性 ………………………………………………………………………237
4.5.4 基于申威处理器的OpenACC编程 …………………………………………………….238
4.6 小结 …………………………………………………………………………………………………………..246
题 …………………………………………………………………………………………………………..246
第 5 章
并行程序性能化
.
………………………………………………………………………248
5.1 Amdahl定律 ………………………………………………………………………………………………248
5.2 影响性能的主要因素 ………………………………………………………………………………….250
5.2.1 并行开销 ………………………………………………………………………………………..250
5.2.2 负载均衡 ………………………………………………………………………………………..251
5.2.3 并行粒度 ………………………………………………………………………………………..252
5.2.4 并行划分 ………………………………………………………………………………………..252
5.2.5 依赖关系 ………………………………………………………………………………………..253
5.2.6 局性 ……………………………………………………………………………………………254
5.3 并行程序的可扩展性及性能化方法 …………………………………………………………255
5.3.1 什么是并行程序的可扩展性？ ………………………………………………………..255
5.3.2 确并行程序可扩展性的重要原则：独立计算块 ……………………………256
5.3.3 数据划分对性能和可扩展性的影响 …………………………………………………259
5.3.4 其他常用性能化方法 …………………………………………………………………..264
5.4 PCAM并行设计方法 …………………………………………………………………………………266
5.4.1 划分 ……………………………………………………………………………………………….266
5.4.2 通信 ……………………………………………………………………………………………….268
5.4.3 组合 ……………………………………………………………………………………………….270
5.4.4 映射 ……………………………………………………………………………………………….271
5.5 小结 …………………………………………………………………………………………………………..272
题 …………………………………………………………………………………………………………..272
第 6 章
典型并行应用算法
.
………………………………………………………………………274
6.1 矩阵相乘 ……………………………………………………………………………………………………274
6.1.1 基于分块的并行矩阵相乘 ……………………………………………………………….274
6.1.2 改进的分块矩阵相乘——Cannon算法 ……………………………………………..275
6.1.3 支持矩阵相乘的用硬件——脉动阵列 ………………………………………….277
6.2 线性方程组的直接求解 ………………………………………………………………………………279
6.2.1 线性方程组及其求解方法简介 ………………………………………………………..279
6.2.2 三角方程组的回代求解 …………………………………………………………………..281
6.2.3 高斯消去法 …………………………………………………………………………………….281
6.2.4 LU分解算法 ……………………………………………………………………………………282
6.2.5 并行LU分解：逐行交错条带划分和块–循环分配 …………………………….285
6.3 线性方程组的迭代求解 ………………………………………………………………………………286
6.3.1 迭代求解方法 ………………………………………………………………………….286
6.3.2 共轭梯度求解方法 ………………………………………………………………………….289
6.3.3 迭代法求解示例：偏微分方程求解 …………………………………………………295
6.3.4 几种迭代法的并行性讨论 ……………………………………………………………….298
6.3.5 稀疏矩阵的压缩数据格式 ……………………………………………………………….299
6.4 快速排序 ……………………………………………………………………………………………………301
6.5 快速傅里叶变换 …………………………………………………………………………………………303
6.5.1 算法背景 ………………………………………………………………………………………..303
6.5.2 算法原理 ………………………………………………………………………………………..303
6.5.3 递归算法转换为迭代算法 ……………………………………………………………….306
6.5.4 并行算法 ………………………………………………………………………………………..307
6.6 基础线性代数库和软件 …………………………………………………………………………..309
6.6.1 线性代数算法库BLAS …………………………………………………………………….309
6.6.2 线性代数软件LAPACK ………………………………………………………………..312
6.7 小结 …………………………………………………………………………………………………………..314
题 …………………………………………………………………………………………………………..314
附录A
英文缩写词
.
……………………………………………………………………………………316
参考文献…………………………………………………………………………………………………….318
并行程序设计概述
.
………………………………………………………………1
1.1 并行性概述 ……………………………………………………………………………………..1
1.2 如何衡量计算速度 …………………………………………………………………………..3
1.3 并行计算系统基本知识 ……………………………………………………………………6
1.3.1 弗林分类 ……………………………………………………………………………..6
1.3.2 共享内存系统与消息传递系统 ……………………………………………..8
1.3.3 几种常见的并行计算系统 …………………………………………………..10
1.3.4 互连网络 ……………………………………………………………………………15
1.3.5 多级存储体系结构 ……………………………………………………………..16
1.4 并行编程语言/接口分类 ………………………………………………………………17
1.5 浮点数格式 ……………………………………………………………………………………19
1.6 例子程序 ……………………………………………………………………………………….21
1.6.1 矩阵相乘 ……………………………………………………………………………21
1.6.2 规约和扫描 ………………………………………………………………………..22
1.7 小结 ………………………………………………………………………………………………26
题 ………………………………………………………………………………………………27
第 2 章
共享内存系统并行编程
.
…………………………………………………….28
2.1 共享内存系统中的并行模型 …………………………………………………………..28
2.1.1 多线程并行概述 …………………………………………………………………29
2.1.2 同步与互斥的概念 ……………………………………………………………..30
2.2 OpenMP编程 ………………………………………………………………………………..31
2.2.1 概述 …………………………………………………………………………………..31
2.2.2 OpenMP的基本命令 ……………………………………………………………33
并行程序设计
X
2.2.3 共享工作构造及其组合 …………………………………………………………………….35
2.2.4 线程间同步与互斥 ……………………………………………………………………………40
2.2.5 常用子句 ………………………………………………………………………………………….43
2.2.6 OpenMP 示例程序：级数法计算圆周率 …………………………………………….51
2.2.7 task 工作构造 ……………………………………………………………………………………52
2.3 Pthreads编程 ……………………………………………………………………………………………….57
2.3.1 Pthreads 简介 …………………………………………………………………………………….57
2.3.2 线程的创建和止 ……………………………………………………………………………57
2.3.3 线程互斥 ………………………………………………………………………………………….63
2.3.4 Pthreads 示例程序：级数法计算圆周率 ……………………………………………..67
2.3.5 线程同步 ………………………………………………………………………………………….69
2.3.6 Pthreads 示例程序：生产者–消费者 …………………………………………………..76
2.3.7 线程死锁与锁粒度 ……………………………………………………………………………79
2.4 面向多核系统的新型编程语言/接口 …………………………………………………………..82
2.4.1 Cilk与Cilk++ …………………………………………………………………………………….82
2.4.2 TBB ………………………………………………………………………………………………….85
2.5 小结 …………………………………………………………………………………………………………….88
题 …………………………………………………………………………………………………………….88
第 3 章
消息传递系统并行编程
.
…………………………………………………………………90
3.1 MPI 简介 …………………………………………………………………………………………………….90
3.1.1 MPI 是什么？ …………………………………………………………………………………..90
3.1.2 MPI 的并行模式 ……………………………………………………………………………….91
3.1.3 一个简单的MPI 程序 ………………………………………………………………………..92
3.1.4 MPI 基本环境 …………………………………………………………………………………..93
3.1.5 通信子、进程组、进程号 …………………………………………………………………95
3.1.6 MPI 数据类型 …………………………………………………………………………………..96
3.1.7 MPI 通信简介 …………………………………………………………………………………..98
3.2 点对点通信 ………………………………………………………………………………………………….99
3.2.1 标准通信模式 …………………………………………………………………………………100
3.2.2 缓存通信模式 …………………………………………………………………………………104
3.2.3 同步通信模式 …………………………………………………………………………………106
3.2.4 就绪通信模式 …………………………………………………………………………………106
3.2.5 四种通信模式小结 ………………………………………………………………………….107
3.2.6 组合发送接收 …………………………………………………………………………………108
3.2.7 非阻塞通信 …………………………………………………………………………………….109
3.3 集合通信 ……………………………………………………………………………………………………117
3.3.1 集合通信概述 …………………………………………………………………………………117
3.3.2 数据广播MPI_Bcast ………………………………………………………………………..118
3.3.3 数据分发MPI_Scatter ………………………………………………………………………119
3.3.4 数据收集MPI_Gather ………………………………………………………………………121
3.3.5 组收集MPI_Allgather ………………………………………………………………………123
3.3.6 全互换MPI_Alltoall …………………………………………………………………………124
3.3.7 规约MPI_Reduce …………………………………………………………………………….126
3.3.8 组规约MPI_Allreduce ………………………………………………………………………130
3.3.9 扫描MPI_Scan …………………………………………………………………………………130
3.3.10 栅栏MPI_Barrier ……………………………………………………………………………131
3.4 一个MPI示例程序 ……………………………………………………………………………………132
3.4.1 数值积分的计算 ……………………………………………………………………………..132
3.4.2 基于数值积分的圆周率计算程序 …………………………………………………….133
3.4.3 MPI墙钟时间 ………………………………………………………………………………….134
3.5 进程组和通信子 …………………………………………………………………………………………135
3.5.1 组管理 ……………………………………………………………………………………………136
3.5.2 通信子管理 …………………………………………………………………………………….138
3.5.3 组间通信子 …………………………………………………………………………………….140
3.6 MPI与多线程 ……………………………………………………………………………………………141
3.6.1 如何在MPI程序中使用多线程 …………………………………………………………141
3.6.2 MPI+OpenMP示例程序 ……………………………………………………………………142
3.6.3 分析和讨论 …………………………………………………………………………………….144
3.7 进程拓扑 ……………………………………………………………………………………………………145
3.7.1 进程拓扑简介 …………………………………………………………………………………145
3.7.2 创建进程拓扑 …………………………………………………………………………………146
3.7.3 进程拓扑相关的通信函数 ……………………………………………………………….149
3.8 PGAS编程及语言 ……………………………………………………………………………………..150
3.9 作业管理系统及使用 ………………………………………………………………………………….156
3.9.1 作业管理系统简介 ………………………………………………………………………….156
3.9.2 Slurm简介 ……………………………………………………………………………………….156
3.9.3 在Slurm中以作业方式执行程序 ……………………………………………………….158
3.9.4 Slurm的作业脚本 …………………………………………………………………………….160
3.9.5 在Slurm中以其他方式执行程序 ……………………………………………………….161
3.9.6 Slurm常用命令 ………………………………………………………………………………..162
3.10 小结 …………………………………………………………………………………………………………166
题 ………………………………………………………………………………………………………….167
第 4 章
异构系统并行编程
.
……………………………………………………………………….169
4.1 异构系统编程概述 ……………………………………………………………………………………..169
4.2 面向NVIDIA GPU的CUDA编程 ……………………………………………………………..170
4.2.1 CUDA概述 ……………………………………………………………………………………..170
4.2.2 Hello World程序：CUDA程序的基本形态 ……………………………………….172
4.2.3 两个整数相加程序：CPU-GPU数据交换 …………………………………………173
4.2.4 向量求和程序：CUDA多线程 …………………………………………………………176
4.2.5 CUDA线程组织 ………………………………………………………………………………177
4.2.6 CUDA内存层次与变量修饰符 …………………………………………………………181
4.2.7 函数修饰符 …………………………………………………………………………………….184
4.2.8 CUDA流 …………………………………………………………………………………………185
4.2.9 性能化 ………………………………………………………………………………………..192
4.2.10 CUDA统一内存空间 ……………………………………………………………………..197
4.2.11 使用多GPU ……………………………………………………………………………………198
4.3 OpenCL编程 ……………………………………………………………………………………………..200
4.3.1 OpenCL概述 ……………………………………………………………………………………200
4.3.2 OpenCL程序的执行流程及相关API …………………………………………………202
4.3.3 OpenCL示例程序一：向量求和 ……………………………………………………….211
4.3.4 OpenCL的执行模型与线程组织 ……………………………………………………….215
4.3.5 OpenCL的内存层次结构 ………………………………………………………………….218
4.3.6 OpenCL示例程序二：矩阵相乘 ……………………………………………………….220
4.4 面向申威处理器的Athread编程 …………………………………………………………………222
4.4.1 申威处理器及其编程简介 ……………………………………………………………….222
4.4.2 Hello World程序：Athread程序的基本形态 ………………………………………223
4.4.3 Athread变量的局存储空间属性 …………………………………………………….225
4.4.4 Athread主–从核编程接口 …………………………………………………………………225
4.4.5 Athread寄存器通信 ………………………………………………………………………….229
4.4.6 Athread版的Cannon并行矩阵相乘 ……………………………………………………230
4.5 OpenACC编程 …………………………………………………………………………………………..234
4.5.1 OpenACC概述 …………………………………………………………………………………234
4.5.2 OpenACC语法 …………………………………………………………………………………234
4.5.3 OpenACC循环并行性 ………………………………………………………………………237
4.5.4 基于申威处理器的OpenACC编程 …………………………………………………….238
4.6 小结 …………………………………………………………………………………………………………..246
题 …………………………………………………………………………………………………………..246
第 5 章
并行程序性能化
.
………………………………………………………………………248
5.1 Amdahl定律 ………………………………………………………………………………………………248
5.2 影响性能的主要因素 ………………………………………………………………………………….250
5.2.1 并行开销 ………………………………………………………………………………………..250
5.2.2 负载均衡 ………………………………………………………………………………………..251
5.2.3 并行粒度 ………………………………………………………………………………………..252
5.2.4 并行划分 ………………………………………………………………………………………..252
5.2.5 依赖关系 ………………………………………………………………………………………..253
5.2.6 局性 ……………………………………………………………………………………………254
5.3 并行程序的可扩展性及性能化方法 …………………………………………………………255
5.3.1 什么是并行程序的可扩展性？ ………………………………………………………..255
5.3.2 确并行程序可扩展性的重要原则：独立计算块 ……………………………256
5.3.3 数据划分对性能和可扩展性的影响 …………………………………………………259
5.3.4 其他常用性能化方法 …………………………………………………………………..264
5.4 PCAM并行设计方法 …………………………………………………………………………………266
5.4.1 划分 ……………………………………………………………………………………………….266
5.4.2 通信 ……………………………………………………………………………………………….268
5.4.3 组合 ……………………………………………………………………………………………….270
5.4.4 映射 ……………………………………………………………………………………………….271
5.5 小结 …………………………………………………………………………………………………………..272
题 …………………………………………………………………………………………………………..272
第 6 章
典型并行应用算法
.
………………………………………………………………………274
6.1 矩阵相乘 ……………………………………………………………………………………………………274
6.1.1 基于分块的并行矩阵相乘 ……………………………………………………………….274
6.1.2 改进的分块矩阵相乘——Cannon算法 ……………………………………………..275
6.1.3 支持矩阵相乘的用硬件——脉动阵列 ………………………………………….277
6.2 线性方程组的直接求解 ………………………………………………………………………………279
6.2.1 线性方程组及其求解方法简介 ………………………………………………………..279
6.2.2 三角方程组的回代求解 …………………………………………………………………..281
6.2.3 高斯消去法 …………………………………………………………………………………….281
6.2.4 LU分解算法 ……………………………………………………………………………………282
6.2.5 并行LU分解：逐行交错条带划分和块–循环分配 …………………………….285
6.3 线性方程组的迭代求解 ………………………………………………………………………………286
6.3.1 迭代求解方法 ………………………………………………………………………….286
6.3.2 共轭梯度求解方法 ………………………………………………………………………….289
6.3.3 迭代法求解示例：偏微分方程求解 …………………………………………………295
6.3.4 几种迭代法的并行性讨论 ……………………………………………………………….298
6.3.5 稀疏矩阵的压缩数据格式 ……………………………………………………………….299
6.4 快速排序 ……………………………………………………………………………………………………301
6.5 快速傅里叶变换 …………………………………………………………………………………………303
6.5.1 算法背景 ………………………………………………………………………………………..303
6.5.2 算法原理 ………………………………………………………………………………………..303
6.5.3 递归算法转换为迭代算法 ……………………………………………………………….306
6.5.4 并行算法 ………………………………………………………………………………………..307
6.6 基础线性代数库和软件 …………………………………………………………………………..309
6.6.1 线性代数算法库BLAS …………………………………………………………………….309
6.6.2 线性代数软件LAPACK ………………………………………………………………..312
6.7 小结 …………………………………………………………………………………………………………..314
题 …………………………………………………………………………………………………………..314
附录A
英文缩写词
.
……………………………………………………………………………………316
参考文献…………………………………………………………………………………………………….318
