UNIVERSITETET I OSLO Institutt for informatikk
Distribuert fellesminne i
software over SCI
Henning Spjelkavik
Hovedfagsoppgave
1. mai 1999
ii
Distribuert fellesminne i software over SCI
Henning Spjelkavik 1. mai 1999
«For over a decade prophets have voiced the contention that the organization of a single computer has reached its limits and that truly significant advances can be made only by interconnection of a multiplicity of computers in such a manner as to permit coope- rative solution.»
Dr. Gene M. Amdahl, IBM Corporation, 1967, [2]
Sammendrag
Denne oppgaven diskuterer utnyttelse av SCI i et system for distribuert fellesminne implementert i software. Foruten å benytte SCI som et medium for rask meldingsutveksling, er også mulighe- ten for å skrive direkte til minnet i en annen maskin via SCI-kortet testet. Konklusjonen er at man har mulighet til å oppnå bedre yt- else ved å utnytte SCI og den ekstra funksjonaliteten. Dette krever dog at programmereren har kjennskap til programmets datastruk- turer og bruk av data for å få en effektiv utnyttelse.
Forord
Denne hovedoppgaven er skrevet til graden Candidatus Scientiarum ved Insti- tutt for Informatikk, Universitetet i Oslo. Arbeidet med oppgaven skal utgjøre to av de totalt tre semestre hovedfagsstudiet varer.
Min veileder har vært Øystein Gran Larsen. Jeg vil rette en takk for en spennende oppgave, for konstruktive kommentarer og kritikk rundt oppgaven og et godt samarbeid.
Videre vil jeg gjerne takke Knut Omang som har vært til stor hjelp under- veis og som ikke minst har inspirert meg faglig. Med sine grundige kunnskaper om SCI har muligheten for å diskutere med ham vært meget viktig.
I tillegg fortjener mine korrekturlesere i innspurten, Endre, mor og far en takk for rettelse av lumske skrivefeil som man ikke oppdager etter å ha lest sin egen tekst for mange ganger. Dessuten vil jeg takke mine studiekamerater ved Ifi, ogspesielt en takk til de som har hatt lesesalsplass samtidig med meg på Forskningsparken, for en hyggelig studietid.
Til slutt en takk til min venninne for å ha ha lest oppgaven med en helt annen synsvinkel og med det tvunget frem klarere formulereringer, og for oppmuntring og støtte under arbeidet.
Blindern, 1 mai 1999 Henning Spjelkavik
iii
iv
Innhold
1 Innledning 1
1.1 Historie . . . 1
1.2 Organisering av oppgaven . . . 4
2 Metoder 7 2.1 Bootstrapping . . . 7
2.2 Fremgangsmåte . . . 8
2.2.1 Endrede protokoller –remote store . . . 9
2.2.2 Implementasjon . . . 9
2.3 Oppsummering . . . 10
3 Bakgrunn 11 3.1 Minnearkitekturer . . . 11
3.1.1 Uniform minnetilgang (UMA) . . . 11
3.1.2 Ikke-uniform minnetilgang (NUMA) . . . 12
3.2 Prosessoren - regneenheten. . . 15
3.3 Multiprosessor eller multicomputer . . . 16
3.3.1 De raskeste maskiner i 1998 . . . 18
3.3.2 Klassifisering av MIMD maskiner . . . 18
3.3.3 Multicomputer kan lage en abstraksjon av DSM . . . . 19
4 Konsistensmodeller 21 4.1 Innledning. . . 21
4.2 Sekvensiell konsistens . . . 22
4.2.1 Videreutvikling av modellen . . . 23
4.3 Prosessorkonsistens (PC) . . . 23
4.4 Svak konsistens . . . 24
4.5 Release konsistens . . . 24 v
vi Innhold
5 Protokoller og CVM 27
5.1 Protokoller for DSM . . . 27
5.1.1 Generelle betraktninger og terminologi . . . 27
5.1.2 Ulike konsepter . . . 28
5.1.3 Lokalisering av side . . . 28
5.1.4 En protokoll for sekvensiell konsistens . . . 29
5.1.5 Ulike implementasjoner av RC . . . 29
5.1.6 Lazy release consistency (LRC) . . . 30
5.1.7 Automatic update release consistency (AURC) . . . 32
5.1.8 Home-based lazy release consistency (HLRC) . . . 33
5.1.9 Sammenligning . . . 33
5.2 Implementasjon av HLRC i CVM . . . 33
5.2.1 Sidefeil. . . 34
5.2.2 Leseforespørsel . . . 34
5.2.3 Synkroniseringspunkter . . . 34
6 Nettverk i eksisterende DSM 37 6.1 De ulike teknologiene. . . 38
6.1.1 HIPPI . . . 38
6.1.2 Memory Channel(MC) . . . 38
6.1.3 Scalable Coherent Interface . . . 40
6.2 Resultater . . . 40
6.3 Diskusjon – konsekvenser for DSM . . . 43
6.3.1 Kjernemodus vs brukermodus og interrupter . . . 43
6.3.2 Ingen kopiering («zero copy») . . . 44
6.3.3 Resultatene fra SoftFLASH. . . 45
6.3.4 Sidestørrelser . . . 46
6.4 Konklusjon . . . 47
6.4.1 Nyere DSM-systemer . . . 47
6.4.2 Konsekvenser . . . 47
7 Ytelse 49 7.1 En definisjon av ytelse. . . 49
7.1.1 Diskusjon . . . 50
7.1.2 Skalering. . . 50
7.1.3 Amdahls lov . . . 51
7.2 Tradisjonelle ytelsestester . . . 51
Innhold vii
7.2.1 Kjerner . . . 52
7.2.2 Syntetiske tester . . . 52
7.2.3 Suiter . . . 52
7.2.4 Hva tester programmene? . . . 53
7.3 Testapplikasjoner . . . 53
7.3.1 Barrier . . . 54
7.3.2 Globalsum. . . 54
7.3.3 FFT . . . 54
7.3.4 Water . . . 54
7.3.5 Hint . . . 55
7.4 Rapportering av resultater . . . 55
8 Utvidelse – Nye protokoller 57 8.1 Relaterte prosjekter . . . 57
8.2 Plattform . . . 59
8.3 Kommunikasjon i CVM. . . 59
8.3.1 UDP . . . 60
8.3.2 MPI . . . 60
8.3.3 Organisering av kapittelet. . . 61
8.4 Første versjon - Naiv MPI/SCI v1.00 . . . 61
8.4.1 Løsning: et forenklet MPI-lag . . . 61
8.4.2 Diskusjon . . . 62
8.5 Andre versjon av MPI/SCI . . . 62
8.5.1 En annen mulig løsning: felles mottagerbuffer . . . 63
8.5.2 Optimalisering av meldingsutveksling . . . 64
8.6 Protokoller som utnytter SCI . . . 65
8.7 AURC over SCI . . . 66
8.7.1 Minneallokering. . . 66
8.7.2 Diskusjon . . . 66
8.7.3 Sideobjekt . . . 67
8.7.4 Protokoll . . . 67
8.7.5 Oppsummering . . . 68
8.8 AURC2 – Remote store ved skrivefeil . . . 69
8.8.1 Sidefeilhåndtering . . . 69
8.9 AURC3 – Remote store for utvalgte sider og dynamisk valg av hjemmenoder 70 8.9.1 Sidefeilhåndtering . . . 70
viii Innhold
9 Eksperimenter og diskusjon 71
9.1 Primitiver . . . 71
9.1.1 Diskusjon . . . 72
9.2 Forbedring fra UDP til MPI/SCI 1 . . . 73
9.2.1 Skalering fra én til to noder. . . 75
9.2.2 Oppsummering . . . 75
9.3 Skalering til flere noder – MPI/SCI 2 . . . 75
9.3.1 Barrier . . . 76
9.3.2 Globalsum. . . 77
9.3.3 FFT . . . 78
9.3.4 Water . . . 81
9.3.5 Hint . . . 82
9.4 Forskjellen mellom MPI/SCI 1 og MPI/SCI 2 . . . 85
10 Konklusjon og videre arbeid 87 10.1 Oppsummering av resultater . . . 87
10.1.1 Lav forsinkelse i nettverket . . . 87
10.1.2 Utnyttelse av funksjonalitet i SCI . . . 88
10.1.3 Fordeling av sidenes hjemmenode . . . 88
10.2 Konklusjon . . . 88
10.3 Videre arbeid . . . 89
10.3.1 Minnebruk . . . 89
10.3.2 Ny arkitektur . . . 90
A Minnebusser 91 B Resultater i tabellform 93 B.1 Barrier . . . 93
B.1.1 Quantify-resultater . . . 93
B.2 Globalsum . . . 94
B.3 Resultater for FFT . . . 95
B.3.1 Statistikk for 100 iterasjoner av FFT . . . 97
B.4 Resultater for Water . . . 97
B.4.1 MPI/SCI-statistikk med Water. . . 97
Figurer
2.1 Arkitektur . . . 9
3.1 Blokkdiagram for UMA (fra [33, side 20] . . . 12
3.2 Blokkdiagram for SMP basert på Pentium Pro (omarbeidet etter [65, side 223] 13 3.3 Blokkdiagram for NUMA. . . 14
4.1 Illustrasjon av sekvensiell konsistens . . . 22
4.2 Alle tidligerestoremå være utført før enload . . . 24
4.3 Kategorisering av ulike skriveaksesser. . . 25
5.1 Illustrasjon av LRC . . . 31
5.2 Illustrasjon av AURC . . . 32
6.1 Arkitektur . . . 39
6.2 Forsinkelser . . . 41
6.3 Forsinkelser i «Memory Channel 2» . . . 43
8.1 Tilstandsdiagram for AURC 1 . . . 68
8.2 Tilstandsdiagram for AURC 2 . . . 69
9.1 Primitiver . . . 72
9.2 Kjøretid for programmene . . . 74
9.3 Forbedring? . . . 74
9.4 Kjøretid for barrier . . . 76
9.5 Kjøretid for globalsum . . . 78
9.6 Kjøretid for fft ved første forsøk . . . 78
9.7 Kjøretid for fft etter modifisering . . . 79
9.8 Kjøretid for water . . . 82
9.9 Hint kurve for 2 noder . . . 83
9.10 Hint kurve for 3 noder . . . 84 ix
x Figurer 9.11 Hint kurve for 4 noder . . . 85
Tabeller
1.1 De tre raskeste maskinene pr. november 1998 ifølge Top500 Supercomputing sites[17] 2
6.1 Oversikt over forsinkelser (se kildehenvisninger på side 41) . . . 41
6.2 Fordeling av tiden som én remote store bruker . . . 43
6.3 Hvor lang tid tar det å levere én melding? . . . 44
6.4 Gjennomstrømning, reciever copy. Hentet fra [61] . . . 45
6.5 Skalering av forsinkelse . . . 46
9.1 Tid iµs for minnerelaterte primitiver. . . 72
9.2 Resultater for MPI/SCI 1 . . . 74
9.3 «Forbedring» fra én til to noder . . . 75
9.4 Resultater for Barrier med MPI/SCI 2 . . . 77
9.5 Statistikk for FFT . . . 80
9.6 Statistikk for Water med 4 noder . . . 83
9.7 Forbedring fra første til andre generasjon . . . 86
xi
xii
Kapittel 1
Innledning
1.1 Historie
Siden datamaskinen ble introdusert på slutten av 1940-tallet, har det blitt ut- viklet stadig raskere maskiner og maskinsystemer. Man ønsker likevel å ha en- da større regnekraft enn det én maskin kan tilby. Derfor kobles regneenheter sammen for å lage et kraftigere system.
De raskeste systemene, gjerne kalt for supercomputere eller superdata- maskiner, er og har vært meget dyre. Disse maskinene har vært utviklet spesielt for sitt formål – å utføre store mengder beregninger på kortest mulig tid – og utviklerne har derfor kunnet bruke store ressurser på å utvikle spesielle de- ler for sine prosjekter. Både nettverksteknologien og regneenhetene er ofte spesielle for prosjektet. Det har vært store variasjoner i hvordan enhetene blir benyttet og koblet sammen. Dette har i mange tilfeller også medført at det er store forskjeller i hvordan de skal programmeres. Ikke bare fra leverandør til leverandør, men også fra modell til modell. Dette gjør disse systemene meget dyre, ikke bare i innkjøp og drift, men også ved at de menneskene som utfører denne jobben må lære seg nye måter å programmere maskinen på, og deretter skrive om algoritmer for å utnytte maskinen[33, side 13].
Den teknologiske utviklingen innen integrert kretsteknologi har medført at prosessorer implementert i CMOS idag omtrent har tatt over markedet for regneenheter i datamaskiner. Med VLSI-teknologi kan man nå ha mange millioner transistorer på én brikke, og produsert i stort volum blir slike brikker meget rimelige.
Et annet viktig bidrag er at algoritmer og teknikker som ble utviklet til mainframes og supermaskiner allerede på 60-tallet for å utnytte parallellitet i kode idag igjen blir benyttet, slik som f.eks Tomasulos algoritme[56, side 251]. Den gang ble algoritmene implementert på kretskort, idag blir de laget i silisium i chipene.
De maskinene som idag regnes for å ha størst regnekraft, er derfor ba- 1
2 1.1 Historie sert på prosessorer i CMOS. Ved Universitetet i Mannheim vedlikeholder de en liste over de maskinene som er skal være raskest i verden til å løse et lig- ningssystem fra ytelsestesten Linpack[17]. Som vist i tabell 1.1ser vi at pro- sessorene er det som har blitt kalt skalare mikroprosessorer, og foruten at de brukes i noder for kraftige systemer, benyttes disse prosessorene også i vanlige arbeidsstasjoner og PCer.
Det tallet som brukes til å rangere systemene er fra den rapporterte maksi- male ytelsen under Linpackkjøringen (Rmax), her gjengitt med enhet Tflop/s.
prosessor maks Tflop/s
Intel ASCI Intel Pentium Pro 1.338
Cray T3E DEC Alpha 21164 0.891
IBM SP-2 PowerPC 604e 0.468
Tabell 1.1: De tre raskeste maskinene pr. november 1998 ifølge Top500 Su- percomputing sites[17]
En annen type arkitektur som har vært meget vanlig, er basert på å bruke vektorprosessering i tillegg til skalarprosessorer [33, 10]. Flere japanske fir- maer, som Fujitsu og Hitachi, har implementert vektorprosessorer i CMOS [10].
Blant de mest kjente produsentene, og i sin tid av mange regnet som den ledende av denne typen maskiner finner vi Cray, som gikk konkurs tidlig på nittitallet. Rettighetene ble delvis kjøpt opp av Silicon Graphics, og delvis av Sun. Det selges fortsatt Cray-maskiner, både basert på Crays tradisjonelle vek- torkonsept og på vanlige skalarprosessorer.
Hvordan?
Det finnes mange måter å lage parallelle datamaskiner på. Én inndeling er å se på hvordan de ulike enhetene kommuniserer, og hvordan de har tilgang til minnet. Det er to hovedtyper. Enten er maskinen basert på en eller annen form for delt tilgang til minnet, noe jeg vil kalle for fellesminne i denne opp- gaven («shared memory»), eller den benytter meldingsutveksling («message passing»).
Denne inndelingen er imidlertid ganske grov. Hvorledes, og på hvilket ni- vå i maskinen dette implementeres, varierer. Dette vil vi komme grundigere tilbake til, fordi det er viktig for forståelsen av distribuert felles minne i soft- ware.
1.1 Historie 3 Nettverk av arbeidsstasjoner
Tidligere var de raskeste maskinene basert på spesielle prosessorer og arkitek- turer. Idag benyttes det i stor grad prosessorer som vi har i vanlige arbeidssta- sjoner. Burde det ikke være mulig å koble sammen arbeidsstasjonene våre og få de til å oppføre seg som én kraftig maskin?
Et «Nettverk av arbeidsstasjoner» (NOW)[5] er nettopp denne idéen. Å benytte rimelige arbeidsstasjoner, koble disse sammen med nettverksteknologi og få en klynge med høy ytelse til lav pris er ønsket. Dette skal være utstyr som produseres i store volum og følgelig er nodene forholdsvis rimelige, spesielt sett i forhold til nodene i et tradisjonelt supersystem.
NOW har benyttet tradisjonelle protokoller (TCP/IP) over vanlige linker som Ethernet (10 MBit) og i det siste 100 Mbit Ethernet og ATM. Disse har relativt høye forsinkelser – flere ordner – sammenlignet med den interconnect- teknologien som benyttes på bakplanet i klynger og supermaskiner.
Kommunikasjonen over nettverket i et NOW er meldingsutveksling[5], fordi vanlige nettverk ikke tilbyr noen annen mulighet, som for eksempel å skrive rett inn i bestemte adresser i minnet til maskinen i den andre enden.
Med interconnect har man tradisjonelt ment en teknologi for sammen- kobling som har høy båndbredde og lav forsinkelse. Ofte har de vært propri- etære, og meget dyre. Det tradisjonelle nettverket Ethernet er kjennetegnet ved høy forsinkelse og lav båndbredde.
Distribuert fellesminne i software (DSM)
Fellesminne er en interessant modell for programmering av parallelle program- mer, fordi den byr programmereren fordeler i forhold til tradisjonell parallell- programmering ved hjelp av meldingsutveksling. Abstraksjonen av fellesminne gjør at prosessene kan bruke datastrukturer som aksesseres på vanlig måte i programmene, men som likevel er globale for alle prosessene i applikasjonen.
Ved vanlig meldingsutveksling må programmereren ta stilling til hva som skal sendes når og til hvem. Med DSM er kommunikasjonen transparent, og forhåpentlig vil dette medføre at utvikleren kan konsentrere seg mer om de parallelle algoritmer som brukes, og ikke med hvordan kommunikasjonen skal implementeres.
Kanskje er det også lettere å porte programmer fra kraftigere maskiner med fellesminne til denne modellen, enn til en meldingsutvekslingsmodell, siden abstraksjonen er den samme[3].
4 1.1 Historie
Teknikker for implementasjon
Distribuert fellesminne kan implementeres ved å bruke det virtuelle minnesys- temet til å detektere bruk av minne som er delt. Dette kaller vi for et sidebasert DSM-system, og det er denne tilnærmingsmåten vi ser på i denne oppgaven1. Granulariteten, hvor fin oppdeling vi får av de delte sidene, avhenger av minnesystemet, men størrelsen kan ikke være mindre enn én fysisk side i maski- nen. Det er typisk 4 kB eller 8 kB på de maskiner som benyttes.
Ved forsøk på å lese eller skrive til delte lokasjoner, må systemet sørge for å innhente korrekte data slik at leseoperasjonen returnerer det den skal, og dessuten sørge for at det ved skriving til en side ett sted ikke medfører at gamle data blir lest et annet sted.
Motivasjon
Feltet DSM ble foreslått og først implementert av Kai Li med prosjektet Ivy på slutten av åttitallet[48].
På 1990-tallet har flere prosjekter basert på disse idéene vært utført. Vi har tatt utgangspunkt i Erlichsons artikkel om SoftFLASH[20]. Artikkelen bygger på hans doktorgrad om SoftFLASH, og den beskriver det han opplevde som problemer med DSM på dette tidspunktet.
Erlichson implementerte et system for distribuert felles hukommelse, bas- ert på FLASH-protokollen, utviklet ved Stanford for et distribuert hardware system[44]. Han benyttet HIPPI som interconnect[21].
Konklusjonen i artikkelen er at overhead, begrenset båndbredde og den høye forsinkelsen på nettverket, hindrer god ytelse for kommunikasjonsintensive applikasjoner. Likevel avslutter han:
«Overall, this approach still appears promising, but our results in- dicate that large low latency networks may be needed to make cluster-based virtual shared-memory machines broadly useful as large-scale shared-memory multiprocessors.»
Scalable Coherent Interface (SCI) har tradisjonelt blitt omtalt som inter- connect. Protokollen er designet for cache-coherens, og for å sitte på minne- bussen. Hos oss sitter SCI-kortet på I/O-bussen og brukes i første omgang som nettverk.
Vi benytter SCI som er et nettverk med stor båndbredde og meget lav latency sammenlignet med de fleste nettverksteknologier som tidligere er be- nyttet. Derfor burde SCI være godt egnet for DSM. Vi ser nærmere på dette temaet i kapittel6.
1Det finnes også mange andre tilnærmingsmåter. Peter Keleher vedlikeholder en oversikt over mange ulike prosjekter[41].
1.2 Organisering av oppgaven 5
1.2 Organisering av oppgaven
I kapittel2vil vi presentere grundigere målet med oppgaven, og hvilke meto- der som er benyttet for undersøkelsen.
Deretter vil de innledende kapitlene beskrive ulike måter å bygge maskiner med høy ytelse og høy grad av parallellitet. Vi vil klassifisere ulike arkitekturer på ulike nivåer og konsistensmodeller, og forsøke å sette dette i sammenheng med hvordan vi implementerer DSM.
Videre vil vi gå igjennom protokoller og implementasjon av disse i flere DSM-systemer. For å begrunne hvorfor vi tror at vi kan få bedre ytelse med SCI istedet for de nettverksteknologier som tidligere er brukt, vil vi se på hva som har vært flaskehalsen i andre systemer.
For å sammenligne ulike systemer må vi definere hva vi sammenligner. Vi vil derfor diskutere ulike forståelser av ytelse, hvordan dette kan måles, og ikke minst drøfte en del av svakhetene.
Dernest vil vi presentere våre implementasjoner. Vi vil se på både hvilke valg som ble gjort, og ikke minst hvorfor.
Til slutt går vi igjennom resultater fra ulike tester kjørt med de ulike pro- tokollene, vi identifiserer problemer og ser på mulige forbedringer.
6
Kapittel 2
Metoder
Målet for oppgaven var å undersøke distribuert fellesminne i software (Soft- ware DSM) med bruk av SCI som nettverk.
Vi kunne enten starte med å bygge opp et nytt system fra bunnen, eller vi kunne utvide og tilpasse et eksisterende system, for å undersøke problemstill- ingen.
Én ulempe ved å starte forfra, er at det ville kunne ta mye tid å utvikle et fungerende system, før vi kunne komme til konkrete eksperimenter med SCI.
En fare med dette var å miste fokus fra målet, som var ikke å studere hvordan utvikle et software DSM system, men å studere hvordan man kan benytte SCI i et slikt system.
For å kunne sammenligne ytelse og egenskaper med andre nettverk og protokoller, ville det også være gunstig å benytte et system som man allerede har mange resultater og testprogrammet til.
Vi har derfor valg å ta utgangspunkt i Pete Kelehers Coherent Virtual Machine (CVM)[38].
2.1 Bootstrapping
Coherent Virtual Machine
Peter Keleher deltok i utviklingen av TreadMarks[3]. Senere har han laget Coherent Virtual Machine – CVM, som er laget spesielt for å eksperimentere med nye protokoller[38]. CVM er fritt tilgjengelig under GNU lisens[23].
Mens TreadMarks idag er kommersielt tilgjengelig, er CVM ment for å ekspe- rimentere, og med en lisens som tillater endringer og spredning av kildekoden.
7
8 2.2 Fremgangsmåte
Drivere for SCI – Slib
Det finnes flere ulike drivere for SCI-kortene, noe avhengig av hvilken maski- narkitektur vi ville velge å bruke. Dolphin Interconnect Solutions, som har levert kortene, leverer med én driver. I tillegg har det ved Institutt for Infor- matikk blitt utviklet en flerlags driver (kalt ICM) som har et grensesnitt som er implementert på flere plattformer[59], inkludert Solaris og Windows NT, men denne driveren fungerer bare med PCI buss i maskinen.
CVM er kun tilgjengelig på Solaris (SPARC) av våre platformer, og vi fikk den ikke til å kjøre under Solaris x86 under innledende forsøk. I det tilgjen- gelige klusteret ved instituttet[51] finnes det 4 UltraSPARC 1 koblet sammen med blant annet en SCI ring med SCI-kort basert på SBus.
Knut Omang ved instituttet har skrevet et bibliotek som tilbyr meldings- utveksling, opprettelse av delte variabler, låser med mere, over SCI til arbeidet med sin doktorgradsavhandling[55, 52]. Denne kan benytte både ICM og Dolphins driver for kommunikasjon med SCI-kortet.
Ved å velge Slib som grensesnitt mot SCI burde vi kunne bli med til en eventuell ny generasjon av UltraSparc basert på PCI-bus, noe som var en po- tensiell mulighet da prosjektet startet.
2.2 Fremgangsmåte
CVM har to arkitekturer for kommunikasjon mellom nodene. I første omgang benyttet CVM UDP/IP til kommunikasjon, men ved porting til en IBM SP- 2 klynge (som er basert på IBM RS/6000 arbeidsstasjoner) ble det skrevet støtte for å benytte Message Passing Interface (MPI) i tillegg[50].
MPI tilbyr pålitelig levering av melding mellom noder, mens når man be- nytter UDP må applikasjonen selv sørge for å håndtere tap av datagrammer [73].
Koden for kommunikasjon over UDP/IP er derfor betydelig mer komp- leks enn over MPI. Dette kan illustreres ved å nevne at det er ca 1000 kode- linjer for vanlig kommunikasjon og drøyt 550 for MPI.
Siden Slib tilbyr pålitelig meldingsutveksling over SCI så vi det som natur- lig å starte med å skrive et relativt enkelt lag som mappet MPI-kall til Slib-kall.
Figur2.1 viser en lagdelt modell for kommunikasjonen i min modifiserte ut- gave av CVM.
CVM benytter et meget lavt antall MPI-kall, og kun funksjoner knyttet til initialisering, status, og pålitelig sending og mottak av meldinger. Denne løsningen var en effektiv måte å få et fungerende system som benyttet SCI.
2.2 Fremgangsmåte 9
Applikasjon CVM
MPI/SCI Slib SCI driver SCI kort
Figur 2.1: Arkitektur
2.2.1 Endrede protokoller –remote store
SCI tilbyr funksjonalitet som vanlige nettverksteknologier ikke tilbyr. Vi ønsk- et å undersøke hvordan vi kunne benytte denne funksjonaliteten i forbindelse med DSM.
For spesielt interessant regnet vi muligheten for remote store, det vil si at man kan skrive fra en maskin (A) direkte til minnet på en annen maskin (B) uten å belaste annet enn minnebussen og SCI-kortet på maskin B. For å utføre skriveoperasjonen gjør man som vanlig når man skriver til minne via instruk- sjonenstoreeller tilsvarende på andre arkitekturer.
Dette settes opp på forhånd ved at deler av minnet på maskin B deles ut via SCI-kortet. På maskin A kan vi sette opp en mapping fra en virtuell adresse i maskin A til det delte minnet på maskin B.
Vi har brukt mye tid på å vurdere og teste ulike måter å implementere og utnytte remote store. For å undersøke hvordan en protokoll med remote store kunne implementeres, har vi laget mange små testprogrammer som bruker driverene på ulike måter, kombinert med måling av tids- og ressursbruk.
2.2.2 Implementasjon
Resultatene av ulike undersøkelser, kombinert med krav til protokollen vi har ønsket å lage, medførte at vi valgte å bruke systemkallet mmap(3) direkte mot Dolphins driver for å håndtere oppsettet av hvor og hvordan de ulike sider i minnet skulle peke, enten til en annen node, eller lokalt. Dette er det nivået som ligger nærmest driveren, men som likevel lar oss gjøre det vi ønsker fra brukermodus.
Det finnes klare ulemper ved dette valget. Denne løsningen er kun porta- belt til så lenge denne driveren finnes til ønskede kombinasjonen av operativ- system og hardware, og kallene har den samme semantikken.
Videre var det også flere valg. Først testet vi å benytte en filpeker (file
10 2.3 Oppsummering descriptor) pr. side som kunne brukes med remote store. Dette ville kunne lette håndteringen når sider skulle settes opp til å peke til andre noder. En slik løsning ville nok være lettere å porte til nye drivere, fordi hver side behandles isolert, og ikke er avhengig av hvordan de andre sidene settes opp.
Det største problemet var begrensninger i antall åpne filer, både i opera- tivsystemer og for driveren. Dette låste seg ved alt for få sider (under hundre), og løsningen ble forkastet.
Vi endte opp med å velge å mappe hele CVM-minnet fysisk via SCI- driveren og tilbake til det virtuelle minnet. I forhold til de andre nodene map- pet vi inn alt remote minne fysisk. En klar ulempe er at dette bruker mye av adresserommet i SCI, noe som vil begrense antallet delte sider totalt i system- et. Dette vil igjen medføre en begrensning i hvor stort system vi kan bygge.
Når vi skal sette opp bruk av minne på andre maskiner, trengs det kun et munmap/mmap-par. Dette tar mellom 50 og 100 mikrosekunder, se i avsnitt 9.1, noe som er raskere enn å hente over en kopi av siden.
Vi har benyttet denne funksjonaliteten i flere protokoller som ligner Au- tomatic Update Release Consistency1 (AURC) [11,79]. Dette er en hjem- menodebasert protokoll med release consistency som tillater flere skrivende noder, og som bruker en form for remote store for å oppdatere hjemmenod- en.
Et annet alternativ ville være å la Slib håndtere delte sider, og abstrahere oss fra driveren. Problemet var at Slib ikke har nødvendig funksjonalitet for å flytte hjemmenoden til delte variabler (i.e. sider). I alle tilfeller måtte det altså skrives et nytt grensesnitt mot driveren for å kunne manipulere sidetabellene slik vi ønsket.
2.3 Oppsummering
Vi håpet å kunne få bedre ytelse og god skalering med testprogrammene. Det vil si lavere kjøretid enn ved å bruke det vanlige nettverket. Med god skalering mener vi ihvertfall at kjøretiden synker når vi øker antall noder. Idéelt sett bør kjøretiden halveres når antall noder dobles. En alternativ skalering er at utført arbeid dobles ved doblet antall noder med konstant kjøretid.
1home based LRC, multiple writers.
Kapittel 3
Bakgrunn
Vi vil først studere ulike former for tilgang til fellesminne i multiprosessorer, og deretter se på to ulike typer prosessorer. Til slutt skal vi diskutere kort forskjellen på en multiprosessor og en multicomputer.
3.1 Minnearkitekturer
Maskiner eller systemer som benytter flere enn én prosessor, kan deles inn grovt etter hvordan kommunikasjonen mellom de ulike prosessorene utføres.
Vi snakker vanligvis i dag om to metoder. Enten er maskinen basert på mel- dingsutveksling, eller så er den basert på en eller annen form for fellesminne.
Denne inndelingen kan brukes på flere lag i maskinen, og det er fullt mulig at maskinvaren benytter fellesminne, men at programmereren ser et meldingsut- vekslingsgrensesnitt, eller motsatt.
En maskin med fellesminne vil for eksempel ønske å støtte gjenbruk av eksisterende kode basert på Message Passing Interface (MPI), og kan da imp- lementere meldingsutveksling. Det kan gjøres meget effektivt ved å utveksle pekere til bufre i fellesminne for meldinger som skal overføres.
3.1.1 Uniform minnetilgang (UMA)
En vanlig PC består vanligvis av én prosessor (CPU), minnebrikker og et an- tall periferienheter (I/O) koblet sammen ved hjelp av databusser. For å øke prosesseringskraften kan man sette flere prosessorer sammen i en maskin, og la disse prosessorene dele de andre ressursene.
I UMA-modellen for multiprosessor, deles tilgangen til minnet mellom al- le prosessorene. Alle prosessorer har lik tilgangstid til minnet, og vi sier derfor at delingen er uniform. Dog kan hver prosessor ha sin egen cache. Kommu- nikasjonen skjer gjerne via en buss. Dette har betydning for hvor godt denne
11
12 3.1 Minnearkitekturer tilnærmingsmåten skalerer.
Slike systemer kalles tett koblede fordi ressursene deles i så stor grad. Når alle prosessorer har lik tilgang til alle periferienheter kalles systemet for en sym- metrisk multiprosessor (SMP). En skjematisk fremstilling av «Uniform Me- mory Architecture» (UMA) er vist i figur3.1.
Interconnect (Buss, crossbar etc)
P2 Pn
00 1100110011 01010011
P1
Minne I/O
Figur 3.1: Blokkdiagram for UMA (fra [33, side 20]
Mange produsenter har multiprosessorutgaver av sine uniprosessorer, og en slik utvidelse kan derfor være relativt rimelig.
Et eksempel: Intel Pentium Pro
Et konkret eksempel på en produsent som tilbyr både vanlig uniprosessor og symmetrisk multiprosessering er Intels arkitektur for Pentium Pro. Arki- tekturen er laget for at inntil fire prosessorer kan kobles sammen på denne måten[65, side 223]. Det finnes i dag leverandører som bygger maskiner med enda flere prosessorer, 8 og 10 veis, men det er foreløpig usikkert om ytelsen skalerer[24].
Blokkdiagrammet i figur3.2illustrerer arkitekturen.
3.1.2 Ikke-uniform minnetilgang (NUMA)
Et system med fellesminne hvor tilgangstiden til et ord i minnet varierer med hvor dette ordet er lokalisert, benytter ikke-uniform minnetilgang. Denne mo- dellen kalles for «Non-uniform Memory Architecture» (NUMA).
Det er vanlig i slikt design at minnet er distribuert sammen med hver prosessor. Hver prosessor har eget minne, i tillegg til tilgang til de andre pro- sessorenes minne. Minnet, både lokalt og lokalisert hos andre prosessorer, er
3.1 Minnearkitekturer 13
Main
memory bridge
Host/PCI
PCI Bus bridge
Host/PCI
PCI Bus
CPU0 CPU1 CPU2 CPU3
Pentium Pro Bus
Figur 3.2: Blokkdiagram for SMP basert på Pentium Pro (omarbeidet etter [65, side 223]
tilgjengelig i et globalt adresserom.
Tilgangstiden er lavere til minne som er lokalt for prosessoren enn til minne hos en annen prosessor, på grunn av forsinkelsen i sammenkoblings- nettverket.
Dessuten kan man ha rene minnemoduler – det vil si minne uten lokal prosessor – koblet til sammenkoblingsnettverket (interconnect). Dette minnet kalles da for globalt fellesminne. Figur3.3demonstrerer konseptet.
Det er idag vanlig at prosessorer har cache for å forsøke å skjule den store forskjellen i hastighet mellom prosessor og minne. I den arkitekturen som er forklart over, antar vi at cachene er koherente innenfor visse betingelser som bestemmes ved arkitekturen.
Dersom ikke-lokalt minne caches, så må det finnes en protokoll for å sør- ge for at gamle, ugyldige data ikke blir benyttet. Slike protokoller kalles for koherensprotokoller.
NCC-NUMA
Et system basert på en NUMA arkitektur, men som ikke har cache-koherens, kaller vi for «Non-cache coherent NUMA» (NCC-NUMA). Dette betyr at minne som finnes i cache lokalt i flere noder, kan bli inkonsistente dersom én node oppdaterer sin lokale kopi.
Dette i motsetning til en cache-koherent maskin (CC-NUMA), hvor lo- kale kopier enten vil bli ugyldiggjort eller oppdatert ved endringer. I systemer hvor alle oppdateringer mot minne går via én felles minnbuss, kan koherens implementeres ved at de lokale cachene lytter («snooper») på minnebussen.
Det vil si at de undersøker alle skriveoperasjoner, og dersom adressen det skri-
14 3.1 Minnearkitekturer
00 1100110011 01010011
Interconnect (Buss, crossbar etc) P
M1 M2 Mn
Globalt delt minne
1 P2 Pn
Figur 3.3: Blokkdiagram for NUMA
ves til finnes lokalt, så oppdateres den lokale cachen, enten med nye data, eller ved å gjøre kopien ugyldig.
Diskusjon
Ved en bussarkitektur er båndbredden låst, men det er rimelig å koble til en ekstra node på bussen. Imidlertid øker faren for at bussen blir mettet, og ikke tåler et større antall noder.
Dersom man benytter en svitsj og kobler til en ny node med en ekstra port, vil båndbredden øke, men denne ekstra enheten tilkoblet er dyr.
I en ring vil en ekstra tilkoblet node øke den totale båndbredden, men siden avstandene blir større vil forsinkelsen (latency) øke.
Grovt sett er UMA best egnet for en buss, siden tilgangstiden skal være lik uansett hvor data befinner seg, men man kan også tenke seg mer kompliserte løsninger.
Svitsjer, ringer og ulike sammensetninger blir mer aktuelle når vi ønsker å skalere til et stort (hundretalls) noder. Da er nok også NUMA arkitekturer enklere å implementere enn UMA.
Ett eksempel på en slik maskin er (SGI) Cray T3E som skalerer til inntil 2048 CPUer (DEC Alpha EV5) med et logisk globalt adresserom, men fys- isk distribuert minne med inntil 2GB pr. CPU. Den benytter ikke-uniform minnetilgang (NUMA). Sammenkoblingen er i en tredimensjonal kube med GigaRing interconnect[26].
3.2 Prosessoren - regneenheten 15
3.2 Prosessoren - regneenheten
Vi kan dele inn prosessorene i to hovedtyper etter hvilken enhet de bruker i sine matematiske operasjoner: skalare og vektorbaserte prosessorer.
Skalare mikroprosessorer
Den dominerende typen prosessorer i dag kalles for skalare mikroprosessorer.
De produseres i meget stort volum, noe som igjen har medført at de er meget rimelige. Til tross for stadige påstander om at metoden vil nå sin begrensning i ytelse, ser vi fortsatt en stadig forbedring i ytelsen fra år til år.
Den grunnleggende enheten som man regner med i en skalarprosessor vil være enten ett heltall eller ett flyttall. Størrelsen på tallet har øket, og idag er det vanligst med 32-bits heltall, men med 64-bits på vei inn (Alpha, Merced, UltraSparc).
Blant den skalare typen prosessorer finner vi Intels serie fra 8086 og opp til dagens Pentium II med andre implementasjoner av denne arkitekturen (AMD K5, Cyrix 6x86 osv), MIPS, Sparc og mange andre.
Introduksjonen av VLSI-teknologi, og kontinuerlige forbedringer i denne teknologien, har gjort det mulig å benytte et meget stort antall transistorer på én silisiumbrikke, og med økende klokkefrekvens.
Vektorbaserte prosessorer
Mens supermaskinene på 1960-tallet utnyttet muligheter for pipelining og dynamisk skedulering av instruksjoner, ble vektorprosessering den dominer- ende teknologien blant de raskeste maskiner på 1970-tallet. Vektorprosessorer opererer på en serie av heltall eller flyttall, altså på vektorer, i motsetning til skalareprosessorer som brukte ett og ett tall.
I mange vitenskapelige beregninger regner man på vektorer i matriser. Iste- det for en løkke for å beregne hvert element i vektoren, så beregnes her alle elementene samtidig. Antall flyttallsoperasjoner pr klokkeperiode kan dermed bli meget høyt, og dette har vært nøkkelen til denne teknologiens tradisjonelt høye ytelse. Man får altså en mye høyere grad av parallellitet hvis man klarer å utnytte vektorer.
Maskiner fra Cray-selskapene er kanskje de mest kjente basert på dette kon- septet. Idag leverer japanske selskaper som Hitachi, Fujitsu og NEC maskiner med vektorprosessorer, implementert i CMOS.
Normalt har man ikke benyttet vektorprosessoren alene. Istedet har man levert en eller flere vektorprosessorer sammen med en skalarprosessor som hovedprosessor. Denne kan så programmeres til å sette opp og bruke vekto- rprosessoren etter programmererens ønske. Det vil her være et kompromiss
16 3.3 Multiprosessor eller multicomputer mellom den kostnad det er med å sette opp vektorenheten, i forhold til å utføre de samme beregningene i en løkke.
De to maskinene som blir regnet som de første vektorprosessorene var CDC Star-100 og TI ASC[56, side B-38], begge annonsert i 1972. Maski- nene hadde en relativt treg skalarprosessor, og jobbet rett mot minnet, uten registre. Oppstartskostnaden ved å benytte vektorenheten var meget høy, skjæ- ringspunktet for når det lønte seg å benytte vektorprosessoren kunne være på over 50 elementer.
Seymour Cray ved Cray Research annonserte CRAY-1 i 1976, og denne hadde en meget rask skalar prosessor med en klokkeperiode på 12.5 ns (80 MHz), og meget lave oppstartskostnader for bruk av vektorer. Denne brukte registre i beregningene, istedet for å jobbe rett mot minnet. Etterfølgende systemer fra Cray, som CRAY X-MP, delvis CRAY-2 og CRAY Y-MP har blitt regnet som ledende da de ble annonsert.
Konvergens?
Vi har allerede sett at mikroprosessorene har tatt opp idéer fra supermaski- nene som ble bygget på 1960-tallet med hensyn til pipelining og dynamisk skedulering.
Nye instruksjoner for multimedia og beregninger i tre dimensjoner i de skalare mikroprosessorene, som AMDs 3D-Now og Intel KNI og til dels MMX (Matrix Math Extensions, eller Multi Media Extensions som markeds- føringen kalte det) har et innslag av vektorer.
Intels nyeste prosessor våren 1999, Pentium III, har som omtrent enes- te nyhet nye instruksjoner, forkortet KNI, som kan utføre beregninger på fire elementers vektorer, mens AMD K6-2 som ble lansert våren 1998 kun- ne utføre operasjoner på to elementers vektorer. Ulike RISC prosessorer har hatt dette enda lenger, for eksempel finnes det såkalte multimediaoperasjoner i UltraSparc-arkitekturen, i tillegg til 64 bitsloadogstore.
Kanskje ser vi en konvergens ved at de skalare mikroprosessorene også begynner å plukke opp idéer fra 1970-tallets vektorprosessorer?
3.3 Multiprosessor eller multicomputer
Michael Flynn introduserte i 1972 en klassifikasjon av datamaskinarkitektur- er basert på instruksjons- og datastrømmer. Konvensjonsjonelle énprosessors maskiner kan klassifiseres som SISD (single instruction stream over a single data stream).
Dagens parallelle maskiner er MIMD (multiple instruction streams over multiple data streams), og disse henter instruksjoner og data fra lokalt minne.
3.3 Multiprosessor eller multicomputer 17 Dette kan være vanlige mikroprosessorer satt sammen til en parallell maskin.
SIMD (single instruction stream over multiple data streams) er gjerne brukt ved å la én kontrollenhet styre et større antall passive prosesseringsele- menter (PE) med eget minne ved å kringkaste instruksjonene til elementene.
De er ikke nødvendigvis generelle prosessorer, heller spesialtilpasset for opp- gaven.
Hennessey og Patterson hevder at det ikke er bygget kommersielle maski- ner basert på MISD[56, side 637], mens Hwang mener at systolske array kan klassifiseres som MISD fordi en felles datastrøm styres gjennom at array av prosesseringselementer som kan utføre ulike instruksjoner[33, side 11]. Man kan kanskje drøfte om systoliske arrays har vært et kommersielt alternativ.
SIMD kan gjøres ved å la en sentral enhet dekode instruksjonene, og på lik linje med en vektormaskin utføre operasjonene enten på den lokale skalar- prosessoren, eller utføre vektoroperasjoner. Forskjellen er at vektoroperasjon- er distribueres til et antall prosesseringselementer (PE) som er passive ALUer som utfører instruksjoner som den sentrale kontrollenheten bestemmer.
For å løse de største problemer vil man koble sammen flere tusen pro- sessorer eller prosesseringselementer i noe som har blitt kalt Massive Parallell Processing (MPP).
Ett eksempel på en slik maskin er Goodyear MPP med blant annet 16384 prosesseringselementer basert på SIMD modellen. Den brukte en Digital PDP- 11 minimaskin til vanlige beregninger (Program and Data Managment Unit og en VAX11/780 som styremaskin (Host), i tillegg til selve arrayet av pro- sesseringselementer og en egen kontrollenhet for disse[8]. Andre eksempler er MasPar MP-1 og Thinking Machines CM-2 og CM-5, som vi kommer kort tilbake til.
Hva er en multiprosessor?
En maskin som betegnes multiprosessor er en maskin med flere prosessorer som er koblet tett sammen. Med tett sammenkobling menes at ressurser, som for eksempel I/O, deles i høy grad. Den fysiske sammenkoblingen skjer gjerne med en buss, svitsj, ring eller spesielle nettverk[33, side 19].
Det enkleste er en maskin med to prosessorer koblet symmetrisk (SMP) med buss som kommunikasjon mot felles I/O og minnesystem (UMA). Sent- ralisert fellesminne arkitektur kan vi kalle en slik løsning hvor alt minnet deles og er samlet på ett sted. Denne arkitekturen er vanskelig å skalere til et stort antall noder.
Med mer avanserte konfigurasjoner med dyrere, og mer avanserte inter- connect teknologi, kan man lage multiprosessorer med et meget stort antall prosesseringselementer eller CPUer hvor minnet er fysisk distribuert. Dette kalles også for skalerbare distribuerte multiprosessorer.
18 3.3 Multiprosessor eller multicomputer
Hva er en multicomputer?
En multicomputer består av autonome maskiner som på en eller annen måte er koblet sammen slik at de fungerer som eller kan abstraheres som én maskin.
Disse autonome maskinene kan godt være multiprosessorer. Scali leverer sine klynger med doble Pentium II-prosessorer, koblet sammen med SCI som interconnect.
Kommunikasjonen i en multicomputer skjer vanligvis via meldingsutveks- ling, siden det er den kommunikasjonsmodellen som støttes av vanlig nett- verksteknologi.
3.3.1 De raskeste maskiner i 1998
De største maskiner, i form av antall prosessorer, har blitt kalt for Massive Pa- rallell Processors (MPP)-maskiner, og betegnelsen har gjerne vært forbeholdt maskiner med mer enn 100 eller kanskje 1000 prosessorer.
Betegnelsen var meget populært på åttitallet, og på begynnelsen av nittital- let, gjerne i form av SIMD arkitektur, for eksempel med maskiner fra Thinking Machines CM-2, tidligere nevnte Goodyear MPP og MasPar MP-1. Thinking Machines gikk bort ifra en ren SIMD arkitektur med sin neste maskin, CM-5, blant annet fordi maskinen kun kunne kjøre én veldig stor jobb om gangen.
Dessuten var skalarytelsen dårlig, noe som medførte at den kun kunne bruk- es til store, parallelle, og av andre grunner grovkornede parallelle jobber[9].
Dette gjorde maskinen for lite kost-effektiv.
Idag er de raskeste MPP-maskiner stort sett basert på mikroprosessor- er som er hyllevare. CM-5 var basert på kortet til en Sun SparcStation 1, Cray T3E på DEC Alpha og Intel Paragon på Pentium Pro. Dessuten finnes det fortsatt en del vektorprosessorer på topp-500 listen , først og fremst re- presentert ved japanske maskiner fra NEC (SX-4), Hitachi (SR2201/1024, pseudovektor) og Fujitsu (VPP700/116), men også Cray T90 (forøvrig ba- sert på ECL istedet for CMOS). En oversikt over ulike typer superdatamaski- ner finnes i [69].
3.3.2 Klassifisering av MIMD maskiner
Vi kan dele inn Flynns MIMD maskiner etter 2 hovedprinsipper; i multiproses- sorer eller multicomputer, og etter om minnet er distribuert eller sentralt. Når en skalerer en maskin til mange noder, blir et sentralt minne en flaskehals[9].
Nøkkelen til skalerbarhet er derfor distribuert minne.
Man kan benytte kommunikasjonsarkitekturen til å vise forskjellen mellom en multiprosessor og en multicomputer, og bruke dette i en definisjon. Bell definerer at en multicomputer benytter eksplisitte meldinger for å aksessere
3.3 Multiprosessor eller multicomputer 19 minne på andre noder, mens han definerer en multiprosessor som en maskin som har ett felles adresserom, altså fellesminne[9].
3.3.3 Multicomputer kan lage en abstraksjon av DSM
Vi har tidligere sett hvordan meldingsutveksling kan implementeres over felles- minne, for å kjøre programmer som er skrevet for eksplisitt meldingsutveksl- ing. Kan vi gjøre det motsatte?
La oss anta at vi har et parallelt program som har deklarert noen variab- ler som globale. Dette programmet kjører vi så på to ulike maskiner med et nettverk i mellom, en slags multicomputer.
Minnesystemet i en maskin håndterer oversettelse fra virtuelle adresser (som programmet bruker), til fysisk minne i maskinen. Tilknyttet denne over- settelsen er det også ulike beskyttelsesmuligheter; slik at man kan hindre hen- holdsvis all tilgang til siden, kun gi lesetilgang eller full tilgang. Dersom prog- rammet forsøker å utføre en ulovlig tilgang, kalles dette en sidefeil, og opera- tivsystemet vil enten kalle en håndterer for dette, eller terminere programmet.
Ved å hekte oss på sidefeilshåndtereren og ved å manipulere beskyttelses- tabellen kan vi vite når programmet prøver å aksesserere de globale variablene.
Hvis vårt system vet hvilken node som sist skrev til denne variabelen, så kan vi innhente de riktige verdiene, og rette opp beskyttelsen, før vi lar programmet fortsette der det stoppet.
Med denne metoden kan vi lage en fellesminneabstraksjon over maskiner som tilbyr meldingsutveksling. Det har den fordel at vi kan skrive program- mer som bruker fellesminne, istedet for å bruke eksplisitt meldingsutveksling.
Eksisterende programmer skrevet for multiprosessorer bør med minimal inn- sats kunne kjøre på et slikt system. Vi kaller dette for distribuert fellesminne implementert i software («software distributed shared memory»).
For at dette skal fungere særlig bra, er vi avhengig av raske nettverk med relativt bra båndbredde, men ikke minst lav forsinkelse, en konsistensmodell og protokoller for utveksling av data[19].
20
Kapittel 4
Konsistensmodeller
4.1 Innledning
Vanlige uniprosessor datamaskiner tilbyr en enkel og intuitiv minnemodell til programmereren. En load skal alltid returnere den siste verdien skrevet til denne adressen i minnet, og verdien skrevet med enstoreblir returnert av alle etterfølgende load fra denne adressen frem til en ny store på samme adresse.
Modellen er at minnet oppdateres sekvensielt etter rekkefølgen av instruksjo- ner i kildekoden.
Maskinen behøver imidlertid ikke å utføre operasjonene nøyaktig i den spesifiserte rekkefølgen. Både kompilatorer, moderne prosessorerer og min- nesubsystemet kan bytte om på rekkefølgen for å oppnå høyere ytelse, bare resultatet er det samme som om instruksjonene hadde blitt utført sekvensi- elt, dvs at kontroll- og dataavhengigheter blir respektert. Dette gjøres ved flere lag med cacher, buffere, og pipelineteknikker og andre teknikker og algoritmer[56,35].
For multiprosessorsystemer er dette vanskeligere. En del av begrepene blir mer uklare. Hva menes for eksempel med «siste verdien skrevet» når flere pro- sessorer har adgang til det samme minnet? I en NUMA arkitektur vil dessuten flerestore-instruksjoner fra ulike prosessorer/noder til samme lokasjon bruke ulik tid på å nå frem til minnet[33].
Ett av aksiomene for distribuerte systemer er at vi ikke kan forutsette en global klokke[74]. Vi kan vanskelig vite når to minneoperasjoner mot samme adresse fra to noder ble sendt i forhold til hverandre. Rekkefølgen operasjo- nen mottas av minnemodulen kan være motsatt av programrekkefølgen. Ved kommunikasjonsproblemer, eller dersom den ene prosessoren jobber mot lo- kalt minne, og den andre kommer via et nettverk, vil vi kunne ha flere ordner ulik gangtid.
Dette skulle begrunne at vi trenger klare modeller som entydig definerer konsistens, slik at vi kan få deterministiske resultater.
21
22 4.2 Sekvensiell konsistens
4.2 Sekvensiell konsistens
Det er etablert flere modeller for konsistens i flerprosessorsystemer. Modelle- ne spesifiserer i hvilken rekkefølge handlinger (events) utført av én prosessor kommer til syne hos de andre prosessorene.
Den første modellen vi vil nevne, er den klassiske «sequential consistency», som er definert av Leslie Lamport i [45]. Denne kommer nærmest vår intuitive modell for en uniprosessor.
En multiprosessor er sekvensielt konsistent hvis og bare hvis resultatet av en hvilken som helst utførelse er den samme som om operasjonene til alle prosessorene ble utført i en sekvensiell orden, og at operasjonene på hver individuelle prosessor kommer til syne i denne sekvensen i den orden den er spesifisert av sitt program.
00 11 00 11
00 11
00 11
0000 1111
Pn P1
Minne
Figur 4.1: Illustrasjon av sekvensiell konsistens
Vi kan illustrere dette ved å tenke oss et minne med kun én port, og n prosessorer som ønsker tilgang. Tilgangen styres av en svitsj som alternerer mellom prosessorene tilfeldig, se figure4.1.
Denne modellen er konseptuelt enkel – den er lett å forstå, kanskje fordi den minner mest om vår vanlig modell. Dessverre ser det ut til å være vanskelig å implementere denne modellen effektivt, fordi den legger store restriksjoner på mulighetene til å utnytte optimaliseringsmuligheter som allerede finnes i maskinvaren[25].
Mark Hill argumenterer for at fordelen med å programmere med sekven- siell konsistens oppveier den, etter hans mening, minkende forskjellen mellom sekvensiell konsistens og svakere konsistensmodeller. Hans konklusjon er at multiprosessorer bør støtte sekvensiell konsistens[31].
4.3 Prosessorkonsistens (PC) 23
4.2.1 Videreutvikling av modellen
En noe mer formell beskrivelse ble etablert av Dubois m.fl[18]. Begrepene som de definerer er meget nyttige når vi skal diskutere andre, mer løse model- ler også.
Definisjon 1 Performing a memory request
A load byPi is considered performed with respect toPk at a point in time when the issuing of a store to the same address by Pk cannot affect the value returned by theload. AstorebyPi is considered performed with respect toPkat a point in time when an issuedloadto the same address byPkreturns the value defined by this store. (or a subsequent storeto the same location). An access is performed when it is performed with respect to all processors.
Definisjon 2 Performing aloadglobally
A load is globally performed if it is performed and if the storethat is the source of the returned value has been performed.
Med disse to definisjonene kan vi se på følgende betingelse for sekvensiell konsistens, noe endret etter [18] i [25], og illustrert ved figur4.2:
Betingelse 1 Sufficient conditions for sequential consistency
– before aloadis allowed to perform with respect to any other processor, all previous load accesses must be globally perfomed and all previous store accesses must be performed, and
– before astoreis allowed to perform with respect to any other processor, all previous load accesses must be globally performed and all previous store accesses must be performed.
4.3 Prosessorkonsistens (PC)
Prosessorkonsistens[25] er en mellomting mellom sekvensiell og svak konsis- tens, som forklares i seksjon4.4. Denne blir benyttet i betingelsene for release- konsistens.
PC krever at store fra én prosessor kommer til syne i riktig rekkefølge, men den sier ikke noe om hvordan store fra to ulike prosessorer synes hos hverandre eller én tredje prosessor. En annen endring er at en loadetter en store kan passere og hente verdien, uten å måtte vente på at storeer utført globalt (globally performed).
24 4.4 Svak konsistens
m b
a store
load
tid
store performed
Figur 4.2: Alle tidligerestoremå være utført før enload
4.4 Svak konsistens
Om vi innfører synkroniseringspunkter i programmene, og definerer min- neoperasjonene i forhold til disse, får vi en svakere modell.
En optimalisering som vil bryte med sekvensiell konsistens, er pipelining avstore-operasjoner. Etter betingelsen1, må enhverstorevære fullført før en ny store kan utføres. Med synkronisering må programmereren, eventuelt en kompilator, identifisere og legge inn tilstrekkelig med synkronisering.
Svak konsistens (weak consistency) ble definert av Dubois et al i [18]:
Betingelse 2 Conditions for Weak Consistency
– before an ordinaryloadorstoreaccess is allowed to perform with respect to any other processor, all previous synchronization accesses must be performed, and
– before a synchronization access is allowed to perform with respect to any other processor, all previous ordinary loadand storeaccesses must be per- formed, and
– synchronization accesses are sequentially consistent with respect to one ano- ther.
4.5 Release konsistens
I [25] presenterer forfatterne en modell de kaller for «release consistency».
To aksesser er i konflikt dersom de er mot samme adresse, og minst én av dem er enstore. Gitt at disse to aksessene utføres fra to prosessorer,a1oga2, vil her ha et race. Dette paret av operasjoner kalles et konkurrerende par.
4.5 Release konsistens 25 I et produsent-forbruker (producer-consumer) eksempel, vil vi ofte bruke en flaggvariabel for å signalisere til den andre prosessen når det finnes data.
Andre ganger vil man beskytte oppdateringen av en datastruktur ved hjelp av lock og unlock-operasjoner. Slike aksesser kalles for synkroniseringsaksesser.
Disse har to viktige karakteristikker:
– Det er konkurrerende aksesser, ved at den ene prosessoren leser en va- riabel, mens den andre vil skrive til den,
– dessuten brukes disse aksessene til å styre programflyten slik at andre aksesser ikke blir i konflikt.
shared access competing
synchronization acquire release
non-synchronization non-competing
Figur 4.3: Kategorisering av ulike skriveaksesser
De ulike typene skriveaksesser kan kategoriseres slik som vist i figur4.3.
En acquire-aksess skaffer tilgang til et kritisk område (i.e. lock) mens rele- ase går ut (i.e. unlock). Dersom vi vet hva de ulike aksesser gjør, kan vi utnytte dette i en løsere minnemodell. Artikkelen innfører begrepet «Properly labe- led (PL) programs», og viser at programmer hvor konkurrerende aksesser er markert, kan utføres med release consistency og likevel være ekvivalente med sequential consistency.
At et program er PL vil si at et tilstrekkelig antall med aksesser er merk- et som acquire eller release, slik at for alle lovlige interleavinger av aksesser, er hvert par av aksesser som er i konflikt separert av release/acquire. Ifølge beviset skal resultater da være ekvivalent med sekvensiell konsistens[25].
Betingelse 3 Conditions for Release Consistency
– before an ordinaryloadorstoreis allowed to perform with respect to any other processor, all previous acquire accesses must be performed, and – before a release access is allowed to perform with respect to any other proces-
sor, all previous ordinaryloadandstoreaccesses must be performed, and – special accesses are processor consistent with respect to one another.
26 4.5 Release konsistens Vi kan utnytte den kunnskapen vi får om minnebruken ved disse merke- lappene (labler) til å utsette spredningen av de oppdaterte data.
Kapittel 5
Protokoller og CVM
5.1 Protokoller for DSM
Det finnes mange måter å implementere de ulike konsistensmodellene i et DSM-system. I dette kapittelet vil vi gå igjennom ulike implementasjoner av konsistensmodellene. For de protokollene som allerede er implementert i CVM, vil vi også vise til hvordan implementasjonen er gjort der, i den grad det er relevant for forståelsen.
5.1.1 Generelle betraktninger og terminologi
Siden kommunikasjonen er en begrensende faktor, vil vi ønske både å redu- sere antallet meldinger og lengden av dem. Avhengig av den underliggende kommunikasjonsteknologien vil man kunne gjøre ulike kompromisser. F.eks vil det med ethernet i en tradisjonell implementasjon være så stor oppstarts- kostnad i forhold til kostnaden pr. sendte byte, at det vil være viktigere med få meldinger enn korte meldinger[42].
Et sidebasert DSM-system deler større enheter enn et cachelinjebasert sys- tem, den har en grovere granularitet. Dette kan gi øket grad av falsk deling («false sharing»).
Falsk deling vil si at to prosesser skriver til samme side, men ulike adresser i siden. Med optimalt fin granularitet hadde ikke de to prosessene skrevet til samme side. Dersom vi har at kun én prosess kan skrive til en side av gangen, vil vi risikere at skrivetillatelsen til siden hopper mellom de to prosessene. Dette kalles for ping-pong effekten og det vil oftest være meget merkbart for ytelsen til programmet.
Utnyttelse av konsistensmodellenrelease consistency medfører at man kan få redusert kommunikasjonen ved ulike optimaliseringer[37].
27
28 5.1 Protokoller for DSM
5.1.2 Ulike konsepter
Når en side hos en nodeaikke er oppdatert fordi en annen node (b) har skrevet siden senere, nevner litteraturen to måter å sørge for at ikke utdaterte data blir lest. Den éne metoden, kalt invalidate, invaliderer sider som er skrevet til. Disse sidene må da hentes på nytt når noden ønsker å lese eller skrive.
Den andre varianten, update, medfører at noden a sørger for å få overført endringer fra de noder som har skrevet til siden, slik at siden blir oppdatert riktig ved synkroniseringspunkter.
Dersom en side skal oppdateres kan man enten oversende hele siden, eller bruke en annen metode, som kallestwin & diff for å oppdatere endringer fra andre noder. Idet en side blir skrevet til for første gang, vil DSM-systemet lage en kopi – en tvilling (twin). Når så endringene skal propageres, sammenlignes den skrevne siden med originalen. Resultatet blir en diff, en melding som er kortere enn siden, som oppsummerer hvilke endringer som må gjøres for å gjøre en tidligere kopi oppdatert. Dette gir kortere meldinger enn om hele siden skulle vært overført, men det tar selvsagt tid å beregne forskjellene og bygge opp diffen.
Flere av protokollene som implementerer RC kan varieres mellom at én node har eksklusiv skrivetilgang (single writer – SW), eller at flere noder kan skrive samtidig (multiple writers – MW). Spesielt ved MW kan det være nød- vendig å kunne overføre bare endringer fra flere noder, og så settes disse sam- men til en riktig, oppdatert side ved hjelp av twin & diff. Med SW kan man overføre hele siden, men det vil medføre lengre meldinger enn om man ba- re sender endringene. Hva som vil lønne seg, kan variere fra applikasjon til applikasjon[42]
5.1.3 Lokalisering av side
Når en prosessor1 ønsker å lese fra en side som den ikke har rettigheter til, må vi ha en metode for å lokalisere hvor denne siden befinner seg. I CVM har Keleher valgt å ha ha enmanagerfor hver side. Denne vet hvem som til enhver tid har siden. Er det den selv, trengs det én melding for å finne ut hvor siden befinner seg, hvis ikke videresendes forespørselen til den registrerte eieren. I tillegg til svaret tilbake til spørrende node krever dette maksimalt to meldinger (O(2))[42].
I det første sidebaserte DSM-systemet, IVY, brukte man en kjede av sann- synlige eiere(probable owners). Protokollen fungerer slik at alle prosessorer som har hatt en side husker hvem de har gitt den videre til. For å lokalisere en side spør man først den opprinnelige eieren, og deretter følger man kjeden. Li og
1I de følgende avsnitt vil vi bruke prosessor synonymt med prosess. Det kan imidlertid være en forskjell dersom man i en node kjører flere prosesser pr. prosessor, eller om man kjører med et SMP-system. Dette er faktorer som vi ikke ser på i denne oppgaven.
5.1 Protokoller for DSM 29 Hudak viste at man i verste fall vil haO(n+klogn)meldinger for å lokalisere en side i et n-prosessor system med k sidefeil[48]. I gjennomsnitt gir dette maksimaltlognmeldinger pr feil. Allerede ved åtte noder vil man med en sta- tisk manager pr. side ha færre antall meldinger i verste fall (worst-case), enn med probable owner, siden2<log 8. Kelehers simulering viste at vedn= 8, så gav statisk eierskap et snitt på 1.83 meldinger for å lokalisere siden pr miss, mens probable owner gav 1.86[42].
5.1.4 En protokoll for sekvensiell konsistens
I CVM er protokollen implementert slik at det enten eksisterer én node med skrivetillatelse til siden, eller n lesere, hvor n er mellom 0 og antall noder.
Eierskapet til en side flyttes til den som etterspør siden, uavhengig om det var en skrive- eller leseforespørsel.
For å unngå ping-pong effekten, garanteres en prosessor å ha en side i et visst tidsrom (100 ms) før den kan flyttes. Uten denne garantien økte eksek- veringstiden i visse tilfeller med opptil 5 ganger[42].
Når en node ber om skrivetilgang til en side, må alle noder som har en kopi av siden invalidere sine kopier.
5.1.5 Ulike implementasjoner av RC
I DASH har RC blitt brukt slik at man pipelinet skriveoperasjoner til minnet.
Først ved en release ble prosessoren stoppet for å vente på at alle operasjonene var utført[47]. Dette medfører at man reduserer ventingen ved flere etterføl- gende skriveoperasjoner. Man slipper med totalt én venteperiode, istedet for én pr. skriveoperasjon.
For å redusere antallet meldinger, brukte man i Munin en «delayed upda- te que» (DUQ) hvor alle skriveoperasjoner ble bufret. Alle operasjonene ble satt sammen til én melding og sendt samtidig ved release[13]. Denne kaller vi for «eager release consistency» (ERC), fordi den oppdaterer i synkroniserings- punktet. Dette er en ivrig oppdatering, fordi det er mulig å vente til et senere tidspunkt, noe vi skal se straks.
I CVMs implementasjon av ERC, blir endringer propagert til andre pro- sesser med kopi av siden når en skrivende prosess utfører release. For å redu- sere lengden på meldingene, beregnes det en diff som propageres. Prosessen blokkeres frem til den har mottatt bekreftelse på at diffen er mottatt og utført på samtlige noder med kopi[36].
Når acquire skal utføres, lokaliseres den prosessoren som sist gjorde en release, men ingen konsistensinformasjon overføres.
Ved miss lokaliseres eieren av siden via sidens manager, og siden overføres så til den som hadde lesefeil.
30 5.1 Protokoller for DSM
5.1.6 Lazy release consistency (LRC)
Keleher viste ved et eksempel at å sende oppdateringer ved release kan medføre unødvendige meldinger, dersom noen av prosessorene ikke benytter disse da- taene senere. Det er tilstrekkelig å oppdatere kopien av en side som skal endres først ved acquire, istedet for ved release. Da unngår man å sende oppdaterin- ger som aldri vil bli benyttet. Dette kaller Keleher for lazy release consistency (LRC)[36].
Når en prosessor utfører en acquire, må den finne ut hvilke endringer den må se, for å oppdatere sin lokale kopi slik at vi følger definisjonen av RC.
I CVM bruker Keleher happened-before-1(hb1) partiell orden for å definere rekkefølgen på hendelser. HB1 ble definert i [1], men vi velger å presentere Kelehers forenklede variant fra [36]:
Definisjon 3 Happened-before-1 partial order
Shared memory accesses are partially ordered byhappened-before-1, denoted
hb1→, defined as follows:
– Ifa1 anda2 are accesses on the same processor, anda1occours beforea2 in program order, thena1hb1
→ a2.
– If a1 is a release on processor p1, and a2 is an acquire on the same me- mory location on processorp2, anda2returns the value written bya1, then a1hb1→ a2.
– Ifa1hb1→ a2 anda2hb1→ a3, thena1hb1→ a3.
RC krever at før en prosessor fortsetter forbi en acquire, må samtlige tid- ligere aksesser etter hb1→være utført på prosessoren. I CVM garanteres dette ved at det propageres skrivevarsler (write-notices). Vi deler opp eksekveringen i intervaller og nummerer slik at et nytt intervall påbegynnes ved hver spe- sialaksess (i.e. release/acquire, eller barriére).
Hver prosessor har et vektortidsstempel (vector timestamp) for hvert in- tervall. La oss kalle denne Vp(i), hvor ier intervallet hvor dette tidsstempel gjelder for prosessorp. Vektoren inneholder ett element for hver prosessorq, og verdien av elementet for prosessorq er det seneste intervall som er utført (performed) påp. Elementet tilper pr definisjon liki.
Ved en aksessmiss må det, om det ikke finnes en lokal kopi, hentes en kopi av siden. Uansett må differ innhentes for å oppdatere siden slik endringer som har skjedd siden kopien sist ble oppdatert er gjenspeilet.
Ved acquire sender prosessorenp sitt tidsstempel til den som sist utførte en release, q. Prosessorq bruker denne informasjonen til å videresende alle skrivevarsler som den har mottatt for alle intervaller som ikke er utført påp.
5.1 Protokoller for DSM 31 Dersom vi kjører en invalideringsprotokoll, invalideres sider som p nå har mottatt skrivevarsler fra. Er det derimot en oppdateringsprotokoll hen- tes diff’er fra de prosessorer som har skrevet, og disse må så utføres i riktig rekkefølge på den lokale siden. Fordelen med en invalideringsprotokoll er at vi kun henter inn differ når de absolutt trengs, det vil si ved en sidefeil når programmet trenger tilgang til siden. På den annen side vil dette kreve flere meldinger.
Figur5.1demonstrerer protokollen.
Acquire(l)
Write(x) make twin Release(x)
Acquire(l) make diff
apply Read(x) Release(x) piggybacked
diff
Node 1 Node 0
Figur 5.1: Illustrasjon av LRC
Single writer Denne protokollen tillater kun én skrivende prosessor. Der- som den ønsker å skrive, må den innhente eksklusiv skrivetilgang til siden.
Dog kan det finnes mange lesere til én side. Dersom to prosessorer konkurrer- er om å skrive til den samme siden, risikerer vi ping-pong effekten. Protokollen kalles for «Lazy consistency, Single Writer», forkortet LSW.
Multiple writers (LMW) I motsetning til LSW, tillates at flere prosessor- er skriver til den samme siden. Dette håndterer falsk deling («false sharing») slik at vi unngår ping-pong effekten, ved at siden hopper mellom prosessore- ne. Flere prosessorer kan skrive til samme side, og deretter settes endringene sammen ved hjelp av diffene.
En annen fordel ved «Lazy consistency, Multiple Writers» (LMW) er at om en prosessor ønsker å skrive til en side som den allerede har cachet lokalt, er dette en avgjørelse som ikke krever kommunikasjon – den kan tas lokalt.
