S-114.240 Rinnakkaislaskenta laskennallisessa tieteessä
 

Suunnittelun kvantitatiivinen perusta

Perustuen Fosterin kirjan lukuun 3

Heikki Waris


 

Sisällysluettelo

 Yleistä

 Amdahlin laki
 Havainnoista ekstrapolointi
 Asymptoottinen analyysi
 Malleista

 Mallien parametrit ja suunnittelu

 Suoritusaika
 Laskenta-aika
 Viestintäaika
 Joutokäynti
 Esimerkki finite difference algoritmilla
 Tehokkuus ja nopeutus
 Skaalautuvuusanalyysi
 Skaalautuvuus kiinteällä ongelman koolla
 Skaalautuvuus skaalatulla ongelman koolla
 Suoritusprofiili

 Mallien käyttö

 Kokeelliset tutkimukset
 Kokeellinen suunnittelu
 Kokeellisten tietojen kerääminen ja tarkistus
 Tietojen sovittaminen malleihin
 Implementointien arviointi
 Ylimääräinen overhead
 Nopeutuksen anomaliat
 Korjattu viestintäkustannusmalli
 Ristikytkentäverkko
 Väylään perustuvat verkot
 Ethernet
 Mesh verkot
 Hyperkuutioverkko
 Moniportaiset välikytkentäverkot
 Kilpailu kaistasta finite difference algoritmissa
 Kilpailu kaistasta finite butterfly-rakenteessa
 Input/Output

 Esimerkki algoritmien vertailusta mallien avulla

 Shortest path algoritmit
 Rinnakkais-Floyd 1
 Rinnakkais-Floyd 2
 Rinnakkais-Dijkstra 1
 Rinnakkais-Dijkstra 2
 Vertailua

 Yhteenveto
 Lähteet

Yleistä

Rinnakkaisohjelmoinnissa pyritään harvoin optimoimaan jokin yksittäinen piirre. Joudutaan tekemään kompromisseja eri tekijöiden välillä. Suorituskykymalleilla voidaan välttää virheinvestointeja myöhemmin huonoiksi osoittautuviin implementointeihin.

Suorituskyvyllä voidaan tarkoittaa useita eri asioita kuten suoritusaikaa; laskennallisten kerneleiden skaalautuvuutta; mekanismeja tiedon luomiseksi, siirtämiseksi verkossa tai levylle tai ohjelman vaiheiden välillä; kustannuksia ohjelmiston elinkaaren eri vaiheissa. Kokonaisuudessaan aiheeseen liittyy suuri määrä mittareita, joiden painoarvo riippuu kulloisenkin ongelman luonteesta. Usein esiin nousee kuitenkin kaksi mittaa, suoritusaika ja rinnakkainen skaalautuvuus. Näistä on myös helppo rakentaa matemaattisia malleja.

Käytetään jatkossa seuraavia merkintöjä:

Amdahlin laki

Kaikilla algoritmeilla on jokin peräkkäiskomponentti joka rajoittaa nopeutusta (nopeutus tarkoittaa suoritusaikojen suhdetta yhden ja useamman prosessorin tapauksessa, esim. 5% peräkkäiskomponentista saadaan nopeutukseksi 20). Amdahlin lain mukaan tämä suhde määrää suurimman mahdollisen nopeutuksen. Koska toisaalta laskennalliseen ongelmaan voidaan löytää rinnakkainen ratkaisu, tämä laki ei pidä aina paikkaansa. Jos peräkkäisohjelmaa rinnakkaistetaan osa (yleensä laskennallisesti monimutkaisin osa ensin) kerrallaan kunnes haluttu suorituskyky saavutetaan, laki pätee. Tällainen ohjelmointitapa sopii lähinnä pieniin rinnakkaiskoneisiin. Kaavana S(P)=(s+p)/(s+w(P)+p/P).

Havainnoista ekstrapolointi

