模糊C均值聚类算法的并行化研究
摘 要：使用Intel Parallel Amplifier高性能工具，针对模糊C均值聚类算法在多核平台的性能问题，找出串行程序的热点和并发性，提出并行化设计方案。基于Intel并行库TBB(线程构建模块)和OpenMP运行时库函数，对多核平台下的串行程序进行循环并行化和任务分配的并行化设计。
关键词：多核；并行化；模糊C均值算法；Intel Parallel Amplifier；OpenMP
多核处理器的迅速发展，使得多核化不断全面普及。为了应对计算机硬件的发展要求，尽可能利用多核资源，就要设计出相应的并行化应用程序。多核平台下的并行化有多种方案，利用英特尔推出的高性能分析工具Intel Parallel Amplifier对串行应用程序进行性能分析，寻出热点实现并行化是其中的一种方法。
模糊C均值聚类算法(FCM)是一种常用的聚类算法，在大规模数据分析、数据挖掘、模式识别、图像处理等领域有着非常广泛的应用。它是给定分类数，通过优化目标函数得到样本点对聚类中心的隶属度，寻找样本点的最佳分类方案。本文将多核技术应用到模糊C均值聚类并行算法的设计中，把目标函数迭代的过程和处理数据的过程并行化，提高聚类过程的效率及多核处理器的利用率。实验结果表明，本方法减少了程序的运行时间，显示了多核编程的高效性。
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并行编程模型
