可扩展并行算法的设计与分析PDF|Epub|txt|kindle电子书版本网盘下载

可扩展并行算法的设计与分析PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

Chapter 1 Introduction1

第1章 并行计算机1

1．1．1 SISD computers2

1．1．2 SIMD parallel computers2

1．1 Classification of parallel computers2

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 multiprocessor3

1．1．4 Distributed memory MIMD parallel multiprocessor4

1．1．4 分布存储MIMD并行多处理机4

1．1．5 分布共享存储MIMD并行机5

1．1．5 Distributed Shared memory MIMD parallel computers5

1．2 并行计算机的发展6

1．2．1 Push of applications demand6

1．2 Development of parallel computers6

1．2．1 应用需求的推动作用6

1．2．4 80年代中期7

1．2．3 80年代早期7

1．2．4 In middle 1980s7

1．2．3 In early 1980s7

1．2．2 In 1970s7

1．2．2 70年代7

1．2．6 90年代早期8

1．2．5 In later 1980s8

1．2．6 In early 1990s8

1．2．5 80年代后期8

1．2．7 From middle 1990 to now9

1．2．7 90年代中期至今9

1．3．1 Vector procedure design11

1．3 Parallel procedure design11

1．3．1 向量程序设计11

1．3 并行程序设计11

1．3．2 共享存储并行程序设计12

1．3．2 Parallel procedure design under Shared memory12

1．3．3 数据并行程序设计13

1．3．3 Parallel procedure design based on data13

1．3．4 消息传递并行程序设计14

1．3．4 Parallel procedure design based on message passing14

1．4 Classification of parallel algorithms15

1．4 并行算法的分类15

1．5 并行算法的发展16

1．5 Development of parallel algorithms16

第2章 并行计算模型17

2．1 计算模型位置与准则17

2．1 Pole rules of parallel computing models17

Chapter 2 Parallel Computing Models17

2．2．1 SIMD-PRAM model18

2．2．1 SIMD-PRAM模型18

2．2 PRAM模型18

2．2 PRAM model18

2．2．2 MIMD-PRAM model19

2．2．2 MIMD-PRAM模型19

2．2．3 Characteristics of PRAM model20

2．3 H-PRAM model20

2．3 H-PRAM模型20

2．2．3 PRAM模型的特点20

2．4 LogP模型22

2．4 LogP model22

2．5 C3模型23

2．5 C3 model23

2．6 BDM模型24

2．7 Comparison of five models24

2．7 5种模型比较24

2．6 BDM model24

3．1．1 并行算法的运行时间27

3．1 Some concepts and performance parameters27

3．1．1 Runtime of parallel algorithms27

第3章 并行算法性能度量27

3．1 若干概念与性能参数27

Chapter 3 Performance Evaluation for Parallel algorithms27

3．1．2 Scale and classification of problems28

3．1．2 问题的规模与分类28

3．1．3 Scale of parallel computers29

3．1．4 Parallelism and granularity29

3．1．3 并行机规模29

3．1．4 并行度与粒度29

3．2 并行算法运行时间模型30

3．2 Runtime model for parallel algorithms30

3．1．5 加速比与效率30

3．1．5 Speedup and efficiency30

3．2．1 共享存储环境下的运行时间模型31

3．2．1 Runtime model under shared memory environments31

3．2．2 Runtime model under distributed memory environments32

3．2．2 分布式存储环境下的运行时间模型32

3．3．2 Performance evaluation criterions under distributed memory environments37

3．3 Performance evaluation rules for parallel algorithms37

3．3．1 Performance evaluation criterions under shared memory environments37

3．3．1 共享存储环境下的性能评价准则37

3．3 并行算法性能评价准则37

3．3．2 分布式存储环境下的性能评价准则37

第4章 并行算法可扩展性分析40

Chapter 4 Scalability Analysis of Parallel Algorithms40

4．1．1 Definition of scalability42

4．1 Definition,parameter and prime characteristics of scalability42

4．1．1 可扩展性定义42

4．1 可扩展性定义、指标和基本特征42

4．1．2 Parameters and characterization of parallel system scalability43

4．1．2 并行系统可扩展性指标及其基本特征43

4．1．3 并行算法及其实现的可扩展性44

4．1．3 Scalability of parallel algorithm and its implementation44

4．2．1 并行算法可扩展性的等效率度量方法45

4．2 常用的可扩展性度量方法45

4．1．4 并行算法——体系结构组合可扩展性45

4．2．1 Iso-efficiency method to parallel algorithms45

4．2 Normal measure methods to scalability45

4．1．4 Scalabi Lity of parallel algorithms-architecture conbinations45

