SKALOWALNOŚĆ:

-czyli zdolność automatycznego dostosowania pracy aplikacji do liczby dostępnych procesorów 
obliczeniowych. Dane i sekwencje sterujące wysyłane są przez proces sterujący do takiej liczby 
procesów obliczeniowych jaka jest dostępna. 

Skalowalność (ang. scalability) — zdolność systemu informatycznego do sprawnego działania w 
warunkach rosnącej liczby użytkowników, zwiększającej się wielkości przetwarzanych danych lub 
powiększającej się mocy obliczeniowej. Dotyczy również zawężania funkcjonowania systemu. 

Skalowalność (ang. scalability) - zapewnienie coraz wydajniejszej pracy w miarę zwiększania liczby 
elementów składowych. Jest to np. cecha sieci komputerowych polegająca na zdolności do dalszej 
rozbudowy.

Jeszcze do tego dostałem pytanie: „jaki warunek musi spełniać aplikacja aby można było powiedzieć że 
jest skalowalna?”
odpowiedzi nie ma

X. Model PRAM

W modelu przetwarzania sekwencyjnego kluczowa role pełni model maszyny RAM (random access 
machine). Kazda taka maszyna składa sie z ustalonego programu, jednostki obliczeniowej, tasmy (tylko 
do odczytu) z danymi wejsciowymi, tasmy (tylko do zapisu) na wynik działania programu oraz 
nieograniczonej pamieci o dostepie swobodnym. Ponadto kazda komórka pamieci jest w stanie 
zapamietac liczbe całkowita o nieograniczonym zakresie. Jednostka obliczeniowa nie jest 
skomplikowana – pozwala na wykonywanie najprostszych instrukcji takich jak: kopiowanie komórek 
pamieci, porównania i skoki
warunkowe, podstawowe operacje arytmetyczne itp. Ustalony program uzytkownika składa sie z ciagu 
takich instrukcji. Miara złozonosci programów dla maszyny RAM sa typowo
czas działania mierzony liczba wykonanych instrukcji i zuzycie pamieci mierzone liczba 
wykorzystywanych komórek. Zeby uchronic ten model przed zniekształceniami zabronione jest 
generowanie bardzo duzych liczb w krótkim czasie. Np. zabrania sie generowania
liczb o niewielowmianowej długosci zapisu w wielomianowym czasie. Mozna to osiagnac albo przez 
uwazny dobór zestawu instrukcji, albo przerzucajac odpowiedzialnosc na „twórców algorytmów” dla 
danego modelu. W ten sposób otrzymujemy game równowaznych modeli dla obliczen sekwencyjnych. 
Naturalnym uogólnieniem modelu RAM jest dodanie
wiekszej liczby jednostek obliczeniowych. Idee maszyny PRAM moze ilustrowac ponizszy schemat:

PRAM - załozenia

• Pamiec jest wspólna dla wszystkich procesorów.
• Kazdy procesor jest maszyna typu RAM.
• Wszystkie procesory działaja synchronicznie.
• Czas działania mierzymy liczba dostepów do pamieci współdzielonej.
• Zuzycie pamieci liczymy liczba uzytych komórek.
• Dodatkowym parametrem jest liczba uzytych procesorów. Tu zakładamy, ze w wielomianowym czasie 
mozna uzyc „tylko” wielomianowej liczby procesorów.

Uwagi do załozen

• Ostatni punkt załozen mozna rozwiazac np. w taki sposób, ze procesor P

1 

oblicza potrzebna

liczbe procesorów, a nastepnie włacza je wpisujac liczbe do odpowiedniego rejestru.
• Liczenie dostępów do pamięci ma taki sens praktyczny, ze zwykle wszelkie operacje typu 
komunikacyjnego zabierają znacznie wiecej czasu niz obliczenia lokalne.
• Wada założenia o jednostkowym czasie dostepu jest, wystepowanie w rzeczywistych systemach 
równoległych mechanizmów komunikacji o bardzo zróznicowanej wydajnosci.

