第4期 申彦，等：CMP上基于数据集划分的K-means多核优化算法 ·611- 验，所以需要针对不同实验平台中不同类型的CPU 个数据点的所属类别、计算簇中心以及计算准则函 进行测试。HPPR03380MT平台采用的CPU是 数E这4个阶段均进行了并行化改进。且在这4个 Intel i3-3240@3.40GHz,核心类型为Ivy Bridge,64 阶段中，每个数据点的任务量是相当的，因此MC-K- 位CPU,双核，四线程，支持超线程技术，3MB三级 means算法所采取的等分数据集的方法可以取得较 缓存，双通道。HP ProLiant DL388pGen8平台采用 好的负载均衡性，算法取得了对比算法中最高的加 的CPU是Intel Xeon E5-2609@2.40GHz,核心类型 速率。 为Sandy Bridge,64位CPU,四核，四线程，10MB三 PKMeans_.MT算法取得了较低的加速率。分析 级缓存，四通道。 算法可知，该算法仅在读取数据集以及迭代计算每 对比算法为文献[l5]描述的基于MapReduce 个数据点的归属时利用parfor函数进行了并行化。 的并行K-means算法(PKMeans_MR)以及文献[l6] 对新分类中心点的计算及准则函数的计算均没有并 描述的PKMeans_.MT算法。在实验中根据上述文 行化，且算法需要依托MATLAB平台，故取得了较 献描述的算法思想分别实现了各算法进行对比实 低的加速率。 验。因为相同初始化条件下各算法最终聚类的结果 PKMeans_.MR算法在对比算法中取得了最低的 是一样的，所以实验主要对比分析相关算法的执行 加速率。分析算法可知，PKMeans_.MR算法改进原 时间以及加速率情况。 K-means算法，使其以MapReduce方式运行，节点之 4.1人工生成数据集测试 间在迭代时需要多次通信、多次同步，且算法需适应 人工生成数据集由数据生成程序根据K个高 MapReduce固有模式，降低了算法的运行效率，因此 斯分布随机产生，每个高斯分布设置一个随机权重 取得了最低的加速率。但对比原K-means算法仍提 来确定是否产生数据。每一个高斯分布的中心是随 高了一倍多的运行效率。 机产生的，区间为[-5,5]。数据点每个维度值的产 可以看出，对K-means进行并行化改进，适应了 生区间为[0.7,1.5]。产生的人工数据集包含100 多核CPU的发展趋势，可以极大程度提高算法的运 维，180000个数据点，数据集使用二进制bin文件 行效率，满足处理大规模数据集的需要。 保存。本次实验因为数据集以及聚类测试算法是在 同一台计算机上的，所以读取数据集时的阻塞系数 30 28.24 25.28 blockCoefficient设置为0。聚类簇数量设置为k=5。 整个实验随机产生5个不同的人工生成数据 20 =5 集，针对每个数据集，分别执行MC-K-means、PK- 15 11.47 :水 PKMeans MR 10 1001 9.029.35 Means_.MR、PKMeans_MT以及K-means算法各I0 7.028 oK-means 次，各自共运行50次，最后以聚类时间的平均值作 5 为算法聚类效率的评价。实验结果如图2、3所示。 Intel Xeon E5-2609Intel i3-3240 该数据集较为规整，算法运行收敛较快。从实 操作平台 验结果可以看出：针对服务器领域的Xeon E5-2609, 图2运行时间对比 虽然主频较低，但依靠较大的L3缓存以及四通道 Fig.2 Comparison of run time 的内存控制器，使得各算法取得了较高的执行效率。 4.00r 3.60 K-means算法在该平台环境下执行消耗了25.28s, 3.50 3.10 PKMeans_.MR消耗了10.01s,PKMeans_MT消耗了 3.00 3.133.02 2.53 2.16 =5 2.50 8.15s,MC-K-means则需要7.02s。而在i3-3240所 2.00 MC-K-means 在平台环境下，K-means算法消耗了28.24s,PK- 翼 PKMeans MT 1.50 PKMeans MR 1.00 Means_MR消耗了11.47s,PKMeans_MT消耗了 0.50 9.35s,MC-K-means在该平台则需要9.02s。从并 0 Intel Xeon E5-2609 Intel i3-3240 行化改造后各算法的执行结果来看，在Xeon E5- 操作平台 2609所在平台，算法获得了更高的加速比。这主要 图3加速率对比 是由于Xeon E5-2609是四核四线程的，拥有真实的 Fig.3 Comparison of speedup rate 四核心，可以更好地并行完成各并行化算法划分的 逐步增大生成数据集的规模，生成的人工数据 多任务聚类工作。而3-3240是双核心的，依靠超 集为100维，分别包含180000个数据点，360000 线程技术实现的四线程并行，但是CPU的双物理核 个数据点，540000个数据点，720000个数据点， 心需要频繁的进行线程上下文的切换，消耗了一部 900000个数据点。在Intel Xeon E5-2609平台测试 分的运行时间，获得了较低的加速比。 每个算法的加速率。实验每次随机产生2个相同大 其中，MC-Kmeans算法在读取数据集、判断每验，所以需要针对不同实验平台中不同类型的 ＣＰＵ 进行测试。 ＨＰ ＰＲＯ ３３８０ ＭＴ 平台采用的 ＣＰＵ 是 Ｉｎｔｅｌ ｉ３⁃３２４０＠ ３．４０ ＧＨｚ，核心类型为 Ｉｖｙ Ｂｒｉｄｇｅ，６４ 位 ＣＰＵ，双核，四线程，支持超线程技术，３ ＭＢ 三级 缓存，双通道。 ＨＰ ＰｒｏＬｉａｎｔ ＤＬ３８８ｐ Ｇｅｎ８ 平台采用 的 ＣＰＵ 是 Ｉｎｔｅｌ Ｘｅｏｎ Ｅ５⁃２６０９＠ ２．４０ ＧＨｚ，核心类型 为 Ｓａｎｄｙ Ｂｒｉｄｇｅ，６４ 位 ＣＰＵ，四核，四线程，１０ ＭＢ 三 级缓存，四通道。 对比算法为文献［１５］ 描述的基于 ＭａｐＲｅｄｕｃｅ 的并行 Ｋ⁃ｍｅａｎｓ 算法（ＰＫＭｅａｎｓ＿ＭＲ）以及文献［１６］ 描述的 ＰＫＭｅａｎｓ＿ＭＴ 算法。 在实验中根据上述文 献描述的算法思想分别实现了各算法进行对比实 验。 因为相同初始化条件下各算法最终聚类的结果 是一样的，所以实验主要对比分析相关算法的执行 时间以及加速率情况。 ４．１ 人工生成数据集测试 人工生成数据集由数据生成程序根据 Ｋ 个高 斯分布随机产生，每个高斯分布设置一个随机权重 来确定是否产生数据。 每一个高斯分布的中心是随 机产生的，区间为［－５，５］。 数据点每个维度值的产 生区间为［０．７，１．５］。 产生的人工数据集包含 １００ 维，１８０ ０００ 个数据点，数据集使用二进制 ｂｉｎ 文件 保存。 本次实验因为数据集以及聚类测试算法是在 同一台计算机上的，所以读取数据集时的阻塞系数 ｂｌｏｃｋＣｏｅｆｆｉｃｉｅｎｔ 设置为 ０。 聚类簇数量设置为 ｋ ＝ ５。 整个实验随机产生 ５ 个不同的人工生成数据 集，针对每个数据集，分别执行 ＭＣ⁃Ｋ⁃ｍｅａｎｓ、 ＰＫ⁃ Ｍｅａｎｓ＿ＭＲ、ＰＫＭｅａｎｓ＿ＭＴ 以及 Ｋ⁃ｍｅａｎｓ 算法各 １０ 次，各自共运行 ５０ 次，最后以聚类时间的平均值作 为算法聚类效率的评价。 实验结果如图 ２、３ 所示。 该数据集较为规整，算法运行收敛较快。 从实 验结果可以看出：针对服务器领域的 Ｘｅｏｎ Ｅ５⁃２６０９， 虽然主频较低，但依靠较大的 Ｌ３ 缓存以及四通道 的内存控制器，使得各算法取得了较高的执行效率。 Ｋ⁃ｍｅａｎｓ 算法在该平台环境下执行消耗了 ２５．２８ ｓ， ＰＫＭｅａｎｓ＿ＭＲ 消耗了 １０．０１ ｓ，ＰＫＭｅａｎｓ＿ＭＴ 消耗了 ８．１５ ｓ，ＭＣ⁃Ｋ⁃ｍｅａｎｓ 则需要 ７．０２ ｓ。 而在 ｉ３⁃３２４０ 所 在平台环境下，Ｋ⁃ｍｅａｎｓ 算法消耗了 ２８． ２４ ｓ，ＰＫ⁃ Ｍｅａｎｓ＿ＭＲ 消耗了 １１． ４７ ｓ， ＰＫＭｅａｎｓ ＿ＭＴ 消耗了 ９．３５ ｓ，ＭＣ⁃Ｋ⁃ｍｅａｎｓ 在该平台则需要 ９．０２ ｓ。 从并 行化改造后各算法的执行结果来看，在 Ｘｅｏｎ Ｅ５⁃ ２６０９ 所在平台，算法获得了更高的加速比。 这主要 是由于 Ｘｅｏｎ Ｅ５⁃２６０９ 是四核四线程的，拥有真实的 四核心，可以更好地并行完成各并行化算法划分的 多任务聚类工作。 而 ｉ３⁃３２４０ 是双核心的，依靠超 线程技术实现的四线程并行，但是 ＣＰＵ 的双物理核 心需要频繁的进行线程上下文的切换，消耗了一部 分的运行时间，获得了较低的加速比。 其中，ＭＣ⁃Ｋｍｅａｎｓ 算法在读取数据集、判断每 个数据点的所属类别、计算簇中心以及计算准则函 数 Ｅ 这 ４ 个阶段均进行了并行化改进。 且在这 ４ 个 阶段中，每个数据点的任务量是相当的，因此 ＭＣ⁃Ｋ⁃ ｍｅａｎｓ 算法所采取的等分数据集的方法可以取得较 好的负载均衡性，算法取得了对比算法中最高的加 速率。 ＰＫＭｅａｎｓ＿ＭＴ 算法取得了较低的加速率。 分析 算法可知，该算法仅在读取数据集以及迭代计算每 个数据点的归属时利用 ｐａｒｆｏｒ 函数进行了并行化。 对新分类中心点的计算及准则函数的计算均没有并 行化，且算法需要依托 ＭＡＴＬＡＢ 平台，故取得了较 低的加速率。 ＰＫＭｅａｎｓ＿ＭＲ 算法在对比算法中取得了最低的 加速率。 分析算法可知，ＰＫＭｅａｎｓ＿ＭＲ 算法改进原 Ｋ⁃ｍｅａｎｓ 算法，使其以 ＭａｐＲｅｄｕｃｅ 方式运行，节点之 间在迭代时需要多次通信、多次同步，且算法需适应 ＭａｐＲｅｄｕｃｅ 固有模式，降低了算法的运行效率，因此 取得了最低的加速率。 但对比原 Ｋ⁃ｍｅａｎｓ 算法仍提 高了一倍多的运行效率。 可以看出，对 Ｋ⁃ｍｅａｎｓ 进行并行化改进，适应了 多核 ＣＰＵ 的发展趋势，可以极大程度提高算法的运 行效率，满足处理大规模数据集的需要。 图 ２ 运行时间对比 Ｆｉｇ． ２ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｕｎ ｔｉｍｅ 图 ３ 加速率对比 Ｆｉｇ． ３ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｓｐｅｅｄｕｐ ｒａｔｅ 逐步增大生成数据集的规模，生成的人工数据 集为 １００ 维，分别包含 １８０ ０００ 个数据点，３６０ ０００ 个数据点，５４０ ０００ 个数据点，７２０ ０００ 个数据点， ９００ ０００个数据点。 在 Ｉｎｔｅｌ Ｘｅｏｎ Ｅ５⁃２６０９ 平台测试 每个算法的加速率。 实验每次随机产生 ２ 个相同大 第 ４ 期 申彦，等：ＣＭＰ 上基于数据集划分的 Ｋ⁃ｍｅａｎｓ 多核优化算法 ·６１１·