Rinnakkainen tutkimus

Moniprosessoriympäristössä algoritmien rinnakkaisuus on vält­

tämättömyys, muutoin voitaisiin hyödyntää vain yhtä prosesso- Tämä voidaan tulkita koskemaan myös varmennettuja järjes­

telmiä, joissa prosessorit suorittavat samaa tehtävää. Näissä­

kin käsittely on rinnakkaista.

Varsinaiset moniprosessorijärjestelmät voidaan Flynnin mukaan jakaa kahteen osaan sen mukaan, suoritetaanko samaa käskysek-venssiä usealle eri datalle (SIMD) vai suoritetaanko samanai­

kaisesti myös eri käskyjä (MIMD). Edellinen voidaan määritel­

lä selkeästi, mutta jälkimmäinen jakautuu vielä useaan osit­

tain päällekkäiseen alaryhmään /9/.

Yleisin kriteerio luokiteltaessa MIMD-järjestelmiä on proses­

sorien keskinäisen liitännän väljyys. Yhteinen muisti sekä yhteinen syöttö/tulostuslaitteisto viittaisivat tämän mukaan lujaan sidokseen ja kommunikoinnin rajoittaminen vain tiet­

tyyn kommunikointikanavaan viittaa väljään sidokseen. Lipovs- kin /3/ mukaan oleellinen ero on kuitenkin siinä, että väljäs-

liitetyllä systeemillä ei ole keskitettyä systemin tilaa, vaan tila muodostuu kunkin prosessorin tilojen "summana".

Perusteluna väitteelleen Lipovski mainitsee mm. muistinhal- 1intayksiköt. Näiden avulla voidaan kunkin prosessorin tila suojata muilta yhtä tehokkaasti kuin erityistä kommunikoin­

tikanavaakin käyttäen, vaikka muisti olisikin laitteistota­

solla kytketty kaikkiin prosessoreihin tasavertaisesti. Tämä asettaa käyttöjärjestelmille entistä suuremman merkityksen vikojen leviämistä estettäessä.

Aiempien jaotteluiden tilalle ehdotetaan lokaalisuuksiin pe­

rustuvaa jaottelua. Lokaalisuus merkitsee varsinaisesti saan- tioikeuksia. Prosessorilla voi olla saantioikeudet tiettyihin oheislaitteisiin, muistiin tai yhteisiin kommunikointikana—

vün» Nämä kuuluvat tällöin kyseisen prosessorin lokaliteet—

t-i-j-1"1, Samat laitteet voivat kuulua muidenkin prosessorien lo—

kaliteettiin. Lokaalisuus voi olla staattista tai dynaamista.

Esimerkiksi muistiavaruuden hallinnassa dynaaminen lokaali—

suus tarkoittaa, että yhteismuistia voidaan tarpeen mukaan jakaa kullekin prosessorille lokaalimuistiksi. Dynaamisen lokaalisuuden hyötynä on suuri joustavuus erilaisten tehtä­

vien suhteen; staattinen lokaalisuus edellyttää laitteistol­

ta vähemmän, lisäksi operaatiot ovat nopeampia. Kumpaakaan ei

voi asettaa yleisesti toisensa edelle vaan molempia voidaan käyttää saman järjestelmän eri osissa.

Moniprosessoritutkimus on viime aikoina ollut voimakasta sel­

västi nähtävissä olevien tehokkuuden ja luotettavuuden kasvun vuoksi. Suurin alan tutkimuskeskus on ollut Carnegie-Mellon yliopisto Yhdysvalloissa kolmen koelaitteiston turvin. Tut­

kimusta on tehty myös muualla ja sovellutuskohteet ovat hyvin vaihtelevia. Seuraavaksi esitetään lyhyt katsaus muutamiin laitteistoihin, niiden ohjelmistoon ja päämotiiveihin.

2.2.1 C.mmp

C.mmp on Carnegie-Mellon yliopiston suunnittelema laitteisto /10/. Se koostuu kuudestatoista PDP-11 minitietokoneesta, jotka liittyvät yhteismuistiin ristiinkytketysti siten, että muisti jakautuu kuuteentoista lohkoon ja muistista luku voi tapahtua yhtäaikaisesti eri lohkoista. Laitteiston maksimi­

suorituskyky on 6 MIPS.

Projektin varsinaisena ansiona on pidettävä suunniteltua käyt­

töjärjestelmää tai käyttöjärjestelmän ydintä Hydraa, jonka ympärille on jo rakennettu useitakin täydellisiä käyttöjärjes­

telmiä .

Hydra ei tarjoa tavanomaisia käyttöjärjestelmän piirteitä, tiedostoja, komentokieltä tai edes ajoitinta. Hydra tarjoaa olosuhteet, joissa käyttäjän on helppo kirjoittaa ohjelmia, j°tka sisältävät nämä ominaisuudet. Perustyökaluna on käytet­

ty niinkutsuttuja oikeuksia; tietyllä ohjelmalla tai ohjelman osalla on oikeudet vain määrättyihin muistialueisiin ja mää­

rättyihin oheislaitteisiin sekä määrättyihin muihin ohjel­

miin. Näillä kutsutuilla ohjelmilla taasen saattaa olla oikeudet joihinkin eri ohjelmiin tai resursseihin. Ohjelmia kutsutaan oikeuksien avulla, varsinaisia osoitteita ei ole käytössä.

Kun ohjelmoija pyrkii sallimaan kullekin ohjelmalohkolle

mahdollisimman vähän oikeuksia, voidaan vikojen leviäminen eristää. Sovellutusohjelmoijalle suodaan mahdollisuus luoda uusia operaatioita ja tietotyyppejä, jotka ovat täysin

tasavertaisia Hydran valmiiksi toteutettujen operaatioiden kanssa. Sovellutusohjelmoijalle on pyritty jättämään

mahdollisimman useat sovellutusohjelmien suoritustapaan liittyvistä päätöksistä. Tämä on eräs olennaisin menetelmä turvattaessa järjestelmän yleiskäyttöisyys.

Päätavoitteina Hydran suunnittelussa on pidetty symmetrisyyt­

tä sekä yleiskäyttöisyyttä. Näiltä osin voitaneen sanoa, että Hydra on vaikuttanut olemassa olevista käyttöjärjestelmistä eniten esiteltävän käyttöjärjestelmän lähtökohtiin ja työtä edeltävässä kirjallisuustutkimuksesta Hydraa koskevat rapor­

tit ovat muodostaneet suuren osan.

C.mmp-projektin jälkitarkastelusta /11/ voidaan luetella seu- raavat ansiot: Suunniteltu moniprosessori on symmetrinen ja tehokkuuteensa nähden edullinen. Hydra on käyttökelpoinen valine, jonka avulla voidaan ohjelmoida käyttöjärjestelmiä tavallisten sovellutusohjelmien tapaan. Hydra on prosesso­

rien suhteen symmetrinen. Toisin sanoen prosessorit suorit­

tavat tarvitsemansa käyttöjärjestelmäoperaatiot riippumatta muista prosessoreista.

Negatiivisia seikkoja on myös myönnetty: Laitteisto ei ole min luotettava kuin olisi toivottu. PDP-11:n pieni osoite- avaruus on osoittautunut haitalliseksi. Tavoitteessa osittaa C.mmp:tä toiminnallisesti erillisiksi laitteistoiksi ei ole onnistuttu. Käyttäjäystävällisyyteen ei ole kiinnitetty riit­

tävästi huomiota.

2.2.2 Cm*

Toinen Carnegie-Mellon yliopiston moniprosessoriprojekti on Cm* /12/. Laitteisto koostuu LSI-11 prosessoreista, jotka on kytketty toisiinsa siten, että kukin prosessori voi puhutella

toistensa paikallismuistia hierarkisesti järjestetyn kytkin- verkon avulla. Verkkoon kytkettyjen prosessorien määrällä ei ole käytännössä ylärajaa. Verkossa muistiin viittaus saattaa kestää eri pituisia aikoja riippuen siitä, kuinka monen sol­

mupisteen kautta muistiin viitataan. Verkko huolehtii kunkin prosessorin saantioikeuksien täyttymisestä. Kuvassa 1 esite­

tään Cm*: n rakenne kun järjestelmässä on viisi prosessoriryh—

mää. Kukin ryhmä voi sisältää kymmenen prosessoria. Oheislait­

teet liittyvät yksittäisiin prosessoreihin.

SS Hriocu/sTZfi

4-> St и ro MOST

Kuva 1 Cm*: n arkkitehtuuri

Käyttöjärjestelmän suunnittelussa on suurin huomio kiinnitet­

ty osoitusmekanismeihin. Tämä onkin luonnollista, kun lait­

teistoarkkitehtuuri poikkeaa tavanomaisesta. Osoitusmekanis—

mien osalta on tavoitteina pidetty seuraavia seikkoja; Osoi- tusmekanismien on tuettava modulaarista ohjelmankehitystä;

ohjelman osia on voitava kääntää toisistaan erillään. Tietora­

kenteiden tulee olla vaihtelevan pituisia. Muisti on kyettävä

suojaamaan laitteisto- ja ohjelraavirheitä vastaan. Ohjelmia ja muistissa olevaa tietoa on pystyttävä puhuttelemaan eri ohjelmista eri nimillä vaikka fyysiset osoitteet ovat samoja.

Cm*:lie on suunniteltu kaksi käyttöjärjestelmää: StarOS ja Medusa. Osoitustavoiltaan Medusa on näistä kahdesta yksin­

kertaisempi. Siinä on päähuomio kiinnitetty tehtävien väli­

sen rinnakkaisuuden aikaansaamiselle. Samaan kokonaisuuteen liittyvät tehtävät allokoidaan prosessoreille, jotka ovat osoituksellisesti mahdollisimman lähellä suoritettavaa ohjel­

makoodia ja toisiaan.

StarOS:ssa tavoitteita on pyritty saavuttamaan käyttämällä segmentoitua osoitusta ja oikeuksia Hydran tavoin. Proses­

sorit puhuttelevat muistia oikeuksien avulla ja muistikyt- kimillä tarkistetaan kunkin prosessorin oikeudet ja kutakin oikeutta vastaava fyysinen osoite; oikeuksia voi luonnolli­

sesti muuttaa ohjelmallisesti, mutta sallitut muutokset on tarkkaan rajattu.

Käyttöjärjestelmät tukevat prosessorien välistä kommunikoin­

tia ns. postilaatikko—operaatioiden avulla. Semaforioperaa—

tiot on toteutettu muistikytkimissä olevalla mahdollisuudel­

la lukita tietyn muistilohkon osoitukset operaation suori­

tuksen ajaksi. Väylien lukitseminen operaation ajaksi olisi järjestelmän kannalta liian raskasta.

2.2.3 C.vmp

C.vmp on suppeimmin raportoitu Carnegie Mellon yliopiston moniprosessoriprojekteista. Suunnittelun päämäärät voidaan esittää seuraavasti /13/:

-Järjestelmän tulee voida jatkaa toimintaansa huolimatta pysyvästä laitteistoviasta.

-Pysyvistä ja tilapäisistä virheistä huolimatta järjestelmä ei saa tuottaa virheellisiä tuloksia.

-Käyttäjälle ei tule olla tarpeellista tietää, että hän ohjelmoi vikasietoista tietokonetta.

-Virheen tulee olla korjattavissa lyhyen ajanjakson sisällä.

-Tosiaikaisissa sovellutuksissa ei laitteiston toiminta saa pysähtyä liian pitkäksi ajaksi.

