《并行算法 排序和选择》求取 ⇩

第一章并行计算机与并行计算1

1.1 并行计算机及其分类1

1.1.1 并行计算机的发展1

1.1.2 并行计算机简介2

1.1.3 并行计算机的分类4

1.2 处理器的互连方式5

1.2.1 一维线性连接5

1.2.2 网孔结构5

1.2.3 树形结构6

1.2.4 树网结构7

1.2.5 金字塔结构7

1.2.6 超立方连接8

1.2.8 立方环连接9

1.2.7 q-维网格连接9

1.2.9 洗牌交换网络10

1.2.10 蝶形结构11

1.3 并行计算模型12

1.3.1 不同互连结构的SIMD模型13

1.3.2 共享存贮的SIMD模型14

1.3.3 MIMD并行计算模型15

1.4 并行计算的若干理论问题15

1.4.1 Grosch定律15

1.4.2 Minsky猜想15

1.4.3 Amdahl定律16

1.4.4 构造高性能并行计算机的策略16

1.5 并行算法的一般概念17

1.5.1 并行算法的定义、分类和术语17

1.5.2 并行算法的复杂性18

1.5.3 并行算法的表达20

参考文献21

第二章并行算法的设计23

2.1 引言23

2.2 SIMD-IN机器上开发的并行算法24

2.2.1 SIMD-CC机器上的求和计算24

2.2.2 SIMD-SE机器上的求和计算26

2.2.3 SIMD-MC2机器上的求和计算27

2.3 MIMD机器上开发的并行算法27

2.3.1 MIMD算法的种类28

2.3.2 限制加速的因素29

2.3.3 MIMD算法复杂性分析31

2.4 MIMD机器上的进程通信和同步32

2.4.1 并发性表示32

2.4.2 使用共享变量同步33

2.4.3 通过传递信息的低级同步34

2.4.4 远程过程调用35

2.4.5 并发程序设计语言的分类36

2.5 MIMD机器中的死锁和任务调度37

2.5.1 死锁37

2.5.2 确定性调度模式37

2.5.3 非确定性调度模式38

参考文献39

第三章递归方程的求解40

3.1 分治法40

3.2 递归式展开法41

3.3 齐次递归方程的解41

3.4 齐次方程43

3.5 非齐次方程44

3.6.1 因子求和47

3.6 变换术47

3.6.2 域变换49

3.7 猜测解51

参考文献52

第四章排序和选择网络53

4.1 Batcher归并和排序网络53

4.1.1 比较器网络和［0.1］原理53

4.1.2 奇偶归并网络56

4.1.3 双调归并网络59

4.1.4 Batcher排序网络62

4.2 布尔排序网络和枚举排序网络66

4.2.1 布尔对称函数及其性质66

4.2.2 布尔对称函数在分析和综合排序网络时的应用68

4.2.3 Muller和Preparata的枚举排序网络72

4.3.1 AKS排序网络的基本原理74

4.3 AKS排序网络74

4.3.2 扩展图、ε-对分和ε-准排序75

4.3.3 寄存器的指派和划分77

4.3.4 AKS算法的形式描述78

4.4 分组选择网络79

4.4.1 选择问题和选择网络79

4.4.2 分组原理在选择算法中的应用80

4.4.3 分组选择网络81

4.4.4 平衡分组选择网络83

4.5 递归选择网络86

4.5.1 分离原理在递归算法中的应用86

4.5.2 选择网络上、下界的研究87

4.5.3 递归选择网络89

参考文献92

5.1.1 奇偶转置排序算法94

第五章固定连接的SIMD机器上的并行排序和选择算法94

5.1 一维线性阵列上的并行排序算法94

5.1.2 归拆(Merge-Splitting)排序96

5.1.3 流水线机上的归并排序98

5.2 树机上的并行排序算法100

5.2.1 抽取最小值排序法100

5.2.2 桶排序和归并102

5.2.3 中值排序法106

5.3 混洗连接的SIMD机器上的双调排序算法108

5.3.1 均匀洗牌函数及其性质108

5.3.2 Stone的观察及其计算模型109

5.3.3 Stone的并行排序算法111

5.4 网孔连接的SIMD机器上的双调排序算法112

5.4.1 处理器编号方式113

5.4.2 Thompson和Kung的观察114

5.4.3 Tkompson和Kung的双调排序算法115

5.5 立方连接的SIMD机器上的双调排序算法117

5.5.1 Siegel的观察118

5.5.2 双调归并在SIMD-CC机器上的实现118

5.5.3 双调排序在SIMD-CC机器上的实现119

5.6 SIMD机器上实现的双调选择算法120

5.6.1 双调选择网络120

5.6.2 对双调选择网络之观察122

5.6.3 SIMD机器上实现的双调选择算法123

5.7 SIMD-IN机器上的数据传输124

5.7.1 互连网络中的数据选路125