Nopeutus tietyllä kokoonpanolla (rinnakkaiskone, prosessorimäärä ja ongelman koko) ei tarkoita että algoritmin käytöstä voisi ennustaa muissa kokoonpanoissa. Eri algoritmien vaatimissa laskentamäärissä voi olla vakiokomponentteja ja ongelman kokoon sekä prosessorien määrään sidottuja tekijöitä jolloin tehokkaimman algoritmin valinta riippuu edellä mainituista tekijöistä (pienelle ongelmalle hyvässä algoritmissa vakiokomponentti on pieni jne.). Nopeutus pysyy lähes aina suoraan prosessoreiden lukumäärien suhteesta riippuvan ideaalitapauksen alapuolella (poikkeuksena superlineaarinen nopeutus).

Asymptoottinen analyysi

Kirjallisuudessa voi törmätä algoritmien osalta seuraavan tyyppisiin väitteisiin, jotka pätevät lähinnä suurille N ja P: "tietyille vakiolle c ja ongelman minimikoolle N0 pätee, että N prosessorilla kaikille NN0 kustannus(N) <= cNlogN" Tämä tieto ei ole välttämättä relevantti pienemmille käytännön ongelmille. Jälleen kustannuksissa voi olla muita komponentteja, jotka nousevat merkitseviksi pienillä N ja P. Lisäksi asymptoottinen analyysi ei kerro mitään absoluuttisista kustannuksista. Huomiota on kiinnitettävä myös konetyyppiin, jossa tulokset on saatu.

Malleista

Hyvä malli selittää havainnot ja ennustaa tulevaa häivyttäen samalla merkityksettömät detaljit. Edellä mainitut mallit eivät täytä näitä vaatimuksia. Toisaalta tavanomaiset mallinnustekniikat tuovat käytännössä simulaatioihin liikaa detaljeja rinnakkaislaskentaa ajatellen.

Suoritusaikaa alkaa ensimmäisen prosessorin suorituksen aloittaessa ja päättyy viimeisen prosessorin lopettaessa. Kunkin prosessorin aika koostuu tuona aikana laskemisesta, viestimisestä ja joutokäynnistä. Kokonaissuoritusaika voidaan määritellä joko yksittäisen prosessorin aikakomponenttien summana (T= Ticomp+ Ticomm+ Tiidle) tai käyttökelpoisemmin näin saatujen aikojen keskiarvona (summataan ja jaetaan prosessoreiden lukumäärällä).

Mallien parametrit ja suunnittelu

Suoritusaika

Laskenta-aika

Peräkkäisohjelmassa, joka laskee samoin kuin rinnakkaisalgoritmi voidaan määrittää Tcomp ajastamalla kyseistä ohjelmaa. Muulloin on yritettävä saada ajastukset suoraan kunkin prosessorin kerneliltä. Laskenta-aika riippuu tyypillisesti ongelman koosta ja mikäli algoritmi monistaa laskentaa, myös tehtävien ja prosessoreiden lukumäärästä. Työasemaverkoissa ja muissa heterogeenisissä rinnakkaiskoneissa vaihtelua aiheutuu myös prosessorityypeistä. Lisäksi skaalaaminen voi muuttaa esim. välimuistin suorituskykyä.

Viestintäaika

Tämä voidaan jakaa prosessorin sisäiseen ja prosessoreiden väliseen viestintään. Useissa koneissa nämä voidaan olettaa verrannollisiksi, mutta esim. Ethernetillä kytketyissä työasemissa sisäinen viestintä on huomattavasti nopeampaa. Ideaalimallissa aikakustannukseen käytetään viestin käynnistysaikaa ts (latenssi) ja tavukohtaista siirtoaikaa tw jolloin L tavun viestin siirtoon kuluu aikaa Tmsg= ts+ twL. Mittaukset ovat osoittaneet, että ts ja tw vaihtelevat huomattavasti koneesta toiseen. Riippuu sovelluksesta, kumpi komponentti on merkittävämpi.

Kuva 1. Edestakainen kulkuaika kahden prosessorin välillä viestin pituuden funktiona. Ethernet, FDDI, Intel Paragon, IBM SP1. W.Gropp

Joutokäynti