Dostep do pamieci

Istniej kilka sposobów modelowania równoległego dostepu do pamieci współdzielonej.We wszystkich 
modelach zakładamy oddzielenie operacji zapisu i odczytu. Przyjmujemy, ze maszyna PRAM działa w 
cyklu składajacym sie z:
• (jesli potrzeba) czytaj z pamieci współdzielonej,
• (jesli potrzeba) wykonaj obliczenia lokalne,
• (jesli potrzeba) pisz do pamieci współdzielonej.
W ten sposób zakładamy, ze nie ma konfliktów typu:
jednoczesny zapis/odczyt.
Pozostaja jednak konflikty typu: jednoczesny zapis/zapis i odczyt/odczyt. Generalnie mozliwosci sa 
nastepujace:
• maszyna EREW-PRAM: nie dopuszcza sie konfliktów zadnego rodzaju,
• maszyna CREW-PRAM: dopuszcza sie konflikty typu jednoczesny odczyt,
• maszyna ERCW-PRAM: dopuszcza sie konflikty typu jednoczesny zapis,
• maszyna CRCW-PRAM: dopuszcza sie zarówno konflikty typu jednoczesny odczyt jak i jednoczesny 
zapis.
Przy czym w przypadku dopuszczenia jednoczesnego odczytu (CREW, CRCW) zakładamy, ze 
wszystkie procesory przeczytaja zadana komórke pamieci. W przypadku dopuszczenia jednoczesnego 
zapisu sytuacja jest bardziej złozona.
Rozwiazywanie konfliktów typu jednoczesny zapis
• ECR (equality conflict resolution) – jednoczesny zapis sie powiedzie, jesli wszystkie procesory próbuja 
zapisac to samo.
• PCR (priority conflict resolution) - zapis udaje sie tylko procesorowi o najwyzszym priorytecie. 
• ACR (arbitrary conflict resolution) - jednemu z procesorów zapis sie powiedzie.

x. Lista kontrolna w projektowaniu podziału

1. Liczba zadań powinna być co najmniej o jeden rząd większa niż liczba procesorów.
2. Ma być skalowalny (liczba zadań rośnie ze wzrostem rozmiaru problemu)
3. Czy nie jest zbyt duża liczba powieleń obliczeń i danych?
4. Czy zadania mają podobny rozmiar?

x. Lista kontrolna w projektowaniu komunikacji

1. Czy wszystkie zadania wykonują taką samą liczbę komunikacji?
2. Komunikacja powinna zapewnić równoległe wykonywanie komunikatów.
3. Czy każde zadanie komunikuje się tylko z niewielką ilością zadań sąsiadujących? Jeżeli nie to czas 
komunikacji może być większy od czasu obliczeń. 

x. Lista kontrolna w projektowaniu aglomeracji

1. Ilość zadań nie mniejsza niż ilość procesorów.

Algorytm wciąż ma być skalowalny (odp: zad18)

x. Planowanie statyczne i dynamiczne, przykład zastosowania

Statyczne – dokonujemy mapowania przed wykonaniem programu
Dynamiczne – mapowanie następuje podczas wykonania programu 
Gdy dane są niedokładne lub ich brak to stosujemy alg. dynamiczne w sys. scentralizowanych - kontrola 
wykorzystania mocy obliczeniowej (obciżenie) - ilość zadań wykonywanych na 1 komputerze 

x. Planowanie dokładne i heurystyczne, przykład zastosowania

Planowanie dokładne - korzystamy z funkcji celu z określeniem ekstremów (?) Planowanie heurystyczne 
- przybliża wynik. Stosowane najczęsciej.

x. Planowane scentralizowane i rozproszone, przykład zastosowania

Podział stosowany dla planowania dynamicznego(tylko) Zcentralizowane – procesor - koordynator jest 
odpowiedzialny za podział zadań na procesory Zdecentralizowane – brak koordynatora 
Scentralizowane – 1komp. podejmuje decyzje o mapowaniu. + prostota, - wąskie gardło (ogranicza 
skalowalność) Ropzroszone – wszystkie komputery podejmują decyzję wspólnie. + duża skalowalność, - 
duży czas planowania. 

x. Algorytmy planowania zadań

FCFS (ang. First Come, First Served)
Według tego schematu, ten z procesów, który pierwszy zgłosi zapotrzebowanie na procesor, otrzyma go 
jako pierwszy. Implementacja tego algorytmu jest wykonywana przy pomocy kolejki FIFO. Algorytm 
ten dokonuje najsprawiedliwszego przydziału czasu (każdemu według potrzeb), jednak powoduje bardzo 
słabą interakcyjność systemu - pojedynczy długi proces całkowicie blokuje system na czas swojego 
wykonania, gdyż nie ma priorytetów zgodnie z którymi mógłby zostać wywłaszczony. Algorytm ten 
stosuje się jednak z powodzeniem w systemach wsadowych, gdzie operator ładuje zadania do 
wykonania, a one wykonują się do skutku 

SJF (Shortest Job First) - Najpierw najkrótsze zadanie
Jest algorytmem optymalnym ze względu na najkrótszy średni czas oczekiwania. W wersji z 
wywłaszczaniem, stosowana jest metoda: najpierw najkrótszy czas pracy pozostałej do wykonania. 
Problemem tego algorytmu jest głodzenie długich procesów - może się zdarzyć, że cały czas będą 
nadchodzić krótsze procesy, a wtedy proces dłuższy nigdy nie zostanie wykonany.

Kolejki priorytetowe
Wybierany jest proces o najwyższym priorytecie. W tej metodzie występuje problem nieskończonego 
blokowania (procesu o niskim priorytecie przez procesy o wysokim priorytecie). Stosuje się tu 
postarzanie procesów, polegające na powolnym podnoszeniu priorytetu procesów zbyt długo 
oczekujących 

Rotacja (Round Robin)
Każde z zadań otrzymuje kwant czasu; po spożytkowaniu swojego kwantu zostaje wywłaszczone i 
ustawione na końcu kolejki 

Planowanie z wykorzystaniem wielu kolejek
Opiera się na podziale procesów pomiędzy poszczególne grupy, procesy są na stałe przypisywane od 
jednej z kategorii. Każda z kolejek może stosować swój własny algorytm kolejkowania, ponadto 
pomiędzy kolejkami powinno następować jakieś wybrane planowanie. Dodatkowo można przydzielać 
procentowe wartości czasu różnym kolejkom z uwzględnieniem ich ważności.
Planowanie z wykorzystaniem wielu kolejek ze sprzężeniem zwrotnym
Ten rodzaj planowania umożliwia przemieszczanie się procesów pomiędzy kolejkami, występują tu 
dodatkowe koszty związane z planowaniem, ale zyskujemy na elastyczności.

Planowanie zadań dla wielu procesorów
Należy rozróżnić systemy z identycznymi procesorami (homogeniczne) i różnymi procesorami 
(heterogeniczne). Dla środowiska heterogenicznego jest konieczne pisanie różnych programów na każdy 
z procesorów, natomiast w przypadku procesorów homogenicznych mamy do czynienia z planowaniem 
zadań bardzo zbliżonego do tego w systemie z jednym procesorem, jednak z dodatkowymi 
utrudnieniami. Można zastosować metodę ładowania dzielonego polegającą na przydzieleniu każdemu 
procesorowi oddzielnej kolejki zadań. Można również stosować wspólną kolejkę dla wszystkich 
procesorów. Należy wtedy jednak zapewnić, aby wszystkie procesy zostały prawidłowo wykonane 
(proces nie może być wykonywany przez dwa procesory, proces nie może zostać „zgubiony”). Należy 
część czasu jednego z procesorów przeznaczyć na planowanie zadań dla siebie i pozostałych 
procesorów. Takie podejście nazywane jest wieloprzetwarzaniem asymetrycznym.

x. Definicja i sposoby modelowania wydajności

Przez wydajność aplikacji rozumie się wiele aspektów,czas wykonania, przyspieszenie, efektywność, 
skalowalność, zasoby systemu, kosz, projektowanie i konserwacja aplikacji 
ekstrapolacja z obserwacje 
T=N + M

2

 / P

T = (M + M

2

) / P

podejscie oparte o prawo Amdala 
analiza asymptotyczna  O (N log N)  O(P) istnieje N

0

, że  N>=N

0

 , to koszt obliczeń <=N log N na P 

procesorów

x. Czas wykonania programu rozproszonego

T jest funkcja zależna od T=F(N,P,Moc), Ts=Tobliczen+Tkomunikacji+Tprzestoju. Czas wykonywania 
aplikacji rozproszonej to czas, który upływa od chwili, gdy pierwszy procesor zaczyna obliczenia a 
ostatni   kończy.T=1/P*(To+Tk+Tp)-jest   to   Tsumaryczny   TsObliczen   można   obliczyć   korzystająć   z 
aplikacji sekwencyjnej(brak Tk i Tp) TsKomunikacji = ts+l*tw [ts-czas starotowy;tw-czas przekazania 
jednego słowa,jednostki;l-ilość jednostek] T=(Tobl-Tkom)/P

x. Czas obliczeń

Czas  obliczen  jest  to  czas   ktory  procesy poswiecaja  na  obliczenia,  czyli   na  wykonywanie  operacji 
arytmetycznych i logicznych. Wraz ze wzrostem ilosci procesorow problem mozemy podzielic na coraz 
wiecej   podproblemow   i   laczny   czas   obliczen   dla   problemu   maleje.   TsObliczen   można   obliczyć 
korzystająć z aplikacji sekwencyjnej(brak Tk i Tp) Innym problemem jest to, ze wraz ze wzrostem ilosci 
procesow rozsnie czas komunikacji pomiedzy nimi (o tym w punkcie nastepnym).

x. Czas komunikacji

Czas komunikacji to czas, który procesy poświęcają na komunikowanie się między sobą. Wraz ze 
wzrostem ilości procesów czas potrzebny na komunikację wzrasta. Komunikacja ma na celu np. 
przekazanie wyników obliczeń jednego procesu do drugiego procesu. Optymalny czas wykonania 
programu uzyskujemy dla takiej liczby procesów, przy której suma czasów komunikacji i obliczeń jest 
minimalna (a nie jakby się mogło wydawać im więcej procesorów tym lepiej). Aby zmniejszyć czasy 
komunikacji w niektórych przypadkach możemy zastosować powielenie obliczeń (jeśli jest to 
korzystniejsze czasowo niż komunikacja).

x. Czas oczekiwania

Czas oczekiwania to czas, w którym procesy nie robią nic ze względu na to, że oczekują na zakończenie 
obliczeń przez inne procesy - na przykład gdy występuje synchronizacja barierowa lub gdy oczekują na 
dostęp do zasobów dzielonych (stoją pod semaforem). Czas oczekiwania może wynikać z braku danych 
luz z braku obliczeń

x. Model oparty na danych eksperymentalnych

a) określić wszystkie czynniki, które mogą mieć wpływ na T i dla których da się oszacować wartości: 
   T=(N, P, W, O)       - N wielkość prblemu, P - ilość procesorów, W - ilość wątków, O - pamięc  
operacyjna

b) wybrać strukturę modelu (liniowy, nieliniowy, etc.), np: 
c)badanie eksperymentalne: 
  /---|---|---|---|---|---
  | T | N | P | W | O | ...
  |---+---+---+---+---+---
  | x | x | x | x | x |         - x - jakaś dana
  |---+---+---+---+---+---
  | x | x | x | x | x |
  |---+---+---+---+---+---
  | x | x | x | x | x |
  |---+---+---+---+---+---
    .   .   .   .   .   .
d) z analizy wyników badania wygenerowane zostają współczynniki 
e) wykorzystanie modelu 

x. Komunikacja i synchronizacja w OpenMP

Synchronizacja:
W   przypadku   gdy   wymagane   jest   sekwencyjne   wykonanie   pewnego   fragmentu   kodu   w   sekcji 
równoległej,   możliwa   jest   jego   serializacja.   Przykładem   jest   synchronizowana   sekwencja   OMP 
CRITICAL,   do   której   w   danym   momencie   może   wejść   jeden   wątek,   sekcja   OMP   MASTER   – 
wykonywana jedynie przez wątek główny oraz OMP SINGLE – wykonywana przez dowolny wątek (nie 
można z góry określić który).

Przykład:

#pragma omp paralel for
for(int i=0; i<100; i++)
{

#omp single

printf(„START”);

operations(i);
#omp critical

synchronizacja(i);

#omp master

printf(„Master dziala”);

}

Ponieważ   wątki   mogą   działać   na   wspólnych   danych,   potrzebne   są   mechanizmy   synchronizacji 
zapewniające   uzyskanie   poprawnych   wyników.   OpenMP   dostarcza   konstrukcji,   które   umożliwiają 
prawidłową współpracę wątków. Są to:

a) Synchronizacja domyślna
b) Synchronizacja jawna

Synchronizacja domyślna występuje na końcu bloku kodu wybranych dyrektyw: OMP PARALLEL, 
OMP FOR, OMP SECTIONS, OMP SINGLE;
chyba że użyto klauzuli NOWAIT, która nakazuje brak synchronizacji wątków. Każdy wątek, który 
wykona swoją pracę i dojdzie do punktu synchronizacji, czeka na wszystkie pozostałe wątki. W chwili, 
gdy wszystkie wątki dojdą do punktu synchronizacji, każdy z nich wykonuje dalszą część programu lub 
następuje ich zniszczenie.
W   synchronizacji   jawnej   programista   może   sam   wskazać   miejsce   synchronizacji   poprzez   użycie 
dyrektywy OMP BARRIER.
Dodatkowo   OpenMP   udostępnia   mechanizm   sekcji   krytycznej.   Fragment   kodu,   który   może   być 
wykonany tylko przez jeden wątek w danym czasie, należy umieścić w bloku po dyrektywie  OMP 
CRITICAL.
Można   wskazać   także   operację   atomową,   czyli   polegającą   na   modyfikacji   jednej   komórki   pamięci, 
podczas której tylko jeden proces może te komórkę modyfikować (odczytywać). Operacją taką może 
być   inkrementacja,   dekrementacja   i   przypisanie   wartości   (pod   warunkiem,   że   do   obliczenia 
przypisywanej wartości nie wykorzystuje się modyfikowanej zmiennej). Wskazanie operacji atomowej 
odbywa  się poprzez użycie  dyrektywy OMP ATOMIC. Operacja atomowa często jest wspomagana 
sprzętowo,  dlatego  wykonywana  jest  efektywniej  niż  sekcja krytyczna.  Jednak  obecnie  kompilatory 
przeważnie wykonują operację oznaczoną jako atomową, zamieniając ją na sekcję krytyczną.
Do sterowania synchronizacją w OpenMP dostępne są także funkcje zarządzające ryglami (ang. lock), za 
pomocą których można zatrzymać aktywność wątku, aż do zwolnienia rygla.

Komunikacja pomiędzy wątkami:
Komunikacja między wątkami odbywa się z wykorzystaniem pamięci dzielonej.
Każdy wątek w sekcji równoległej posiada zmienne prywatne i zmienne dzielone – wspólne dla każdego 
wątku. Poprzez zmienne dzielone wątki mogą komunikować się, gdy znajdują się w tej samej sekcji 
równoległej. Zmienne  dzielone  deklarowane są przy wejściu do sekcji równoległej  jako PRIVATE, 
natomiast zmienne współdzielone jako SHARED.
Istnieje  także  możliwość  komunikacji  między  wątkami,  gdy działają  one w ramach  innych  grup w 
innych sekcjach równoległych, jednak tylko w przypadku, gdy w kolejnych sekcjach liczba wątków się 
nie zmienia. Wówczas wątki tworzone w kolejnych obszarach równoległych operują na tym samym 
zestawie   zmiennych.   Deklaracji   zmiennych   dla   wielu   sekcji   równoległych   w   jednym   programie 
dokonuje się za pomocą klauzuli THREAD-PRIVATE.

