65.9K
CodeProject 正在变化。 阅读更多。
Home

使用 Open MPI 的快速排序的并行实现和评估

Moumie Soulemane
starIconstarIconstarIconstarIconstarIcon

5.00/5 (3投票s)

2016年3月3日

CPOL

14分钟阅读

viewsIcon

52752

downloadIcon

1744

使用 Open MPI 库实现快速排序算法， 以比较顺序实现与并行实现

目录

  1. 目标
  2. 相关工作
  3. 实验理论
  4. 使用 MPI 实现的 QuickSort 算法和实现
    1. 提出的算法
    2. 实现
  5. 实验设置和结果
    1. 硬件规格
    2. 软件规格
    3. 安装
    4. 结果
    5. 可视化
    6. 分析
  6. 问题
  7. 结论
  8. 未来工作
  9. 参考文献
  10. 历史

1. 目标

排序在人类活动和个人电脑、智能手机等设备中都有应用，并且在近期技术发展中持续发挥着至关重要的作用。QuickSort算法被认为是最高效的排序算法之一。它由 C.A.R. Hoare 于 1961 年发明，并使用分治策略来解决问题 [3]。其分区特性使得 QuickSort 能够通过任务并行进行并行化。MPI（Message Passing Interface）是一种消息传递接口库，允许通过将代码发送到多个处理器来实现并行计算，因此可以轻松地用于目前大多数多核计算机上。本研究的主要目的是使用 Open MPI 库实现 QuickSort 算法，从而比较顺序实现和并行实现。整个研究将分为多个部分：相关工作、实验理论、使用 Open MPI 的 QuickSort 算法和实现、实验设置和结果、问题以及结论和未来工作。

2. 相关工作

许多研究已经对使用 Posix 线程 (Pthreads)、OpenMP 或消息传递接口 (OpenMPI) 的 Quicksort 算法并行实现进行了研究。例如，[9] 介绍了使用 OpenMP 并行实现 Quicksort 算法所获得的性能提升。作者利用 OpenMP 丰富的库支持和简洁性，显著减少了 Quicksort 并行版本与顺序版本相比的执行时间。在这项研究中，并行版本执行时间的不确定性似乎是主要问题。另一项使用 OpenMPI 和 Pthreads 在集群上的多处理器上进行的并行 Quicksort 实验 [7] 强调了不同的基准测试和优化技术。在 [8] 中使用了与 [7] 相同的算法实现，这次仅侧重于性能分析。简而言之，[7, 8] 展示了几乎相同的并行 Quicksort 和 MPI 实现，在分别对数据块进行排序后，使用基于树的合并来收集不同的块以获得最终的排序数据。然而，在我们的研究中，我们采取了一种完全不同的方法。在我们的实现中，我们仅仅使用了 MPI 的集合通信例程和一个额外的排序步骤来代替合并功能。最初，我们使用 C 语言对 QuickSort 的每个版本（迭代和递归）进行了顺序实现。然后，我们将两个顺序实现移植到 MPI 中，以便并行运行它们。

3. 实验理论

与归并排序类似，QuickSort 使用分治策略，是最高效的排序算法之一；它可以以递归或迭代的方式实现。分治是一种通用的算法设计范例，该策略的关键步骤可总结如下：

  • 分而治之：将输入数据集 S 分成不相交的子集 S1, S2, S3…Sk.
  • 递归：解决与 S1, S2, S3…Sk 相关的子问题。
  • 合而并之：将 S1, S2, S3…Sk 的解合并为 S 的解。
  • 基本情况：递归的基本情况通常是大小为 0 或 1 的子问题。

许多研究 [2] 表明，为了排序 N 个项目，QuickSort 的平均运行时间为 O(NlogN)。QuickSort 的最坏情况运行时间发生在枢轴是唯一的最小值或最大值元素时，正如 [2] 所述，QuickSort 对 N 个项目的最坏情况运行时间为 O(N2)。这些不同的运行时间会受到输入分布（均匀、已排序或半排序、未排序、重复）以及枢轴元素选择的影响。以下是从 Wikipedia [1] 改编的 QuickSort 算法的简单伪代码。

