Superkomputer: Applications

Algorytm grupowania k-średnich [1] (ang. k-means clustering) 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 wersji algorytmu [3], wykorzystującej organizację grupowanych danych w postaci kd-drzewa, do skrócenia czasu obliczeń. Jeżeli wymiar przestrzeni cech jest niewielki, to zastosowanie kd-drzew może znacznie skrócić czas pracy algorytmu. Dotychczas algorytmy tego typu badano raczej w wersji szeregowej. Ze względu na niezbalansowanie struktury kd-drzewa ich zrównoleglenie nie jest trywialne i wymaga dynamicznego równoważenie obciążenia. Takie równoważenie dynamiczne jest dostarczane przez mechanizm zadań OpenMP. Jako minimum, wynikiem projektu będzie wersja równoległa dla jednego węzła klastra Tryton (24 rdzenie). Wersja ta zostanie porównana z równoległym naiwnym (klasycznym) algorytmem Lloyda oraz z równoległymi algorytmami opartymi o nierówność trójkąta, które opracowano w ramach poprzedniego grantu KDM TASK [2]. Jako maksimum, zostanie opracowana wersja rozproszona, wykorzystująca zrównoleglenie hybrydowe MPI/OpenMP i wybrany algorytm dynamicznego równoważenia obciążenia pomiędzy węzłami klastra.
Badania eksperymentalne rozważanych algorytmów skupią się na porównaniu skalowalności i czasu obliczeń. Mniej istotne jest natomiast porównanie wyników grupowania danych, ponieważ wszystkie algorytmy osiągają ten sam wynik (jeżeli pominąć błędy zaokrągleń). Zostaną wykorzystane syntetyczne zbiory danych o rozmiarze do kilkuset (powiedzmy 300) GB. Wyniki zostaną opublikowane w dobrym czasopiśmie naukowym z listy JCR. 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 ramach projektu zostanie eksperymentalnie zbadana skalowalność pewnych algorytmów równoległych, początkowo wykorzystujących wiele rdzeni w jednym węźle. Nawet w takim przypadku niezbędne jest wykorzystanie maszyn KDM, gdyż należy przeprowadzić bardzo dużo eksperymentów obliczeniowych (na przykład zmieniając zbiór danych, bądź liczbę grup). Przeprowadzenie obliczeń w TASK umożliwi otrzymanie wyników w rozsądnym czasie, dzięki możliwości zlecania wielu zadań do kolejki. W przypadku udanego opracowania wersji równoległej MPI/OpenMP potrzebne będzie zbadanie jej skalowalności (pojedyncze zadanie wykorzystujące do 64 węzłów), co jest niewykonalne bez wykorzystania zasobów KDM.
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. W dalszej części algorytm ma zostać rozszerzony na wiele węzłów. Oprogramowanie zainstalowane obecnie na klastrze Tryton (kompilator Intel, oraz biblioteki Intel MPI i OpenMPI) w zupełności spełnia wymagania tej aplikacji.

Literatura
1. Jain, A. K., Data clustering: 50 years beyond K-means, Pattern Recognition Letters 31(8) pp. 651-666, 2010.
2. Kwedlo W., Czochański P. J., A Hybrid MPI/OpenMP Parallelization of K-Means Algorithms Accelerated Using the Triangle Inequality, IEEE Access 7, (2019) 42280-42297
3. Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., & Wu, A. Y. (2002). An efficient k-means clustering algorithm: Analysis and implementation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(7), 881-892.