Tätä voi olla vaikeampi määritellä, sillä se riippuu operaatioiden suoritustavasta. Jos se johtuu laskennan puutteesta, voidaan käyttää kuormantasaustekniikoita. Jos syy on datan puutteessa, ohjelma pitää tehdä rakenteeltaan sellaiseksi, että prosessorit voivat suorittaa laskentatehtäviä odotellessaan tietoja. Jos aikakustannus vaihdosta uuteen tehtävään on pienempi kuin joutokäyntikustannus, jokaiselle prosessorille voidaan luoda useita tehtäviä joita voi suorittaa muiden tietoja odotellessa. Vaihtoehtoisesti voidaan rakentaa ohjelma siten, että tietojen lähetyspyynnöt tehdään riittävän hyvissä ajoin jolloin ne ovat käytettävissä oikea-aikaisesti.

Esimerkki finite difference –algoritmilla

Oletetaan NxNxZ –ristikko. Jaetaan tämä yhdessä horisontaalidimensiossa eri tehtäville (P kpl), joille jokaiselle tulee Nx(N/P)xZ –aliristikko. Jokainen tehtävä suorittaa saman laskennan kullekin ristikon pisteelle jokaisella ajanhetkellä. Koska laskentaa ei ole monistettu, yhden aika-askeleen laskenta-ajaksi saadaan Tcomp= tcN2Z, missä tc on yksittäisen ristikon pisteen laskemiseen keskimäärin käytetty aika. 9 pisteen stencilillä jokainen tehtävä vaihtaa naapureidensa kanssa 2NZ datapistettä eli yhteensä 4NZ pistettä (oletetaan että aliristikko vähintään 2xN). Tcomm= 2P(ts+tw2NZ) ; jos N on jaollinen P:llä ja pisteen laskenta-aika on vakio, saadaan kokonaissuoritusajaksi T1d fin.diff.= (Tcomp+Tcomm)/2= tcN2Z/P+ts2+tw4NZ.

Tehokkuus ja nopeutus

Suhteellinen tehokkuus Erelative= T1/PTP, missä T1 on suoritusaika 1 prosessorilla ja TP vastaavasti P prosessorilla. Suhteellinen nopeutus Srelative= PE1. Nämä ovat siis vain suhteellisia arvoja, joten jokin toinen algoritmi voi olla P prosessorilla absoluuttisesti parempi vaikka sen suhteelliset arvot olisivat huonompia. Edellä mainitulle finite difference –algoritmille absoluuttinen tehokkuus E= tcN2Z/(tcN2Z+ts2P+tw4NZP).

Skaalautuvuusanalyysi

Finite difference –algoritmille pätee:

Empiirisen datan kanssa mallit voivat vastata kysymyksiin:

Skaalautuvuus kiinteällä ongelman koolla

Eräs lähestymistapa skaalautuvuuden mittaamiseen on määrittää kiinteäkokoisen ongelman suoritusaika ja tehokkuus prosessorien lukumäärän funktiona. Tällöin tiedetään esim. nopein tapa ratkaista ongelma A koneella X tai suurin prosessorien lukumäärä, jolla tehokkuus säilyy yli 50%.

Skaalautuvuus skaalatulla ongelman koolla

Nyt E pidetään vakiona ja P muuttuu (isoefficiency function). Kasvavalla prosessorimäärällä T1= E(Tcomp+ Tcomm+ Tidle). Jälleen finite difference –algoritmille tcN2Z~ E(tcN2Z+ts2P+tw4NZP).2D-hajotus on skaalautuvampi kuin 1-D. Yleensäkin korkeamman asteen dekompositiot tuntuvat olevan tehokkaampia.

Suoritusprofiili

Jos ohjelma ei täytä asetettuja vaatimuksia, malleja voi käyttää parannuskeinojen hakemiseen. Syinä voivat olla voimakkaasti kertautunut laskenta, joutokäynti, viestien valmistelut ja lähetykset tai niiden yhdistelmä. On pyrittävä selvittämään näistä dominoiva komponentti laskemalla suoritusprofiili. Ratkaisuna voi olla kertautuvan laskennan vähentäminen viestintää lisäämällä tai granulaarisuuden lisääminen viestien valmisteluiden vähentämiseksi. Viestien lähetysten aiheuttaessa kustannuksia voidaan pienentää viestien kokoa tai antaa laskennan kertautua eri prosessoreissa.
 