4．2．2 并行算法——机器组合的等速度度量方法46

4．2．2 Iso-speedup method to combinations of parallel algorithm-machine46

4．2．3 并行算法——体系结构的等计算时间/通信开销比率度量方法47

4．2．3 Iso-ratio(Computing time/Communication overhead)method to parallel algorithm-architecture47

4．3 Some practical examples for scalability analysis48

4．3．1 矩阵乘并行算法可扩展性分析48

4．3 实用例子可扩展性分析48

4．3．1 Scalability analysis of parallel algorithms for matrix multiply48

4．3．2 Scalability analysis of combinations of Narier-Stokes partial differential equations paralle50

4．3．2 Navier-Stokes偏微分方程组并行算法与YH-3组合的可扩展性分析50

Chapter 5 Parallel Computing on Linear Algebra Equations53

第5章 线性代数方程组的并行计算53

5．1．1 Michielse Vorst算法54

5．1 Direct solutions to tridiagonal linear algebra equations54

5．1．1 Michielse Vorst algorithm54

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 equations56

5．1．4 Direct solutions to period tridiagonal linear algebra equations61

5．1．4 周期三对角线性方程组的直接解法61

5．2．1 Krylov subspace iteration method64

5．2 Krylov subspace iteration method for solving sparse linear equation64

5．2．1 Krylov子空间迭代法64

5．2 求解稀疏线性方程组的Krylov子空间迭代法64

5．2．2 预条件技术67

5．2．3 Krylov子空间迭代法的并行计算67

5．2．2 Preconditioning technology67

5．2．3 Parallel Computing on Krylov subspace iteration method67

5．3．1 Development of linear algebra software70

5．3．1 线性代数软件的发展70

5．3 Briefintroduction to ScaLAPACK and solving generic linear equations70

5．3 ScaLAPACK简介及一般线性方程组求解70

5．3．2 Data layout and distribution in ScaLAPACK71

5．3．3 LU分解的并行计算与实现71

5．3．2 ScaLAPACK的数据布局与分布71

5．3．3 Parallel computing and implementation of decomposition71

6．1．1 Divide-and-conquer algorithm75

6．1 Parallel computing on symmetric tridiagonal matrix eigenvalue proplem75

6．1．1 分而治之算法75

6．1 对称三对角特征值矩阵特征值问题的并行计算75

第6章 特征值与特征值向量的并行计算75

Chapter 6 Parallel computing on eigenvalues and eigenvectors75

6．1．2 Homotopy algorithm79

6．1．2 同伦连续算法79

6．2．1 二分法及其改进81

6．2 对称带状矩阵特征值问题的并行计算81

6．2．1 Bisection method and its modification81

6．2 Parallel computing on symmetric band matrix eigenvalue proplem81

6．2．2 Divide-and-conquer algorithm based on bisection method83

6．2．2 基于二分迭代的分而治之算法83

6．3 Parallel computing on nonsymmetric matrix eigenvalue problem88

6．3 非对称矩阵特征值问题的并行计算88

6．3．1 Divide-and-conquer algorithm88

6．3．1 分而治之算法88

6．3．2 Spectral decomposition algorithm92

6．3．2 谱分解算法92

6．4 Scalability analysis of algorithm94

6．4 算法可扩展性分析94

第7章 多重网格与区域分解算法的并行计算96

Chapter 7 Parallel Computing on Multigrids and Domain Decomposition96

7．1．1 Prime principle of algorithm97

7．1．1 算法原理97

7．1 Parallel computing on multigrids algorithm97

7．1 多重网格算法的并行计算97

7．1．2 简单应用规则100

7．1．2 Simple rules of application100

7．1．3 内在并行度101

7．1．3 Intrinsic parallelism101

7．1．4 Grids partitioning and communication structure102

7．1．4 网格划分与通信结构102

7．1．5 可扩展分析103

7．1．5 Scalability analysis103

7．1．6 算法并行的内在瓶颈106

7．1．6 Intrinsic bottleneck of parallel algorithm106

7．1．7 Algorithm improving107

7．1．7 算法改进107

7．2 两层加性Schwarz区域分解算法的并行计算108

7．2 Parallel Computing on double-level Schwarz domain decomposition108

7．2．1 算法原理109

7．2．1 Prime principle of algorithm109

7．2．2 并行实现与数值实验110

7．2．2 Parallel implementation and numerical tests110

7．2．3 Scalability analysis111

7．2．3 可扩展分析111

Chapter 8 Parallel Computing on Discrete Transforms and Discrete Convolutions112

8．1 Parallel algorithm for one dimensional DFT112

