跨层精度自动调节的k均值聚类近似计算方法

doi:10.19665/j.issn1001-2400.2020.03.007

Abstract

Abstract:

With the application of artificial intelligence on the embedded platform, the k-means clustering algorithm, as the basis of the artificial intelligence method, is implemented on the embedded platform. Energy consumption is the key for the algorithm implementation on the embedded platform. In order to reduce the energy consumption of the k-means on the embedded platform, an approximate computing method based on cross-layer dynamic precision scaling for the k-means is proposed. First, the iteration process is constrained from the distance between data point to centroid and data point change trend. And a dynamic precision scaling method is proposed. Then the data reorganization and access method of external memory is designed from the structural level, which can realize the access of approximate memory. In addition, the approximate adder and multiplier are designed which can automatically adjust the calculation accuracy. Finally, the approximate computing of the k-means is realized. Experimental results show that the proposed method can reduce the energy consumption by 55%~58% compared with the accurate computing without affecting the quality of clustering. The proportion of the energy saving is the highest.

Key words: approximate computing, dynamic precision scaling, k-means clustering, energy consumption

CLC Number:

TP18

LI Zhao,YUAN Wenhao,REN Chongguang,HUANG Chengcheng,DONG Xiaoxiao. Approximate computing method based on cross-layer dynamic precision scaling for the k-means[J].Journal of Xidian University, 2020, 47(3): 50-57.

Figures/Tables 7

References 18

[1]	WANG C, CHEN Z G, SHANG K, et al. Label-removed Generative Adversarial Networks Incorporating with K-Means[J]. Neurocomputing, 2019,361:126-136. doi: 10.1016/j.neucom.2019.06.041
[2]	刘景美, 韩庆庆, 沈志威, 等. 采用k均值聚类的物理层密钥生成方案[J]. 西安电子科技大学学报, 2019,46(1):8-13.
	LIU Jingmei, HAN Qingqing, SHEN Zhiwei, et al. Method for Secret Key Generation Using k-menas Clustering[J]. Journal of Xidian University, 2019,46(1):8-13.
[3]	REZA M N, NA I S, BAEK S W, et al. Rice Yield EstimationBased on k-means Clustering with Graph-cut Segmentation using Low-altitude UAV Image[J]. Biosystems Engineering, 2019,177:109-121. doi: 10.1016/j.biosystemseng.2018.09.014
[4]	刘永利, 郭呈怡, 刘静, 等. 结合FCS的多视图模糊聚类算法[J]. 西安电子科技大学学报, 2019,46(4):99-106.
	LIU Yongli, GUO Chengyi, LIU Jing, et al. Multi-view Fuzzy Clustering Algorithm Using FCS[J]. Journal of Xidian University, 2019,46(4):99-106.
