Wejście smoka

Antionowy model jest oparty na pojęciach przestrzeń, punkt przestrzeni, dane punktowe, antion, dane antionowe, antionowy program, ruch antionów w przestrzeni, ekspansja, transfer. Opiszemy je po kolei.

Przykłady antionowych programów powinny wyrobic u czytelnika odpowiednia intuicję. Nie powinien być z tym kłopot, poniewaz antionowe programy sa pisane w znanym jezyku „C” a lokalne obliczenia w punktach / antionach są wyrażone tradycyjnym sposobem. Róznicę miedzy zwykłym i antionowym programem stanowią instrukcje ruchu antionów w przestrzeni. Później podamy formalną definicją antionowego obliczenia jako sekwencji stanów S0,S1,S2, … i wprowadzimy pojęcie czasoprzestrzennego diagramu obliczenia.

Przestrzenie

W matematyce przestrzeń jest zbiorem elementów, które zazwyczaj nazywamy punktami, plus sposób jakim sie przechodzi z jednego punktu do drugiego. Przestrzenie, które nas interesuja są formalnie algebraiczne struktury znane jako (dyskretne) grupy. Punkty przestrzeni identyfikujemy z elementami grupy, chociaz moglibyśmy te dwie rzeczy oddzielić (elementy grupy są transformacje, które „działają” na zbiorze punktów przestrzeni). Tak jak to tu robimy jest jednak prościej, zwłaszcza że dla wizualizacji przestrzeni posługujemy się pojęciem „diagram Cayleya” grupy. Wierzchołkami diagramu (grafu) Cayleya są elementy grupy. Sa to równoczesnie punkty przestrzeni. Skierowane krawędzie grafu (też elementy grupy) modelują kierunki w przestrzeni. Kierunki się nazywają generatory.

Żeby sie szybko posunąc do przodu z wykładem, zajmiemy sie od razu specjalną i z punktu widzenia równoległych algorytmów najwazniejszą grupą  (C2 )n .  Ze względu na swą prostotę będzie nam towarzyszyc przez znaczną część wykładu. Dla n=3 mamy przestrzeń, która sie nazywa „trójwymiarowa kostka”, albo 3-kostka. Zbiór punktów jest  (C2 )3 = {000,001,010,011,100,101,110,111}, generatorami są {001,010,100). Poniżej jest graf 3-kostki.

Konwencja rysowania jest taka, że zamiast dwu przeciwnie skierowanych krawędzi (tam i z powrotem) rysujemy jedną nieskierowanąn krawędź czyli bez strzałki. Krawędzie oznaczamy 001,010,100, albo prosciej z wykorzystaniem kolorów (kolory czarny, niebieski, czerwony). Krawędzie/kolory nazywaja sie generatory dlatego, że wszystkie punkty przestrzeni można wygenerować tak, że z jakiegoś wybranego punktu, który oznaczymy jako „zerowy”, wędrujemy po krawedziach grafu i po drodze znaczymy reszte punktów sposobem pokazanym na rysunku. Czyli idąc z „xyz” wzdłuz krawędzi „uvw” wchodzimy do punktu, którego trzy wspólrzędne są

x^u
y^v
z^w

Symbol ^ jest operacja dodawania modulo 2 wspólrzędnych. Na przykład idąc z „101” wzdłuż krawędzi „001” wejdziemy do „100”. W odróżnieniu od zwykłego dodawania + mamy 1^1=0 (a nie 2). Reszta operacji jest 0^0=0, 0^1 = 1^0= 1.

(C2 )3 jest specjalny przypadek  (C2 )n , albo nawet  (C2 )infinity  . Ogólna nazwa jest n-kostka, albo hiperkostka. Matematycznych przestrzeni innych niz  (C2 )n   jest nieskończona ilość. Troche sie nimi zajmiemy pózniej. Na razie wystarczy mieć na oku  (C2 )3 , albo  (C2 )n   . Punkty kostki bedziemy oznaczać w dziesietnym (arabskim) systemie liczbowym, a nie dwójkowo (binarnie), jak to jest na powyzszym rysunku. Tak jest prościej. Piszemy więc  (C2 )3  = {0,1,2,3,4,5,6,7}.

Antiony

Antion jest aktywnym elementem w obliczeniu. Obliczenie startuje od poczatkowego antionu umieszczonego w punkcie 0 = 000. Antion ma „punktowy wymiar”, tak samo jak punkt przestrzeni. „Zakres widzenia” antionu jest lokalny. Antion „widzi” zawsze tylko punkt przestrzeni, w którym sie aktualnie znajduje. Antion może w punkcie wykonywac obliczenie (na danych punktowych i swych własnych) i może przechodzic z punktu do punktu. Ruch antionu z punktu do punktu jest skokowy.

Warto troche poćwiczyć ruchy antionów w 3-kostce i dziesiętno/ dwójkową konwencje oznaczania punktów. Weźmy jeden antion w punkcie 0 (dwójkowo 000). Jesli rozkażemy antionowi, żeby sie przesunął wzdłuż generatora 1 (dwójkowo 001, kolor czarny), to przesunie się do punktu 1 (czyli 001). Jeśli mu teraz rozkażemy „przesuń sie wzdłuz generatora 4 (dwójkowo 100, kolor czerwony), to przejdzie w górę do punktu 5. Później pokażemy antionowy program, który ustawi w każdym punkcie 3-kostki po jednym antionie. W całej kostce bedzie razem 8 antionów. Jeśli w takim stanie wykonamy w programie rozkaz, żeby wszystkie antiony wykonały równoczesnie ruch wzdłuż generatora 001 (wykonamy operację „t(001)”), to taki ruch będzie wyglądał jak zwierciadlane odbicie wzdłuz czarnego generatora. Cztery antiony w jedna strone, cztery naprzeciw.

Tę ostatnią wizję „równoczesnej refleksji” można poszerzyć dla kostki dowolnego wymiaru. Połowa, czyli N/2 antionów przsunie sie w jedna strone, równoczesnie N/2 antionów w przeciwnym kierunku. Liczba N może być na przykład 240, czyli 2240 punktów i tyle samo antionów. Takie N może kogoś przerazić, bo jak mozna równocześnie przemieszczać tyle antionów.

Dane punktowe i antionowe

Z fizyki klasycznej znamy taki termin „skalarne pole φ”, który oznacza, że w każdym punkcie x fizycznej 3-wymiariowej przetrzeni mamy jakas liczbe, skalar φ(x). Podobnie jest u nas. Każdy punkt przestrzeni bedzie miał przyporzadkowanych ogólnie wiecej takich skalarów, czyli listę zmiennych. Na przykład zmiennych typu integer, bit string, … Zależy od przykładu, od problemu, który programujemy. W kazdym punkcie przestrzeni bedziemy mieli identyczną listę, identyczną strukturę danych. Podobnie w antionach, kazdy antion bedzie miał identyczną listę antionowych zmiennych (identyczną dla danego problemu, dla danego programu). Jesli bedziemy w czasie obliczenia rozważać antion w jakimś punkcie, to bedziemy mieli dwie listy danych (zmiennych) naprzeciwko siebie, antionowe zmienne i punktowe zmienne.