《并行算法的设计与分析》求取 ⇩

前言1

第一章导论1

1.1 并行计算机的体系结构及分类1

1.1.1 并行处理系统发展谱1

1.1.2 并行计算机的分类2

1.1.3 处理器互连网络3

1.2 并行计算模型9

1.2.1 SIMD互连网络模型9

1.2.2 SIMD共享存储模型10

1.2.3 MIMD共享存储模型11

1.2.4 MIMD异步通信模型11

1.2.5 专用并行计算模型11

1.2.6 其他并行计算模型12

1.3 并行算法的一般概念13

1.3.1 并行算法的定义和术语13

1.3.2 并行算法的复杂度14

1.3.3 并行算法的表达16

1.3.4 并行算法的WT表示17

1.3.5 并行算法的同步和通信20

习题23

参考文献24

第二章并行算法的基本设计技术26

2.1 平衡树方法26

2.1.1 求取最大值26

2.1.2 计算前缀和27

2.2.1 表序问题的计算30

2.2 倍增技术30

2.2.2 求森林的根31

2.3 分治策略32

2.3.1 SIMD模型上分治算法的描述32

2.3.2 SIMD共享存储模型上的FFT算法33

2.4 划分原理35

2.4.1 归并原理35

2.4.2 划分算法与归并算法36

2.5 流水线技术37

2.5.1 一维阵列上的流水线归并排序原理37

2.5.2 一维阵列上的流水线归并排序算法37

2.6 加速级联策略39

2.6.1 常数时间求最大值算法39

2.6.2 双对数时间算法40

2.6.3 加速级联算法41

2.7 破对称技术41

2.7.1 基本着色算法41

2.7.2 快速3-着色算法42

2.7.3 最优3-着色算法43

习题44

参考文献46

第三章比较器网络上的排序和选择算法47

3.1 Batcher归并和排序网络47

3.1.1 比较操作和［0，1］原理47

3.1.2 奇偶归并网络48

3.1.3 双调归并网络49

3.1.4 Batcher排序网络51

3.2.1 分组选择网络53

3.2 (m，n)-选择网络53

3.2.2 平衡分组选择网络55

3.3 AKS排序网络56

3.3.1 扩展图和划分网络56

3.3.2 部分排序算法59

3.3.3 完全排序算法61

习题65

参考文献66

第四章排序和选择的同步算法67

4.1 Stone双调排序算法67

4.1.1 均匀洗牌函数及其性质67

4.1.2 Stone的观察及其计算模型68

4.1.3 Stone的并行排序算法69

4.2.1 处理器编号方式71

4.2 Thompson和Kung双调排序算法71

4.2.2 Thompson和Kung的观察72

4.2.3 Thompson和Kung的双调排序算法73

4.3 Preparata和Vuilemin双调排序算法75

4.3.1 算法原理75

4.3.2 流水线技术76

4.3.3 算法描述77

4.4 Akl并行k-选择算法79

4.4.1 算法原理及物理描述79

4.4.2 并行k-选择算法79

4.4.3 算法分析81

4.5.1 归并算法的基本原理82

4.5.2 ？时Valiant归并82

4.5 Valiant并行归并算法82

4.5.3 ？时Valiant归并83

4.6 Hirschberg并行桶排序算法84

4.6.1 并行桶排序算法原理84

4.6.2 并行桶排序算法描述85

4.7 Preparat？并行枚举排序算法86

4.7.1 枚举排序及其实现方法86

4.7.2 排序算法的设计和分析87

4.8 Cole并行归并排序算法89

4.8.1 使用覆盖和位序的归并方法89

4.8.2 Cole最佳排序算法91

4.8.3 算法的正确性证明及分析95

习题98

参考文献99

第五章排序和选择的异步和分布式算法100

5.1 MIMD-CREW模型上的异步枚举排序算法100

5.1.1 算法原理和描述100

5.1.2 算法举例和分析101

5.2 MIMD-TC模型上的异步快排序算法102

5.2.1 算法原理和描述102

5.2.2 算法举例和分析103

5.3 分布式k-选择算法104

5.3.1 随机k-选择算法104

5.3.2 确定k-选择算法106

5.4 分布式求中值算法107

5.4.1 分布式中值107

5.4.2 分布式求中值算法108

5.5 分布式定序算法109

5.5.2 分布式定序算法110

5.5.1 分布式计算模型110

5.5.3 算法复杂度分析112

5.6 分布式排序算法113

5.6.1 模型和定义113

5.6.2 静态排序算法114

