Demetleme Problemi İçin Paralel Karınca Yaklaşımı

Abstract

Bu çalışmada, öncelikle demetleme problemi çözümü için karınca demetleme yöntemi ardışıl olarak gerçeklenmiştir. Gerçeklenen algoritma seçilen paralel kütüphane kullanılarak iteratif bir yaklaşım ile paralelleştirilmiştir. Demetlenecek veriler ve demetleme ortamını oluşturan 2 boyutlu ortam ve toplam adım sayısı işlemciler arasında paylaştırılır. İşlemcilerden biri master işlemci olarak belirlenir. Master işlemci dahil her işlemci kendine atanan alanda ardışıl demetleme çözümünü çalıştırır ve çalışmasının sonlandığını master işlemciye bildirir. Master işlemci ardışıl demetleme çözümünü bütün verileri ve 2 boyutlu alanın tamamını kullanarak tekrar çalıştırır. Demetleme algoritmasının daha iyi bir noktadan başlayabilmesi amaçlanmaktadır. Yapılan çalışmada gerçeklenen iteratif ve kısmi paralelleştirme işleminin özellikle algoritma sonlanma zamanında iyileştirmeye sebep olup olmayacağı araştırılmıştır. Yapılan testlerde iki ve dört işlemi için seçilen veritabanları için performans ölçüm sonuçları elde edilmiştir. Algoritmanın daha iyi bir noktadan başlamasını sağlamak ve atılacak toplam adım sayısının diğer işlemcilerle paylaşmasını sağlamak algoritma çalışma zamanlarında iyileşmeyi sağlamıştır. Haberleşme maliyetinin diğer paralelleştirme yöntemine göre çok düşük olması da algoritmanın avantajlarından biridir.

In this study sequential ant based clustering is implemented. The implementation is parallelized using an iterative approach through the chosen parallelization library, which is MPI. All the processors share the dataset to cluster and the 2-dimensional clustering environment. One of the processors is marked as master. Each of the processors, including the one denoted as master, runs the sequential algorithm and informs the master processor when the run ends. After all processors finish clustering the data assigned to them, the master processor runs the sequential algorithm again, but this time it uses all the items in the dataset and the whole 2-dimensional clustering environment. The aim of the first stage is to provide a better start point for the clustering algorithm performed by the master in the second stage. It is analyzed if the implemented iterative and partially parallel clustering method causes a better time performance then its fully sequential version. Tests are executed for 2 and 4 processors on selected example datasets. As stated above, the aim is to make the second stage of the algorithm to start from a better initial situation for clustering by dividing the grid and the number of iterations among the processors. The aim of this study is to speed up the ant clustering method, which is normally very time consuming. Thus, no steps are taken to improve the clustering solution. As a result of the experiments, it is seen that the proposed algorithm performs better based on time measurements, however it does not improve other clustering performance measures. This is an expected outcome. The communication cost is very small compared to other ant clustering parallelization techniques found in literature.