15-aug-2022
Krótka historia mrówkowego modelu równoległego obliczenia. Pierwotnie w modelu były „mrówki” i „struktury”. Mrówki wędrowały po strukturach i wykonywały obliczenia. Strukturami były grafy (wierzchołki i krawedzie). Wziąłem nastepnie do pomocy (dyskretne) grupy i diagramy (grafy) Cayleya, do roli struktur danych w programach.
Grupy to bardzo rozpowszechnione obiekty algebraiczne. Grupa G, w abstrakcyjnym sensie, to zbiór elementów g,g´, … plus jakaś iloczynowa operacja g * g´ = g´´, plus odpowiednie aksjomatyczne warunki jak przemiennosc mnożenia, istnienie elementu odwrotnego, … itd. W zastotowaniach elementy grupy reprezentują zazwyczaj transformacje obiektów z jakiegoś zbioru X, mówimy że działają na zbiorze X, g.x= x´.
W Warszawie w mrówkowym modelu zmieniłem termin „struktura” na „przestrzeń”. Elementy grupy G są w modelu traktowane równocześnie jako transformacje i jako punkty przestrzeni. Czyli G i X to ten sam zbiór, X= G. Tak jest prościej i mozna bezposrednio korzystac z diagramów (grafów) Cayleya. W programach transformacje przestrzeni zapisujemy t(r). Za „r” podstawiamy elementy grupy G , ale nie wszystkie, tylko niektóre. Wystarczy, zeby te „r” generowały grupę G. Tak więc w naszym modelu przestrzeń to grupa G plus podzbiór generatorów R⊂G. Elementy „g” rysujemy jako punkty (kropki) na kartce papieru a generatory „r” jako strzałki z punktu g do puntu g´= g.r. Tak powstaje diagram Cayleya grupy . Więcej o diagramach Cayleya, o definicji grup przy pomocy generatorów, itd., w którymś z rozdziałów AB PLUS.
W historii nauki zdarzało się wielokrotnie, że terminy do oznaczenia czegoś nowego, były wybrane niezbyt szczęśliwie. To samo mozna powiedziec o terminie „mrówka”. Teraz to zmieniam na termin „antion”, bardziej naukowy, bardziej miedzynarodowy i sugerujacy podobieństwo do fizycznej cząsteczki. Kilkadziesiąt lat temu zabrał mnie prof. Turski do prof. Pawlaka (dwa piętra w górę w pałacu kultury w Warszawie), czy by sie zgodził byc recenzentem mojej pracy doktorskiej. Prof. Pawlak powiedział owszem, pod warunkiem, ze zmienię nazwę „mrówka” na coś innego. „Nie będę sie przecież wygłupiał”, tak dosłownie powiedział. Miał rację, terminy naukowe trzeba wybierać tak, zeby to wyglądało naukowo. Ale wtedy było juz za późno na zmianę, bo artykuł do czasopisma juz był w druku.
Mieszkałem w Warszawie w akademiku na Grójeckiej z kolegą Janem Slavikiem, z Pilzna, doktorantem instytutu fizyki UW. Omawialiśmy czasami tematy fizyczne. Równiez inne tematy, bo Honza interesował sie polską sztuka, literaturą, historią. Raz poszedłem z Honzą do instytutu na Hożej posłuchac wykładu jakiegoś profesora z CERN-u o cząstce „J/ψ” (charmonium). Właśnie ją eksperymentalnie odkryli i trzeba było do niej dopasować teorię. Pamiętam, jaki zabawny szum rozległ się na sali, kiedy ten profesor tłumaczył, ze termin „gluon” pochodzi od „kleju”, którym sa w hadronach zlepiane kwarki. Stardardowy model roi sie od innych podobnie zabawnych terminów. Tak wiec „mrówka” to nic specjalniego. Ale termin „antion” jest lepszy.
Niestety kolega Slavik (późniejszy docent na katedrze fizyki na technicznym uniwersytecie w Pilznie) niedawno zmarł. Jak zresztą równiez prof. Turski, albo prof. Frištacký, u którego mogła sie rozpocząć moja całozyciowa kariera naukowa. Kiedy kończyłem studia na fakultecie elektrotechnicznym (FE) w Bratysławie w r. 1968, pracę dyplomową z aplikacji teorii automatów robiłem własnie u prof. Frištackiego, który mnie potem wziął jako asystenta (dzięki rekomendacji kolezanki z rocznika, Heleny Šalamonowej, córki szefa katedry). Trzy lata tam byłem. Pamietam, ze m.in. prowadziłem studencką pracę dyplomową na temat switching circuit dla ewaluacji wyrażen arytmetycznych Chyba stamtąd pochodzi idea „mrówki“, jako agenta chodzącego po drzewach wyrażeń arytmetycznych. Nie byłem geniuszem, raczej przeciętniakiem. Najwyzej bym sie zgodził na przydomek „ostatni romantyk“, jak mnie nazwał w tamtych czasach kolega Jan Borsuk. Widocznie coś było we mnie, ze ludzie mi wierzyli. Choć pewnie było tak, że w końcu zdradziłem ich wiarę, musiało tak być.
Na studiach a następnie bedąc asystentem na FE polubiłem matematykę. Wyrobiłem w sobie matematyczną intuicję (tak naprawdę niewiele poza nią …). Studia inzynierskie to była raczej klasyczna analiza, ale w czasie asystentury to juz była dyskretna matematyka i wpływ rodzącej sie „computer science“. W roku 1972 jakimś trafem weszłem do kółka młodych matematyków przy słowackiej akademii nauk, którego cotygodniowe seminaria prowadił prof. Gruska. Dzisiaj żywa legenda komputerowych naukowców. Raz miałem przygotować referat wg. artykułu w CACM „Towards data structures“. Zbiegiem okolicznosci natrafiłem na książkę prof. Turskiego „Struktury danych“. Do tego moje własne rozmyslania o równoległym obliczeniu na strukturach danych. Przypadek chciał, że mogłem skorzystać z mozliwości studium doktoranckiego na Uniwersytecie Warszawskim. Te okolicznosci przeniosły mnie na nastepne trzy lata do Warszawy. Wszystko przebiegało szybko, niemalze nie zdązyłem sie pozegnac z Bratysławą.
Odbierajac dyplom dr matematyki otrzymałem propozycję prof. Turskiego, żebym pracował na UW. Ale juz wtedy miałem na karku żone i małego synka, a córka była w drodze. Wiedziałem z własnego doswiadczenia, ze nie będe umiał sobie sam w Warszawie z ta sytuacją poradzić. Wróciłem do rodzinnych stron. Związałem sie na 20 lat z „OKD“ (spółka weglowa), gdzie znalazłem pracę przy komputerach, od historycznych po nowoczesne. Prof. Turski w tym czasie jeszcze kilkakrotnie próbował mnie przemówic/wydostać stamtąd. Ostatni raz w r. 1995, kiedy był dziekanem wydziału matematyki na UW. Odmówiłem, między innymi obawiałem się, że nie dam rady. Co konkretnie profesjonalnie robiłem, wtedy i potem (razem 40 lat) byłoby na dłuzsze opowiadanie. Może i ciekawe, lecz niezwiązane z „mrówkowym“ tematem. W tym czasie „computer science“, masywne równoległe obliczenia, równiez nowoczesna fizyka (ciagle myślę, ze to ściśle związane tematy), poszły tak daleko, ze jestem bezradny wobec powstałej masy informacji. I czasu mi juz pozostało niewiele.
20/Feb/2021. About 50 years since the idea originated, called ant model, now called antion model.
11/Feb/2019. Ponad 40 lat od publikacji mych dwóch artykułów w Acta Informatica i Information Processing Letters opisujacych wstępne informacje dotyczące „mrówkowego“ modelu równoległych obliczeń [1,2]. Pierwszy artykuł zawiera kilka przykładów programów ilustrujących pożyteczność takiego podejscia do opisu równoleglych algorytmów. Drugi artykuł zawęża definicję przestrzeni, w której odbywają się obliczenia, w zasadzie na (C2)n (n-cube, albo hypercube, i przestrzenie włożone (embedded) do hypercube).
Następne artykuły pochodzą z lokalnych seminariów w Czechach [3,4]. A mniej więcej 10 lat później, kiedyś na początku 90-tych lat, powstał dokument „antbook” opisujący programowanie w języku C przy pomocy kernela symulującego obliczenia równoległe. Dokument niepublikowany, częściowo dystrybuowany (ale nigdzie nie cytowany). Znakiem rozpoznawczym dla tych dokumentów jest użycie terminologii ants/ points.
We wszystkich nowych tekstach, które tu będę zamieszczał (czyli od 11/2/2019) będzie zmiana terminologii. Zamiast czysto biomorficznego terminu „mrówka“ będę używał terminu „antion“. Oczywiscie słowo „antion“ pochodzi od angielskiego „ant“. Tak jak kiedyś, albo jeszcze dziś, różne nowe terminy naukowe są wyprowadzane z greckiego języka. Teraz już czas brać te rzeczy z angielskiego.
Zmieniam nazwę zwłaszcza dlatego, ażeby „mrówka” była nazywana identycznie w jakimkolwiek języku (angielskim, polski,czeskim,… ). Określenie „antion” bedzie oznaczać równoczesnie dwie rzeczy. Jednak, jak przedtem, to będzie „fictitious being”, mobilny twór, który „jak żywy” bedzie sie poruszać w przestrzeni i robić obliczenia wg. programu który nosi ze sobą. „Antion” bedzie też oznaczac „czasteczkę”, jak w fizyce. Nie twierdzę, że antiony odpowiadają jakimś istniejącym fizycznym cząsteczkom. Ale niektóre konstrukcje i „zjawiska” występujące w antionowym modelu mozna przyrównać do standardowych teoretyczno fizycznych pojęć (… łącznie z kosmologią).
Dokumenty można czytać wstępując na odpowiednio nazwane strony/ podstrony w menu. Np. strona „antbook” dotyczy pracy z roku 1993, w których jest opis implementacji mrówkowych programów na PC przy pomocy Borland C. Specjalnie jest tam kernel „kern.c” itd. i kilka przykładów. Chociaż dziś to już jest nieaktualne, idea jest zastosowana dla współczesnego kernelu napisanego w MS Visual C++. Też mozna odnależć odpowiednią podstronę i przeczytać jak to działa. Programowanie współczesnych superkomputerów oparte o „message passing“ (MP) przypomina „mrówkowe“ podejście. Nie mogę jedna twierdzić, że architektura „hypercube” w połaczeniu z metodą MP była jakoś inspirowana artykułami [1,2]. Poza tym MP całkowicie ignoruje teoretyczne podstawy masywnych równoległych algorytmów, mianowicie symetrie (teorię grup) i co za tym idzie możliwość eliminacji (albo częściowej eliminacji) indeksowania danych w programach.
[1] R. Zuczek: A New Approach to Parallel Computing. Acta Inf. 7: 1-13 (1976)
[2] R.Zuczek: The Universal Space for Parallel Computation. Inf. Process. Lett. 6(2): 42-45 (1977)
[3] R.Zuczek: Implementace takzvanych mravencovych programu, SOFSEM’82
Proc., 413-417, (1982)
[4] R.Zuczek: Souvislost mezi dvema zpusoby popisu paralelnich
algoritmu, MOP’86 Proc., 145-153, (1986)