Superkomputer: Applications

Opis projektu:
Celem projektu jest opracowanie algorytmów budujących reguły automatów komórkowych, na bazie obserwacji wyidealizowanego zjawiska. Zakłada się, że dostępne obserwacje są cząstkowe - tzn. brakuje w nich wartości dla części komórek oraz brakuje części kroków czasowych, tj. konfiguracji automatu w pewnych chwilach czasu. Rozważane strategie rozwiązania problemu identyfikacji, budowane są w oparciu o algorytmy ewolucyjne - głównie zmodyfikowany algorytm genetycznych.
Badania mają charakter teoretyczny - rozważane obserwacje, na obecnym etapie projektu - są wygenerowane przez program komputerowy. Nie mniej jednak, definicja problemu oraz rozważane metody rozwiązania pozwolą w przyszłości na rozwiązywanie problemu identyfikacyjnego w praktycznych zagadnieniach modelowania matematycznego.
Oczekiwane rezultaty naukowe to lepsze zrozumienie własności dynamicznych automatów komórkowych (badane są związki znanych metryk własności dynamicznych automatów oraz możliwości / wydajności identyfikacji) oraz budowa zestawu algorytmów rozwiązujących problem identyfikacji dla 1-wymiarowych, dwu-stanowych automatów komórkowych.
Uzasadnienie wykorzystania zasobów KDM TASK:
W ramach badań, planujemy przebadać wpływ braków w obserwacjach na wydajność identyfikacji - tj. czas jaki potrzebny jest na znalezienie rozwiązania przez algorytm ewolucyjny. Badaną przez nas klasą automatów są tzw. elementarne automaty komórkowe. Jest ich 256. Dla każdego z nich przeprowadzamy szereg eksperymentów - algorytm identyfikacyjny uruchamiany jest dla serii obserwacji o różnym stopniu "cząstkowości" obserwacji (tj. różnej liczbie brakujących wartości w komórkach). W sumie daje to kilkanaście tysięcy przypadków do sprawdzenia. Ze względu na stochastyczną naturę algorytmów ewolucyjnych, każdy przypadek musi zostać rozważony wielokrotnie - aby możliwe było otrzymanie wyników istotnych z punktu widzenia statystyki.

Tak duży rozmiar eksperymentu wymaga zastosowania komputerów o dużej mocy obliczeniowej. Przeprowadzenie symulacji nie jest możliwe z wykorzystaniem zwykłych stacji roboczych czy komputerów ogólnie dostępnych.

Użyte metody obliczeniowe i narzędzia technologiczne:
Każdy konkretnych przypadek - tj. zestaw obserwacji danego systemu, realizowany jest oddzielnie jako program działający na jednej, wieloprocesorowej maszynie. Obliczenia zrównoleglone są z wykorzystaniem biblioteki OpenMP - wszystkie procesory biorą udział w wyliczaniu funkcji dopasowania osobników w populacji algorytmu ewolucyjnego. Zrównoleglenie na wielu maszynach uzyskuje się przez uruchomienie w tym samym czasie wielu przypadku (algorytmu dla wielu zbiorów obserwacji). Poszczególne wykonania są jednak w pełni niezależne, co daje dużą elastyczność i możliwość rozłożenia obliczeń w czasie - zależnie od dostępnych zasobów obliczeniowych. Nie istnieje potrzeba komunikacji między poszczególnymi maszynami realizującymi obliczenia w tym samym czasie (nie ma żadnej korzyści z wprowadzenia takiej komunikacji).

Oprogramowanie zaimplementowane jest w językach C/C++ z wykorzystaniem bibliotek OpenMP oraz GNU Scientific Library (GSL). Przetwarzanie danych wynikowych realizowane jest w języku Python oraz za pomocą skryptów shell.