Kernel nr. 16 mozna naprogramować trochę inaczej. Dołączmy do antionów licznik τ , parametr reprezentujacy dyskretny czas 0,1,2,3,… Zamiast pierwotnej kolejki
rozważamy teraz zbiór antionów. Niebieskie i czerwone antiony razem wzięte to właśnie ten zbiór. Nowa reguła będzie taka, że kernel sie najpierw zajmie antionami z minimalnym τ w zbiorze antionów. Kernel wybierze przypadkowo antion z minimalnym τ i wprowadzi go do aplikacji. Równocześnie podniesie w wybranym antionie licznik τ o jedynkę, czyli wykona τ = τ+1. Umieści zero, jeden, lub dwa antiony (wg. o(), t(), tx()) z tak zmodyfikowanym licznikiem do zbioru antionów i w końcu wykona return. W ramach następnej operacji t(), tx(), lub o() przejdzie do kolejnego przeszukiwania zbioru antionów. Widać, że jest to samo, jak w układzie z kolejką. Wprowadzona przypadkowość wyboru minimalnego antionu w zbiorze nie wpłynie na rezultat obliczenia. Rozwiązanie nr. 16 z kolejką jest prostsze, bo nie trzeba się zajmować sztucznym parametrem τ . W kernelu nr. 16 jest granica między τ i τ+1 w kolejce automatyczna.
Wyżej opisaną regułę asynchronicznego odpalania można okreslić jako globalną. W tym sensie, że jeden kernel zajmuje się całą chmarą antionów, czyli ma globalne spojrzenia na cały zbiór antionów. Opiszemy teraz kernel nr. 17 , w którym regułę asynchronicznego odpalania antioniowych operacji można określić jako lokalną. To będzie nowy paradygmat. W kazdym punkcie moze istnieć samodzielny kernel i zajmować sie tylko tym, co się dzieje w danym punkcie.
Będą dwa liczniki. Oprócz licznika „τ” dołączonego do antionów jak wyżej dołączymy do wszystkich punktów przestrzeni analogiczny licznik „c” . Kazda operacja w punkcie/ antionie automatycznie bedzie dodawać do obu liczników c i τ jedynke. Liczniki są jak zegary, które mierzą czas (ilość tików). Ale właściwie c i τ będą liczyć odległości w czasoprzestrzeni (ilosć przebytych antionowych/ punktowych krawędzi w czasoprzestrzennym diagramie). W synchronicznej interpretacji, gdzie mamy równoczesne odpalanie antionów (odpalają wszystkie antiony umieszczone wzdłuż pionowej osi w czasoprzestrzennym diagramie), mamy zawsze c= τ. Mechanizm kernelu nr. 17 polega na tym, że wybór antionu do odpalenia jest wprawdzie przypadkowy (i nie synchroniczny), ale musi być spełniony lokalny warunek c= τ. Fizyk by napisał c – τ = 0. Warunek jest lokalny, czyli w procesie obliczeniowym w róznych punktach/ antionach moga byc różne wartosci c= τ. Równoległy proces sterowany taką regułą prowadzi do tego samego rezultatu, jaki daje synchroniczny równoległy proces. Zakładamy, że liczniki c i τ są na początku (w punkcie „0” i w początkowym antionie) wyzerowane. Pojemność liczników jest nieograniczona.
Na przykładzie postaramy się zilustrować jak to działa. Obliczamy współczynniki dwumianu (x+1)n . Opuscimy powtarzające się syntaktyczne i operacyjne elementy w programie, żeby tekst programu był krótszy
binom = 1; // place „1” to initial point
xpand(pow(2,6) – 1); // expand to 0,1,2, … 63, function pow(2,6) returns 26
if (currentpoint) binom = 0; // place „0” to rest of points
for (k = 0; k <= 10; k = k + 1) // 10 razy
{
A = binom; // pick up binom
t(gtrans(63)); // gray transfer in subspace 111111
binom = binom + A; // add to binom
}
Najpierw zobaczmy przebieg synchronicznego obliczenia. Czas 0,1,2,3. … idzie w dół. W kolejnych wierszach 0,1,2,3,… i w punktach 0,1,3,2,6,7,5,4,12,.. wg kodu Graya, będą wartości jak w trójkącie Pascala. Czyli wartość „pod” jest sumą dwu wartosci „nad”. Tak jest dzięki instrukcji binom = binom + A :
1,0,0,0,…
1,1,0,0,0,0…
1,2,1,0,0,0,0,….
1,3,3,1,0,0,0,….
1,4,6,4,1,0,……
1,5,10,10,5,1,….
….
Teraz zobaczmy przebieg asynchronicznego obliczenia. Mozliwych asynchronicznych obliczeń jest więcej, wybieramy jedno z możliwych. Pierwszy schemat (dwa wiersze) przedstawia sytuację po idealnym synchronicznym rozmnożeniu. Poszczególne antiony oznaczyliśmy A,B,C,… Według programu mamy 64 antionów, które się poruszają w przestrzeni C64 (diagram Cayleya rysujemy jak koło, ostatni element jest połączony z pierwszym (zerowym)). Będziemy obserwowac sytuacje tylko dla antionów A,B,…H . Punkty przestrzeni nie oznaczylismy. Możemy sobie wyobrazic, ze poiniżej schematu jest sekwencja g0, g1, g2, … czyli sekwencja kodów Graya dla punktów 0,1,2,3, … (w dwójkowej notacji).
A0 B0 C0 D0 E0 F0 G0 H0
Licznik „τ” w antionach jest przedstawiony jako górny indeks. Liczba w dolnym wierszu to licznik „c” . Kazda operacja w punkcie/ antionie dodaje do obu liczników c i τ jedynke. Wybór antionu do odpalenia jest wprawdzie przypadkowy, ale musi być spełniony lokalny warunek c= τ. Przypuśćmy, że „przypadkowo” wybralismy na początek antion A (warunek c= τ jest spełniony). Odpalenie przesuwa antion o jedno miejsce wprawo i odpowiednie liczniki przechodza z zera na jedynkę, 0 -> 1. Antion A przechodzi z g0 do g1 i teraz w punkcie g1 mamy dwa antiony, A i B. I tak dalej. Przypadkowo wybrane antiony s oznaczone kolorem.
I tak dalej. Powyższa ilustracja nie jest pełna. Nie ma w niej opisu co sie dzieje z wartosciami binom i A. Nie ma opisu jak to wygląda w części ekspansji (zaczynamy od idealizowanego stanu, kiedy wszystkie antiony juz są rozmnożone i c = τ = 0). Opisujemy tylko operacje zwiazena z permutacjami t(). Nie docierany do końcowego stanu, kiedy wszystkie antiony wykonają o() i otrzymamy rezultat obliczenia. Odpalamy przypadkowo tylko parę antionów. Pełna ilustracja, albo raczej dowód, że rezultat obliczenia jest identyczny jak dla synchronicznego przypadku, by wymagała opisu wszystkich mozliwych przypadkowych odpaleń, wszystkich możliwych dróg aż do końca obliczenia. Naszym zamiarem było pokazanie zaskakującego zjawiska, że mianowicie antiony się zlepiają do punktów tworząc kolejkę !! To „odkrycie” jest podstawa implementacji kernelu nr. 17. Wcale nie trzeba wprowadzać parametry c i τ , wystarczy podtrzymywać dla kazdego punktu przestrzeni samodzielną kolejke antionów. „Dowód” ze taka konstrukcja kernelu jest poprawna polega na sprawdzaniu. Wykonujemy rózne aplikacje na róznych danych wykorzystujące kernel 17 i kernel 16. Porównujemy rezultaty. Wierzymy na podstawie poprzednich eksperymentów, że kernel 16 daje te same rezultaty co synchroniczne obliczenie. Jesli teraz kernel 17 daje w wyniku to samo co kernel 16, to znaczy, ze kernel 17 daje te same wyniki co synchroniczne obliczenie. I to jest cały „dowód”.