5.7.2 用排序网络实现选路125

5.7.3 SIMD-IN机器上的数据传播126

参考文献128

第六章共享存贮的SIMD机器上的并行排序和选择算法129

6.1 引言129

6.2 Akl的并行算法130

6.2.1 并行h-选择算法130

6.2.2 并行快排序算法133

6.3 Valiant归并和排序算法136

6.3.1 求极大值的下界136

6.3.2 Valiant并行归并137

6.3.3 Valiant并行排序139

6.4 Hirschberg排序算法140

6.4.1 并行桶排序算法140

6.4.2 快速并行排序143

6.5 Preparata排序算法145

6.5.1 枚举排序及其实现方法145

6.5.2 排序算法的设计和分析146

6.6 SIMD-SM机器上实现的归并选择算法148

6.6.1 归并选择原理149

6.6.2 归并选择算法的设计和分析149

6.7 Cole归并排序算法151

6.7.1 Cole算法原理152

6.7.2 CREW模型上的算法描述152

6.7.3 CREW模型上的算法分析155

参考文献156

第七章MIMD机器上的并行排序和选择算法157

7.1 引言157

7.2 MIMD-CREW模型上的枚举异步排序158

7.2.1 算法原理158

7.2.2 算法的形式描述158

7.3.1 算法原理159

7.2.3 算法分析159

7.3 MIMD-TC模型上的异步快排序159

7.3.2 算法的形式描述160

7.3.3 算法分析162

7.4 分布式选择算法163

7.4.1 分布式k-选择算法163

7.4.2 分布式多项选择算法166

7.4.3 分布式求中值算法167

7.4.4 分布式求极值算法169

7.5 分布式定序算法173

7.5.1 计算模型173

7.5.2 分布式定序算法174

7.5.3 算法复杂性分析176

7.6.2 各场点只有一个元素(|X1|=1)时的分布式排序算法177

7.6.1 模型和定义177

7.6 分布式静态排序算法177

7.6.3 基于分布式k-选择的分布式排序算法178

7.6.4 基于分布式多项选择的分布式排序算法179

7.7 分布式动态排序算法180

7.7.1 问题描述180

7.7.2 分布式动态排序算法182

7.7.3 算法复杂性分析182

参考文献183

第八章并行外排序185

8.1 引言185

8.2 两路磁带外排序185

8.2.1 树机上的归并外排序算法185

8.2.2 算法8.1在磁带机上的实现186

8.3.1 一维线性阵列上的外排序算法188

8.3 流水线式磁带外排序188

8.3.2 算法8.2在磁带机上的实现190

8.4 并行磁盘排序194

参考文献197

第九章VLSI计算模型上的排序算法198

9.1 VLSI计算模型和面-时下界198

9.1.1 VLSI计算模型198

9.1.2 时-空论199

9.1.3 面-时下界200

9.2 常用电路结构图的布局202

9.2.1 树的布局202

9.2.2 网孔和树网的布局203

9.2.3 洗牌-交换网的布局204

9.2.4 CCC的布局205

9.3.1 平面图分离定理206

9.2.5 蝶形结构的布局206

9.3 VLSI布局理论206

9.3.2 分治布局法207

9.3.3 布局的下界理论208

9.4 VLSI计算模型上的几种排序算法208

9.4.1 基本的VLSI电路模块208

9.4.2 Batcher排序网络的VLSI实现209

9.4.3 SIMD-SE上双调排序的VLSI实现210

9.4.4 SIMD-MC2上奇偶归并排序的VLSI实现210

9.4.5 树网结构上的枚举排序算法212

9.4.6 CCC结构上的双调排序算法213

参考文献217

第十章选择和排序的概率并行算法218

10.1 引言218

10.2.1 概率判定树和串行选择算法219

10.2 并行判定树模型上的概率k-选择算法219

10.2.2 概率并行k-选择算法描述222

10.2.3 概率并行k-选择算法分析223

10.3 并行判定树模型上的概率排序算法226

10.4 并行RAM模型上的概率排序算法227

10.4.1 PRAM-CREW模型上的概率排序算法描述228

10.4.2 PRAM-CREW模型上的概率排序算法分析231

参考文献235

附录A并行排序算法的下界236

A.1 排序问题的一组基本下界236

A.2 基于比较的并行排序算法之下界237

A.3 q-维网格上的并行排序之下界237

A.4 树机上的并行排序之下界238

参考文献239

B.1.1 整数函数及其等式240

附录B数学知识240

B.1 数和不等式240

B.1.2 数列求和241

B.1.3 代数不等式241

B.2 阶乘及其应用242

B.2.1 和与积242

B.2.2 阶乘243

B.2.3 二项式系数244

B.3 调和数、斐波那契数和渐近表示246

B.3.1 调和数246

B.3.2 斐波那契数246

B.3.3 渐近表示247

B.4 数学归纳法248

参考文献248