Trzy podstawowe fazy (bloki) obliczenia to expansja, permutacja, i retrakcja (epr). Taki schemat znajdziemy w wiekszości podstawowych równoległych algorytmów. Żeby dodać trochę tajemniczości do tego tematu przyrównam to do trójki Brahma, Vishnu, Shiva z hinudskiej mitologii … (znajdźcie w wikipedii).
Ekspansja
Ekspansja antionów do przestrzeni jest praktycznie obecna na poczatku kazdego antionowego programu. Jest na tyle częstym blokiem programowym, że w prob-16-bope.cpp znajdziecie funkcje, która was zwolni od nudnego wypisywania instrukcji tx(1); tx(2); tx(4); … Ale zeby było choć raz wiadomo o co chodzi w bloku ekspansji, pokażemy go szczegółowo. Spójrzmy na następujacy program.
#include <iostream>
#include “prob-16-kern.h”
extern int currentpoint;
int sizeofpoint = 4;
int pointdata; // zmienna punktowa (size 4)
int main()
{
pointdata = 1;
tx(1); tx(2); tx(4);
if (currentpoint) pointdata = 111;
cout << „currentpoint ” << currentpoint << ” ” << pointdata << ” \n”;
o();
}
Wkładamy program do Visual Studio, do prob-16-main (być może poprawimy cudzysłowy), i włączamy „Rebuild Solution”. Powinno być bez błędu. Następnie wchodzimy do „Start Without Debugging”. Program się wykona i w oknie „… Debug Console” otrzymamy
currentpoint 0 1
currentpoint 4 111
currentpoint 2 111
currentpoint 6 111
currentpoint 1 111
currentpoint 5 111
currentpoint 3 111
currentpoint 7 111
Program startuje w punkcie „zero”. Do zmiennej punktowej „pointdata” umiesci wartosc 1. Nastepuje sekwencja tx(1), tx(2), tx(4). Poczatkowy antion sie rozmnoży na dwa antiony w punktach 0,1. Następną instrukcję tx(2) wykonają więc dwa antiony. Otrzymamy 4 antiony w punktach 0,1,2,3. W ostatnim kroku ekspansji 4 antiony wykonaja rownocześnie instrukcję tx(4) i otrzymamy 8 antionów w punktach 0,1,2,3,4,5,6,7. Dalej 8 antionów drukuje swoje wartosci zmiennych „currentpoint” i „pointdata”. W koncu wszystkie antiony równoczesnie wyjdą z przestrzeni wykonując operację o().
Permutacja
Po fazie ekspansji bywa faza permutacja. Poniżej jest przykład. Po ekspansji do 8 punktów 3-kostki (do pointdata) umieszczamy jakąs liczbę integer przy pomocy funkcji wejscia „cin”. Nastepnie w cyklu dla generatorów k= 1,2,4 oblicza się suma włozonych liczb. Jest to modyfikacja programu „suma” pod stronicą VISUAL STUDIO. Program „suma” tam do wartosci „pointdata” ładował „random generator”. Tu trzeba przez klawiature 8 razy włozyc jakas liczbe. Program w cyklu wykonuje refleksje wzdłuz kolejnego generatora. Czyli wykonuje specjalną permutację, która jest bardzo charakterystyczna i bardzo czesta dla równoległych programów w hiperkostce.
#include
using namespace std;
#include „prob-16-kern.h”
#include „prob-16-bope.h”
extern int currentpoint;
int sizeofpoint = 8;
int pointdata; // 4 bytes
int k; // 4 bytes
int main()
{
int A;
tx(1); tx(2); tx(4); // expand to 3-cube
cin >> pointdata; // wczytuj liczbę
k = 1; // pierwszy generator
while (k < 8) { // cykl dla generatorów k = 1,2,4
A = pointdata; // pobierz czesciową sumę
t(k); // zrób refleksję wzdłuz generatora k
pointdata = pointdata + A; // oblicz nową częsciową sumę
k = k << 1; // weź następny generator
}
cout << „sum ” << currentpoint << ” ” << pointdata << ” \n”;
o();
}
Na przykład, jeśli do „cin” wczytamy 8 razy jedynkę, to wynik w kazdym „pointdata” bedzie 8. Przedstawiony program
Retrakcja
Retrakcja jest odwrotnością ekspansji. Retrakcję programujemy z wykorzystaniem kombinacji operacji t() i o(). Program retrakcji moze być użyteczny chociazby z tego powodu, że w jednym punkcie może być potrzebna informacja, że obliczenie całej chmury antionów z całą pewnoscią dobiegło końca. Albo też chcemy, żeby wynik obliczenia chmury antionów (jakas jedna liczba) znajdował się w jednym miejscu. Zazwyczaj w początkowym punkcie „zero”.
Pokażemy przykład. Chodzi o równoległą wersję algorytmu Hornera. Wielomian p(x)= a7x7 + a6x6 + a5x5 + a4x4 + a3x3 + a2x2 + a1x + a0 napiszemy w ekwiwalentnej formie ((a7x + a6) x2 + (a5x + a4))x4 + (a3x + a2) x2 + (a1x + a0). Opuszczamy początkowy tekst programu z ekspansją, dalej jest:
dla x= 2; currentpoint 0 a 255
dla x= 3; currentpoint 0 a 3280
dla x=1; currentpoint 0 a 8