如上方的伪代码所示，以下是 Quicksort 的基本工作机制：

  • 选择数组中的任意元素作为枢轴
  • 将所有其他元素（枢轴除外）分成两个分区
    • 所有小于枢轴的元素必须在第一个分区
    • 所有大于枢轴的元素必须在第二个分区
  • 使用递归对两个分区进行排序
  • 连接第一个已排序的分区、枢轴和第二个分区
  • 输出是一个已排序的数组

我们使用 Open MPI 作为并行化 QuickSort 算法的骨干库。事实上，学习消息传递接口 (MPI) 可以增强我们对并行编程的基础知识，因为 MPI 比等效库 (OpenMP) 更底层。顾名思义，MPI 的基本思想是消息可以在不同进程之间传递或交换，以执行给定的任务。一个例子可以是主进程通过通信和协调将一个巨大的任务分成块并分发给它的从属进程。Open MPI 由学术、研究和行业合作伙伴联盟开发和维护；它结合了高性能计算社区的专业知识、技术和资源 [11]。正如 [4] 中所述，MPI 有两种通信例程：点对点通信例程和集合通信例程。在本研究中使用了集合例程，如实现部分所述。

4 使用 MPI 实现的 QuickSort 算法和实现

以下各节详细介绍了我们将 QuickSort 算法移植到 MPI 的过程。

4.1 提出的算法

总的来说，这里用于使用 MPI 执行 QuickSort 的总体算法如下：

  1. 启动并初始化 MPI。
  2. 在主进程 MASTER 下获取输入。
    1. 从输入文件中读取数字列表 L。
    2. 使用 L 初始化主数组 globaldata。
    3. 启动计时器。
  3. 将输入大小 SIZE 除以参与进程数 npes，得到每个块的大小 localsize.
  4. 将 globaldata 按比例分发给所有进程。
    1. MASTER 将 globaldata 散发给所有进程。
    2. 每个进程接收到一个子数据 localdata。
  5. 每个进程在本地排序其大小为 localsize 的 localdata。
  6. Master 将其他进程排序的 localdata 收集到 globaldata 中。
    1. 收集每个已排序的 localdata。
    2. 释放 localdata。
  7. 在 MASTER 下，对 globaldata 进行最终排序。
    1. 对 globaldata 进行最终排序。
    2. 停止计时器。
    3. 将输出写入文件。
    4. 顺序检查 globaldata 是否已正确排序。
    5. 释放 globaldata。
  8. 终止 MPI。

4.2 实现

为了使用 C 编程实现上述算法，我们使用了一些 MPI 集合通信例程。因此，在使用 MPI_Init 初始化 MPI 后，分别使用 MPI_Comm_size 和 MPI_Comm_rank 获取大小和秩。使用 MPI_Wtime 获取开始的墙上时钟时间，根进程使用 MPI_Scatter 将包含输入的数组按大小比例分发给所有参与的进程，并在排序后使用 MPI_Gather 重新收集。最后，再次使用 MPI_Wtime 获取结束的墙上时钟时间，并通过调用 MPI_Finalize 来终止 MPI。在接下来的部分，我们提出的算法的每个部分都通过从实现源代码中提取的代码片段进行说明。

  1. 启动并初始化 MPI。

  2. 在主进程 MASTER 下获取输入。

    启动计时器。

  3. 将输入大小 SIZE 除以参与进程数 npes，得到每个块的大小 localsize。

  4. 将 globaldata 按比例分发给所有进程。

  5. 每个进程在本地排序其大小为 localsize 的 localdata。

  6. Master 将其他进程排序的 localdata 收集到 globaldata 中。

  7. 在 MASTER 下，对 globaldata 进行最终排序。

    停止计时器。

    将信息写入输出文件。

    检查最终的 globaldata 数组是否已正确排序。

    释放分配的内存。

  8. 终止 MPI。

QuickSort 算法的两个版本都已实现；然而，尽管它们使用相似的函数进行了几乎相同的实现，但递归部分中的递归已由堆栈替换，以便使其成为迭代的。它们的函数签名在下一部分给出。

  • 递归 QuickSort

  • 迭代 QuickSort

运行此程序所需的输入文件可以使用输入生成器生成，其中我们指定大小和文件名（input_generator.c），然后使用以下说明进行编译和运行。

5 实验设置和结果

