并行性分析的数学原理

总序

序

第一章 硬件并行设施

1.1 计算机并行性的发展

1.2 流水线并行原理

1.3 多向量流水

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

1.5 阵列与数据流方式

1.6 多核芯片

1.7 紧耦合多处理机

1.8 松耦合多计算机

1.9 集群

1.10 单体巨型机

1.11 复体巨型机

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

1.13 云计算平台

第二章 语言并行机制

2.1 VFoRTRAN语言

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

2.3 向量函数

2.4 向量过程

2.5 流水线处理

2.6 向量链接

2.7 向量屏蔽

2.8 数组运算

2.9 PFoRTRAN语言

2.10 HPF语言

2.11 BXC语言

2.12 时序算子

2.13 控制结构

2.14 点对点通信

2.15 并行程序设计

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

3.1 并行处理的三种粒度

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

3.3 单层赋值循环的适应性

3.4 临时变量与归纳变量

3.5 三种赋值与限制条件

3.6 繁衍层次

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

3.8 元素间的优先关系

3.9 数据相关与输人相关

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

4.1 语句问的相关依赖

4.2 语句图与并行性判别

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

4.4 变序点

4.5 A0型循环的层次片断

4.6 计算实例

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

4.8 循环体的最简形式

4.9 指令级的并行性

4.10 加权汇编语句图

第五章 变量视图

5.1 坐标方法

5.2 超平面方法

5.3 相关分析方法

5.4 图论方法

5.5 统一的解析判别法

5.6 拓扑排序

5.7 临时数组与暂存语句

5.8 改写算法

第六章 元素视图

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

6.2 有待跨越的“鸿沟”

6.3 判别准则

6.4 判别举例

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

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

6.7 结点的数学抽象

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

6.9 生存带的胀缩

6.10 包含关系的数学表示

6.11 强化定理

6.12 偏序结构

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

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

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

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

7.1 不定因素与参数集

7.2 10型循环及其闭体

7.3 10型循环的并行处理

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

7.5 再识别算法

7.6 再改写算法

7.7 优化算法

7.8 识别改写优化链

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

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

8.1 简单三岔控制转移

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

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

8.4 （t1，t2，m，t3，n>型组合方式的嵌入载体

8.5 （t1，t2，t3，m，n>型组合方式的嵌入载体

8.6 （t1，t2，t3，n，m）型组合方式的嵌入载体

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

8.8 退化情形

8.9 简单多岔控制转移

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

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

8.12 双阶律

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

8.14 GN型计算实例

8.15 结构化的多岔控制转移

8.16 GNs型计算实例

8.17 G型实现算法

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

9.1 离散层次的概念

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

9.3 向10型循环的拓广

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

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

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

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

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

9.9 反原形与拟离散性

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

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

9.12 同态定理

9.13 向10型循环的拓广

9.14 向11型和G型循环的拓广

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

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

10.2 分部并行的两种手段

10.3 循环分布与局部并行

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

10.5 语句团

10.6 语句团顺序

10.7 语句团的复杂组合

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

10.9 向控制结构的分布

10.10 向句内成分的分布

10.11 其他“奇异”现象举例

第十一章 变序点分割

11.1 先分布后分割

11.2 变序点概念的精确描述

11.3 第一类实变序点·

11.4 第二类实变序点

11.5 第三类实变序点

11.6 变序点的重叠

11.7 变序点的组合

11.8 变序点的萎缩

11.9 控制结构的变序点分割

11.10 综合实例

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

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

12.2 循环中递归的成因

12.3 递归的分割

12.4 等长递归分割算法

12.5 变长的递归分割

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

12.7 全程递归分割算法

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

12.9 片断递归分割算法

12.10 片断递归分割举例

12.11 控制结构的递归分割

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

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

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

13.1 多重循环的最内层循环

13.2 多重A型循环

13.3 多重层次片断定理

13.4 多重10型循环

13.5 多重11型和G型循环

13.6 多重循环的数组化

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

14.1 预备知识

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

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

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

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

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

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

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

14.9 结论

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

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

参考文献

《中国科学技术大学校友文库：并行性分析的数学原理》既是计算机工程技术领域的理论专著，又是用抽象数学解决工程技术实际问题的应用专著。它囊括了（微积分学开创、由微分方程和复变函数等继承与发展的）精确思维与（概率论与数理统计和信息论开创、由模糊数学等发扬光大的）不精确思维，并包括“纯粹”数学中近世代数在内的几十门数学分支，运用于应超级电脑之运而生的并行处理这一工程技术前沿，获得巨大的成功。其内容基本按“公理一定义一引理一定理一证明一推论一应用”的数学演绎体系编写，以满足关系国计民生的高科技所要求的正确性与可靠性；它也是作者近半个世纪跨应用数学与计算机科学两大专业方向科研成果的结晶，由于透彻地把握住了本质，有能力深入浅出地展现给读者。
　　全书共14章，内容几乎穷尽硬件，语言，以及语句、变量、元素、指令、迭代等五大相关视图，以及离散与简洁、分割与分布、并行死锁等并行处理软件涉及的所有方面。
　　《中国科学技术大学校友文库：并行性分析的数学原理》可供计算机科技工作者、大专院校师生，特别是有志于把抽象数学与工程技术相结合的科研人员阅读。