Kuva 2. Laskennasta, viestien valmisteluista ja lähetyksistä aiheutuvien kustannuksten osuudet P:n funktiona 1-d finite difference algoritmille, kun N=512 , Z=1, ts=200 m s, tw=0.8 m s, tc=1 m s . Esimerkissä ei ole huomioitu joutokäyntiä tai kertautuvaa laskentaa.

Mallien käyttö

Kokeelliset tutkimukset

Mallinnuksen rooli on useimmin kokeiden ohjaajana ja tulosten selittäjänä. Kokeellisilla tutkimuksilla voidaan jo varhaisessa vaiheessa määrittää parametrien arvoja ja myöhemmin verrata havaittua ja mallinnettua suorituskykyä.

Kokeellinen suunnittelu

Aluksi on tunnistettava tieto, jota halutaan saada. Kokeita tehdään yleensä vaihtelevalla ongelman koolla ja prosessorien määrällä. Näiden datapisteiden maksimointi pienentää yksittäisten mittausvirheiden vaikutusta sekä mahdollistaa mallin tarkkuuden arvioimisen ja niiden alueiden tunnistamisen joissa malli ei päde. Seuraavaksi on suunniteltava kokeet joilla haluttu data kerätään – on varmistuttava siitä että mitataan nimenomaan haluttua osaa algoritmista.

Kokeellisten tietojen kerääminen ja tarkistus

Tulosten on oltava tarkkoja ja toistettavia. Ajan mittaaminen systeemin timer rutiineita kutsumalla voi aiheuttaa suuria kustannuksia toistettaessa kaikissa prosessoreissa. Vaihtoehtoisesti voidaan valita yksi prosessori, jonka toiminta kuvastaa hyvin muita, tai käyttää profilointi- ja jäljitystyökalua. Tulosten olisi oltava toistettavissa korkeintaan 2-3% vaihteluvälillä toisistaan. Vaihtelua voi aiheutua seuraavasta:

Kokeellisten tulosten vaihtelu voi paljastaa virhelähteet mittauksissa. Toistettavissakaan kokeissa ei kuitenkaan voida olla varmoja siitä, että tulokset ovat oikeita. Luottamusta voi lisätä mittaamalla samaa asiaa eri tavoilla.

Tietojen sovittaminen malleihin

Kun kalibrointitarkoituksissa saadut kokeelliset tutkimustulokset sovitetaan malliin, saadaan määritettyä tuntemattomia parametrejä. Sovituksessa voidaan käyttää perinteisiä menetelmiä, esim. pienin neliösumma.

Implementointien arviointi

Suorituskykymalleille on käyttöä myös suunnittelun jälkeisessä koodin kirjoittamisessa. Suuret poikkeamat havaitun ja ennustetun suoritusajan välillä viittaavat huonoon malliin tai puutteelliseen implementointiin. Empiirisiä tuloksia voi käyttää puutteiden sijainnin määritykseen. Aluksi pitää kuitenkin varmistua siitä, että mallin ja kokeiden tulokset ovat oikeat ja että niissä mitataan samaa asiaa. Seuraavaksi on saatava rinnakkaiskoodin suoritusprofiili, joka perustuu mitattuihin arvoihin. Suoritusaikoja kerätään laskennan eri vaiheista ongelman koon ja prosessorien määrän vaihdellessa.

Ylimääräinen overhead

Usein jokin merkityksettömänä ohitettu algoritmin piirre osoittautuu käytännössä merkittäväksi.

Nopeutuksen anomaliat

Toteutus saattaa toimia mallin ennustusta nopeammin prosessorien määrän kasvaessa. Syynä voi olla seuraavaa:

Korjattu viestintäkustannusmalli

