Czas i przestrzeń

Formalnie antionowe obliczenie jset sekwencja stanów S0, S1, S2, …  . Symbol Sτ oznacza konfigurację „punkty/ antiony” w dyskretnym czasie „τ”. Będziemy traktować symbole Sτ za zbiory punktów i antionów zgromadzonych bezposrednio przed instrukcją tx(), t(), albo o(). Czyli będziemy abstrahować od (być może bardzo złozonych) lokalnych procedur obliczeniowych w punktach/ antionach. Analizujemy tylko operacje ruchu w przestrzeni.

W tej sytuacji możemy obliczenie S0,S1,S2,… przedstawić w graficznej formie ogołoconej od szczegółów lokalnych operacji. Taki graf będziemy nazywac czasoprzestrzennym diagramem obliczenia. Poziome przerywane linie bedą reprezentować punkty przestrzeni a pełna linią rysowane strzałki będą reprezentować przeskoki antionów pod działaniem operacji tx(), albo t().

Diagram ekspansji

Zobaczmy jak taki diagram wyglada dla naszego poprzedniego programu w C23 (ekspansja „…” plus permutacja). Najpierw ekspansja, która wyglada następująco:

tx(1); tx(2); tx(4);

Czas jest oznaczony na górze. W czasie τ=0 mamy rozmnożenie antionu z punktu 0 do punktów 0,1. W czasie τ=1 mamy dwa antiony w 0 i 1 odpalone równoczesnie a w czasie τ=2 mamy 4 antiony. W czasie τ=2 nastepuje ekspansja antionów do punktów 0,1,2,3,4,5,6,7.

Diagram permutacji

Po skończonej fazie ekspansji znajdujemy się w stanie S3. Mamy 8 antionów w 8 punktach przestrzeni C23 , i wchodzimy do pętli „for”. W tej części diagramu wyobrażamy sobie transport danych punktowych „a” po poziomych przerywanych strzałkach a transport danych antionowych „A” i „GEN” po skośnych pełnych strzałkach. W fazie permutacji bardzo zalezy, zeby odpalanie operacji w poszczególnych czasach τ= 3,4,5 odbywały sie równoczesnie, naraz. Spójrzmy na lewy górny fragment diagramu. Wartość „a” płynie z wierzchołka (v,τ) = (0,3) do (0,4) i napotyka na wartość „A” płynacą z wierzchołka (1,3) do (0,4). (Po pełnej strzałce płynie również „GEN”.) W wierzchołku (0,4) diagramu nastepuje operacja dodawania „a+A”. Wynik sie umieści do zmiennej „a”, żeby był przygotowany do następnego kroku.

t(1); t(2); t(4);

Diagram retrakcji

Retrakcja jest odwrotnością ekspansji. Czas oznaczylismy 6,7,…. , żeby mozna diagram przykleić do poprzedniego diagramu permutacji. Razem sklejone trzy diagramy: ekspansji, permutacji i retrakcji (EPR) przedstawiają „normalną” postać oblicznie antionowego.

Program wykorzystujący retrakcję jest „schemat Hornera” w sekcji „EPR”. W programie mamy:

t(1);   if ((currentpoint & 1) != 0) o();             // retract
t(2);   if ((currentpoint & 2 != 0) o();             // retract
t(4);   if ((currentpoint & 4) != 0) o();             // retract

Konkretnie antion (1,6) wykonuje transfer t(1) i przechodzi do (0,7).  Antion (0,6) przechodzi do (1,7), gdzie znika wykonujac o(). Nie można zrobic tak, żeby antion w (0,6) zniknął juz w punkcie 0.  Musi najpierw przejsć do (1,7), żeby dopiero tam zniknąć. W czasie τ= 7 mamy juz tylko 4 antiony, w czasie τ= 8 zostały 2 antiony. Ostatni antion całego procesu znika w punkcie „zero”.