浅谈模糊C均值聚类算法的并行化研究

　　摘  要： 使用Intel Parallel Amplifier高性能工具，针对模糊C均值聚类算法在多核平台的性能问题，找出串行程序的热点和并发性，提出并行化设计方案。基于Intel并行库TBB（线程构建模块）和OpenMP运行时库函数，对多核平台下的串行程序进行循环并行化和任务分配的并行化设计。

　　并行性主要是指同时性或并发性，并行处理是指对一种相对于串行处理的处理方式，它着重开发计算过程中存在的并发事件。并行性通常划分为作业级、任务级、例行程序或子程序级、循环和迭代级以及语句和指令级。作业级的层次高，并行处理粒度粗。粗粒度开并行性开发主要采用MIMD方式，而细粒度并行性开发则主要采用SIMD方式。开发计算机并行性的方法主要有：资源重复、时间重叠和资源共享三种方法。

　　多核处理器的迅速发展，使得多核化不断全面普及。为了应对计算机硬件的发展要求，尽可能利用多核资源，就要设计出相应的并行化应用程序。多核平台下的并行化有多种方案，利用英特尔推出的高性能分析工具Intel Parallel Amplifier对串行应用程序进行性能分析，寻出热点实现并行化是其中的一种方法。

　　多核架构能够使用的软件更出色地运行，并创建一个促进未来的软件编写更趋完善的架构。尽管认真的软件厂商还在探索全新的软件并发处理模式，但是，随着向多核处理器的移植，已有软件无需被修改就可支持多核平台。操作系统专为充分利用多个处理器而设计，且无需修改就可运行。为了充分利用多核技术，应用开发人员需要在程序设计中融入更多思路，但设计流程与对称多处理 （SMP） 系统的设计流程相同，并且单线程应用也继续运行。

　　多内核（multicore chips）是指在一枚处理器（chip）中集成两个或多个完整的计算引擎（内核）。多核技术的开发源于工程师们认识到，仅仅提高单核芯片（one chip）的速度会产生过多热量且无法带来相应的性能改善，先前的处理器产品就是如此。他们认识到，在先前产品中以那种速率，处理器产生的热量很快会超过太阳表面。即便是没有热量问题，其性价比也令人难以接受，速度稍快的处理器价格要高很多。

　　模糊C均值聚类算法（FCM）是一种常用的聚类算法，在大规模数据分析、数据挖掘、模式识别、图像处理等领域有着非常广泛的应用。它是给定分类数，通过优化目标函数得到样本点对聚类中心的隶属度，把目标函数迭代的过程和处理数据的过程并行化，提高聚类过程的效率及多核处理器的利用率。实验结果表明，本方法减少了程序的运行时间，显示了多核编程的高效性。

　　1 模糊C均值聚类算法（FCM）

　　模糊C均值聚类算法[1]的基本思想是确定每个样本数据隶属于某个聚类的程度，把隶属程度相似的样本数据归为一个聚类。FCM把n个样本集合X={x1，x2，…，xn}分为c个模糊组，并且求每组的聚类中心Ci（i=1，2，…c），使得目标函数，该算法是优化目标函数的迭代过程。这个过程从一个随机的隶属度矩阵开始，确定聚类中心计算目标函数，通过迭代过程达到样本分类。

　　初始化：给定样本数n，聚类数c∈[2，n]，模糊度m=2，迭代停止阈值？棕。

　　（4）如果目标函数的改变量小于？棕，停止算法，否者重复（2）直到改变量小于？棕。为了确保FMC得到一个解，要不断调整隶属度矩阵，需多次运行该算法。

　　2 多核技术与工具软件

　　2.1 Intel Parallel Amplifier高性能工具

　　Intel Parallel Amplifier是英特尔在2009年发布的高性能工具[2]，界面设计友好，操作简单方便。开发人员只需要运行工具就可对串行程序进行分析，研究分析结果进行并行化设计，确保多核的完全利用。IPA（Intel Parallel Amplifier）有以下三种类型的性能分析。

