Przepraszam, czy chciałoby się komuś wrzucić jakieś testy do tego zadania. Serdecznie Dziękuje :)

Ja nie rozumiem czemu KOL jest typu B i SEK typu A.
Na mój gust powinno być na odwrót.

jak na mój gust, to kółko jest znacznie prostsze :)

Paczka testów, głównie losowych (~5MiB):
https://toy.bzium.org/~embe/PA2014/kol.tar.bz2

Potwierdzam testy

Wszystkich nie sprawdzałem, tylko losowo wybrane po jednym z każdej wielkości, i się zgadzają. BTW, czy macie jakiś skrypt do testowania na dużej ilości plików?

Ja mam, ale działa tylko na Windowsie :)

Ja również mam Windowsa, jak zapewne spora część pozostałych. Czy mógłbym prosić o udostępnienie?

https://dl.dropboxusercontent.com/u/66374230/tester_rozproszone.zip

w katalogu roboczym musi znajdować się plik run.bat :)

help - /?

Edit: (Do sprawdzania poprawności outów polecam usunąć z run.bat wypisywanie ścieżki do pliku .in)

Testowanie lokalne swoją drogą, a wchodzi wam ten drugi test przykładowy 0b? :d

ledwo, ledwo
0b OK 4.89s/5.00s 20

U mnie 4.18/5.00.
Swoją drogą, ten sam test na programie jednoinstancjowym ma czas 3.74/5.00 :)

Ja mam czas 1.87/5.00

To chyba niepotrzebnie się stresuję moim 0.54s/5.00 ;)

Dzięki wielkie za testy, potwierdzam. Czas na 0b: 0.84/5.00

Taka mała sprawdzaczka, podaje czasy usermode w sekundach :)

$ for i in `seq 1 10` ; do /usr/bin/time -f'%U' ./local/run 10 kol.e < test/kol_MB_r_100000_$i.in | diff - test/kol_MB_r_100000_$i.out ; done
0.23
0.24
0.24
0.24
0.23
0.25
0.26
0.24
0.23
0.22

Niestety lokalny (jedno-procesorowy) pomiar czasu zadań rozproszonych jest bardzo trudny.

Receive() [z tego co widzę u siebie] uprawia spin-polling/busy-looping i tym samym żre 100% jednego procka aż otrzyma dane [pewnie bo nie używa blokujących syscall'i]. Tym samym spowalnia wszystkie pozostałe wątki wykonania.

Czy dzięki takiemu Receive() nie można wypisać każdym programem clock() i wybrać max?

Nie. Bo:

(a) HyperThreading oznacza że jeden wątek robiący Receive() spowalnia drugi wątek coś liczący na tym samym rdzeniu. Tym samym temu drugiemu wątkowi czas biegnie nawet do dwóch razy szybciej (do 2x mniej instrukcji na cykl) niż gdyby liczył na nie obciążonej maszynie.

(b) jeśli mamy mniej procków niż instancji to kolejność ich wykonywania jest 'at the mercy of the scheduler'

Wyobraźmy sobie 2 instancje:
(a) LiczCos(1 sekunda) Send(b) Receive(b) Exit()
(b) LiczCos(1 sekunda) Send(a) Receive(a) Exit()
Widać że powinno skończyć po 1 sekundzie (+ trochę czasu na synchronizację).

Wykonajmy to na 1 procesorze. Załóżmy, że scheduler quantum to 10 sekund (z reguły jest bliżej 10ms ale to tylko czyni kontr przykład trudniejszy do skonstruowania).

Scheduler wybiera wątek (b) - bo mu wolno.
Wątek (b) wykonuje się przez 10 sekund albo do czasu wykonania blokującego syscall'a (czyli nigdy bo nie mamy takich).

Przez pierwszą sekundę coś liczymy, Send(a) wsadza coś do jakiegoś bufora gdzieś i praktycznie zajmuje zero czasu. Następnie Receive(a) przez 9 sekund siedzi i bardzo aktywnie wysiaduje jaja na procku.

Skończył się 10s quantum. Scheduler wybiera wątek (a).
Wątek (a) liczy coś przez sekundę, robi Send(b) i Receive(b) w praktycznie zerowym czasie (bo dane już czekają w jakimś buforze) po czym robi Exit().

Scheduler wybiera wątek (b) [bo nie ma wyboru].
Wątek (b) otrzymuje dane i robi Exit()

(a) wykonywało się 1+epsilon sekund.
(b) wykonywało się 10+epsilon sekund.

Jak widać maksimum to 10+epsilon i jest większe od właściwego wyniku 1+epsilon sekund.

Trywialnie przykład rozszerzyć żeby minimum też było złe.
Np.
(a) 2x{ LiczCos(1 sekunda) Send(b) Receive(b) } Exit()
(b) 2x{ LiczCos(1 sekunda) Send(a) Receive(a) } Exit()

Właściwy czas 2+epsilon sekund.
A nam na powyższym schedulerze wyjdzie:
- przez 10 sekund [b] (1 licz1 + 0 send1 + 9 receive1)
- przez 10 sekund [a] (1 licz1 + 0 send1 + 0 receive1 + 1 licz2 + 0 send2 + 8 receive2)
- przez 1 sekund [b] (0 receive1 + 1 licz2 + 0 send2 + 0 receive2 + 0 exit)
- przez 0 sekund [a] (0 receive2 + 0 exit)

czas [a] = 10, [b] = 11, min = 10, max = 11, poprawny = 2
11 i 10.

---

W praktyce scheduling quantum jest dużo mniejszy więc będzie mniej rozbieżne, ale też odpalamy dużo więcej instancji, mamy _dużo_ mniej procków niż instancji, mamy hyperthreading oraz scheduler jest dużo bardziej losowy.

No i jeszcze dochodzą efekty związane z opróżnianiem się cache'u procesora przy każdej zmianie tego który wątek się liczy (plus przenoszenie się wątków z jednego procka na inny i znowu pusty cache).

#include <stdio.h>

#include "message.h"

volatile b;

int main (void) {
int NoN = NumberOfNodes();
int i;

for (i = 0; i < 400000000; ++i) ++b;

for (i = 0; i < NoN; ++i) Send(i);
for (i = 0; i < NoN; ++i) Receive(i);
}

Procek "Intel(R) Core(TM) i5-2520M CPU @ 2.50GHz" (2 cores x 2 HTs = 4 cpus)

1 Instancja:
real 0m1.050s
user 0m1.004s
sys 0m0.044s

(Jak widac tak dobrane zeby chodzilo ~sekunde)

100 Instancji:
real 0m35.150s
user 2m12.257s
sys 0m3.550s

user+sys = 135.8s, czyli (z Dirichleta) ktoryś z wątków musiał chodzić 1.358s

czyli max czas procesora po wszystkich instancjach >= 1.358s.
A wiadomo, że powinno chodzić bliżej sekundy.

Ktoś powie że te 0.358s to czas synchronizacji stu instancji.
Dobra zwiększamy 400,000,000 pięciokrotnie do 2,000,000,000.

1 Instancja:
real 0m4.595s
user 0m4.552s
sys 0m0.041s

(Jak widać nie całkiem 5 razy dłużej bo koszty rozruchu są spore)

100 Instacji:
real 2m47.122s
user 10m52.864s
sys 0m9.606s

user+sys = 662.47s, czyli któryś z wątków musiał chodzić 6.6247s
a wiadomo, że powinno być 4.6, czyli ~2s nadmiaru.

(bez petli zuzywajacej czas)

1 Instacja:
real 0m0.089s
user 0m0.041s
sys 0m0.046s

100 Instacji:
real 0m1.966s
user 0m2.220s
sys 0m1.288s

user+sys = 3.5s, czyli synchronizacja okolo 0.035s per instancje.

Widać, że to się nie zgadza i większość tych nadmiarów powyżej jest zupełnie sztuczna i wynikiem nie-blokującej natury Receive().

Z drugiej strony gdyby Receive() nie zużywało procesora to można by pomyśleć o takim kontrprzykładzie:

1. instancja coś liczy i wysyła wynik do instancji 2.
i. (1<i<n) instancja odbiera od i-1, coś liczy i wysyła wynik do instancji i+1.
n. instancja odbiera od n-1, coś liczy i wypisuje wynik na stdout.

W takim wypadku max czasów procesora byłby stały i zależał tylko od czasów obliczeń, natomiast ciężko mówić tu o jakimkolwiek zrównolegleniu (tylko jedna instancja coś liczy w danym momencie).

IMHO najlepiej byłoby żeby Receive() nie wisiało na procku, ale czas trwania był liczony z zegara a nie z procesorów.

Mogłyby być dopuszczone wątki przy zadaniach rozproszonych... skoro i tak rozpraszamy. Oczekiwanie na dostarczenie wiadomości nie blokowałoby maszyny.

To wogóle możnaby sprytnie na jednym rdzeniu zasymulować.

Trzeba by:
- sprytnie pilnować czasu zegara w każdym wątku (zegar[i]),
- zawsze wątek z najstarszym zegarem odpalać (ten z min zegar[i])
- puszczać wątek i-ty aż zużyje (timelimit-zegar[i]) czasu (jeśli tak to TLE) albo się zablokuje (na jakimś receive, zakładam, że bufory są na tyle duże że send się nie blokuje)
- zegar[i] += ile_czasu_procka_zużył

Oczywiście komunikaty międzymaszynowe trzeba ostemplowywać czasem zegarowym (wysyłającego wątku) w momencie ich wysłania i nie można ich dostarczyć przed tym czasem.

Jeśli w pewnym momencie wszystkie wątki czekają na dane, to patrzymy na zakolejkowane wiadomości, które można by dostarczyć (tzn. ktoś na nie czeka), spośród nich bierzemy tą którą można najwcześniej dostarczyć, docelowy procesor przeskakuje w przód w czasie do momentu wysłania/dostarczenia wiadomości, wiadomość dostarczamy i kontynuuje się zabawa.

Jeśli w pewnym momencie wszystkie wątki czekają na dane i nie ma nic do dostarczenia do się program zakleszczył i jest TLE.

(albo jakoś takoś)