5.6.3 算法复杂度分析114

习题115

参考文献116

第六章并行搜索118

6.1 单处理机上的搜索118

6.1.1 单处理机上的顺序搜索118

6.2.1 SIMD-EREW模型上的搜索119

6.1.2 单处理机上有序表的对半搜索119

6.2 SIMD共享存储模型上有序表的搜索119

6.2.2 SIMD-CREW模型上的搜索120

6.3 SIMD共享存储模型上随机序列的搜索123

6.3.1 SIMD-SM模型上的随机序列搜索算法描述123

6.3.2 SIMD-SM模型上的随机序列搜索算法分析124

6.4 树连接的SIMD模型上随机序列的搜索124

6.4.1 提问124

6.4.2 维护125

6.5 网孔连接的SIMD模型上随机序列的搜索126

6.5.1 提问127

6.6 MIMD共享存储模型上有序表的搜索130

6.6.1 AVL树及其顺序插入算法130

6.5.2 维护130

6.6.2 Ellis并行搜素和插入算法132

习题134

参考文献134

第七章排列和组合135

7.1 产生排列的顺序算法135

7.1.1 排列和组合135

7.1.2 产生词典序的排列算法136

7.1.3 产生排列的计数方法138

7.2 产生组合的顺序算法140

7.2.1 产生词典序的组合算法140

7.2.2 产生组合的计数方法142

7.3.1 串行排列算法的并行化144

7.3 产生排列的并行算法144

7.3.2 自适应排列产生器148

7.3.3 全排列产生器149

7.4 产生组合的并行算法150

7.4.1 非自适应组合产生器151

7.4.2 自适应组合产生器154

习题155

参考文献156

第八章数据传输与选路157

8.1 引言157

8.2 贪心选路算法158

8.2.1 一维阵列上的贪心选路算法158

8.2.2 二维阵列上贪心选路算法的分析159

8.2.3 蝶形网络上的贪心选路算法161

8.3.1 二维阵列上的随机选路算法162

8.3 随机和确定选路算法162

8.3.2 超立方网络上的随机选路算法164

8.3.3 二维阵列上的确定选路算法165

8.4 数据的分布和集中167

8.4.1 数据的分布167

8.4.2 多到一选路算法169

8.5 线路交换模式下的选路算法171

习题173

参考文献174

第九章并行串匹配176

9.1 引言176

9.1.1 基本概念和研究现状176

9.1.2 基本定义和术语177

9.2.1 SIMD-CREW模型上的非周期串的匹配算法178

9.2 正文分析178

9.2.2 SIMD-CREW模型上的周期串的匹配算法181

9.3 模式预处理183

9.8.1 求WIT表的一般方法183

9.3.2 完全非周期串的WIT表求法184

9.3.3 SIMD-CREW模型上任意串的WIT表求法187

9.3.4 模式匹配算法的复杂度188

9.4 后缀树上的串匹配188

9.4.1 数字搜索树与后缀树189

9.4.2 子串的编码190

9.4.3 后缀树的构造192

9.4.4 后缀树上的并行串匹配195

习题196

参考文献198

第十章表达式求值199

10.1 构造表达式树199

10.1.1 全括号表达式的表达式树199

10.1.2 表达式树上的括号操作200

10.1.3 计算match(i)的并行算法201

10.2 填充游戏用于表达式求值202

10.2.1 二叉树上的填充游戏202

10.2.2 填充游戏用于算术表达式求值203

10.3 最优的并行表达式求值算法205

10.4 一般表达式求值算法208

10.4.1 一般表达式与直线程序208

10.4.3 仅有加法操作符的dag的计算209

10.4.2 仅有乘法操作符的dag的计算209

10.4.4 gbdag图和直线程序的计算210

10.5 正则表达式到非确定自动机的最优并行转换213

10.5.1 基本概念和术语213

10.5.2 SIMD-CREW模型上的HU转换方法215

习题217

参考文献218

第十一章上下文无关语言的并行识别与语法分析219

11.1 一般的上下文无关语言的并行识别219

11.1.1 基本概念和术语219

11.1.2 残缺部分语法树及其合成规则221

11.1.3 共享存储模型上歧义性上下文无关语言并行识别算法223

11.2 一般上下文无关语言的并行语法分析226

11.2.1 基本概念和算法原理226

11.2.2 SIMD-CREW模型上一般上下文无关语言的语法分析算法227

11.3 括号语言的最优并行识别和语法分析230

11.3.1 基本概念和算法原理230

11.3.2 算法的具体实现231

