Charakterystyka sieci (grafów) spotykanych w dzisiejszym świecie sprawia, że nawet najbardziej podstawowe zadania przetwarzania grafów (takie jak obliczanie spójnych składowych lub najkrótszych ścieżek) stanowią spore wyzwanie.
Sieci te bywają bardzo duże: ich rozmiar może z łatwością przekroczyć pojemność pamięci głównej pojedynczego komputera. Nawet jeśli sieć mieści się w pamięci głównej komputera, może się zdarzyć, że użycie dobrze znanych i sprawdzonych optymalnych algorytmów (takich jak przeszukiwanie wszerz) nie gwarantuje, że obliczenia zostaną wykonane wystarczająco szybko. Podczas gdy częstotliwości taktowania procesorów konsumenckich przestały wzrastać, systematycznie rośnie liczba rdzeni typowego procesora. W związku z tym, uzasadnionym jest poszukiwanie wydajnych algorytmów równoległych zarówno w klasycznych modelach pamięci współdzielonej (PRAM), jak i bardziej współczesnych modelach obliczeń masowo równoległych (takich jak MapReduce) z danymi wejściowymi rozproszonymi pomiędzy wiele maszyn.
Kolejnym wyzwaniem, przed którym stoimy, jest to, że spotykane obecnie sieci zmieniają się w czasie. W typowym scenariuszu sieć podlega bardzo częstym, niewielkim aktualizacjom. Aktualizacje są na tyle małe, że ponowne obliczanie wymaganych informacji od zera po każdej zmianie wydaje się nierozsądne. Ta myśl dała początek bardzo bogatemu obszarowi dynamicznych algorytmów grafowych, w którym poszukuje się wydajnych struktur danych utrzymujących żądane informacje o własnościach dynamicznych grafów. Większość dotychczasowych prac w tym obszarze ma charakter czysto teoretyczny. Praktyczna ewaluacja dynamicznych algorytmów grafów jest wciąż w powijakach.
Celem badań naszego zespołu jest projektowanie i ewaluacja nowych równoległych i dynamicznych algorytmów dla podstawowych problemów przetwarzania grafów. Po pierwsze, prowadzimy teoretyczne badania nad tym, jakie równoległe kompromisy pomiędzy głębokością a pracą algorytmu mogą być osiągnięte i w jakim stopniu te rozwiązania mogą być skuteczne w dynamicznych sytuacjach. Po drugie, opracowujemy implementacje i przeprowadzamy eksperymentalne oceny dynamicznych i równoległych algorytmów grafowych dla problemów w kręgu zainteresowań praktyków.
Badania zespołu są częściowo skoordynowane z celami grantu NCN 2022/47/D/ST6/02184 ,,Równoległe i dokładne algorytmy dla problemów ścieżkowych w grafach skierowanych’’ realizowanego przez IDEAS NCBR.
Google Scholar
Bartosz Zieliński