Parallelization study on the clustering technique to mine large datasets

Abstract

Bu tezde, mesaj geçirme arayüzü (MPI) ve birleşik aygıt mimarisi hesaplaması (CUDA) modelini uygulayarak geliştirilen paralel öbekleme algoritmaları, çok geniş veri kümeleri üzerindeki uygulamaları ile birlikte tanıtılmıştır. WaveCluster, wavelet dönüşümü tabanlı yenilikçi bir öbekleme analizi yaklaşımıdır. Bu yaklaşımın etkinliğine rağmen, çok boyutlu geniş veri kümeleri üzerinde çalıştırıldığında çalışma zamanı fazla olmaktadır. Geliştirilen MPI algoritmasında; yüksek verimlilik değerlerini elde etmek için işlemciler arasındaki haberleşme en az seviyede tutulmuştur. Yapılan deneysel çalışmalarda, MPI algoritması yüksek hızlanma değerleri vermiştir ve ayrıca artan işlemci sayısı ile birlikte doğrusal bir çalışma karakteristiği göstermiştir. WaveCluster yaklaşımı ayrıca grafik işlemci ünitesi (GPU) üzerinde CUDA modeli uygulanarak paralelleştirilmiştir. Geliştirilen CUDA algoritmasında, wavelet dönüşümü ve bağlı parçaları işaretleme algoritmaları geliştirilmiştir. CPU üzerinde sıralı çalışan WaveCluster yaklaşımına kıyasla CUDA algoritmalarında yüksek hızlanma değerleri elde edilmiştir.

Parallel clustering algorithm implementations concerning message passing interface (MPI) and compute unified device architecture (CUDA) model with their applications to very large datasets have been presented in the thesis. WaveCluster is a novel clustering approach based on wavelet transforms. Despite it?s novelty, it requires considerable amount of time to collect results for large sizes of multidimensional datasets. In the MPI algorithm; divide and conquer approach has been followed and communication among processors are kept at minimum to achieve high efficiency. Developed parallel WaveCluster algorithm exposes high speedup and scales linearly with the increasing number of processors. Parallel behavior of WaveCluster approach has been also investigated by executing the algorithm on graphical processing unit (GPU). High speedup values have been obtained in the computation of wavelet transform and connected component labeling algorithms in the GPUs with respect to the sequential algorithms running on the CPU.