并行算法 排序和选择PDF电子书下载

第一章 并行计算机与并行计算 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