炼数成金 门户 CUDA 查看内容

使用OpenMP让程序可并行化

2015-9-11 14:56| 发布者: 炼数成金_小数| 查看: 1354| 评论: 0|来自: shellsec

摘要: OpenMP就是其中一种,在实际的使用之后,感觉OpenMP是一种很方便的并行计算工具,它能够提供线程级别的并行化,所以OpenMP一般用于共享内存的单机系统。本文将以K-Means算法作为样例来进行讲解。在介绍算法之前,先 ...

tm 算法 测试 案例 并行计算

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

热身完毕后进入正题。

K-Means算法是一种聚类算法,顾名思义,它进行划分的方法是依赖于计算均值,算法的整体流程非常简单,假如要把样本分为M个类别:
在样本集N中随机选取M个个体,作为初始类心;
遍历样本中的所有个体,每个个体都与当前的M个类心分别求距离,并将自己和距离最小的那个类心归为一类;
通过平均值的方法计算每一类点集的中心作为该类新的类心
若类心在两次迭代中不再发生变化,则计算结束,否则回到第二步继续迭代

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

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

void KMeans(Point input[], Point output[], int N, int M)  {   // 随机选取M个点作为初始类心   int rndNum(0), tmp(N);   int* rndArr = new int[N];   for(int i(0); i < N; ++i)   rndArr[i] = i;   for(int i(0); i < M; ++i)   {   rndNum = rndArr[rand() % tmp--];   output[i] = input[rndNum];   rndArr[rndNum] = rndArr[tmp];   }   // 迭代   int* countNum = new int[M]; // 类别对应点数目   double* sumX = new double[M]; // 类别对应X的和   double* sumY = new double[M]; // 类别对应Y的和   bool flag; // 迭代标记     double d, minD;   double tmpX, tmpY;   do   {   flag = false;   // 标记点   for(int i(0); i < N; ++i)   {   minD = INF;   for(int j(0); j < M; ++j)   {   d = DistanceS(input[i], output[j]);   if(d < minD)   {   minD = d;   input[i].type = j; // 标记类别   }   }   }   // 计算新类心   memset(countNum, 0, sizeof(int) * M);   memset(sumX, 0, sizeof(double) * M);   memset(sumY, 0, sizeof(double) * M);   for(int i(0); i < N; ++i)   {   countNum[input[i].type]++;   sumX[input[i].type] += input[i].x;   sumY[input[i].type] += input[i].y;   }   for(int i(0); i < M; ++i)   {   tmpX = sumX[i] / countNum[i];   tmpY = sumY[i] / countNum[i];   if(abs(tmpX - output[i].x ) > LIMIT || abs(tmpY - output[i].y ) > LIMIT)   flag = true;   output[i].x = tmpX;   output[i].y = tmpY;   }   }while (flag);  }
void KMeans ( Point input [ ] , Point output [ ] , int N , int M )

{

     // 随机选取M个点作为初始类心

     int rndNum ( 0 ) , tmp ( N ) ;

     int * rndArr = new int [ N ] ;

     for ( int i ( 0 ) ; i < N ; ++ i )

         rndArr [ i ] = i ;

     for ( int i ( 0 ) ; i < M ; ++ i )

     {

         rndNum = rndArr [ rand ( ) % tmp — ] ;

         output [ i ] = input [ rndNum ] ;

         rndArr [ rndNum ] = rndArr [ tmp ] ;

     }

     // 迭代

     int * countNum = new int [ M ] ;          // 类别对应点数目

     double * sumX = new double [ M ] ;      // 类别对应X的和

     double * sumY = new double [ M ] ;      // 类别对应Y的和

     bool flag ;      // 迭代标记

     double d , minD ;

     double tmpX , tmpY ;

     do

     {

         flag = false ;

         // 标记点

         for ( int i ( 0 ) ; i < N ; ++ i )

         {

             minD = INF ;

             for ( int j ( 0 ) ; j < M ; ++ j )

             {

                 d = DistanceS ( input [ i ] , output [ j ] ) ;

                 if ( d < minD )

                 {

                     minD = d ;

                     input [ i ] . type = j ;      // 标记类别

                 }

             }

         }

         // 计算新类心

         memset ( countNum , 0 , sizeof ( int ) * M ) ;

         memset ( sumX , 0 , sizeof ( double ) * M ) ;

         memset ( sumY , 0 , sizeof ( double ) * M ) ;

         for ( int i ( 0 ) ; i < N ; ++ i )

         {

             countNum [ input [ i ] . type ] ++ ;

             sumX [ input [ i ] . type ] += input [ i ] . x ;

             sumY [ input [ i ] . type ] += input [ i ] . y ;

         }

         for ( int i ( 0 ) ; i < M ; ++ i )

         {

             tmpX = sumX [ i ] / countNum [ i ] ;

             tmpY = sumY [ i ] / countNum [ i ] ;

             if ( abs ( tmpX – output [ i ] . x ) > LIMIT || abs ( tmpY – output [ i ] . y ) > LIMIT )

                 flag = true ;

             output [ i ] . x = tmpX ;

             output [ i ] . y = tmpY ;

         }

     } while ( flag ) ;

}

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

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

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

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

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

#pragma omp parallel for private(minD, d, i, j)   for(i = 0; i < N; ++i)   {   minD = INF;   for(j = 0; j < M; ++j)   {   d = DistanceS(input[i], output[j]);   if(d < minD)   {   minD = d;   input[i].type = j; // 标记类别   }   }   }
#pragma omp parallel for private(minD, d, i, j)

         for ( i = 0 ; i < N ; ++ i )

         {

             minD = INF ;

             for ( j = 0 ; j < M ; ++ j )

             {

                 d = DistanceS ( input [ i ] , output [ j ] ) ;

                 if ( d < minD )

                 {

                     minD = d ;

                     input [ i ] . type = j ;      // 标记类别

                 }

             }

         }

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

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

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

5类

5,000,000个点

点横纵坐标的取样范围[0, 10000]
使用OpenMP让程序可并行化
使用OpenMP让程序可并行化

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

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

测试结果如下所示:

使用OpenMP让程序可并行化

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

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

鲜花

握手

雷人

路过

鸡蛋

最新评论

热门频道

  • 大数据
  • 商业智能
  • 量化投资
  • 科学探索
  • 创业

即将开课

热门文章

     

    GMT+8, 2020-1-21 18:52 , Processed in 0.172918 second(s), 23 queries .