第一章 并行分布式计算与并行化编译系统 1
1．1 并行分布式计算机系统 1
1．1．1 需要_大型科学与工程计算 1
1．1．2提高计算机系统性能的基本途径 3
1．1．3几种基本的并行结构 4
1．2 并行性与并行计算 8
1．2．1 并行计算举例 8
1．2．2 并行处理 8
1．2．3 并行性 10
1．3 并行分布式程序设计 14
1．3．1 一般程序设计 14
1．3．2 并行分布式程序设计的一般过程 16
1．3．3 并行分布式程序的特点 17
1．3．4 并行程序设计的特殊困难 19
1．3．5 并行程序设计的基本问题与基本途径 20
1．4 并行程序设计语言的一般特性 21
1．4．1 总体设计时必须要考虑的问题 21
1．4．2 并行程序设计语言特性 25
1．5 自动并箸划分与并行化编译 27
1．5．1 自动并行划分的目标与任务 27
1．5．2 并行化编译的基本问题 29
本章小结 31
习题与思考题 32
2．1 并行计算模型与并行语义 34
第二章 并行计算模型 34
2．1．1 转移系统 35
2．1．2 Mazurkiewicz Trace 语言 36
2．1．3 事件结构 38
2．1．4 异步转移系统 42
2．1．5 语义问题 42
2．2 数据驱动（并行计算）模型 43
2．2．1 模型 43
2．2．2 预备知识 44
2．2．3 主要定理 45
2．3．1 并行度及其概示图 51
2．3 并行性的度量 51
2．3．2 调和平均性能 52
2．4 数据驱动模型下的加速比估计式 53
2．4．1 复杂性度量 54
2．4．2 不考虑通信开销时的加速比估计式 54
2．5 考虑通信开销时的加速比估计式 58
2．5．1 模型 58
2．5．2 加速比估计式 58
2．5．3 几点结论 60
本章小结 61
习题与思考题 62
3．1 并行分解概论 63
3．1．1 并行分解问题的提出 63
第三章 程序并行化的一般理论 63
3．1．2 并行性的分级 64
3．1．3 并行分解的困难性 66
3．1．4 并行分解的一般原则 68
3．1．5 经验与启发 71
3．2 图的最优划分 73
3．2．1 数学模型——化为分配问题 73
3．2．2 构造初始分配算法 75
3．2．3 最优分配算法 76
3．2．4 不保证子图连通的划分算法 77
3．2．5 确保子图连通的算法 78
3．2．6 推广 79
3．2．7 实例 80
3．3 相关图的划分 85
3．3．1 问题的提出 85
3．3．2 问题的解决途径 87
3．4 DO—LOOP的并行划分 91
3．4．1 DO—LOOP语句 91
3．4．2 层次相关图 92
3．5 具有约束条件的相关方程的解 97
3．5．1 一维情形 97
3．5．2 多维情形 100
3．5．3 线性函数的上下界 102
3．6．1 强并行划分算法 105
3．6 强并行划分 105
3．6．2 相关区域的确定 106
3．6．3 相关链接图的构造 108
3．6．4 并行划分与程序重构 109
3．6．5 迭代变量可分离情形的DO并行划分 113
3．7 弱并行划分问题与超平面法 116
3．7．1超平面法原理 116
3．7．2 通信费用最小的划分 117
3．8 线性变换法 123
3．8．1数学模型 123
3．8．2静态分解 128
3．9．1 初等变换 136
3．9 循环变换与并行优化 136
3．9．2 么模变换的性质与循环变换 139
3．9．3 特殊情况 143
3．9．4 适当么模变换的存在性 146
3．10 迭代空间的分块 151
3．10．1问题与定义 151
3．10．2实现 152
3．10．3非正方形迭代空间的分块 154
3．11 同态变换法 155
3．11．1理论 156
3．11．2算法 159
3．12 启发式搜索法 166
本章小结 170
习题与思考题 171
第四章 算法映射 173
4．1算法结构与系统结构的匹配 173
4．1．1 问题的提法 173
4．1．2 网络拓扑判别准则 175
4．1．3 常见的几种规则网络拓扑 176
4．2 网络构到超立方结构的映射 180
4．2．1 拓扑映射 180
4．2．2 环映射到超立方结构 181
4．2．3 网映射到超立方结构 182
4．2．4 二维网结构映射的改进方法 183
4．3．1 双根二叉完全树到超立方的映射 187
4．3 树结构到超立方结构的映射 187
4．2．5多维网格情形 187
4．3．2 三叉完全树的映射 190
4．3．3 四叉完全树的映射 192
4．4 任意二叉树到超立结构的映射 195
4．4．1 概念与记号 195
4．4．2 算法描述 197
4．4．3 镜象折叠算法 201
本章小结 206
第五章 程序并行化的实现 209
5．1 程序并行化一般过程 209
5．1．1 引论 209
5．1．2 HZPARA的总体框架 210
5．1．3 HZPARA中相关分析器的结构 212
5．2程序的过程调用图——CALL图 218
5．2．1 基本概念 218
5．2．2 简章CALL图的构造 219
5．2．3 基本CALL图的相关分析 221
5．3 过程作为参数时CALL图的构造 224
5．4 程序的中间表示及其构造 230
5．4．1 基本概念 231
5．4．2 程序PDG图及其构造 234
5．4．3 程序的系统相关图SDG 241
5．5 程序的局部相关分析 242
5．5．1 基本概念和定义 243
5．5．2 程序的局部数据相关分析 244
5．6 程序的全局相关分析 247
5．6．1 过程调和用参数的处理 247
5．6．2 别名变量对的检测与处理 251
5．6．3 程序的全局相关优化 256
5．8 具有分支结构程序的相关分析 270
5．8．1 基本术语——任务流图和相关关系 271
5．8．2 任务的可执行条件 273
5．8．3 算法及实例 279
本章小结 284
习题与思考题 284
6．1 并行操作系统支持概论 287
第六章 并行操作系统支持 287
6．1．1 PARAGON OSF/1的总体结构 288
6．1．2 PARAGON OSF/1的文件系统 290
6．1．3 结点分区的划分与作业调度 290
6．1．4 用户与应用接口 291
6．1．5 PARAGON OSF/1的设计思想和特点 292
6．2 Mach微核设计思想 293
6．2．1 Mach 产生的背景及其设计目标 293
6．2．2 Mach 的主要设计思想 294
6．2．3 Mach 的总体结构 295
6．2．4 处理器管理与分配策略 298
6．2．6 进程通信 299
6．2．5 任务与线程的调度 299
6．2．7 进一步的新发展 301
6．3 超立方结构上的作业调度 302
6．3．1 斟本概念 303
6．3．2 可抢占调度 304
6．3．3 最小完成时间的调度 306
6．3．4 不可抢占调度 309
6．4．1 引论 310
6．4．2 进程动态调度模型与主要问题 311
6．4．3 几种主要负荷平衡策略 314
6．5 HAPARA 进程调度 318
6．5．1 引言 318
6．5．2 进程静态调度模型 319
6．5．3 分配策略 320
6．5．4 分配算法 322
6．5．5 推广到相关驱动图的情形 328
6．5．6 推广到一般拓扑结构的计算机系统 329
6．5．7 应用到动态进程调度策略 329
6．6 映射启发调度 329
本章小结 336
第七章 并行程序设计环境与工具 338
7．1 并行程序设计环境与工具概论 338
7．1．1 各个抽象级并行性的特点与控掘方法 338
7．1．2 并行程序开发过程（生存周期）中的工具环境的一般特点 339
7．1．3 当前商用并行程序设计工具与环境的一般特点 340
7．2 数据分解语言HPF简介 343
7．2．1 HPF设计背影 343
7．2．2 HPF概况 345
7．2．3 数据对准（ALIGN）与分布（DISTRIBUTE）指示 346
7．2．4 数据并行语句与指示 349
7．2．5 展望 351
7．3 性能监控与分析工具 352
7．3．1 Paraide的总体结构 352
7．3．2 Paraide的设计思想 354
7．4 并行程序设计方法展望 356
本章小结 358
参考文献 359