并行程序设计原理PDF电子书下载

第一部分　基础 2

第1章　导论 2

1.1　并行的威力和潜能 2

1.1.1　并行，一个熟悉的概念 2

1.1.2　计算机程序中的并行 2

1.1.3　多核计算机，一个机遇 3

1.1.4　使用并行硬件的更多机遇 4

1.1.5　并行计算和分布式计算的比较 4

1.1.6　系统级并行 5

1.1.7　并行抽象的便利 5

1.2　考察顺序程序和并行程序 6

1.2.1　并行化编译器 6

1.2.2　范例求解的变化 7

1.2.3　并行前缀求和 8

1.3　使用多指令流实现并行 9

1.3.1　线程概念 9

1.3.2　统计3的个数的多线程求解方法 10

1.4　目标：可扩展性和性能可移植性 17

1.4.1　可扩展性 17

1.4.2　性能可移植性 18

1.4.3　原理第一 18

1.5　小结 19

历史回顾 19

习题 19

第2章　认识并行计算机 21

2.1　用可移植性衡量机器特征 21

2.2　6种并行机介绍 21

2.2.1　芯片多处理器 21

2.2.2　对称多处理器体系结构 23

2.2.3　异构芯片设计 26

2.2.4　机群 27

2.2.5　超级计算机 27

2.2.6　对6种并行计算机的评论 30

2.3　顺序计算机的抽象 30

2.3.1　应用RAM模型 31

2.3.2　评估RAM模型 31

2.4　PRAM：一种并行计算机模型 32

2.5　CTA：一种实际的并行计算机模型 32

2.5.1　CTA模型 33

2.5.2　通信时延 36

2.5.3　CTA的性质 36

2.6　存储器访问机制 37

2.6.1　共享存储器 37

2.6.2　单边通信 37

2.6.3　消息传递 38

2.6.4　存储器一致性模型 38

2.6.5　程序设计模型 39

2.7　进一步研究通信 40

2.8　CTA模型的应用 40

2.9　小结 41

历史回顾 41

习题 41

第3章　性能分析 43

3.1　动机和基本概念 43

3.1.1　并行和性能 43

3.1.2　线程和进程 43

3.1.3　时延和吞吐率 44

3.2　性能损失的原因 45

3.2.1　开销 45

3.2.2　不可并行代码 46

3.2.3　竞争 47

3.2.4　空闲时间 47

3.3　并行结构 48

3.3.1　相关性 48

3.3.2　相关性限制并行性 49

3.3.3　粒度 50

3.3.4　局部性 51

3.4　性能协调 51

3.4.1　通信和计算 52

3.4.2　存储器和并行性 52

3.4.3　开销与并行 52

3.5　性能度量 53

3.5.1　执行时间 54

3.5.2　加速比 54

3.5.3　超线性加速比 55

3.5.4　效率 55

3.5.5　加速比问题 55

3.5.6　可扩展加速比和固定加速比 56

3.6　可扩展性能 56

3.6.1　难于达到的可扩展性能 57

3.6.2　硬件问题 57

3.6.3　软件问题 58

3.6.4　问题规模的扩展 58

3.7　小结 59

历史回顾 59

习题 59

第二部分　并行抽象 62

第4章　并行程序设计起步 62

4.1　数据和任务并行 62

4.1.1　定义 62

4.1.2　数据和任务并行的说明 62

4.2　Peril-L记号 63

4.2.1　扩展C语言 63

4.2.2　并行线程 63

4.2.3　同步和协同 64

4.2.4　存储器模型 64

4.2.5　同步存储器 66

4.2.6　归约和扫描 67

4.2.7　归约的抽象 68

4.3　统计3的个数程序实例 68

4.4　并行性的表示 68

4.4.1　固定并行性 68

4.4.2　无限并行性 69

4.4.3　可扩展并行性 70

4.5 按字母顺序排序实例 71

4.5.1　无限并行性 71

4.5.2　固定并行性 72

4.5.3　可扩展并行性 73

4.6　三种求解方法的比较 77

4.7　小结 78

历史回顾 78

习题 78

第5章　可扩展算法技术 80

5.1　独立计算块 80

5.2　Schwartz算法 80

5.3　归约和扫描抽象 82

5.3.1　通用归约和扫描举例 83

5.3.2　基本结构 84

5.3.3　通用归约结构 86

5.3.4　通用扫描组件举例 87

5.3.5　应用通用扫描 88

5.3.6　通用向量操作 89

5.4　静态为进程分配工作 89

5.4.1　块分配 90

5.4.2　重叠区域 91

5.4.3　循环分配和块循环分配 92

5.4　不规则分配 94

5.5　动态为进程分配工作 95

5.5.1　工作队列 95

5.5.2　工作队列的变体 97

5.5.3　案例研究：并发存储器分配 97

5.6　树 99

5.6.1　按子树分配 99

5.6.2　动态分配 100

5.7　小结 100

历史回顾 100

习题 101

第三部分　并行程序设计语言第6章　线程程序设计 104

6.1　POSIX Threads 104

6.1.1　线程的创建和销毁 104

6.1.2　互斥 108

6.1.3　同步 110

6.1.4　安全性问题 117

6.1.5　性能问题 120

6.1.6　案例研究1：连续过度松弛 124

