在《并行计算》这门课程中我了解到了很多使程序并行化的方法,OpenMP就是其中一种,在实际的使用之后,感觉OpenMP是一种很方便的并行计算工具,它能够提供线程级别的并行化,所以OpenMP一般用于共享内存的单机系统。本文将以K-Means算法作为样例来进行讲解。在介绍算法之前,先做一下热身运动,OpenMP库已经在Visual Studio 2013中集成(前几个版本似乎也有),所以你可以很轻松的为你的Visual Studio项目添加OpenMP支持,在项目属性中,如图所示的地方开启OpenMP支持即可:

1

热身完毕后进入正题。

K-Means算法是一种聚类算法,顾名思义,它进行划分的方法是依赖于计算均值,算法的整体流程非常简单,假如要把样本分为M个类别:

  1.        在样本集N中随机选取M个个体,作为初始类心;
  2.        遍历样本中的所有个体,每个个体都与当前的M个类心分别求距离,并将自己和距离最小的那个类心归为一类;
  3.        通过平均值的方法计算每一类点集的中心作为该类新的类心
  4.        若类心在两次迭代中不再发生变化,则计算结束,否则回到第二步继续迭代

通过这样的算法,我们就可以把整个样本划分为M类,在数据集优秀、距离公式恰当且初始类心选择科学的情况下,K-Means算法的聚类效果是很好的。在本文中,我选取最简单的“教学案例”来描述这个算法,毕竟本文的重点是OpenMP的使用。

下面给出“串行版”K-Means算法,这个算法用来对一个二维点集进行运算:

 

 

看这段代码,注释已经写得很明白了,整个程序也很简单,就是按照前文所描述的那四个步骤,那么我们来思考如何将其并行化。

首先就是找瓶颈,理论上程序中的所有前后无关的循环都可以并行化,但是对于一个算法而言,我们只要优化最值得优化的核心部分,就可以获得极高的整体提升。

显然迭代是无法并行化的,因此我们将注意力集中到迭代的内部过程,其中最核心的部分就是将每个点与类心求距离并标记归类,这里请额外关注高亮的那两层循环,在学习算法的时候爸爸妈妈都说过(?),最内层循环体中的代码对整体效率的影响最大,那我们是否就要将内层循环并行化呢?答案是:错!

首先我们并行提高效率的根本作用是,让多个步骤可以同时进行,那么为我们能让多少个步骤同时进行呢?通常你的CPU有几个核心,最大的并行度就是几,外层循环的参数是N – 样本总数,内层循环M – 类别数目,通常情况下N >> M,因此应当将这种双层循环视为单层,才有助于充分利用机器的并行度。

接下来则是见证奇迹的时刻,在双层循环的代码的加上简单的一句话,变成这样:

 

 

这句话让接下来的for语句并行执行,private是声明了四个线程内的私有变量,这样for内部的这四个变量在各个线程中就可以独立存在互不影响了。

不过等等……就样就完成了。WTF?

这是真的……整个程序只加这样一句话就可以了!用实验数据说话,下图是测试用的点集,是用我老师提供的一个小程序随机生成的,参数如下:

5类

5,000,000个点

点横纵坐标的取样范围[0, 10000]

2

由于此数据集的文本文档太大,在这里不予提供,上图可以很好的描述数据的分布状况,算法的结果也大致相符(要注意,K-Means的收敛次数和初始点的选取相关度是很大的,而且最终收敛的结果也同样受此影响,因此测试结果包括时间都会有一定的波动)。

测试用的机器是4核心8线程的。

测试结果如下所示:

3

串行中有一次执行得非常快速,应该是得益于初始类心的选择非常优秀,但从平均情况来说,还是很能说明情况的。最后的加速比还是很符合预期的,电脑总共就四个核心嘛~不过由于有一个特优数据,导致最终加速比超过了4,无伤大雅。

使用OpenMP可以让计算密集型的程序在恰当的时候充分利用整台机器的性能,当然它的用法很丰富,还提供了规约等方法,这里只是以最简单的例子来给大家展示,使用OpenMP来让你的程序并行执行,是多么的轻松:P

说点什么

  Subscribe  
提醒