Ideaalimallia voidaan jatkaa todellisiin verkkoihin, jolloin joissakin olosuhteissa voidaan saada huomattavasti tarkempi malli. Ideaalimallissa kustannus viestin lähettämisestä prosessorilta toiselle ei ollut riippuvainen prosessorien sijainnista tai samanaikaisesti tapahtuvasta muiden prosessoreiden viestinnästä. Kun viestejä lähetetään runsaasti, on otettava huomioon verkoissa usein esiintyvät reitittimet tai kytkentäsolmut. Samalle johdolle pyrkivä viesti voidaan estää tai reitittää edelleen. Reitin pituus ei juuri vaikuta merkitsevästi, mutta kilpailu kaistasta tuo ideaalimalliin tekijän S, joka viittaa samaa johtoa samanaikaisesti tarvitsevien prosessorien määrään: Tmsg bandwidth limited= ts+ twSL. Eli jokaisella prosessorilla on 1/S osa koko kaistasta. Tämä kaava ei huomioi uudelleenlähetyksiä, mutta on kokemusten perusteella riittävän tarkka käytännön tarkoituksiin. Vaikutus on merkittävin synkronisesti suoritettavissa algoritmeissa joissa prosessorit eivät voi jatkaa muuta laskentaa viestejä odottaessaan (esim. finite difference algoritmi).

Ristikytkentäverkko

Ristikytkin välttää kilpailua kytkemällä N tuloa N lähtöön N2 kytkimellä, ja on huonosta skaalautuvuudestaan huolimatta suosittu mekanismi pienillä työasemamäärillä (tyypillisesti <22). Suuremmat tulevat kalliiksi. S= 1.

Väylään perustuvat verkot

Väylä on erittäin huonosti skaalautuva, koska vain yksi prosessori kerrallaan voi viestiä sillä. Tässä tapauksessa S= samanaikaisesti viestimistä yrittävien prosessoreiden määrä. Väyliä käytetään tavallisesti jaetun muistin koneissa luku- ja kirjoituspyyntöjen välittämiseen globaaliin muistiin. Välimuistilla pyritään tosin vähentämään väylän liikennettä.

Ethernet

Ethernetin S on kuten muissakin väylään perustuvissa verkoissa.

Mesh verkot

Mesh verkon prosessorit on liitetty ristikytkentäverkon kytkimiin. D-ulotteisessa (usein D=2 tai 3)mesh verkossa jokainen prosessori on kytketty suoraan 2D välittömään naapuriin. Yhteyksiä on tyypillisesti yhdellä johdolla kumpaankin suuntaan. Prosessoreiden välisiä etäisyyksiä lyhennetään kytkemällä niitä silmukoiksi. Toisaalta tällöin päätepisteiden välisistä johdoista tulee muita pidempiä, ellei verkkoa laskosteta. Lisäksi silmukan aliverkot ovat väylään perustuvia jolloin silmukan edut menetetään jos kone jaetaan usean käyttäjän kesken. S riippuu algoritmista.

Hyperkuutioverkko

Kuten mesh verkoissa, prosessorit on liitetty kytkinelementteihin. D-ulotteinen hyperkuutio yhdistää jokaisen 2d prosessorista d muuhun prosessoriin. Se voidaan määritellä rekursiivisesti – kytkemällä kaksi d –ulotteista hyperkuutiota yhteen saadaan d+1 –ulotteinen hyperkuutio. S riippuu algoritmista. Hyperkuutiolla on mielenkiintoisia ominaisuuksia. Nimeämällä prosessorit loogisesti binaarikoodilla havaitaan, että kaksi prosessoria on kytketty toisiinsa jos ja vain jos niiden koodit poikkeavat toisistaan yhdellä bitillä. Toisaalta se on kuin mesh –verkko jossa on ylimääräisiä pitkän matkan yhteyksiä mikä vähentää entisestään kilpailua kaistasta. Toisaalta se on teknisesti hankalampi toteuttaa.

Kuva 3. Hyperkuutioita 1-4 ulottuvuudessa. Huomaa rekursiivinen binaarikoodaus. Viestin kulkumatka on korkeintaan d.

