GPU Hızlandırmalı Veri Demetleme Algoritmalarının İncelenmesi

Yıl 2013, Cilt: 4 Sayı: 11, 19 - 59, 01.04.2013

Nazire Merve Çetin Murat Hacıömeroğlu

https://doi.org/10.5824/1309-1581.2013.2.002.x

Öz

Veri demetleme algoritmaları, arama; spam, saldırı tespiti; hücre, gen, doküman analizi; moleküler dinamik simülasyonlarının biçimlerinin analizi gibi uygulamalar için oldukça önemlidirler. Veri demetleme algoritmaları için birçok araç geliştirilmiştir; ancak günümüzde teknolojinin hızla gelişmesiyle toplanan veri miktarı git gide artmaktadır. Veri miktarının artması, analizin neticesini olumlu etkilese de mevcut veri demetleme araçları, büyük-ölçekli veri kümeleriyle çalışan uygulamaların gereksinimlerini hız bakımından karşılayamaz hale gelmişlerdir. Veri demetlemede hızın rolü, veri madenciliği araştırma topluluğunun bir süredir ilgi alanındadır. Araştırmacılar, çeşitli optimizasyon tekniklerinden, veri yapısı tasarımlarından, CPU'da paralelleştirme tekniklerinden ve PC küme sistemi kullanımı gibi yöntemlerden yararlanmaktadırlar. Fakat son zamanlarda düşük maliyet ile yüksek performans sunan yeni bir yaklaşım tüm ilgiyi üzerine çekmiştir: Genel Amaçlı GPU Programlama GPGPU . GPU’ların yüksek paralel hesaplama gücü ve grafik kartlarındaki gelişimin CPU’ya oranla daha hızlı hızlanması, aslında grafik canlandırma ve oyunlar için yoğun matematiksel hesaplamalar yapmak üzere tasarlanan grafik kartlarından genel amaçlı programlar için de yararlanmayı söz konusu hale getirmiştir. Bu makalede, GPGPU yaklaşımıyla veri demetleme algoritmalarının performansını artıran çalışmalar incelenmiş, özetlenmiş, avantajlarından ve eksik yanlarından bahsedilmiştir. Sonuç olarak, bu yaklaşımının üstünlüğü göz önünde bulundurularak konuyla ilgili bilime katkı sağlanabilecek açık alanlar verilmiş ve incelenen çalışmalardan elde edilen GPGPU yaklaşımıyla uygulama geliştirirken dikkat edilmesi gereken hususlar ortaya konulmuştur

Anahtar Kelimeler

CUDA, hızlandırma için GPU, genel amaçlı gpu programlama GPGPU, grafik işlemci birimi GPU, paralel hesaplama, veri demetleme

Survey of GPU Accelerated Data Clustering Algorithms

Öz

Data clustering algorithms are quite important for applications such as search; spam, attack detection; cell, gene, document analysis; analysis of conformations of molecular dynamics simulations. Many tools are developed for data clustering algorithms. However, today technology is improving rapidly so that collected data amount grows more and more. Although increased data amount affects the result of analysis positively, when current data clustering tools work with large scale datasets, they don't meet the requirements of such that applications in terms of speed. Data mining research community is interested in the rol of speed on data clustering for a while. Researchers take advantage of methods such as various optimization techniques, data structure designs, parallel techniques on CPU, using PC cluster systems. However, recently a new approach which offers low cost and high performance, attracts all attention: General Purpose GPU Programming: GPGPU . Through high parallel computing power of GPUs and more rapid development of graphics carts than CPUs, it has become to benefit graphics carts, which design to do intensive mathematical computations, for general purpose programs. In this paper, we investigate works that increase performance of data clustering algorithms with GPGPU approach, summarize them, mention advantages and disadvantages of these works. In conclusion, considering the advantages of this approach, prospected areas in this matter that could contribute to the science are given and particular points in developing the application by GPGPU approach were exhibited from the outcomes of verified practices

Anahtar Kelimeler

CUDA, GPU for acceleration, general purpose programming GPGPU, graphic processor unit GPU, parallel computing, data clustering

Kaynakça

