基于并行粒子群优化算法在排序技术上的应用

论文摘要

超级计算机(高性能计算机)是计算机中功能最强、运算速度最快、存储容量最大的一类计算机。多用于国家高科技领域和尖端技术研究,是一个国家经济和科技实力的综合体现,也是促进科技及经济发展、社会进步和国防安全的重要工具。目前已经成为了世界各国竞相争夺的战略制高点。并行计算(Parallel Computing)与高性能计算(High Performance Computing)是同义词,因为任何的高性能计算都离不开并行技术。如何使高性能的并行机系统充分地在国民经济、科研和社会中发挥作用,实为当务之急,也引起了许多研究人员的广泛关注。MPI (Message Passing Interface)是目前最重要的一个基于消息传递的并行编程平台,已成为消息传递并行编程平台上的标准,是并行程序设计的主流工具。MPICH是一种最重要的MPI实现,在局域网内通过MPICH连接现有的计算机,组成高性能的并行计算机,针对复杂优化问题进行大规模的计算。粒子群优化算法(Particle Swarm Optimization, PSO)源于人类对鸟群扑食行为的研究。是一种基于群体的智能算法和优化工具,并且在自身的算法上存在着内在的并行性。但是在处理大量数据和大规模复杂优化问题时,PSO算法依然需要大量的处理时间,而并行PSO算法可以大幅度缩减问题的求解时间以及简化求解问题。因此,对并行PSO算法的研究也受到了很多科研人员的重点关注。排序技术是经常使用在数据处理过程中的一类问题,也是计算机系统内部经常使用的一种操作。排序可以简单的理解为：把一组无序的数列转化为有序数列。排序通常要消耗大量的计算时间,而把并行粒子群优化算法加入到排序算法中,可以有效的改善求解时间。本文通过构建基于MPI的计算机群环境,实现了基于并行粒子群优化算法的快速排序、秩排序算法。并且通过对串行的排序算法与基于并行粒子群优化算法的排序算法进行求解时间、求解复杂度、并行加速比等方面的对比与分析,说明了并行粒子群优化算法在排序算法中应用的可行性与有效性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 课题研究的背景
• 1.2 课题的历史及发展现状
• 第二章 并行计算基础及程序设计
• 2.1 并行计算机结构模型
• 2.2 并行算法的设计
• 2.2.1 并行算法的设计基础
• 2.2.2 并行算法的设计方法
• 2.2.3 并行算法的设计过程
• 2.3 并行程序设计
• 2.3.1 并行程序设计概述
• 2.3.2 并行编程风格
• 2.3.3 并行程序的设计流程
• 2.3.4 并行层次及代码粒度
• 第三章 MPI并行环境及编程模式
• 3.1 MPI简介
• 3.2 MPI编程基础
• 3.2.1 MPI程序的基本结构
• 3.2.2 MPI的常用函数
• 3.3 MPI消息传递的基本概念
• 3.3.1 MPI消息传递
• 3.3.2 MPI的缓冲区、进程号和通信子
• 第四章 粒子群优化算法
• 4.1 群体智能
• 4.1.1 群体智能简介
• 4.1.2 群体智能特点
• 4.2 粒子群优化算法简介
• 4.2.1 标准的粒子群优化算法
• 4.2.2 粒子群优化算法参数分析
• 4.3 并行粒子群优化算法
• 4.3.1 并行粒子群优化算法的基本思想
• 4.3.2 并行粒子群优化算法的任务分配
• 第五章 并行粒子群优化算法在排序中的实现
• 5.1 排序算法的简介
• 5.1.1 排序的定义
• 5.1.2 排序算法
• 5.1.3 排序算法的分类
• 5.1.4 排序算法的效率分析
• 5.2 并行粒子群优化算法在排序算法中的实现
• 5.2.1 排序算法并行化的意义
• 5.2.2 实验环境的配置
• 5.2.3 算法实例
• 5.3 串行排序算法与并行粒子群排序算法的性能分析与比较
• 5.3.1 几种加速比性能分析定律
• 5.3.2 并行算法的可扩放性
• 5.3.3 并行粒子群优化排序算法的性能分析
• 第六章 结论
• 致谢
• 参考文献
• 附录A 攻读硕士学位期间发表论文目录