串行算法并行化基础

第0章 绪论

0.1 计算科学

0.2 为什么要并行计算

0.3 巨型机、高性能计算机本质特征：并行计算

0.4 巨型机、高性能计算机基本矛盾：台数与计算效率的矛盾

0.5 并行运算和并行数据传送

0.6 并行执行方式和重叠执行方式

0.7 并行算法与串行算法并行化

0.8 巨型机、高性能计算机的关键技术

0.9 数据相关和控制相关

第1章 串行算法并行化的基本概念

1.1 题目的规模与计算工作量N

1.2 题目的计算时间T

1.3 题目最快串行计算算法C0

1.4 题目在并行计算模型M（S）下并行计算算法B

1.5 题目在M（S）下并行计算算法B的计算速度：Vb，M（s）（N）

1.6 在并行计算模型M（S）下题目并行计算算法B的加速比

1.7 在并行计算模型M（S）下题目并行计算算法B的效率

1.8 并行算法B的计算复杂性

1.9 常数效率并行算法

1.10 在某些讨论中的算法分类

1.11 并行计算台数S对并行计算速度的影响及串行算法并行化的意义

第2章 执行并行计算算法的并行计算机系统结构模型

2.1 并行算法实现的两要素之一：并行传送

2.2 单指令流一单数据流（SIMD）计算机

2.3 SIMD二维阵列机

2.4 流水线向量机

2.5 第二代巨型机：纵横加工（分段处理）流水线向量机

2.6 细胞结构化虚共存纵横加工向量机

2.7 多维立方体机

2.8 多指令流一多数据流系统MIMD

2.9 内部互联网络

2.10 通用或专用计算网络

2.11 PRAM并行随机访问计算机

2.12 可变总线结构

2.13 素数存储系统

2.14 分段线性变换存储系统

第3章 向量语言

3.1 数据类型与数据结构

3.2 向量基本运算

3.3 向量或者数组中的向量

3.4 可以用硬件实现的控制向量

3.5 变长向量运算

3.6 向量语言的扩充

3.7 向量高级语言

第4章 串行算法并行化方法综述与比较

4.1 串行算法并行化之一：多分法方法

4.2 串行算法并行化之二：倍增法

4.3 串行算法并行化之三：纵横加工法

4.4 串行算法并行化效率比较

4.5 串行算法并行化之四：利用软件、硬件和软件硬件结合的优化方法

4.6 串行算法并行化之五：利用硬件直接实现的控制向量一

第5章 两路归并与分类串行算法并行化

5.1 归并与排序的快速串行算法

5.2 归并基本定义与定理

5.3 K E Batcher的Odd-even并行归并网络

5.4 根据归并基本定理所构造的快速并行归并算法

5.5 K E Batcher的Bitonic归并算法

5.6 利用并行归并来实现并行排序

5.7 归并与排序串行算法并行化的OPTIMAL并行算法之一：纵横并行归并算法

5.8 归并与分类串行算法并行化的OPTIMAL并行算法之二：k-维并行归并算法

5.9 在理论模型上的排序

第6章 多路归并串行算法并行化

第7章 一类一阶递推串行算法并行化

第8章 一类广函数：纵橫矩加工广函数

附录 （m,N）选择问题的纵横并行算法例子

参考文献

《串行算法并行化基础》第1章首先介绍这些有关串行算法并行化基本概念。并行计算是在一定的并行计算系统的类型上实现的，所以第2章介绍一些基本并行计算系统类型。多指令流多数据流巨型机是当今高性能计算机系统的主流，许多大部头的书都有详细论述，本专著就不重复。单指令流多数据流巨型机是20世纪60年代末到80年代并行计算的高性能计算机系统的主流，其中许多设计思路在当今仍然不失其价值。它们很容易使用的原因是对应的并行计算模式可以规范到十分自然的向量运算形式，即有一个理想的描述语言：向量语言。第3章就介绍一种向量语言。多指令流多数据流巨型机的并行计算模式目前难于规范到十分自然的运算形式，也就是尚不存在一个理想的描述语言。通过向量语言的了解，或许有助于今后多指令流多数据流高性能计算机系统理想的描述语言的诞生。第4章介绍串行算法并行化的各种类型。第5章到第7章介绍具体的、典型的串行算法的并行化，包括两路归并、多路归并、排序和广义一阶递推。最后一章（第8章）介绍一类广函数一一纵横矩阵加工广数。
引入并行是为了提高计算速度，到底能不能有效提高计算速度？如何度量计算速度的提高及其有效性？这些需要通过一些基本概念来刻画。