VME VODILO V VEČRAČUNALNIŠKIH ARHITEKTURAH M. COLNARIČ, I. ROZMAN, B. PREMZEL TEHNIŠKA FAKULTETA MARIBOR POVZETEK - Članek obravnava problematiko vodil v večprocesorskih sistemih s poudarkom na VME vodilu. To je prire- jeno za prloritetni in Round Robin arbitracijski algoritem z Daisy-Chain povezavo na posameznih nivojih. Ker je v no- vejših raziskavah utemeljeno, da tovrstni algoritem ne daje optimalnih rezultatov, so v članku nakazani možni načini realizacije drugih izbirnih pravil. AHSTRACT - In the article multiprocessor systems' buses are discussed with accent on the VME bus. It is designed for priority and Round Robin arbitration scheme with Daisy - Chained modules on each level. Since it is proved in recent research that this kind of algorithms are not optimal, some other arbitration protocols are described. UVOD Z razvojem mikroprocesorjev prevzemajo mikroraču- nalniški sistemi čedalje kompleksnejše nalocje. Marsi- katerih zahtev pa tudi najmočnejši procesorji ne morejo zadovoljiti. Iz tega razloga in ker jim cena nenehno upa- da so čedalje zanimivejši sistemi, kjer si več procesor- jev deli globalne resurse. Najpomembnejši med njimi je vodilo za prenos podatkov. Preko njega procesorji komunicirajo z drugimi resursf in med seboj. Vsak sistem z več procesorji mora reše- vati problem dodeljevanja vodila uporabnikom. Uspeš- nost reševanja tega problema v veliki meri vpliva na prepustnost celotnega sistema in je torej ena od najva- žnejših odločitev pri snovanju mikroračunalniškega si- stema. Hitrost je tudi vzrok, da ne uporabimo program- ske temveč aparaturno rešitev. Sistem za dodeljevanje vodila po vnaprej določeni shemi se imenuje arbitracija. Druge pomembne odločitve pri snovanju protokola vodila so še - sinhrono ali asinhrono vodilo: odločiti se moramo, ali bodo vse enote v računalniku delale z istim taktom, ki se prenaša po skupnem vodilu (sinhrono) ali bodo lah- ko njihove hitrosti različne (asinhrono). Sinhroni na- cin je bistveno enostavnejši, asinhroni pa omogoča ka~ sne.je vključevanje noveiših, hitrejših enot. - multipleksirano vodilo ali ne: ker zaradi same zasno- ve mikroprocesor in resursi ne potrebujejo istooasno na linijah naslova in podatkov, lahko po istih linijah pošljemo naprej adreso, nato pa vsebino teh celic. Za- radi manj linij je vodilo manjše, uporabi se manj vezij, vendar ne dosegamo takšnih hitrosti kot pri nemultiplek- siranih vodilili. Člonek teh problemov ne obravnava. Dotaknili se bomo le tematike arbitraže. SPLOŠNO O ARBITRACIJSKIH ALGORITMIH Glavni nalogi arbitracijskega sistema sta preprečiti isto- časno dostop dveh ali več procesorjev do vodila in do- deljevanje vodila procesorjem po vnaprej predpisanem optimalnem pravilu. Osnovne odločitve o tipu arbitracijskega algoritma so ve- zane na naravo naloge, ki bi jo naj opravljal. Če gre za sprotni sistem, nas bo zanimal prioritetni (ali vsaj delno prioritetni) algoritem, če želimo poslovni sistem z več procesorji in pametnim razdeljevanjem nalog, bo nam bolj ustrezal FIFO ali Round Robin algoritem (rotirajoči prioritetni algoritem).' Kot za pridobitev nas zanimajo tudi algoritmi za sproš- čanje vodila. Poznamo dva glavna principa - sprostitev, ko je prenos končan (release when done, RWD) in - sprostitev na zahtevo (release on request - ROR). Pri prvem enota, ki je zmagala v arbitracijskem postop- ku,sprost.i vodilo, ko je izvedla prenos podatkov, ne gle- de na to, katera enota je medtem zahtevala vodilo. l'ri drugem pa enota med prenosom podatkov spremlja Hnijo, preko kat.ere ji arbiter signalizira, da mnra prekiniti s 51 komunikacijo, ker je vodilo zahtevala po prioriteti višja enota. Iz samega delovanja vodila lahko sklepamo, da poleg vodi- la in čistih modulov obstaja še sistem, ki skrbi za arbi- tracijo. Ta arbitracijski sistem je lahko samostojni mo- dul, lahko pa je porazdeljen na vse potencialneuporabnike vodila. Glede na način povezave modulov nanj ločimo ne- kaj osnovnih tipov: - Zvezdasta povezava: Vse naprave, ki lahko zahtevajo vodilo, so povczane na arbiter mimo vodila s po dvema posebnima linijama. Po eni enota zahteva vodilo (Bus Request), po drugi do- bi odobritev (Bus Grant). Protokol je izredno enostaven, arbiter lahko dela po kakrčnikoli metodi. Slabe strani so drago posebno ožičenje, na vodilu ni informacije o . teiti, kdo trenutno zaseda, na arbiter ni mogoče pro- gramsko vplivati. Slika 1: Zvezdasta povezava na arbiter Daisy chain: Na vsakem konektorju ]e par priključkov za arbitražo. Signal s prejšnjega konektorja gre na en priključek, z drugega pa na naslednji konektor. Na ta način je reali- MLBITEIL Slika 2: Daisy chain zirana zaporedna povezava modulov. Kadar hoče naprava vodilo, pošlje po "wire - OR" liniji signal arbitru in čaka na odobritev na vhodnem priključku. Vsak modul ima vhodni in izhodni priključek kratko sta- knjen, razen če tudi sam želi vodilo. Kadar torej dve ali več naprav istočasno pošljeta zahtevo po vodilu, ga bo do- bila tista, katere konektor je fizično bližje arbitru. Slabosti tega sistema so: - počasnost, saj vsaka plošča doda nekaj zakasnitve, do- kler se signal ne vrne do enote, ki je zahtevala vodilo - v vsakem konektorju mora biti plošča ali slepi konek- tor s prevezo, ki omogoči prenos signala - o arbitraciji je na liniji še vedno malo podatkov. - Shema z naslovno - prioritetnimi linijami To posebno shemo uporablja več sodobnejših vodil in tu- di standard IEEE P 896 Futurebus. Na vodilu je 4 do 8 arbitracijskih linij, na katere skušajo posamezni modu- li vpisovati svoje prioritetne številke po posebnem algo- ritmu, opisanem v 4. poglavju. Čigar številka je ostala na vodilu, je dobil odobritev za prenos podatkov. Razši- ritev osnovnega algoritma, da se moduli po principu "poštenosti" sami odpovedujejo vodilu in s tem omogo- čajo, da tudi moduli z nlžjimi prioritetnimi številkami dobijo dostop do vodila, bistveno izboljšanje lastnosti, povezane s sodobnimi izsledki o primernosti posamez- nih arbitracijskih algoritmov. S tem se namreč pribli- žujemo enakopravnosti modulov. Prioritete ostanejo le za reševanje istočasnih zahtev vodila. VOOILD 2A PMNOS C P1 PZ P3 SHka 3: Naslovno prioritetna arbitraža ARBITRACIJSKI ALGORITEM PRI VME VODILU Eno najbolj znanih vodil je gotovo VME vodilo. Njegov raz- voj sega v pozna sedemdeseta leta, ko je pri Motoroli skupinn inženirjev razvijala Exormacs na osnovi 52 MC 68000 procesorja. Njegovo vodilo se je imenovalo VERSAbus. Kmalu pa so v evropskih podružnicah Motoro- le ugotovili, da se VERSAbus ne bo obnesel kot standard, zato so ga prenesli na evropski format tiskanega vezja in ga imenovali VME. Leta 1983 je 1EEE začeln postopek za standardizacijo VME vodila ter mu dala šifro P1014. Spre- jetje standarda se pričakuje konec leta 1985. Istočasno bi ga naj sprejela tudi 1BC. VME sistem je sestavljen iz štirih skupin signalnih linij (vodil) in zbirke funkcionalnih modulov, ki predstavljajo vmesnike med napravami in vodili. Štiri vodila, ki sestavljajo VME vodilo, so vodilo za pre- nos podatkov (DTD - Data Transfer Dus), arbitracijsko vodilo, prioritetno prekinitveno ter vodilo za notranje po- trebe (ura, inicializacija, napake ipd—). Viodilo je bilo prvotno namenjeno enoprocesorskim siste- mom, v katerih so določene enote lahko zahtevale prenos podatkov (npr.DMA kontrolerji, disk kontrolerji itd...). Z razvojem večprocesorskih sistemov pa se VME vodilo uporablja tudi zanje. Arbiter na VME vodilu je lahko izvedcn kot ena od treh opcij: - PRI (prioritetni algoritem): arbiter dodeli vodilo po stalnih prioritetah modulov, ki dajejo zahleve na linije, od najvišje (DR3 ) do najnižje (nRO ) - RRS (Round Robin Select): arbiter dodeljuje vodilo po principu rotirajočih prioritet. Če je imel vodilo modul na nivoju N, bo imel najvišjo prioriteto modul na nivo- ju N-l, dokler ne pridemo do začetka (N = 0). Tedaj ima najvišjo prioriteto spet N = 3. - ONE (edini nivo): arbiter upošteva samo linijo BR 3 in obravnava Daisy Chain strukturo na tem nivoju. Arbiter je vedno v fizičnoprvem konektorju nn vodilu. To je povezano s principom Daisy Chain. Lahko je samostoj- na plošča ali pa le razširitev univerzalne procesorske plošče, ki izpolnjuje zahteve minimalnega arbitra. Razen pri opciji ONE arbiter sprejema zahteve po vodilu na štirih linijah BR0 do BR3, ki so izvedene v tehniki z od- prtitn kolektorjem, tako, da lahko povežemo izhode več modulov. Vsaka linija ima odgovarjajočo.linijo za odobri- tev vodila (BGx-grant), izvedeno kot Daisy Chain. Če je vodilo prosto, ko je arbiter dobil zahtevo, takoj pošlje grant po ustrezni liniji. Signal potuje med moduli, ki imajo vhodne in izhodne linije sklenjene, dokler ne naleti na. modul, ki je nanj čakal. Ta dobi vodilo. Ko ga je ne- hal uporabljati, fja sprosti in pošlje grant za naslednjo zahtevo. Informacijo o zasedenosti vodila nosi linija BHS4 (Bus Busy). Arbiter lahko pri prioritetnem načinu tudi zahteva takojšnjo sprostitev vodila po liniji BCLR (Bns Clear), kar odgovarja načinu sproščanja na zahtevo (IIC)H). i DUT If BSx P1 Bft« Baa. P2. I OUT ' k- Slika 4: Shematski prikaz delovanja arbitracijske shome na VME vodilu za eno Daisy Chain linijo Za arbitražo lahko uporabimo prioritetni ali krožni (Round Robin) algoritem. Na vsakem od nivojev se ustva- ri Daisy Chain struktura, pri čemer ima modul, ki jo bližje arbitru, višjo prioriteto, oziroma bo večkrat do- bil odobritev za uporabo vodila. Novejše raziskave kaže- jo, da prioritetni način ni najoptimalnejši pri dodeljevan- ju resursov. To ne velja za sprotne sisteme, kjer zaradi naravetaakov mora obstajati prioritetna lestvica. Kaj- večja prepustnost sistemov se doseže pri enakovrednosti procesorjev in ustrezni razdelitvi nalog med njimi. V ta namen bi bil najustreznejši arbitracijski algoritem čakal- na vrsta po principu FIFO.Te pa s konceptom, kot ga ima VME vodilo, ni mogoče uresničiti. Sam problem nastopi pri tesni povezanosti procesorja v sistemu. Če dodamo vsakemu procesorju svoj del lokal- nega pomnilnika in tako samostojne naloge, da ne bo po- gosto zahteval povezave z drugimi moduli, bo vodilo raz- meroma nezadostno in se bo vrsta le redko zgradila. Te- daj strežni algoritem ne bo imel prehudega vpliva na pre- pustnost sistema. Tipični primer takšne arhitekture so računalniški sistemi za vodenje robotov. Pogosta je zasnova, kjer vsako os robota vodi svoj raču- nalnik, vsi pa so povezani preko VME vodila s skupnimi globalnimi resursi - globalni pomnilnik, disk in drurja periferija. Vsak računalnik je na nivoju premikov svoje osi avtonomen, ima svoj lokalni pomnilnik in riirpktno upravlja preko vmesnikov z izvršilnimi orrjani. Sklnplje- 53 nost sistema je v tem primeru še dovolj lahka, da slabe strani prioritetne sheme ne pridejo usodno do izraza. SPLOŠNEJŠI ARBITRACIJSKI ALGORITEM Ker so večprocesorski sistemi vse številnejši, je nasta- la potreba po novem vodilu, namenjenem prav zanje. V ta namen so pri IEEE ustanovili posebno komisijo, ki raz- vija novo standardno vodilo IEEE P896. Osnovna ideja o arbitraciji datira v leto 1966. Kasneje je bila predelana in prirejena za sodobne zahteve ter upo- rabljena v standardih IEEE 696, P896 ter v NuBus (Texas Instruments) in Multibus II (Intel). Vsaka enota ima svojo N-bitno arbitracijsko številko, vo- dilo pa N-bitno arbitracijsko vodilo na principu odprtega kolektorja. Ko dobi enota, ki je zahtevala vodila, signal za začetek arbitracije, skuša na arbitracijske linije vpi- sati svojo številko. Če je na vodilu že višja prioriteta, kot je njena, umakne manj pomembne bite. Enoti, katere prioriteta ostane na vbdilu ob koncu arbitracije, ae dovO.li: prenos podatkov. Predno ta sprosti vodilo, sproži ponov- no arbitracijo, ki omogoči naslednji najpomembnejši eno- ti dostop do vodila. Ker smo s tem pravilom še vedno pri prioritetah mu do- damo še pravilo "poštenja", ki prepoveduje enoti, ki rii- ma izrecne časovne omejitve, zahtevati vodilo, ki ga je sprostila, dokler ga ne dobijo vsi drugi prosilci. Na ta način dobimo gotovo najpopolnejšo vodilo, vendar z naj- bolj zapletenim arbitracijskim vezjem, ki mora biti na vsakem modulu v sistemu. Na tem mestu je treba razčistiti s pojmom prioritete na vodilu. Namen prioritet v zvezi s pravilom "poštenosti" je rešiti problem istočasnih zahtev. V zgoraj opisanem sistemu ima prioriteta malo skupnega z odločanjem, ka- tera enota bo največkrat dobila vodilo in nima nič skupne- ga s prioriteto taskov. Taski z nizko prioriteto imajo mno- gokrat na vodilu visoko prioriteto (masovni prenosi po- datkov itd...). ZAKLJUCEK: VME vodilo je bilo koncipirano za enoprocesorske siste- me. Sam koncept sicer podpira tudi večprocesorsko ar- hitekturo, vendar ne moremo doseči optimalne propust- nosti, kot jo teoretično lahko določimo. VME sistem pa ima druge prednosti. Ker je kot standard izredno široko razširjen in priznan, obstaja na tržišču mnogo modulov, ki jih lahko uporabimo. Od zahtevnosti problema, ki bi ga radi rešili z našim računalnikom bo odvisno, ali se bomo zadovoljili z VME ali bomo iskali optimalnejše arbitracijske algoritme. LITERATURA /1/Rozman, I., Colnarič, M.: Modeliranje MP/MC arhi- tektur s skupnim vodilom, Jugoslovanski mednarodni simpozij za računalniško tehnologijo in probleme in- formatike, Informatica 83, Ljubljana 1983, str. 14-18 /2/ Colnarič, M., Rozman, I.; Simulacija multiproce- sorskega računalnika s skupnim vodilom, Jogoslo- venskD savetovanje o mikroprocesorskim sistemima MIPRO 83, Rijeka 1983, str. 2.32 - 2.38 /3/Rozman, I., Colnarič, M., Donačič, D.: Analiza učinkovitosti arhitekture s skupnim vodilom pri sta- tistično neenakem.zasedanju vodila, Jugoslovensko savjetovanje o mikroprocesorskim sistemima MIPHO 84, Rijeka 1984, str. 3.80 - 3.84 /4/ VMEbus Manufacturers Group: VMEbus Specification Manual, Rev. B, August 1982 /5/ Gustavson, D.R.: Computer Busses - A Tutorial, IEEE MICRO, August 1984, str. 7-22 /6/ Taub, D. M.: Arbitration and Control Aquisition in the Proposed IEEE 896 Futurebus, IEEE MICRO, August 1984, str. 28 - 41 /7/ Fischer, W.: IEEE PlOH - A Standard for the High- - Performance VME Bus, IEEE MICRO, February 1985, str. 31-41