Moniportaiset välikytkentäverkot

MIN-verkossa käytetään vähemmän kytkimiä kuin ristikytkentäverkoissa. Sen sijaan viestejä välitetään useiden kytkentäportaiden kautta. Joko n porrasta kn-1-kxk yksisuuntaisia ristikytkimiä yhdistää P=kn prosessoria tai n porrasta kn-1-kxk kaksisuuntaisia ristikytkimiä yhdistää P=2kn prosessoria. Jälkimmäisessä tapauksessa linkit ovat kaksikanavaisia. Yksisuuntaisen MIN:n kaikki prosessorit ovat yhtä kaukana toisistaan, koska kaikki viestit kulkevat yhtä monen johdon kautta. Kaksisuuntaisessa prosessorin sijainnilla on hieman enemmän merkitystä.

Kilpailu kaistasta finite difference –algoritmissa

Ideaalimallissa prosessorikohtainen viestintäkustannus on Tideal fd comm= ts2+tw4NZ. Väylään perustuvassa verkossa yksi prosessori kerrallaan lähettää. Jos oletetaan, että puolet prosessoreista pyrkii lähettämään samanaikaisesti, saadaan kustannukseksi Tbus fd comm= ts2+tw2PNZ. Kaistan rajallisuudella on voimakas vaikutus tällaiseen yksinkertaiseenkin algoritmiin.

Kilpailu kaistasta finite butterfly-rakenteessa (hyperkuutio)

P tehtävää suorittaa logP vaihtoa N/P datamäärälle. Ideaalimallissa prosessorikohtainen viestintäkustannus on Tideal bf comm= logP(ts+twN/P). Kilpailua kaistasta ei ole, jos käytetään ristikytkentäverkkoa tai P prosessorin hyperkuutiota. Väylän tapauksessa oletetaan taas, että puolet prosessoreista pyrkii lähettämään samanaikaisesti jolloin saadaan kustannukseksi Tbus bf comm= ts2+tw2PNZ. Yksiulotteisessa mesh –verkossa viestit kulkevat yhteensä P(P-1) linkkiä mutta koska yksiulotteinen kaksisuuntainen verkko tarjoaa vain 2(P-1) johtoa, algoritmi vaatii vähintään P/2 askelta: T1d mesh bf comm³ tslogP+twN/2.

Kuva 4. Rinnakkais-FFT (=kaksi butterfly-operaatiota) 1-ulotteisessa Intel DELTA mesh-verkossa ja Ethernetillä kytketyillä RS/6000 prosessoreilla. Jalostetut mallit ottavat huomioon kilpailun kaistanleveydestä ja ovat siksi parempia.

Input/Output

Sovelluksia, joilla on huomattavia I/O –vaatimuksia (erityisesti tallennettavaa dataa):

I/O –toimintaa kannattaa verrata viestintään, jossa osapuolina ovat prosessorit ja levyt. Jos koneella on vain yksi levy tai levyt ovat kytkettyinä vain yhteen prosessoriin, suorituskykyä ei juuri pysty optimoimaan. Yleensä I/O –polkuja on kuitenkin useita jolloin pyritään järjestämään I/O –operaatiot siten, että useat prosessorit lukevat ja kirjoittavat samanaikaisesti eri polkujen kautta.

Yksittäisten luku- ja kirjoituspyyntöjen lukumäärä on usein merkittävämpi I/O –suorituskyvylle kuin siirretyt tietomäärät. Lukumäärä riippuu osittain datan jakautumisesta muistiin ja levylle ja on siten sovelluksen määritettävissä. Hajauttamalla data useille levyille, vähennetään todennäköisyyttä että useat prosessorit pyrkivät lukemaan tiettyä levyä samanaikaisesti.

