| 第一章 引言 | 第1-17页 |
| §1.1 问题的提出 | 第11-12页 |
| §1.2 基本定义 | 第12-14页 |
| §1.3 本文工作 | 第14-17页 |
| 第二章 排序算法理论与实现途径 | 第17-29页 |
| §2.1 排序算法的分类 | 第18-19页 |
| §2.1.1 分类方法1--串行排序和并行排序 | 第18页 |
| §2.1.2 分类方法2--适应算法与非适应算法 | 第18-19页 |
| §2.1.3 分类方法3--确定的排序算法和随机的排序算法 | 第19页 |
| §2.2 串行排序算法 | 第19-21页 |
| §2.2.1 串行排序算法的界 | 第19-20页 |
| §2.2.2 几种常见串行排序算法的对比 | 第20-21页 |
| §2.3 并行排序算法的界 | 第21-23页 |
| §2.3.1 节点数的界 | 第22-23页 |
| §2.3.2 信息传输和面积的界 | 第23页 |
| §2.4 并行排序算法的实现途径 | 第23-26页 |
| §2.4.1 并行计算模型 | 第23-25页 |
| §2.4.2 专用并行结构下实现排序--排序网络 | 第25页 |
| §2.4.3 通用并行结构下实现排序--SIMD和MIMD上的排序算法 | 第25-26页 |
| §2.4.4 广播通信模型(BCM)下实现排序 | 第26页 |
| §2.5 归并在排序中的重要地位 | 第26-29页 |
| 第三章 并行排序综述 | 第29-61页 |
| §3.1 引言 | 第29-31页 |
| §3.2 两路归并网络 | 第31-34页 |
| §3.2.1 奇偶归并网络 | 第31-32页 |
| §3.2.2 双调归并网络 | 第32-34页 |
| §3.3 Batcher两路排序网络 | 第34-36页 |
| §3.3.1 奇偶排序网络 | 第34-35页 |
| §3.3.2 双调排序网络 | 第35-36页 |
| §3.4 g-链周期排序网络 | 第36-40页 |
| §3.4.1 基本定义 | 第36-37页 |
| §3.4.2 网络构造 | 第37-39页 |
| §3.4.3 网络分析 | 第39-40页 |
| §3.5 多路归并排序网络 | 第40-47页 |
| §3.5.1 方法1--LB多路归并排序网络 | 第42-45页 |
| §3.5.2 方法2--PP排序网络 | 第45-47页 |
| §3.5.2.1 改进的ColumnSort算法 | 第45-46页 |
| §3.5.2.2 (k~(1／2),n／(k~(1／2)))--归并器的构造方法 | 第46-47页 |
| §3.6 各种排序网络的对比分析 | 第47-49页 |
| §3.7 de Bruijn网上的双调排序算法 | 第49-51页 |
| §3.7.1 de Bruijn网络 | 第49页 |
| §3.7.2 双调排序算法的实现 | 第49-51页 |
| §3.7.3 算法分析 | 第51页 |
| §3.8 在2D-PEC网络上的双调排序算法 | 第51-55页 |
| §3.8.1 2D-PEC网络介绍 | 第51-53页 |
| §3.8.2 在2D-PEC网络上的双调排序算法 | 第53-54页 |
| §3.8.3 算法分析 | 第54-55页 |
| §3.9 在星图(Star Graph)互联网络下的排序算法 | 第55-57页 |
| §3.9.1 星图的有关定义 | 第55-56页 |
| §3.9.2 排序算法 | 第56-57页 |
| §3.9.3 算法分析 | 第57页 |
| §3.10 在MIMD模型下的通用随机排序算法 | 第57-58页 |
| §3.10.1 并行的随机排序算法 | 第57-58页 |
| §3.10.2 理论分析 | 第58页 |
| §3.11 本章小节 | 第58-61页 |
| 第四章 一种高效的多路并行归并算法--ISS-Mk算法 | 第61-83页 |
| §4.1 倾斜与振荡多路归并算法--SS-Mk算法 | 第61-66页 |
| §4.1.1 SS-Mk算法介绍 | 第61-65页 |
| §4.1.2 SS-Mk算法分析 | 第65-66页 |
| §4.2 改进的倾斜与振荡多路归并算法--ISS-Mk算法 | 第66-74页 |
| §4.2.1 ISS-Mk算法描述 | 第66-69页 |
| §4.2.2 ISS-Mk算法正确性证明 | 第69-73页 |
| §4.2.3 ISS-Mk算法分析 | 第73-74页 |
| §4.3 SORTBLOCK算法 | 第74-81页 |
| §4.3.1 SORTBLOCK算法描述 | 第74-77页 |
| §4.3.2 SORTBLOCK算法的正确性证明 | 第77-81页 |
| §4.4 本章小节 | 第81-83页 |
| 第五章 多路归并算法SS-Mk的应用与网络实现 | 第83-93页 |
| §5.1 基于SS-Mk算法的并行排序算法的实现 | 第83-84页 |
| §5.1.1 SS-Sk的算法描述 | 第83-84页 |
| §5.1.2 SS-Sk的算法分析 | 第84页 |
| §5.2 基于SS-Mk归并算法的网络--SS-Mk归并网络 | 第84-88页 |
| §5.2.1 SS-Mk归并网络的构造过程 | 第85-88页 |
| §5.2.2 SS-Mk归并网络的具体实例 | 第88页 |
| §5.3 基于SS-Sk算法的排序网络--SS-Sk排序网络 | 第88-91页 |
| §5.3.1 SS-Sk排序网络实现 | 第88-90页 |
| §5.3.2 SS-Sk排序网络的时间延迟 | 第90页 |
| §5.3.3 排序网络具体实例 | 第90-91页 |
| §5.4 本章小节 | 第91-93页 |
| 第六章 多路归并算法ISS-Mk的应用 | 第93-97页 |
| §6.1 基于ISS-Mk的并行排序算法--ISS-Sk算法 | 第93-94页 |
| §6.1.1 ISS-Sk的算法描述 | 第93页 |
| §6.1.2 ISS-Sk的算法分析 | 第93-94页 |
| §6.2 基于ISS-Mk归并算法的归并网络--ISS-Mk归并网络 | 第94-96页 |
| §6.3 基于ISS-Sk算法的排序网络--ISS-Sk排序网络 | 第96页 |
| §6.4 小节 | 第96-97页 |
| 第七章 SS-Sk、ISS-Sk排序网络和Batcher排序网络比较 | 第97-101页 |
| §7.1 SS-Sk排序网络与Batcher排序网络的比较 | 第97-99页 |
| §7.2 ISS-Sk排序网络与Batcher排序网络的比较 | 第99-101页 |
| 第八章 结束语 | 第101-105页 |
| §8.1 本文工作总结 | 第101-102页 |
| §8.2 对并行排序研究的考虑 | 第102-105页 |
| 参考文献 | 第105-115页 |
| 作者简介 | 第115-116页 |
| 攻读博士学位期间撰写的学术论文及译著 | 第116页 |
