基于图形处理器的层次聚类算法效率研究

doi:10.3778/j.issn.1002-8331.2008.31.015

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (31): 53-56.DOI: 10.3778/j.issn.1002-8331.2008.31.015

基于图形处理器的层次聚类算法效率研究

李琳¹,李肯立²

1.衡阳师范学院计算机科学技术系，湖南衡阳 421008
2.湖南大学计算机与通信学院，长沙 410082

收稿日期:2008-06-10 修回日期:2008-08-27 出版日期:2008-11-01 发布日期:2008-11-01
通讯作者: 李琳

Research on efficiency of hierarchical clustering algorithm based on Graphics Processing Unit

LI Lin¹,LI Ken-li²

1.Department of Computer & Science，Hengyang Normal University，Hengyang，Hunan 421008，China
2.College of Computer and Communication，Hunan University，Changsha 410082，China

Received:2008-06-10 Revised:2008-08-27 Online:2008-11-01 Published:2008-11-01
Contact: LI Lin

摘要/Abstract

摘要： 鉴于Larsen等人利用图形处理器（GPU）的多纹理技术做矩阵运算操作，以实现GPU在矩阵相乘方面的通用计算，提出一种利用GPU和CPU的协同处理模式，应用在基于层次聚类的动态近邻选择模型的聚类算法（DNNS）中，将算法中比较耗时的邻接度矩阵计算步骤交由GPU完成，而算法其余步骤由CPU执行，从而使算法的聚类效率得到显著提高。在配有Pentium IV 3.4 G CPU和NVIDIA GeForce 7800GT显卡的硬件环境下经过实验测试，证明这种协同处理模式下的运算速度比完全采用CPU计算速度要快25%左右。这种改进的层次聚类算法适合在数据流环境下对大量数据进行实时高效聚类操作。

关键词: 图形处理器, 通用计算, 划分聚类

Abstract: Referring to the matrix calculation operation with the multitexturing technique of Graphics Processing Units（GPU） proposed by Larsen，which is utilized to realize the general purpose computation on the matrix multiplication，one mode of GPU+CPU co-processing is brought forward.It is used in the hierarchical clustering algorithm using Dynamic Nearest Neighbors Selection （DNNS） Model.The step of computing connectivity matrix spending much time is finished by GPU，others are processed by CPU and it is very evident that the calculation efficiency is promoted.Experiments are conducted in a PC with Pentium IV 3.4G CPU and NVIDIA GeForce 7800 GT，the results of which indicates that the calculation speed under the mode of co-processing is 25% faster than that finished only by CPU.The improved hierarchical clustering algorithm is very useful for the operation on volumes of data under the environment of data stream at high speed and high quality.

Key words: Graphics Processing Units（GPU）, general purpose computation, hierarchical clustering algorithm

李琳¹,李肯立². 基于图形处理器的层次聚类算法效率研究[J]. 计算机工程与应用, 2008, 44(31): 53-56.

LI Lin¹,LI Ken-li². Research on efficiency of hierarchical clustering algorithm based on Graphics Processing Unit[J]. Computer Engineering and Applications, 2008, 44(31): 53-56.

[1]	杨捷，吴素萍. 点云重建的并行算法[J]. 计算机工程与应用, 2020, 56(6): 213-219.
[2]	朱超，吴素萍. 特征点检测DoG并行算法[J]. 计算机工程与应用, 2020, 56(10): 36-43.
[3]	范昱伶1，王美丽1，何东健2. 基于OpenCL的点云分割方法[J]. 计算机工程与应用, 2018, 54(1): 191-195.
[4]	丁祥武，陈金鑫，王梅. 异构计算平台上列存储系统的并行连接优化策略[J]. 计算机工程与应用, 2017, 53(5): 73-80.
[5]	刘高明1，2，荣葵2，朱辉1，谭怀亮2. 应用于嵌入式RTOS的图形显示系统设计[J]. 计算机工程与应用, 2016, 52(9): 190-195.
[6]	公维理. 基于嵌入式CPU-GPU的高清鱼眼视频实时校正系统[J]. 计算机工程与应用, 2016, 52(14): 172-179.
[7]	张延松1，2，苏明川1，张宇1，王方舟1. 位图连接索引服务机制研究[J]. 计算机工程与应用, 2015, 51(5): 107-115.
[8]	林敏，钟一文. 三种GPU并行的自适应邻域模拟退火算法[J]. 计算机工程与应用, 2015, 51(22): 70-76.
[9]	朱正东1，刘袁1，魏洪昌１，颜康1，王寅峰2，董小社1. 面向CPU-GPU架构的源到源自动映射方法[J]. 计算机工程与应用, 2015, 51(21): 41-47.
[10]	汪宏1，2，王鹏1，2. 基于GPU的AC模式匹配改进算法[J]. 计算机工程与应用, 2015, 51(18): 7-12.
[11]	曾博1，2，雷友诚1，王丛知2，邱维宝2，冯歌2，曾成志2，杨戈2，郑海荣2. 基于CUDA的声辐射力弹性成像算法研究[J]. 计算机工程与应用, 2015, 51(18): 249-254.
[12]	龙满生，罗文浪. 基于OpenCL的累积汇流并行计算[J]. 计算机工程与应用, 2014, 50(3): 22-29.
[13]	唐绍华. 面向众核GPU加速系统的网络编码并行化及优化[J]. 计算机工程与应用, 2014, 50(21): 79-84.
[14]	蒋建洪1，罗玫2. 电子商务卖方数据聚类方法的改进研究[J]. 计算机工程与应用, 2013, 49(8): 27-31.
[15]	张兵强1，张立民1，李垠广2，张建廷1. 分块LOD连续非线性分布的地形渲染[J]. 计算机工程与应用, 2013, 49(4): 213-218.

基于图形处理器的层次聚类算法效率研究

Research on efficiency of hierarchical clustering algorithm based on Graphics Processing Unit

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics