Zadanie 3. Algorytmy rownolegle
-------------------------------

Algorytmy rownolegle sa jednym z przedmiotow zainteresowania algorytmiki.

Zaklada sie, ze algorytmy takie sa wykonywane przez wiele procesorow na
maszynie PRAM (Parallel Random Access Memory), czyli na komputerze, w ktorym
swobodny rownolegly dostep do wspolnej pamieci maja wszystkie procesory. Jeden
z prostych algorytmow polega na obliczeniu dla kazdego wezla i n-elementowej
listy, liczby wezlow d(i) znajdujacych sie za nim. Klasyczny algorytm
sekwencyjny realizujacy to zadanie dzialalby w czasie liniowym i wygladalby
mniej wiecej tak:
         _
        /
        | 0                     jesli next (i) = nil 
  d(i) =|   
        | d(next (i)) + 1       wpp. 
        \_

W powyzszym opisie i oznacza wezel listy, a next (i) wezel znajdujacy sie
bezposrednio za nim. 

Algorytm rownolegly rozwiazujacy ten problem dziala nastepujaco. Z kazdym
wezlem listy zwiazujemy jeden procesor. Procesor i-ty jest zatem odpowiedzialny
za i-ty wezel listy. Nastepujaca procedura oblicza wartosc d(i) w kazdym wezle
w czasie O(log n):

  for each processor i in parallel do
    if next(i) = nil then d(i) = 0 
                     else d(i) = 1
  while istnieje obiekt i taki, ze next (i) <> nil do 
    for each processor i in parallel do
      if next (i) <> nil then 
        d(i) := d(i) + d(next (i));
        next(i) := next(next(i))

Instrukcja for each i in parallel polega na rownoleglym wykonaniu swojej tresci
na wszystkich procesorach. Bardziej szczegolowy opis tego algorytmu mozna
znalezc w ksiazce: Cormen, Leiserson, Rivest "Wprowadzenie do algorytmow"
(rozdzial 30.1.1).  

Jak widac po tym zapisie algorytmicy nie troszcza sie o kwestie zwiazane z
zapewnieniem prawidlowej synchronizacji, zadowalajac sie przedstawieniem
algorytmu oraz zalozeniem, ze wnetrze petli wykonuje sie synchronicznie, czyli
ze wszystkie procesory i odczytuja najpierw wartosc d(i), potem d(next(i)), a
dopiero potem dokonuja modyfikacji wartosci.

Napisz program realizujacy przedstawiony algorytm. Program glowny powinien
pobrac z linii polecen jeden argument N: dlugosc listy. Nastepnie powinien
utworzyc liste dlugosci N i z kazdym z jej wezlow zwiazac osobny watek
("procesor"). Watek glowny powinien nastepnie poczekac na zakonczenie dzialania
wszystkich watkow i wypisac na standardowym urzadzeniu wyjsciowym obliczone
wartosci d(i). Watki nalezy synchronizowac za pomoca mechanizmow muteksow i/lub
zmiennych warunkowych w sposob zapewniajacy przenosnosc napisanego programu.

Termin odbioru zadania - zajecia nr 13.

Wszelkie pytania prosze kierowac na adres: mengel@mimuw.edu.pl

Powodzenia.