Logowanie do System sprawozdań KDM

Równoległe algorytmy grupowania k-średnich wykorzystujące nierówność trójkąta do skrócenia czasu obliczeń

Kierownik projektu: Wojciech Kwedlo

Politechnika Białostocka

Wydział Informatyki

Białystok

Streszczenie projektu

Algorytm grupowania k-średnich (ang. k-means clustering) [5] jest jednym z podstawowych algorytmów stosowanych w eksploracji bardzo dużych zbiorów danych (ang. big data). Głównym celem projektu jest zbadanie skalowalności autorskiego zrównoleglenia tego algorytmu w technologii OpenMP+MPI, zarówno klasycznej wersji zaproponowanej przez Lloyda jak i ostatnio zaproponowanych wersji (algorytmy Elkana [3], Hamerly'ego [4], annularny [4] i YinYang [1]) wykorzystujących nierówność trójkąta do skrócenia czasu obliczeń. O ile zrównoleglenie algorytmu Lloyda zostało opisane w literaturze [2,6] (choć brak implementacji hybrydowych OpenMP + MPI), to cztery algorytmy wykorzystujące nierówność trójkąta zostały zbadane w zasadzie wyłącznie w wersjach szeregowych. Ze względu na możliwość niezrównoważonego obciążenia oraz konieczność utrzymywania dodatkowych struktur danych, otwartą kwestią jest czy przewaga tych czterech algorytmów nad algorytmem Lloyda (nawet kilkudziesięciokrotne skrócenie czasu obliczeń) w środowisku jednordzeniowym utrzyma się w ich równoległej implementacji wykonywanej na tysiącach rdzeni. Jednym z celów projektu jest dostarczenie odpowiedzi na powyższe pytanie. Innym celem jest próba selekcji najszybszego algorytmu równoległego wykorzystującego nierówność trójkąta. Dodatkowo, hybrydowa implementacja OpenMP + MPI zostanie porównana eksperymentalnie z implementacją 'flat MPI', w której każdy rdzeń systemu wykonuje odrębny proces MPI.

Do badań eksperymentalnych algorytmów grupowania zostaną wykorzystane publicznie dostępne duże zbiory danych pochodzące z dziedziny przetwarzania obrazów, z których największy ma 300 GiB, oraz zbiory danych generowane przez generator liczb pseudolosowych z ustalonego rozkładu (mieszanina wielowymiarowych rozkładów normalnych).

Wyniki projektu zostaną opublikowane w dobrym czasopiśmie naukowym z listy JCR, poruszającym tematykę obliczeń równoległych (np. Parallel Computing, IF2014=1,511). Po publikacji wyników przewidywane jest udostępnienie kodów źródłowych oprogramowania na zasadach oprogramowania o otwartych źródłach (ang. open source).

W przyszłości rozważana będzie implementacja algorytmów dla środowiska wielu akceleratorów GPU (hybrydowe zrównoleglenie CUDA+MPI).

W ramach projektu zostanie eksperymentalnie zbadana skalowalność, zarówno słaba (ang. weak) jak i silna (ang. strong) równoległych algorytmów grupowania danych. Zbadania skalowalności tych algorytmów dla maszyn równoległych wykorzystujących tysiące rdzeni nie jest możliwe bez dostępu do KDM. W instytucji wnioskodawcy największe klastry obliczeniowe są wyposażone w odpowiednio 128 rdzeni (łącze Infiniband DDR) oraz 160 rdzeni (łącze Gigabit Ethernet). Zasoby te nadają się wyłącznie do testowania (debugowanie, wstępne testy skalowalności, szacowanie zapotrzebowania na moc obliczeniową) równoległych implementacji algorytmów.

W obliczeniach prowadzonych w ramach projektu zostanie wykorzystana opracowana przez autorów implementacja algorytmów grupowania k-średnich w języku C++. Wymaga ona kompilatora zgodnego ze standardem programowania wielowątkowego OpenMP i biblioteki MPI. Oprogramowanie zainstalowane obecnie na klastrze Tryton (kompilator Intel wersja 16, oraz biblioteki Intel MPI i OpenMPI) spełnia wymagania tej aplikacji.

Literatura

1. Ding Y., et al. Yinyang k-means: A drop-in replacement of the classic k-means with consistent speedup. Proceedings of the 32nd International Conference on Machine Learning (ICML-15), pp. 579-587, 2015.

2. Dhillon, I. S., Modha D.S., A data-clustering algorithm on distributed memory multiprocessors. In Large-Scale Parallel Data Mining, Springer, 2002. pp. 245-260.

3. Elkan C., Using the triangle inequality to accelerate k-means, Proceedings of the 20th International 3. Conference on Machine Learning (ICML'2003), vol. 3, pp. 147-153, 2003.

4. Hamerly G., Drake J., Accelerating Lloyd's algorithm for k-means clustering. In Partitional Clustering Algoirthms, pp.41-78, Springer, 2015.

5. Jain, A. K., Data clustering: 50 years beyond K-means, Pattern Recognition Letters 31(8) pp. 651-666, 2010.

6. Jin, R., Yang, G. Agrawal, G., Shared memory parallelization of data mining algorithms: Techniques, programming interface, and performance. IEEE Transactions on Knowledge and Data Engineering, 17(1), 71-89, 2005

Centrum Informatyczne Trójmiejskiej Akademickiej Sieci Komputerowej
ul. G. Narutowicza 11/12, 80-233 Gdańsk   |   tel. 58-347-24-11
email: office@task.gda.pl   |   NIP: 584-020-35-93