STOHASTIČNI PRISTOP K ANALIZI UČINKOVITOSTI VEČPROCESORSKIH SISTEMOV INF0RMATICA1/88 UDK 681.324:519.21 Slavko Mavric Peter Kolbezen institut »Jožef Štefan« Predstavljen Je stohastidni pristop pri modeliranju in analizi učinkovitosti veiprocesarskih sistemov s skupnim pomnilnikom, pri katerih Je vsakemu procesorju pridru±en Se njegov zasebni pomnilnik. Zgrajen je model veiprocesorskega sistema in de-finiran njegov re±im delovanja. Postopek analize temelji na opisu tega modela s etohastiino Petrijevo mreto. Iz drevesa dosegljivosti te mreže dobimo parametre pripadajoče markovske' ver ige. Analiza stacionarnega stanja te verige pa nas pripelje do iskanega pokazatelja učinkovitosti večprocesorskega sistema. Stochastic Approach in Per-formance AnalyBis o-f MultiprocBEsor SyEtema. A stochastic approach in modelling and per-formance analYSis o-f global memary based mul t i processor systems is presented. Every processor o-f such a 5ystem possesses its own private memory. A model o-f system has been built and its workload has been de-fined. Description o-f system activity with stochastic Petri net is the -first step in a per-formance analysis. From the reachability tree o-f this Petri net it is possible to obtain parameters o-f associated Markov chain. Steady state analysis o-f this chain leads us •finally to a desired performance indeK.o-f a mul tipročessor system. 1. Uvod Pri ocenjevanju učinkovitosti računalniških sistemov srečamo tri osnovne pristope. To so! merjenje, simulacija in analitično modeliranje. Prvi pristop vključuje meritve na samem sistemu pod dejanskimi delovnimi pogoji ter primerjalno merjenje s testnimi (benchnark) programi. Oboje zahteva popolno okolje ocenjevanega sistema. Pri simulaciji opifeemo dogajanje v računalniškem sistemu s si mulacijskim programom. Pri tem so nam navadno v pomoč temu namenjeni programski Jeziki. Iz izvajanja sifflulaciJBkega programa sklepamo o lastnostih simuliranega sistema. Analitični model predstavlja z matematičnimi orodji opisano dogajanje v sistemu. Ocena učinkovitosti sistema nastopa kot analitična ali numerična rešitev tega modela. Velik pomen analitičnega modeliranja je v dejstvu, da ga lahko opravimo ±B V zelo zgodnji -fazi načrtovanja računalniškega sistema in nam je v pomoč pri izbiri optimalne arhitekture. V tem članku predstavljamo stohastični pristop k modeliranju in analizi večprocesorskih sistemov na osnovi markovskih procesov. 2. Določan ie fnodal a vačprocpgorBkpoa »ictema Prvi korak pri ocenjevanju učinkovitosti nekega večprocesorskega sistema je v določitvi njegovega modela, ki mora zajeti vse bistvene lastnosti sistema. Mad*el mora de-finirati množico sistemskih gradnikov, njih medsebojne povezave in razmerja ter režim delovanja celotnega sistema. Pri tem se moramo odločiti za primeren nivo abstrakcije predstavitve sistema. Nivo abstrakcije pomeni nivo detajlov, ki jih pri opisu sistema upoštevamo. Ta naj določa kaj so gradniki sistema ter kakšna so njihova medsebojna razmerja in pravila komunikacije. Nivo abstrakcije izberemo tako, ti sodelujejo Opis modela je podan s parametri, ki govore č hitrosti, kapaciteti in zakasnitvi posameznit da nam bo analiza na osnovi izbranega modela dala kot rezultat nek parameter, ki bo dovolj dobro opisoval učinkovitost sistema. Model mora torej vsebovati vse bistvene elemente, ki so za analizo potrebni, vse detajle, ki na tem nivoju abstrakcije niso pomembni, pa naj model ne zajame. Pri vrednotenju učinkovitosti računalniških sistemov lahko zasledimo različne nivoje abstrakcije: - Aparaturni nivo. Ta nivo se nanaša na preizkušanje pravilosti nekega vezja z logičnega stališča. Gradniki modela tega nivoja so posamezna integrirana vezja. Za opis takega modela obstajajo posebni programski jeziki. - Funkcionalni nivo. Cilj analize na tem nivoju je ovrednotenje obnašanja osnovnih funkcionalnih enot aparaturne opreme, kot so procesorji, pomnilniške enote, vodila itd., ko pri izvajanju neke operacije. o enot. - - '^ - Sistemski nivo.- Na tem nivoju se ovrednoti učinkovitost celotnega sistema na osnovi poznanih funkcij posameznih enot. Osnovni gradniki modela so aparaturno/programske enote, kot procesne enote,. vhodno/izhodne in komunikacijske enote. Izbira najprimernejšega nivoja abstrakcije pri modeliranju nekega sistema Je odvisna od razmerja med točnostjo rezultatov na eni strani in kompleksnostjo ter ceno analize na drugi strani. Za ovrednotenje učinkovitosti večprocesorskega sistema nam ni potrebno poznati detajlov na nivoju posameznih integriranih vezij, prav tako pa za splošno namenski sistem ne potrebujemo natančno poznavanje aktivnosti sistema v realnem okolju neke aplikacije. Zato je funkcionalni nivo za analizo učinkovitostivečprocesorskih sistemov najpri merneJši. Osnovne predpostavke, na katerih temelji naš model večprocesorskega sistema so naslednjei osnovni gradniki modela so procesorji, pomnilniške enote in povezovalna mreža. 26 - vsak procesor P ima svoj zasebni pomnilnik 2P, ki Je dostopen le njemuu - vsak procesor lahko zahteva dostop do neke skupne pomniIniSke enot« SP, ki mu je dostopna. - pomnilnižka enota sprejme in po njej lastnem pravilu servisira zahteve posameznih procesorjev. povezovalna mreta PM povezuje procesorje in skupne pomniInitke enote. Ce ni drugače rečeno, se predpostavlja, da so zakasnitve, ki jih vna4« povezovalna mreia, enake nit. BploSen model, ki zadoSta tem pogojem prikazuje slika 1. Ko jenivo abstrakcije določen in so s tem poznani gradniki modela in njih medsebojne povezave, je potrebno de-finirati še re±im delovanja tega modela. Pri sistemih, v katerih je vsakemu procesorju pridružen zasebni pomnilnik, izvajajo procesorji program iz tega pomnilnika. To izvajanja se prekinja s posegi v skupni pomnilnik. Aktivnost posameznega procesorja lahko smatramo kot zaporedje dostopov do različnih pomniIniSkih enot. Model režima delovanja nekega procesorja je torej v ponavljajočem izvajanju naslednje sekvence: dostop, ali zaporedje dostopov v zasebni pomniIni k dostop, ali zaporedje dostopov v skupni pomniIni k Konfliktna situacija lahko nastopi pri uporabi povezovalne mreže ali skupnih pomnilniftkih enot. Vsak procesor je tekom delovanja v sploSnem v enem izmed naslednjih treh stanj; - Aktivno stanje. Procesor izvaja program iz svojega zasebnega pomnilnika. - Stanje dostopa. Procesor izvaja bralno ali vpisovalno operacijo na neki skupni pomnilniSki enoti. - Čakajoče stanje. Procesor čaka na zahtevani dostop do skupne pomniIniSke enote. Takšna aktivnost procesorjev na -funkcionalnem nivoju je lahko posledica povsem različnega obnašanja na sistemskem nivoju. Zamislimo si tri večprocesorske sisteme. Pri prvem poteka komunikacija med posli s pošiljanjem sporočil preko pomniIniških vmesnikov, lociranih v skupnem pomnilniku. Pri drugem sistemu izvajajo procesorji neko operacijo nad vhodnimi podatki, ki jih najdejo v skupnem pomnilniku; tja tudi shranjujejo vmesne rezultate. V tretjem sistemu pa izvajajo procesorji program iz hitrih 'cashe' pomnilnikov, ki se morajo občasno osveževati iz skupnega pomnilnika. Ce opazujemo obnašanje posameznega procesorja v vseh treh sistemih, zaključimo, da v vsakem primeru le-to rezultira v zaporedju dostopov do različnih pomnilniikih enot. Zaporedju dostopov v zasebni pomnilnik sledi zaporedje dostopov v skupni pomnilnik in obratno. Ti trije primeri kažejo, kako se lahko povsem različno delovanje večprocesorskega sistema na sistemskem nivoju, reducira na enako obnašanje na -funkcionalnem nivoju. Režim delovanja na funkcionalnem nivoju je torej v vseh treh primerih enak. Za ocenitev učinkovitosti večprocesorskega sistema na osnovi zgrajenega modela, moramo seveda najprej količinsko oceniti parametre tega modela. Pri našem -funkcionalnem modelu so ti parametri časi trajanja zaporedij dostopov do zasebnega in skupnega pomnilnika, ki v celoti popisujejo režim delovanja posameznih procesorjev. Tej oceni sledi postopek analize. Ta nas na osnovi teh parametrov in topološkega opisa sistema vodi k izračunu veličine, ki nam bo dala dovolj dober opis učinkovitosti večprocesorskega sistema. Imenujemo jo per-f ormančni pokazatelj. Pri določitvi režima delovanja, oziroma pri ocenitvi parametrov modela srečamo dva osnovna pristopa. Deterministični pristop zahteva natančno poznavanje delovanja vsakega procesorja. Dobra stran tega pristopa je v tem, da v popolnosti Slika 1. Splošen model večprocesorskega si stema sledimo obnašanju celega sistema in s simulacijo določamo čas, ki je potreben za dokončanje neke poznane operacije. Slabost determinističnega pristopa Je v dejstvu, da jo potrebno popolno poznavanje režima delovanja procesorjev, kar v času načrtovanja sistema ni vedno možno in da so dobljeni rezultati relevantni le za tisto aplikacijo in ne kažejo funkcijske odvisnosti od parametrov modela. Ce uporabimo verjetnostni pristop, obravnavamo parametre režima delovanja kot naključne spremenljivke z neko znano porazdelitvijo verjetnosti. Stohastični pristop nam ne omogoča tako natančnega vpogleda v izvajanje neke operacije v sistemu kot deterministični pristop, zato pa nam daje rezultate kot -funkcijske odvisnosti med parametri modela, in per-f ormančni mi pokazatelji. S tem nam pomaga k boljšemu razumevanju dogajanja v kompleksnem vsčprocesorskem sistemu. Stohastično analizo je moč opraviti že v zelo zgodnji -fazi razvoja samega sistema kot pomoč pri testiranju in primerjanju posameznih arhitekturnih različic s staližča izbranih per-f ormančnih pokazateljev. Verjetnostni pristop temelji na tem, da opišemo dogajanje v modelu z nekim stohastičnim procesom. Število stanj tega procesa js odvisno od števila vseh možnih sti>,nj, ki jih lahko doseže obravnavani večproc(='iiorski sistem, oziroma njegov model. Določiti moramo tudi medsebojne odviBnosti, oziroma pogojne verjetnosti med stanji procesa. Zaradi sprejemljive matematične kompleksnosti se za modeliranje podobnih sistemov pogosto uporablja razred stohastičnih procesov z markovsko lastnostjo, ki jim pravimo markovske veri ge. Harkgvake verige Def i ni ci je nanašajo na verig (CZMV prehodov med ko so prehodi verigah možni določeni z di zvezne veri dogajanja v n De-f i niči jo markovsko las Stohasti čni vel ja in rezultati tip časovno ). Pri njih stanji v vsak pri časovno d 1e ob posamez skretizaci jo č ga primernej ekem večproces CZMV, ki tnost, lahko z proces ŠX(t), tega poglavja se zveznih markovskih lahko prihaja do em trenutku, medtem iskretnih markovskih nih trenutkih, ki so asovne osi. Zato so še za opisovanje orskem sistemu. opisuje omenjeno apišemo takole. t>=0> je CZMV če PCX=>=«o> = = P-CX(tn + i)=Xn-HllX(tn)=«n>. tn-^l>tn>tn-l-> >to- (3.1) Ta markovska lastnost pomeni,da je verjetnostno 27 abnaianje procesa v prihodnosti odvisno samo od trenutnega stanja in ne tudi od zgodovina procesa. Desna gtran gornje enatbe predstavlja prehodno verjetnost med dvema stanjema veriga, ki jo za primer homogene CZMV (kjer so prehodna verjetnosti neodvisne od časa opazovanja) lahko zapi&emo v obliki Ei «1 = 1, i£S. (3.12) Pij(T) = P{X(t + 1>=j IX(t)=l}. (3.2) Vse prehodne verjetnosti verige lahko zapišemo v obliki matrike P(tl) » Cpij(ti)3. Seveda velja enakost Ej Pij«!) = 1, JsS. (3.3) Verjetnost stanja i v trenutku t je po teoremu o popolni verjetnosti podana z enačbo «1 (t) = Ej (Pji 0 (3.6) qij predstavlja v primeru i O j časovno gostoto prehodov e katero proces prehaja iz stanja 1 v stanj« j, medtem ko pomeni ~qii v primeru i = j časovno gostoto s katera proces zapušča stanje i. Velja enakost: Ej qij = O, j»S. (3.7) Iz enačbe 3.4 lahko, s tako de-f inirani mi qij, pridemo do enačbe za verjetnost nekega stanja i v poljubnem trenutku. S'i oo Tedaj tudi velja lim »i(t) =0 t->Oo (3.9) (3. 10) in tako pridemo do sistema linearnih enačb Ej t+T I Wi>t> = PT>. (3. 13) Edini porazdelitveni zakon, ki zadošča temu pogoju, je eksponentna porazdelitev. Gostoto verjetnosti te porazdelitve podaja enačba f(t) = a exp(-at), t >= O. (3.14) Lahko bi pokazali, da so časi trajanja posameznih stanj CZMV eksponentna porazdelJani a funkcijo gostote verjetnosti •fWi =0 <3.15) (3. 16) Analiza vačprocesorakih sistemov s pomočjo pridruženih markovskih verig pomeni torej predpostavko, da se čase trajanja aktivnih stanj in stanj dostopa obravnava kot eksponentno porazdeljene naključne spremenljivke. 4. StohastiCns Petr i j »ve mreža V nadaljevanju nas zanima vprašanje, kako na osnovi modela večprocesorskega sistema pridemo do pridružene markovske verigo. Direktna pot je lahko zelo zapletena, saj moramo evidentirati vsa stanja sistema in časovne gostote prehodov med njimi. Pomagamo si s stohastičnimi Petrijevimi mrežami (SPM), ki predstavljajo učinkovito orodje za opisovanje sočasnosti in sinhronizacije v paralelnih sistemih. BPM so nekakšna nadgradnja standardnih PetriJevih mrež v tem, da vpeljejo vanje dimenzijo časa kot naključno veličino. SPM Je bipartiten gra-f , ki ga sestavlja množica položajev P, množica prehodov T, množica povezav A,' množica prehodnih hitrosti Q in začetna označitev Mo- SPM je torej določena s peterko Pl tp-1)X (p.2)K 0,p-1,1,0 fx (O,p-1,1,0) •> f-p-1 Slika 5. Diagram prehajanja stanj markovske ver i ge Slika 4. Drevo dosegljivosti SPM Drevo dosegljivosti SPM nam popolnoma doloža CZMV s katero bomo ponazorili dogajanje v naSem vecprocesorskem sistemu, saj predstavlja dosegi jivostna množica prostor stanj CZMV, prehodne hitrosti drevesa dosegljivosti pa so enake časovnim gostotam prehodov verige. Diagram prehajanja stanj tako dobljene markovske verige prikazuje slika 5. Preden se lotimo reševanja markovske verige, se moramo odločiti za nek per-f ormančni pokazatelj, ki nam bo dal dovolj dobro informacijo o učinkovitosti vedprocesorskega sistema. Za ta pokazatelj smo izbrali povprečno število aktivnih procesorjev (procesorjev v aktivnem stanju) in ga imenovali procesna moč sistema P. Izračunamo jo po enačbi Ei (iTin-i (i ) ) , i eS, (4.1) 6. Zaključek Rezultati predstavljene stohastične analize EO dobljeni pod predpostavkami, navedenimi v poglavju 5. Te predpostavke so nam omogočile, da smo obravnavali dogajanje v vecprocesorskem sistemu kot markovski proces. Čeprav se realni sistemi v splošnem ne podrejajo tetn predpostavkam lahko uvidimo, da dajo markovski modeli navadno celo pesimistično oceno o učinkovitosti modeliranega sistema. Zakaj? V realnem sistemu ima porazdelitev časov dostopa navadno manjšo varianco v primeru z eksponentno porazdelitvijo. Tedaj je dejanska učinkovitost boljša, kot jo je napovedal naš model. Isto velja v. primeru, ko časi aktivnih stanj in stanj dostopa niso za vse procesorje enaki. Iz tega lahko zaključimo, da-dajejo rezultati, dobljeni na osnovi predstavljene stohastične analize, dovolj dobro oceno o učinkovitosti obravnavanega večprocesorskega sistema. kjer pomeni itj stacionarno verjetnost stanja i CZMV, n^Ci) pa število aktivnih procesorjev v stanju sistema, ki je ponazorjen z i-tim stanjem CZMV. Za izračun procesne moči rabimo torej stacionarne verjetnosti stanj verige, ki jih dobimo iz analize stacionarnega stanja CZMV. To opravimo z rešitvijo sistema linearnih enačb, ki jih lahko zapišemo direktno iz diagrama prehajanja stanj po enačbah .3.11 in 3.12. Dobimo sistem.p+1 enačb •p>>H,; pt 1 (4.2) uit i+1 -((p-i))i + uJITj + (p-i + nxilj-. 1 i = 1. . .p--l itO + Hi +...+ 1(p = 1. Splošna rešitev tega sistema je naslednja: fO = (Ci,; (f^' (p !/(p-k) ! ) )~^ , k=0...p Uj = troP^ . (4.3) Procesna moč pa je enaka P= (Ck (p''n!/(n-k) ! ) - 1 ) / < fEi,. (p'''n ! / (n-k ) I ) ) , k = O... p (4.4) Rezultat analize učinkovitosti našega večprocesorskega sistema je torej enačba, ki podaja odvisnost procesne moči od števila procesorjev in obremeni jivosti sistema. To pomeni, da lahko na podlagi rezultatov stohastične analize ocenimo učinkovitost sistema v različnem obsegu in pod različnimi delovnimi pogoji.' 7. Li teratura 1. Fel1er W., An Introduction to Probability Thsorv and Its Applications, Willey, New York, 1966. 2. Holliday M.A., Exact Performance Estimates -for Mul ti processor Momory and Bus I nter f erence , IEEE Transactions on Computers, Januar 19B7. 3. Jamnik R., Verjetnostni račun. Mladinska "knj.iQa, Ljubljana, 1971. 4. Kari in S., A First Course in Stochastic FTocesses, Academic F'ress, New Vork, 1975. 5. Marsan M.A. s sodelavci, Modeling Bus Cnntention and Memory Inter-f erence in a Mul tiprocessor. Bystem, IEEE Transactions on Computers, Januar 1983. 6. Marsan M. A. s sodel avci ,• Per-f ormance Modele of Mul tiprocessor • Systems, MIT Press, Camtaridge, London, 1986. 7. Peterson J.L., Petri Net Theary and the Modeling of Systems, Prentice-Hall, EngIewood Cli-ffs, 19B1. 8. Vidav I., Višja matematika II, DZS, Ljubljana, 1975. 9. Zuberek UI.M., Timed Petri Nets and Preliminary Performance Evaluation, Proč. of the 7th Annual SympDsium on Computer Architecture, La Baule, 1980.