11.3.3 树的压缩技术233

11.3.4 SIMD-CREW模型上括号语言的语法分析算法236

习题236

参考文献237

第十二章矩阵运算238

12.1 矩阵转置238

12.1.1 单处理机上的矩阵转置算法238

12.1.2 SIMD-MC2模型上的矩阵转置238

12.1.3 SIMD-PS模型上的矩阵转置241

12.1.4 SIMD-EREW模型上的矩阵转置242

12.2 矩阵相乘243

12.2.1 单处理机上的矩阵乘法243

12.2.2 SIMD-MC2模型上的矩阵乘法244

12.2.3 SIMD-CC模型上的矩阵乘法245

12.2.4 MIMD机器上的矩阵乘法248

12.3 矩阵和向量相乘251

12.3.1 树连接的机器上的矩阵和向量乘法251

12.3.2 树网结构上的矩阵和向量乘法253

12.4 心动阵列上的矩阵运算253

12.4.1 二维六角形阵列上的矩阵乘法253

12.4.2 二维六角形阵列上方阵的LU分解255

12.4.3 六角形阵列上的方阵求逆258

12.4.4 一维阵列上求解三角形线性系259

习题261

参考文献264

第十三章数值计算265

13.1 n阶线性代数方程组的求解265

13.1.1 SIMD-CREW模型上的Gauss-Jor？an算法266

13.1.2 MIMD-CREW模型上的Gauss-Seidel算法268

13.1.3 紧耦合多处理机系统中LU算法的效率分析270

13.2 非线性方程的求根272

13.2.1 SIMD-CREW模型上的求根算法272

13.2.2 MIMD-CREW模型上的牛顿求根法274

13.2.3 Fibonacci分点法异步求根算法275

13.3 偏微分方程的求解278

13.3.1 偏微分方程的差分数值求解法278

13.3.2 SIMD-MC2模型上的PDE求解方法279

13.4.1 对称方阵对角化方法282

13.4 方阵的特征值与特征向量Jacobi求法282

13.4.2 SIMD-CC模型上的求特征值算法284

习题286

参考文献287

第十四章FFT和卷积与滤波289

14.1 快速富立叶变换289

14.1.1 离散富立叶变换289

14.1.2 顺序的FFT算法290

14.1.3 FFT应用于多项式乘积291

14.2 DFT直接并行计算法292

14.2.1 SIMD模型上系数矩阵的计算292

14.2.2 SIMD-MT模型上的DFT算法292

14.3.1 SIMD-MC2模型上的FFT算法295

14.3 并行FFT算法295

14.3.2 SIMD-BF模型上的FFT算法298

14.3.3 SIMD-PS模型上的FFT计算299

14.3.4 SIMD-CC模型上的FFT计算301

14.3.5 一维心动阵列上的DFT计算305

14.4 心动阵列上的卷积与滤波计算306

14.4.1 一维卷积在线性阵列上的实现306

14.4.2 无限冲激滤波在线性阵列上的实现308

14.4.3 中值滤波在线性阵列上的实现309

习题311

参考文献312

15.1 图的并行搜索313

15.1.1 算法原理313

第十五章图论算法313

15.1.2 p-深度优先搜索314

15.1.3 p-宽深优先搜索314

15.1.4 p-宽度优先搜索314

15.2 图的传递闭包316

15.2.1 传递闭包问题316

15.2.2 SIMD-CC模型上的传递闭包算法316

15.2.3 二维心动阵列上的传递闭包算法317

15.3 图的连通分量320

15.3.1 SIMD-CC模型上的连通分量算法320

15.3.2 SIMD-SM模型上的连通分量算法322

15.3.3 SIMD-TC模型上的连通分量算法324

15.3.4 SIMD-MT模型上的连通分量算法325

15.4 图的最短路径327

15.4.1 所有顶点对间的最短路径算法328

15.4.2 MIMD-SM模型上单源最短路径算法330

15.5 图的最小生成树333

15.5.1 SIMD-EREW模型上最小生成树算法333

15.5.2 MIMD-SM模型上最小生成树算法336

15.5.3 树机模型上最小生成树算法339

15.6 图的着色342

15.6.1 二分图的边着色算法342

15.6.2 外平面图最优顶点着色算法343

15.6.3 外平面图最优边着色算法349

15.6.4 Halin图最优边着色算法351

习题355

参考文献358

第十六章图象分析和计算几何360

16.1 分量标定360

16.1.1 二维阵列上分量标定平易算法360

16.1.2 二维阵列上Levialdi分量标定算法362

