78 4.4.1. Hazardi uzrokovani zavisnošću po podacima Pristup zajedničkim varijablama za čitanje/pisanje od strane različitih instrukcija koje se nalaze u protočnom sistemu, može dovesti do različitih rezultata ako se instrukcije izvedu različitim redoslijedom. Ovaj tip zavisnosti između instrukcija se naziva zavisnost po podacima. Mijenjanje originalnog redoslijeda instrukcija je dopustivo samo ako to mijenjanje nema uticaja na konačan rezultat izvršenja programa. Ukoliko se instrukcije, između kojih postoji zavisnost po podacima, ne izvode po originalnom redoslijedu, dolazi do logičkih hazarda (sl. 4.9). Sl. 4.9 Mogući hazardi uslijed zavisnosti po podacima Posmatrajmo dvije instrukcije I i J, pri čemu J logički slijedi instrukciju I, a između njih postoji neka od zavisnosti sa sl. 4.9. Ukoliko dođe do promjene originalnog redoslijeda instrukcija, dolazi do nekorektnog čitanja ili upisa, odnosno dolazi do hazarda. Hazardi treba da budu onemogućeni tako da se spriječi izvođenje instrukcije J prije instrukcije I. Ako se sa D(I) označi domen instrukcije I (skup varijabli koje instrukcija I čita/ koristi kao operande), a sa R(I) označi opseg/skup varijabli u koje instrukcija I upisuje vrijednosti, onda između instrukcija I i J postoji zavisnost po podacima ako je: R(I) ∩ D(J) ≠ 0 R(I) ∩ R(J) ≠ 0 D(I) ∩ R(J) ≠ 0 ( RAW zavisnost po podacima) ( WAW zavisnost po podacima) ( WAR zavisnost po podacima) 79 Ipak, mogućnost preuređenja redoslijeda izvršenja instrukcija je poželjna, jer se time može postići veće iskorištenje protočnog sistema i povećati brzina obrade. Pri tome, međusobne relacije u redoslijedu izvođenja između instrukcija između kojih postoji zavisnost po podacima treba da budu sačuvane. Primjer efekta preuređenja instrukcija dat je na sl. 4.10 za 7-stepeni protočni sistem. U fetch stepenu (F), vrši se pribavljanje instrukcije iz memorije za jedan ciklus. U stepenu dekodiranja (D), dekodira se funkcija koju treba realizovati, i identifikuju potrebni resursi (registri, magistrale, funkcionalne jedinice). Stepen I vrši rezervisanje resursa onemogućavanjem pristupa resursima za izvođenje drugih instrukcija. U ovoj fazi se takođe vrši očitavanje operanada iz registara i dovođenje operanada na ulaz funkcionalnih jedinica. Instrukcije se izvode u jednom ili više izvršnih (E)stepeni. U W stepenu se vrši upis rezultata u odredište. Sl. 4.10 Protočno izvođenje instrukcija X = Y + Z, i A = B * C u originalnom i preuređenom redoslijedu 80 U primjeru je ilustrovano izvođenje instrukcija visokog nivoa X = Y + Z, i A = B * C u protočnom sistemu. Na slici 4.10 b) je predstavljeno izvođenje po originalnom redoslijedu instrukcija. Osjenčeni kvadratići reprezentuju cikluse kada je iniciranje instrukcija blokirano ili zbog konflikta u pristupu resursima, ili zbog zavisnosti po podacima. Iniciranje izvršenja prve dvije Load instrukcije je u sukcesivnim ciklusima. Add instrukcija čeka na iniciranje 3 ciklusa, dok oba operanda ne postanu raspoloživa. Sličan je slučaj i sa smještanjem rezultata sabiranja u memoriju. S obzirom da ova instrukcija mora da čeka, s jedne strane raspoloživost D stepena (3 ciklusa) a zatim i raspoloživost rezultata (2 ciklusa), smještanje rezultata operacije sabiranja u memoriju ima ukupno 5 ciklusa kašnjenja. Slična razmatranja su i za izvođenje operacije množenja. Na sl. 4.10 c), prikazano je izvođenje istih operacija sa preuređenim redoslijedom. Ideja je da se sve 4 load operacije izvedu na početku, a operacije add i multiply kasnije, čime se obezbjeđuje bolja raspoloživost podataka za ove instrukcije i smanjenje broja ciklusa čekanja za izvršenje ovih instrukcija. Raspoređivanje instrukcija za izvođenje Planiranje redoslijeda izvršenja instrukcija je moguće u fazi prevođenja (statičko raspoređivanje) i u toku samog izvršenja (dinamičko raspoređivanje). Statičko raspoređivanje obavlja prevodilac, na osnovu analize programa i utvrđivanja zavisnosti po podacima između instrukcija. Prevodilac nastoji povećati rastojanje između iniciranja izvršenja instrukcija kod kojih postoji zavisnost po podacima. Na taj način se obezbjeđuje raspoloživost operanada za pristup od strane instrukcije čije izvršenje zavisi od izvršenja neke prethodne instrukcije, kao što je to ilustrovano prethodnim primjerom. Ova tehnika je jednostavnija za implementaciju, ali se u procesorima visokih performansi primjenjuje dinamičko raspoređivanje instrukcija za izvršenje, za što je potrebna odgovarajuća hardverska podrška. Dinamičko raspoređivanje je prvi put implementirano u sistemu IBM 360/91 sa višestrukim funkcionalnim jedinicama za operacije u pokretnom zarezu. Koncept hardverske platforme je predstavljen na sl. 4.11. 81 Sl. 4.11 Protočni procesor sa višestrukim funkcionalnim jedinicama i distribuiranim stanicama za rezervaciju na bazi markiranja. (sl.6.12) Šema (Tomasulov algoritam) razrješava konflikte u korištenju hardverskih resursa i obezbjeđuje redoslijed izvršenja određen zavisnošću po podacima na bazi markacije registara (register tagging) . Ukoliko pri iniciranju izvršenja instrukcija potrebni operandi nisu raspoloživi, onda se instrukcija prosljeđuje u rezervacionu stanicu (RS) sa odgovarajućim markiranjem potrebnih registara/operanada. Instrukcija čeka u RS dok se prethodno ne izvedu sve potrebne instrukcije u cilju očuvanja zavisnosti po podacima i dok potrebni operandi ne postanu raspoloživi. Kada se ti uslovi ispune (signaliziranjem odgovarajućom markacijom od strane tag jedinice), instrukcija se iz RS prosljeđuje funkcionalnoj jedinici za izvršenje. Na sl. 4.12. prikazano je izvršavanje instrukcija X = Y + Z, i A = B * C sa minimalnim brojem (3) registara, koristeći Tomasulov algoritam. Kada se pojavi rezultat neke operacije na magistrali sa odnosnom markacijom, onda i odredišni registar i RS koja očekuje odnosni podatak, ažuriraju svoj sadržaj. Ako time neka instrukcija/operacija postaje raspoloživa za izvršenje, onda se ona prosljeđuje funkcionalnoj jedinici sa potrebnim operandima. 82 Sl. 4.12 Dinamičko raspoređivanje instrukcija Tomasulovim algoritmom. Sl. 4.13 Dinamičko raspoređivanje instrukcija za izvršenje u CDC 6600 računaru. Slično rješenje primijenjeno takođe davno, u računaru CDC 6600 (sl. 4.13). Instrukcije koje dolaze u protočni sistem se iniciraju za izvršenje i prosljeđuje odgovarajućoj izvršnoj jedinici bez 83 obzira na raspoloživost operanada. U izvršnim jedinicama, instrukcije sa svojim kontrolnim informacijama čekaju u baferu na potrebne podatke, koje produkuju druge instrukcije. Za kontrolu raspoloživosti podataka, omogućenje instrukcija i upravljanje funkcionalnim jedinicama koristi se centralizovani kontroler (scoreboard). 4.4.2. Strukturni hazardi Ovaj tip hazarda se javlja kada dolazi do konflikta u korištenju hardverskih resursa procesora. Npr. ako posmatramo idealan slučaj rada skalarnog RISC procesora koji izvodi jednu instrukciju u svakom ciklusu, onda je memorijski port stalno zauzet. Ukoliko se izvodi instrukcija Load/Store onda će se zahtijevati (dodatno) obraćanje memoriji za pribavljanje/smještanje operanda, što generiše konflikt u pristupu memoriji Sl. 4.14). Sl. 4.14 Zastoji kod protočne obrade zbog strukturnih hazarda. S obzirom na to da je procenat Load/Store instrukcija u ukupnom broju instrukcija koje se izvršaaju visok, ovi konflikti mogu značajno da degradiraju performanse sistema. Da bi se riješio ovaj problem RISC procesori često koriste dual-port memorije, tako da se instrukcijama i podacima može pristupati nezavisno. Sličan problem nastaje kada više instrukcija zahtijeva korištenje iste funkcionalne jedinice istovremeno. U cilju eliminisanja ovakvih konflikata, kako je to prezentovano i u prethodnim primjerima, realizuju se procesori sa višestrukim funkcionalnim jedinicama. 84 4.4.3. Upravljački hazardi Zastoj u protočnom sistemu može biti uzrokovan i promjenom instrukcionog toka (uzrokovanom izvođenjem instrukcijama grananja i drugih instrukcija koje mijenjaju kontrolni tok). Pri promjeni instrukcionog toka potrebno je izračunati ciljnu adresu grananja i eventualno uslove na osnovu kojih se odlučuje o grananju (kod instrukcija uslovnog grananja). Ciljna adresa nije uvijek unaprijed poznata: ona se često mora izračunati/dobiti u toku izvršenja instrukcije. Izvršavanje instrukcija grananja posjeduje određene specifičnosti koje mogu uticati na pojavu zastoja u protočnom sistemu a to su: • • • • Instrukcija koja se izvodi nakon instrukcije grananja zavisi od rezultata izvršenja same instrukcije grananja, Operand na osnovu kojeg se procjenjuje uslov grananja može zavisiti od neke ranije instrukcije, Ako se grananje obavlja, pribavljanje i izvršenje naredne instrukcije ne može početi sve dok se ne sračuna BTA (branch transfer addresss), Sračunavanje BTA može zavisiti od neke ranije instrukcije. Zbog navedenog, kao i zbog činjenice da je procenat izvođenja instrukcija grananja visok, posebna pažnja se posvećuje smanjenju negativnih efekata pri izvođenju ovih instrukcija. Efekat izvršavanje instrukcije grananja na performanse protočnog sistema je ilustrovana slikama 4.15 i 4.16. Pretpostavimo da se izvodi niz instrukcija: Ii Ii+1 Ii+2 Ii+3 . . (grananje na instrukciju Ij) Ij Ij+1 . . Sl. 4.15 Izvršavanje instrukcije grananja u nizu instrukcija 85 S. 4.16 Izvršenje toka instrukcija u protočnom sistemu za slučaj grananja Nakon kompletiranja instrukcije I2, izvršenje instrukcija I+3 … I+6 koje su započete se prekida u protočnom sistemu (protočni sistem se prazni). Na taj način u ciklusima 9-12 ne dolazi do kompletiranja instrukcija, pa su to izgubljeni ciklusi / cijena izvršenja instrukcije grananja. U cilju analize efekata grananja, definišimo slijedeće pojmove: • • • Ostvarenje grananja (branch taken), akcija pribavljanja ne-sekvencijalne/ udaljene instrukcije nakon izvođenja branch instrukcije, Meta grananja (branch target) je instrukcija koja se izvodi u slučaju ostvarenja grananja, Slotovi kašnjenja (delay slots), broj neiskorištenih ciklusa b u k-stepenom protočnom sistemu, između instrukcije u kojoj je došlo do ostvarenja grananja i mete grananja ( 0 ≤ b ≤ k-1 ). Za ilustraciju, posmatrajmo sl. 4.17, gdje ostvarenje grananja u toku izvršenja instrukcije Ib uzrokuje pražnjenje svih instrukcija Ib+1 … Ib+k-1 iz protočnog sistema. Neka je p vjerovatnoća instrukcije uslovnog grananja u programu, q vjerovatnoća da će se grananje ostvariti (tipične vrijednosti su p = 20%, q = 60%). Cijena grananja je pqnbτ , jer je očekivani broj grananja pqn a cijena jednog grananja bτ. Ukupno vrijeme izvođenja n instrukcija je: Teff = kτ + (n – 1) τ + pqnbτ (4.2) 86 ( član kτ + (n – 1) τ je vrijeme izvođenja n instrukcija bez gubitaka ciklusa u protočnom sistemu). Efektivna propusnost protočnog sistema Heff se definiše kao broj instrukcija koje se kompletiraju u jedinici vremena: Heff = n nf = Tett k + n − 1 + pqnb (4.3) Kada n → ∞ , onda je najniža granična vrijednost za Ηeff (b = k – 1) Heff * = f pq(k − 1) + 1 (4.4) Kada je p = q = 0 (nema grananja), onda se dobija da je maksimalna propusnost protočnog sistema f = 1/τ. Degradacija performansi protočnog sistema zbog efekta grananja je 1 f − Heff * pq (k − 1) = 1− = D= f pq (k − 1) + 1 pq (k − 1) + 1 (4.5) Sl. 4.17 Grananje u protočnom sistemu sa b = k – 1 slotova kašnjenja. 87 U cilju smanjenja cijene grananja koriste se različite tehnike: A. Zakašnjeno grananje (delayed branch), B. Predviđanje grananja, C. Druge tehnike smanjenja cijene grananja. A. Zakašnjeno grananje Prilikom izvršenja instrukcije grananja, utvrđivanje da li će se grananje izvesti ili ne može se realizovati u različitim stepenima protočnog sistema, zavisno od njegove implementacije. Zavisno od toga u kom stepenu se donosi odluka o grananju, ciljna instrukcija se pribavlja sa određenim brojem ciklusa zakašnjenja. Ako je to kašnjenje d ciklusa, onda se u protočnom sistemu nalazi d1 instrukcija između instrukcije grananja i mete - instrukcije na koju se grananje vrši (sl. 4.18). Sl. 4.18 Koncept zakašnjenog grananja premještanjem nezavisnih ili NOP instrukcija u slot kašnjenja za 4-stepeni protočni sistem. 88 Umjesto da se u slučaju grananja prazne sve instrukcije u protočnom sistemu između instrukcije grananja i mete ( pri čemu dolazi do gubitka b = d - 1 ciklusa ), kod ove tehnike se nastavlja sa izvršenjem jednog broja ( b ) instrukcija iza instrukcije grananja bez obzira na to da li je grananje izvršeno ili ne. Ono što je potrebno obezbijediti je da su to korisne instrukcije, čije je izvođenje iza instrukcije grananja valjano i za slučaj grananja i za slučaj kada nema grananja, ili da su to instrukcije popune tipa NOP ( No OPeration). Po statističkim analizama, vjerovatnoća mogućnosti premještanja jedne korisne instrukcije u slot kašnjenja je ~0.6, premještanja dvije korisne instrukcije u slot kašnjenja je ~0.2, a tri korisne instrukcije je manja od 0.1. Instrukcije koje se umeću u slot kašnjenja mogu biti (sl. 4.19): • • • Instrukcije ispred instrukcije grananja, Instrukcije sa puta gdje se grananje obavlja, Instrukcije sa puta gdje se grananje ne obavlja. Sl. 4.19 Različite varijante umetanja instrukcija u slot od jednog ciklusa zakašnjenja. Prilikom umetanja instrukcija potrebno je sačuvati originalne relacije zavisnosti po podacima između instrukcija i obezbijediti da modifikovani program produkuje isti rezultat kao originalni program. Primijetimo da umetanje instrukcije koja se nalazi ispred instrukcije grananja u slot kašnjenja uvijek rezultuje izvršavanjem korisne instrukcije, i za slučaj grananja smanjuje kašnjenje u slotu 89 (sl. 4.19a). Ubacivanje instrukcije sa puta grananja u slot kašnjenja je korisno samo u slučaju grananja (sl. 4.19b), a instrukcije sa puta gdje se grananje ne obavlja ako nema grananja (sl. 4.19c). Primijetimo da je za slučaj b) originalna meta (ciljna instrukcija) grananja pomjerena u slot kašnjenja i uvijek će se izvesti, a da je nova meta grananja slijedeća instrukcija iza originalne mete (instrukcija na adresi L+1). Ako dođe do grananja izvešće se sekvenca: Br > , L+1 R6 := R7 + R8 ; Jer se izvršavaju instrukcije u slotu kašnjenja L+1: ---------------- ; Nova meta grananja, a ako ne dođe do grananja izvela bi se sekvenca: Br > , L+1 R6 := R7 + R8 R6 := R8 + R9 ; Jer se izvršavaju instrukcije u slotu kašnjenja ; Instrukcija iz originalne sekvence, za slučaj da nema grananja. Primijetimo da će se, za slučaj kada nema grananja, u slotu kašnjenja izvesti instrukcija R6 := R7 + R8 koja u originalnoj sekvenci ne bi trebala da se izvede. Međutim. S obzirom na to da će se nakon toga izvesti instrukcija R6 := R8 + R9 koja takođe modifikuje registar R6 i time poništava efekat umetnute instrukcije R6 := R7 + R8. Dakle, umetnuta instrukcija u slučaju grananja eliminisaće kašnjenje u slotu, a za slučaj da nema grananja izvođenje umetnute insturkcije neće imati efekta. Slična razmatranja su i za slčučaj 4.19c). Preuređenje programske sekvence u cilju popune slota kašnjenja je najčešće zadatak programskog prevodioca. Međutim, problem sa prethodnom tehnikom gdje se insturkcije iz slota kašnjenja uvijek izvode proizilaze iz teškoće da se slot popuni korisnim instrukcijama. Alternativno rješenje je da se protočni sistem prazni ili ne u zavisnosti od toga da li se grananje realizuje ili ne. Suštinski, postoje tri mogućnosti: 1. 2. 3. Instrukcije u slotu kašnjenja se uvijek izvode, Protočni sistem se prazni (poništavaju se instrukcije u slotu kašnjenja), ako se grananje ne obavlja, Protočni sistem se prazni (poništavaju se instrukcije u slotu kašnjenja), ako se grananje obavlja. 90 Navedene varijante se mogu specifikovati od strane kompajlera kodiranjem u dvobitno polje instrukcije (kod procesora koji dopuštaju takvu mogućnost). Ako prevodilac ne može implementirati efikasno varijantu 1., i ako zaključuje da će se najčešće za neku instrukciju grananja grananje i ostvariti, onda prevodilac popunjava slot kašnjenja instrukcijama sa puta grananja, a u dvobitno polje instrukcije kodira varijantu 2. Primijetimo da ova varijanta povećava obim/dužinu programa zbog kopiranja instrukcija sa puta grananja u slot kašnjenja. B. Predviđanje grananja Predviđanje da li će se grananje desiti ili ne, može se izvršiti statički – u fazi prevođenja (na bazi karakteristika – koda instrukcije grananja), ili dinamički, na bazi istorije grananja registrovane za vrijeme izvođenja programa. Statistički podaci govore, da se kod instrukcija uslovnog grananja grananje češće događa ( > 50% u odnosu na ukupan broj izvršenja instrukcije) odnosno da se povoljniji rezultati dobijaju ako se predviđa izvršenje grananja. Eksploatacija slotova kašnjenja za slučaj ispravnog predviđanja grananja je opisana prethodno. Statičkim predviđanjem se može postići tačnost predviđanja koja je veća od 75%. Kod Dinamičke strategije grananja, predviđanje da li će doći do grananja ili ne pri izvođenju neke instrukcije grananja se bazira na prethodnoj istoriji grananja odnosne instrukcije. Primjer dinamičkog predviđanja grananja na bazi (ograničene) prethodne istorije grananja je predstavljeno slikom 4.20. Za implementaciju dinamičkog grananja koristi se bafer ciljnog grananja BTB (Branch target buffer) Dinamičkim predviđanjem grananja sa jednim bitom istorije, može se postići tačnost predviđanja između 86% i 96%, C. Druge tehnike smanjenja cijene grananja U cilju eliminisanja negativnih efekata grananja primjenjuju se i druge tehnike. Jedna od mogućnosti je da procesor pribavlja istovremeno instrukcije sa oba puta: i sa puta grananja i sa puta kada se grananje ne izvršava. Kada se utvrdi koji je put nekorektan, onda se efekti 91 pribavljanja i izvršenja instrukcija sa tog puta poništavaju. Problem kod ovog rješenja je što kada postoje 2 nerazriješena grananja, procesor treba da pribavlja instrukcije sa četiri puta. Sl. 4.20 Bafer istorije grananja i dijagram stanja grananja za dinamičku predikciju grananja. Tehnika višestrukih nezavisnih nizova instrukcija koristi nezavisne instrukcione tokove (programski tok druge programske niti - thread, npr.) za popunjavanje slotova kašnjenja. S obzirom da ne postoji zavisnost po podacima nezavisnih programskih niti, ove instrukcije se mogu umetati u slotove kašnjenja, pri čemu je to izvršavanje uvijek korisno, te nema neiskorištenih ciklusa u protočnom sistemu. 92 4.5 Superskalarne i VLWI arhitekture Arhitektura CISC i RISC skalarnih procesora može se dalje poboljšati implementacijom koncepata superskalarnog ili vektorskog procesiranja. Dok skalarni procesori izvode jednu instrukciju po ciklusu, kod superskalarnih procesora se koristi više funkcionalnih protočnih sistema, čime se omogućava da se u jednom ciklusu inicira i kompletira izvršavanje više instrukcija. Vektorski procesori izvršavaju vektorske instrukcije na nizovima podataka što je pogodno za protočnu obradu (izvršenje skupa operacija kojima se implementira vektorska instrukcija se ponavlja nad nizom podataka). O vektorskim procesorima biće riječi više u dijelu o SIMD računarima. Superskalarni procesori Ovi procesori su projektovani sa ciljem eksploatacije paralelizma na instrukcionom nivou: instrukcije između kojih ne postoji zavisnost po podacima se mogu izvoditi paralelno. Međutim, statistički pokazatelji ukazuju da se prosječno mogu izvoditi svega dvije instrukcije paralelno u prosječnom programu, bez specifičnih softverskih adaptacija programa (razmotavanje petlji, npr.). Ovo limitira broj iniciranja izvršenja instrukcija po ciklusu na 2-5. Superskalarni procesor stepena m može inicirati izvršenje m instrukcija po ciklusu. Tok izvršenja instrukcija u superskalarnom protočnom sistemu sa iniciranjem 3 instrukcije po ciklusu, ilustrovan je na sl. 4.21. Sl. 4.21. Tok izvršenja instrukcija u 3-stepenom superskalarnom sistemu. 93 Superskalarni procesor stepena m bi radio sa maksimalnim performansama ukoliko bi kontinualno izvodio m instrukcija istovremeno. U praksi, zbog prethodno navedene zavisnosti između instrukcija, u pojedinim ciklusima je broj instrukcija koje se iniciraju za izvršenje (odnosno čije se izvršenje kompletira) manji od m. U tim ciklusima, neki segmenti nekih protočnih sistema se mogu nalaziti u stanju zastoja. Tipična superskalarna arhitektura RISC procesora predstavljena je na sl. 4.22. Instrukcioni keš omogućava pribavljanje i iniciranje izvršenja više instrukcija u jednom ciklusu. Cjelobrojna jedinica i jedinica u pokretnom zarezu sadrže više funkcionalnih jedinica, koje teoretski mogu istovremeno da vrše procesiranje. U cilju podrške za efikasno i istovremeno izvođenje više instrukcija u različitim protočnim stepenima implementiraju se stanice za rezervaciju i baferi preuređenja. Primjer superskalarnih procesora su Intel i960, IBM RS/6000 i DEC 21064. Sl. 4.22. Tipična arhitektura RISC superskalarnog procesora. 94 Intel i960 je 32-bitni, RISC bazirani superskalarni procesor (sl. 4.23) je namijenjen za računarske sisteme koji se 'ugrađuju' u procese (embedded computer systems). Na procesorskom čipu su ugrađeni vremenski brojači, programibilni kontroler prekida i brzi RAM veličine 2Kb, kontroler pristupa memoriji te instrukcioni keš i keš za podatke. Koncept 'zaključavanja' resursa na bazi tabela (scoreboarding) obezbjeđuje logički integritet sekvencijalnog redoslijeda izvršenja instrukcija koje se izvode paralelno. Procesor omogućuje izvođenje 2 instrukcije po osnovnom taktu (max 40MHz, interni procesorski takt do 80MHz ) kontinualno, odnosno 3 instrukcije po osnovnom taktu maksimalno, sa maksimalnim performansama od 150 miliona instrukcija/sec. Ugrađeni mehanizam za predviđanje grananja smanjuje negativne efekte upravljačkih hazarda na minimum. Registarski keš (dubine 15 stanja) omogućuje čuvanje stanja registara pri pozivu procedura i restauraciju tog stanja nakon povratka iz pozvane procedure. Sl. 4.23 Intel i960 procesor. IBM je lansirao 1990 god. superskalarni procesor RISC System 6000 (Sl. 4.24), baziran na arhitekturi PowerPC procesora. Aktuelna implementacija ovog superskalarnog procesora (pod internim nazivom NorthStar, procesor se koristi u IBM AS/400 i RS/6000 sistemima) je stepena 4, sa 5 protočnih stepena u protočnom sistemu (sl.4.25), 64kb kešom za instrukcije i podatke na čipu. Procesor ima 5 funkcionalnih jedinica: • • • • Procesor grananja (branch processor), 2 jedinice za cjelobrojna računanja (FXU), Jedinicu za računanja u pokretnom zarezu (FPU). Load/Store jedinicu 95 Sl. 4.24 Organizacija IBM NorthStar procesora. Raspoređivač instrukcija raspoređuje za izvršenje instrukcije na procesor grananja, te na FXU/FPU instrukcije za cjelobrojne operacije/operacije u pokretnom zarezu. Procesor grananja izvodi instrukcije grananja i operacije vezane za instrukcije uslovnog koda. Upravljačka jedinica NorthStar procesora je sa direktnim (hardwired) upravljanjem. Interne magistrale su 32/64/128 bita. Trenutna radna frekvencija je 262 MHz, dok je u planu podizanje radne frekvencije na 675Mhz. Problem upravljačkih hazarda usljed instrukcija grananja je rješavan kombinacijom više tehnika (prekoredna identifikacija grananja i rana priprema adrese grananja, pribavljanje instrukcija sa oba puta grananja, primjena tehnike zakašnjelog grananja, sa poništavanjem 96 izvedenih instrukcija za slučaj grananja), što je omogućilo smanjenje cijene grananja za slučaj nekorektnog predviđanja na maksimalno 1 ciklus. Sl. 4.25 Organizacija protočnog sistema NorthStar procesora Za vrijeme fetch faze, pribavljaju se sekvencijalne instrukcije (iz L1 keš memorije) u bafer sekvencijalnih instrukcija, dok se instrukcije grananja pribavljaju u bafer grananja. 'Gledanjem unaprijed' u baferu raspoređivanja (dispetch buffer) (do 6 instrukcija), obezbjeđuje se ranije sračunavanje ciljne adrese grananja i pribavljanje instrukcija na putu grananja u bafer grananja. Pribavljanje instrukcija je u blokovima od 32 bajta. U fazi raspoređivanja (dispatch) vrši se dekodiranje i raspoređivanje do 4 instrukcije (iz bafera sekvencijalnih instrukcija ili bafera grananja) u svakom ciklusu. Operandi instrukcija se čitaju iz registara, bafera kompletiranja operacija ili magistrala. U ovoj fazi se takođe generiše ciljna adresa grananja. U fazi izvršenja (execute) izvršavaju se aritmetičke, pomjeračke operacije te generiše adresa za keš podataka. Svi rezultati su raspoloživi svim drugim izvršnim jedinicama u slijedećem ciklusu. Ukoliko neki od operanada potrebnih za operaciju u nekom protočnom stepenu nije raspoloživ, onda se rad protočnog stepena zaustavlja. U fazi potvrđivanja operacija (commit) vrši se potvrđivanje rezultata ili njihovo odbacivanje (u slučaju izvršenja instrukcija u nekorektnom putu kod instrukcija grananja, u slučaju prekida ili straničnih grešaka – page faults). Podaci koji se pribavljaju u kešu podataka, mogu se direktno proslijediti u izvršnu jedinicu. U fazi upisa rezultata (writeback) rezultati se upisuju u registre nakon što su svi konflikti razriješeni i rezultati potvrđeni u prethodnom stepenu. 97 Procesori sa velikom dužinom riječi (VLIW – very large instruction word) VLIW arhitekture su proistekle iz dva dobro profilisana i istražena koncepta: horizontalnog mikrokodiranja i superskalarnog procesiranja. Tipični procesori ovog tipa imaju instrukcije dužine nekoliko stotina bita, gdje različita instrukciona polja specifikuju operacije koje traba istovremeno izvršiti u višestrukim funkcionalnim jedinicama procesora (Sl. 4.26). Sl. 4.26 Arhitektura VLIW procesora i tok obrade u protočnim stepenima Zadatak pakovanja operacija u VLIW instrukciju realizuje programski prevodilac. Iako je cilj, kao i kod superskalarnih procesora, da se više operacija izvodi istovremeno u više funkcionalnih jedinica, bitne razlike su u slijedećem: 98 • • • • Planiranje izvršenja instrukcija se vrši u fazi prevođenja, VLIW procesor ne može ostvariti vertikalnu programsku kompatibilnost sa procesorima koji koriste konvencionalni kratki format instrukcija, S obzirom na to da instrukcija sadrži i plan izvršenja operacija, dekodiranje instrukcija je jednostavnije, S obzirom da nije uvijek moguće specifikovati maksimalan broj operacija za istovremeno izvođenje (zbog hazardnih okolnosti), 'gustina' koda kod superskalarnih mašina je veća nego kod VLIW procesora, Iako su prednosti ove arhitekture jednostavnost strukture hardvera i instrukcionog skupa, potencijalno manji CPI parametar nego kod superskalarnih procesora (Multiflow trace računar dozvoljava izvođenje do 7 operacija istovremeno, sa 256 bita po VLIW instrukciji) i dobre performanse kod aplikacija sa predvidljivim programskim ponašanjem (naučne aplikacije npr.), nedostaci su ozbiljni: znatno niže performanse u aplikacijama opšte namjene, i nemogućnost kompatibilnosti sa kodom konvencionalnih računara, što je ovaj koncept ipak izmjestilo sa glavnog toka aktuelnosti u oblasti računarskih arhitektura. 4.6 Intelova arhitektura IA-64 Smatra se da ova arhitektura predstavlja najznačajniji napredak u oblasti mikroprocesorskih arhitektura od uvođenja 32-birnog mikroprocesora Intel 386 1985. god. Nakon 5 godina zajedničkog istraživanja, god. 1999. Intel i Hewlett Packard su objavili detalje nove arhitekture IA-64 ISA (Instruction Set Architecture) sa ciljem da razvojni inžinjeri širom svijeta ubrzaju razvoj nove generacije aplikacija za platforme koje će biti bazirane na IA-64 procesorima. Prvi model ove arhitekture nazvan je Merced i planiran je za realizaciju 2000. godine. Cilj razvojnih napora Intela i HP-a je bio da se razvije arhitektura sa 64-bitnim instrukcionim skupom za radne stanice visokih performansi, serverske stanice i računarske sisteme preduzeća. U ovom domenu postoji niz aktuelnih aplikativnih oblasti koje zahtijevaju izuzetne performanse, sa tendencijom stalnog povećanja zahtijeva za procesne mogućnosti računara: internet aplikacije, elektronska trgovina, data warehousing, video konferencijski sistemi, procesiranje govora itd. Ovaj osnovni cilj se želio ostvariti tako da se prevaziđu limiti u mogućnostima tradicionalnih arhitektura, s jedne strane, ali i da primijenjeni koncept ostavi dovoljno prostora za budući razvoj. Iz tog razloga, IA-64 je jedinstvena kombinacija više novih karakteristika, kao što su: eksplicitni 99 paralelizam, predikacija, spekulativno izvođenje itd. Novi tehnološki koncept je nazvan EPIC: Explicitly Parallel Instruction Computing. IA-64 arhitektura obzbjeđuje takođe potpunu kompatibilnost sa IA-32 (Pentium) arhitekturom, a takođe i sa Pakardovim PA-RISC procesorom. Ova kompatibilnost je bila jedan od osnovnih projektnih zahtijeva. Procesor može raditi u IA-32 ili IA-64 okruženju, što zavisi od operativnog sistema. IA-64 sistemsko okruženje omogućava izvođenje ili IA-32 ili IA-64 instrukcija u bilo kom trenutku: u tu svrhu su realizovane instrukcije koje prevode procesor iz jednog moda u drugi. • • • jmpe (IA-32 instrukcija) prevodi procesor u IA-64 mod, u kojem izvode IA-64 instrukcije, br.ia (IA-64 instrukcija) prevodi procesor u IA-32 mod, u kojem izvode IA-32 instrukcije, rfi (IA-64 instrukcija) 'povratak iz prekida', vraća procesor ili u IA-32 ili u IA-64 mod. Karakteristike instrukcionog skupa IA-64 uključuje arhitekturne karakteristike koje omogućavaju visoke performanse i koje uklanjaju barijere za dalje poboljšanje performansi. IA-arhitektura je bazirana na slijedećim principima: • Eksplicitni paralelizam − − Mehanizam koji omogućuje kooperativne efekte programskog prevodioca i procesora, Veliki broj resursa koji mogu da iskoriste mogućnosti ILP (instruction level parallelism), npr. 128 cjelobrojnih i 128 registara u pokretnom zarezu, 64 predikatnih registara, 8 registara grananja, višestruke funkcionalne jedinice, • Karakteristike koje poboljšavaju paralelizam na instrukcionom nivou − − − − Spekulativno izvođenje (minimizuje uticaj latentnosti memorije), Predikacija (eliminiše grananja), Softverska protočnost (omogućava efikasno iskorištenje programskih petlji), Predviđanje grananja, kojim se smanjuje cijena grananja. • Karakteristike koje poboljšavaju softverske performanse − Specijalne multimedijalne instrukcije, 100 − − − Visoke performanse arhitekture za izvođenje operacija u pokretnom zarezu, Korištenje registarskih prozora promjenljive dužine kod poziva procedura, Mehanizme za nagovještavanje grananja, odnosno pogađanja keša (branch hints, cashe hints) kojima programski prevodilac može specifikovati svoju procjenu lokalnosti memorije (po mjestu i vremenu) kojoj se pristupa. Ovo omogućava povećanje mogućnosti nalaženja informacija u keš memoriji (cache hit) i smanjenje gubitaka zbog promašaja keša (cache miss). ILP - Paralelizam na nivou instrukcija (instruction level paralelism) ILP je mogućnost izvršavanja više instrukcija u isto vrijeme. IA-64 omogućava grupno iniciranje izvršenja nezavisnih instrukcija (3 instrukcije u grupi, više grupa može biti inicirano za izvršenje u jednom ciklusu). Specifikacija grupa vrši se u fazi prevođenja. Programski prevodilac, za razliku od tradicionalnih arhitektura, ima mogućnost da koristi spekulativne informacije, koje nisu garantovano korektne, i to bez žrtvovanja izvođenja korektnih sekvenci. Pored spekulativnog izvođenja, i druge tehnike omogućavaju povećanje ILP (predikacija, predviđanje grananja itd.). Spekulativno izvođenje Postoje dva tipa spekulacije: upravljačka i spekulacija o podacima. U obe varijante kompajler povećava ILP specifikacijom izvršenja neke operacije ranije, sa ciljem eliminisanja kašnjena na kritičnom putu izvođenja instrukcija. Prevodilac specifikuje spekulativno izvršenje neke instrukcije ranije, ako postoji značajna vjerovatnoća da će spekulacija biti ostvarena (da je izvođenje instrukcije u saglasnosti sa sekvencijalnim tokom izvršenja) i ako ranijim izvršenjem instrukcije dolazi do povećanja mogućnosti eksploatacije paralelizma. Npr. ako posmatramo instrukciju: if (a> b) load (ld_addr1, target1) else load (ld_addr2, target2) izvođenje operacije ld_addr1, target1 prije nego što je poznat uslov a > b se može karakterizovati kao spekulacija da će uslov a> b biti istinit. Ranije izvođenje instrukcije ld_addr1, target1 omogućava preklapanje izvođenja te instrukcije (koja traje duže zbog referenciranja memorije) sa drugim instrukcijama, tako da su operacije specifikovane tom instrukcijom izvršene u trenutku testiranja uslova. Nakon spekulativnog izvođenja instrukcije ld_addr1, target1 druge instrukcije mogu takođe koristiti vrijednosti upisane u target1 i ažurirati druge elemente 101 procesorskog stanja. Ažuriranje stanja registara spekulativnom instrukcijom postavlja jedan bit u registrima procesora (NaT – Not a Thing), i svako naredno korištenje tog sadržaja kao operanda u drugim instrukcijama, kojim se ažuriraju vrijednosti drugih registara, takođe postavljaju bit Nat u tim registrima. Prilikom testiranja uslova, ukoliko je spekulacija bila dobra, svi rezultati se prihvataju i potvrđuju, a ukoliko je spekulacija bila pogrešna, onda se ide na proceduru ‘oporavka’, kojom se poništavaju efekti pogrešne spekulacije, sadržaj target1 se restaurira i ponavlja izvršenje instrukcija koje su koristile spekulativnu vrijednost u target1. Spekulacija o podacima Spekulacija o podacima je dobavljanje podataka iz memorije prije operacije smještanja u memoriju koja prethodi tom pribavljanju, ako postoji potencijalna mogućnost da load i store operacije referenciraju isti dio memorije. Npr. Store (st_addr, data) Load (ld_addr, target) Use (target) Ukoliko load i store instrukcije referenciraju različite memorijske lokacije, onda redoslijed izvođenja može biti promijenjen. Međutim, ako u fazi prevođenja ovo ne može da se utvrdi, onda se izvođenje load prije store operacije može smatrati spekulativnim, sa spekulacijom da load i store instrukcije ne referenciraju istu memorijsku lokaciju. Prevodilac, ako je specifikovao spekulativno dobavljanje (load), postavlja instrukciju provjere spekulacije na mjestu originalne instrukcije punjenja, tj. gornji programski kod se mijenja u sekvencu: aload (ld_addr, target) store (st_addr, data) acheck(target, recovery_addr) use(target) Instrukcija acheck utvrđuje da li se upis na memorijsku lokaciju preklapa sa očitavanjem, i ako je to tačno ide se na proceduru oporavka. Predikacija Predikacija je uslovno izvršenje instrukcija. U tradicionalnim arhitekturama, uslovno izvršenje se implementira instrukcijama grananja. IA-64 ahitektura implementira ovu funkciju 102 korištenjem predikatskih instrukcija. Vrijednost predikata se postavlja intrukcijom poređenja u odnosni predikatski registar. Predikovana instrukcija se izvodi ako je vrijednost predikata 1 (1 – bitna vrijednost u predikatskom registru), u suprotnom predikovana instrukcija ima isti efekat kao i nop (no operation) instrukcija. Predikacijom se uklanjaju grananja koja se koriste za uslovno izvršenje, stvaraju se veći blokovi sekvencijalnih instrukcija (bazični blokovi) i eliminišu gubici koji nastaju zbog pogrešne procjene grananja. Npr. instrukcija bez predikata: r1 = r2 + r3 kada je predikovana ima formu if(p5) r1 = r2 + r3. U ovom primjeru p5 je kontrolni predikat, koji odlučuje da li će se ili ne instrukcija izvesti i ažurirati stanje mašine. Predikatima se, kao što je pomenuto, pridjeljuje vrijednost instrukcijama poređenja. Predikatskim izvođenjem se izbjegavaju grananja tako što se kontrolne zavisnosti transformišu u zavisnost po podacima. Npr. ako je originalni kod: if ( a > b ) c = c + 1 else d = d*e + f, Grananje kod uslova se može eliminisati, ako se konvertuje gornji kod u predikatski kod: pT, pF = compare (a > b ) if ( pT ) c = c + 1, if ( pF ) d = d*e + f, pa se originalni kod, koji sadrži grananja, transformiše u kod sa predikatskim instrukcijama, kod kojih postoji zavisnost po podacima. Operacije sa registrima Cjelobrojni registri sadrže 64 bita + 1 NaT bit, registri za operacije u pokretnom zarezu sadrže 82 bita. Registarski model procesora predstavljen je na sl. 4.27. 103 Sl. 4.27 Registarski model procesora IA-64. Mogućnosti cjelobrojnih operacija i operacija u pokretnom zarezu su raznovrsne; ovdje ćemo ilustrovati tehniku korištenja registarskih prozora kod poziva procedura, kojom se izbjegava tradicionalno čuvanje i restauriranje sadržaja registara (register spill and fill) prilikom poziva na sličan način opisan za RISC procesore, ali umjesto fiksnog broja registara koji se pridjeljuju proceduri, vrši se dinamičko pridjeljivanje samo potrebnog broja registara. Registarski skup od 128 registara je podijeljen na dva podskupa: statički, koji sadrži registre 0-31 i magacinski (stacked) podskup. Statički podskup je vidljiv iz svih procedura, dok se magacinski podskup dinamički dodjeljuje procedurama, redom kako se one pozivaju. CFM (current frame marker) pokazuje na par cjelobrojnih indikatora sof (size of frame) i sol (size of locals) koji specifikuju ukupan broj registara magacinskog podskupa koji je pridijeljen proceduri (sof) i broj registara pridijeljen proceduri za njene lokalne potrebe na osnovu zahtjeva iz procedure (specijalnom funkcijom alloc za dodjelu registara). PFM (previous frame marker) sadrži ove informacije u tekućoj proceduri za prethodnu proceduru, iz koje je tekuća procedura pozvana. Prilikom poziva neke procedure B iz procedure A, parametri koje prosljeđuje procedura A (output A) proceduri B su u startu dio registarskog prozora procedure B, pri njenom pozivu. 104 Preimenovanje registara se vrši automatski, tako da numeracija dodijeljenih registara svakoj proceduri počinje sa brojem 32 pa nadalje. Procedura B alocira potreban broj registara alloc funkcijom (za lokalne potrebe i za prosljeđivanje parametara drugim procedurama koje ona poziva) (sl. 4.28). Sl. 4.28 Pridjeljivanje registara pri pozivu (i povratku iz) procedura. U prethodnom tekstu su navedeni samo neki najvažniji elementi novih koncepata primijenjenih u IA-64 arhitekturi. S obzirom na izloženo i na ogroman napor uložen od strane vodećih svjetskih kompanija, čini se da će ova arhitektura označiti novi prodor u organizaciji i mogućnostima procesora i računarskih sistema. Radna frekvencija prvog procesora iz ove serije (Merced) je različita za različite procesorske komponente: od 3 GHz u funkcionalnim i registarskim jedinicama, pa do 100MHz za sistemsku magistralu. 105 5. Hijerarhijska organizacija memorije Jedinice za pohranjivanje podataka su često hijerarhijski organizovane u računarskom sistemu, kako je to predstavljeno na Sl. 5.1. Memorijsku tehnologiju i organizaciju na svakom nivou karakteriše 5 parametara: − − − − − Vrijeme pristupa ti (access time), od CPU do i-tog memorijskog nivoa, Veličina (kapacitet) memorije si na nivou i (u bajtima), Cijena po bajtu ci na memorijskom nivou i, Propusni opseg bi (transfer bandwidth) između nivoa i i i+1, Jedinica transfera xi (obično izražena u bajtima) između nivoa i i i+1. Sl. 5.1 Organizacija memorije sa 4 hijerarhijska nivoa. Memorijske jedinice na nižim nivoima su brže za pristup, manje po kapacitetu i skuplje po bajtu. Tj. imamo: 106 ti-1 < ti , si-1 < si , ci-1 > ci , bi-1 > bi , i xi-1 < xi (i = 1, …, 4 ). Registri i keš memorije su dijelovi procesorskog kompleksa, sa realizacijom ili na procesorskom čipu, ili na procesorskoj ploči. Registri su specijalni memorisjki elementi: plan korištenja registara često realizuje programski prevodilac, transfer podataka između registara je pod kontrolom procesora (odnosno upravljačke jedinice) i izvršava se brzinom kojom radi procesor (obično u jednom taktnom intervalu). Zbog toga se često registri i ne smatraju memorijskim nivoom, pominjanje registara je prije svega iz razloga komparacije sa drugim nivoima. Rad keša kontroliše jedinica za kontrolu pristupa memoriji (MMU – memory managament unit). Rad keša ne zahtijeva nikakvo programiranje, on je za programera transparentan. Keš takođe može biti realizovan na jednom ili više nivoa. Pristup glavnoj (primarnoj) memoriji se odvija pod kontrolom MMU i operativnog sistema. Glavna memorija takođe može da se organizuje u više modula i u više podnivoa. Disk jedinice i jedinice magnetne trake rade pod kontrolom operativnog sistema, sa ograničenom interakcijom operatera. Disk memorija je najviši memorijski nivo sa on-line pristupom. Jedinice magnetne trake predstavljaju memorijski nivo sa off-line pristupom i koriste se uglavnom u svrhu arhiviranja (programa i podataka). 5.1 Inkluzija, koherencija i lokalnost Informacije smještene u hijerarhijski organizovanom memorisjkom sistemu (M1, M2, …, Mn) imaju tri karakteristične osobine: inkluziju (uključenost), koherentnost i lokalnost, kao što je to ilustrovano na Sl. 5.2. Skup svih adresibilnih riječi u Mn čini virtuelni adresni prostor računara. Osobina inkluzije se iskazuje sa: M1 ⊂ M2 ⊂ M3 ⊂ … ⊂ Mn. Inkluzija skupova implicira da su sve informacije originalno pohranjene u spoljnjem nivou Mn . U toku obrade, dio informacija se kopira u Mn-1. Analogno, podskup Mn-1 se kopira u Mn-2 itd. Tj. ako se informaciona riječ nalazi u Mi, onda se kopije te informacije takođe nalaze u svim višim nivoima Mi+1, Mi+2, … , Mn, ali informacija koja se nalazi u Mi+1 ne mora postojati u Mi u posmatranom trenutku. Nepostojanje riječi u Mi (word miss) implicira nepostojanje te riječi u svim nižim nivoima (Mi-1, Mi-2, … , M1). Najviši nivo je memorija za arhiviranje (backup storage) gdje se mogu naći sve informacije. 107 Sl. 5.2 Inkluzija i transfer podataka između susjednih nivoa u memorijskoj hijerarhiji. Transfer informacija između CPU i keš memorije se izražava u riječima (4 ili 8 bajtova, zavisno od dužine riječi procesora). Keš ( M1 ) je podijeljena u keš blokove. Tipična veličina keš bloka je 32 bajta ( 8 riječi). Transfer između keš memorije i glavne memorije se izvodi u ovim blokovima. Glavna memorija je izdijeljena na stranice, veličine najčešće 4Kb. Svaka stranica sadrži 128 keš blokova za primjer sa Sl. 5.2. Stranice su jedinične količine informacija pri transferu između 108 glavne memorije i disk jedinica. One se grupišu u segmente koji mogu biti različite veličine; razmjena informacija između disk jedinica i jedinica magnetnih traka se zasniva na transferu segmenata. Svojstvo koherentnosti zahtijeva da informacija na nekom nivou, ima konzistentne (identične) kopije na slijedećim - višim nivoima. Održavanje koherentnosti se može realizovati slijedećim strategijama: − − Upis odmah ( write through - WT), Odgođeni upis ( write back - WB). WT strategija ažurira odgovarajuću kopiju u Mi+1, čim je došlo do ažuriranja neke riječi u Mi. WB metod odgađa ažuriranje informacije u Mi+1, sve do momenta dok se odnosna informacija ne uklanja iz Mi. Lokalnost referenciranja je svojstvo programa da memorijske adrese, generisane u toku izvršavanja programa, imaju tendenciju grupisanja posmatrano sa aspekta vremena i prostora. U najvećem broju programa, 90% vremena programskog izvršenja proističe izvršenjem 10% programskog koda (90-10 pravilo, Hennesy/Patterson). Kao posljedicu imamo svojstvo lokalnosti: ovo svojstvo ima tri dimenzije: temporalnu, prostornu i sekvencijalnu. Temporalna lokalnost je svojstvo da će memorijske reference, generisane u najbližoj prošlosti, vjerovatno ponovo biti generisane u skoroj budućnosti (ovo svojstvo je posljedica iterativnih operacija u programu, programskih petlji, npr.). Prostorna lokalnost je svojstvo da se generišu memorijske reference koje su bliske jedna drugoj (npr kod programskih rutina, makroa itd.). Sekvencijalna lokalnost se odnosi na činjenicu da se često generiše sekvencijalni niz adresa (npr. tokom sekvencijalnog izvođenja niza instrukcija, sve dok se ne naiđe na instrukciju grananja, pristup nizovima podataka itd.). Primjer referenciranja memorije u vremenu za tri procesa ( a, b, c) predstavljen je na Sl. 5.3. Skup memorijskih adresa koji je generisan u vremenskom intervalu ( t, t + ∆ t ), naziva se radni skup (working set - Denning, 1968). Za vrijeme izvršenja programa, radni skup se mijenja postepeno, odnosno posjeduje određeni stepen kontinualnosti. To znači da se u toku izvođenja informacije najčešće 'pogađaju' na nižim hijerarhijskim nivoima. 109 Sl. 5.3 Tipični profil referenciranja memorije pri izvođenju procesa 5.2 Planiranje memorijske organizacije Performanse memorijskog sistema zavise od efektivnog vremena pristupa (effective access time) Teff bilo kom nivou u memorijskoj hijerarhiji, i od frekvencije pristupa tim nivoima. Stopa pogađanja (hit ratio) hi je vjerovatnoća da je zahtijevana informacija raspoloživa u Mi. Stopa promašaja (miss ratio) se definiše kao 1- hi. Stopa pogađanja na sukcesivnim nivoima je slučajna varijabla sa područjem vrijednosti između 0 i 1, i funkcija je kapaciteta memorije, politike upravljanja memorijom i ponašanja programa. Frekvencija pristupa (access frequency) nivou Mi se definiše kao: fi = (1- h1) (1- h2) … (1- hi-1) hi. Veličina fi je de facto vjerovatnoća uspješnog pristupanja nivou Mi, čemu je prethodilo i-1 promašaja na nižim nivoima. Primijetimo da je: 110 ∑ n i =1 f i = 1 , i f1 = h 1 . S obzirom na svojstvo lokalnosti, frekvencije pristupa opadaju veoma brzo od nižih ka višim nivoima, tj. f1 >> f2 >> f3 … >> fn, odnosno unutrašnjim memorijskim nivoima se pristupa mnogo češće nego vanjskim. Efektivno vrijeme pristupa se definiše kao: Teff = ∑f i =1 n i • i t = h1 t1 + (1-h1) h2 t2 + (1- h1) (1- h2) h3 t3 + … + (1- h1) (1- h2) … (1- hn-1) tn, gdje su t1, t2, …, tn vremenski gubici (cijena u vremenskim jedinicama) koja se mora platiti za pristupanje slijedećem višem nivou u memorijskoj hijerarhiji. Vrijeme pristupa kešu (za slučaj da informacija nije raspoloživa u registrima) je t1, cijena (vrijeme pristupa) zbog nepostojanja informacija u kešu prvog nivoa (promašaj bloka – block miss) je t2, cijena zbog nepostojanja informacija u glavnoj memoriji (promašaj stranice – page fault) je t3 (ako je glavna memorija slijedeći nivo u memorijskoj hijerarhiji) itd. t1 < t2 < …< tn. Stone (1990) je pokazao da je cijena promašaja keša 2-4 puta skuplja od cijene pogađanja keša, dok je cijena promašaja stranice u glavnoj memoriji (page fault) 1000 – 10 000 puta veća od cijene pogađanja. Optimizacija hijerarhijske organizacije memorije Ukupna cijena hijerarhijskog memorijskog sistema se procjenjuje kao Ctotal = ∑c i =1 n i • si S obzirom na to da je c1 > c2 > c3 … > cn hijerarhijski memorijski sistem se realizuje tako da je s1 < s2 < …< sn. Optimalno projektovana hijerarhijska organizacija memorije treba biti takva da je Teff blisko vremenu t1 (vremenu pristupa nivou M1), i ukupna cijena bliska cijeni cn nivoa Mn. Problem projektovanja hijerarhijskog memorijskog sistema se svodi na problem minimizacije n Teff = ∑f i =1 i • i t , 111 uz slijedeća ograničenja: si > 0, ti > 0 , za i = 1, 2, …, n, Ctotal = ∑c i =1 n i • s i < C0 . Vrijednosti karakterističnih parametara za memorijski sistem tipičnog main-frame računara dati su u tabeli 5.1 (podaci se odnose na 1993. god.). Tabela 5.1 Karakteristične vrijednosti parametara memorijskog sistema 5.3 Koncept virtuelne memorije Glavna memorija se često naziva i fizička memorija. U ovoj memoriji se nalaze programi u toku izvršenja kao i podaci i rezultati koje ovi programi koriste/produkuju. S obzirom na to da je veličina glavne memorije ograničena, svi programi ne mogu biti smješteni istovremeno u glavnoj memoriji. Koncept virtuelne memorije omogućuje virtuelno proširenje glavne memorije sekundarnom memorijom, čime se postiže da veći broj programa može istovremeno koristiti fizičku memoriju. Samo aktivni programi, ili njihovi dijelovi, se nalaze u glavnoj memoriji u jednom trenutku vremena. Programi (ili njihovi dijelovi) se učitavaju sa sekundarne memorije (disk jedinice) u memoriju i vraćaju nazad na disk pod kontrolom operativnog sistema. 112 Skup adresa, preko kojih se može pristupiti raspoloživim memorijskim lokacijama glavne memorije čini fizički adresni prostor. Adrese koje generiše programski prevodilac prilikom prevođenja izvornog programa, odnosno instrukcije prilikom izvođenja su virtuelne adrese. Virtuelni adresni prostor je po pravilu veći od fizičkog adresnog prostora. Prilikom izvođenja programa, potrebno je obezbijediti prevođenje virtuelnih adresa sadržanih u programu, u odnosne fizičke adrese, odnosno realizovati mapiranje virtuelnog na fizički adresni prostor. Neka je V skup virtuelnih adresa, generisanih programom koji se izvodi, i neka je M skup fizičkih adresa pridjeljenih programu za izvođenje. Virtuelni memorijski sistem zahtijeva automatski mehanizam za implementaciju mapiranja: ft : V → M ∪ {0} Mapiranje je dinamička funkcija koja varira u vremenu, pridjeljivanje fizičke memorije programu koji se izvodi vrši se od strane operativnog sistema. Za bilo koju virtuelnu adresu v ∈ V, imamo: m, ako m ∋ M sadrzi podatak referenciran virtuelnom adresom v ft (v) = 0, ako se podatak referenciran virtuelnom adresom v ne nalazi u M Dakle, funkcija ft (v) prevodi virtuelnu adresu v u jedinstvenu fizičku adresu m, ako postoji pogodak (memory hit) u M. Kada postoji promašaj, funkcija vraća vrijednost 0, čime se indicira da se referencirana informacija ne nalazi u memoriji. Jasno je da efikasnost mapiranja ima izražen uticaj na performanse virtuelne memorije. Koncept virtuelne memorije je znatno teže implementirati u multiprocesorskim sistemima gdje se javljaju drugi složeni problemi kao što su: održavanje koherentnosti i konzistentnosti, problem zaštite pristupa i drugi. U tekstu koji slijedi, ukratko su izložena dva virtuelna memorijska modela multiprocesorskih sistema(Sl. 5.4.). Privatna virtuelna memorija U ovom modelu, svakom procesoru se pridjeljuje privatni virtuelni adresni prostor. Svaki privatni virtuelni prostor je izdijeljen na stranice. Stranice različitih virtuelnih prostora se mapiraju u stranice iste fizičke memorije, koja je zajednička za sve procesore. Ovaj koncept omogućava korištenje relativno malih procesorskih adresnih prostora (32-bita), zaključavanje/zaštitu svake stranice koja se zasniva na bazi procesa i korištenje privatnih memorijskih mapa, koje ne zahtijevaju eksluzivan pristup. Problem predstavlja referenciranje 113 istih fizičkih stranica iz različitih virtuelnih stranica istog ili različitih virtuelnih prostora (problem sinonima). Problem koji se morao posebno rješavati je taj da iste virtuelne adrese u različitim virtuelnim adresnim prostorima, mogu da referenciraju različite fizičke stranice u glavnoj memoriji. Sl. 5.4 Modeli virtuelne memorije za multiprocesorske sisteme. Dijeljena virtuelna memorija U ovom modelu, virtuelni adresni prostori svih procesora se kombinuju u jedinstveni dijeljeni virtuelni adresni model. Svakom procesoru se dodijeljuje dio jedinstvenog adresnog prostora. Virtuelni adresni prostori različitih procesora mogu da se preklapaju. Prednost ovog modela je to što su sve adrese jedninstvene. Procesori mogu da generišu adrese veće od 32 bita a sinonimi nisu dozvoljeni. 114 Pristup tabeli straničenja mora biti omogućen od strane više procesora; u cilju zaštićenog pristupa tabeli straničenja koristi se zaključavanje. Obično se iznad koncepta straničenja realizuje segmentacija što omogućava da svaki proces ima svoj adresni prostor. 5.3.1 Straničenje, TLB, Segmentacija Kod tehnike straničenja, u cilju preslikavanja virtuelnog u fizički adresni prostor i virtuelni i fizički adresni prostor se dijele na stranice iste dužine. Različite šeme translacije virtuelnih u fizičke adrese su predstavljene na Sl. 5.5. Sl. 5.5 Mehanizmi translacije virtuelnih u fizičke adrese. 115 Šeme sa slike 5.5a, koriste translacione mape koje se mogu implementirati na različite načine. Ove mape mogu biti smještene u keš memoriju, specijalnu asocijativnu memoriju ili u glavnu memoriju. Svaka mapa sadrži određeni broj ulaza, a svakim ulazom (Sl. 5.6) se specifikuje translacija. Pristup odgovarajućem ulazu u tabeli se vrši na bazi funkcije mapiranja, koja se primjenjuje na virtuelnu adresu. Mapiranje se može implementirati hash ili kongruentnom funkcijom. Sl. 5.6 Struktura ulaza u tabelu straničenja Varijante translacionih mapa su keš straničenja (TLB – table lookaside buffer) i tabela straničenja (PT – page table). TLB je brza memorija koja sadrži najčešće referencirane ulaze tabele straničenja. Najpovoljnija varijanta je ako se translacija virtuelne u fizičku adresu realizuje preko TLB ulaza. Ukoliko TLB ne sadrži ulaz koji specifikuje translaciju, onda se traženje nastavlja u tabeli straničenja. Hadrverska organizacija sistema straničenja koja koristi TLB data je na Sl. 5.7. Sl. 5.7 Straničenje sa korišćenjem TLB (St. 7.146) 116 Tabele straničenja (PT) sadrže suštinski iste ulaze kao i TLB (koji specifikuju asocijaciju između virtuelnih i fizičkih stranica – okvira). Ove tabele se kreiraju u glavnoj memoriji nakon kreiranja korisničkih procesa (za svaki proces se kreira posebna PT). S obzirom da broj aplikativnih procesa može biti veliki, broj PT u memoriji može takođe biti veliki. I TLB i PT se moraju dinamički ažurirati kako bi odražavali aktuelno stanje. Mape translacije predstavljaju tekući snimak stanja memorijskog referenciranja. Ukoliko se tražena stranica ne nalazi u memoriji (ne postoji par (virtuelna stranica, fizička stranica) u PT), onda se generiše stranična greška (page fault). U tom slučaju se tekući proces suspenduje, aktivira se novi proces (izvršava se context switch), a tražena stranica se dobavlja sa diska/jedinice magnetne trake, u memoriju. Nakon tog transfera suspendovani proces se stavlja u listu spremnih procesa, i nakon njegovog aktiviranja, nastavlja se izvršenje od one instrukcije koja je generisala straničnu grešku. PT se mogu implementirati i u više nivoa. Ovim se de-facto formira stablo za prevođenje adresa, sa mogućnošću proširenja memorijskog prostora koji se mapira i implementacijom sofistifikovane zaštite pristupa stranicama. Primjer prevođenja virtuelnih u fizičke adrese kod tehnike straničenja, dat je na Sl. 5.8. U navedenom primjeru, u posebnom registru se čuva tabela straničenja procesa. Broj virtuelne stranice se koristi kao indeks u tebeli straničenja, iz koje se čita odgovarajući broj fizičke stranice (broj okvira). Ovaj broj se kombinuje sa pomjerajem virtuelne adrese čime se dobija željena realna (fizička) adresa. Prethodno opisana tehnika (direktnog) straničenja je pogodna ako virtulni adresni prostor nije izuzetno veliki (do 32 bita). U slučaju velikog virtuelnog adresnog prostora (52 bitne virtuelne adrese kod IBM RS/6000, npr) PT bi postale izuzetno velike. U takvim slučajevima koriste se invertovane tabele straničenja (IPT). Kod ove tehnike (Sl. 5.5c, Sl. 5.9) invertovana tabela straničenja (IPT) sadrži jedan ulaz za svaku fizičku stranicu (frame). Prema tome, broj ulaza je određen brojem fizičkih umjesto virtuelnih stranica. 117 Sl. 5.8 Tehnika mapiranja virtuelnog u fizički adresni prostor straničenjem. Polje veza formira lanac IPT ulaza koji imaju istu hash vrijednost. Npr, hash funkcija može mapirati broj virtuelne stranice → indeks ulaza u IPT na slijedeći način: indeks ulaza u IPT = broj virtuelne stranice mod n gdje je n broj fizičkih stranica (frame-ova). Sadržaj vrijednosti virtuelne adrese stranica# (vrijednost ključa) se upoređuje sa vrijednošću str.# u ulazu u tabeli straničenja koji odgovara vrijednosti hash funkcije za datu virtuelnu stranicu. Ako su vrijednosti iste, onda se odgovarajući broj fizičke stranice dobija u polju ulaz#. Ako se vrijednosti ključa ne poklapaju, onda se preko polja ‘veza’ ide na slijedeći ulaz sa istom hash vrijednošću i postupak ponavlja dok se ne pronađe fizička stranica, ili utvrdi da tekućoj virtuelnoj adresi nije pridružena nijedna (fizička) stranica u glavnoj memoriji (frame). U posljednjem slučaju generiše se stranična greška. 118 Sl. 5.9 Mapiranje invertovanom tabelom straničenja Segmentiranje. U memorijskom sistemu sa segmentiranjem, korisnički programi su strukturirani u logičke segmente (Sl. 5.10) koji mogu biti različite dužine. Dakle, segmentacija omogućava da se programski kod organizuje na bazi korisničke predstave programa. Virtuelna adresa specifikuje broj segmenta i pomjeraj u okviru segmenta. Sl. 5.10 Organizacija korisničke aplikaciju po segmentima 119 Broj segmenta se koristi kao indeks u segmentnoj tabeli. Ulaz segmentne tabele sadrži pored specifikacije bazne fizičke adrese i specifikaciju maksimalne dužine segmenta. Mehanizam generisanja fizičke adrese predstavljen je na Sl. 5.11. Sl. 5.11 Generisanje fizičke adrese iz virtuelne u memorijskom sistemu sa segmentacijom. Tehnike segmentacije i straničenja moguće je kombinovati (straničenje segmenata). Kod ove organizacije memorije, virtuelna adresa se sastoji iz tri dijela: broj segmenta, broj stranice (u okviru segmenta), pomjeraj. Generisanje fizičke iz virtuelne adrese ovom tehnikom dato je na Sl. 5.12. Sl. 5.12 Prevođenje adresa segmentacijom i straničenjem 120 5.3.2 Politika zamjene stranica Ukoliko se stranica ne nalazi u memoriji, onda je potrebno učitati traženu stranicu sa sekundarne memorije u glavnu memoriju. Problem se pojavljuje kod odlučivanja u koju fizičku stranicu (frame) treba učitati nove podatke, odnosno koju postojeću stranicu treba zamijeniti. Postoji više politika zamjene stranica: 1) 2) LRU (Least recently used), zamjenjuje onu fizičku stranicu u glavnoj memoriji koja najduže nije referencirana (posmatrano do tekućeg trenutka), Optimalni (OPT), zamjenjuje onu stranu koja neće biti referencirana najduži period, posmatrano od tekućeg trenutka (ova politika se realno ne može implementirati, jer se buduća referenciranja ne mogu uvijek tačno predvidjeti), FIFO (first in first out), zamjenjuje onu stranu koja je najduže u memoriji, LFU (least frequently used), zamjenjuje onu stranu koja je najrjeđe referencirana u prošlosti, Zamjena stranice na bazi slučajnog izbora itd. 3) 4) 5) LRU tehnika je najčešće korištena i najčešće daje najbolje rezultate (tj. najmanji broj transfera stranica između diska i glavne memorije). 121 6 Vi{eprocesorske arhitekture 6.1 Ra~unarski sistemi upravqani kontrolnim tokom Najve}i broj ra~unarskih arhitektura koristi tradicionalni (von Neumann-ov) sekvencijalni tok izvo|ewa ra~unawa u procesorskim elementima, odre|en kontrolnim tokom. Niz instrukcija, smje{tenih u memoriji, izvodi se sekvencijalno jedna za drugom. Eksplicitni transfer kontrole na drugi sekvencijalni niz instrukcija ostvaruje se programski, odgovaraju}om naredbom. Po Flynn-ovoj klasifikaciji, vi{eprocesorski sistemi se dijele na: • • • SIMD MISD MIMD- ma{ine sa jednim tokom instrukcija i vi{estrukim tokom podataka, ma{ine sa vi{estrukim tokom instrukcija i jednim tokom podataka, ma{ine sa vi{estrukim tokom i instrukcija i podataka. 122 6.1.1 SIMD ra~unarski sistemi (Single instruction-multiple data) Kod arhitektura ovog tipa postoji jedan sekvencijalni tok instrukcija i jedna kontrolna jedinica koja upravqa istovremenim izvr{ewem svake instrukcije na vi{e procesnih elemenata. Svi omogu}eni procesni elementi izvode (istu) instrukciju nad razli~itim podacima, ~ime se realizuje paralelna obrada na odre|enom skupu podataka. Jednim instrukcionim tokom se izbjegava ponavqawe procesa dobavqawa instrukcije za svaku procesnu jedinicu. S obzirom na to da svi procesori rade sinhronizovano, na osnovu upravqa~kih signala iz kontrolne jedinice, ovakve arhitekture su pogodne za eksploataciju sitnozrnastog paralelizma. Osnovne varijante ovih arhitektura predstavqene su na Sl. 6.1. Procesorska poqa (array processors) Kod ra~unara sa ovim tipom arhitekture, procesor se sastoji iz skupa procesnih elemenata (PE) povezanih sinhronom mre`om. Svi procesni elementi rade pod kontrolom jedne kontrolne jedinice (CU). Program koji se izvodi mo`e da se nalazi ili u memoriji kontrolne jedinice, ili u procesnim elementima. Skalarne ili kontrolne instrukcije izvodi direktno CU. CU dekodira vektorske instrukcije, odre|uje na kojim PE se teku}a instrukcija izvodi i inicira sinhrono izvr{ewe na svim (omogu}enim) PE. Podaci nad kojima PE izvode zahtijevanu operaciju se ili ve} nalaze u memorijskim modulima dostupnim PE, ili se prethodno pune u memoriju (od strane CU (emisijom) preko kontrolne magistrale, ili od strane eksterne jedinice preko sistemske magistrale podataka). Na taj na~in, vi{e procesnih elemenata izvr{ava paralelnu obradu nad odre|enim skupom podataka. Obra|ene podatke PE-i smje{taju u memoriju. Memorija u kojoj se nalaze podaci mo`e biti ili lokalna memorija (LM) procesnih elemenata ili globalni memorijski moduli (M), kojima mogu pristupiti razli~iti PE. U oba slu~aja realizuje se mre`a za povezivawe, kojom se omogu}ava izmjena podataka izme|u PE, odnosno pristup zajedni~kim podacima (Sl 6.1). Smje{tawe podataka po memorijskim elementima mora biti takvo da omogu}i da se elementima nizova podataka, koji treba da se procesiraju paralelno, pristupi istovremeno i bez konflikta. Za ure|ewe podataka na opisani na~in ~esto je potrebno mijewati raspored podataka po procesnim elementima, {to se realizuje 123 mre`om za povezivawe i odgovaraju}im funkcijama usmjeravawa i prenosa (rutirawa). I/O Linije podataka Podaci i instrukcije memorija CU Kontrolne linije PE0 LM0 PE1 LM1 PEN-1 LMN-1 Kontrola Spre`na mre`a a) PE-PE model. b) PE - memorijski model. Sl. 6.1 Varijante arhitektura SIMD ra~unara. 124 Procesor sa poqem PE-a se normalno povezuje na ra~unar op{te namjene (hostdoma}in) preko kontrolne jedinice. Ra~unar op{te namjene izvr{ava standardne sistemske funkcije i komunikaciju sa spoqnim svijetom, tako da se procesorska poqa mogu smatrati pridodatom procesnom jedinicom za izvr{avawe specifi~nih aplikacija ili dijelova aplikacija kao {to je linearno programirawe, matri~na algebra, prepoznavawe oblika itd. Ipak, programirawe ovakvih procesora nije jednostavno. Ono se realizuje ili ekstenzijom postoje}ih jezika ili posebnom bibliotekom funkcija koje se pozivaju iz dijela aplikacije koji se izvodi na ra~unaru doma}inu. Izvo|ewe skalarnih operacija na ovim ma{inama je relativno sporo. Vr{ne performanse se ostvaruju rijetko i u posebno pogodnim aplikacijama. Ovaj tip organizacije je karakterisao niz ra~unara, od prvog superra~unara Illiac-a IV pa do aktuelnih Thinking Machine CM-2 i MasPar MP-1. Primjer sra~unavawa parcijalnih suma niza elemenata Sk = k ∑A i =0 i , gdje je A niz elemenata {Ai , i = 1, …n }, dat je na Sl. 6.2 Za ilustraciju, predstavi}emo organizaciju sada ve} istorijskog ra~unara Illiac-a IV (Sl. 6.3) i dati primjere izvo|ewa operacija na ovom ra~unaru. Illiac-a IV je ra~unar sa 64 procesora povezanih mre`om u formi re{etke. (karakteristike ove spre`ne mre`e bi}e izlo`ene kasnije). Kontrolna jedinica dekodira instrukcije koje se dobavqaju iz procesnih elemenata pod kontrolom operativnog sistema, i vr{i distribuciju instrukcija za izvr{ewe ka potrebnim procesnim elementima. Kontrolna jedinica tako|e izvodi proste skalarne operacije. Prosqe|ivawe podataka izme|u procesnih elemenata se vr{i instrukcijama rutirawa. Procesni element (Sl. 6.4) ima 4 64-bitna registra (A – akumulator, B – operand registar, R – registar za rutirawe, S – op{ti registar za prihvat podataka), 16 – bitni indeks registar X i 8 – bitni statusni/mod registar D. Svaki procesni element ima vezu / mo`e rutirati podatke, ka 4 druga procesna elementa. 125 Sl. 6.2 Sra~unavawe parcijalnih suma niza elemenata na mre`nom procesoru. 126 Sl. 6.3 Organizacija ra~unara Illiac-a IV. 127 Si Xi Di Sl. 6.4 Struktura procesnog elementa Illiac-a IV. Primjer izvo|ewa proste vektorske operacije na ovom ra~unaru dat je na Sl. 6.5. i Sl. 6.6. 128 Sl. 6.5 Sabirawe dva vektora: du`ina vektora jednaka je broju procesnih elemenata. 129 Sl. 6.6 Sabirawe dva vektora: du`ina vektora je ve}a od broja procesnih elemenata. 130 Asocijativni procesori Za razliku od klasi~nih ra~unara, gdje se referencirawe nekog podatka u memoriji ostvaruje na osnovu adrese, asocijativni procesori referenciraju podatke u memoriji na osnovu wihovog sadr`aja. Na taj na~in je mogu}e referencirawe vi{e podataka istovremeno. Memorija koja ima navedene mogu}nosti, naziva se asocijativna memorija. Tipi~na organizacija asocijativne memorije data je na Sl. 6.7. Kqu~ za referencirawe se specifikuje preko registra za komparaciju (CR) i registra za maskirawe (MR). Upravqa~ka logika inicira komparaciju sadr`aja svih nemaskiranih dijelova CR sa svim lokacijama asocijativne memorije. Komparaciju izvodi kontrolna logika pridru`ena svakoj memorijskoj lokaciji, i za one lokacije koje zadovoqavaju tra`eni uslov, postavqa se logi~ka jedinica u korespondentni bit registra za indikaciju. Komparacija se mo`e izvoditi serijski, bit po bit, ili paralelno (svi biti se istovremeno procesiraju). Registar za komparaciju Registar maskirawa Indikator Privremeni registar Sl. 6.7 Organizacija asocijativne memorije. 131 Vi{e sukcesivnih selekcija se mo`e sa~uvati u podskupu privremenih registara, a rezultantna selekcija se mo`e dobiti logi~kim operacijama nad elementima ovog podskupa. Asocijativni procesori se povezuju na ra~unar doma}in kao specijalizovani procesori za odre|ene aplikacije. Modul za povezivawe sa okolinom (obi~no se radi po korisni~kim zahtjevima) obezbje|uje {irok spektar mogu}nosti: direktan pristup memoriji, paralelni U/I, spregu sa drugim specijalizovanim procesorima, kori{tewe senzorskih ulaza itd. Sve ovo omogu}ava postizawe visokih performansi u aplikacijama kao {to su matri~ne operacije, upravqa~ki sistemi u stvarnom vremenu, sistemi za upravqawe i manipulaciju podacima, gdje se sekvencijalno procesirawe realizuje na konvencionalnom ra~unaru-doma}inu, a paralelne operacije (prije svega selekcije na skupu podataka) na pridodatim asocijativnim procesorima. Zbog skupe realizacije komparatorske logike, asocijativne memorije su malog kapaciteta i skupe, {to limitira wihovu upotrebu za specijalizovane namjene. Zna~ajnu primjenu asocijativnih memorija imamo u realizaciji ke{ memorija, gdje se utvr|ivawe raspolo`ivosti podatka/instrukcije u ke{u utvr|uje na bazi privjeska (tag) generisanog na bazi adrese. Primjeri kori{tewa asocijativne ke{ memorije su IBM 3033, Motorola 88110, Intel Pentium procesori itd. Primjer paralelne selekcije elemenata koji zadovoqavaju zahtijevani uslov dat je na Sl. 6.8. 132 Sl. 6.8 Selekcija elemenata po uslovu tra`ewa u asocijativnoj memoriji. 133 Vektorski procesori Mnogi, ra~unski zahtjevni algoritmi, sadr`e veliki broj operacija koje rade sa ure|enim skupovima (nizovima) elemenata-vektorima. Ove operacije se mogu klasifikovati u slijede}e osnovne grupe: f1: V → V, f2: V → S, f3: V x V → V, f4: V x S → V, gdje su V i S vektorski odnosno skalarni operand, respektivno. Neke varijante vektorskih instrukcija su predstavqene na Sl. 6.10. Zajedni~ka im je karakteristika da se ista operacija ponavqa na svim elementima ili parovima elemenata vektora. Izvo|ewe ovih operacija se mo`e optimizovati ako se izbjegne ponavqawe dobavqawa i dekodirawa instrukcija za svaki element vektora, odnosno ako se cijeli proces inicira jednom (vektorskom) instrukcijom. Vektorska instrukcija sadr`i operacioni kod, adrese operanada, du`inu vektora i adresni inkrement. Po{to se kod skalarnih ma{ina ove operacije implementiraju programskom petqom, izbjegava se tako|e gubitak uslijed programske kontrole zavr{etka petqe. Generalna organizacija vektorskog procesora prikazana je na Sl. 6.9. Skalarni procesor Ss1 Jedinica za procesirawe instrukcija Skalarni registri Ss2 S sn Proto~ni stepeni Glavna memorija Kontroler vektorskih instrukcija S v1 Sv2 Kontroler vektorskog pristupa Vektorski registri Svn Vektorski procesor Sl. 6.9 Organizacija vektorskog procesora. Svaki vektorski registar mo`e da sadr`i jedan vektor sa N elemenata. Jedinica za procesirawe instrukcija dobavqa i dekodira instrukcije iz glavne memorije i prosqe|uje skalarne instrukcije skalarnom procesoru, a vektorske kontroleru vektorskih instrukcija. Skalarni i vektorski procesor se (svaki) sastoji iz vi{e paralelnih proto~nih funkcionalnih sistema inplementiranih za efikasnu proto~nu obradu skalarnih odnosno vektorskih instrukcija. 134 Sl. 6.10 Neke varijante vektorskih instrukcija. 135 Proto~ni procesori mogu biti jednofunkcionalni ili vi{efunkcionalni. Vektorska instrukcija se inicira i izvodi pod kontrolom vektorskog instrukcionog kontrolera, koji vr{i raspore|ivawe izvr{ewa vektorske operacije na jedan ili vi{e proto~nih funkcionalnih sistema vektorskog procesora, inicira pribavqawe operanada pod kontrolom vektorskog kontrolera pristupa, te inicira po~etak izvr{ewa vektorske operacije u vektorskom procesoru. Vrijeme pribavqawa operanada i postavqawa kontrolnih registara (pripremno vrijeme vektorske operacije) je obi~no znatno ve}e od vremena procesirawa vektora tp ~ t1 * N, gdje je t1 vrijeme izme|u sukcesivnih operanada, a N du`ina vektora. Nakon inicirawa obrade, sukcesivni operandi ulaze u proto~ni funkcionalni sistem sa periodom t1 i obra|uju se redom u proto~nim stepenima. Izlaz iz zadweg proto~nog stepena se smje{ta ili u memoriju ili u vektorski registar. Kada se neki proto~ni funkcionalni sistem i odgovaraju}i vektorski registri dodijele za izvo|ewe neke vektorske operacije, ne mogu se dodijeliti za izvo|ewe slijede}e operacije sve dok se teku}a operacija ne zavr{i. Da bi se mogu}nosti vektorskog procesora iskoristile na adekvatan na~in, potrebno je generisati optimizovan izvr{ni kod, sa ciqem maksimalnog kori{tewa proto~nih resursa i minimizacijom pripremnih vremena vektorskih operacija, za {to su razvijeni vektoriziraju}i prevodioci. Grafi~ki prikaz izvo|ewa operacija u vektorskom i osnovnom skalarnom procesoru dat je na Sl. 6.11. Prva generacija vektorskih superra~unara je razvijena krajem 60-tih godina i reprezentuju je STAR-100 TI-ASC i CDC 6600/7600. Drugu generaciju ovih ma{ina predstavqaju CRAY-1, Cyber-200, Fujitsu VP-200, svi procesnih mo}i ispod 500 Mfloaps-a. Posqedwe generacije ovih ma{ina reprezentuju Cray Y-MP te Fujitsu 2000, NEC SX-X, Hitachi S800 sistemi. 136 Sl. 6.11 Grafi~ki prikaz izvo|ewa operacija u vektorskom i osnovnom skalarnom procesoru. 137 6.1.2 MISD arhitekture (Sistoli~ni procesori) Mnogi problemi koji zahtijevaju intenzivna ra~unawa (procesne resurse) i koji sadr`e visok stepen paralelizma mogu se efikasno rije{iti primjenom jednostavnih procesnih elemenata organizovanih u neku regularnu strukturu (mre`a, stablo, linearno poqe i sl.). Ovakva organizacija procesirawa je pogodna za implementaciju u VLSI tehnologiji, s obzirom na jednostavnost elemenata i pravilnost strukture. Informacije u ovaj (sistoli~ni) sistem se "upumpavaju" preko vawskih }elija, preko kojih se ostvaruje i izlazna veza. Bazi~ni element naj~e{}e omogu}ava samo jednostavne operacije, kao npr. sabirawe i mno`ewe, kako je to predstavqeno primjerom na Sl. 6.12. d a b c b a d=c+a*b Sl. 6.12 Bazi~ni procesni element sistoli~nog procesora. Procesni element mo`e da procesira podatke i ostvaruje vezu sa drugim elementima paralelno (vi{e bita odjednom) ili serijski, mo`e biti sa ili bez lokalne memorije. Podaci ulaze u sistoli~no poqe, obra|uju se u procesnim elementima po principu proto~ne obrade i prenose u slijede}e procesne elemente ritmi~no i sinhrono. Komunikacija izme|u procesnih elemenata je jednostavna i lokalizovana na najbli`e susjede, {to omogu}ava (zbog malog rastojawa) pove}awe frekvecnije radnog takta. Primjer mno`ewa matrica koriste}i sistoli~ka poqa dat je na sl. 6.13. Sistoli~ni procesori zahtijevaju specifi~no projektovawe algoritama za odre|ene ra~unski intenzivne probleme i odgovaraju}u organizaciju sistoli~nog poqa. Visoke performanse i niska cijena implementacije uticali su na primjenu sistoli~kih poqa u mnogim oblastima (digitalna obrada signala, matri~na izra~unavawa i sl.). Tehnolo{ki problemi u implementaciji velikog broja U/I 138 veza na VLSI kolu, limitiraju veli~inu i mogu}nost sistoli~nih procesora, a time i oblast wihove primjene. Sl. 6.13 Mno`ewe matrica u sistoli~kom poqu 6.1.3 MIMD arhitekture MIMD (Multiple Instruction Multiple Data) arhitekture se sastoje od niza procesorskih elemenata, pri ~emu svaki procesor izvodi niz "svojih" instrukcija nad vlastitim 139 tokom podataka, pod kontrolom autonomne kontrolne jedinice. Rad procesorskih elemenata je asinhron, {to daje veliku fleksibilnost ovakvim sistemima. Ova pogodnost MIMD arhitektura nije bez cijene, s obzirom da procesni elementi moraju da kooperi{u u ciqu izvr{ewa jedinstvenog posla. Planirawe mehanizama komunikacije i sihronizacije postaje od osnovne va`nosti. Budu}i da je komunikaciono i sinhronizaciono vrijeme znatno ve}e od vremena izvo|ewa instrukcija, od interesa je eksploatacija paralelizma na vi{em nivou granularnosti (iako, naravno, svaki procesor pojedina~no mo`e eksploatisati paralelizam na ni`em, grupnom ili instrukcijskom nivou, zavisno od svoje arhitekture). MIMD arhitekture se daqe dijele na visoko-paralelne (~vrsto spregnute) i labavo spregnute. U kategorije labavo spregnutih sistema spadaju LAN (local area network) i WAN (wide area network) ra~unarske mre`e. Sprega izme|u ra~unara u ovim sistemima se izvodi serijskim linijama, a izme|u udaqenih ra~unara koriste se modemi i komutirane veze. Po{to jedino visoko paralelni sistemi mogu efikasno eksploatisati paralelizam sa vi{im nivoom granularnosti, daqa razmatrawa }emo ograni~iti na ove arhitekture, uz napomenu da se procjep izme|u ovih arhitektura i lokalnih ra~unarskih mre`a sve vi{e smawuje. Visoko paralelni sistemi se daqe mogu klasifikovati na multiprocesore i multira~unare. U prvom slu~aju procesori komuniciraju preko zajedni~ke memorije, a u drugom izmjenom poruka preko sistema (mre`e) za povezivawe. Ove arhitekture se mogu predstaviti (sli~no SIMD) modelima na Sl. 6.14 i Sl. 6.15. I jedne i druge arhitekture koriste brze ke{ memorije u ciqu uskla|ivawa propusnog opsega procesora i glavne memorije (multira~unari) i u ciqu smawewa konflikata pri pristupu memoriji i pristupu resursima spre`ne mre`e, te u ciqu umawewa efekata ka{wewa uslijed transmisije kroz mre`u (latencije), kod multiprocesora. Posebno su izra`eni problemi u realizaciji ke{ memorija kod multiprocesorskih sistema, zbog potrebe o~uvawa konzistencije podataka. Razli~ite strategije se primjewuju za implementaciju upisa i o~uvawe konzistentnosti (sa razli~itim performansama u pogledu vjerovatno}e postojawa podataka u ke{u, rastere}ewa pristupa glavnoj memoriji, cijeni implementacije itd.) kao npr. upis jedanput, upis kroz ke{, upis mimo ke{a i sl. 140 Sl. 6.14 MIMD PE - PE model. LM ozna~ava lokalni memorijski modul, a PE procesni element. Sl. 6.15 MIMD PE - memorijski model. M ozna~ava globalni memorijski modul. Multiprocesori U multiprocesorkim sistemima (IBM ES/9000, Sequent Symmetry, IBM RP3, BBN Butterfly, Fujitsu VPP500) svi procesorski elementi imaju pristup zajedni~koj memoriji preko spre`ne mre`e odre|ene strukture (varijanta sa kori{tewem memorije sa vi{e ulaza je skupa i ograni~ena na mawi broj procesora). Zajedni~ka memorija se realizuje obi~no u vi{e modula ~ime se obezbje|uje mogu}nost istovremenog pristupa razli~itim modulima. S obzirom na to da procesori dijele jedinstveni (globalni) adresni prostor, konflikti pri pristupawu istim memorijskim modulima mogu biti veoma izra`eni, a samim tim i limitiraju}i faktor u ekspanziji ovih sistema. Naime, intenzivna kooperacija izme|u procesora zahtijeva ~est pristup zajedni~kim memorijskim resursima (varijablama) i mo`e rezultovati ne`eqenim efektima. U ciqu smawewa broja konflikata, procesori mogu imati lokalne memorije u koje se smje{taju lokalni programi i podaci. Povezivawe procesorskih i memorijskih elemenata ostvaruje se preko spre`nih mre`a (komunikacionih podsistema). Od na~ina povezivawa u 141 znatnoj mjeri zavise performanse, mogu}nosti i naravno cijena ovakvih sistema. Kao {to se vidi sa Sl.6.14 i Sl.6.15, spre`ne mre`e se koriste i za povezivawe i komunikaciju izme|u ostalih dijelova sistema (PE-PE, PE-UI procesori). U tekstu koji slijedi, opisane su razli~ite varijante i osnovne karakteristike spre`nih mre`a. Spre`ne mre`e Zajedni~ka magistrala Najjednostavniji na~in sprezawa modula paralelnog sistema je preko zajedni~ke magistrale (Sl. 6.16). Sl. 6.16 Povezivawe zajedni~kom magistralom. Ovakav na~in povezivawa naj~e{}e se koristi kod multiprocesorskih paralelnih sistema. Moduli glavne memorije su mapirani u virtuelni adresni prostor svakog procesora i tipi~no su isprepleteni u ciqu postizawa ve}eg propusnog opsega. Po{to samo jedan procesor mo`e zauzeti magistralu i pristupiti zajedni~koj memoriji, broj procesora koji se mogu vezati na magistralu je ograni~en (naj~e{}e do 20). U ciqu smawewa konflikata i pove}awa memorijskog propusnog opsega koriste se ke{ memorije i arhitekture sa vi{estrukim magistralama (npr. Encore Ultramax). 142 Krosbar Veza svakog procesora sa svakim modulom globalne memorije mo`e se ostvariti i preko krosbar spre`ne mre`e (Sl. 6.17). M0 M1 MN-1 Sl. 6.17 Krosbar spre`na mre`a za povezivawe N procesorskih elemenata sa N memorijskih modula. Mre`u ~ini niz ortogonalnih n x n linija, gdje se veza izme|u procesorskih elemenata i memorijskih modula ostvaruje preko prekida~kih elemenata na svakom presjeci{tu linija. Svi procesori mogu istovremeno i bez konflikta da pristupe memoriji, sve dok pristupaju razli~itim modulima. Iako ova {ema znatno reducira konflikte, cijena mre`e raste proporcionalno sa N2 (brojem prekida~kih elemenata) {to nije prihvatqivo za sisteme sa velikim brojem procesnih elemenata. Primjer kori{tewa krosbar mre`e su IBM ES/9000, Fujitsu VPP500 i Cray Y-MP multiprocesori. Kao rezultat kompromisa izme|u performansi i cijene, nastale su mnoge varijante spre`nih mre`a, pri ~emu se nijedna, generalno, ne mo`e smatrati najboqom. Terminologija, u daqem opisu, }e se odnositi na procesorskoprocesorski model povezivawa, iako su rje{ewa tako|e primjenqiva na procesorsko-memorijski sistem. Za paralelni sistem koji se sastoji od N procesorskih elemenata, ~ije adrese ~ine skup P = {0,1, ... ,N-1}, spre`na mre`a se mo`e definisati skupom funkcija povezivawa, gdje je svaka funkcija povezivawe bijekcija sa P na P. Kada se izvr{ava neka funcija povezivawa f, onda se ostvaruje veza od procesora i ka procesoru f(i) (procesor i {aqe podatke procesoru f(i)). 143 Jednostepene spre`ne mre`e Ove mre`e se mogu predstaviti Sl. 6.18, gdje se veza ulaznih i izlaznih modula ra~unarskog sistema ostvaruje odgovaraju}im povezivawem ulaznih selektora (demultipleksera) i izlaznih selektora (multipleksera). Ove mre`e se nazivaju i recirkuliraju}e, jer podatak mo`e da pro|e kroz mre`u nekoliko puta prije nego {to stigne do odredi{ta. 0 US 0 IS 0 0 1 US 1 IS 1 1 N-1 US N-1 IS N-1 N-1 Sl. 6.18 Principijelna {ema jednostepenih mre`a. Hiper-kocka Neka je ukupan broj procesora N = 2m, i neka je binarna reprezentacija adrese svakog od N procesora pm −1 ... pi +1 pi pi −1 ... p0 . Funkcije povezivawa za ovu spre`nu mre`u date su izrazom: Cubei ( p m −1 ... pi +1 pi pi −1 ... p0 ) = p m −1 ... pi +1 pi pi −1 ... p0 za 0 ≤ i ≤ m − 1 , gdje je p i bit komplement od pi . Svaki procesni element se mo`e funkcijama povezivawa povezati sa m drugih procesora, tako da je ukupan broj mogu}ih povezivawa m * 2 m , odnosno broj veza je (m * 2 m ) / 2 . Funkcije povezivawa i 3-dimenzionalna strukturna reprezentacija za N = 8, date su na Sl. 6.19. 144 000 010 001 011 0 1 2 3 4 5 6 7 (Cube 0) 0 1 2 3 4 5 6 7 (Cube 1) 100 110 101 111 0 1 2 3 4 5 6 7 (Cube 2) Sl. 6.19 Struktura hiper-kocke i funkcije povezivawa. Cubei ( p m −1 ... pi +1 pi pi −1 ... p 0 ) mapira bilo koju adresu na drugu, koja ima na i-tom mjestu komplementiran bit. U predstavi na kocki, Cube0 povezuje ~vorove na horizontalnim, Cube 1 na dijagonalnim a Cube 2 na vertikalnim linijama. Za transfer su potrebna 1, 2 ili 3 koraka (recirkulacije) zavisno od izvora i odredi{ta. Posmatraju}i konceptualnu predstavu jednostepenih spre`nih mre`a sa Sl. 2.11 funkcije povezivawa hiper-kocke bi se dobile tako da se ulazni selektori USA ( 0 ≤ A ≤ N − 1 ) sa adresom A = a m−1... ai +1ai ai −1... a0 ve`u na m izlaznih selektora (IS) ~ije su adrese a m −1 ... a i +1 a i a i −1 ...a 0 , ( 0 ≤ i ≤ m − 1 ). S druge strane, svaki izlazni sektor sa adresom t m −1 ...t i +1 t i t i −1 ...t 0 , je povezan sa ulaznim selektorima (US) sa adresama t m −1 ...t i +1 t i t i −1 ...t 0 , ( 0 ≤ i ≤ m − 1 ). Hiper-kocka je primijewena u Caltec Cosmic Cube MIMD ma{ini, nCUBE (MIMD), Intel (MIMD), CM-2 (SIMD) itd. Spre`na mre`a PM2I Funkcije povezivawa za ovu mre`u su definisane izrazom: iPSC PM2 +i (P) = (P + 2 i ) mod N, PM2 -i (P) = (P - 2 i ) mod N, (N = 2 m , 0 ≤ i ≤ m − 1 ) i predstavqene su na Sl. 6.20. Ukupno ima 2m funkcija povezivawa. U ovoj {emi povezivawa, procesor sa adresom P mo`e poslati podatke svim drugim procesorima ~ije su adrese (P ± 2i) mod N. Odre|ivawe rute za komunikaciju izme|u procesora mo`e se bazirati na razlici adresa odredi{nog i izvori{nog procesora. Npr. za komunikaciju izme|u procesora 1 i 12 (N = 16), 145 razlika adresa je 11, pa podatak mo`e sti}i na odredi{te kori{tewem funkcija PM2I+0, PM2I+1, PM2I+3, prolaze}i kroz ~vorove 2,4. Razli~it skup funkcija rezultova}e istim odredi{tem, ako je vrijednost ∑ 2i jednaka razlici adresa odredi{ta i izvori{ta, gdje je i indeks PM2I funkcija iz skupa. Data manipulator vi{estepene spre`ne mre`e su bazirane na PM2I mre`ama. N=8 Sl. 6.20 Funkcije povezivawa PM2I spre`ne mre`e. Re{etka (~etiri najbli`a susjeda) a b c d e 0 1 2 3 f f 4 5 6 7 g g 8 9 10 11 h h 12 13 14 15 e a b c d Sl. 6.21 Re{etka (FNN). Funkcije povezivawa za ovu mre`u predstavqene su na Sl. 6.21 i definisane sa: FNN+1(P) = (P+1) mod N FNN-1 (P) = (P -1) mod N FNN+n(P) = (P + n) mod N FNN-n(P) = (P - n) mod N gdje se n = N podrazumijeva kao cijeli broj. 146 Sli~no kao kod PM2I mre`a, rutirawe u FNN mre`i se mo`e ostvariti na bazi razlike adresa odredi{nog i izvori{nog procesora. Ako posmatramo PM2I i FNN mre`u gdje obe povezuje N procesora i gdje je N = 2m za PM2I i n = N (cije- li broj) za FNN mre`u (odnosno n = 2 m / 2 ), onda je PM2I+0 = FNN+1, PM2I–0 = FNN–1, PM2I+m/2 = FNN+n, PM2I– m/2 = FNN–n. Implikacija je da su FNN funkcije povezivawa podskup PM2I funkcija. Ovaj tip spre`nih mre`a (sa razli~itim podvarijantama) je ~esto kori{ten u aktuelnim sistemima: Intel Paragon, CM-2, ASCI Red, Cray T3E (3D-torus) itd. Mije{awe i izmjena (Shuffle - Exchange) Ova mre`a ima dvije funkcije povezivawa: Shuffle ( pm −1 pm −2 ... p1 p0 ) = ( p m − 2 ... p1 p 0 p m −1 ) i Exchange ( p m −1 p m − 2 ... p1 p 0 ) = ( p m −1 p m − 2 ... p1 p 0 ) . Rutirawe podataka se realizuje nizom perfektnih mije{awa i izmjena, a maksimalan broj rutirawa je 2m (m mije{awa i m izmjena). Vi{estepene mre`e Vi{estepene mre`e, generalno, obezbje|uju povezivawe N sistemskih resursa sa M drugih resursa. Sastoje se iz odre|enog broja stepeni, pri ~emu se u svakom stepenu nalazi odre|eni broj a x b krosbar prekida~kih elemenata. Naj~e{}e, vi{estepne mre`e povezuju N ulaza sa N izlaza koriste}i 2 x 2 krosbar prekida~ke elemente, koji mogu biti postavqeni u jedno od 4 stawa (Sl. 6.22). a0 a1 Prekida~ki element b0 b1 Direktna veza a0 a1 b0 b1 Emisija odozdo a0 a1 b0 b1 Izmjena a0 a1 b0 b1 Emisija odozgo a0 a1 b0 b1 Sl. 6.22 Funkcije stawa 2x2 krosbar prekida~kih elemenata. 147 Mre`a vr{i prenos podataka od izvori{nih do odredi{nih elemenata komunikacionim putovima odre|enim stawima prekida~kih elemenata u pojedinim stepenima. Stawe prekida~kog elementa se odre|uje kontrolnim bitovima na ulazu, koji je obi~no, za i-ti stepen, i-ti bit adresne informacije rutirawa. (Naj~e{}e se na 2x2 prekida~kom elementu koristi 1 kontrolni bit, a drugi uzima za komplement prvog). U tekstu koji slijedi, izlo`ene su osnovne karakteristike vi{estepenih mre`a na primjeru generalizovane kocke. Generalizovana kocka Ova mre`a se sastoji iz m = log2N stepeni, gdje je N broj ulaznih odnosno izlaznih elemenata koji se povezuju. U svakom stepenu postoji N/2 prekida~kih elemenata (ukupno m * N/2) i po N ulaznih i izlaznih veza, ozna~enih od 0 … N-1. Ako se veze ozna~e tako da gorwi (dowi) ulazi (izlazi) prekida~kih elemenata imaju istu oznaku, onda stepen i generalizovane kocke implementira funkciju povezivawa Cubei , jer vr{i povezivawe linija ~ije se adrese razlikuju u i-toj bit poziciji. Ako se ostvaruje veza svih ulaza na po jedan izlaz, onda se koriste samo direktna i unakrsna stawa prekida~kih elemenata. Ako je neki prekida~ki element u stepenu i postavqen u stawe unakrsnog povezivawa, onda on izvr{ava Cubei funkciju povezivawa. Ako se vr{i povezivawe ulaza S = ( s m −1 s m − 2 ... s1 s 0 ) sa izlazom D = ( d m −1 d m − 2 ... d 1 d 0 ) , onda stawe odgovaraju}eg prekida~kog elementa u stepenu i mora biti postavqeno za unakrsno povezivawe, ako je s i ⊕ d i = 1 , u suprotnom - za direktno povezivawe. Primjer povezivawa ulaza 1 sa izlazom 4 dat je na Sl. 6.23. 148 Sl. 6.23 Put od ulaza 1 do izlaza 4 u generalizovanoj kocki sa 8 PE. Prekida~ki elementi su postavqeni u stawe za unakrsno povezivawe u stepenima 2 i 0 ( Cube 2 , Cube0 ) i direktno u stepenu 1. Za slu~aj prosqe|ivawa od jednog izvora ka vi{e odredi{ta istovremeno, koristi se stawe emisije odozgo (odozdo) prekida~kih elemenata. Za prosqe|ivawe poruka kroz mre`u, mo`e se koristiti adresa rutirawa (routing tag) T = S ⊕ D, inicijalne du`ine m-bita, gdje su S i D adrese izvori{ta/odredi{ta. U narednom stepenu, odnosni bit kori{ten u prethodnom stepenu mo`e se odbaciti. Ako se koristi prenos na vi{e odredi{ta (emisija), potrebno je 2m bita za adresu rutirawa. Topologije ekvivalentne generalizovanoj kocki su vi{estepene mre`e tipa omega, delta i dr. Ovaj tip spre`nih mre`a kori{ten je u velikom broju paralelnih arhitektura: NY Ultracomputer/IBM RP3, Illinois Cedar, BBN Butterfly, i dr. Sve navedene mre`e mogu se primijeniti u SIMD ili MIMD arhitekturama. Neke mre`e se mogu podijeliti na nezavisne mre`e, pri ~emu svaka podmre`a ima standardne mogu}nosti odgovaraju}eg tipa i veli~ine (hiper-kocka, PM2I mre`e imaju takvu osobinu) te mogu biti primijewene i u MSIMD (vi{estrukom SIMD) ili razdjeqivim SIMD/MIMD sistemima. Ovakvi sistemi se mogu razdijeliti u mawe nezavisne ma{ine razli~ite veli~ine, koje mogu raditi u SIMD ili MIMD modu (CM-5, PASM npr.). Spre`ne mre`e se karakteri{u na osnovu operativnog moda, upravqa~ke strategije, metodologije prekidawa i topologije. 149 Operativni mod mo`e biti sinhroni ili asinhroni. Sinhroni mod rada mre`a se koristi kod SIMD sistema, gdje se povezivawa i transferi (instrukcija i podataka) realizuju upravqawem iz jedne kontrolne jedinice. Asinhroni mod karakteri{e rad MIMD sistema (multiprocesori i multira~unari). U nekim sistemima realizovana je kombinacija sinhronog/asinhronog na~ina rada. Upravqa~ka strategija defini{e na~in upravqawa prekida~kim elementima, i mo`e biti centralizovana, gdje centralni kontroler, fizi~ki izdvojen od logike za prenos podataka, upravqa stawem prekida~kih elemenata, i distribuirana, gdje je upravqa~ka logika implementirana u prekida~kim elementima. Prekida~ki metod mo`e biti paketni (packet switching) ili baziran na fizi~kom povezivawu na nivou kola (circuit switching). U prvom slu~aju, podaci se prenose od izvori{ta do odredi{ta u paketima odre|ene du`ine, prolaze}i kroz niz prekida~kih elemenata. U drugom slu~aju, podskup prekida~kih elemenata se postavqa u stawa koja omogu}avaju postojawe direktne fizi~ke veze izme|u izvori{ta i odredi{ta za vrijeme trajawa transfera (npr. u Intel iPSC-2 sistemu, uspostavqawe veze izme|u izvori{ta i odredi{ta zahtijeva 350 µ s , sa brzinom transfera od 2.8 Mbyte/s). Mre`e koje omogu}avaju da se istovremena veza izme|u vi{e parova ulaznoizlaznih elemenata ostvaruje bez konflikata u prekida~kim elementima mre`e ili komunikacionim linijama, nazivaju se neblokiraju}e. Kod mre`a za paketni prenos, postoji vi{e tehnika kojima se paketi usmjeravaju od izvori{ta do odredi{ta. Ako je {irina prenosnog puta W (bita), i ako se podaci iz izvora ubacuju u mre`u sa periodom Tc, onda je propusni opseg kanala W/Tc. Efektivna brzina prenosa je mawa jer, pored informacionih podataka, paketima se dodaju adresne informacije i informacije za detekciju/korekciju gre{aka. Dodatno, prenosnim putovima se mogu prosqe|ivati i drugi paketi u svrhu sinhronizacije i dijagnostike u okviru mre`e, paketi potvrde prijema drugih paketa i sl. Tehnika "prosqe|ivawa bez pam}ewa" (wormhole routing) prosqe|uje najmawe dijelove paketa koji se mogu prenijeti (w bita) slijede}em elementu u prenosnom putu, ~im su oni raspolo`ivi (jedan paket koji se prenosi mo`e da ima dijelove u svim ~vori{tima prenosnog puta). Ako je L du`ina poruke, D broj segmenata prenosnog puta kojima se prenosi paket, a Ts vrijeme pripreme poruke i 150 inicijalizacije kanala, onda je (za slu~aj da nema ~ekawa zbog blokirawa u prenosnom putu) vrijeme prenosa Ts + Tc * (L /W + D). Kod tehnika "zapamti pa pro- slijedi" (store and forward), svako ~vori{te kroz koje poruka prolazi prvo primi kompletnu poruku, a zatim je prosqe|uje slijede}em ~voru, pa je du`ina prenosa od izvori{ta do odredi{ta (pod pretpostavkom da nema ~ekawa na resurse) Tn = Ts+Tc * (L / W)*D. Tehnika sa pam}ewem po potrebi (virtual cut through), omogu}ava prenos poruka bez zadr`avawa, sve dok se po~etak poruke (adresno zaglavqe) daqe prosqe|uje. Ako je slijede}e ~vori{te (izlazni kanal) zauzet, onda se poruka prikupqa i ~uva u prihvatniku posqedweg dostignutog ~vora. Kako ulazni kanal ne bi bio zauzet u slu~aju jedne blokirane poruke u ~voru, ~esto se realizuju ~vori{ta sa ve}im brojem prihvatnika. Topologija mre`e se mo`e opisati grafom kod kojeg ~vorovi predstavqaju prekida~ke elemente, a lukovi komunikacione putove. Kod stati~kih topologija (Sl. 6.24) veza izme|u ~vorova je fiksna i ustanovqene veze se ne mogu rekonfigurisati, dok dinami~ke topologije dozvoqavaju dinami~ku promjenu komunikacionih veza. Sl. 6.24 Stati~ke topologije povezivawa. Broj ~vorova grafa predstavqa veli~inu mre`e (network size). Osnovni parametri koji se koriste za procjenu komunikacionih mogu}nosti, kompleksnosti i cijene mre`e su: stepen ~vora (node degree-broj komunikacionih veza u jednom 151 ~voru) i dijametar mre`e (maksimalni najkra}i put izme|u bilo koja dva ~vora mre`e). Multira~unari Multira~unari se sastoje iz skupa procesnih elemenata (svaki sa procesorom, lokalnom memorijom i komunikacionom jedinicom) povezanih prema odre|enom rasporedu (topologiji). Svaki procesni element izvodi asinhrono instrukcije iz svoje lokalne memorije. Komunikacija sa drugim procesnim elementima u sistemu se ostvaruje izmjenom poruka. S obzirom na to da su cijena i kompleksnost limitiraju}i faktori za potpuno povezivawe svih procesnih elemenata, svaki procesni element je ograni~en na povezivawe sa odre|enim brojem susjednih elemenata. Poruka, tipi~no, treba da pro|e kroz odre|eni broj PE prije nego {to do|e do kona~nog odredi{ta. Topologija povezivawa se ~esto bira tako da je pogodna za implementaciju algoritama ciqnih aplikacija na odnosnoj arhitekturi. Budu}i da je teoretski kapacitet ovakve mre`e po ~voru Γ = topolo{kog grafa (broj veza n *W , gdje je n stepen ~vora D sr prema susjedima), W {irina puta za prenos informacija i D sr du`ina sredweg puta poruke, te`i se za minimalnim dijametrom grafa (~ime se smawuje D sr ). U ovu klasu MIMD sistema spadaju Intel iPSC2, n-CUBE, Paragon, Cray T3E, ASCI Red i drugi. Naj~e{}e isticana prednost multira~unara je mogu}nost jednostavnog pro{irewa dodavawem novih elemenata ({to je bio jedan od osnovnih projektnih parametara Inmos transpjutera), dok im je mana ka{wewe u prenosu poruka ka udaqenim procesnim elementima. U daqem tekstu date su osnovne karakteristike NYU Ultracomputer-a i Intel Paragon ra~unara, kao primjera multiprocesorske, odnosno multira~unarske arhitekture. 152 NYU Ultracomputer Blok {ema ovog MIMD ra~unara sa dijeqenom memorijom data je na Sl. 6.25. Procesni elementi tako|e imaju lokalnu memoriju. Za povezivawe bilo kojeg procesnog elementa sa bilo kojim globalnim memorijskim modulom koristi se vi{estepena Omega spre`na mre`a, sa implementacijom koncepata objediwavawa (combining) i Fetch & Op funkcija u prekida~kim elementima, sa ciqem pribli`avawa konceptu "para-ra~unara" (PRAM, J.Schwartz: bilo koji broj PE mo`e ~itati sadr`aj neke lokacije zajedni~ke memorije istovremeno (u jednom ma{inskom ciklusu); bilo koji broj PE mo`e upisivati u neku memorijsku lokaciju istovremeno). Sl. 6.25 Blok {ema NYU Ultracomputer-a. PNI (MNI) ozna~avaju procesorski (memorisjki) mre`ni interfejs. Dijeqenoj memoriji se pristupa indirektno, u vi{e ciklusa, preko spre`ne mre`e. Procesni elementi su vezani na mre`u preko procesorskog mre`nog interfejsa, a memorijski moduli preko memorijskog mre`nog interfejsa. Usmjeravawe prenosa u j-om stepenu mre`e je odre|eno vrijedno{}u j-tog bita odredi{ne adrese (‘0’ realizuje direktno povezivawe u odgovaraju}em prekida~kom elementu u j-tom stepenu, ‘1’ realizuje unakrsno povezivawe). Svaki ~vor u mre`i ima mogu}nost prikupqawa i objediwavawa poruka. Poruke koje se ne propu{taju na izlaz zbog zauzetosti odredi{ta, prikupqaju se u prihvatniku ~vora, te se ne zahtijeva transmisija. Funkcijom objediwavawa u svakom ~voru se objediwavaju zahtjevi vi{e procesnih elemenata za pristup zajedni~koj memorijskoj lokaciji. Tako npr., vi{e zahtjeva za o~itavawe jedne memorijske 153 lokacije se objediwava i daqe prosqe|uje kao jedan. Po dobijawu tra`ene vrijednosti u ~voru u kojem je realizovano objediwavawe, emisijom se prosqe|uje dobijena vrijednost svim procesnim elementima koji su tra`ili o~itavawe. Kod istovremenog zahtjeva za ~itawe i pisawe, vrijednost koja se upisuje {aqe se u memoriju, a istovremeno i vra}a procesnim elementima koji su tra`ili ~itawe. Kod vi{estrukog upisa, primjewuje se princip serijalizacije. Fetch&add je jedna forma Fetch&op operacije koja se izvr{ava u ~vorovima mre`e i predstavqa mo}nu generalizaciju test&set sinhronizacione primitive. Intel Paragon. Blok {ema ovog multira~unara data je na Sl. 6.26. Spre`na mre`na ima topologiju re{etke, a struktura svakog ~vora u re{etki je data na Sl. 6.27. U/I ~vorovi Servisni ~vorovi Mre`a Sl. 6.26 Blok {ema Intel Paragon ra~unara. Procesor je i860XP, RISC arhitekture sa radnim taktom 50 MHz, 16Kb instrukcionim i 16Kb ke{-om za podatke, i proto~nom jedinicom za operacije u pokretnom zarezu. Vr{ne performanse su 75 Mflops-a za operacije u duploj preciznosti i 100Mflops-a za operacije u jednostrukoj preciznosti. 154 16 MB Mre`ni interfejs Memorijski kontroler DRAM 32 MB i860 XP procesor poruka Port za pro{irewe i860 XP Aplikacioni procesor RPM Takt 50MHz 400MB/s Sl.6.27 Struktura procesnog elementa. Komunikacija izme|u procesora odvija se na bazi poruka. Svaki ~vor koji {aqe poruku drugom procesoru dijeli poruku u pakete, koji se prenose odvojeno. Poruke se prenose kao niz 16 bitnih rije~i preko MRC-u (Mesh Routing Component) (Sl. 6.28). Algoritam usmjeravawa je E-Cube, gdje se svi podaci prvo usmjeravaju horizontalno, a zatim vertikalno za razliku odstojawa po horizontali/vertikali (Sl. 6.29). Na hardverskom nivou, koristi se tehnika "prosqe|ivawa bez pam}ewa". 10 jednosmjernih portova 16 bitni paralelni transfer + paritet 200 MBytes/s po portu iMRC Sl. 6.28 Komponenta za rutirawe u re{etki. 155 GP ~vor GP ~vor Sl. 6.29 E-cube rutirawe (GP ozna~ava procesni element). 2.1.1 Ra~unarski sistemi upravqani tokom podataka Izvo|ewe nekog algoritma na ra~unarskom sistemu realizuje se ure|enim skupom operacija (ma{inskih instrukcija) izme|u kojih postoje relacije pretho|ewa i koje se izvode nad odre|enim podacima. Dok se kod von Neumann-ovih ma{ina operacije izvode sekvencijalno, pri ~emu je sekvenca odre|ena tokom programa, kod sistema upravqanih tokom podataka izvr{avaju se one operacije koje imaju raspolo`ive potrebne operande (uz uslov raspolo`ivosti procesnih resursa). Dakle, operacije se izvode paralelno i asinhrono, i nema ne`eqenih efekata koji se javqaju u multiprocesorskim sistemima uslijed istovremenih i nesinhronizovanih pristupa zajedni~koj memoriji. ^im se realizuje neka operacija, ona produkuje izlaz (nove podatke), a novi podaci ~ine spremnim za izvr{ewe novi skup operacija. Dakle, izvr{ewe operacija upravqano je tokom podataka u sistemu. Ovaj proces se modelira grafom, gdje se ~vorovima (aktorima) modeliraju operacije i pravilo okidawa (izvr{ewa), a lukovima podaci potrebni za izvo|ewe operacija, te produkti operacija i transmisija podataka. Postoje dva tipa ovih arhitektura: stati~ke i dinami~ke. Stati~ke arhitekture dopu{taju postojawe samo jednog podatka na bilo kom luku u bilo kom trenutku (Static Dataflow ma{ina). Dinami~ke arhitekture dopu{taju da se generi{e vi{e podataka izme|u dva ~vora tako {to se podaci iz razli~itih produkcija (iteracija) posebno markiraju za jedinstvenu identifikaciju i za adekvatno uparivawe sa odgovaraju}im podacima na drugim ulaznim granama neke operacije (Manchester ma{ina). 156 2.1.2 Sistemi upravqani zahtjevom Kod ovih sistem izvode se samo one instrukcije, ~iji su rezultati potrebni za izvo|ewe drugih instrukcija. Sve operacije ~ine ugnije`den skup, gdje se u svakom koraku vr{i redukcija izra~unavawem najdubqe ugnije`denih operacija. 2.1.3 Performanse paralelnih sistema Postoji {irok interes za ocjenu performansi paralelnih i uop{te ra~unarskih sistema i to tako da se performanse iska`u nekim jednostavnim indeksom, koji, s jedne strane, treba da iska`e mogu}nost sistema, a s druge strane, da bude osnov za komparaciju razli~itih sistema. Za ovo interes imaju prije svega krajwi korisnici koji bi na taj na~in raspolagali va`nim parametrom za izbor jedne od opcija pri nabavci ra~unarske opreme. Tako|e, ovakav parametar bi bio veoma va`an za procjenu mogu}nosti sistema da zadovoqi predvi|eni rast zahtjeva za obradu u budu}nosti. Ovakav indeks je potreban i proizvo|a~ima kako bi optimizovali arhitekturu, operativni sistem i programske prevodioce i realizovali proizvod za `eqenu ciqnu grupu, kao i mnogim drugima: ekonomistima, menaxmentu itd. Postoji nekoliko osnovnih problema za dobijawe takvog indikatora: prvi je objektivna te{ko}a da se kompleksni, me|usobno isprepleteni faktori redukuju u jedan reprezentativni indikator; drugi je potreba za verifikovanim standardom i nezavisnom institucijom koja bi verifikovala proklamovane karakteristike. Na kraju, problem predstavqa i obezbje|ewe izvo|ewa testirawa u pribli`no jednakim radnim uslovima. Jedan od najranijih poku{aja da se performanse ra~unara kvantifikuju datira po~etkom 60-tih godina (J.C.Gibson), i zasniva se na mjerewu i sra~unavawu vremena izvr{ewa "prosje~ne" instrukcije; recipro~na vrijednost ove veli~ine daje broj izvr{ewa prosje~nih instrukcija u sekundi (MIPS). Ovaj test ne uzima relativnu snagu "prosje~nih" instrukcija u razli~itim arhitekturama, pa se zato mo`e koristiti samo za komparciju ~lanova iz iste arhitekturne familije. Iz navedenog razloga, razvijeni su sinteti~ki test programi, sa ciqem da se reprezentuju tipi~ne aplikacije, pisane u jeziku visokog nivoa. Whestone test reprezentuje izvo|ewe milion "Whestone" instrukcija (nagla{eno numeri~kih i FP instrukcija), 157 a inverzna vrijednost vremena izvr{ewa (u sekundama) daje performanse u milionima (Whestones) instrukcija. Dhrystone test uzima u obzir strukturu podataka i operacija koje se sre}u u programima. LINPACK test je u po~etku bio FORTRAN program kojim se rje{ava sistem od 100 linearnih jedna~ina u duploj preciznosti (rezultat testa se iskazuje u poznatim MFLOPS-a). U ciqu boqe ocjene performansi, test je modifikovan za rje{avawe jedna~ina sa 1000 nepoznatih sa mogu}no{}u vlastite implementacije testa. Kako su procesne mogu}nosti superra~unara dramati~no rasle, rje{avawe ovog sistema jedna~ina se izvodilo u veoma kratkom vremenskom intervalu, te su pravila za LINPACK test modifikovana tako da je mogu}e koristiti sistem jedna~ina sa proizvoqnim brojem nepoznatih (MP-LINPACK). Iako iz navedenih razloga ovi testovi daju samo orijentaciju o mogu}nostima razli~itih arhitektura, ipak, mnogi drugi aspekti mogu biti i zna~ajniji za korisnika prilikom izbora ra~unarske opreme kao npr. mogu}nosti U/I podsistema, sistema za upravqawe bazama podataka, komunikacioni protokoli, podr{ka za odr`avawe, procesni zahtjevi aplikacija i naravno cijena. 158 7 Programirawe paralelnih sistema Iako se, iz prethodno izlo`enog, vidi izuzetna kompleksnost i raznovrsnost problema u podru~ju arhitektura, jo{ ve}i izazovi postoje u podru~ju programirawa paralelnih sistema. Napredak u ovoj oblasti tekao je sporije iz dva osnovna razloga: objektivna kompleksnost problema i nepostojawe jedinstvenog modela paralelne arhitekture kao generalne paradigme za paralelno procesirawe, analogne modelu Von Neuman-ove ma{ine za sekvencijalno programirawe. Rje{ewe problema le`i u odgovoru na jednostavno pitawe: "Kako realizovati program, kojim se rje{ava `eqeni aplikativni problem, tako da wegovo izvo|ewe na paralelnoj arhitekturi bude optimalno?". Optimalno izvo|ewe podrazumijeva postojawe funkcije ciqa koja mo`e biti: minimalno vrijeme izvr{ewa programa (algoritma), ravnomjerno optere}ewe procesnih resursa, minimalna cijena izvo|ewa i sl. Uobi~ajena funkcija ciqa za izvo|ewe neke aplikacije na paralelnom sistemu u teoretskim razmatrawima je minimizacija vremena izvr{ewa, a za skup nezavisnih programa, optimalan balans optere}ewa po procesnim elementima. U praksi, naj~e{}e je od interesa dobijawe najpovoqnijeg odnosa performansa/cijena, gdje cijena ukqu~uje ne samo cijenu procesirawa nego i razvoja aplikacije. Prethodno navedeno pitawe implicira inherentno postojawe paralelizma u aplikativnom problemu, te optimalnu eksploataciju istog u paralelnom sistemu. Aplikativni problem se mo`e rije{iti odre|enim ure|enim skupom operacija algoritmom, koji se mo`e posmatrati na razli~itim nivoima apstrakcije: nivou zadataka, podzadataka, procedura, grupa instrukcija, samih instrukcija ili elementarnih operacija. Izme|u odre|enih operacija (na svakom nivou) mo`e postojati 159 zavisnost u pogledu redoslijeda izvo|ewa (proistekla iz zavisnosti po podacima ili kontrolnoj zavisnosti). Za operacije izme|u kojih ne postoji zavisnost, ka`emo da se mogu izvesti (procesirati) istovremeno (paralelno). Ponovimo uslove nezavisnosti grupa operacija (iz ta~ke 4.4.1 – upravqa~ki hazardi) onako kako je to prvobitno definisao Bernstein (1966), koriste}i ulazno/izlazne skupove podataka. Varijable se klasifikuju u 4 kategorije: varijable koje se samo ~itaju, varijable koje se samo upisuju, varijable koje se prvo ~itaju, a zatim upisuju, varijable koje se prvo upisuju, a zatim ~itaju. Ako se skupovi ovih tipova varijabli ozna~e sa Wi , X i , Yi , Z i , onda se grupe operacije sa Sl. 7.1 a) mogu izvesti kao na Sl. 7.1 b), pod uslovom da je: 1) (W1 U Y1 U Z 1 ) I ( X 2 U Y 2 U Z 2 ) = 0 , 2) ( X 1 U Y1 U Z 1 ) I (W2 U Y 2 U Z 2 ) = 0 , 3) X 1 I X 2 I (W3 U Y 3 ) = 0 . Ako navedeni uslovi nisu ispuweni, onda postoji antizavisnost, direktna zavisnost ili izlazna zavisnost po podacima, respektivno. U svakom trenutku u procesu izvo|ewa, za skup operacija izme|u kojih ne postoji zavisnost u pogledu redoslijeda izvo|ewa i koje su spremne za izvo|ewe ka`emo da ~ine slobodan skup (intuitivno, optimalan raspored treba da omogu}i izvo|ewe {to ve}eg broja slobodnih operacija u svakom slijede}em vremenskom intervalu). P1 P1 P2 P2 P3 P3 a) Serijska b) Paralelno-serijska Sl. 7.1 Sekvence izvo|ewa operacija. 160 Bez obzira na to na kom nivou se razmatra problem, krajwi rezultat je raspodjela izvr{ewa bazi~nih (ma{inskih) instrukcija po procesorima. Problem optimalnog izvo|ewa (sa stanovi{ta zadate funkcije ciqa) u osnovi se sastoji iz: • problema grupisawa (podjele problema na zrna (grains), veli~ine konkurentnih modula-zrna koja se raspore|uju po procesnim elementima i strukture elementarnih operacija po zrnima), • problema optimalnog raspore|ivawa zrna po procesnim elementima. Rje{avawe ovih problema zahtijeva da se u razmatrawe ukqu~i i niz dodatnih parametara: karakteristike i mehanizmi me|uprocesorske komunikacije, te mogu}nost preklapawa komunikacionih i ra~unskih operacija, heterogenost procesorskih i memorijskih elemenata i sl. U realnim sistemima, naglasak je na {to efikasnijoj eksploataciji paralelizma, uz {to mawe optere}ewe programera. Automatska identifikacija i eksploatacija paralelizma, sofistikovano okru`ewe i alati, pogodni mehanizmi i metode za eksplicitnu specifikaciju i eksploataciju paralelizma su odnosni aspekti u ovom domenu koji su predmet kontinualnog istra`ivawa i usavr{avawa. 7.1 Vremenski gubici u paralelnim sistemima Teoretski, maksimalno ubrzawe koje se mo`e posti}i izvo|ewem programa na paralelnom sistemu sa N procesora jednako je broju procesora. U takvom scenariju, svih N procesora bi izvodilo samo korisne instrukcije, i svi bi po~eli i zavr{ili procesirawe u istim vremenskim trenucima. U praksi, ostvarivawe ovakvih maksimalnih performansi se ne posti`e zbog gubitaka vremena prouzrokovanih: • • • • komunikacionim ka{wewima, sinhronizacijom izme|u procesora, nezaposleno{}u procesora (prazni hodovi procesora), neophodnim upravqa~kim aktivnostima operativnog sistema. Komunikaciona ka{wewa i mehanizmi Kao {to smo prethodno pomenuli, izvo|ewe ra~unawa (procesa, niti, grupa instrukcija) se u paralelnim sistemima raspodjequje po procesnim elementima. Procesori koji izvode ra~unawa izme|u kojih postoji zavisnost po podacima, moraju imati 161 mogu}nost me|usobne komunikacije u ciqu izmjene podataka. Procesori izmjewuju podatke na dva osnovna na~ina: preko zajedni~ke memorije ili preko komunikacionih kanala (kompromisni koncept je koncept po{tanskog sandu~eta). Implikacije me|uprocesorske komunikacije su komunikaciona ka{wewa i konflikti zbog kori{tewa zajedni~kih (komunikacionih) resursa. Komunikaciona ka{wewa se odnose na vrijeme koje je potrebno za transfer podataka od izvora do odredi{ta, a konflikti u kori{tewu resursa nastupaju kada se pojavi vi{e zahtjeva za kori{tewe jednog resursa, {to rezultuje dodjeqivawem resursa jednom zahtjevu i ~ekawem ostalih. Prilikom prenosa poruka kroz spre`nu mre`u npr., vi{e poruka istovremeno mo`e zahtijevati prolaz kroz jedan ~vor, uz mogu}u degradaciju komunikacionog saobra}aja ne samo u okolini navedenog ~vora, nego i u cijeloj mre`i. Za redukovawe ovih konflikata koriste se razli~ite tehnike: npr. objediwavawe istih komunikacionih zahtjeva u komunikacionim ~vorovima, primijeweno u NYU Ultracomputer/IBM RP3, ili razli~ite softverske adaptivne tehnike usmjeravawa poruka koje uzimaju i obzir i teku}e stawe saobra}aja u mre`i. Prema tome, ka{wewa uslijed izmjene podataka izme|u procesora, mogu u znatnoj mjeri uticati na performanse paralelnog izvo|ewa. Za ilustraciju, u tabeli 7.1 za neke paralelne i distribuirane sisteme date su aproksimativne vrijednosti parametara komunikacionih ka{wewa Ts i Tw u [ µ s ] (vrijeme incijalizacije kanala i vrijeme prenosa izme|u procesora po rije~i). Tipi~no ka{wewe pri transferu 100 bajtne poruke izme|u procesora je, za prvu generaciju multira~unara (1983-1987) 6000 µ s , za drugu generaciju (1988-1992) 5 µ s i tre}u (aktuelnu) generaciju ispod 0.5 µ s [45]. Tabela 7.1 Aproksimativne vrijednosti parametara komunikacionih ka{wewa za neke paralelne ra~unarske sisteme. Sistem Cray-T3E Intel Paragon Thinking Machines CM-5 Intel DELTA nCUBE-2 Radna stanica na Ethernet-u Ts [ µ s ] Tw [ µ s ] 0.013 121 82 77 154 1500 0.07 0.44 0.54 2.4 5.0 162 Mehanizam komunikacije kod multiprocesora je (naj~e{}e) direktan pristup dijeqenim varijablama u zajedni~koj memoriji. Ovakvi mehanizmi podlo`ni su nepredvi|enim i ne`eqenim efektima: kod asinhronog izvo|ewa ra~unawa po procesorima bilo koja izmjena u sekvenci pristupa zajedni~kim varijablama mo`e produkovati razli~it krajwi rezultat (alternativno, procesori mogu komunicirati i mehanizmom poruka). Kod multira~unara, komunikacija se realizuje na bazi prenosa poruka, kori{tewem specifi~nih naredbi odre|enog programskog jezika ili biblioteke funkcija. Nijedan pristup jo{ uvijek nema adekvatno rje{ewe za fundamentalne probleme memorijske latentnosti i komunikacionih ka{wewa. Problemi sa odr`awem koherentnosti ke{ memorija i nagomilavawem konflikta na magistrali, kod sistema sa zajedni~kom memorijom, limitiraju pove}awe broja procesora u ovim sistemima. Cijena komunikacije izme|u procesora kod MIMD multira~unara sa distribuiranom memorijom name}e eksploataciju krupnozrnastog paralelizma na globalnom nivou: ra~unawa (implicitno) treba da izvedu hiqade instrukcija bez prekida (promjene konteksta) ili poziva operativnog sistema. Cijena kreirawa, blokirawa, destrukcije, komunikacije i sinhronizacije za ra~unawa, mo`e iznositi stotine (pa i hiqade) procesorskih ciklusa. Npr. kod sistema baziranih na standardnim mikroprocesorima, pristizawe poruke u neki procesni element mo`e: • • • generisati prekid za odredi{ni procesor, uz aktivirawe sekvence za obradu poruke, detektovati sam procesor periodi~nim ispitivawem da li je poruka stigla, biti detektovano strukturom programa, ako se obezbijedi, da za svako slawe poruke iz izvori{nog procesora, odredi{ni procesor izvede korespondentu prijemnu primitivu. Svi navedeni na~ini su relativno spori i neefikasni za sitnozrnastu komunikaciju, neophodnu za eksploataciju sitnozrnastog paralelizma. Napori za prevazila`ewe ovih problema i}i }e vjerovatno u pravcu razvoja vi{enitnih arhitektura, gdje }e cijena upravqawa nitima biti relativno mala. Sa programskog aspekta, komunikacija se realizuje odgovaraju}im konstrukcijama programskih jezika. 163 CSP (communicating sequential programs) jezici podr`avaju iskqu~ivo komunikaciju preko kanala: komunikacija se realizuje eksplicitnim imenovawem odredi{ta komunikacije. Izlazna naredba ima format: : = ! < expression > a prijem se inicira ulaznom naredbom : = ? target variable. Osnovni koncept komunikacije u ADA programskom jeziku su randevui: randevu se ostvaruje sa dva doga|aja: • • pozivom koji jedan zadatak upu}uje drugom, prihvatom komunikacije od strane drugog zadatka izvo|ewem ACCEPT naredbe (Sl. 7.2). Ipak, ADA dozvoqava i komunikaciju preko dijeqenih varijabli kategorizacijom varijable SHARED kvalifikatorom. CALL ACCEPT Sl. 7.2 ADA randevui. H.F.Jordan , predla`e slijede}e tipove varijabli u programskim jezicima za paralelno procesirawe u sistemima sa distribuiranom memorijom: • • • • private - jedno ime varijable ovog tipa referencira u memoriji svakog procesora specifi~nu memorijsku lokaciju, unique - jedna varijabla ovog tipa postoji samo u memoriji jednog procesora, cooperative update - postoji jedna kopija varijable u svakom memorijskom modulu. A`urirawe se mora izvesti istovremeno nad svim kopijama. replicated - a`urirawe se izvodi nad lokalnim kopijama podataka (npr. kod indeksne varijable koja uzima isti opseg vrijednosti u svim procesorima). 164 Tako|e se predla`u globalni komunikacioni mehanizmi: emisija (broadcast), univerzalna emisija i univerzalna izmjena za prosqe|ivawe i izmjenu podataka. Concurrent Pascal zahtijeva eksplicitnu specifikaciju dijeqenih varijabli te kontrolisan pristup preko definisanih procedura za rad nad dijeqenim varijablama. Compositional C++ (CC++, Caltec/Chandy, Kesselman) ima ekstenziju standardnog C++ jezika kojom se defini{u procesorski objekti koji se koriste za reprezentaciju lokalnog adresnog prostora: ra~unawa koja se izvode u procesorskom objektu i koja rade sa podacima definisanim u tom objektu, rade u lokalnom (i zato "jeftinom") adresnom prostoru. Za referencirawe podataka i funkcija u drugim procesorskim objektima, koriste se globalni pokaziva~i. Primjer pristupa ne-lokalnim podacima iz nekog ra~unawa (niti) iz procesorskog objekta p obj1 , dat je na Sl. 7.3. Svako referencirawe podataka u drugom procesorskom objektu se realizuje: • • • formirawem i slawem poruke udaqenom procesorskom objektu (uz blokirawe niti ra~unawa koje je iniciralo referencirawe), kreirawem nove niti za pristup udaqenom objektu. Pristup se realizuje zavr{etkom izvo|ewa kreirane niti na udaqenom procesoru, vra}awem tra`ene vrijednosti inicijalnoj niti i nastavkom izvo|ewa iste. pobj1 *gptr *gptr = 3 write(*gptr,3) ack read (*gptr) value = 3 var_x = 3 * pobj2 var_x var_y += *gptr ? var_x Sl. 7.3 Udaqeno pisawe/~itawe. MPI (message passing interface) procesi izvode programe pisane u standardnim sekvencijalnim jezicima. Komunikacija izme|u procesa se realizuje u odre|enim ta~kama pozivom odgovaraju}ih funkcija iz MPI biblioteke za slawe i prijem poruka (MPI-SEND i MPI-RECV). Grupa procesa mo`e biti istovremeno ukqu~ena u proces grupne komunikacije (emisije npr.) kroz MPI mehanizam komunikatora. 165 Prosqe|ivawe poruka je nedeterministi~ko (ako procesi A i B {aqu poruku procesu C, bez obzira na redoslijed slawa, redoslijed prijema nije odre|en). Sinhronizacija Ra~unawa u procesnim elementima se izvode brzinom koja se ne mo`e ta~no predvidjeti. Posqedica toga je asinhrono generisawe akcija, doga|aja i podataka koji se koriste u drugim procesima u paralelnom sistemu. U ciqu ure|ivawa ovih doga|aja, uvodi se skup ograni~ewa (sinhronizacija) koja se koriste za odga|awe izvo|ewa odre|enih ra~unawa, kako bi se zadovoqili potrebni uslovi. Osnovni tipovi sinhronizacije kod multiprocesora su me|usobno iskqu~ivawe i sinhronizacija uslova. Me|usobno iskqu~ivawe obezbje|uje da procesi pristupaju ekskluzivno fizi~kim ili virtuelnim resursima. Dio koda koji se izvodi ekskluzivno od strane nekog procesa i u kojem se (eksluzivno) pristupa dijeqenoj varijabli, naziva se kriti~na sekcija. Sinhronizacija uslova je tip sinhronizacije gdje procesi moraju da ~ekaju dok stawe dijeqene varijable, koje zavisi od rezultata izvo|ewa grupe procesa, ne dobije `eqenu vrijednost. Kod me|usobnog iskqu~ivawa proces detektuje status kriti~ne sekcije, i ako je slobodna, postavqa status kriti~ne sekcije u zauzeto a zatim izvodi kriti~nu sekciju. Ako je kriti~na sekcija zauzeta, proces mo`e nastaviti sa ispitivawem statusa kriti~ne sekcije (kontinualno ili periodi~no) ne osloba|aju}i procesor, ili se mo`e implementirati mehanizam koji proces stavqa u stawe ~ekawa a procesor osloba|a za druge aktivnosti. Proces koji ekskluzivno izvodi kriti~nu sekciju, na izlasku iz kriti~ne sekcije postavqa indikator statusa kriti~ne sekcije u slobodno. Ako su neki procesi u redu ~ekawa za kriti~nu sekciju, onda se aktivira jedan od procesa sa liste ~ekawa, na bazi odre|enog prioriteta. Naj~e{}a implementacija ovog mehanizma je preko nedjeqivih P(s) i V(s) primitiva (Dijkstra), gdje P primitiva osigurava ekskluzivan ulaz u kriti~nu sekciju; s je varijabla stawa zauzetosti kriti~ne sekcije, a V primitivom se reguli{e napu{tawe kriti~ne sekcije. Pro{ireni semafor koji je razvio Agervala (1977) omogu}ava da proces zahtijeva vi{e resursa istovremeno. Uslovno kriti~na sekcija je strukturirani, korisni~ki orijentisani mehanizam (csect v do await c:s) koji obezbje|uje da proces ne mo`e u}i u kriti~nu sekciju s dok se ne ispuni uslov c, i da 166 ne mo`e do}i do preklapawa izvo|ewa razli~itih kriti~nih sekcija nad istim dijeqenim resursom v. Ekstenzije uslovno kriti~nih sekcija su monitori, koji ~ine skup dijeqenih podataka i skup funkcija preko kojih se jedino mo`e pristupiti strukturama dijeqenih podataka. Monitorske funkcije obezbje|uju sinhronizaciju konkurentnih procesa. Sinhronizacija uslova se naj~e{}e realizuje mehanizmom barijere. Svi procesi moraju sti}i na barrier naredbu (koja se stavqa u kod svakog procesa). Samo jedan proces (nakon {to su svi stigli na barijeru), prolazi kroz barijeru, i izvodi kod izme|u barrier i endbarrier naredbe (Sl. 7.4). Nakon toga, svi procesi mogu nastaviti izvo|ewe naredbe iza barijere. barrier endbarrier Sl. 7.4 Sinhronizacija na barijeri. Varijanta fazi-barijere dopu{ta da izvo|ewe procesa bude u nekoj sekciji koda prilikom sinhronizacije. Sinhronizacija mehanizmom doga|aja, koristi primitive wait i signal. Wait primitiva obezbje|uje stavqawe procesa u stawe ~ekawa na doga|aj (ili kombinaciju doga|aja). Drugi, aktivni procesi, signaliziraju primitivom signal nastanak odre|enih doga|aja i kada se desi doga|aj na koji blokirani proces ~eka, operativni sistem ga prevodi u stawe procesa spremnog za izvo|ewe. U paralelnim multira~unarskim sistemima, sinhronizacija se realizuje mehanizmom poruka. Neke od varijanti primitiva za izmjenu poruka, opisane su prethodno. Za implementaciju sinhronizacije pri pristupu zajedni~kim resursima neophodna je bila realizacija nedjeqivih operacija ispitivawa i a`urirawa memorijskih lokacija na hardverskom/instrukcionom nivou. Razli~iti sistemi imaju razli~itu formu ovih instrukcija: TEST-AND-SET (TAS), COMPARE-AND-SWAP 167 (CAS) i sl. U vi{eprocesorskim sistemima mora se obezbijediti da procesor koji izvodi navedene instrukcije, ima kontrolu nad pristupom memoriji za cijelo vrijeme izvo|ewa instrukcije. Fetch & add operacija omogu}ava konkurentno izvr{avawe generalizovane TAS instrukcije uz serijalizaciju pristupa memoriji. Kod sinhronizacionih metoda na bazi bit mapa (HEP sistem), svakoj dijeqenoj varijabli se pridru`uje sync i data poqe. Svaka sinhronizaciona instrukcija je nedjeqiva i sadr`i poqe maske, koje sadr`i informacije potrebne za ispitivawe i modifikaciju sync poqa (forma: OP Address, Mask). Operacija ~itawa, npr. testira odre|eni bit sync poqa, i ako je on ‘1’ (raspolo`iv) ~itawe se realizuje, a odnosni bit postavqa u ‘0’. Prazni hodovi procesora Prazni hodovi procesora su periodi u kojima procesor ne obavqa korisne instrukcije. U paralelnim sistemima (zbog zavisnosti po podacima ra~unawa (operacija) na razli~itim procesorima) prazni hodovi su naj~e{}e uzrokovani: • • • ~ekawem na zavr{etak ra~unawa koja produkuju podatke, ~ekawem na prosqe|ivawe podataka (komunikaciona ~ekawa), ~ekawem na dodjelu posla. Navedena, ~ekawa mogu poticati od neodgovaraju}eg rasporeda ra~unawa po procesnim elementima, redoslijeda izvo|ewa ra~unawa i dr. Navedene pojave produ`avaju vrijeme izvr{ewa programa, smawuju iskori{tewe procesora i pove}avaju cijenu. Gubici uslijed aktivnosti operativnog sistema U paralelnim sistemima operativni sistem je, kao i kod jednoprocesorskih sistema, odgovoran za upravqawe izvr{ewem programa. Ove aktivnosti podrazumijevaju stati~ko/dinami~ko mapirawe procesa po procesnim elementima, upravqawe procesima i resursima, nadgledawe aktivnosti u sistemu i sl. Iako su funkcije operativnih sistema visoko optimizovane, ove aktivnosti tako|e produ`avaju vrijeme izvo|ewa programa u paralelnom okru`ewu. 168 7.2 Granularnost paralelizma Da bi se neki program izveo na paralelnoj arhitekturi konkurentnim procesirawem na vi{e procesnih elemenata, on se mora razdijeliti na parcijalno ure|en skup zadataka (T, p ). Efikasnost paralelnog izvo|ewa zavisi od vi{e parametara: broja i karakteristika procesora i komunikacionih resursa, broja modula na koje se program dijeli za izvo|ewe i strukture veza izme|u razdijeqenih modula, iznosa pojedinih komponenata vremenskih gubitaka itd. Pove}awe broja modula i broja procesora koji se pridjequju programu za izvr{ewe mo`e rezultovati degradacijom performansi, ako vremenski gubici (zbog intenzivirawa me|uprocesorske komunikacije) znatno rastu sa porastom broja modula i procesora. Granularnost modula-zrna ima zna~ajan uticaj na kvalitet razdiobe i defini{e se kao odnos potrebnog vremena ra~unawa u odnosu na komunikaciona ka{wewa generisana zrnom (R/C). Ka`e se da je zrno sitno ako je odnos R/C mali (> 1). Sitna zrna su mikrooperacije i instrukcije; grupe instrukcija ~ine zrna sredweg nivoa granularnosti, a krupna zrna su funkcije i procesi (zadaci). Generalno, dekompozicija na sitna zrna implicira ve}i iznos paralelizma, ali i ve}e gubitke vremena, zbog pove}awa iznosa komunikacije i sinhronizacije. Analogno, krupnija zrna impliciraju mawi stepen paralelizma, ali i mawe vremenske gubitke. Kako je to prethodno izlo`eno paralelizam na nivou mikrooperacija i instrukcija eksploati{e se na hardverskom nivou, paralelizam sredweg nivoa se mo`e eksploatisati hardverski, softverski ili kombinovano (programske petqe, niti) dok se krupnozrnasti paralelizam eksploati{e softverskim tehnikama. Da bi se ostvarile dobre performanse izvo|ewa, potrebno je napraviti balans izme|u iznosa paralelizma me|u programskim modulima i odgovaraju}eg iznosa vremenskih gubitaka. Zato je u odre|enim slu~ajevima potrebno grupisati sitnozrnaste zadatke u ve}a zrna, a u drugim dekomponovati krupna zrna u sitnozrnaste module. Da bi se paralelizam eksploatisao, potrebno je prvo izvr{iti identifikaciju istog, a zatim ga na odgovaraju}i na~in specifikovati ma{ini. Identifikacija i specifikacija paralelizma, mo`e se realizovati: 169 • • • automatski u fazi prevo|ewa, a na osnovu relacija zavisnosti po podacima pojedinih grupa naredbi, eksplicitno od strane programera, odgovaraju}im instrukcijama programskog jezika, kombinovano. 7.3 Automatska identifikacija i specifikacija paralelizma U ovom pristupu, sav teret identifikacije i specifikacije na~ina na koji }e se eksploatisati paralelizam (prestrukturirawe, particionisawe, mapirawe) preuzimaju programski prevodioci, a korisnici realizuju programe koriste}i standardne jezike. Pored toga {to korisnik ne ula`e nikakav dodatni napor u odnosu na sekvencijalno programirawe, ovaj pristup omogu}ava direktnu eksploataciju postoje}ih sekvencijalnih programa (ponovo prevedenih paraleliziraju}im prevodiocem) na paralelnim sistemima. Osnovni problem je {to paraleliziraju}i kompajleri te{ko mogu, u op{tem slu~aju, identifikovati visok nivo paralelizma (npr. zbog nemogu}nosti da odrede vrijednosti pokaziva~a u fazi prevo|ewa, zbog ogromnog broja kompleksnih me|uzavisnosti i sl.). Cijena koja se pla}a za komoditet programera je, ~esto, zna~ajno umawewe ubrzawa izvo|ewa aplikacije i iskori{tenosti resursa paralelne ma{ine. Paraleliziraju}i kompajleri koriste razli~ite postupke transformacije izvornog programa u ciqu postizawa {to ve}eg iznosa paralelizma u trasformisanom kodu, naravno uz o~uvawe semanti~kog integriteta izvornog programa. Optimizacija po tragu (trace scheduling) npr., je tehnika globalne optimizacije, koja se zasniva na selidbi operacija (prije/poslije granawa) u ciqu pove}awa bazi~nih blokova (i time iznosa paralelizma) po najvjerovatnijem putu izvo|ewa. Optimizacija programskih petqi je od vitalnog zna~aja za eksploataciju paralelizma, jer petqe potencijalno sadr`e veliki iznos paralelizma i izvo|ewe petqi je naj~e{}e dominantni dio izvo|ewa programa. Osnovne tehnike optimizacije su vektorizacija, razmotavawe petqi i softverska proto~nost. Tehnika vektorizacije nastoji iskazati operacije u petqi skupom vektorskih operacija; razmotavawem petqi za odre|eni broj iteracija pove}ava se 170 bazi~ni blok u tijelu petqe, i na taj na~in pove}ava iznos paralelizma koji se mo`e eksploatisati pri izvo|ewu. Tehnikom softverske proto~nosti, transformi{e se tijelo petqe u ciqu omogu}ewa direktne eksploatacije paralelizma izme|u iteracija i u okviru jedne iteracije (Sl. 7.5). Neki od ad-hok optimizacionih postupaka su: zamjena indukcionom varijablom u izrazima u petqi, preimenovawe skalarnih varijabli, zamjena slijede}ih referencirawa skalara wegovim izrazom, dijeqewe petqi, dijeqewe domena podataka, i sl. a: b: c: d: i←i +1 1: a j←i +h k←i +g l←j +1 a) a) Sekvencijalna petqa 0: a 1: b, c 2: d, a 3: b, c 4: d b) b) Dvostruko razmotana petqa 1: a 2: b, c 3: d, a 2: b, c 3: d c) c) Proto~na petqa Sl. 7.5 Optimizacija petqe. FORTRAN 77 program Modul za prikaz FRONT END Analiza Interakt. modul Katalog transform. Interna predstava BACK END Paralelizovani SUPRENUM FORTRAN program Sl. 7.6 Struktura sistema SUPERB. Kao primjer automatske identifikacije i specifikacije parelelizma, navedimo SUPERB (Suprenum Parallelizer Bonn), interaktivni paralelizator koji 171 transformi{e standardne FORTRAN 77 sekvencijalne programe u semanti~ki ekvivalentne paralelne SUPRENUM FORTRAN programe, za SUPRENUM MIMD ma{inu . Struktura sistema je predstavqena na Sl. 7.6. Front End trasformi{e FORTRAN 77 program u internu reprezentaciju. Modul za analizu sadr`i alate za analizu toka programa i analizu zavisnosti: izlaz iz ovog modula su informacije o nizovima definicija varijabli i nizovima kori{tewa, zavisnosti izme|u naredbi, `ivotu varijabli, raspolo`ivo{}u izraza i sl. Na osnovu tih informacija vr{i se paralelizacija, i to u dvije faze: • identifikuje se krupnozrnasti paralelizam i raspodjequje u skup procesa (MIMD paralelizacija). Paralelizacija se bazira na razdiobi domena podataka, pri ~emu svaki segment predstavqa lokalni adresni prostor procesa, • svaki proces se analizira, identifikuju se programske petqe koje se prestruktui{u kao vektorske operacije (SIMD paralelizacija-vektorizacija). Time se posti`e visok stepen paralelne obrade u ~vorovima koji izvode procese i koji imaju mogu}nost efikasnog procesirawa vektorskih operacija. Interaktivni sistem ipak dopu{ta korisniku mogu}nost pra}ewa i pode{avawa procesa transformacije. Back End modul, na osnovu transformisane interne reprezentacije, generi{e paralelizovan SUPRENUM FORTRAN program. Sli~an pristup koristi Parafrase prevodilac razvijen na univerzitetu u Ilinoisu, Buldog prevodilac (Yale) i dr. Neka rje{ewa omogu}avaju da se odre|eni problemi specifikuju jezikom visokog nivoa, baziranim na apstraktnim tipovima podataka - objektnim klasama, koji sadr`e kako definiciju potrebnih struktura podataka za navedene probleme, tako i operacija pridru`enih odnosnoj klasi. Ovakva specifikacija ne sadr`i specifi~ne konstrukcije za paralelno programirawe. Sistem automatski prevodi ovakvu specifikaciju visokog nivoa u paralelni programski jezik (SUPRENUM FORTRAN). U programskom jeziku BLAZE poku{ava se na}i kompormisno rje{ewe izme|u sekvencijalnog programirawa i eksplicitne identifikacije i specifikacije paralelizma u paralelnim programskim jezicima. Sa izuzetkom naredbe "forall", tok kontrole u BLAZE jeziku je potpuno sekvencijalan. Intencija jezika je da se ostvari 172 visoko paralelizovano izvo|ewe na razli~itim SIMD i MIMD arhitekturama uz potpuno osloba|awe korisnika od detaqa paralelnog izvo|ewa (korisnik nema predstavu o mogu}im vi{estrukim nitima toka kontrole u fazi izvo|ewa npr.). Realizaciju ovog ciqa u potpunosti preuzima prevodilac i run-time okru`ewe. Jezik ima sintaksu sli~nu PASCAL-u. Da bi prevodilac mogao izvr{iti kvalitetnu paralelizaciju, napravqene su odre|ene restrikcije: pokaziva~i nisu implementirani jer spre~avaju efikasnu identifikaciju paralelizma. Dodatno, procedure imaju funkcionalnu semantiku: efekat izvo|ewa procedure mo`e biti samo pridjeqivawe povratne vrijednosti procedure. U okviru procedure dozvoqen je pristup samo lokalnim podacima. Gnije`dewe procedura nije dozvoqeno. Ovakav koncept procedura je karakteristi~an za funkcionalne jezike (bazirane na toku podataka). Ipak, za razliku od funkcionalnih jezika BLAZE dopu{ta vi{estruko pridjeqivawe istoj varijabli. Dakle, jezik omogu}ava programirawe na na~in veoma blizak konvencionalnom, {iroko kori{tenom PASCAL-u, a s druge strane automatsku identifikaciju i specifikaciju paralelizma u toku prevo|ewa, i eksploataciju istog u fazi izvo|ewa programa. Sli~ne karakteristike imaju i funkcionalni jezici SISAL, VAL ili ID. 7.4 Projektovawe i razvoj paralelnih programa I pored toga {to kori{tewe paraleliziraju}ih prevodilaca osloba|a korisnika dodatne dimenzije kompleksnosti programirawa u paralelnom okru`ewu, ipak ono ima i nekoliko ozbiqnih nedostataka. Osnovni nedostatak je nemogu}nost prevodilaca da mijewa semantiku programa, odnosno strukturu sekvencijalnih algoritama, koji ~esto ne sadr`e mnogo inherentnog paralelizma. Prestrukturirawem postoje}ih algoritama ili konstrukcijom novih, mo`e se obezbijediti znatno pove}awe iznosa (pa prema tome i eksploatacije) paralelizma. Konkurentnost se pojavquje kao fundamentalni zahtjev za algoritme i programe. Daqe, mnogi postoje}i sekvencijalni jezici sadr`e konstrukcije koje limitiraju mogu}nost detekcije paralelizma u postoje}im programima (pokaziva~i, mnogostruko ugnije`dene procedure sa mogu}no{}u pristupa dijeqenim varijablama, "alias" varijable i sl.). Sekvecijalni programi nisu automatski prilagodqivi za izvo|ewe za slu~aj pove}awa broja procesora u sistemu i obima problema. Mogu}nost pro{irewa (scalability) u navedenom smislu se tako|e name}e 173 kao jedan od bitnih zahtjeva za paralelne programe. Kompleksnost paralelnog programirawa izrazito potencira modularnost kao fundamentalni princip programirawa. Aspekti modularnosti sekvencijalnog programirawa moraju biti pro{ireni, s obzirom na specifi~nost paralelnih sistema. Prirodan ciq je da se navedena svojstva iska`u adekvatnim konstrukcijama odgovaraju}eg programskog jezika, ne optere}uju}i programera detaqima komunikacije i koordinacije me|u procesorima. Pored programskog jezika, od su{tinskog zna~aja za razvoj i realizaciju paralelnih programa je postojawe generalnog modela paralelne ma{ine, koji bi omogu}io razvoj generalnih tehnika i metoda programirawa paralelnih ma{ina, primjenqivih na najve}em broju sistema. Tako|e, ovakav generalni model bi olak{ao proces standardizacije operativnih sistema i razvojne radne okoline. I pored navedenih argumenata u prilog eksplicitno paralelnog programirawa, MIMD sistemi za sada mogu da, na me|uprocesorskom nivou, efikasno eksploati{u samo krupnozrnasti paralelizam. Za efikasno izvo|ewe ra~unawa po procesnim elementima novijih (RISC baziranih) arhitektura i daqe }e biti od interesa optimalno ure|ewe niza instrukcija u fazi prevo|ewa. 7.4.1 Programski modeli paralelnih ma{ina Robusnost i jednostavnost von-Neuman-ovog modela (sekvencijalnog) ra~unara omogu}io je razvoj generalnih tehnika programirawa, standardizaciju programskih jezika pa i arhitektura i operativnih sistema (UNIX npr.) sekvencijalnih ma{ina. Odgovaraju}a paradigma neophodna je i za paralelne sisteme. U daqem tekstu dat je kratak pregled postoje}ih varijanti. PRAM (Paralel Random Access Machine) model je idealizovana i pojednostavqena predstava paralelnih sistema sa dijeqenom memorijom, gdje svaki procesor u svakom ciklusu izvodi ili jednu elementarnu operaciju, ili ~ita/pi{e iz lokalne ili dijeqene memorije. Razli~ite varijante PRAM modela defini{u pristup memoriji sa vi{e ili mawe restrikcija: kod EREW (Exclusive Read Exclusive Write) PRAM modela nije dozvoqen istovremeni pristup dijeqenoj memoriji od strane razli~itih procesora niti za ~itawe niti za upis. CREW (Concurrent Read Exclusive Write) model dozvoqava istovremeno ~itawe ali ekskluzivan upis, dok CRCW nema ograni~ewa na pristup zajedi~kim lokacijama. Ovakav upro{ten model nije 174 primjenqiv kao generalna platforma za paralelno programirawe, iako omogu}ava dobijawe uvida u strukturu i kompleksnost paralelnog ra~unawa. Model programirawa koji odgovara ovom ma{inskom modelu zasniva se na skupu procesa koji dijele podatke u istom adresnom prostoru, i kojem pristupaju asinhrono. Koordinacija aktivnosti i kontrolisan pristup zajedni~kim resursima, zahtijeva eksplicitno i pa`qivo programirawe i realizuje se sinhronizacionim mehanizmima tipa semafora, monitora i sl. Navedeni koncept ne obezbje|uje u su{tini zahtjeve za modularno programirawe i ne uzima u obzir druge aspekte (lokalnost npr.), veoma zna~ajne za druge modele paralelnih ma{ina. Multira~unar Ovaj model paralelnog sistema je idealizovana predstava MIMD paralelnih sistema i mo`e se predstaviti istom {emom (Sl. 6.14, 6.15). Svaki ra~unar izvodi svoj vlastiti program iz lokalne memorije. Lokalni procesi imaju direktan pristup podacima u lokalnoj memoriji, a komunikacije sa procesima u drugim ra~unarima se ostvaruju slawem i prijemom poruka preko spre`ne mre`e (u op{tem smislu, ovim mehanizmom se ostvaruje pristup udaqenim memorijama, distribuiranim po drugim procesnim elementima). U idealizovanoj mre`i, cijena transfera poruka zavisi samo od du`ine poruke. Bitna karakteristika modela je lokalnost tj. svojstvo sistema da je cijena pristupa lokalnoj memoriji mnogo mawa od cijene pristupa udaqenoj memoriji. Programi razvijeni za ovaj model, mogu se efikasno implementirati i na multiprocesorske sisteme, budu}i da isti podr`avaju komunikacione mehanizme na bazi poruka. Postoji nekoliko modela programirawa koji odra`avaju arhitekturne karakteristike multira~unarskog modela paralelnih sistema. Oni se zasnivaju na prostim apstrakcijama kojima se mogu iskazati konkurentnost, lokalnost/globalnost te mogu}nost pro{irewa i modularnog programirawa. Model zasnovan na zadacima i kanalima se sastoji iz varijabilnog skupa zadataka koji se izvode konkurentno. Zadatak se izvodi u lokalnoj memoriji nekog od procesnih elemenata nad lokalnim podacima. Komunikacija sa zadacima na drugim procesorima se realizuje preko U/I portova, mehanizmom poruka. U/I portovi razli~itih zadataka mogu biti spojeni dinami~ki kreiranim kanalima. Zadaci se mapiraju na procesore; mapirawe ne smije uticati na semantiku programa. 175 Sli~ne su{tinske karakteristike imaju model prosqe|ivawa poruka (message passing model) i objektno orijentisani model u kojem objekti konceptualno odgovaraju zadacima. SPMD (single program multiple data) programski model se reprezentuje jednim programom, koji se izvodi nad disjunktnim skupovima podataka. On odgovara podskupu gore navedenih modela, za slu~aj fiksnog broja identi~nih zadataka koji iste operacije izvode nad razli~itim podacima. Ovaj model je primjenqiv za MIMD arhitekture sa velikim brojem procesnih elemenata. Koncepti ovog modela vodili su razvoju FORTRAN-a 90 i High Performance Fortran-a (HPF). SIMD model paralelnih sistema reprezentuje odgovaraju}u specijalizovanu klasu arhitektura, koja nije pogodna kao generalna platforma za paralelno procesirawe, iako su ovi sistemi izrazito pogodni za rje{avawe dosta {iroke klase specijalizovanih i dobro strukturiranih nau~nih problema. Adekvatan model programirawa za ovaj model arhitektura se zasniva na paralelizmu podataka, koji podrazumijeva mogu}nost fine granularnosti operacija. Programer treba da specifikuje strukture podataka nad kojima se (iste) operacije mogu izvesti paralelno, a prevodilac generi{e odgovaraju}i kod. Ovaj model programirawa pogodan je i za MIMD arhitekture sa velikim brojem procesnih elemenata i regularnom strukturom povezivawa. Kriti~ki osvrt na aktuelne modele programirawa i arhitektura dao je Dennis, uz tvrdwu da nijedan navedeni model ne zadovoqava principe modularnog programirawa (a samim tim ni generalnost programirawa), te da modeli arhitektura ne uzimaju adekvatno u obzir fundamentalna pitawa latentnosti memorije i me|uprocesorske sinhronizacije. Predla`e se generalni semanti~ki model predstavqen na Sl 7.7. Predlo`eni model ima izvori{te u argumentaciji da se koncept modularnosti najpogodnije implementira ako je mogu}e aktivirati funkcije (procedure) uz specifikaciju korektnih parametara, bez obzira na to gdje se funkcije ili argumenti nalazili. Svaki objekat ima jedinstven identifikator (pokaziva~ na objekat). Aktivirawe modula se onda defini{e parom (procedure_pointer, argument_pointer) (argument_pointer se odnosi na strukturu koja sadr`i skup vrijednosti argumenata za proceduru). 176 Stablo aktivacije Aktivnost EP IR Pointer procedure Ofset Okvir Programski DAG x: Z: Varijable okvira Zapisi Tekst n 1 ... n Poqe Heap DAG Sl. 7.7 Generalni semanti~ki model paralelnog procesirawa. Model se sastoji iz 3 komponente (od kojih se svaka mo`e predstaviti acikli~kim orijentisanim grafom). Prvi dio sadr`i kod procedura kojim se defini{u aktivnosti. Svaki luk u grafu indicira poziv neke procedure iz nadre|enog modula. Korespondentni graf je stablo aktivacije, gdje svaki ~vor sadr`i lokalne podatke za aktiviranu proceduru. Tre}i dio je sistemski heap, ~iji ~vorovi reprezentuju strukture podataka, a podre|eni ~vorovi elemente struktura. U ovakvom modelu aktivnost se defini{e parom instrukciona_referenca (IR), pokaziva~_okru`ewa (EP). Instrukciona referenca identifikuje programski modul i instrukciju u modulu, spremnu za izvr{ewe. Pokaziva~ okru`ewa identifikuje aktivaciono stablo pridru`eno programskom modulu. Neka operacija u modelu mo`e da: izvodi lokalna ra~unawa, selektuje slijede}u operaciju na bazi neke lokalne vrijednosti, manipuli{e strukturama na heap-u i inicira ili zavr{i aktivirawe nekog modula. Sistem dopu{ta postojawe vi{e konkurentnih aktivnosti u istom modulu i vi{e instanci jednog modula. Implementacione varijante za koordinaciju aktivnosti su fork i join operacije u nitima, ili uslovi aktivacije po konceptu ma{ina upravqanih podacima. 177 Model nije baziran na nekoj postoje}oj arhitekturi ili tehnologiji, ve} suprotno, ima ambiciju da trasira puteve za projektovawe arhitektura koje }e zadovoqiti fundamentalne zahtjeve za paralelno programirawe. Model tako|e uva`ava fizi~ke limite kapaciteta memorije, fiksnu {irinu rije~i i sl. ali i implementacione aspekte. Vi{enitni koncepti i principi upravqawa na bazi toka podataka se predla`u kao bazni za razvoj arhitektura novih ma{ina. 7.4.2 Projektovawe paralelnih programa Projektovawe i realizacija paralelnih programa je kompleksan zadatak, koji nije mogu}e formalizovati skupom precizno definisanih koraka i postupaka. Stoga je neophodan odre|eni metodolo{ki pristup koji apostrofira razmatrawe bitnih faktora i razli~itih opcija od kojih zavisi kvalitet rje{ewa, i koji obezbje|uje kriterijume za izbor izme|u razli~itih alternativa. Projektovawe paralelnih programa je u uskoj vezi sa algoritamskom podlogom i veoma ~esto zahtijeva prestrukturirawe postoje}eg algoritma ili razvoj adekvatnijeg. Bez obzira na ma{inski ili programski model, rezultat projekta treba da bude skup modula (zadataka) koji obavqaju odre|ena ra~unawa i izme|u kojih postoje precizno definisane interakcije, te wihov raspored po procesnim elementima paralelnog sistema. Naravno, konkurentno izvo|ewe modula raspodjeqenih po procesnim elementima, mora realizovati `eqenu funkciju. Realizacija navedenog ciqa se mo`e ostvariti strukturirawem projektovawa u ~etiri faze: particionisawe, ustanovqavawe veza (komunikacija), ukrupwavawe i mapirawe (Sl. 7.8). U praksi, proces nije strogo sekvencijalan: nezadovoqavaju}e alternative u nekoj fazi mogu implicirati ponovno razmatrawe varijanti u prethodnim fazama. Particionisawe ima za ciq da se cijeli proces izdijeli na {to ve}i broj zadataka izme|u kojih postoji potencijalno velika mogu}nost konkurentnog procesirawa. Zadaci obuhvataju kako ra~unawa (skup operacija) tako i podatke nad kojima se ra~unawa izvode. Dobra podjela implicira ravnomjernu raspodjelu, kako ra~unawa, tako i podataka po zadacima. Osnovne komplementarne tehnike razdiobe su dekompozicija domena (podataka) i funkcionalna dekompozicija. Generalno, zadaci ne treba da sadr`e redundantna ra~unawa ili podatke i, broj zadataka koji se dobijaju dekompozicijom treba da je u proporciji sa veli~inom problema. 178 Zadovoqavawem navedenih principa, dolazi se do rje{ewa sa izra`enom konkurentno{}u i adaptibilno{}u u odnosu na obim problema. Povezivawe je faza u kojoj se ustanovqava zavisnost izme|u zadataka i potrebni transferi (komunikacije) podataka izme|u wih. Za specifikaciju komunikacije potrebno je definisati, kako same podatke koji se izmjewuju odre|enim komunikacionim mehanizmom (porukama npr.), tako i komunikacione veze (kanale) izme|u zadataka. PROBLEM Particionisawe Komunikacija Ukrupwavawe Mapirawe Sl. 7.8 Proces projektovawa paralelnih programa. Komunikacionu strukturu dekomponovanog sistema karakteri{e lokalnost, strukturnost, dinami~nost i sinhronizam. Dobra dekompozicija obezbje|uje da zadaci komuniciraju sa malim skupom susjednih zadataka (lokalnost), tj. obezbje|uje balansiranu dekompoziciju komunikacija, tako da susjedni zadaci formiraju regularnu strukturu. Kod stati~kih komunikacija, svaki zadatak izmjewuje podatke samo sa unaprijed odre|enim zadacima. Za realizaciju sinhronih transfera, zadaci 179 koji su ukqu~eni u transfer moraju da kooperi{u za realizaciju transfera (kod asinhronih transfera slawe/prijem su nezavisni). Komunikacije tako|e treba da imaju mogu}nost konkurentnog izvr{ewa i mogu}nost preklapawa sa ra~unawima. Ykrypwavawe / grupisawe zadataka se vr{i u ciqu smawewa komunikacionih aktivnosti (i vremenskih gubitaka) uz zadr`avawe {to je mogu}e ve}eg iznosa paralelizma. Dodatno, potrebno je odr`ati prilagodqivost (scalability) rje{ewa obimu problema, i prihvatqivu cijenu programske implementacije. U ovoj fazi potrebno je, tako|e, uzeti u obzir implementacione aspekte (broj procesora, na~in komunikacije i sl.). Smawewe odnosa komunikacija/ra~unawe po zadatku, grupisawem susjednih zadataka koji me|usobno komuniciraju u jedan (ve}i) zadatak, zasniva se na efektu odnosa povr{ina i volumena (komunikacioni zahtjevi su proporcionalni povr{ini, a kompjutacioni volumenu pod-domena), tako da se pove}awem pod-domena posti`e `eqeni efekat. Daqe, grupisawe zadataka sa sekvencijalnom zavisno{}u ne smawuje paralelizam, a omogu}ava smawewe iznosa komunikacije (u slu~aju postojawa dovoqnog broja procesnih elemenata). Smawewe komunikacionih gubitaka mo`e se ostvariti i vi{estrukim ponavqawem izvo|ewa istog ra~unawa u razli~itim procesnim elementima. Neki od agoritama za grupisawe datog skupa zadataka, predstavqenog acikli~nim orijentisanim grafom (DAG), koji se baziraju na prethodnim principima, opisani su ukratko u tekstu koji slijedi. Grupisawe po vertikalnim slojevima je metoda koja se bazira na grupisawu sekvencijalnih ~vorova u ve}i ~vor. DAG, koji reprezentuje sistem zadataka, se transformi{e u ekvivalentni graf sa horizontalnim slojevima, tako da je du`ina puta od korijena grafa do svih ~vorova u jednom sloju ista. Zatim se svi ~vorovi koji pripadaju kriti~nom putu grupi{u u jedan ~vor (particiju), ~vorovi iz formirane particije se virtuelno uklawaju iz grafa i postupak ponavqa na preostalom skupu. Grupisawe eliminisawem komunikacionog ka{wewa, se zasniva na grupisawu ~vorova, uz uslov da se ukupno vrijeme izvr{ewa ne produ`ava. Naime, grupisawem susjednih ~vorova (nekog ~vora i wegovih prethodnika/nasqednika) pove}ava se vrijeme ra~unawa, ali se elimini{u vremena komunikacije. Grupisawe se nastavqa dok se ukupno vrijeme izvo|ewa ne pove}ava. Algoritam grupisawa koji se zasniva na vi{estrukom ponavqawu izvo|ewa zadataka smawuje iznos komunikacije izme|u zadataka multiplicirawem izvo|ewa 180 zadatka na vi{e procesnih elemenata (Sl. 7.9). Cijena za smawewe ukupnog vremena izvo|ewa je pove}awe zauze}a memorijskih i procesnih resursa. Vrijeme PE1 PE2 Vrijeme 0 PE1 1 2 PE2 0 1 1 2 3 4 1 1 1 1 2 1 4 1 1 3 1 1 1 1 5 1 1 2 3 4 3 5 3 5 4 2 3 4 a) b) Sl. 7.9 Raspored na dvoprocesorskom sistemu: a) bez duplicirawa zadataka b) sa duplicirawem zadataka. Mapirawe zadataka po procesnim elementima sa ciqem minimizacije funkcije ciqa je, u op{tem slu~aju, kompleksan problem. Ako je funkcija ciqa mininizacija vremena izvo|ewa sistema zadataka na paralelnoj arhitekturi, onda se govori o algoritmima raspore|ivawa (task scheduling algorithms). Za postizawe navedene funkcije ciqa, algoritmi raspore|ivawa se baziraju na strategiji raspore|ivawa konkurentnih zadataka na razli~ite procesore (u ciqu paralelnog izvr{ewa), i na strategiji objediwavawa izvr{ewa zadataka na jednom procesoru, u ciqu smawewa komunikacionih aktivnosti. Kako su navedene strategije opre~ne, algoritmi raspore|ivawa uvijek ukqu~uju kompromis ova dva bazi~na principa. Ako je funkcija ciqa ravnomjerno optere}ewe procesnih elemenata u sistemu, onda se mapirawe zadataka naziva balansirawe optere}ewa (load balancing). U odre|enim slu~ajevima (kada su zadaci me|usobno nezavisni), optimizacija rasporeda optere}ewa rezultuje i optimizacijom vremena izvo|ewa skupa zadataka. 181 7.4.3 Implementacioni mehanizmi Koncept rje{avawa problema paralelnog izvo|ewa skupa zadataka potrebno je izraziti na pogodan na~in u programskom jeziku adekvatnih mogu}nosti. Kompleksnost problema implicira neophodnost modularnog programirawa, tj. izgradwe kompleksnih modula (i na kraju cijelog programa) od komponentnih. U sekvencijalnom programirawu module mo`emo posmatrati kroz funkcije i kroz ulazno/izlazni skup podataka koji je povezan sa izvo|ewem funkcije. Kod paralelnih programa, u razmatrawe treba ukqu~iti tako|e zadatke-aktivnosti koji se generi{u u modulu i wihovo mapirawe na procesore, dekompoziciju podataka po zadacima, te karakteristike komunikacije. U paralelnim sistemima, moduli se mogu na razli~ite na~ine komponovati u programski sistem (Sl. 7.10). Sekvencijalna kompozicija je karakteristi~na za SPMD programe, gdje se isti program izvodi u svim procesnim elementima tako da se razli~ite komponente (moduli) pozivaju i izvode sekvencijalno jedna za drugom. Paralelna kompozicija mapira svaku komponentu na razli~it procesor, uz paralelno izvo|ewe istih. Konkurentna kompozicija omogu}ava konkurentno izvo|ewe razli~itih komponenata na svakom od procesorskih elemenata. Mnogi programski jezici obezbje|uju podr{ku za specifikaciju paralelizma (identifikovanog kroz fazu projektovawa), komunikaciju izme|u zadataka, implementaciju koncepta modularnog programirawa i mapirawe zadataka po procesnim elementima. 182 Sekvencijalna kompozicija modula Paralelna kompozicija Vrijeme Konkurentna kompozicija Sl. 7.10 Varijante kompozicije programa u programski sistem. Sjen~ewem su ozna~ena dva programska modula koji se izvode na ~etiri procesorska elementa. Osnovni koncept paralelnog kodirawa opisao je M.R. Conway (1963), sugeri{u}i par instrukcija (ma{inskog jezika) FORK, JOIN za kreirawe konkurentnih procesa. S obzirom da for petqa ~esto sadr`i nezavisne iteracije, za specifikaciju kreirawa nezavisnih procesa za svaku interaciju koristi se varijanta parallel for instrukcija. Blok strukturiranu konstrukciju predlo`io je Dijkstra ~ija je forma: begin S0 ; cobegin S1; S2; ...., Sn; coend Sn+1 ; end. S0 se izvodi prije (grupa) naredbi S1, S2, ... , Sn, koje se pak mogu izvesti konkurentno. Nakon kompletirawa svih naredbi S1, S2, ... , Sn izvodi se naredba S n +1 . (Analogno ovoj konstrukciji koriste se konstrukcije parbegin-parend). Hoare, na temequ gorwe konstrukcije, defini{e paralelnu komandu za specifikaciju paralelnih procesa: := [ { || }] OCAM jezik, koristi PAR i SEQ naredbe za eksplicitnu specifikaciju paralelnog/sekvencijalnog izvo|ewa. U konkurentnom Pascal-u, defini{u se tipovi i instance procesa; procesi se iniciraju (startuju) init naredbom, a za sinhronizaciju pristupa dijeqenim resursi- 183 ma izme|u procesa koriste se monitori. U ADA programskom jeziku paralelni procesi se specifikuju preko TASK konstrukcije. Svaki task ima svoju deklaraciju i definiciju. Instance task-ova se kreiraju i aktiviraju pozivom procedura u kojima su definisani. Komunikacija izme|u task-ova se realizuje ili mehanizmom randevua ili preko dijeqenih varijabli. Pored ovih osnovnih konstrukcija za podr{ku paralelnom procesirawu, kojima se omogu}ava eksplicitna specifikacija paralelizma, savremeni paralelni programski jezici sadr`e i druge konstrukcije za podr{ku. CC++ (Compositional C++) je ekstenzija standardnog C++ jezika, koji pored apstrakcija "procesorski objekat" i "globalni pokaziva~" pomenutih u dijelu 7.1. ima i apstrakcije "thread", "sync variable", "atomic function" i "transfer functions". Niti (threads) se kreiraju i izvode u okviru procesorskog objekta. Inicijalno, program se izvodi sa jednom niti kotrole; vi{estruke niti se kreiraju pomo}u par, parfor i spawn naredbi. Dok se niti formirane sa par i parfor ne kompletiraju, ne mo`e se izvesti slijede}a aktivnost. Spawn dozvoqava kreirawe nezavisnih niti. Ovim konstrukcijama se implementira koncept konkurentnog izvr{ewa, a procesorska apstrakcija implementira koncept lokalnosti. Niti se izvode (podrazumijevaju}e) u procesorskom objektu u kojem su kreirane. Na~in komunikacije i sinhronizacije izme|u niti je pomenut prethodno. Za sinhronizaciju ~itawa/upisa iz dijeqene varijable koristi se modifikator sync u deklaraciji dijeqene varijable. (Ako nit ~ita iz sync varijable u koju vrijednost nije upisana, ona se blokira dok vrijednost ne bude upisana). Modifikator atomic omogu}ava implementaciju kriti~nih sekcija: dvije atomic funkcije istog objekta ne mogu se izvesti istovremeno. Transfer podataka proizvoqnog tipa izme|u procesorskih objekata se realizuje transfer funkcijama. Mapirawe na fizi~ke procesore se realizuje tako da se niti mapiraju na procesorske objekte, a procesorski objekti na fizi~ke procesore. Za definisawe fizi~ke lokacije procesorskih objekata, koriste se konstruktorske funkcije (proct i node-t). FORTRAN M je ekstenzija standardnog FORTRAN-a 77. Omogu}ava eksplicitnu specifikaciju zadataka i wihovog paralelnog izvr{ewa, kanala, slawa i prijema poruka te mapirawa na virtuelnu ma{inu. Procesi se deklari{u istom sintaksnom konstrukcijom kao i potprogrami, s tim da se koristi kqu~na rije~ PROCESS umjesto SUBROUTINE. Procesi koji se 184 pozivaju u bloku PROCESSES/ENDPROCESSES se aktiviraju za konkurentno izvr{ewe. Petqom PROCESSDO/ENDPROCESSDO se kreiraju vi{estruke instance istog procesa. Za komunikaciju izme|u procesa kreiraju se kanali (konstrukcijom CHANNEL) sa ulaznim i izlaznim vratima(portom). Procesi koji imaju adrese ulaznih/izlaznih vrata (up/ip) otvorenog kanala mogu da komuniciraju primitivama SEND(ip) i RECEIVE(up). MERGER je kanal koji omogu}ava komunikaciju tipa mnogina-jedan. Navedeni koncept kanala omogu}ava kreirawe dinami~ke strukture kanala i povezivawe tipa mnogi-na-mnogi, te implementaciju sinhrone/asinhrone komunikacije. Za specifikaciju virtuelnog ra~unara sa strukturom procesora u n dimenzija, koristi se direktiva PROCESSORS (I1, I2, ... , In). LOCATION (I1, I2, ... , In) direktiva specifikuje elemenat u vi{edimenzionalnoj strukturi procesora, na kojem se proces izvodi. SUBMACHINE konstrukcija, omogu}ava mapirawe procesa na podskup procesora virtuelne ma{ine. FORTRAN 90 i wegova ekstenzija HPF (High Performance Fortran) su jezici koji eksploataciju paralelizma baziraju na paralelizmu koji se dobija primjenom istih operacija na razli~itim segmentima nekog skupa podataka (ovaj tip paralelizma se ozna~ava terminom paralelizam podataka (data parallelism)). Strukture podataka podr`ane u navedenim jezicima za ovakav tip eksploatacije paralelizma su nizovi podataka. Ako su A, B, C nizovi, onda A = B * C prevodilac automatski prepoznaje kao operaciju sa paralelizmom podataka. Prevodilac tako|e poku{ava automatski detektovati paralelizam u programskim petqama. Prevodilac transformi{e program u SPMD formu, gdje vi{e procesora izvode isti program nad razli~itim segmentima podataka. Ako izvo|ewe na nekom procesoru zahtijeva komunikaciju sa drugim procesorom, u ciqu dobijawa podataka iz susjednog poddomena, u fazi prevo|ewa se automatski ume}u potrebni mehanizmi. PROCESSORS direktiva omogu}ava deklaraciju organizacije virtuelnih procesora (uobi~ajeno se deklari{e jedan apstraktni za jedan fizi~ki procesor). DISTRIBUTE direktiva se koristi za specifikaciju domena po virtuelnim procesorima. Pored toga {to se konkurentnost eksploati{e direktno iz operacija nad poqima, paralelne operacije se iniciraju FORALL (triplet, triplet, ... , triplet, mask) assignment naredbom pridjeqivawa, gdje se paralelno izvode sve naredbe pridjeqivawa sa indeksima definisanim tripletima, pod uslovima da je mask izraz istinit. Za eksplicitnu specifikaciju nezavisnosti iteracija petqe koristi se direktiva INDEPENDENT. 185 Pored navedenih paralelnih jezika, postoje i drugi paralelni programski jezici: paralelni logi~ki jezici (Multilisp, Concurrent Prolog i sl.) i paralelni funcionalni jezici (VAL, SISAL, ID, npr.). Funkcionalni jezici ne dozvoqavaju operacije koje mogu proizvesti grani~ne (side) efekte; funkcije ne mogu mijewati vrijednost varijabli koje nisu lokalne, a ulazno/izlazni parametri mogu biti samo vrijednosti, a ne reference. Pridjeqivawe nekoj varijabli dozvoqeno je samo jedanput, tako da se zavisnost po podacima veoma jednostavno identifikuje, naravno uz cijenu znatno ve}ih memorijskih zahtjeva. 7.5 Operativni sistemi Da bi ostvarili generalne zahtjeve koji se postavqaju pred operativne sisteme kao {to su: obezbje|ewe programskog interfejsa prema ma{ini, upravqawe resursima, sinhronizacija svih aktivnosti i mehanizama za implementaciju korisni~kih koncepata visokog nivoa, aspekti neosjetqivosti na gre{ke itd. operativni sistemi paralelnih ma{ina moraju uzeti u obzir i specifi~ne arhitekturne karakteristike kao i specifi~nosti koncepata paralelnog programirawa. Navedeni elementi otvaraju niz dodatnih dilema, ne samo u pogledu funkcija nego i same organizacije operativnih sistema. Centralizovana organizacija se koristi uglavnom kod paralelnih ma{ina sa dijeqenom memorijom, sa dvije varijante: (prva) master-slave, gdje jedan procesor izvodi rutine operativnog sistema i dijeli posao "podre|enim" procesorima, i druga, gdje su procesori ravnopravni i istovremeno mogu da izvr{avaju rutine (jedinstvenog) operativnog sistema. U distribuiranoj varijanti koja se koristi kod multira~unarskih sistema, operativni sistem je jedinstven, ali fizi~ki distribuiran po procesnim elementima. Svaki procesni element preko lokalnog (mikro) jezgra operativnog sistema obezbje|uje servise lokalnim procesima, ali obezbje|uje i spregu sa ostalim procesorima kako u ciqu kooperativnog procesirawa tako i u ciqu obezbje|ewa pristupa i kori{tewa zajedni~kih resursa: U/I podsistema, sistema datoteka, dijeqenih objekata i funkcija i sl. U ciqu efikasne eksploatacije paralelizma u okviru jednog procesa, savremeni operativni sistemi moraju da podr`e koncept konkurentnog izvo|ewa vi{estrukih niti. Sve aktivirane niti mogu da se izvode paralelno pod uslovom raspolo`ivosti 186 procesorskih resursa. Iako postoji vi{e varijanti naj~e{}e se koristi implementacija niti kao "laganih" procesa. U takvoj varijanti, sve niti generisane u okviru jednog procesa dijele najve}i dio konteksta tog procesa: kod, stati~ke i globalne podatke, heap, i sve atribute procesa kojima manipuli{e jezgro operativnog sistema (identifikator vlasnika, deskriptore otvorenih datoteka i sl.). Privatni konteksti niti minimalno sadr`e stawe registara, identifikator i prioritet niti. Rudimentarni kontekst niti omogu}ava brzu promjenu konteksta, odnosno prelaz izvo|ewa sa jedne niti na drugu. Kernel ne u~estvuje u kreirawu, aktivirawu, sinhronizaciji i ga{ewu niti. Ove funkcije se standardno realizuju bibliotekom izvo|ewa. Varijante niti koje raspore|uje jezgro operativnog sistema, nazivaju se "te{ke" niti (heavy weight threads). Dakle, arhitekture paralelnih sistema i principi paralelnog programirawa imali su presudan uticaj na evoluciju operativnih sistema u pravcu obezbje|ewa podr{ke za rad u navedenom okru`ewu; specijalno kroz koncepte mikrokernela (mikrojezgra) operativnog sistema, vi{enitnog izvo|ewa, memorijski mapiranih datoteka, aktivirawa funkcija na udaqenim procesorima i sl. Za ilustraciju, operativni sistem Intel Paragon ra~unara je multira~unarski UNIX, sa podr{kom za vi{enitno izvo|ewe, konceptom virtuelne memorije i strani~ewa, mogu}no{}u mapirawa korisni~kih procesa na jedan ili vi{e procesora. Operativni sistem ima jedinstvene sistemske strukture i distribuirano upravqawe procesima. Struktura programskog sistema u svakom procesnom elementu data je na Sl. 7.11. Sistem koristi Mach mikrokernel, razvijen na Carnegie-Mellon univerzitetu, OSF/1 Unix server i NX-protokol za prosqe|ivawe poruka. Funkcije mikrokernela su upravqawe procesima i nitima, komunikacija izme|u procesa, upravqawe virtuelnom memorijom i upravqawe ure|ajima. Server obezbje|uje podr{ku za mre`nu komunikaciju i pristup datotekama. sistemskih funkcija za implementaciju vi{enitnog koncepta 187 korisni~ki proces Mach 3.0 mikrokernel NX server OSF/1 UNIX sa multikorisni~kim pro{irewima kernel NX aplikacioni interfejs API hardver Sl. 7.11 Intel Paragon OSF/1 arhitektura. 7.6 Razvojno okru`ewe Te{ko}e u razvoju softvera, iskazane terminom "softverska kriza" jo{ 1968 (Int.Cont. on Software engineering, Garmish) forsirale su stvarawe metodologija i tehnika za razvoj softvera, ali i odgovaraju}ih sredstava za primjenu istih, odnosno odgovaraju}eg razvojnog okru`ewa. S obzirom na nagla{enu kompleksnost paralelnog programirawa, takvo okru`ewe se pojavquje kao imperativ. Pored programskih jezika (opisanih u prethodnom dijelu), razvojno okru`ewe ~ine sredstva za konstrukciju programa, analizu i izbor odgovaraju}ih varijanti raspore|ivawa, instrumentalizaciju i testirawe/verifikaciju. Sredstva za konstrukciju u naj{irem smislu sadr`e alate za analizu, specifikaciju, projektovawe, kodirawe aplikacija, vo|ewe projekta i sl. Primjeri su programski paketi za strukturno ili objektno orijentisanu analizu i projektovawe, formalni jezici za specifikaciju zahtjeva i algoritama rje{ewa, sintaksnosemanti~ki orijentisani procesori teksta, paketi za upravqawe i vo|ewe projekta i sl. Alati za raspore|ivawe zadataka u vi{eprocesorskom sistemu dobili su adekvatnu pa`wu tek u posqedwe vrijeme. Ovi alati poma`u korisniku u procesu particionisawa problema na skup zadataka te pri raspore|ivawu zadataka po procesnim elementima date arhitekture. Ovi alati moraju imati jednostavan, grafi~ki orijentisan interfejs prema korisniku. Razli~ite implementacije sadr`e razli~ite varijacije komponentnih alata opisanih u tekstu koji slijedi. 188 Alat za specifikaciju aplikacija omogu}ava prezentaciju aplikacija u grafi~koj formi (obi~no u formi orijentisanog acikli~kog grafa). Ova predstava se koristi u fazi particionisawa i raspore|ivawa sistema zadataka. Kreirawe grafi~ke ekvivalentne forme programa mogu}e je automatskom transformacijom iz izvornog programa (PARSA). Odre|eni alati koriste specijalni kod za izra`avawe paralelizma u programu i specifikaciju wegove strukture (OREGAMI), a neki alati zahtijevaju od korisnika specifikaciju programa u formi grafa. Obi~no, grafi~ka reprezentacija zahtijeva i specifikaciju procjene izvo|ewa pojedinih aktivnosti predstavqenih u grafu. Alat za particionisawe omogu}ava transformaciju grafa u ekvivalentnu formu u ciqu smawewa me|uprocesorske komunikacije. Alat za raspore|ivawe omogu}ava mapirawe zadataka na arhitekturu, na osnovu odre|enog algoritma. Arhitektura i algoritmi raspore|ivawa mogu biti fiksni ili korisnik mo`e vr{iti selekciju na osnovu vi{e mogu}ih opcija, ili ~ak implementirati vlastite opcije. U sklopu ovog modula (ili kao poseban modul) realizuje se vizuelni prikaz performansi programa pri izvo|ewu na simuliranoj ili stvarnoj arhitekturi. Vizuelizacija obi~no ukqu~uje prikaz aktivirawa procesa i stawa procesora u toku izvo|ewa, komunikacije podataka, te parametre kao {to su ubrzawe, iskori{tewe procesora, ukupno vrijeme izvr{ewa i sl. Testirawe aplikacija u paralelnim sistemima ne ukqu~uje samo verifikaciju korektnosti nego i eksperimentisawe sa vi{estrukim parametarskim opcijama u ciqu postizawa efikasne implementacije. Prvi korak u sferi eksperimentisawa je instrumentalizacija: registrovawe, mjerewe, akvizicija i analiza podataka i doga|aja. U praksi se koriste razli~ita sredstva instrumentalizacije: softverski, hardverski, hibridni, mre`ni monitori; prirodni i sinteti~ki generatori optere}ewa; softverski alati za analizu strukture podataka i sl. Primjer implementacije okru`ewa za instrumentalizaciju je IIE (Integrated Instrumentation Environment for Multiprocessors [108]), razvijen na Carnegie Mellon univerzitetu (Sl. 7.12). 189 Menaxer {ema Kontroler pobuda Baza pod. Instrumentalizovana pobuda Relacioni monitor Rezidentni monitor Instrumentalizovani OS Sl. 7.12 IIE Programsko okru`ewe. IEE se zasniva na konceptu integracije vi{e instrumentalnih sredstava u jedinstveno okru`ewe za upravqawe eksperimentima. Za definisawe skupa mogu}ih eksperimenata defini{e se {ema eksperimenta, a konkretni eksperiment predstavqa instancu {eme. Menaxer {eme, na osnovu definisane {eme (eksperimenta) i podataka o stawu okoline, daje potrebne informacije za generisawe ulaznih vrijednosti u pojedinim ta~kama programa u toku eksperimenata. Rezidentni monitor u koordinaciji sa operativnim sistemom, vr{i registrovawe i mjerewe podataka i veli~ina od interesa, koji se preko menaxera eksperimenata zapisuju u bazu eksperimenata za kasniju analizu. Pored navedenih, mnogi drugi projekti bavili su se razvojem okru`ewa za programirawe u paralelnim sistemima: • Spice projekt (CMU), sa ciqem konstrukcije programskog i radnog okru`ewa za nau~na istra`ivawa na mre`i ra~unara, • PRESTO je sistem za objektno-orijentisano (C++ bazirano) programirawe u multiprocesorskom (Sequent Balance) okru`ewu, • Argus projekat (MIT), predmet istra`ivawa je okru`ewe za analizu dinami~ke varijacije paralelnog softvera. • ISSOS projekat (PARTS Labs, Ohio) se bavi razvojem jezi~kih primitiva i programskog sistema koji podr`ava razvoj i eksperimentisawe te pode{avawe paralelnih programa, 190 • i drugi (Gypsy projekat (Texas/Austin), Cedar (Xerox Parc), SARA (UCLA) itd.). 7.7 Ostali aspekti Ostali aspekti programirawa paralelnih sistema ukqu~uju aspekte pouzdanosti/(ne)osjetqivosti na gre{ke, programirawa u stvarnom vremenu, standardizacije (CORBA standard npr.) i sl. Za odre|enu klasu aplikacija (vojni sistemi, upravqawe hemijskim i nuklearnim procesima, elektroenergetski sistemi, komunikacioni sistemi i sl.), pouzdanost sistema je faktor od osnovnog zna~aja. U ciqu obezbje|ewa ve}e pouzdanosti i raspolo`ivosti sistema moraju postojati dodatni hardverski i programski moduli (dijagnosti~ki podsistem), koji mogu detektovati pojavu otkaza u sistemu i prebaciti funkcije sa elementa koji je otkazao na ispravan modul. Neosjetqivost na gre{ke (fault tolerance) je tako|e va`na karakteristika spre`nih mre`a. Fault tolerance parametar f spre`ne mre`e se defini{e kao broj ~vorova koje je mogu}e ukloniti iz mre`e, a da mre`a i daqe bude povezana (tj. da nijedan ~vor ne postaje izolovan). Drugi va`an parametar je dijametar mre`e u slu~aju otkaza (fault diameter) d nf - maksimalni dijametar koji se dobija uklawawem iz spre`ne mre`e f ~vorova. 8 Raspore|ivawe zadataka na procesore u vi{eprocesorskim sistemima 8.1 Uvod i generalna specifikacija problema raspore|ivawa Teorija raspore|ivawa tretira {irok spektar problema iz domena upravqawa resursima, domena elektro-in`iwerstva, primijewene matematike i ra~unarske tehnike. Jednu klasu problema ~ini raspore|ivawe m poslova Ji , i = 1, ... ,m za procesirawe na n ma{ina Mj, j = 1, ... ,n. Raspored za svaki posao Ji je pridjeqivawe jednog ili vi{e intervala vremena za taj posao na jednoj ili vi{e ma{ina. Raspored je vaqan, ako nema preklapawa intervala pridjeqivawa na jednoj ma{ini, niti preklapawa intervala pridjeqenih jednom poslu, te ako su ispuweni drugi zahtjevi specifi~ni za odre|eni problem. Rasporedi procesirawa mogu se predstaviti Gantt-ovim dijagramima (Sl 8.1). Svaki posao Ji se sastoji od operacija Oi1, Oi2, ... , Oi,ni , a svaka operacija Oij ima procesne zahtjeve pij. Tako|e, svakoj operaciji Oij je pridru`en podskup µ ij skupa M ma{ina, na kojima se Oij mo`e izvoditi. Uz poslove mogu biti pridru`eni i vrijeme lansirawa ri (najranije vrijeme kada je prva operacija raspolo`iva za izvo|ewe), krajwe vrijeme zavr{etka posla di, te funkcija fi(t) koja specifikuje cijenu ako se posao Ji zavr{i u vremenskom trenutku t. 8.1 Uvod i generalna specifikacija problema raspore|ivawa Op{ti problem ove klase se specifikuje u formi ristike ma{ina, β karakteristike poslova, a 192 reprezentuje karakte- α /β /γ , gdje α γ kriterijum optimalnosti. α , β i γ su defi- nisani nizovi karaktera i wihove kombinacije, kojima se izra`avaju razli~ite mogu}e karakteristike poslova, ma{ina i ciqnih funkcija. Kod generalnog modela raspore|ivawa (general job shop), izme|u bilo kojih operacija Oij posla Ji mogu postojati relacije pretho|ewa. Svaka operacija se izvodi na namjenskoj ma{ini (svi µ ij su skupovi od jednog elementa). Specijalni slu~ajevi su job shop, flow shop, open shop i mixed shop. Relacije pretho|ewa izme|u operacija kod job shop problema su u formi U op{tem slu~aju je µ i j ≠ µ i, j+1. Oi 1 → Oi 2 → ... → Oi,ni i = 1, ... , m. J3 J2 J1 J3 J1 J4 J3 J1 J4 Sl. 8.1 Gantt-ov dijagram. Flow shop je specijalni slu~aj job shop problema, kada je broj operacija u svakom poslu jednak broju ma{ina, i svaka operacija Oij se izvodi na ma{ini Mj. Open shop se defini{e kao flow shop, s tim da izme|u operacija ne postoje relacije pretho|ewa. Mixed shop je kombinacija job shop i open shop problema. Ako je Ci vrijeme zavr{etka posla Ji , onda se vrijednosti Ci pridjequje vrijednost funkcije fi (Ci) koja reprezentuje cijenu zavr{etka posla Ji u trenutku Ci. Neke od funkcija fi su: MSPi = Ci Li = Ci – di Ei = max (0, di – Ci) Ti = max (0, Ci – di) (raspon izvo|ewa(makespan)) (ka{wewe(lateness)) (ranije izvr{ewe(earliness)) (kasnije izvr{ewe(tardiness)) Na bazi funkcije fi (ili kombinacije ovakvih funkcija), na razli~ite na~ine se mo`e definisati ciq-funkcija ukupne cijene, npr. γ = max{ fi }, γ = max { ϖ i * f i }, γ = ∑ fi , γ= ∑ϖ i f i , gdje je ϖ i te`inski faktor. Ciq odre|ivawa rasporeda je da se na|e vaqan raspored koji minimizuje ukupnu cijenu izvo|ewa n poslova na m ma{ina. Drugu klasu problema ~ini projektno raspore|ivawe (project scheduling). Kod ovih problema projekt se reprezentuje mre`om zadataka izme|u kojih postoje relacije Raspore|ivawe zadataka na procesore 193 pretho|ewa. Najpoznatije tehnike projektnog raspore|ivawa su metod kriti~nog puta (CPM) i tehnike procjewivawa i revizije projekta (PERT). Ciq ovih tehnika je minimizacija vremena zavr{etka projekta kao i identifikacija kriti~nih puteva realizacije. CPM metod najprije za svaki zadatak sra~unava najranije mogu}e vrijeme po~etka EST(Ti) = max{EST(Tj ) + τ j} gdje je Tj neposredni prethodnik zadatka Ti, a τ j je wegovo trajawe. Procedura se primjewuje od po~etnog zadatka (startno vrijeme = 0) pa do zavr{nog. Analogno tome, za svaki zadatak sra~unava se najkasnije vrijeme po~etka (polaze}i od zavr{nog zadatka za koji se uzima da je najkasnije vrijeme po~etka izvr{ewa jednako najranijem), na osnovu izraza: LST(Ti) = min {LST (Tj) – τ i} , Tj ∈ SUCC(Ti). Na osnovu ova dva vremena, svakom zadatku se pridjequje raspon kao razlika najkasnijeg i najranijeg vremena po~etka realizacije. Ovaj raspon reprezentuje vremenski opseg u kojem se mo`e zapo~eti izvr{ewe zadatka, a da se ukupno vrijeme trajawa projekta ne produ`i. Za zadatke koji imaju raspon po~etka realizacije jednak nuli, ka`e se da le`e na kriti~nom putu. Svako ka{wewe izvo|ewa zadataka na kriti~nom putu ima za posqedicu i ka{wewe realizacije cijelog projekta. PERT metoda je u osnovi ekstenzija CPM tehnike, s tim da se bazira na specifikaciji najvjerovatnijeg, optimisti~kog i pesimisti~kog trajawa zadatka. Metoda daje probabilisti~ku procjenu optimisti~kog, o~ekivanog i pesimisti~kog trajawa projekta. Implicite se podrazumijeva da za realizaciju projekta broj potrebnih resursa nije ograni~en. Problem raspore|ivawa izvo|ewa zadataka u vi{eprocesorskim sistemima je izuzetno intenzivno analiziran i istra`ivan. Formulacija problema je jednostavna: kako mapirati skup zadataka T = {Ti}, i = 1, ... , m izme|u kojih mogu da postoje ograni~ewa pretho|ewa, na skup procesora {Pk}, k = 1, ... , n tako da se ostvari `eqena funkcija ciqa (npr. minimalno vrijeme zavr{etka izvo|ewa cijelog skupa). Ograni~ewa pretho|ewa se specifikuju DAGom (orijentisanim acikli~kim grafom) G = {T, A}, gdje je T skup zadataka(~vorova) a A = {Aij} skup orijentisanih lukova. Ako je orijentisani luk Aij ∈ A, onda on reprezentuje ograni~ewe da zadatak Tj mo`e po~eti izvr{ewe samo nakon zavr{etka izvo|ewa zadatka Ti. Ti je neposredni prethodnik zadatka Tj, a Tj je neposredni nasqednik zadatka Ti. Svaki zadatak Ti karakteri{e potrebno vrijeme (cijena) procesirawa. Ako su svi procesori identi~ni (homegeni vi{eprocesorski sistem) onda je cijena procesirawa zadatka Ti identi~na na svim procesorima. U heterogenim sistemima, cijena izvo|ewa zadatka Ti na procesoru Pj se specifikuje elementom (matrice) τ ij, i = 1, ... , m, j = 1, ... , n. Svaki orijentisani luk Aij ∈ A ima te`inu Dij, koja reprezentuje koli~inu podataka koji se izmjewuju izme|u zadataka Ti i Tj. Odgovaraju}a cijena komunikacije je 0, ako se zadaci Ti i Tj izvode na istom procesoru, a Cij u suprotnom. 8.1 Uvod i generalna specifikacija problema raspore|ivawa 194 Funkcija raspore|ivawa se mo`e posmatrati i kao resurs za upravqawe resursima, a Raspore|iva~ Potro{a~ Politika/ strategija Resursi osnovna struktura procesa se mo`e prikazati slikom Sl 8.2. Sl. 8.2 Sistem za raspore|ivawe. Raspore|ivawe se mo`e posmatrati i ocjewivati sa stanovi{ta uticaja strategije na potro{a~e i/ili resurse. Zahtjev sa stanovi{ta potro{a~a je da raspore|ivawe resursa bude "kvalitetno" (odnosno da su performanse raspore|ivawa dobre), i da bude efikasno (tj. da kompleksnost strategije ne generi{e veliko re`ijsko vrijeme). U navedenoj predstavi, potro{a~i su procesi a resursi procesori. Raspore|ivawe (zadataka) i alokacija (resursa/procesora) su termini koji se ~esto koriste za opis istog mehanizma sa stanovi{ta potro{a~a/resursa. Za razliku od projektnog raspore|ivawa, raspore|ivawe u vi{eprocesorskim sistemima generalno podrazumijeva ograni~ene procesorske i druge resurse, a mo`e da sadr`i i niz drugih specifi~nih karakteristika (topologija povezivawa procesora, komunikaciona ka{wewa, heterogenost, zahtjevi za obradu u stvarnom vremenu i sl.). Metode za rje{avawe navedenog problema mogu se klasifikovati prema Sl. 8.3 . Lokalno raspore|ivawe se odnosi na klasi~no raspore|ivawe procesa koje realizuje operativni sistem na jednom (lokalnom) procesoru, i koje se sastoji iz pridjeqivawa procesora nekom zadatku (procesu) u odre|enom vremenskom intervalu. Globalno raspore|ivawe se odnosi na odlu~ivawe o lokaciji, odnosno procesorskom resursu za izvo|ewe zadatka u vi{eprocesorskom sistemu, i mo`e se klasifikovati u dve grupe: metode za stati~ko i metode za dinami~ko raspore|ivawe. Kod stati~kog raspore|ivawa, pridjeqivawe zadataka procesorskim elementima vr{i se u fazi prevo|ewa programa, i bazira se na pretpostavqenim vrijednostima vremena izvr{ewa zadataka i komunikacionih ka{wewa izme|u procesora. Tehnike dinami~kog raspore|ivawa odluku o (pre)alokaciji donose u fazi izvo|ewa. Pod pretpostavkom da su procjene trajawa izvo|ewa zadataka i komunikacionih ka{wewa ta~ne u fazi prevo|ewa, odre|ivawe rasporeda mo`e biti optimalno ili podoptimalno. Optimalno raspore|ivawe podrazumijeva pretra`ivawe cijelog prostora rje{ewa i poznato je kao ra~unski kompleksan problem (eksponencijalne kompleksnosti). Broj koraka za nala`ewe optimalnog rje{ewa se mo`e redukovati kori{tewem Raspore|ivawe zadataka na procesore 195 tehnike "granaj i ograni~i" (branch and bound), kojom se na bazi procjene granica optimalnog rje{ewa odbacuje (preska~e) tra`ewe rje{ewa u oblasti za koju je izvjesno da ne sadr`i optimum. lokalno globalno stati~ko dinami~ko optimalno podoptimalno distribuir. ne-distribuir. aproksimativno heuristi~ko kooperativno ne-kooperativno optimalno podoptimalno “nabrajawem” graf – matem. teoretsko program. na bazi teorije poslu`ivawa aproksimativno heuristi~ko Sl. 8.3 Klasifikacija metoda raspore|ivawa (Casavant 1988). Druga grupa metoda stati~kog raspore|ivawa produkuje rje{ewa koja nisu optimalna, ali su "dovoqno dobra", odnosno blizu optimalnog rje{ewa, uz prihvatqivu (polinomsku) kompleksnost. Aproksimativni algoritmi pretra`uju prostor rje{ewa dok algoritam na bazi odre|enog kriterijuma ne zakqu~i da je rje{ewe dovoqno dobro. Aproksimativni i optimalni algoritmi mogu se zasnivati na metodama "nabrajawa" (enumerative), teoriji grafova, teoriji poslu`ivawa ili matemati~kom programirawu. Metode za dinami~ko raspore|ivawe zadataka polaze od (realnije) pretpostavke da se naj~e{}e vrijeme izvo|ewa zadataka i drugi uslovi ne mogu kvalitetno procijeniti u fazi prevo|ewa, dakle odlu~ivawe se mora realizovati u toku izvo|ewa. Ako se odlu~ivawe vr{i na jednom mjestu, onda se radi o centralizovanom (ne-distribuiranom) raspore|ivawu, a u suprotnom o distribuiranom raspore|ivawu. Ako je odlu~ivawe o raspore|ivawu zadataka distribuirano na razli~ite procesore, onda procesori prilikom odlu~ivawa mogu me|usobno da kooperi{u ili ne. Kooperativno raspore|ivawe mo`e biti optimalno ili podoptimalno, sa karakteristikama opisanim za 8.2 Kompleksnost raspore|ivawa 196 stati~ko raspore|ivawe. Pored ove, hijerarhijske klasifikacije metoda raspore|ivawa, postoje i druge specifi~ne karakteristike koje pojedine metode iz navedene hijerarhije mogu imati. Adaptivni algoritmi koriste informacije o stawu sistema za dono{ewe odluka, dok ne-adaptivni odlu~ivawe vr{e na bazi fiksnog modela ili na bazi fiksne distrubicije vjerovatno}a pojedinih varijanti odlu~ivawa. Dinami~ko raspore|ivawe mo`e u fazi izvo|ewa alocirati zadatak procesoru sa ili bez mogu}nosti prealocirawa. Metode za balansirawe optere}ewa karakteri{e dinami~ka preraspodjela optere}ewa izme|u procesora sa ciqem da se ostvari boqe iskori{tewe resursa i vrijeme odziva. Raspore|ivawe sa preuzimawem polazi od pretpostavke da zadatak mo`e biti prekinut u toku izvo|ewa, uz dodjelu procesora drugom zadatku, i nastavqawe i kompletirawe prekinutog zadatka u nekom kasnijem trenutku. Pri raspore|ivawu bez preuzimawa, bilo koji zadatak ~ije je izvr{ewe zapo~eto na nekom procesoru izvr{ava se neprekidno do kompletirawa izvo|ewa. Heuristi~ki algoritmi se baziraju na parametrima koji su u korelaciji sa funkcijom ciqa koja se `eli optimizovati. Ovi parametri se koriste za specifikaciju heuristi~ke funkcije, na osnovu koje se donosi odluka o raspore|ivawu. Navedena taksonomija pokazuje raznovrsnost i kompleksnost problematike, iako mnogi algoritmi sadr`e specifi~nosti koje nisu obuhva}ene navedenom klasifikacijom (raspore|ivawe zadataka koje karakteri{u zahtjevi za izvo|ewe u stvarnom vremenu, npr.). 8.2 Kompleksnost raspore|ivawa Kqu~na karakteristika algoritama za raspore|ivawe zadataka je wihova kompleksnost, odnosno vrijeme koje je potrebno za nala`ewe rje{ewa. Sa ovog stanovi{ta, neki algoritmi su efikasni, a neki ne. O~igledno, ova konstatacija je veoma uop{tena, i potrebno je dati precizniju kvalifikaciju ove karakteristike algoritama. Algoritam (u op{tem smislu) ~ini kona~na sekvenca preciznih instrukcija kojima se dolazi do rje{ewa problema. Problem Q predstavqa relaciju na skupu X instanci problema i skupu S rje{ewa problema. Vrijeme sra~unavawa rje{ewa algoritmom je obi~no funkcija "veli~ine" problema, koja se mo`e reprezentovati odre|enom karakteristikom ulazne veli~ine u problem - instance problema x ∈ X: npr. broj jedna~ina/nepoznatih za problem rje{avawa sistema linearnih jedna~ina, broj zadataka kod problema raspore|ivawa na vi{eprocesorski sistem, ili broj elemenata u nizu za probleme sortirawa. Dakle, ulaz se mo`e na odre|eni na~in kvantifikovati wegovom veli~inom ili du`inom, od koje zavisi vrijeme trajawa Raspore|ivawe zadataka na procesore 197 algoritma. Da bi se procijenilo vrijeme trajawa algoritma, od interesa je odre|ivawe gorwe granice broja koraka koje je potrebno izvesti L(n) u zavisnosti od veli~ine obima problema n = | x |. Umjesto preciznog izraza za L(n) naj~e{}e se posmatra aproksimacija granice: ka`e se da je gorwa granica L(n) algoritma reda O(g(n)), ako postoje konstante C i n0 takve da je L(n) ≤ C * g(n) za ∀n ≥ n 0 . Problem je rje{iv u polinomskom vremenu, ako postoji polinom p takav da je gorwa granica algoritma O (p(n)). Problemi koji imaju opseg rje{ewa {da, ne} spadaju u grupu problema odlu~ivawa. Ovi problemi se mogu smatrati funkcijama koje svaku instancu x problema mapiraju na Q(x) ∈ {da,ne}. Za probleme odlu~ivawa koji su rje{ivi u polinomskom vremenu ka`e se da spadaju u klasu P . Problemi raspore|ivawa se mogu formulisati kao problemi odlu~ivawa, npr. o tome da li se dati skup zadataka reprezentovan sa G = {T,A}, mo`e rasporediti na skup procesora {Pk}, tako da je raspon izvo|ewa ≤ K. Rje{ewe sa vrijedno{}u "da" se mo`e specifikovati sertifikatom; npr "raspored s je mogu}, sa rasponom ≤ K", gdje s specifikuje konkretan raspored. U op{tem slu~aju, sa N P se ozna~ava klasa problema odlu~ivawa, tako da svako rje{ewe sa odgovorom "da" za neko x ima sertifikat y, pri ~emu je | y | ograni~eno polinomski u zavisnosti od | x |, i da postoji algoritam koji verifikuje u polinomskom vremenu da je y vaqan sertifikat za x. Svaki problem odlu~ivawa koji je rje{iv u polinomskom vremenu pripada skupu N P problema, odnosno P ⊆ N P (ako za neki problem odlu~ivawa postoji algoritam koji za svaki x sra~unava u polinomskom vremenu odgovor Q(x) ∈ {da, ne}, onda se (polinomski) algoritam kojim se rje{ava problem mo`e lako konvertovati u algoritam za verifikaciju (verifikacija se mo`e izvr{iti samim algoritmom u polinomskom vremenu)). Pitawe da li je P = N P , jo{ je otvoreno, iako indikacije ukazuju da je P ≠ N P .Ako imamo dva problema odlu~ivawa P i Q, onda ka`emo da se P mo`e reducirati na Q (P ∝ Q) ako postoji funkcija g (sa polinomskom kompleksno{}u) koja transformi{e instance problema P u instance problema Q tako da, ako je x instanca problema P za koju je rje{ewe "da", onda g preslikava x u g(x) koji je instanca problema Q za koju je rje{ewe tako|e "da". Lako se pokazuje da, ako su P i Q problemi odlu~ivawa i P ∝ Q, onda Q ∈ P = > P ∈ P . Problem Q je N P - kompletan ako je Q ∈ N P i ako za ∀ P ∈ N P imamo P ∝ Q. Klasu N P – te{kih problema ~ine problemi na koje se mogu reducirati neki (a time i svi) N P kompletni problemi. Intuitivno, N P problemi nisu te`i od N P -kompletnih problema, a N P -te{ki problemi nisu lak{i od N P –kompletnih. S obzirom na navedene definicije, ako bi rje{ewe bilo kojeg N P -kompletnog problema bilo u P , onda bi svi N P problemi bili u P , i analogno, ako bi se dokazalo da bilo koji N P -kompletan problem nema rje{ewa 8.3 Algoritmi za stati~ko raspore|ivawe 198 u P , onda bi to va`ilo i za sve N P -kompletne probleme. Dakle, ~iwenica da za N P kompletne probleme nisu prona|eni algortmi u polinomskom vremenu ne zna~i i tvrdwu (ve} samo preovla|uju}e uvjerewe, na osnovu osobina takvih problema) da takva rje{ewa ne postoje. Neki problemi su N P -kompletni, ako maksimalna vrijednost pojedinih karakteristika objekata nije ograni~ena. Ako se ograni~i maksimalna vrijednost relevantnih karakteristika objekata, problem prelazi u klasu P . Odgovaraju}i algoritmi se nazivaju pseudopolinomski, jer imaju polinomski ograni~eno vrijeme ra~unawa samo ako je vrijednost relevantnih karakteristika objekata ograni~ena. Primjeri N P -kompletnih problema odu~ivawa su problemi particionisawa skupa od n cjelobrojnih elemenata u dva podskupa sa osobinom da je suma elemenata u oba podskupa jednaka; problem utvr|ivawa da li u neorijentisanom grafu G = (T, A) (T-skup ~vorova, Askup lukova izme|u ~vorova) postoji podgraf C sa k ili mawe ~vorova, tako da za svaki luk (u,v) ∈ A, barem jedan ~vor na luku (u,v) pripada podgrafu C i sl. Zna~aj ovih poznatih problema je u tome {to se polinomskom transformacijom novog problema u neki od navedenih, mo`e identifikovati pripadnost problema klasi N P -kompletnih problema. Problem optimalnog raspore|ivawa zadataka na skup procesora (sa minimalnim vremenom izvr{ewa kao funkcijom ciqa) je poznat (u op{tem slu~aju) kao N P - kompletan problem. Npr. raspore|ivawe skupa zadataka sa proizvoqnim vremenima izvr{ewa na dva procesora, mo`e se jednostavno reducirati na navedeni problem particionisawa. Ovo implicira da je problem raspore|ivawa ra~unski kompleksan, {to je i osnovni razlog za {iroku primjenu algoritama koji daju podoptimalna, ali dovoqno kvalitetna rje{ewa u polinomskom vremenu. 8.3 Algoritmi za stati~ko raspore|ivawe Kao {to je prethodno pomenuto, stati~ko raspore|ivawe zadataka po procesorskim elementima vr{i se prije po~etka izvo|ewa. Pretpostavke od kojih polazi najve}i broj algoritama jesu: graf zadataka je orijentisan, acikli~an i stati~an; zadatak pridijeqen nekom procesoru ne mo`e kasnije biti prealociran; svi procesori su me|usobno (direktno ili indirektno) povezani i mogu izmjewivati podatke; zadaci imaju procesne i komunikacione karakteristike koje se ne mijewaju i koje su poznate prije izvo|ewa (u fazi prevo|ewa); zadatak koji generi{e podatke, prosqe|uje ih zadacima koji ih koriste nakon {to je wegovo izvo|ewe zavr{eno; komunikacija podataka od jednog zadatka ka razli~itim zadacima-kori- Raspore|ivawe zadataka na procesore 199 snicima se odvija paralelno. Pretpostavke koje variraju u razli~itim algoritmima su: homogenost/heterogenost procesora; izvo|ewe zadataka bez preuzimawa/sa preuzimawem; specifi~nosti komunikacionog podsistema i sl. Tipi~na funkcija ciqa za koju se `eli na}i minimum je ukupno vrijeme izvo|ewa skupa zadataka. Da bi se ovaj ciq ostvario potrebno je, s jedne strane, minimizovati komunikaciona ka{wewa, a s druge strane, maksimalno paralelizovati procesirawe zadataka. Po{to se minimizacija komunikacionih ka{wewa ostvaruje grupisawem zadataka za izvr{ewe na istom procesoru, {to zna~i sekvencijalizacijom izvr{ewa, a s druge strane, paralelizacija procesirawa podrazumijeva izvo|ewe zadataka na razli~itim procesorima, jasno je da optimalno rje{ewe sadr`i kompromis dva navedena suprotna principa. Budu}i da je problem nala`ewa optimalnog rje{ewa u op{tem slu~aju N P - kompletan, naj~e{}e se koriste algoritmi koji daju podoptimalna rje{ewa u polinimskom vremenu. Kao {to je prethodno navedeno, ovi algoritmi mogu biti aproksimativni i heuristi~ki. Naj~e{}e kori{teni aproksimativni algoritmi se baziraju na metodi simulacije kaqewa, metodama matemati~kog programirawa i ograni~enog pretra`ivawa prostora rje{ewa. Heuristi~ki algoritmi se naj~e{}e baziraju na tehnikama raspore|ivawa po listama prioriteta (list scheduling), te na tehnikama objediwavawa u grupe (clustering). U daqem tekstu su ukratko opisani neki algoritmi za stati~ko raspore|ivawe. 3.3.1 Algoritmi za optimalno raspore|ivawe Razli~iti algoritmi za optimalno raspore|ivawa podrazumijevaju odre|ene specifi~nosti strukture i karakteristika grafova koji reprezentuju sistem zadataka. Ako se sistem sastoji od m nezavisnih zadataka, ~ija su vremena izvo|ewa τ 1 , τ 2 , ... , τ m i n procesora onda je optimalno vrijeme raspore|ivawa sa preuzimawem dato sa (Muntz i Coffman): 1 m = max max {τ i }, τi To n i =1 1≤i ≤m ∑ Deterministi~ki optimalni algoritmi raspore|ivawa sa preuzimawem, u homogenim vi{eprocesorskim sistemima, koji produkuju rje{ewe u vremenu ograni~enom polinomskom funkcijom zavisnosti od broja zadataka (bez ra~unawa komunikacionih ka{wewa) su svedeni na slijede}e specijalne slu~ajeve: 1) Graf G se sastoji od ~vorova (zadataka) koji imaju me|usobno proporcionalna vremena izvo|ewa, a broj procesora je ograni~en na 2. 8.3 Algoritmi za stati~ko raspore|ivawe 200 2) Svaki ~vor u grafu G ima najvi{e jednog nasqednika, odnosno, graf G ima formu stabla (rooted tree). Vremena izvo|ewa ~vorova su me|usobno proporcionalna, a broj procesora je ≥ 2. Za nepreuzimaju}e raspore|ivawe, uslov dobijawa optimalnog algoritma za slu~ajeve 1) i 2) je da zadaci imaju ista vremena izvr{ewa. Algoritmi koji daju optimalna rje{ewa za navedene slu~ajeve predstavqaju razli~ite varijante i ekstenzije Hu-ovog bazi~nog algoritma. U osnovi, ovi algoritmi formiraju sortiranu listu zadataka po pridijeqenim prioritetima, a zatim (dok se lista ne isprazni) dodjequju zadatak najvi{eg prioriteta iz liste, spreman za izvo|ewe, prvom slobodnom procesoru na izvr{avawe. Iako navedeni algoritmi nisu direktno primjenqivi u realnim sistemima, dobijeni analiti~ki rezultati daju odre|ene smjernice o tome kako eksploatisati paralelizam u vi{eprocesorskim sistemima. Tako|e, oni mogu pomo}i u procjewivawu granica ubrzawa koje se posti`e paralelnim izvo|ewem, najlo{ijih slu~ajeva itd. Npr. odnos vremena izvr{ewa ( ϖ ) m zadataka (sa ograni~ewima pretho|ewa) na n procesora, raspore|enih bilo kojim algoritmom na bazi prioritetne liste (list scheduling) koji ne uzima u obzir komunikaciona ka{wewa, u odnosu na vrijeme optimalnog rasporeda (ϖ 0 ), dat je sa ϖ / ϖ 0 = 2 −1 n . Optimalni deterministi~ki algoritmi u op{tem slu~aju daju (optimalno) rje{ewe u vremenu koje se ne mo`e ograni~iti polinomskom funkcijom zavisnosti od broja zadataka. Iako su za prakti~nu primjenu od interesa samo algoritmi koji daju rje{ewa u vremenu ograni~enom polinomskom funkcijom, navedeni algoritmi imaju veliki zna~aj u analizi i procjewivawu heuristi~kih algoritama, uo~avawu i korigovawu wihovih "slabih ta~aka", analizi najlo{ijih slu~ajeva i sl. Algoritam koji je predlo`io Stone se bazira na primjeni Ford/Fulkersonovog (max tok/min presjek) algoritma, kojim se maksimalni protok (robe) u mre`i dobija nala`ewem minimalnog presjeka grafi~kog modela mre`nog toka. Mre`a kojom se mogu realizovati razli~iti tokovi se modelira grafom, gdje postoje izvori, odredi{ta i me|u~vorovi povezani lukovima. Lukovima se pridjequju te`ine, koje reprezentuju maksimalni protok izme|u ~vorova. Raspore|ivawe zadataka na procesore 201 Specifi~ni tok se reprezentuje orijentisanim grafom, gdje te`ine na pojedinim granama predstavqaju iznos toka (robe npr.) izme|u ~vorova. Suma ulaznih i izlaznih tokova za unutra{we ~vorove mora biti ista, a suma (izlaznih) tokova iz izvora mora biti jednaka sumi (ulaznih) tokova odredi{ta. Maksimalni tok u mre`i se dobije sumom te`ina na lukovima koji pripadaju minimalnom presjeku. Presjek lukova mora biti takav da u potpunosti dijeli izvore od odredi{ta. Ovaj model optimizacije, zasnovan na grafovima, iskori{ten je za odre|ivawe pridjeqivawa zadataka heterogenim procesorima, sa ciqem minimizacije ukupne cijene izvo|ewa i komunikacije. Struktura zadataka predstavqa se grafom, gdje ~vorovi reprezentuju same zadatke, a te`ine na lukovima cijenu komunikacije izme|u zadataka ako se oni izvode na razli~itim procesorima. Vremena izvo|ewa zadataka na svakom procesoru se daju posebnom tabelom Sl. 8.4. P0 B 5 A 2 C 4 D 3 B C D 2 10 8 A 6 P1 12 9 5 4 Sl. 8.4. Specifikacija izvo|ewa sistema zadataka u heterogenom sistemu. Za slu~aj izvo|ewa zadataka na dva procesora, dodaju se dva ~vora So i S1 (koji reprezentuju, s jedne strane procesore, a s druge strane izvore/odredi{te u modelu mre`nog toka). Tako|e se dodaju lukovi koji povezuju ~vorove So i S1 sa ~vorovima zadataka. Te`ina na luku kojem pripada So i neki zadatak X odgovara vremenu izvo|ewa tog zadatka na P1 i obrnuto, luk koji povezuje ~vor S1 i zadatak X ima te`inu koja je jednaka vremenu izvo|ewa zadatka X na Po. Za prethodni primjer, pro{ireni graf izgleda kao na Sl. 8.5. Konstrukcija grafa je takva da odgovara modelu mre`nog toka, a presjek koji dijeli izvore i odredi{ta odre|uje alokaciju zadataka po procesorima. Suma te`ina svih lukova na presjeku, predstavqa sumu ukupne cijene izvo|ewa (procesorske i komunikacione). Problem alokacije zadataka, za datu funkciju ciqa, svodi se na problem nala`ewa minimalnog presjeka mre`nog toka, {to se realizuje direktno Ford/Fulkerson-ovim algoritmom (koji je reda O(n5)). Odre|ivawe redoslijeda i startnih vremena izvo|ewa zadataka na procesorima, ostavqa se za fazu izvo|ewa. 8.3 Algoritmi za stati~ko raspore|ivawe 202 6 2 9 S0 12 5 4 A 2 C 4 D 10 8 S1 5 B 3 Sl. 8.5 Modifikovani graf i presjek koji odre|uje pridjeqivawe modula. Navedeni metod, principijelno razvijen i za sistem sa n procesora, za vi{e od 3 procesora postaje ra~unski neupravqiv. Osim toga, za slu~aj da su procesori homogeni, funkcija ciqa je takva da se svi zadaci mapiraju na jedan procesor. Interesantno je napomenuti da autor isti~e primjenqivost ove tehnike ne samo za stati~ko nego i za dinami~ko raspore|ivawe zadataka. Raspore|ivawe zadataka na procesore 203 3.3.2 Heuristi~ki algoritmi Heuristi~ki algoritmi donose odluku o raspore|ivawu zadataka na bazi uticaja odre|enih parametara na funkciju ciqa koja se optimizuje. Na primjer, kriti~ni put odre|uje raspon izvo|ewa, i algoritmi koji se baziraju na ovom parametru u svakom koraku nastoje maksimalno da smawe kriti~ni put. Ovi algoritmi polaze od odre|enih, a priori pretpostavki o strukturi zadataka i uslova eksploatacije, i naj~e{}e garantuju podoptimalno rje{ewe u odre|enim granicama. Vrijeme raspore|ivawa je znatno kra}e u odnosu na druge tehnike, {to ove metode ~ini najatraktivnijim za primjenu. Dva naj~e{}e kori{tena generalna pristupa su raspore|ivawe po listama prioriteta (list scheduling) i objediwavawe u grupe (clustering). Raspore|ivawe po listama prioriteta Raspore|ivawe po listama prioriteta je jednostavna i efikasna tehnika, koja u najve}em broju slu~ajeva, daje dovoqno dobre rasporede. Princip raspore|ivawa je slijede}i: zadacima se pridjequju prioriteti na osnovu odre|ene heuristi~ke funkcije, a zatim se oni stavqaju u listu, sortiranu prema navedenom prioritetu. Ukoliko postoje ograni~ewa pretho|ewa u izvo|ewu zadataka, onda, u posmatranom trenutku, zadaci ~iji su svi prethodnici zavr{ili izvo|ewe se ozna~avaju spremnim za izvo|ewe, a procesori koji ne procesiraju zadatke se ozna~avaju raspolo`ivim. Ako u posmatranom trenutku postoje raspolo`ivi procesori i zadaci spremni za izvo|ewe, onda se prvo vr{i pridjeqivawe spremnog zadatka sa najvi{im prioritetom procesoru iz skupa raspolo`ivih. Zatim se pridijeqeni zadatak uklawa iz prioritetne liste, a procesor iz skupa raspolo`ivih. Proces se u odnosnom trenutku ponavqa za slijede}e zadatke spremne za izvo|ewe, po opadaju}em redoslijedu prioriteta, i zavr{ava se kada se iscrpe svi spremni zadaci ili raspolo`ivi procesori. Zatim se inkrementira globalni takt, sve do trenutka kada neki od procesora ne postaje raspolo`iv, ili novi zadatak spreman za izvo|ewe, nakon ~ega se opisani proces pridjeqivawa ponavqa. Najjednostavnija ilustracija raspore|ivawa po listama prioriteta je za slu~aj nezavisnih zadataka. Na primjer, LPT (Largest Processing Time) algoritam vr{i raspore|ivawe nezavisnih zadataka, pri ~emu je prioritet zadatka ve}i ako mu je vrijeme izvo|ewa du`e. Opis ovog algoritma je dat u tekstu koji slijedi. Neka je dat skup {Ti} i = 1, ... , m nezavisnih zadataka koji se izvode na n procesora. Vrijeme potrebno za izvo|ewe zadataka Ti ozna~imo sa τ i . U svakom posmatranom trenutku postoji parcijalni raspored zadataka na procesore. Neka je Fj teku}e vrijeme zavr{etka procesirawa procesora Pj (tj. vrijeme kada procesor Pj postaje raspolo`iv). 8.3 Algoritmi za stati~ko raspore|ivawe procedure LPT 204 1) Postavi k = 1 i Fj = 0 za 1 ≤ j ≤ n. Stavi zadatke Ti, i = 1, ... , m u listu L i sortiraj listu po opadaju}im vremenima izvo|ewa zadataka τ i . 2) Izaberi procesor Pj sa najmawim Fj (tj. procesor sa minimalnim teku}im vremenom zavr{etka). 3) Pridijeli zadatak Tk, sa k-tog ulaza liste prioriteta, procesoru Pj, i a`uriraj Fj na vrijednost Fj = Fj + τ k . 4) Ako je k ≠ m inkrementiraj k i idi na 2. U suprotnom, algoritam zavr{ava pri ~emu je raspon izvo|ewa jednak maksimalnoj vrijednosti Fj, j = 1, ... ,n. end LPT Ukoliko izme|u zadataka postoje relacije pretho|ewa, onda se samo spremni zadaci mogu rasporediti za izvo|ewe. Najpoznatiji heuristi~ki algoritam za raspore|ivawe zadataka izme|u kojih postoje relacije pretho|ewa je HLFET (Highest Level First with Estimated Times), ili metod kriti~nog puta. Algoritam ne uzima u obzir komunikaciona ka{wewa izme|u zadataka. Svakom zadatku Ti se pridjequje prioritet, koji je jednak sumi vremena izvo|ewa svih zadataka, na najdu`em putu od Ti do nekog zavr{nog ~vora. Raspore|ivawe po HLFET {emi realizuje se prema slijede}oj proceduri: procedure HLFET 1) Inicijalizacija. Svakom zadatku Ti, i = 1, ... , m , pridijeli prioritet koji je jednak sumi vremena izvo|ewa svih zadataka na najdu`em putu od Ti do nekog zavr{nog ~vora. Postavi k = 1 i Fj = 0 za 1 ≤ j ≤ n. Stavi zadatke Ti u listu L i sortiraj L po opadaju}oj vrijednosti prioriteta zadataka. Iniciraj t = 0. Uz svaki Ti zadatak postavi vrijednost INDEGREE (Ti) jednaku broju wegovih neposrednih prethodnika. Zadatak Ti je spreman za izvo|ewe ako je vrijednost parametra INDEGREE (Ti) = 0. 2) Pridijeli zadatak Ti spreman za izvo|ewe (sa najvi{im prioritetetom u posmatranom trenutku) slobodnom procesoru. Ukloni Ti iz liste L i procesor Pj iz skupa raspolo`ivih. Pove}aj k za 1 i Fj = Fj + τ i . Ponovi 2 sve dok ima zadataka spremnih za izvo|ewe i raspolo`ivih procesora u posmatranom trenutku. 3) Ako je k = m algoritam zavr{ava. Raspon izvo|ewa je max Fj. U suprotnom postavi t = j min Fj, j pripada skupu procesora koji vr{e procesirawe. Za svaki procesor Pj koji j zadovoqava gorwi uslov i korespondentni zadatak Ti koji zavr{ava izvo|ewe na Pj u trenutku t, Raspore|ivawe zadataka na procesore - stavi procesor Pj u listu raspolo`ivih, 205 - za svaki ~vor Tl koji je nasqednik Ti a`uriraj INDEGREE(Tl) = INDEGREE(Tl) – 1 a zatim idi na korak 2. end HLFET HLFET algoritam nastoji u svakom koraku da smawi najdu`i put, prioritetnim raspore|ivawem zadatka koji se nalazi na tom putu. Takva strategija mo`e rezultovati neravnomjernim balansom optere}ewa procesora, i time du`im rasponom izvo|ewa. Na primjer, ako se rasporedi zadatak sa najve}im prioritetom (na kriti~nom putu), onda je potrebno pridijeliti izvo|ewe drugih zadataka drugim procesnim elementima za vrijeme izvo|ewa pomenutog zadatka. Ali, ako je pomenuti zadatak "kontrolni" on mo`e da blokira raspore|ivawe drugih zadataka dok se ne zavr{i wegovo izvo|ewe. Predlo`ena ekstenzija HLFET algoritma [G.Sih] uzima u obzir komunikaciona ka{wewa. Zadatku se dodjequje dinami~ki nivo/prioritet, koji se mijewa u toku procesa raspore|ivawa. Dinami~ki nivo DL(Ti, Pj, nog zadataka Ti na procesoru Pj ∑ (t ) ) odra`ava pogodnost raspore|ivawa izvo|ewa spremu stawu ∑ (t ) , gdje ∑ (t ) obuhvata kako stawe procesirawa ∑ (t ) ) je najranije i (prethodno raspore|enih zadataka) tako i stawe komunikacionih resursa (prethodno aktiviranih i mapiranih transfera podataka) u trenutku t. DA(Ti, Pj, vrijeme kada su svi podaci potrebni za izvo|ewe zadatka Ti, raspolo`ivi na procesoru Pj za stawe ∑ (t ) . S obzirom da raspolo`ivost podataka potrebnih za izvo|ewe T zavisi od topo- logije povezivawa procesora, ova veli~ina se izra~unava u topolo{ki zavisnom modulu raspore|iva~a, koji uzima u obzir stawe komunikacionih resursa u datom trenutku. Dinami~ki nivo izra`ava se sa: DL(Ti, Pj, ∑ (t ) ) = SL(Ti) - max{t, DA (Ti, Pj, ∑ (t ) }. gdje SL(Ti) ozna~ava stati~ki prioritet. U svakom koraku za izvo|ewe se selektuje zadatak spreman za raspore|ivawe i raspolo`ivi procesor (par), za koji prethodni izraz ima najve}u vrijednost. 8.3 Algoritmi za stati~ko raspore|ivawe 206 Dinami~ki nivo ima jednostavnu interpretaciju. Drugi ~lan u izrazu predstavqa najranije vrijeme kada su podaci, potrebni za Ti, raspolo`ivi na Pj. Stati~ki prioritet, koji se odre|uje na isti na~in kao i za HLFET, se umawuje za navedeni ~lan. To zna~i, da zadatak koji }e dugo ~ekati na podatke, ne treba odmah pridijeliti procesoru za izvo|ewe (jer se on ionako ne}e izvoditi zbog ~ekawa na podatke) uprkos wegovom visokom stati~kom prioritetu. Odnosno, povoqnije je rasporediti zadatak sa mawim stati~kim prioritetom, koji }e prije biti spreman za izvo|ewe, i na taj na~in smawiti prazan hod procesora. Ovaj pristup autor naziva HDLFET algoritam (Highest Dynamic Level First with Estimated Time). Osnovni nedostatak HDLFET algoritma je nemogu}nost da se procesor dr`i u praznom hodu. Naime, algoritam u svakom koraku raspore|ivawa, koji je odre|en globalnim taktom, dodjequje zadatak sa najve}im dinami~kim prioritetom raspolo`ivom procesoru, nastoje}i eksploatisati raspolo`ivi paralelizam. Ovakav pristup nije pogodan za slu~aj sitnozrnastog paralelizma, gdje je komunikaciono vrijeme izra`eno, ve} je potrebno omogu}iti serijalizaciju izvo|ewa paralelnih zadataka na jednom procesoru, u ciqu minimizacije efekta komunikacionih ka{wewa. Npr. DAG na Sl. 8.6, ima optimalan raspored izvo|ewa kada se svi zadaci raspodijele na jedan procesor. 14 B 1 A 2 9 D 4 3 C 5 Sl. 8.6. Sitnozrnasti DAG. Da bi se rije{io navedeni problem, autor predla`e fundamentalnu modifikaciju HDLFET algoritma raspore|ivawa, dozvoqavaju}i da svi procesori u svakom koraku raspore|ivawa budu raspolo`ivi, {to omogu}ava da se nekom procesoru sukcesivno dodijeli vi{e zadataka (pogodnih za izvo|ewe na tom procesoru). Iz navedenog razloga, u modifikovanom algoritmu, ne koristi se globalni takt za napredovawe procesa raspore|ivawa. Dinami~ki nivo koji se dodjequje spremnim zadacima je: DL(Ti, Pj ) = SL(Ti) - max {DA(Ti, Pj, ∑ ) , TF(P , ∑ ) }, j Raspore|ivawe zadataka na procesore gdje je TF(Pj, 207 ∑) najranije vrijeme kada procesor Pj zavr{ava procesirawe pridijeqenih zadataka za stawe ∑. Autor tako|e predla`e ekstenzije algoritma za stati~ko raspore|i- vawe zadataka u heterogenom vi{eprocesorskom okru`ewu, uzimawem u obzir pogodnosti raspore|ivawa zadatka na svakom procesoru, pogodnosti raspore|ivawa na odre|eni procesor sa stanovi{ta nasqednika, te raspolo`ivosti vi{e istovrsnih procesora. Tako|e, razmatra se kori{tewe drugih postupaka, kao {to su, na primjer, te`inski faktori pojedinih ~lanova, raspore|ivawe unazad i uvo|ewe dodatnih ograni~ewa pretho|ewa koja poboq{avaju raspored, ali i uvode dodatna re`ijska vremena. Algoritmi na bazi grupisawa (Clustering algorithms) U prisustvu komunikacionih ka{wewa, optimalno raspore|ivawe se ne dobija uvijek maksimalnom eksploatacijom paralelizma. Problem dobijawa optimalnog rasporeda mo`e se posmatrati i kao problem grupisawa zadataka, pridjeqivawa grupa procesorima i odre|ivawa redoslijeda izvr{ewa u okviru svake grupe (procesora). Za ilustraciju, posma- x Dxy τx Dxz y τy trajmo jednostavan graf zadataka na Sl. 8.7. Dxy, Dxz - koli~ina jedini~nih podataka koji se prosqe|uju od x ka y odnosno z. z τz τ x ,τ y ,τ z - Vrijeme potrebno za izvr{ewe zadataka x, y, z. Sl. 8.7 Jednostavan graf zadataka sa komunikacionim ka{wewima. Optimalan raspored grafa sa Sl. 8.7 na 2 identi~na procesora, ako je funkcija ciqa minimalni raspon izvo|ewa, zavisi od vrijednosti Dxy, Dxz, τ y , τ z . Zbog jednostavnosti, pretpostavimo da komunikacija D jedini~nih podataka izme|u 2 procesora zahtijeva D vremenskih jedinica. Vrijeme komunikacije izme|u zadataka, ako se zadaci izvedu na istom procesoru, je zanemarqivo. Onda je Topt = τ x + min { τ y + τ z , max { τ y , τ z + Dxz }, max { τ z , τ y + Dxy}} Ako je ~lan τ y + τ z minimalan, onda je optimalan raspored kada se svi zadaci izvode na jednom procesoru; ako u "min" izrazu minimalnu vrijednost ima ~lan max { τ y , τ z + Dxz}, onda 8.3 Algoritmi za stati~ko raspore|ivawe 208 se optimalan raspored dobija izvo|ewem x i y na P1 i z na P2; u suprotnom, x i z treba izvr{iti na P1, a y na P2. Dakle, komunikaciona ka{wewa imaju bitnu ulogu u odre|ivawu grupa zadataka (klastera) koja se pridjequju procesorima. Algoritmi na bazi grupisawa nastoje formirati grupe, koje }e minimizovati komunikaciona ka{wewa pri izvo|ewu, nakon wihovog mapirawa na procesore, uz {to je mogu}e ve}u eksploataciju paralelizma. Jasno je da su navedeni ciqevi opre~ni: eliminisawe komunikacionih ka{wewa se ostvaruje grupisawem zadataka na jednom procesoru, dakle serijalizacijom, dok se s druge strane eksploatacija paralelizma posti`e disperzijom konkurentnih zadataka na razli~ite procesore (~ime se pove}avaju komunikaciona vremena). Optimalno rje{ewe je dakle najboqi kompromis dve navedene (opre~ne) strategije i, u op{tem slu~aju, problem wegovog nala`ewa je N P -kompletan. Formalno, problem grupisawa, za sistem specifikovan u dijelu 3.1, se mo`e iskazati kao problem mapirawa DAG-a na g grupa {G1, G2, ..., Gg }, map(Ti) = Gk , i = 1, ... , m, (1 ≤ k ≤ g ≤ n), tako da se zadovoqi funkcija ciqa. Ako je funkcija ciqa minimalno vrijeme izvo|ewa (raspon izvo|ewa - "paralelno" vrijeme) na vi{eprocesorskom sistemu sa n procesora, onda se problem svodi na odre|ivawe grupa Gk, k = 1, ... , g, pridjeqivawe grupa procesorima i odre|ivawe redoslijeda izvo|ewa svakog zadatka u grupi, tako da se za dati raspored ostvari uslov min { max {CT (T i )} } , s i = 1: m gdje je CT(Ti) vrijeme kompletirawa zadatka Ti, a s skup svih mogu}ih rasporeda izvo|ewa skupa T na P (min-max kriterijum). Tehnike linearnog grupisawa, na osnovu polaznog DAG-a, formiraju grupe (clusters) zadataka, pri ~emu svaka grupa sadr`i zadatke koji imaju najvi{e jednog prethodnika i najvi{e jednog nasqednika u grupi (linearne grupe). U (linearnoj) grupi ne mogu biti me|usobno nezavisni zadaci. Primjeri tehnika linearnog grupisawa su algoritmi koje su predlo`ili Kim i Browne i Lee . Prvi algoritam, u svakom koraku, identifikuje orijentisani put sa najve}om te`inom (sumom procesnih i komunikacionih zahtjeva), i izdvaja zadatke na tom putu u linearnu grupu. Zatim zadatke iz navedene grupe uklawa iz DAG-a i postupak ponavqa za preostale ~vorove, sve dok se kompletan graf ne razdijeli u linearne grupe. Izme|u linearnih grupa postoje relacije pretho|ewa i komunikacioni tokovi odre|eni polaznim DAG-om. Navedeni algoritam, za mapirawe linearnih grupa na vi{eprocesorski sistem, primjewuje tehnike koje se zasnivaju na teoriji grafova. Raspore|ivawe zadataka na procesore 209 Drugi pomenuti metod dobijawa linearnih grupa (dijeqewe po vertikalnim slojevima (vertically layered partitioning)) izvodi se u dve faze: u prvoj fazi, polazni sitnozrnasti DAG se transformi{e topolo{kim sortirawem u me|usobno disjunktne horizontalne slojeve. Svi zadaci u sloju k ≥ 0 su me|usobno nezavisni, i imaju barem jednog prethodnika u sloju k-1. U modifikovanom grafu, identifikuje se direktni (vertikalni) put najve}e te`ine, i izdvaja u linearnu grupu (Sl. 8.9). Izdvojeni ~vorovi se uklawaju iz grafa i postupak se ponavqa sa preostalim ~vorovima modifikovanog grafa, sve dok se ne iscrpe svi ~vorovi (modifikovanog) grafa. Osnovna ideja navedenih algoritama je da se minimizuje kriti~ni put: zadaci koji su na kriti~nom putu, zbog relacija pretho|ewa, moraju se izvesti sekvencijalno. Grupisawem ovih zadataka na jednom procesoru, elimini{u se komunikaciama ka{wewa pri wihovom izvo|ewu ~ime se nastoji dobiti najpovoqniji raspon izvo|ewa. Me|utim, grupisawem zadataka na kriti~nom putu DAG-a, ne dobija se uvijek optimalan raspored izvo|ewa, kao {to to pokazuje slijede}i primjer. 10 B 1 A 1 4 C 10 Sl. 8.8 Primjer sistema zadataka. 5 4 D 5 1 E 1 Kriti~ni put grafa je ABDE, jer je suma te`ina na putu 1+1+5+10+5+1+1=24 (suma te`ina na putu ACE je 20). Ako raspore|ivawe vr{imo na 2 (identi~na) procesora, onda dodjeqivawe grupe na kriti~nom putu (ABDE) jednom procesoru i dodjeqivawe preostalog zadatka C na drugi procesor daje raspon izvo|ewa 20. Grupisawem zadataka BD na P1 i ACE na P2 dobija se raspon izvo|ewa 14. 8.3 Algoritmi za stati~ko raspore|ivawe 210 1 1 2 2 4 4 3 5 3 8 5 7 8 7 6 6 10 9 10 9 a) Polazni DAG b) Modifikovani graf sa horizontalnim slojevima V3 V1 1 V2 2 4 5 3 8 7 6 10 9 Sl. 8.9 Grupisawe dijeqewem po vertikalnim slojevima. Raspore|ivawe zadataka na procesore n1 1 3 n2 6 0.5 n3 1 2.5 2 n6 2.5 n7 1 Po~etni DAG 1 n4 1 4 1 n5 2 n2 6 2 2.5 n7 1 a) po~etno grupisawe n7 b) korak 1 3 n1 1 n4 1 0.5 n3 1 4 2.5 n6 1 1 n5 n2 2 n6 n1 n4 n3 n5 211 n1 n4 n2 n3 n5 n2 n1 n4 n5 n6 n6 n7 c) korak 2 n1 n4 n2 n3 n5 n2 n7 d) korak 3 n1 n4 n5 n6 n6 n7 e) korak 4 n7 f) korak 7 Sl. 8.10 Grupisawe Sarkar-ovim algoritmom Sarkarov algoritam grupisawa se bazira na sukcesivnom poboq{awu grupisawa polaze}i od inicijalnog, u kojem je svaki zadatak mapiran u posebnu grupu. U svakom slijede}em koraku, algoritam nastoji da poboq{a grupisawe objediwavawem najpogodnijih grupa. Algoritam prvo sortira lukove koji povezuju ~vorove(zadatke) po opadaju}im vrijednostima te`ina, i onda vr{i grupisawe u a = | A | koraka (a je broj lukova). U svakom koraku se ispituje slijede}i luk iz liste: ako se anulirawem te`ine luka ne pove}ava paralelno vrijeme izvr{ewa, onda se zadaci povezani tim lukom (i automatski grupe kojima oni pripadaju) objediwavaju. 8.3 Algoritmi za stati~ko raspore|ivawe 212 Po{to je odre|ivawe paralelnog vremena tako|e N P - kompletan problem, a zahtijeva se u svakom od a koraka, Sarkov algoritam koristi slijede}u strategiju za odre|ivawe redoslijeda izvr{ewa u okviru grupa: zadatak sa najdu`im putem do zavr{nog ~vora (blevel) ima najvi{i prioritet, pri ~emu se koristi blevel vrijednosti ~vora iz prethodnog koraka. U tom slu~aju kompleksnost ra~unawa paralelnog vremena je reda O(a+m) (m je ukupan broj zadataka/~vorova), tako da je ukupna kompleksnog algoritma reda O(a * (a+m)). Primjer grupisawa kori{tewem navedenog algoritma dat je dijagramima na Sl. 8.9 i Tabeli 8.1. Tabela 8.1 Koraci grupisawa zadataka Sarkarovim algoritmom za primjer sa Sl.8.10 Korak Ispitivani luk par.vrijeme ako se luk anulira Anulirawe luka paralel. vrijeme 0 1 2 13 (n4,n6) (n1,n2) (n3,n6) (n6,n7) (n2,n7) (n1,n3) (n5,n6) 13 10 10 10 11 11 10 Da Da Da Da Ne Ne Da 13 10 10 10 10 10 10 3 4 5 6 7 Pored navedenog algoritma grupisawa, Sarkar izla`e kompletan koncept za particionisawe i raspore|ivawe, koji strukturira u faze: 1) Procjene komunikacionih i procesnih zahtjeva, 2) Ekspanzije strukture grafa zadataka, 3) Objediwavawa, 4) Pridjeqivawa procesora. U prvoj fazi se procjewuje cijena komunikacije i izvr{ewa na osnovu analize programske strukture. U drugoj fazi vr{i se ra{~lawivawe krupnijih programskih modula na komponentne dijelove, kako bi se eksponiralo dovoqno potencijalnog paralelizma za eksploataciju na odnosnoj vi{eprocesorskoj arhitekturi. Nakon toga vr{i se objediwavawe komponenata u grupe kako je prethodno opisano, sa ciqem da se elimini{u zna~ajna komunikaciona vremena i time smawi raspon izvo|ewa (objediwavawe se vr{i samo ako se ne pove}ava procijeweno paralelno vrijeme izvr{ewa). U fazi 4, vr{i se pridjeqivawe formiranih grupa procesorima kori{tewem modifikovanog raspore|ivawa po prioritetnoj listi. Svaka grupa se redom mapira na svaki od procesora, i bira se onaj procesor, za koji je paralelno vrijeme izvo|ewa najkra}e. Raspore|ivawe zadataka na procesore 213 8.4 Dinami~ko raspore|ivawe Kod dinami~kog raspore|ivawa, pridjeqivawe zadataka procesnim elementima (PE) se vr{i u fazi izvo|ewa. Struktura i karakteristike skupa zadataka, procesnih elemenata i komunikacionog podsistema mogu biti veoma razli~iti, a mogu se i dinami~ki mijewati. Kao posqedicu imamo razli~ite algoritme i tehnike raspore|ivawa i funkcije ciqa koje se `ele optimizovati. Tehnike za dinami~ko balansirawe optere}ewa su u posqedwe vrijeme predmet intenzivnog istra`ivawa. One su prije svega od interesa u distrubuiranim sistemima op{te namjene (lokalne mre`e radnih stanica npr.), gdje je od interesa efikasno kori{tewe raspolo`ivih resursa, {to se ostvaruje ravnomjernom (balansiranom) raspodjelom optere}ewa - skupa (nezavisnih) zadataka po procesnim elementima. Balansom optere}ewa se naj~e{}e posti`e i minimizacija prosje~nog vremena izvr{ewa zadataka. Dinami~ko raspore|ivawe zadataka u sistemima u stvarnom vremenu, s druge strane, ima za ciq minimizaciju (vjerovatno}e) ka{wewa izvr{ewa zadataka u odnosu na krajwe zahtijevano vrijeme zavr{etka. Svi algoritmi u osnovi sadr`e strategiju i mehanizme za: • procjewivawe i distribuciju informacija, • odlu~ivawe o isplativosti izvr{ewa transfera zadataka, • lokaciju transfera, • selekciju zadataka za transfer. U fazi procjewivawa i distribucije informacija registruju se podaci od interesa za slijede}u fazu algoritma: optere}ewe procesora, karakteristike zadataka (zahtjevi za procesorskim i drugim resursima, krajwe vrijeme izvr{ewa, prioriteti) i sl. Mehanizmi za odlu~ivawe o transferu, na osnovu registrovanih informacija i definisanih kriterijuma, donose odluku o izvr{ewu transfera zadataka sa jednih PE na druge. Kriterijumi zavise od funkcije ciqa, te stawa i karakteristika sistema. Dok se kod tehnika za balansirawe optere}ewa odluka donosi na osnovu procjene dobitka koji se dobija o~ekivanim balansom u odnosu na re`ijske gubitke, u sistemima u stvarnom vremenu transfer se poduzima onda kada "negarantovani" zadatak (zadatak ~ije se vrijeme izvr{ewa ne mo`e garantovati do zahtijevanog trenutka u nekom PE) mo`e postati "garantovan" wegovim transferom na drugi PE. U fazi locirawa transfera odre|uje se izvor i odredi{te transfera. Selekcija zadataka specifikuje koji se zadaci (ili dijelovi zadataka) prebacuju iz izvora u odredi{ta. 8.4 Dinami~ko raspore|ivawe 214 Navedeni mehanizmi se mogu implementirati centralizovano ili distribuirano (s tim da se obi~no procjewivawe i distribucija informacija i selekcija zadataka realizuje lokalno, odnosno distribuirano). Centralizovani pristup ima na raspolagawu stawe cijelog sistema na jednom mjestu i na taj na~in mogu}nost dono{ewa ta~nih procjena i odluka. Ipak, akumulacija informacija na ovaj na~in implicira znatno re`ijsko vrijeme - gubitke, kao i ka{wewa koja mogu biti tolika da dolazi do zastarijevawa informacija. Alternativno, kod distrubuiranog pristupa, iako nisu sve informacije na raspolagawu prilikom procjewivawa stawa i odlu~ivawa, re`ijski gubici su znatno mawi, a informacije (zbog maweg ka{wewa) ta~nije. S obzirom na to da se aktivnosti potrebne za dinami~ko raspore|ivawe raspodjequju po procesnim elementima, ovakav pristup je adekvatan i za slu~aj pove}awa kompleksnosti sistema (pove}awa broja zadataka i procesnih elemenata). S obzirom na na~in dono{ewa odluka o lokaciji transfera, algoritmi mogu biti deterministi~ki, probabilisti~ki i adaptivni. Kod deterministi~kih algoritama transfer zadataka iz preoptere}enog PE se vr{i po fiksnoj {emi: npr. ako je PEi preoptere}en, transfer vi{ka optere}ewa }e se uvijek izvr{iti u PEj. Probabilisti~ki pristup vr{i transfer vi{ka optere}ewa iz PEi u PEj sa vjerovatno}om pij. Adaptivni pristup uzima u obzir teku}e stawe kod dono{ewa odluka. Stawe PE mo`e da karakteri{e broj zadataka koji ~ekaju na izvr{ewe, ukupno zahtijevano vrijeme izvr{ewa teku}ih zadataka, raspolo`ivost razli~itih resursa i sl. S obzirom na karakteristike akvizicije i distribucije informacija, Wang kategorizuje algoritme za dinami~ku raspodjelu optere}ewa u distribuiranim sistemima u slijede}e grupe: Hijerarhijski: Raspore|ivawe je distribuirano i organizovano u vi{e hijerarhijskih nivoa. Svaki raspore|iva~ u hijerarhiji je odgovoran za raspore|iva~e ili servere na ni`em nivou hijerarhije. Balansirawe optere}ewa se inicira zahtjevima za procesne resurse ka vi{im/ni`im hijerarhijskim nivoima, dok se ne ostvari ravnomjerna raspodjela. Sekvencijalni: PE sistema ~ine virtualni prsten. Svaki PE ima svoj raspore|iva~, preko kojeg zadaci u PE dobijaju dijeqene resurse u sistemu. Po virtuelnom prstenu se prosqe|uje kontrolni `eton kojim se obezbje|uje serijalizacija aktivnosti raspore|iva~a PE pri (de)alocirawu dijeqenih resursa. [eme ovog tipa naj~e{}e imaju osnovni naglasak na rje{avawu konflikata pri konkurentnom pristupu zajedni~kim resursima, a ne na raspodjeli optere}ewa. Raspore|iva~ koji je teku}i vlasnik kontrolnog `etona, ima mogu}nost alokacije zajedni~kih resursa. Pogodbeni: Kod ovih algoritama preoptere}eni PE {aqu "zahtjev za licitaciju" drugim PE u sistemu za preuzimawe dijela optere}ewa (inverzna varijanta je da neoptere}eni PE {aqu Raspore|ivawe zadataka na procesore 215 "zahtjev za licitaciju" drugim PE za slawe dijela optere}ewa). Po prijemu zahtjeva, neoptere}eni PE (server) mo`e izvoru (po{iqaocu) poslati ponudu za preuzimawe posla. Nakon dobijawa ponuda za servisirawe, izvor bira server (obi~no po kriterijumu najmawe optere}enosti) i prosqe|uje mu vi{ak optere}ewa. Inicirani nivoom: Optere}enost svakog PE se reprezentuje na osnovu pore|ewa teku}eg optere}ewa i indeksa minimalnog/maksimalnog optere}ewa. Ako je optere}ewe ispod minimalnog, onda se {aqe informacija drugim PE o spremnosti za preuzimawe optere}ewa iz drugih PE. Ako je PE preoptere}en, onda se poku{ava prebaciti dio zadataka na druge PE. Ove {eme mogu generisati znatna komunikaciona re`ijska vremena, specijalno u slu~ajevima visokog ukupnog nivoa optere}ewa. Sa odlu~ivawem na bazi stawa: Kod ovih {ema odlu~ivawe o transferu zadataka se vr{i na bazi procjene stawa sistema koje se periodi~no a`urira. Algoritam nastoji proslijediti vi{ak optere}ewa u nekom PE ka najpovoqnijem PE, na bazi teku}e opservacije stawa i usvojenih kriterijuma. Osnovni problem kod ovih algoritama je izbor parametara koji odre|uju prostor stawa i wihova akvizicija. Kompleksnost prostora stawa i wegovo ~esto a`urirawe stvara visok nivo re`ijskih gubitaka i ka{wewa. Rijetko uzorkovawe i a`urirawe stawa sistema ~ini informacije zastarjelim. Potrebno je na}i kompromisno rje{ewe, koje obezbje|uje da razlika izme|u procijewenog i stvarnog stawa sistema bude {to mawa. U daqem tekstu, za ilustraciju, opisani su neki algoritmi za dinami~ko balansirawe optere}ewa. Difuzioni: Svaki PE kooperi{e sa susjedima u ciqu rje{avawa problema preraspodjele optere}ewa iz preoptere}enih PE u neoptere}ene PE. Globalno balansirawe se posti`e na taj na~in {to se zadaci iz preoptere}enih dijelova sistema, po principu difuzije, prosqe|uju u malo optere}ene dijelove sistema. Difuzija inicirana po{iqaocem {ema raspore|ivawa je potpuno distribuirana i asinhrona. Svaki PE vodi evidenciju o optere}ewu u svom domenu, koji ~ini sam PE i wegovi najbli`i susjedi. A`urirawe stawa optere}ewa PE iz domena vodi se na osnovu poruka, koje izmjewuju PE iz svakog domena. Poruke se prosqe|uju ili periodi~no ili na osnovu promjene stawa optere}ewa, kada se optere}ewe promijeni za neki iznos ∆ L, odnosno kada prelazi preko odre|enog nivoa. Odlu~ivawe o isplativosti balansirawa se vr{i tako da PEp prvo sra~una prosje~no optere}ewe u svom domenu: Lp = 1 (l p + K +1 ∑l k =1 K k ) 8.4 Dinami~ko raspore|ivawe gdje je K broj susjednih PE a l k wihova optere}ewa. Kriterijum za inicirawe balansa je da je 216 l p − L p > LH . LH je prag odstupawa optere}ewa iznad kojeg se PE smatra preoptere}enim. U tom slu~aju se vi{ak optere}ewa raspodjequje na susjedne PE u domenu, proporcionalno pridijeqenoj te`ini hk , hk = { L p − lk , ako je l k < L p , ako je l k ≥ L p 0 Ako je ukupni mawak optere}ewa u susjednim PE iz domena Hp = ∑h k =1 K k onda se susjednom PEk iz domena pridjequje iznos optere}ewa δ k = (l p − L p ) hk ; Hp δ k ≥ δ min Ilustracija balansirawa optere}ewa ovom tehnikom data je na Sl. 8.11. 10 0 1 9 30 6 4 5 5 Sl. 8.11 Balansirawe optere}ewa difuzijom iniciranom po{iqaocem. Preklapawem domena balansirawa posti`e se difuzija vi{ka optere}ewa navedenim mehanizmom, iz preoptere}enih dijelova sistema u mawe optere}ene segmente, odnosno balansirawe na globalnom planu. Za a`urirawe kompletnog stawa optere}ewa, PE treba da izmijene K*N poruka (N je broj procesnih elemenata). U najgorem slu~aju, slu~aju velikog (ta~kastog) optere}ewa jednog PE, Raspore|ivawe zadataka na procesore 217 broj transfera je reda O(K*N). Difuzija inicirana prijemnikom je u osnovi inverzna prethodno opisanoj tehnici, jer neoptere}eni procesori zahtijevaju optere}ewe od preoptere}enih susjednih PE iz domena i dobijaju potvrdu za svaki zahtjev (ove poruke su potrebne za svaki transfer). Potrebno je napomenuti da su, s obzirom na razli~ite mogu}nosti a`urirawa stawa optere}ewa, mogu}e varijacije ovih tehnika, kriterijuma isplativosti transfera i sl. Gradijentni model koristi gradijentnu mapu udaqenosti neoptere}enih PE za transfer optere}ewa sa preoptere}enih PE. Kod ovih algoritama, neoptere}eni procesori {aqu poruke o (svom) stawu drugim procesorima u sistemu, a preoptere}eni procesori {aqu dio svog optere}ewa najbli`em neoptere}enom procesoru. Optere}ewa se usmjeravaju na bazi gradijenta udaqenosti. Udaqenost se defini{e kao najkra}i put od izvori{nog do odredi{nog PE. Inicijalno, svaki PE inicijalizuje parametar udaqenosti na vrijednost dijametra sistema (Wmax). Udaqenost PE postaje 0 ako optere}ewe PE padne ispod doweg praga (Low-Water-Mark). Svaki PE p, ~iji su susjedni PEn , sra~unava parametar udaqenosti i proximity(PEp) = min {proximity( PE n )} + 1 i i koji ne mo`e prema{iti vrijednost Wmax. Sistem ne zahtijeva balansirawe optere}ewa, ako svi PE imaju vrijednost parametra udaqenosti Wmax. Ako se udaqenost PE mijewa, on mora izvijestiti svoje susjede, {to uzrokuje lanac izmjena parametra udaqenosti u PE sistema. Isplativnost transfera mo`e da se kontroli{e pragovima LWM i HWM (Low/High-Water- Mark), tako {to se transfer zadataka od preoptere}enog PEp ka neoptere}enom PEq vr{i ako je L p - L q > HWM - LWM gdje su L p i L q optere}ewa PEp i PEq. Prosqe|ivawe optere}ewa (zadataka) od PEp ka PEq vr{i se na osnovu minimalnog gradijenta udaqenosti, {to rezultuje transferom optere}ewa najkra}im putem do najbli`eg neoptere}enog procesora. Iznos optere}ewa koji se prenosi sa preoptere}enog na neoptere}eni PE mo`e se razli~ito selektovati u razli~itim implementacionim varijantama: kao procenat teku}eg optere}ewa, fiksan broj zadataka i sl. Primjer ovog modela dat je na Sl. 8.12, gdje dva preoptere}ena procesora prenose dio optere}ewa ( δ ) najbli`im putem do neoptere}enog PE. 8.4 Dinami~ko raspore|ivawe 218 2 1 2 3 1 0 1 2 2 1 2 3 3 2 3 4 Sl. 8.12 Gradijentna difuzija. Hijerarhijski metod balansirawa kreira hijerarhijsku strukturu domena balansirawa. Odre|enim procesorima se dodjequje nadle`nost za balansirawe domena na razli~itim hijerarhijskim nivoima (Sl. 8.13). 0 3 0 4 2 0 2 4 6 1 0 1 2 3 4 5 6 7 0 Sl. 8.13 Hijerarhijski metod balansirawa optere}ewa. Informacije o optere}ewu pojedinih PE/domena dobijaju se na osnovu poruka o stawu optere}ewa na ni`im nivoima. U slu~aju da dva domena istog (ni`eg) nivoa imaju razli~ita optere}ewa, onda se na osnovu vrijednosti te razlike donosi odluka (na prvom vi{em nivou) o balansirawu optere}ewa izme|u domena. ^vor nadle`an za balansirawe obavje{tava Raspore|ivawe zadataka na procesore 219 preoptere}eni domen o koli~ini preoptre}ewa koje je potrebno prebaciti na neoptere}eni domen. Svaki procesor iz preoptere}enog domena ima svoj odgovaraju}i par u korespondentnom neoptere}enom domenu, kome prenosi svoj dio preoptere}ewa. Dakle, globalno balansirawe se posti`e pewawem ka vrhu hijerarhije i balansirawem optere}ewa izme|u susjednih domena na svakom nivou. Ova {ema ukqu~uje sve procesore u proces balansirawa, i ostvaruje kako lokalni tako i globalni balans na nivou cijelog sistema. Odre|eni domeni hijerarhijske strukture mogu biti u mawoj ili ve}oj mjeri izolovani iz procesa balansirawa, postavqawem odgovaraju}ih parametara.