6.1.7　案例研究2：重叠同步与计算 129

6.1.8　案例研究3：多核芯片上的流计算 134

6.2　Java Threads 134

6.2.1　同步方法 135

6.2.2　同步语句 136

6.2.3　统计3的个数程序实例 136

6.2.4　易变存储器 138

6.2.5　原子对象 138

6.2.6　锁对象 138

6.2.7　执行器 138

6.2.8　并发集合 138

6.3　OpenMP 138

6.3.1　统计3的个数程序实例 139

6.3.2　parallel for的语义局限 141

6.3.3　归约 141

6.3.4　线程的行为和交互 142

6.3.5　段 142

6.3.6　OpenMP总结 143

6.4　小结 143

历史回顾 143

习题 143

第7章　MPI和其他局部视图语言 145

7.1　MPI：消息传递接口 145

7.1.1　统计3的个数程序实例 145

7.1.2　组和通信子 152

7.1.3　点对点通信 152

7.1.4　集合通信 154

7.1.5　举例：连续过度松弛 157

7.1.6　性能问题 159

7.1.7　安全性问题 164

7.2　分区的全局地址空间语言 164

7.2.1　Co-Array Fortran 165

7.2.2　Unified Parallel C 166

7.2.3　Titanium 167

7.3　小结 167

历史回顾 168

习题 168

第8章　ZPL和其他全局视图语言 169

8.1　ZPL程序设计语言 169

8.2　ZPL基本概念 169

8.2.1　区域 170

8.2.2　数组计算 171

8.3　生命游戏实例 173

8.3.1　问题 173

8.3.2　解决方案 173

8.3.3　如何实现 174

8.3.4　生命游戏的哲学 175

8.4　与众不同的ZPL特征 175

8.4.1　区域 175

8.4.2　语句级索引 175

8.4.3　区域的限制 176

8.4.4　性能模型 176

8.4.5　用减法实现加法 177

8.5　操作不同秩的数组 177

8.5.1　部分归约 177

8.5.2　扩充 178

8.5.3　扩充的原理 179

8.5.4　数据操作举例 179

8.5.5　扩充区域 180

8.5.6　矩阵乘 181

8.6　用重映射操作重排数据 182

8.6.1　索引数组 183

8.6.2　重映射 183

8.6.3　排序举例 185

8.7　ZPL程序的并行执行 186

8.7.1　编译器的职责 186

8.7.2　指定进程数 187

8.7.3　为进程分配区域 187

8.7.4　数组分配 188

8.7.5　标量分配 188

8.7.6　工作分派 188

8.8　性能模型 189

8.8.1　应用实例1：生命游戏 190

8.8.2　应用实例2：SUMMA算法 190

8.8.3　性能模型总结 191

8.9　NESL并行语言 191

8.9.1　语言概念 191

8.9.2　用嵌套并行实现矩阵乘 192

8.9.3　NESL复杂性模型 192

8.10　小结 192

历史回顾 193

习题 193

第9章 对并行程序设计现状的评价 194

9.1　并行语言的四个重要性质 194

9.1.1　正确性 194

9.1.2　性能 195

9.1.3　可扩展性 196

9.1.4　可移植性 196

9.2　评估现有方法 196

9.2.1　POSIX Threads 196

9.2.2　Java Threads 197

9.2.3　OpenMP 197

9.2.4　MPI 197

9.2.5　PGAS语言 198

9.2.6　ZPL 198

9.2.7　NESL 199

9.3　可供将来借鉴的经验 199

9.3.1　隐藏并行 199

9.3.2　透明化性能 200

9.3.3　局部性 200

9.3.4　约束并行 200

9.3.5　隐式并行与显式并行 201

9.4　小结 201

历史回顾 201

习题 202

第四部分　展望 204

第10章　并行程序设计的未来方向 204

10.1　附属处理器 204

10.1.1　图形处理部件 204

10.1.2　Cell处理器 207

10.1.3　附属处理器的总结 207

10.2　网格计算 208

10.3　事务存储器 209

10.3.1　与锁的比较 210

10.3.2　实现方法 210

10.3.3　未解决的问题 211

10.4　MapReduce 212

10.5　问题空间的提升 214

10.6　新出现的语言 214

10.6.1　Chapel 215

10.6.2　Fortress 215

10.6.3　X10 216

10.7　小结 218

历史回顾 218

习题 218

第11章　编写并行程序 219

11.1　起步 219

11.1.1　访问和软件 219

11.1.2　Hello,World 219

11.2　并行程序设计的建议 220

11.2.1　增量式开发 220

11.2.2　侧重并行结构 220

11.2.3　并行结构的测试 221

11.2.4　顺序程序设计 221

11.2.5　乐意写附加代码 222

11.2.6　测试时对参数的控制 222

11.2.7　功能性调试 223

11.3　对结课课程设计的设想 223

11.3.1　实现现有的并行算法 223

11.3.2　与标准的基准测试程序媲美 224

11.3.3　开发新的并行计算 224

11.4　性能度量 225

11.4.1　与顺序求解方法比较 226

11.4.2　维护一个公正的实验设置 226

11.5　了解并行性能 227

11.6　性能分析 227

11.7　实验方法学 228

11.8　可移植性和微调 229

11.9　小结 229

历史回顾 229

习题 229

术语表 230

参考文献 234