PAR1

Question 1

zrychleni na jednom procesoru

Answer 1

S(n;p)/p

Question 2

práce asynchonniho systemu

Answer 2

W(n;p) = p1+p2+…+pn; kde pi=pocet pracujicich procesoru v kroku i (1;2;…n) a n=T(n;p)

Question 3

linearni zrychleni

Answer 3

S(n;p) = p

Question 4

vztahy ekvivalence

Answer 4

cenove optimalni – linearni zrychleni – konstantni efektivnost

Question 5

psi1(p)

Answer 5

asymptoticky minimalni fce takove ze n=ohm(psi(p)):E(n;p)>E0

Question 6

psi2(n)

Answer 6

asymptoticky maximalni fce takova ze p=O(psi2(n)):E(n;p)>E0

Question 7

superlinearni zrychleni

Answer 7

u sekvencniho jednoprocesoroveho je malo mista a musí se swapovat – u paralelniho to není potreba(vice mista ve sdilene pameti)

Question 8

spodni mez paralelniho casu

Answer 8

L(n;p)=SL(n)/p – nejmensi mozny cas za který muze p procesoru vyresit dany problem

Question 9

efektivnost

Answer 9

E(n;p) = SU(n)/C(n;p)

Question 10

paralelni zrychleni

Answer 10

S(n;p) = SU(n)/T(n;p) – nejlepsi zrychleni ve které muzeme doufat je p – ale to by procesory musely pracovat efektivne

Question 11

paralelni cas

Answer 11

T(n;p) – cas který uplyne od zacatku vypoctu do ukonceni vypoctu nejpomalejsiho procesoru

Question 12

optimalni sek alg

Answer 12

TAK (n) = Θ(SU (n)) = Θ(SLK (n))

Question 13

sekvencni spodni mez

Answer 13

SL(n)- nejhorsi casova slozitost nejlepsiho mozneho SA

Question 14

Sekvencni casova slozitost

Answer 14

T (n)

Question 15

cenove optimalni

Answer 15

C(n;p) = O(SU(n))

Question 16

co popisuje paralelni práce

Answer 16

popisuje skutecne vykonanou praci všech procesoru – nezapocitava nepracujici procesory

Question 17

Co plati u SL(n)

Answer 17

pro vsechna A plati T(n)=ohm(SL(n))

Question 18

absolutne minimalni cas

Answer 18

Je-li dano n; pak pmt je nejmensi počet procesoru; pro které T(n;pt)=absolutne minimalni cas Tmin
Je-li dano n, Tmin je cas nejrychlejisho zpracovani : pro vsechna p, T(n,p) >=T(n,pmt)=Tmin

Question 19

paralelni cena

Answer 19

C(n;p) = p x T(n;p) – u paralelniho vypoctu muzou nektere procesory skoncit s vypoctem driv coz ale shorsuje efektivnost protože necinne cekaji

Question 20

nejlepsi znamy

Answer 20

TAK (n) = Θ(SU(n)) = ω(SLK (n))

Question 21

co dela psi2(n)

Answer 21

udava asymptoticky nejvetsi počet procesoru který ještě poskytuje reseni dane instance problemu o velikosti n s konstatni E

Question 22

psi3(n)

Answer 22

asymptoticky minimalni fce takova ze p=ohm(psi3(n)) a p=O(pmt):T(n;p)=O(Tmin)

Question 23

jake dva pripady mohou nastat při zkoumani absolutne minimalniho casu ?

Answer 23

a) graf je klesajici a proto je pozadovany počet procesoru roven maximalnimu poctu (cas klesa umerne s poctem procesoru; kdy nakonci spracovava každý procesor konstatne slozitou operaci) b)graf po dosahnuti Tmin zase zacne stoupat (cas se zhorsuje → procesory delaji neefektivni praci) počet procesoru se hleda jako místo s první derivaci rovnou nule

Question 24

skalovatelnost PA

Answer 24

schopnost prizpusobit se menicimu se poctu procesoru nebo velikosti reseneho problemu – udrzet efektivnost nebo dobry cas

Question 25

co dela psi1(p)

Answer 25

udava asymptoticky nejmensi instanci problemu která je na danem poctu procesoru p resitelna s konstantni E

Question 26

sekvencni horni mez

Answer 26

SU(n) – nejhorsi casova slozitost nejrychlejsiho SA po K

Question 27

co dela psi3(n)

Answer 27

udava asymptoticky nejmensi počet procesoru; která vyresi velikost problemu n v radove optimalnim case

Question 28

pracovne optimalni

Answer 28

W(n;p) = O(SU(n))

Question 29

paralelni pocitac

Answer 29

je skupina propojenych vypocetnich prvku (uzlu), ktere spolupracuji, aby rychle vyresily narocne problemy