• Anderson, D., Luke, R., & Keller, J. (2007). Analysis and Design of Intelligent Systems using Soft Computing Techniques. P. Melin, O. Castillo, E.G.Ramírez, J. Kacprzyk, & W.Pedrycz (Dü). içinde Springer Berlin Heidelberg.
• Anderson, D., Luke, R., & Keller, J. (2008). Speedup of Fuzzy Clustering Through Stream Processing on Graphics Processing Units. IEEE Transactions on Fuzzy Systems, 16(4), 1101-1106.
• Bai, H., He, L., Ouyang, D., Li, Z., & Li, H. (2009). K-Means on commodity GPUs with CUDA. 2009 World Congress on Computer Science and Information Engineering (CSIE 2009), (s. 651-655). Los Angeles, California USA.
• Beckmann, N., Kriegel, H., Schneider, R., & Seeger, B. (1990). The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. Proc. ACM SIGMOD Int. Conf. on Management of Data, (s. 322-331). Atlantic City, New Jersey, USA.
• Ben-Dor, A., Shamir, R., & Yakhini, Z. (1999, Ekim). Clustering Gene Expression Patterns. Journal of Computational Biology, 6(3/4), 281-297.
• Bezdek, J. (1981). Pattern Recognition with Fuzzy Objective Function Algoritms. Kluwer Academic Publishers Norwell, MA, USA.
• Böhm, C., Noll, R., Plant, C., & Wackersreuther, B. (2009). Density-based clustering using graphics processors. CIKM '09: 18th ACM conference on Information and knowledge management, (s. 661- 670). Hong Kong, China.
• Böhm, C., Noll, R., Plant, C., Wackersreuther, B., & Zherdin, A. (2009). Transactions on Large-Scale Data- and Knowledge-Centered Systems I. A. H. and J. Küng, & R. Wagner (Dü). içinde Springer Berlin Heidelberg.
• BrookGPU. (2012, Aralık). BrookGPU. http://graphics.stanford.edu/projects/brookgpu/index.html adresinden alınmıştır
• C++ AMP (C++ Accelerated Massive Parallelism). (2012, Aralık). C++ AMP (C++ Accelerated Massive Parallelism). http://msdn.microsoft.com/en-us/library/vstudio/hh265137.aspx adresinden alınmıştır
• Cao, F., Tung, A., & Zhou, A. (2006). Scalable Clustering Using Graphics Processors. WAIM 2006: 7th International Conference on Advances in Web-Age Information Management, (s. 372-384). Hong Kong, China.
• Chang, D., Jones, N., Li, D., Ouyang, M., & Ragade, R. (2008). Compute pairwise euclidean distances of data points with GPUs. Proceedings of the IASTED International Symposium on Computational Biology and Bioinformatics (CBB 2008). Orlando, Florida, USA.
• Chang, D., Kantardzic, M., & Ouyang, M. (2009). Hierarchical clustering with CUDA/GPU. PDCCS'09: Proceedings of the ISCA 22nd International Conference on Parallel and Distributed Computing and Communication Systems, (s. 7-12). Cambridge, Massachusetts, USA.
• Che, S., Boyer, M., Meng, J., Sheaffer, D. T., & Skadron, K. (2008, Temmuz). A performance study of general-purpose applications on graphics processors using CUDA. Journal of Parallel and Distributed Computing, 68(10), 1370-1380.
• Che, S., Meng, J., Sheaffer, J., & Skadron, K. (2007). A Performance Study of General Purpose Applications on Graphics Processors. GPGPU'07: First workshop on general purpose processing on graphics processing units. Northeastern University, Boston, MA.
• Corporation, N. (2012). Nvidia Cg. Nvidia Cg. http://http.developer.nvidia.com/CgTutorial/cg_tutorial_chapter01.html adresinden alınmıştır
• CUDA™ (Compute Unified Device Architecture) Zone. (2012, Aralık). CUDA™ (Compute Unified Device Architecture) Zone. https://developer.nvidia.com/category/zone/cuda-zone adresinden alınmıştır
• Cui, X., Charles, J., & Potok, T. (2012, Eylül). The GPU Enhanced Parallel Computing for Large Scale Data Clustering. Future Generation Computer Systems, In Press, Corrected Proof.
• Dunn, J. (1973). A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well- Separated Clusters. Journal of Cybernetics, 3, 32-57.
• Espenshade, J., Pangborn, A., Laszewski, G., & Roberts, D. (2009). Accelerating Partitional Algorithms for Flow Cytometry on GPUs. 2009 IEEE International Symposium on Parallel and Distributed Processing with Applications, (s. 226-233). Chengdu, Sichuan, China.
• Ester, M., Kriegel, H., Sander, J., & Xu, X. (1996). A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96).
• Fang, W., Lau, K., Lu, M., Xiao, X., Lam, C., Yang, P., . . . Yang, K. (2008). Parallel Data Mining on Graphics Processors. Tech. rep., HKUST-CS08-07.
• Farivar, R., Rebolledo, D., Chan, E., & Campbell, R. (2008). A Parallel Implementation of K-Means Clustering on GPUs. PDPTA'08: International Conference on Parallel and Distributed Processing Techniques and Applications, (s. 340-345). Las Vegas, Nevada.
• Hall, J., & Hart, J. (2004). GPU Acceleration of Iterative Clustering. A. Lastra, M. Lin, & D. Manocha (Dü.), 2004 ACM Workshop on General Purpose Computing on Graphics Processors. içinde Wilshire Grand Hotel, Los Angeles, California.
• Harris, C., & Haines, K. (2005). Iterative Solutions using Programmable Graphics Processing Units. FUZZ '05: The 14th IEEE International Conference on Fuzzy Systems, (s. 12-18). Reno, NV.
• Jian, L., Wang, C., Liu, Y., Liang, S., Yi, W., & Shi, Y. (2011, Ağustos). Parallel data mining techniques on Graphics Processing Unit with Compute Unified Device Architecture (CUDA). Journal of Supercomputing, 1-26.
• Karch, G. (2010). GPU-based acceleration of selected clustering techniques. Master's thesis, Silesian University of Technology, Faculty of Automatic Control, Electronics and Computer Science, Gliwice, Poland.
• Kaufman, L., & Rousseeuw, P. (1987). Clustering by Means of Medoids in Statistical Data Analysis Based on the L1–Norm and Related Methods. (Y. Dodge, Dü.) Reports of the Faculty of Mathematics and Informatics. Delft University of Technology.
• Kohlhoff, K., M.H.Sosnick, Hsu, W., Pande, V., & Altman, R. (2011, Haziran). CAMPAIGN: an open- source library of GPU-accelerated data clustering algorithms. Bioinformatics, 27(16), 2321-2322.
• Kohlhoff, K., Pande, V., & Altman, R. (2012, Ağustos). K-means for parallel architectures using all- prefix-sum sorting and updating steps. IEEE Transactions on Parallel and Distributed Systems, IEEE Early Access Articles.
• Kumar, N., Satoor, S., & Buck, I. (2009). Fast Parallel Expectation Maximization for Gaussian Mixture Models on GPUs Using CUDA. HPCC'09: 11th IEEE International Conference on High Performance Computing and Communications, (s. 103-109). Seoul, Korea (South).
• Li, Y., Zhao, K., Chu, X., & Liu, J. (2013, Mart). Speeding up k-Means algorithm by GPUs. Journal of Computer and System Sciences, 79(2), 216–229.
• Lib Sh - Embedded Metaprogramming Language. (2012, Aralık). Lib Sh - Embedded Metaprogramming Language. http://libsh.org/ adresinden alınmıştır
• Lin, K., & Lin, C. (2011). A fast CAST-based clustering algorithm for very large database. Proceedings of 2011 International Conference on System Science and Engineering (ICSSE), (s. 420-424). Macau, China.
• Liu, Z., & Ma, W. (2008). Exploiting Computing Power on Graphics Processing Unit. CSSE'08: International Conference on Computer Science and Software Engineering, 02, s. 1062-1065. Wuhan, China.
• MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, (s. 281-297). the Statistical Laboratory, University of California, Berkeley, Calif.
• Microsoft DirectX. (2012, Aralık). Microsoft DirectX. http://msdn.microsoft.com/en- gb/library/windows/apps/hh309467.aspx adresinden alınmıştır
• Nvidia. (2012). GPU Hesaplama Nedir? GPU Hesaplama Nedir? http://www.nvidia.com.tr/object/gpu- computing-tr.html adresinden alınmıştır
• NVIDIA. (2012, Kasım). NVIDIA CUDA Programming Guide | PG-02829-001_v5.0. NVIDIA CUDA Programming Guide | PG-02829-001_v5.0. http://docs.nvidia.com/cuda/pdf/CUDA_C_Programming_Guide.pdf adresinden alınmıştır
• OpenCL™ (Open Computing Language) Zone. (2012, Aralık). OpenCL™ (Open Computing Language) Zone. http://developer.amd.com/resources/heterogeneous-computing/opencl-zone/ adresinden alınmıştır
• OpenGL (Open Graphics Library). (2012, Aralık). OpenGL (Open Graphics Library). http://www.opengl.org/ adresinden alınmıştır
• Pangborn, A. (2010). Scalable Data Clustering for Flow Cytometry using GPUs. Master's thesis, The Kate Gleason College of Engineering at Rochester Institute of Technology, Rochester, New York.
• Shalom, S., & Dash, M. (2011, Ekim). Efficient Hierarchical Agglomerative Clustering Algorithms on GPU Using Data Partitioning. 12th International Conference on Parallel and Distributed Computing, Applications and Technologies, (s. 134-139).
• Shalom, S., Dash, M., & Tue, M. (2008). Efficient K- Means Clustering Using Accelerated Graphics Processors. DaWaK'08: 10th International Conference on Data Warehousing and Knowledge Discovery, (s. 166-175). Turin, Italy.
• Shalom, S., Dash, M., & Tue, M. (2008). Graphics Hardware based Efficient and Scalable Fuzzy C- Means Clustering. AusDM 2008: The Australasian Data Mining Conference, (s. 179-186). Glenelg, South Australia.
• Shalom, S., Dash, M., Tue, M., & Wilson, N. (2009). Hierarchical Agglomerative Clustering Using Graphics Processor with Compute Unified Device Architecture. 2009 International Conference on Signal Processing Systems (ICSPS 2009), (s. 556-561). Singapore.
• Takizawa, H., & Kobayashi, H. (2006). Hierarchical parallel processing of large scale data clustering on a PC cluster with GPU co-processing. Journal of Supercomputing, 36(3), 219-234.
• Temizel, A. (2011). CUDA ve OpenCL Temelleri. Hesaplamalı Bilimlerde GPU Teknolojileri ve Genel Amaçlı GPU Programlama Semineri, (s. 59). ODTÜ Enformatik Enstitüsü Ural Akbulut Amfisi, Ankara.
• Thapa, R., Trefftz, C., & Wolffe, G. (2010). Memory-efficient implementation of a graphics processor- based cluster detection algorithm for large spatial databases. 2010 IEEE International Conference on Electro/Information Technology (EIT). Normal, IL, USA.
• The Compute Shader Technology (DirectCompute). (2012, Aralık). The Compute Shader Technology (DirectCompute). http://msdn.microsoft.com/en-us/library/ff476331.aspx adresinden alınmıştır
• Vaitheeshwaran, V., Nagwanshi, K., & Rao, T. (2012, Mart). Multicore Processing for Classification and Clustering Algorithms. IJCA Proceedings on National Conference on Innovative Paradigms in Engineering and Technology (NCIPET 2012), ncipet, s. 20-24.
• Voorhees, E. (1986). Implementing agglomerative hierarchical clustering algorithms for use in document retrieval. Information Processing and Management, 22(6), 465-476.
• Wilson, J., Dai, M., Jakupovic, E., & Meng, F. (2007). Supercomputing with toys: Harnessing the power of NVDIA 8800GTX and Playstation 3 for bioinformatics problems. CSB 2007: Computational Systems Bioinformatics Conference, (s. 387-390). University of California, San Diego, USA.
• Wu, R., Zhang, B., & Hsu, M. (2009). Clustering Billions of Data Points Using GPUs. UCHPC-MAW'09: Proceedings of the combined workshops on UnConventional high performance computing workshop plus memory access workshop, (s. 1-6). Ischia, Italy.
• Wu, R., Zhang, B., & Hsu, M. (2009, Mart). GPU-Accelerated Large Scale Analytics. Tech. rep., HP Laboratories Technical Report.
• Zechner, M., & Granitzer, M. (2009). Accelerating K-Means on the Graphics Processor via CUDA. INTENSIVE 2009: The First International Conference on Intensive Applications and Services, (s. 7- 15). Valencia, Spain.
• Zhang, Q., & Zhang, Y. (2006, Nisan). Hierarchical clustering of gene expression profiles with graphics hardware acceleration. Pattern Recognition Letters, 27(6), 676–681.
• Zhang, Y., Mueller, F., Cui, X., & Potok, T. (2011, Şubat). Data-intensive document clustering on graphics processing unit (GPU) clusters. Journal of Parallel and Distributed Computing, 71(2), 211-224.
• Zhao, Y., Sheong, F., Sun, J., Sander, P., & Huang, X. (2013, Ocak). A Fast Parallel Clustering Algorithm for Molecular Simulation Trajectories. Journal of Computational Chemistry, 34(2), 95- 104.