WS-SSA: harmonogramowanie przepływów pracy w chmurze z wykorzystaniem algorytmu stada salp

Dlaczego inteligentniejsze kierowanie ruchem cyfrowym ma znaczenie

Za każdą mapą online, analizą medyczną czy odkryciem fal grawitacyjnych stoi sieć zadań komputerowych, które muszą zostać wykonane we właściwej kolejności, na odpowiednich maszynach i jak najszybciej oraz najtaniej. W nowoczesnych środowiskach chmurowych zadania te są podzielone na tysiące powiązanych kroków rozproszonych po centrach danych na całym świecie. Gdy tym cyfrowym ruchem zarządza się źle, naukowcy dłużej czekają na wyniki, a dostawcy zużywają więcej energii elektrycznej niż to konieczne. W artykule przedstawiono nowe podejście do orkiestracji takich złożonych przepływów pracy, czerpiące inspirację z zaskakującego źródła: łańcuchów drobnych stworzeń morskich zwanych salpami.

Jak duże zadania naukowe są rozbijane na części

Duże aplikacje naukowe i biznesowe rzadko działają jako jeden program. Zamiast tego są rozkładane na wiele mniejszych zadań zależnych od siebie nawzajem. Badacze przedstawiają tę strukturę jako skierowany acykliczny graf: węzły oznaczają zadania, a strzałki pokazują, które wyniki muszą być wytworzone, zanim inne zadania będą mogły się rozpocząć. W centrum danych chmurowych zadania te odwzorowuje się na maszyny wirtualne — programowe komputery różniące się szybkością, pamięcią i przepustowością sieci. Wyzwanie polega na decyzji, które zadanie powinno zostać uruchomione na której maszynie i kiedy, tak aby cały przepływ pracy zakończył się jak najszybciej przy efektywnym wykorzystaniu zasobów.

Dlaczego znalezienie najlepszego planu jest tak trudne

Wybór idealnego harmonogramu dla tysięcy współzależnych zadań rozproszonych na wielu maszynach to klasyczny przykład problemu NP-trudnego: liczba możliwych przypisań rośnie tak gwałtownie, że sprawdzenie ich wszystkich w praktyce jest niemożliwe. Z tego powodu systemy chmurowe polegają na sprytnych skrótach, zwanych heurystykami i metaheurystykami, aby wyszukać dobre — choć niekoniecznie doskonałe — rozwiązania. Tradycyjne reguły, takie jak obsłuż w kolejności zgłoszeń (first-come-first-served) czy round robin, są proste, lecz przy dużej skali nieefektywne. Bardziej zaawansowane podejścia, w tym algorytmy genetyczne, optymalizacja rojem cząstek i optymalizacja inspirowana koloniami mrówek, przeszukują przestrzeń rozwiązań inteligentniej, ale mogą utknąć w przeciętnych rozwiązaniach, wymagać starannego strojenia parametrów lub ignorować ważne zależności między zadaniami.

Nauka od łańcuchów salp w oceanie

Nowa metoda, nazwana WS-SSA, adaptuje Algorytm Stada Salp do realiów przepływów pracy w chmurze. W naturze salpy poruszają się w łańcuchach, z liderem z przodu i podążającymi za nim osobnikami, korygując kierunek w poszukiwaniu pożywienia. WS-SSA traktuje każdy możliwy plan harmonogramowania jako członka takiego łańcucha. Najlepiej znany plan pełni rolę „pożywienia”, kierując ruchem harmonogramu-lidera, podczas gdy naśladowcy stopniowo dostosowują się w stronę obiecujących obszarów. Kluczowym rozwiązaniem projektowym jest to, że każda pozycja w tej sztucznej rojowej strukturze bezpośrednio koduje, która maszyna wirtualna wykonuje dane zadanie, używając prostych liczb całkowitych zamiast wartości ciągłych wymagających późniejszego przekształcania. W połączeniu ze starannym uporządkowaniem zadań, które zawsze respektuje ich zależności, zapewnia to, że każdy rozważany przez rój kandydat na harmonogram jest poprawny i od razu wykonalny.

Testowanie nowego planisty

Aby sprawdzić skuteczność WS-SSA, autorzy przeprowadzili obszerne symulacje przy użyciu WorkflowSim, narzędzia naśladującego rzeczywiste przepływy pracy naukowej działające w środowisku CloudSim. Testowali pięć benchmarkowych aplikacji z astronomii, sejsmologii, fizyki fal grawitacyjnych i bioinformatyki, o rozmiarach od kilkudziesięciu do tysiąca zadań oraz konfiguracjach chmury od kilku do stu maszyn wirtualnych. WS-SSA porównano z sześcioma klasycznymi regułami harmonogramowania oraz trzema nowoczesnymi metodami metaheurystycznymi, w tym z algorytmem optymalizacji wielorybów, algorytmami genetycznymi i optymalizacją rojem cząstek. Główną miarą był całkowity czas zakończenia (makespan), a jako wtórne, ściśle powiązane kryterium śledzono całkowite zużycie energii przez maszyny wirtualne.

Co wyniki oznaczają dla czasu i energii

W szerokim zestawie eksperymentów WS-SSA konsekwentnie generowało szybsze harmonogramy niż metody konkurencyjne. Średnio skracało makespan o około jedną trzecią w porównaniu z tradycyjnymi heurystykami, a jednocześnie osiągało poprawę o kilka do ponad dwudziestu procent w stosunku do dobrze znanych metaheurystyk. Ponieważ zmniejszyły się także okresy bezczynności i marnotrawne obliczenia, całkowite zużycie energii spadało równolegle — często w podobnym zakresie — bez konieczności explicite optymalizacji względem zużycia mocy. Testy statystyczne przeprowadzone na 30 niezależnych przebiegach potwierdziły, że te ulepszenia nie były przypadkowe, szczególnie w przypadku większych i bardziej złożonych przepływów pracy. Badanie pokazuje, że prosta, dyskretna wersja strategii inspirowanej salpami potrafi niezawodnie poruszać się w ogromnej przestrzeni możliwych harmonogramów i dostosowywać do różnych struktur przepływów pracy oraz konfiguracji maszyn.

Szybsza nauka przy bardziej oszczędnej chmurze

W praktycznym ujęciu WS-SSA to inteligentniejszy kontroler ruchu dla cyfrowej autostrady, która stoi za nowoczesną nauką i usługami chmurowymi. Koordynując kiedy i gdzie każde zadanie jest uruchamiane, skraca czas między uruchomieniem złożonego zadania a uzyskaniem końcowego rezultatu, jednocześnie obniżając rachunek energetyczny centrów danych. Praca nie zmienia sposobu, w jaki same przepływy pracy są definiowane; zamiast tego oferuje bardziej efektywny sposób ich uruchamiania na istniejących platformach chmurowych. Przyszłe rozszerzenia uwzględniające jednocześnie koszt, energię i terminy mogą uczynić takie schedulery inspirowane rojami ważnym narzędziem dla bardziej ekologicznych i responsywnych infrastruktur obliczeniowych.

Cytowanie: Sharawy, A.A., Sakr, R.H., Eladrosy, W. et al. WS-SSA: workflow scheduling in cloud computing using salp swarm algorithm. Sci Rep 16, 13402 (2026). https://doi.org/10.1038/s41598-026-48037-w

Słowa kluczowe: harmonogramowanie przepływów pracy w chmurze, optymalizacja metaheurystyczna, algorytm stada salp, obliczenia naukowe, energooszczędna chmura