　　（1）热点（Hotspot）分析：运行热点分析可收集到不同类型的数据，确定应用程序运行消耗的时间，以及识别出耗时的函数。在执行程序时，IPA通过数据收集器定期采样，并在操作系统的协作下中断程序收集数据。它通过获取整个程序各个CPU的指令指针（IP）采样，计算出每个函数的运行时间，再用调用栈采样为程序创建调用关系树。

　　（2）并发性（Concurrency）分析：运行并发性分析可确定应用程序是否有效地利用了所有可执行核，识别出有可能并行化的串行代码。它与热点分析一样收集数据信息，但是要比热点分析多，除了一般的程序运行数据，还有所有可执行核的工作情况。理想的情况是执行程序的线程数等于处理器的可执行核数，也就是完全利用（Fully Utilized）。

　　（3）锁定和等待（Locks and Waits）分析：在前两种分析的基础上，运行锁定和等待分析，可获得更多的程序运行数据。

　　为了测试程序并行优化的效果，IPA提供了“比较结果（Compare Results）”的功能，用来比较串行程序和并行程序性能差别。

　　2.2 TBB线程构建模块

　　TBB线程构建模块（Intel Thread Building Blocks）是基于GPLv2开源的、用来实现并行语义的C++模板库[3]。TBB提供了高性能可扩展的算法，面向任务编程，支持任何ISO C++编译器，具有很好的可移植性。本文将Intel并行库TBB的tbb_block_rang2d和tbb_parallel_for配合使用，前者的作用是对一个二维的半开区间进行可递归的粒度划分；后者的作用可以实现负载均衡的并行执行固定数目独立循环迭代体。

　　2.3 OpenMP并行编程模型

　　OpenMP是为共享内存以及分布式共享内存设计的多线程并行编程应用接口，包含了一套编译语句以及一个函数库，是一个编译指令和库函数的集合[4]。OpenMP也可以用于多核处理器并行程序设计中。在OpenMP中线程的创建是通过编译指导语句实现的，本文采用sections和section命令。sections被称作工作分区编码，它定义了一个工作分区，然后由section将工作区划分成几个不同的工作段，每个工作段都由多核处理器的每个执行核并行执行。

　　3 C均值聚类算法的并行优化设计

　　3.1 基本流程

　　C均值聚类算法串行程序的并行化设计可分为以下几个阶段：首先用IPA高性能工具得到热点函数的花费时间和并行情况，分析串行程序的可并行性[5]；然后运用TBB和OpenMP进行并行优化设计；使用IPA的Compare Results功能进行比较，测试并行程序的性能效果。基本流程如图1所示。

　　3.2 热点定位

　　通过“Hotspot”可以获得热点函数所花费的时间，调用栈信息可以得到它被不同函数调用花费的时间。IPA采集的数据为程序段花费的总时间、CPU运行的时间、CPU空闲时间、处理器的核数、执行程序的线程数等。找到热点函数后，打开源代码，分析哪些代码花费处理器时间多。

　　3.3 并发性分析

　　Concurrency分析可以得到热点函数在执行过程中各个其他任务并行执行的情况，以及各个线程的任务分配情况。IPA并发性分析不仅包含热点采集的时间数据，更重要的是程序的并发状态。它用5种不同状态（Idle、Poor、Ok、Ideal、Over）表示并发性的情况。在多核平台下，理想的状态应该达到Ok以上，也就是说当热点函数运行时，其他线程同时工作在处理器上，这样可以提高多核资源的利用率。

　　实行并行性的缘故，由于计算机和外部的设备不匹配，输入和输出极大地影响了效率。类如一台计算机的内存里只有一个程序在运行，该程序还不能处理的他为拥有的数据，并且只有在他获得数据后他可以继续执行下一步操作，影戏这个程序必须等待输入或输出。既然这个程序控制着个计算机，那么计算机也必须等待。使得一个计算机等待时间要远超过他处理数据实花的时间。为啥俩个程序不可以同时放进内存呢？一旦如此，程序A等待数据时，处理器就可以转向程序B。还可以继续推广，有俩个或更多的程序装入内存以便更好的利用内存。一般来说，装入内存的程序越多，处理器的利用率也就越高。

　　3.4 串行程序优化

