基于GPU和CPU协同处理实现的Canopy算法探索 |
| 2012-06-21 11:30 作者：冯 楠 来源：硅谷网-《硅谷》杂志 HV： 编辑： 【搜索试试】
|
|
摘要：提出一种基于GPU（图形处理器）和CPU协同处理实现来提高聚类算法Canopy的计算效率的优化方案。利用GPU高效的并行性和灵活的可编程性等特点，将Canopy聚类算法中比较耗时的距离计算及与阈值T，T的比较步骤交由GPU处理，算法其余步骤仍由CPU处理，理论上提高算法速度。
关键词：GPU；聚类；Canopy
中图分类号：TP391文献标识码：A文章编号：1671—7597（2012）0510
0引言
【《硅谷》杂志2012年5月刊文】
Canopy聚类算法是一个聚类效果好、非常高效、适用范围广的方法。它使用非常轻量的距离量度（本文使用欧几里得距离作为相异度标量）把数据划分到重叠的区域中，是对传统聚类算法的预处理。Canopy聚类算法的主要过程为：
1）设有一个数据点集合S和预设的两个距离阈值：T，T（其中T＞T）；
2）从数据点集合S中任选一点p，计算点p与所有CanopyCenter之间的距离（如果当前不存在CanopyCenter，则把点p作为一个CanopyCenter），如果点p与某个CanopyCenter距离小于T，则点p加入到这个Canopy中；
3）如果点p与某个CanopyCenter的距离小于T，则将点p从数据点集合S中删除（这里是认为当前点p与这个CanopyCenter已经够近了，因此它不能再作为其他Canopy的中心）；
4）重复步骤2、3，直到数据点集合S为空为止。
1基于GPU的Canopy聚类算法实现
通过对Canopy聚类算法和GPU通用计算的研究，将Canopy聚类算法转化为GPU纹理渲染过程，利用GPU高效的并行性和灵活的可编程性等特点，提高算法速度。
1.1并行策略分析
从上文对Canopy聚类算法主要过程的介绍中可以发现，并行点主要集中在第2、3这两个步骤，即计算数据点与某个CanopyCenter的距离，最终生成Canopy的过程，这个过程交由GPU处理；而新CanopyCenter的生成交由CPU处理。
1.2GPU中的数据点存储
GPU中并行计算处理的对象为纹理图像，纹理图像的每个像素包含（r，g，b，a）4个颜色通道，每个颜色通道用一个32位浮点数表示。为了利用GPU实现Canopy聚类计算，数据点的一个度量值存储在一个像素的一个通道内。当数据点的度量维数d高于4维时，可以使用多个纹理的相对应的像素通道存储数据点的各个度量值。
假设有一组N个数据点的集合S={X，X，X，…，X}待聚类，其中X（1≤i≤N）具有d个可度量值。我们可以使用一个通道存储一个数据点的一个度量值，即使用一个包括⌈d/4⌉张像素个数为N的纹理组来存储相应数据。下面以一组有16个数据点，其中每个数据点有16个可度量值的待聚类集合S的纹理表示为例，说明数据点的存储和距离计算方法，如图1。
数据点X（x，x，x，x，x，x，x，x，x，x，x，x，x，x，x，x）
数据点X（x，x，x，x，x，x，x，x，x，x，x，x，x，x，x，x）
中心点X（x，x，x，x，x，x，x，x，x，x，x，x，x，x，x，x）
图1数据点的纹理表示
计算距离时，对各个纹理进行与CanopyCenter相对应度量值的距离计算后，累加各距离值，最后利用深度缓存保存该值。基于欧几里德距离值的平方仍保持原距离值间的大小关系不变，因而该文利用欧几里德距离值的平方作为相似性度量值。如下式：
D（X，X）=++…+=
但是，对于Canopy聚类算法来说，还需要引入某种机制来存储数据点所属的Canopy的标号。通常，一个模板缓存对应一个像素，因而可以将数据点所属的Canopy标号存储在对应的模板缓存中的模板值中。
1.3距离与Canopy标号的计算
利用GPU的子素处理器具有可编程的特点，可以使用子素程序进行纹理检索和数学计算，从而更新子素的颜色和深度值。实际上，更新的子素深度值可以是输入子素的颜色和坐标的函数值。该文将使用子素程序进行数据点和CanopyCenter间的距离计算。同时允许进行深度测试，确保仅当后面计算得到的子素深度值小于深度缓存中记录的深度值时，执行更新深度缓存操作，进而完成“不能作为CanopyCenter”的数据点的记录。
Canopy标号计算过程如下：
1）初始化深度缓存中的深度值为T；
2）初始化模板缓存中的模板值为1，即假设所有的数据点所属的Canopy标号为1；
3）进行深度测试，确保仅当后面计算得到的子素深度值小于深度缓存中记录的深度值时，执行更新深度缓存操作；
4）模板测试设置为一直通过状态，仅当子素深度值D<T时，更新与X对应的模板值为当前Canopy的标号；
5）当数据点集合S为空时，模板缓存中的模板值保存了各个数据点所属的Canopy的标号，而深度缓存中则保存了各个数据点到CanopyCenter间的距离。
2整体过程概述
首先由GPU初始化CanopyCenter和深度缓存值；然后计算所有数据点与CanopyCenter的距离并与两个距离阈值T，T进行比较，结果记录在深度缓存和模板缓存中；将所有D<T的数据点X的标号传送到CPU中；CPU将这些数据点从数据点集合S中删除，然后随机从集合S中取出1个数据点作为新的CanopyCenter连同其标号一起回传给GPU。重复上述过程，当数据点集合S为空时结束。主要流程如图2。（注：本文版权归作者本人和硅谷杂志所有，禁止他人未经授权转载）
|
|
|
|
【对“基于GPU和CPU协同处理实现的Canopy算法探索”发布评论】 |
版权及免责声明：
① 本网站部分投稿来源于“网友”，涉及投资、理财、消费等内容，请亲们反复甄别，切勿轻信。本网站部分由赞助商提供的内容属于【广告】性质，仅供阅读，不构成具体实施建议，请谨慎对待。据此操作，风险自担。
② 内容来源注明“硅谷网”及其相关称谓的文字、图片和音视频，版权均属本网站所有，任何媒体、网站或个人需经本网站许可方可复制或转载，并在使用时必须注明来源【硅谷网】或对应来源，违者本网站将依法追究责任。
③ 注明来源为各大报纸、杂志、网站及其他媒体的文章，文章原作者享有著作权，本网站转载其他媒体稿件是为传播更多的信息，并不代表赞同其观点和对其真实性负责，本网站不承担此类稿件侵权行为的连带责任。
④ 本网站不对非自身发布内容的真实性、合法性、准确性作担保。若硅谷网因为自身和转载内容，涉及到侵权、违法等问题，请有关单位或个人速与本网站取得联系（联系电话：01057255600），我们将第一时间核实处理。
|
|