本节将更详细地介绍将实际数据应用于并行 QuickSort 的不同输入参数所获得的结果。它包括以下部分：硬件规格、软件规格、安装、结果、可视化和分析。

5.1 硬件规格

  • 电脑：ProBook-4440s
  • 内存：3.8 GiB
  • 处理器：Intel® Core™ i5-3210M CPU @ 2.50GHz × 4
  • 显卡：Intel® Ivybridge Mobile x86/MMX/SSE2
  • 操作系统类型：32位
  • 硬盘：40.1 GB

5.2 软件规格

  • 操作系统：Ubuntu 14.04 LTS
  • Open MPI：1.10.1 发布
  • 编译器：gcc version 4.8.4
  • Microsoft Excel 2007 用于绘图。

5.3 安装

Open MPI 的安装过程并不总是那么直接，并且取决于预期的环境。最初，我们在 Microsoft Windows 7 操作系统上使用 Cygwin 安装了 Open MPI。CygWin 是 Microsoft Windows 的一个类 Unix 环境和命令行界面。它提供了 Windows 应用程序、数据和其他系统资源与类 Unix 环境的应用程序、软件工具和数据的原生集成 [10]。可以在 [5] 中找到 CygWin 在 Microsoft Windows 上的完整安装过程。在更新 CygWin 后，我们遇到了一个未解决的问题和关键错误，如本报告的问题部分所述。因此，我们选择安装一个带有 Linux 作为客户操作系统的虚拟机，并在其中安装了 MPI。同样，由于问题部分解释的一些限制，我们最终在正常安装为宿主操作系统的 Ubuntu 上安装了 CygWin。Ubuntu 像其他 Linux 发行版一样，为 Open MPI 软件包的安装和执行提供了合适的环境。基本安装步骤可以在 [6] 中找到。本研究中获得的所有结果均来自我们基于 Ubuntu 的安装。但是，Open MPI 也可以安装在未在此处提及的其他一些操作系统上。

5.4 结果

下表列出了记录的不同数据。第一列是实验编号（No.）；第二列是参与进程数（# process）；第三列是应用于 QuickSort 的输入数据大小。最后两列分别表示并行 QuickSort 的迭代版本和递归版本的执行墙上时钟时间。

不支持。 # 进程 输入大小 迭代墙上时间 递归墙上时间
1 1 20 0.0000 0.0000
2 0.0001 0.0000
5 0.0002 0.0004
10 0.0004 0.0005
20 0.0013 0.0032
2 1 100 0.0000 0.0000
2 0.0001 0.0001
5 0.0002 0.0004
10 0.0003 0.0005
20 0.0016 0.0020
3 1 1000 0.0011 0.0012
2 0.0003 0.0003
5 0.0004 0.0004
10 0.0007 0.0008
20 0.0014 0.0016
4 1 10000 0.0849 0.0860
2 0.0030 0.0030
5 0.0031 0.0030
10 0.0038 0.0035
20 0.0035 0.0043
5 1 100000 8.2165 8.5484
2 0.0393 0.0383
5 0.0333 0.0325
10 0.0418 0.0488
20 0.0446 0.0475
6 1 1000000 835.8316 2098.7
2 0.4786 0.4471
5 0.3718 0.3590
10 0.3646 0.3445
20 0.4104 0.3751

5.5 可视化

本节将展示比较迭代 QuickSort 和递归 QuickSort 在不同进程数和各种输入大小下的不同图表。X 轴表示进程数，Y 轴表示以秒为单位的执行墙上时钟时间。

 

以下是我们在此次实验中使用的一个示例输出文件格式。

 

5.6 分析

在图 01 和图 02 中，单个进程的排序速度最快，随着进程数量的增加而变慢。然而，在图 03 中，执行时间从单个进程急剧下降到最快的执行时间（当两个进程并行运行时），然后随着进程数量的增加又开始变慢。最后，在图 04 和图 05 中，迭代和递归实现几乎具有相同的执行时间，排序速度随着进程的增加而加快，变化较小。图 06 的输入大小为一百万个数字。在这里，单进程排序是本次实验中最慢的，甚至在递归时停止。随着进程数量的增加，排序速度再次加快。在这些不同的图表中，我们可以清楚地观察到，总的来说，迭代 QuickSort 比递归版本更快。在单个进程的顺序执行中，输入量越小，排序越快，输入量越大，速度越慢。然而，在并行执行中，当输入大小和进程数都增加时，执行时间会减少。我们有时会注意到 MPI 执行时间的异常行为，它在每次执行后都会变化。我们只取了第一次执行时间来最小化这种变化并获得更一致的执行时间。

