并行排序算法的设计范文

《电脑与信息技术杂志》2014年第三期

1并行算法

1.1并行算法分类并行算法的种类非常多，分类标准也均有所不同。按照基础运算对象进行分类，有数值和非数值两周并行算法。按照并行运算过程中，各进程的执行时间进行分类，有同步、异步和独立三种不同的并行算法。按照进程处理机中，它们各自承担所要计算任务量进行分类，有大粒度、中粒度和小粒度三种并行算法。

1.2并行算法设计方法并行算法的设计需要参照系统类型以及系统的特征，对某一问题针对性在处理机上进行并行解决。并行算法的设计一般有三种办法：对已有的串行算法进行检查，对算法中的并行性进行开发，并加以优化；根据问题本身的特征出发，设计一个完全不同的并行算法；在已有算法的基础上，根据问题的特征进行修改，处理类似的问题；第一种设计方法中，如若该串行算法已经有内在相关顺序性，就非常难做并行的优化；第二种设计方法中，对现有算法进行修改，则要熟知问题的特殊性；第三种设计方法，凭空创新设计出一个算法，技巧性非常强，不但没什么章法，而且技术水平达不到。针对并行算法的设计，目前最为普遍的设计方法有平衡树技术、分治策略技术、流水线技术以及倍增技术等等。

1.3并行算法计算模型并行计算模型是指从所有并行机中，把共性存在的基本特征分离出来，最终形成一个抽象的并行计算处理机，且要在具体并行机至上。它与顺序计算中的VonNeumann模型非常相似。根据普渡报告分析，并行计算模型，必须能够保证并行计算处理机针对哪种计算，表现出超强的计算能力。并行计算的模型、算法设计以及并行机的相互关系，如图1所示：并行计算模型在并行算法中，有着至关重要的作用。它作为一种常见物质基础提供给并行算法，进行相关研究；它还可以拿出一个简单便利的框架结构，用于并行算法的设计以及开发分析；因其适用性较强，看适用在许多种类的并行处理机上，使得新的并行算法充满生命力。

2并行排序的基本思想

并行排序算法是参照快速排序算法的分治方法，首先在主进程内，把其宿主机上等待排序的某一数组分割为n块，文件的大小决定n的值。然后再把n块数据推送到对应数量的从进程中，从进程对其已经接受的数据在宿主机上进行串行排序，最后所有从进程将已排好序的数据回传给主进程，同时数据要放回到原数值的位置上，完成了并行排序。按照此思想进行排序，缺点是不能确定算法的性能。可以借鉴负载均衡的思想，对该算法做出一些改进。从进程接受到数据后，不再对数据进行划分，只需要将其分为相同大小的n块，并将n块推送到对应的n个从进程中，由从进程来对分到的数据进行排序操作，排序完成后将已排序的数据传回给主进程。最后主进程只需要对接收到的n块排序数据进行归并排序，至此就完成了数据的排序工作。

3算法设计

3.1算法基本思想本文并行排序的算法思想是，首先形成部分有序的数据库，然后依次读入将数据顺序分成的数据块，快的大小不能超出内存的大小。最后再对每一个小块进行排序，排序的结果保存到临时的文件中。

3.2算法设计假设需要排序的数据总量为N，分为n个数据块，每个数据块的数据量为A，即N=nA，每一块数据块进行排序的耗费的时间为t(A)。设立三个A的函数，readblock()读入数据块、sortblock()数据块的排序、writeblock()保存已排序的数据块，分三个步骤完成数据排序。排序耗费的总时间t(A)由三个函数执行总时间的决定，分别记作tr(A)、ts(A)、tw(A)。完成所有数据排序的时间为：如果只需要某一个进程对数据处理的话，即串行执行上述三个步骤，如图2所示：但是因为readblock()、sortblock()、writeblock()三者在排序的时候所占用的系统资源均不相同。若如想要数据读入readblock()和数据保存writeblock()二者同时进行的话，就需要把排序前数据和已排序的数据分布安防在两个不同的硬盘上，而且还不会争夺I/0资源。另外，因为这两个模块占用的CPU资源特别少，数据排序sortblock()也可以并行运行，互不影响。所以说我们通过使用单机进行数据的排序，提高了排序算法的效率。合理的并行算法运行时，必须根据数据块的特性制定。本文上述三个block相互排斥，在并行运算时，必须遵循以下规则：第M个数据块的readblock()、sortblock()、writeblock()结束之后，方能开始第M+1个数据块对应的readblock()、sortblock()、writeblock()；第M个数据块的readblock()结束之后方能开始sortblock()；第M个数据块的sortblock()结束之后，方能开始write-block()。总之，要保证三个进程并行运行完成对数据的排序工作，如图3所示：三个进程并行运行可以充分利用系统的CPU、I/0资源，当开始运行后，任一时间都会有readblock()、sortblock()、writeblock()并行运行。这样保证了进程运行时不存在等待的情况，同时正好是重要路由算法得的最优执行方案。在调用三个进程之前，必须要先创建进程，应用进程创建函数。程序执行时顺序完成数据的读入、数据排序和数据的保存。多次测量执行时间后，取平均值，以此为依据启动三个进程。最终，多进程的并行排序得以实现。

4结束语

当前数据信息量高速增长，信息化建设也逐步推进，人们对数据处理速度提出了更高的要求，计算机速度要求也越来越高，也成为许多学者和专家积极研究探索的重要课题。开发人员也不再需要考虑进程的通信和控制等问题，仅需要编写正确的编译指导语句实现数据的并行计算。并行计算中的算法设计和负载均衡等核心问题，需要今后进行进一步的研究，从而提高并行处理的效率。

作者：覃贤立单位：云南师范大学信息学院广西民族师范学院