x. Model wykonywania programu w OpenMP

x. Szeregowanie iteracji w OpenMP(statyczne, dynamiczne, GSS)

Składnia:

schedule(type [, chunk])

Sposoby szeregowania operacji w pętli:

•

simple, static

•

dynamic

•

guided

•

runtime

•

Domyślnie kompilator przyjmuje zawsze szeregowanie statyczne

•

Dynamic   –   czas   wykonywania   się   nieznacznie   waha   w   poszczególnych   iteracjach   (np.   gdy   w   pętli 

stosujemy if-else, gdzie instrukcje w „if” wykonują się w podobnym czasie jak w „else”)

•

Guided – czas wykonywania poszczególnych iteracjach waha się znacząco

•

Runtime – stosujemy jeżeli nie wiemy jak pętle będą się zachowywać

Przykład:

#pragma omp for schedule(dynamic)

for(i=0;i<j;i++)

sum++;

DYNAMI

STATIC

GUIDED

t

(czas)

N

(liczba iteracji)

x. Zmienne "threadprivate", klauzula "copyin", przykłady zastosowania

•

Private  obowiązuje   tylko   w  zakresie  statycznym.  Natomiast  zmienna  taka   w  zakresie  dynamicznym 

będzie Shared. Po to właśnie warto stosować threadprivate.

•

Copyin powiązana jest z threadprivate. Ma taką rolę jak firstprivate.

Threadprivate
Dyrektywa threadprivate oznacza, że wszystkie zmienne podane jako parametry w lista będą 
prywatne dla wątków w całej przestrzeni programu. Składnia: 
   #pragma omp threadprivate (lista)  
Każda   z   kopii   zmiennej   jest   inicjowana   raz,   w   nieokreślonym   punkcie   programu,   przed 
pierwszym odwołaniem do niej. 
Copyin
Każda kopia zmiennej zadeklarowanej jako threadprivate i wymienionej w klauzuli copyin jest 
przy wejściu do bloku równoległego inicjowana wartością zmiennej z wątku głównego. Skłądnia 
klauzuli. 
   copyin (lista)

x. Wątki dynamiczne w OpenMP, przykłady zastosowania

OpenMP udostępnia mechanizm wątków dynamicznych. Dzięki niemu aplikacja może 
dynamicznie decydować ile wątków ma być utworzonych w regionie równoległym aby uzyskać 
możliwie jak największą wydajność. Konsekwencją uruchomienia wątków dynamicznych jest to, 
że użytkownik ustawiając ilość wątków w regionie równoległym, ustawia ich maksymalną, a nie 
dokładną ilość. Mechanizm wątków dynamicznych w OpenMP uruchamiany jest za pomocą 
zmiennej środowiskowej OMP_DYNAMIC. Zmienna ta przyjmuje wartości TRUE oraz FALSE. 
Dodatkowo mechanizm ten można uruchomić za pomocą funkcji z biblioteki OpenMP: 
omp_set_dynamic(). Aby dowiedzieć się czy uruchomiony został mechanizm wątków 
dynamicznych należy użyć funkcji omp_get_dynamic(). Wątki dynamiczne można w systemach 
w których wykonywanych jest wiele prac przez wielu użytkowników i użycie zasobów zmienia 
się dynamicznie.
Przykład:
//z dupy przykład
omp_set_dynamic(true);
omp_set_num_threads(4);
#pragma omp parallel
{

for(int i = 0; i < 4; i++)

std::cout << „Iteracja „ << i << std::endl;
}