第8章 离散变换与离散卷积的并行算法112

8．1 一维DFT的并行算法112

8．1．1 Parallel fast FFT113

8．1．1 并行快速傅里叶变换113

8．1．2 一维DFT的分裂并行算法116

8．1．2 Decomposition parallel algorithm for one dimensional DFT116

8．1．3 实序列DFT的计算117

8．1．3 Computing real serial DFT117

8．2．1 并行行列算法118

8．2．1 Parallel row-column algorithm118

8．2 Parallel algorithm for two dimensional DFT and multiple dimensional DFT118

8．2 二维及多维DFT的并行算法118

8．2．2 并行矩阵转置119

8．2．2 Parallel matrix reverse119

8．2．3 通信和计算的重叠120

8．2．3 Overlapping communication and computing120

8．2．4 多维实序列DFT的计算121

8．2．4 Computing multiple real serial DFT121

8．3．1 并行多项式变换122

8．3 并行多项式变换算法122

8．3 Parallel polynomial transforms algorithm122

8．3．1 Parallel polynomial transforms122

8．3．2 DFT的并行多项式变换算法123

8．3．2 Parallel polynomial transforms algorithm of DFT123

8．4．1 用DFT计算DCT126

8．4 离散余弦变换的并行算法126

8．4．1 Computing DCT with DFT126

8．4 Parallel computing discrete cosine transform126

8．4．2 Parallel computing two dimensional discrete cosine transform127

8．4．2 二维离散余弦变换的并行算法127

8．5 Parallel algorithm for discrete W transform128

8．5．1 用DFT计算DWT128

8．5．1 Computing DWT with DFT128

8．5 离散W变换的并行算法128

8．5．2 多维DWT的并行多项式变换算法129

8．5．2 Parallel polynomial transforms algorithm of multiple dimensional DWT129

8．6 离散卷积的计算132

8．6 Computing discrete convolution132

Chapter 9 Wavelet analysis its parallel algorithms135

第9章 小波分析的并行算法135

9．1 小波变换导论135

9．1．1 连续小波变换135

9．1 Introduction to wavelet transform135

9．1．1 Continuous wavelet transform135

9．1．2 小波级数136

9．1．2 Wavelet series136

9．1．3 多尺度分析和离散小波变换137

9．1．3 Multiple measure analysis and discrete Wavelet transform137

9．1．4 Multiple measure analysis and Mallat algorithm of high dimension139

9．1．4 高维多尺度分析和Mallat算法139

9．2 Computing function value of wavelet141

9．1．5 Wavelet pack transform141

9．2 小波函数值的计算141

9．1．5 小波包变换141

9．2．1 Iteration algorithm142

9．2．1 迭代方法142

9．2．2 逐点方法143

9．2．2 Point-by-point algorithm143

9．3 小波变换的并行计算145

9．2．3 高维小波函数的计算145

9．2．3 Computing high dimension Wavelet function145

9．3 Parallel computing Wavelet transform145

9．3．1 Period discrete Wavelet transform146

9．3．1 周期离散小波变换146

9．3．2 Parallel computing discrete Wavelet transform147

9．3．2 离散小波变换的并行算法147

9．3．3 FFT method to discrete Wavelet transform151

9．3．3 离散小波变换计算的傅里叶变换方法151

9．3．4 Computing Wavelet series and continuous Wavelet transform152

9．3．4 小波级数和连续小波变换的计算152

9．4 Parallel algorithm for selecting optimal base of Wavelet pack153

9．4．1 Wavelet pack and optimal base153

9．4．1 小波包和最优基153

9．4 小波包最优基选取的并行算法153

9．4．2 Parallel Wavelet pack decomposition and optimal base selection154

9．4．2 并行小波包分解和最优基选取154

9．5 Scalability analysis of discrete Wavelet transform algorithm155

9．5 离散小波变换算法的可扩展性分析155

Chapter 10 Practical Examples for Parallel Procedure under Distributed Memory Environments157

10．1．1 Portable heterogeneous Programming environment PVM157

10．1 message passing environments157

10．1．1 可移植的异构编程环境PVM157

10．1 消息传递环境157

第10章 分布式存储环境下并行程序实例157

10．1．2 Message Passing standard platform MPI158

10．1．2 消息传递标准平台MPI158

10．2 Examples for PVM procedures159

10．2．1 矩阵乘积PVM程序159

10．2．1 Matrix multiply159

10．2 PVM应用程序实例159

10．2．2 Parallel procedure for solving matrix eigenvalue problem164

10．2．2 对称矩阵特征值问题并行求解PVM程序164

References183

参考文献183