第1章 为什么要并行计算 1
1.1为什么需要不断提升的性能 1
1.2为什么需要构建并行系统 2
1.3为什么需要编写并行程序 2
1.4怎样编写并行程序 4
1.5我们将做什么 5
1.6并发、并行、分布式 6
1.7本书的其余部分 7
1.8警告 7
1.9字体约定 7
1.10小结 8
1.11习题 8
第2章 并行硬件和并行软件 10
2.1背景知识 10
2.1.1冯·诺依曼结构 10
2.1.2进程、多任务及线程 11
2.2对冯·诺依曼模型的改进 12
2.2.1 Cache基础知识 12
2.2.2 Cache映射 13
2.2.3 Cache和程序：一个实例 14
2.2.4虚拟存储器 15
2.2.5指令级并行 17
2.2.6硬件多线程 19
2.3并行硬件 19
2.3.1 SIMD系统 20
2.3.2 MIMD系统 22
2.3.3互连网络 23
2.3.4 Cache一致性 28
2.3.5共享内存与分布式内存 30
2.4并行软件 31
2.4.1注意事项 31
2.4.2进程或线程的协调 31
2.4.3共享内存 32
2.4.4分布式内存 35
2.4.5 混合系统编程 37
2.5输入和输出 37
2.6性能 38
2.6.1加速比和效率 38
2.6.2阿姆达尔定律 40
2.6.3可扩展性 41
2.6.4计时 41
2.7并行程序设计 43
2.8编写和运行并行程序 46
2.9假设 47
2.10小结 47
2.10.1串行系统 47
2.10.2并行硬件 48
2.10.3并行软件 49
2.10.4输入和输出 50
2.10.5性能 50
2.10.6并行程序设计 51
2.10.7假设 51
2.11习题 51
第3章用MPI进行分布式内存编程 54
3.1预备知识 54
3.1.1编译与执行 55
3.1.2 MPI程序 56
3.1.3 MPI_ Init和 MPI_Finalize 56
3.1.4通信子、MPI_Comm size和 MPI_Comm_ rank 57
3.1.5 SPMD程序 57
3.1.6通信 57
3.1.7 MPI_Send 58
3.1.8 MPI_Recv 59
3.1.9消息匹配 59
3.1.10 status_P参数 60
3.1.11 MPI_Send和MPI_ Recv的语义 61
3.1.12潜在的陷阱 61
3.2用MPI来实现梯形积分法 62
3.2.1梯形积分法 62
3.2.2并行化梯形积分法 62
3.3 I/O处理 64
3.3.1输出 64
3.3.2输入 66
3.4集合通信 67
3.4.1树形结构通信 67
3.4.2 MPI_Reduce 68
3.4.3集合通信与点对点通信 69
3.4.4 MPI_Allreduce 70
3.4.5广播 70
3.4.6数据分发 72
3.4.7散射 73
3.4.8聚集 74
3.4.9全局聚集 75
3.5 MPI的派生数据类型 77
3.6 MPI程序的性能评估 79
3.6.1计时 79
3.6.2结果 82
3.6.3加速比和效率 83
3.6.4可扩展性 84
3.7并行排序算法 85
3.7.1简单的串行排序算法 85
3.7.2并行奇偶交换排序 86
3.7.3 MPI程序的安全性 88
3.7.4并行奇偶交换排序算法的重要内容 90
3.8小结 91
3.9习题 93
3.10编程作业 98
第4章用 Pthreads进行共享内存编程 100
4.1进程、线程和Pthreads 100
4.2 “ Hello， World”程序 101
4.2.1执行 101
4.2.2准备工作 102
4.2.3启动线程 103
4.2.4运行线程 104
4.2.5停止线程 105
4.2.6错误检查 105
4.2.7启动线程的其他方法 105
4.3矩阵-向量乘法 106
4.4临界区 107
4.5忙等待 109
4.6互斥量 112
4.7生产者-消费者同步和信号量 114
4.8路障和条件变量 117
4.8.1忙等待和互斥量 117
4.8.2信号量 118
4.8.3条件变量 119
4.8.4 Pthreads路障 121
4.9读写锁 121
4.9.1链表函数 121
4.9.2多线程链表 122
4.9.3 Pthreads读写锁 124
4.9.4不同实现方案的性能 125
4.9.5实现读写锁 126
4.10缓存、缓存一致性和伪共享 127
4.11线程安全性 130
4.12小结 132
4.13习题 134
4.14编程作业 137
第5章用OpenMP进行共享内存编程 139
5.1预备知识 140
5.1.1编译和运行OpenMP程序 140
5.1.2程序 141
5.1.3错误检查 143
5.2梯形积分法 143
5.3变量的作用域 147
5.4归约子句 147
5.5 parallel for指令 150
5.5.1警告 150
5.5.2数据依赖性 151
5.5.3寻找循环依赖 152
5.5.4 π值估计 153
5.5.5关于作用域的更多问题 154
5.6更多关于OpenMP的循环：排序 155
5.6.1冒泡排序 155
5.6.2奇偶变换排序 156
5.7循环调度 158
5.7.1 schedule子句 159
5.7.2 static调度类型 159
5.7.3 dynamic和guided调度类型 160
5.7.4 runtime调度类型 160
5.7.5调度选择 161
5.8生产者和消费者问题 162
5.8.1队列 162
5.8.2消息传递 162
5.8.3发送消息 162
5.8.4接收消息 163
5.8.5终止检测 163
5.8.6启动 164
5.8.7 atomi c指令 164
5.8.8临界区和锁 165
5.8.9在消息传递程序中使用锁 166
5.8.10 critical指令、atomic指令、锁的比较 167
5.8.11经验 167
5.9缓存、缓存一致性、伪共享 168
5.10线程安全性 172
5.11小结 174
5.12习题 176
5.13编程作业 179
第6章 并行程序开发 182
6.1 n体问题的两种解决方法 182
6.1.1问题 182
6.1.2两个串行程序 183
6.1.3并行化n体算法 186
6.1.4关于I/O 188
6.1.5用OpenMP并行化基本算法 188
6.1.6用OpenMP并行化简化算法 191
6.1.7评估OpenMP程序 193
6.1.8用Pthreads并行化算法 194
6.1.9用MPI并行化基本算法 195
6.1.10用MPI并行化简化算法 197
6.1.11 MPI程序的性能 200
6.2树形搜索 201
6.2.1递归的深度优先搜索 203
6.2.2非递归的深度优先搜索 204
6.2.3串行实现所用的数据结构 205
6.2.4串行实现的性能 206
6.2.5树形搜索的并行化 206
6.2.6采用Pthreads实现的静态并行化树搜索 208
6.2.7采用Pthreads实现的动态并行化树搜索 209
6.2.8 Pthreads树搜索程序的评估 212
6.2.9采用OpenMp实现的并行化树搜索程序 213
6.2.10 OpenMp实现的性能 215
6.2.11采用MPI和静态划分来实现树搜索 215
6.2.12采用MPI和动态划分来实现树搜索 221
6.3忠告 226
6.4选择哪个API 226
6.5小结 227
6.5.1 Pthreads和OpenMP 228
6.5.2 MPI 228
6.6习题 230
6.7编程作业 236
第7章 接下来的学习方向 238
参考文献 240
索引 242