并行性分析的数学原理PDF电子书下载

第一章 硬件并行设施 1

1.1 计算机并行性的发展 1

1.2 流水线并行原理 3

1.3 多向量流水 7

1.4 向量指令系统与向量汇编语言 12

1.5 阵列与数据流方式 16

1.6 多核芯片 20

1.7 紧耦合多处理机 22

1.8 松耦合多计算机 27

1.9 集群 30

1.10 单体巨型机 34

1.11 复体巨型机 40

1.12 源于小微巨型机的可伸缩性 46

1.13 云计算平台 54

第二章 语言并行机制 58

2.1 VFORTRAN语言 58

2.2 三元挑选符与下标对应规则 61

2.3 向量函数 62

2.4 向量过程 65

2.5 流水线处理 67

2.6 向量链接 72

2.7 向量屏蔽 74

2.8 数组运算 82

2.9 PFORTRAN语言 88

2.10 HPF语言 91

2.11 BXC语言 93

2.12 时序算子 97

2.13 控制结构 101

2.14 点对点通信 103

2.15 并行程序设计 106

第三章 显数据相关性的三种视图 110

3.1 并行处理的三种粒度 111

3.2 相关依赖等价条件下的并行处理 113

3.3 单层赋值循环的适应性 117

3.4 临时变量与归纳变量 120

3.5 三种赋值与限制条件 122

3.6 繁衍层次 126

3.7 结合链同体链与年长顺序定理 132

3.8 元素间的优先关系 136

3.9 数据相关与输入相关 139

第四章 语句视图与依赖片断 144

4.1 语句间的相关依赖 144

4.2 语句图与并行性判别 148

4.3 解析判别法与非整除规则 150

4.4 变序点 154

4.5 A0型循环的层次片断 158

4.6 计算实例 161

4.7 A1型和A型循环的层次片断 164

4.8 循环体的最简形式 168

4.9 指令级的并行性 171

4.10 加权汇编语句图 174

第五章 变量视图 179

5.1 坐标方法 179

5.2 超平面方法 193

5.3 相关分析方法 203

5.4 图论方法 213

5.5 统一的解析判别法 222

5.6 拓扑排序 228

5.7 临时数组与暂存语句 231

5.8 改写算法 237

第六章 元素视图 246

6.1 以元素为结点的困难和片断的概念 246

6.2 有待跨越的“鸿沟” 248

6.3 判别准则 250

6.4 判别举例 253

6.5 等价类与R-P逆对所引起的暂存 257

6.6 时序层次等价类的数学抽象 260

6.7 结点的数学抽象 262

6.8 循环间包含关系的直观含义 264

6.9 生存带的胀缩 266

6.10 包含关系的数学表示 269

6.11 强化定理 272

6.12 偏序结构 275

6.13 比较判别法及其在循环体上的应用 279

6.14 比较判别法在取值点集合上的应用 285

6.15 元素视图A型算法全过程 290

第七章 控制依赖向数据依赖的转换 298

7.1 不定因素与参数集 298

7.2 I0型循环及其闭体 301

7.3 I0型循环的并行处理 306

7.4 关于I0型循环并行的充要条件 313

7.5 再识别算法 316

7.6 再改写算法 329

7.7 优化算法 337

7.8 识别改写优化链 344

7.9 两道例题演示I0型算法全过程 358

第八章 多岔控制转移的结构化重构 370

8.1 简单三岔控制转移 370

8.2 三岔控制转移的完备形式 378

8.3 程序变换应满足的集合方程 381

8.4 〈t1，t2，m，t3，n〉型组合方式的嵌入载体 384

8.5 〈t1，t2，t3，m，n〉型组合方式的嵌入载体 390

8.6 〈t1，t2，t3，n，m〉型组合方式的嵌入载体 395

8.7 程序变换目标程序的优化 401

8.8 退化情形 411

8.9 简单多岔控制转移 416

8.10 简单多岔控制转移的并行处理 419

8.11 多岔控制转移的完备形式 422

8.12 双阶律 424

8.13 完备形式多岔控制转移的结构化变换 427

8.14 GN型计算实例 430

8.15 结构化的多岔控制转移 436

8.16 GNS型计算实例 439

8.17 G型实现算法 442

第九章 离散连通与简洁冗余 455

9.1 离散层次的概念 455

9.2 具有离散层次的A型循环的可并行性质 462

9.3 向I0型循环的拓广 467

9.4 时序层次离散性的判别方法 471

9.5 一类简单的具有离散层次的A型循环 477

9.6 一类简单的具有离散层次的I0型循环 484

9.7 下标表达式单调变化的循环类 492

9.8 下标表达式单调变化的例题 498

9.9 反原形与拟离散性 507

9.10 简洁循环与冗余循环的概念 515

9.11 A型简洁循环与A型冗余循环 518

9.12 同态定理 521

9.13 向I0型循环的拓广 526

9.14 向I1型和G型循环的拓广 531

第十章 分部并行与循环分布 543

10.1 从并行的本质把握分部并行 543

10.2 分部并行的两种手段 545

10.3 循环分布与局部并行 549

10.4 从元素视图考查循环分布 552

10.5 语句团 554

10.6 语句团顺序 558

10.7 语句团的复杂组合 562

10.8 孤立非线性下标“奇异”团 566

10.9 向控制结构的分布 570

10.10 向句内成分的分布 575

10.11 其他“奇异”现象举例 580

第十一章 变序点分割 587

11.1 先分布后分割 587

11.2 变序点概念的精确描述 594

11.3 第一类实变序点 599

11.4 第二类实变序点 601

11.5 第三类实变序点 604

11.6 变序点的重叠 608

11.7 变序点的组合 614

11.8 变序点的萎缩 626

11.9 控制结构的变序点分割 630

11.10 综合实例 636

第十二章 递归分割与并行划分 644

12.1 递归关系及其对并行性的否定 644

12.2 循环中递归的成因 647

12.3 递归的分割 651

12.4 等长递归分割算法 655

12.5 变长的递归分割 661

12.6 完善的关键边组析取算法 666

12.7 全程递归分割算法 670

12.8 片断分割与稳态目标搜索算法 674

12.9 片断递归分割算法 678

12.10 片断递归分割举例 681

12.11 控制结构的递归分割 688

12.12 并行划分中的次序与迭代视图 698

12.13 迭代结点与并行划分举例 700

第十三章 向多重循环的拓广 703

13.1 多重循环的最内层循环 703

13.2 多重A型循环 706

13.3 多重层次片断定理 711

13.4 多重I0型循环 716

13.5 多重I1型和G型循环 723

13.6 多重循环的数组化 726

第十四章 并行死锁的静态检测 731

14.1 预备知识 732

14.2 MPI同步通信死锁检测基本理论 739

14.3 MPI同步通信顺序模型死锁静态检测算法 753

14.4 比例方程组与MPI同步通信静态死锁检测 759

14.5 死锁检测算法实现与基于素数序列的哈希表性能优化 767

14.6 MPI同步通信嵌套循环模型死锁检测 772

14.7 全节点空间MPI同步通信死锁检测 779

14.8 MPICH同步通信程序死锁判定框架性算法 788

14.9 结论 795

附录一从“银河”到“天河” 797

附录二 对范植华并行处理理论与工程成果的专家评价 802

参考文献 809