Poikkeamat datan jakaumassa muistin ja levyn välillä kasvattaa tarvittavia luku- ja kirjoitusmääriä. Tilannetta voidaan korjata muokkaamalla toista komponenteista noudattamaan haluttua jakaumaa tai jakaa data uudelleen siirron yhteydessä. Usein data kannattaa järjestellä uudelleen muistissa I/O –pyyntöjen minimoimiseksi. Seurauksena poistetaan kytkös levyllä ja muistissa olevien datajakaumien väliltä.

Esimerkki algoritmien vertailusta mallien avulla

Shortest path –algoritmit

Analyysi osoittaa, että kolme neljästä lyhimmän polun algoritmista on optimaalisia tietyissä olosuhteissa. Pyritään löytämään lyhimmät polut kaikkien graafin solmuparien välille. Käytetään algoritmissa syötteenä NxN –naapuruusmatriisia A, josta nähdään suorat linkit kahden eri solmun välillä. Laskemalla saadaan tulokseksi NxN –matriisi S jossa on lyhimmän solmujen i ja j välisen reitin pituus tai ¥; jos polkua ei ole.

Floydin algoritmissa luodaan väliaikainen matriisi I, jossa on kulloisellakin askeleella lyhin tunnettu polun etäisyys solmujen i ja j välillä. Seuraavilla askeleilla tutkitaan kaikki solmut ja lasketaan, tuleekoedullisemmaksi kulkea niiden kautta. Tarvittaessa matriisia I päivitetään. Kun yhden vertailuoperaation kustannus on tc, on kokonaiskustannus noin tcN3.

Dijkstran algoritmi laskee kaikki lyhimmät polut V yksittäisestä solmusta. Joukossa T ovat solmut joille ei ole löytynyt lyhintä polkua ja di ilmoittaa lyhimmän tunnetun polun somusta vs solmuun vi. Alussa T=V ja di= ¥ . Kokonaiskustannus on noin tcN3F, missä F ~1.6.

Rinnakkais-Floyd 1

Jaetaan matriisi I ja lähtömatriisi S yhdessä ulottuvuudessa riveittäin korkeintaan N prosessorille. Tällöin jokainen tehtävä tarvitsee paikallisen datansa lisäksi matriisin I rivin k, eli jokainen tehtävä levittää oman rivinsä muille. Puurakenteisena tämä levitys tapahtuu logP askeleella, joten N kappaletta N kokoisia lähetyksiä tekee kustannuksiksi TFloyd 1= N3/P+NlogP(ts+twN).

Rinnakkais-Floyd 2

Jaetaan matriisi I kaksiulotteisesti korkeintaan N2 prosessorille, jolloin jokainen tehtävä tarvitsee paikallisen datansa lisäksi NP-1/2 arvoa kahdelta muuta samassa rivissä ja sarakkeessa olevalta tehtävältä. NP-1/2 kappaletta P-1/2 kokoisia lähetyksiä tekee kustannuksiksi TFloyd 2= tcN3/P+NlogP(ts+twNP-1/2).

Rinnakkais-Dijkstra 1

Graafi monistetaan jokaiselle P tehtävälle, jotka suorittavat peräkkäisalgoritmin N/P solmulle. Näin hyödynnetään N prosessoria eikä tarvita viestintää. Suoritusaika on TDijkstra 1= tcFN3/P.

Rinnakkais-Dijkstra 2

Kun PN, muodostetaan N joukkoa joissa kaikissa on P/N tehtävää. Graafi monistetaan jokaiselle joukolle, jotka suorittavat peräkkäisalgoritmin yhdelle solmulle. Graafin solmut jaetaan joukon sisällä. Suoritusaika on TDijkstra 2= tcFN3/P+Nlog(P/N)(ts+2tw).

Vertailua

Kuva 5. Neljän shortest-path algoritmin suorituskyky.

Yhteenveto

Matemaattisia suorituskykymalleja voidaan kehittää kuvaamaan rinnakkaisalgoritmien suoritusaikaa, tehokkuutta ja skaalautuvuutta yksinkertaisten parametrien funktioina. Näitä malleja voidaan käyttää monissa implementoinnin vaiheissa:

Lähteet

Ian Foster, Designing and Building Parallel Programs, Addison-Wesley 1995