　　通过分析源代码，可以对串行程序进行如图2所示的并行优化。

　　（1）因为隶属度矩阵的归一化和样本矩阵的标准化没有数据相关性，所以可以利用OpenMP的工作分区功能在两个线程中同时执行运算，提高多核的利用率，节省程序运行时间。使用OpenMP的优化设计：

　　#include <omp.h>

　　初始化数据

　　#pragma omp parallel sections//工作分区

　　{#pragma omp setion

　　样本数据标准化

　　#pragma omp section

　　隶属度矩阵归一化}

　　（2）归一化后的隶属度矩阵和标准化的样本数据做矩阵乘法的运算，可以使用TBB并行库进行优化设计[6-7]。TBB：：block_range2d表示的是二维迭代空间的模板类，它包含在头文件TBB/blocked_range.h中，作用是根据需求对并行任务正确的划分。因为矩阵相乘是二维空间的运算，因此采用block_range2d模板类。迭代空间划分好后，就可以使用TBB：：parallel_for执行并行操作。parallel_for包含在头文件TBB/parallel_for.h中，作用是对循环体进行并行化处理。使用TBB的优化设计：

　　#include “tbb/taske_scheduler_init.h”

　　# include ”tbb/parallel_for.h”

　　#include ”tbb/blocked_range2d.h”

　　task_scheduler_init init；//初始化对象

　　{//矩阵相乘的tbb并行化

　　parallelMul（）double c， double a，double b}{parallel _for（blocked_range2d<size_t> （0，k，0，n），MatrixlMul（c，a，b））；}

　　}

　　4 实验结果测试

　　本文采用UCI标准数据集中的Wine数据集作为测试实例，该数据集包含有178个样本，每个样本有13个属性特征，分为3类，每类分别为59，71，48，数据为178×13的矩阵。设定加权指数m=2，停止阈值ω=le-4。

　　（1）实验平台

　　硬件：Intel Pentium Dual T3400 @2.16 GHz 2.16 GHz，2 GB内存。

　　软件：Microsoft Windows XP professional service pack3操作系统；Visual.Studio.2008英文版；parallel_studio_ sp1_setup（评估版）；tbb22_009oss_win（TBB2.2版本）[8]。

　　为了检测并行优化的效果，要对测试结果、热点、并发性和串行程序进行对比。

　　（2）实验结果

　　经过实验测试获得Wine数据集3个分类的样本数，分别为59、64、48，与标准分类相比误差很小。本文通过5次运行FMC得到的实验结果相同，说明模糊C均值算法的并行优化设计是可行的。

　　（3）热点对比

　　从图3可以看到并行后热点函数Update执行时间减少为15.321 ms，这是由于Update函数中有二维矩阵的并行化设计。在双核平台下，串行程序的线程数为1，而并行程序的线程数为3。

　　表1是IPA中Compare Results功能的比较结果，各项时间的差值都为正数，表明性能提高。

　　（4）并发性对比

　　幷发的实质是一个物理CPU（也可以多个物理CPU）在若干道程序之间多路复用，并发性是对有限物理资源强制行驶多用户共享以提高效率。实现幷发技术的关键之一是如何对系统内的多个活动（进程）进行切换。并行性指的是两个或两个以上的事件或活动在同一时刻发生。在多道程序环境下，并行性使多个程序同一时刻可在不同CPU上同时执行。并行性和并发性的区别：并行的时间或者活动一定是幷发的，但是反之并发的时间或者活动未必是并行的。并行性是并发性的特例，而并发性是并行性的拓展。

　　从图4可以看到并行程序的并发效果。热点函数Update并行后不仅时间减少了，状态也由Poor变为Ideal。说明当热点函数运行时，其他线程同时运行在多核处理器上，多核利用率得到提高。

　　本文将Intel多核高性能工具应用到FMC串行程序的并行优化设计中，提出并行优化设计方案，把TBB和OpenMP引入到聚类算法的并行化设计中。并行聚类算法在处理海量数据时将大大节省时间，并且提高多核资源的利用率。下一步的工作是从并行算法的可扩展性进行探究，并在众核处理器上做进一步测试，以便更好地提高聚类算法效率。