Chapter 1 Introduction 1
第1章 并行计算机 1
1．1．1 SISD computers 2
1．1．2 SIMD parallel computers 2
1．1 Classification of parallel computers 2
1．1．2 SIMD型并行机 2
1．1 并行计算机的分类 2
1．1．1 SISD型计算机 2
1．1．3 共享存储MIMD并行多处理机 3
1．1．3 Shared memory MIMD parallel multiprocessor 3
1．1．4 Distributed memory MIMD parallel multiprocessor 4
1．1．4 分布存储MIMD并行多处理机 4
1．1．5 分布共享存储MIMD并行机 5
1．1．5 Distributed Shared memory MIMD parallel computers 5
1．2 并行计算机的发展 6
1．2．1 Push of applications demand 6
1．2 Development of parallel computers 6
1．2．1 应用需求的推动作用 6
1．2．4 80年代中期 7
1．2．3 80年代早期 7
1．2．4 In middle 1980s 7
1．2．3 In early 1980s 7
1．2．2 In 1970s 7
1．2．2 70年代 7
1．2．6 90年代早期 8
1．2．5 In later 1980s 8
1．2．6 In early 1990s 8
1．2．5 80年代后期 8
1．2．7 From middle 1990 to now 9
1．2．7 90年代中期至今 9
1．3．1 Vector procedure design 11
1．3 Parallel procedure design 11
1．3．1 向量程序设计 11
1．3 并行程序设计 11
1．3．2 共享存储并行程序设计 12
1．3．2 Parallel procedure design under Shared memory 12
1．3．3 数据并行程序设计 13
1．3．3 Parallel procedure design based on data 13
1．3．4 消息传递并行程序设计 14
1．3．4 Parallel procedure design based on message passing 14
1．4 Classification of parallel algorithms 15
1．4 并行算法的分类 15
1．5 并行算法的发展 16
1．5 Development of parallel algorithms 16
第2章 并行计算模型 17
2．1 计算模型位置与准则 17
2．1 Pole rules of parallel computing models 17
Chapter 2 Parallel Computing Models 17
2．2．1 SIMD-PRAM model 18
2．2．1 SIMD-PRAM模型 18
2．2 PRAM模型 18
2．2 PRAM model 18
2．2．2 MIMD-PRAM model 19
2．2．2 MIMD-PRAM模型 19
2．2．3 Characteristics of PRAM model 20
2．3 H-PRAM model 20
2．3 H-PRAM模型 20
2．2．3 PRAM模型的特点 20
2．4 LogP模型 22
2．4 LogP model 22
2．5 C3模型 23
2．5 C3 model 23
2．6 BDM模型 24
2．7 Comparison of five models 24
2．7 5种模型比较 24
2．6 BDM model 24
3．1．1 并行算法的运行时间 27
3．1 Some concepts and performance parameters 27
3．1．1 Runtime of parallel algorithms 27
第3章 并行算法性能度量 27
3．1 若干概念与性能参数 27
Chapter 3 Performance Evaluation for Parallel algorithms 27
3．1．2 Scale and classification of problems 28
3．1．2 问题的规模与分类 28
3．1．3 Scale of parallel computers 29
3．1．4 Parallelism and granularity 29
3．1．3 并行机规模 29
3．1．4 并行度与粒度 29
3．2 并行算法运行时间模型 30
3．2 Runtime model for parallel algorithms 30
3．1．5 加速比与效率 30
3．1．5 Speedup and efficiency 30
3．2．1 共享存储环境下的运行时间模型 31
3．2．1 Runtime model under shared memory environments 31
3．2．2 Runtime model under distributed memory environments 32
3．2．2 分布式存储环境下的运行时间模型 32
3．3．2 Performance evaluation criterions under distributed memory environments 37
3．3 Performance evaluation rules for parallel algorithms 37
3．3．1 Performance evaluation criterions under shared memory environments 37
3．3．1 共享存储环境下的性能评价准则 37
3．3 并行算法性能评价准则 37
3．3．2 分布式存储环境下的性能评价准则 37
第4章 并行算法可扩展性分析 40
Chapter 4 Scalability Analysis of Parallel Algorithms 40
4．1．1 Definition of scalability 42
4．1 Definition,parameter and prime characteristics of scalability 42
4．1．1 可扩展性定义 42
4．1 可扩展性定义、指标和基本特征 42
4．1．2 Parameters and characterization of parallel system scalability 43
4．1．2 并行系统可扩展性指标及其基本特征 43
4．1．3 并行算法及其实现的可扩展性 44
4．1．3 Scalability of parallel algorithm and its implementation 44
4．2．1 并行算法可扩展性的等效率度量方法 45
4．2 常用的可扩展性度量方法 45
4．1．4 并行算法——体系结构组合可扩展性 45
4．2．1 Iso-efficiency method to parallel algorithms 45
4．2 Normal measure methods to scalability 45
4．1．4 Scalabi Lity of parallel algorithms-architecture conbinations 45
4．2．2 并行算法——机器组合的等速度度量方法 46
4．2．2 Iso-speedup method to combinations of parallel algorithm-machine 46
4．2．3 并行算法——体系结构的等计算时间/通信开销比率度量方法 47
4．2．3 Iso-ratio(Computing time/Communication overhead)method to parallel algorithm-architecture 47
4．3 Some practical examples for scalability analysis 48
4．3．1 矩阵乘并行算法可扩展性分析 48
4．3 实用例子可扩展性分析 48
4．3．1 Scalability analysis of parallel algorithms for matrix multiply 48
4．3．2 Scalability analysis of combinations of Narier-Stokes partial differential equations paralle 50
4．3．2 Navier-Stokes偏微分方程组并行算法与YH-3组合的可扩展性分析 50
Chapter 5 Parallel Computing on Linear Algebra Equations 53
第5章 线性代数方程组的并行计算 53
5．1．1 Michielse Vorst算法 54
5．1 Direct solutions to tridiagonal linear algebra equations 54
5．1．1 Michielse Vorst algorithm 54
5．1 三对角线性方程组的直接解法 54
5．1．2 Double-direction parallel decomposition algorithm（DPP algorithm） 55
5．1．2 双向并行分裂算法（DPP算法） 55
5．1．3 对角占优三对角线性方程组的并行算法（PPD算法） 56
5．1．3 Parallel algorithms for diagonal dominant tridiagonal linear algebra equations 56
5．1．4 Direct solutions to period tridiagonal linear algebra equations 61
5．1．4 周期三对角线性方程组的直接解法 61
5．2．1 Krylov subspace iteration method 64
5．2 Krylov subspace iteration method for solving sparse linear equation 64
5．2．1 Krylov子空间迭代法 64
5．2 求解稀疏线性方程组的Krylov子空间迭代法 64
5．2．2 预条件技术 67
5．2．3 Krylov子空间迭代法的并行计算 67
5．2．2 Preconditioning technology 67
5．2．3 Parallel Computing on Krylov subspace iteration method 67
5．3．1 Development of linear algebra software 70
5．3．1 线性代数软件的发展 70
5．3 Briefintroduction to ScaLAPACK and solving generic linear equations 70
5．3 ScaLAPACK简介及一般线性方程组求解 70
5．3．2 Data layout and distribution in ScaLAPACK 71
5．3．3 LU分解的并行计算与实现 71
5．3．2 ScaLAPACK的数据布局与分布 71
5．3．3 Parallel computing and implementation of decomposition 71
6．1．1 Divide-and-conquer algorithm 75
6．1 Parallel computing on symmetric tridiagonal matrix eigenvalue proplem 75
6．1．1 分而治之算法 75
6．1 对称三对角特征值矩阵特征值问题的并行计算 75
第6章 特征值与特征值向量的并行计算 75
Chapter 6 Parallel computing on eigenvalues and eigenvectors 75
6．1．2 Homotopy algorithm 79
6．1．2 同伦连续算法 79
6．2．1 二分法及其改进 81
6．2 对称带状矩阵特征值问题的并行计算 81
6．2．1 Bisection method and its modification 81
6．2 Parallel computing on symmetric band matrix eigenvalue proplem 81
6．2．2 Divide-and-conquer algorithm based on bisection method 83
6．2．2 基于二分迭代的分而治之算法 83
6．3 Parallel computing on nonsymmetric matrix eigenvalue problem 88
6．3 非对称矩阵特征值问题的并行计算 88
6．3．1 Divide-and-conquer algorithm 88
6．3．1 分而治之算法 88
6．3．2 Spectral decomposition algorithm 92
6．3．2 谱分解算法 92
6．4 Scalability analysis of algorithm 94
6．4 算法可扩展性分析 94
第7章 多重网格与区域分解算法的并行计算 96
Chapter 7 Parallel Computing on Multigrids and Domain Decomposition 96
7．1．1 Prime principle of algorithm 97
7．1．1 算法原理 97
7．1 Parallel computing on multigrids algorithm 97
7．1 多重网格算法的并行计算 97
7．1．2 简单应用规则 100
7．1．2 Simple rules of application 100
7．1．3 内在并行度 101
7．1．3 Intrinsic parallelism 101
7．1．4 Grids partitioning and communication structure 102
7．1．4 网格划分与通信结构 102
7．1．5 可扩展分析 103
7．1．5 Scalability analysis 103
7．1．6 算法并行的内在瓶颈 106
7．1．6 Intrinsic bottleneck of parallel algorithm 106
7．1．7 Algorithm improving 107
7．1．7 算法改进 107
7．2 两层加性Schwarz区域分解算法的并行计算 108
7．2 Parallel Computing on double-level Schwarz domain decomposition 108
7．2．1 算法原理 109
7．2．1 Prime principle of algorithm 109
7．2．2 并行实现与数值实验 110
7．2．2 Parallel implementation and numerical tests 110
7．2．3 Scalability analysis 111
7．2．3 可扩展分析 111
Chapter 8 Parallel Computing on Discrete Transforms and Discrete Convolutions 112
8．1 Parallel algorithm for one dimensional DFT 112
第8章 离散变换与离散卷积的并行算法 112
8．1 一维DFT的并行算法 112
8．1．1 Parallel fast FFT 113
8．1．1 并行快速傅里叶变换 113
8．1．2 一维DFT的分裂并行算法 116
8．1．2 Decomposition parallel algorithm for one dimensional DFT 116
8．1．3 实序列DFT的计算 117
8．1．3 Computing real serial DFT 117
8．2．1 并行行列算法 118
8．2．1 Parallel row-column algorithm 118
8．2 Parallel algorithm for two dimensional DFT and multiple dimensional DFT 118
8．2 二维及多维DFT的并行算法 118
8．2．2 并行矩阵转置 119
8．2．2 Parallel matrix reverse 119
8．2．3 通信和计算的重叠 120
8．2．3 Overlapping communication and computing 120
8．2．4 多维实序列DFT的计算 121
8．2．4 Computing multiple real serial DFT 121
8．3．1 并行多项式变换 122
8．3 并行多项式变换算法 122
8．3 Parallel polynomial transforms algorithm 122
8．3．1 Parallel polynomial transforms 122
8．3．2 DFT的并行多项式变换算法 123
8．3．2 Parallel polynomial transforms algorithm of DFT 123
8．4．1 用DFT计算DCT 126
8．4 离散余弦变换的并行算法 126
8．4．1 Computing DCT with DFT 126
8．4 Parallel computing discrete cosine transform 126
8．4．2 Parallel computing two dimensional discrete cosine transform 127
8．4．2 二维离散余弦变换的并行算法 127
8．5 Parallel algorithm for discrete W transform 128
8．5．1 用DFT计算DWT 128
8．5．1 Computing DWT with DFT 128
8．5 离散W变换的并行算法 128
8．5．2 多维DWT的并行多项式变换算法 129
8．5．2 Parallel polynomial transforms algorithm of multiple dimensional DWT 129
8．6 离散卷积的计算 132
8．6 Computing discrete convolution 132
Chapter 9 Wavelet analysis its parallel algorithms 135
第9章 小波分析的并行算法 135
9．1 小波变换导论 135
9．1．1 连续小波变换 135
9．1 Introduction to wavelet transform 135
9．1．1 Continuous wavelet transform 135
9．1．2 小波级数 136
9．1．2 Wavelet series 136
9．1．3 多尺度分析和离散小波变换 137
9．1．3 Multiple measure analysis and discrete Wavelet transform 137
9．1．4 Multiple measure analysis and Mallat algorithm of high dimension 139
9．1．4 高维多尺度分析和Mallat算法 139
9．2 Computing function value of wavelet 141
9．1．5 Wavelet pack transform 141
9．2 小波函数值的计算 141
9．1．5 小波包变换 141
9．2．1 Iteration algorithm 142
9．2．1 迭代方法 142
9．2．2 逐点方法 143
9．2．2 Point-by-point algorithm 143
9．3 小波变换的并行计算 145
9．2．3 高维小波函数的计算 145
9．2．3 Computing high dimension Wavelet function 145
9．3 Parallel computing Wavelet transform 145
9．3．1 Period discrete Wavelet transform 146
9．3．1 周期离散小波变换 146
9．3．2 Parallel computing discrete Wavelet transform 147
9．3．2 离散小波变换的并行算法 147
9．3．3 FFT method to discrete Wavelet transform 151
9．3．3 离散小波变换计算的傅里叶变换方法 151
9．3．4 Computing Wavelet series and continuous Wavelet transform 152
9．3．4 小波级数和连续小波变换的计算 152
9．4 Parallel algorithm for selecting optimal base of Wavelet pack 153
9．4．1 Wavelet pack and optimal base 153
9．4．1 小波包和最优基 153
9．4 小波包最优基选取的并行算法 153
9．4．2 Parallel Wavelet pack decomposition and optimal base selection 154
9．4．2 并行小波包分解和最优基选取 154
9．5 Scalability analysis of discrete Wavelet transform algorithm 155
9．5 离散小波变换算法的可扩展性分析 155
Chapter 10 Practical Examples for Parallel Procedure under Distributed Memory Environments 157
10．1．1 Portable heterogeneous Programming environment PVM 157
10．1 message passing environments 157
10．1．1 可移植的异构编程环境PVM 157
10．1 消息传递环境 157
第10章 分布式存储环境下并行程序实例 157
10．1．2 Message Passing standard platform MPI 158
10．1．2 消息传递标准平台MPI 158
10．2 Examples for PVM procedures 159
10．2．1 矩阵乘积PVM程序 159
10．2．1 Matrix multiply 159
10．2 PVM应用程序实例 159
10．2．2 Parallel procedure for solving matrix eigenvalue problem 164
10．2．2 对称矩阵特征值问题并行求解PVM程序 164
References 183
参考文献 183