-Laitteiston tulee kyetä toimimaan siten, että se voidaan huoltaa aktiivisena. Toisin sanoen on voitava poistaa viallinen moduuli ja korvata se toisella toiminnan aikana.

-Kustannusten minimoimiseksi on järjestelmä voitava koota valmiista moduuleista.

-Järjestelmässä on voitava joustavasti valita luotettavan tai suorituskykyisen vaihtoehdon välillä ohjelmallisesti tai käyttäjän toimesta.

Näitä ominaisuuksia on tavoiteltu kuvan 2 mukaisella arkkiteh­

tuurilla, jossa äänestys on toteutettu väylätasolla. Äänestä­

minen tapahtuu aina, kun prosessori puhuttelee väylää. Proses­

sorit voivat suorittaa tehtäviä itsenäisestikin väylä-äänes­

tyksistä riippumatta. Muutoin prosessorit suorittavat samaa ohjelmaa. Äänestysyksikkö muodostaa luotettavuuden kannalta kriittisen osan.

Kuva 2 C

2.2.4 SRI SIFT

SIFT (Software Implemented Fault Tolerance) on lennonohjaus- soveHutuksiin suunniteltu vikasietoinen moniprosessori /14/.

Ilmailualan vaatimukset ohjausyksiköiden luotettavuudelle ovat erittäin tiukat : sallitaan 10E-9 virhettä tunnissa kun yhtäjaksoinen käyttö ilman huoltoa on enintään kymmenen

tuntia. Laitteessa on prosessorit kytketty toisiinsa usean väylän avulla. Prosessori voi lukea muiden prosessorien muistia mutta voi kirjoittaa vain omaa muistiaan.

Tyypillisesti tehtävä suoritetaan useassa moduulissa ja kukin prosessori kirjoittaa tuloksen omaan paikallismuistiinsa.

Tulosta käyttävä prosessori lukee kunkin muistista ehdotuksen ja valitsee niistä enemmistön kannan. Äänestys toteutetaan siis ohjelmallisesti. Ohjelmien tulee toimia synkroonissa toistensa kanssa (50us), jotta tarvittavat tulokset olisivat valmiit äänestyksiin. Ajoittainen uudelleensynkronointi on tarpeen prosessorikorttien kellotaajuuksien pienten poikkea­

mien vuoksi.

Tulostus tapahtuu erillisten moduulien avulla ja syöttö/tulos- tus~toiminnot ovatkin arkkitehtuurin kriittinen osa. Luotetta­

vuus on suurelta osin riippuvainen näiden moduulien toteutuk­

sesta.

2.2.5 FTMP

FTMP (Fault Tolerant Multiprocessor) on edellisen tavoin suun­

niteltu lentokonesovellutuksiin /15/. Järjestelmässä moduulit liittyvät toisiinsa varmennetuilla väylillä ja ne on ryhmitel­

ty kolmikoiksi. Jokaisessa kolmikossa on äänestin, joka valit­

see enemmistön kannan edelleen toimitettavaksi. Kolmikoita ei ole muodostettu kiinteästi vaan ryhmittelyä voidaan ajonaikai­

sesti muuttaa, jos jokin prosessoreista vikaantuu.

Varsinaisesti järjestelmä toteuttaa seuraavassa luvussa tar­

kemmin esiteltävää hybridivarmennuksen periaatetta. Moduulien välinen kommunikointi on sarjamuotoista. Äänestykset suorite­

taan bitti kerrallaan laitteistollisesti täysin synkronoidus­

ta Välttämättä tarvittava yhteinen kellosignaali on kriitti­

nen järjestelmän toiminnan kannalta. Äänestävien ohjelmien erilaisuus ei ole mahdollista.

In document Symmetrisen moniprosessorikäyttöjärjestelmän suunnittelu reaaliaikasovellutuksiin (sivua 9-17)