6 问题

这个项目最初计划在 Microsoft Windows 上使用 Cygwin 完成；然而，在 Cygwin 更新后遇到一些问题，我们转而使用虚拟机。下面展示了一个错误消息的截图。

然后我们在 Oracle VirtualBox 上安装的 Ubuntu 作为客户操作系统下安装了 CygWin。整个系统显得不太用户友好，有时速度极慢。由于硬件配置有限，我们只能使用 4 个进程，并建议使用 3 个进程。在将 CygWin 安装到 Ubuntu 上后，情况有所改善，Ubuntu 是一个正常的操作系统。

关于我们当前使用 Open MPI 实现的 QuickSort，存在某些不受欢迎的特性和限制，这些将在未来工作部分作为可能的未来研究方向提出。

7 结论

总结本项目，我们已经成功地使用 C 编程语言实现了递归和迭代版本的顺序 QuickSort 算法。然后，我们借助 Open MPI 库进行了并行实现。通过本项目，我们探索了 MPI 和 QuickSort 算法的不同方面以及它们各自的局限性。本研究表明，总的来说，顺序 QuickSort 在小输入上更快，而并行 QuickSort 在大输入上表现更优。研究还表明，总的来说，迭代版本的 QuickSort 比递归版本性能稍好。研究揭示了执行时间的某些异常行为，它们会意外地变化。然而，由于时间有限，我们无法克服所有困难和限制，下一节为未来的改进提供了一个潜在的范围。

8 未来工作

这个使用 MPI 的 QuickSort 并行实现可以通过以下方式解决其当前局限性来扩展或探索：

  • 输入大小不再总是能被进程数整除，可以使其更具动态性。
  • 可以使用点对点通信例程替换集合通信例程。
  • 收集本地排序数据并进行最终排序可以被一个 merge 函数替换。
  • 通过计算平均运行时间来最小化执行时间中观察到的一些变化。
  • 这个提出的算法可以用其他支持 Open MPI 的编程语言（如 C++、Java 或 Fortran）重新实现。

9 参考文献

  1. Rosetta code，网址：http://rosettacode.org/wiki/Sorting_algorithms/Quicksort，2015 年 12 月。
  2. P. Tsigas 和 Y. Zhang。Quicksort 的一种简单、快速的并行实现及其在 SUN Enterprise 10000 上的性能评估。载于 第十一届 Euromicro 并行、分布式和网络计算会议（Euro-PDP’03）论文集，2003 年，IEEE。
  3. HOARE, C. A. R. 1961。算法 64：Quicksort。Commun. ACM 4, 7, 321。
  4. Blaise Barney，劳伦斯利弗莫尔国家实验室，网址：https://computing.llnl.gov/tutorials/mpi/，2015 年 12 月。
  5. Rer. nat. Siegmar Groß，网址：http://www2.hsfulda.de/~gross/cygwin/cygwin_2.0/inst_conf_cygwin_2.0.x_x11r7.x.pdf，2015 年 12 月。
  6. D. G. Martinez, S. R. Lumley，Open MPI 并行和分布式编程的安装。
  7. P. Kataria，使用 MPI 和 Pthreads 的并行快速排序实现，2008 年 12 月。
  8. P. Perera，使用 MPI 的并行快速排序和性能分析。
  9. V. Prifti, R. Bala, I. Tafa, D. Saatciu 和 J. Fejzaj。用于数值排序的 Quicksort 算法并行化所获得的性能提升。载于 2015 年科学与信息会议，2015 年 6 月 28-30 日，IEEE。
  10. V. Gite，适用于 MS-Windows XP / Vista / 7 操作系统的 UNIX 命令行工具，网址：http://www.cyberciti.biz/faq/unix-command-line-utilities-for-windows/，2015 年 12 月。
  11. Open MPI：开源高性能计算，网址：https://www.open-mpi.org/，2015 年 12 月。

10 历史

  • 2016 年 3 月 3 日：初稿。
© . All rights reserved.