[5]	CAPO M, PEREZ A, LOZANO J A. An Efficient Approximation to the k-means Clustering for Massive Data[J]. Knowledge-Based Systems, 2017,117:56-69. doi: 10.1016/j.knosys.2016.06.031
[6]	DENG T T, CROOKES D, SIDDIQUI F, et al. A New Real-time FPGA-based Implementation of k-means Clustering for Image [C]//Communications in Computer and Information Science: 924(2). Heidelberg: Springer Verlag, 2018: 468-477.
[7]	AMATO F, BARBARESCHI M, COZZOLINO G, et al. Outperforming Image Segmentation by Exploiting Approximate k-means Algorithm [C]//Springer Proceedings in Mathematics and Statistics: 217. New York: Springer New York LLC, 2017: 31-38.
[8]	HU J J, LI Z J, YANG M, et al. A High-accuracy Approximate Adder with Correct Sign Calculation[J]. Integration, 2019,65:370-388. doi: 10.1016/j.vlsi.2017.09.003
[9]	JAVED R H, SIDDIQUE A, HAFIZ R, et al. ApproxCT:Approximate Clustering Techniques for Energy Efficient Computer Vision in Cyber-physical Systems [C]//Proceedings of the 2018 International Conference on Open Source Systems and Technologies. Piscataway: IEEE, 2018: 64-70.
[10]	HUANGP H, WANG C H, MA R Z, et al. A Hardware/Software Co-design Method for Approximate Semi-supervised k-means Clustering [C]//Proceedings of the 2018 IEEE Computer Society Annual Symposium on VLSI. Washington: IEEE Computer Society, 2018: 575-580.
[11]	SAEGUSA T, MARUYAMA T. An FPGA Implementation of k-means Clustering for Color Images Based on Kd-tree [C]//Proceedings of the 2006 International Conference on Field Programmable Logic and Applications. Washington: IEEE Computer Society, 2006: 567-572.
[12]	TIAN Y, ZHANG Q, WANG T, et al. ApproxMA: Approximate Memory Access for Dynamic Precision Scaling [C]//Proceedings of the 2015 ACM Great Lakes Symposium on VLSI. New York: ACM, 2015: 337-342.
[13]	FADAEI A, KHASTEH S H. Enhanced k-means Re-clustering over Dynamic Network[J]. Expert Systems with Application, 2019,132:126-140. doi: 10.1016/j.eswa.2019.04.061
[14]	YU S S, CHU S W, WANG C M, et al. Two Improved k-means Algorithm[J]. Applied Soft Computing Journal, 2018,68:747-755. doi: 10.1016/j.asoc.2017.08.032
[15]	ZHANG G, ZHANG C C, ZHANG H Y. Improved k-means Algorithm Based on Density Canopy[J]. Knowledge-Based Systems, 2018,145:289-297. doi: 10.1016/j.knosys.2018.01.031
[16]	CHIPPA V K, MOHAPATRA D, ROY K, et al. Scalable Effort Hardware Design[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2014,22(9):2004-2016. doi: 10.1109/TVLSI.2013.2276759
[17]	ZHANG Q, XU Q. ApproxIt: a Quality Management Framework of Approximate Computing for Iterative Methods[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017,148(11):1-13.
[18]	CHIPPA V K, ROY K, CHAKRADHAR S T, et al. Managing the Quality vs. Efficiency Trade-off Using Dynamic Effort Scaling[J]. Transactions on Embedded Computing Systems, 2013,12(2):90.

数据集	功耗
数据集	Proposed	ApproxMA	HAA	DES
Iris	5.757	5.962	6.457	6.157
Breasttissue	5.783	5.998	6.487	6.187
Seeds	5.790	6.157	6.517	6.199
Glass	5.792	6.174	6.527	6.207

Approximate computing method based on cross-layer dynamic precision scaling for the k-means

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 18

Related Articles 9

Metrics

Comments

Recommended 10

[1]	ZHANG Chunxiang,ZHOU Xuesong,GAO Xueyao,LIU Huan. Semi-supervised word sense disambiguation by combining k-means clustering and the LSTM network [J]. Journal of Xidian University, 2021, 48(6): 161-171.
[2]	LI Jinze,WANG Zhonghao,LI Mengheng,QIN Tuanfa. Spectrum sharing management method for the small-area-blockchain based on district partition [J]. Journal of Xidian University, 2020, 47(6): 122-130.
[3]	XING Lidong;LI Tao;HUANG Hucai;HAN Jungang. Energy consumption estimation for 3D graphics rendering [J]. Journal of Xidian University, 2017, 44(4): 40-46+74.
[4]	ZHANG Wenzhu;CAO Beibei;ZHOU Xueting. Energy-efficient computation offloading strategy for the terminal in mobile cloud environment [J]. Journal of Xidian University, 2017, 44(3): 175-180.
[5]	WANG Yunfei;BI Duyan;LIU Huawei;LIU Ling;ZHAO Xiaolin. Locally-restricted regular clustering superpixel algorithm [J]. Journal of Xidian University, 2016, 43(3): 95-100.
[6]	LIU Xing;YUAN Chaowei;YANG Zhen;LI Zhenjun. Services promote Lyapunov-based strategy in mobile cloud computing [J]. J4, 2015, 42(6): 138-144.
[7]	ZANG Mingxiang;WANG Ting;ZHOU Wenhong. Low energy consumption NoC mapping algorithm based on the modified electromagnetism-like mechanism [J]. J4, 2014, 41(4): 82-86+93.
[8]	WANG Ju;FANG Dingyi;CHEN Xiaojiang;XING Tianzhang;ZHANG Yuan;GAO Baojian. Data compression of wireless sensor networks in the heritage monitor [J]. J4, 2012, 39(1): 157-162.
[9]	ZHANG Jianxian;ZHOU Duan;YANG Yintang;LAI Rui;GAO Xiang. Low energy consumption mapping algorithm for the network-on-chip [J]. J4, 2011, 38(4): 95-100.