16.1.3 二维阵列上递归的分量标定算法364

16.2 Hough变换365

16.2.1 二维图象的Hough变换365

16.2.2 二维阵列上象素Hough变换的计算366

16.3 近邻问题367

16.4 包含问题368

16.4.1 判断点在多边形中369

16.4.2 判断点在平面细图中371

16.5 相交问题373

16.6.1 求凸壳问题的下界374

16.6 构造问题374

16.6.2 顺序求凸壳算法375

16.6.3 SIMD-MT模型上求凸壳算法376

16.6.4 SIMD-EREW模型上求凸壳算法378

习题383

参考文献384

第十七章组合搜索385

17.1 基于分治法的与树搜索385

17.1.1 搜素树385

17.1.2 SIMD模型上的与树搜索386

17.2 基于分枝限界法的或树搜索386

17.2.1 8-谜问题387

17.2.2 串行分枝限界算法388

17.2.3 用串行分枝限界法求TSP389

17.2.4 并行TSP算法393

17.3 串行的α-β搜索算法394

17.3.1 博弈树与最大最小原理394

17.3.2 串行的α-β算法395

17.4 树机上的并行搜索算法396

17.4.1 树分裂算法397

17.4.2 主变量分裂算法398

17.5 MIMD模型上α-β搜索算法400

17.5.1 基本设计原理400

17.5.2 算法的形式描述401

习题401

17.5.3 算法讨论和分析405

参考文献408

第十八章随机算法409

18.1 引言409

18.1.1 概率论的基本知识409

18.1.2 随机算法的模型及其度量412

18.2 部分独立集413

18.2.1 有向环图414

18.2.2 平面图415

18.3 三角形平面细图中点的位置416

18.3.1 细图层次417

18.3.2 细图层次的构造算法417

18.4 模式匹配419

18.4.1 指纹函数420

18.4.2 串匹配423

18.4.3 二维数组的匹配424

18.5 多项式恒等的验证425

18.5.1 基本技术425

18.5.2 矩阵乘积的验证426

18.6 排序427

18.6.1 随机采样及随机快排序427

18.6.2 并行随机快排序算法428

18.6.3 快速随机并行排序算法430

18.7 最大匹配和完备匹配432

18.7.1 图的代数性质433

18.7.2 测试完备匹配存在的随机算法435

习题438

参考文献439

19.1.1 VLSI电路模型441

19.1 VLSI电路模型和计算模型441

第十九章VLSI计算理论441

19.1.2 VLSI计算模型443

19.2 VLSI面-时下界理论444

19.2.1 几种基本的下界论点444

19.2.2 信息流和穿越序列446

19.3 典型计算图的结构布局法448

19.3.1 树的布局448

19.3.2 网孔和树网的布局449

19.3.3 洗牌交换网的布局449

19.3.4 立方环的布局452

19.4 典型计算图的布局下界453

19.4.1 树的布局下界453

19.3.5 蝶形网的布局453

19.4.2 树网的布局下界455

19.4.3 洗牌交换网的布局下界458

19.4.4 蝶形网的布局下界458

19.5 分治布局法459

19.5.1 分离集459

19.5.2 强分离集461

19.5.3 通道生成462

19.5.4 分治布局法463

19.6 VLSI布局理论466

19.6.1 平面图的分离定理466

19.6.2 图的交叉点数467

19.6.3 布局下界定理468

习题468

参考文献469

第二十章模型与下界471

20.1 不同PRAM模型的相互模拟471

20.1.1 在PRAM-EREW上模拟PPRAM-CRCW471

20.1.2 在CPRAM-CRCW上模拟PPRAM-CRCW472

20.1.3 在APRAM-CRCW上模拟PPRAM-CRCW474

20.2 PRAM-CREW的下界475

20.2.1 理想的PRAM模型475

20.2.2 形式描述475

20.2.3 特定问题的下界478

20.3 PRAM-EREW的下界478

20.3.1 工具和方法478

20.3.2 主要下界479

20.4 PRAM-CRCW的下界480

20.4.1 PRAM-CRCW与无界扇入电路481

20.4.2 无界扇入电路的下界487

20.5 P-完全导论490

20.5.1 问题的可并行化490

20.5.2 NC类和RNC类492

20.5.3 P-完全问题范例496

20.5.4 小结502

习题503

参考文献504

附录A复杂度表示及其符号506

A.1 大-O及其运算506

A.2 大-Ω和大-Θ506

A.3 小-O和小-ω507

附录B 算法复杂界一览表508