Wikipendium

Share on Twitter Create compendium
Languages
  • English
+
Edit History
Tools
  • Edit
  • History
  • Share on Twitter

  • Read in English
  • Add language

  • Create new compendium
Log in
Table of Contents
  1. KAPITTEL 1:
    1. Why Parallel computing
  2. Problemer som er for store for dagens datamaskiner:
  3. Det er to typer parallellisering som er vanlig:
  4. Tre typer parallelle systemer
  5. KAPITTEL 2:
    1. The von Neumann architecture
      1. Modifikasjoner til von Neumann modellen
    2. Caching
      1. Cache mapping
      2. Direct mapping
      3. Fult assossiativ mapping
      4. N-way set assosiativt
      5. Optimalisering ved hjelp av cache
    3. Virtuelt minne
    4. Instruction-level parallelism
      1. Pipelining
      2. Multiple Issue
    5. Hardware multi-threading
    6. Parallel hardware
      1. SIMD (Single instruction, multiple data)
      2. Vector-processing units
      3. Graphical processing unit
      4. MIMD (Multiple instruction, multiple data)
        1. Shared memory:
        2. Distributed memory:
      5. Interconnect networks
        1. Shared memory systems
        2. Distributed memory systems, DIRECT
        3. Distributed memory systems, INDIRECT
        4. Latency
        5. Cache coherence
          1. False sharing
    7. Parallel Software
      1. Steg for å parallelisere en for-loop (embarrasingly parallel):
      2. Shared-memory programs
      3. Nondeterminism
      4. Mutual exclution locks (Mutex / locks)
      5. Thread safety
    8. Distributed memory programs
    9. Input/output (I/O)
    10. Performance / ytelse
      1. Speedup and efficiency
      2. Amdahl’s lov
      3. Gustafsons lov
      4. Scalablillity
      5. Taking time:
      6. Fosters methodology er en 4-stegs modell på å lage serielle programmer parallelle.
  6. KAPITTEL 3:
    1. MPI Basics, Getting started:
      1. Instansiere og avslutte MPI, det mest grunnleggende
    2. Communicators
    3. Send og Recieve:
      1. Collectives
      2. All-reduce
      3. Broadcast
      4. Scatter
      5. Gather og All-gather
      6. Derived datatypes
      7. Feilhåntering
    4. Feil det er lett å gjøre
  7. KAPITTEL 4:
    1. Shared-memory programming with Pthreads
      1. Critical sections, race-conditions… how to be safe?
        1. Busy-waiting
        2. Mutex
      2. Semaphores
      3. Hvordan synkronisere?
        1. Løsning 1: Busy-waiting + mutex
        2. Løsning 2: Semaphores
        3. Løsning 3: Condition variaber
    2. Read / Write locks
    3. Cache coherence
    4. False sharing
    5. Thread safety
  8. KAPITTEL 5:
    1. Shared-Memory Programming med OpenMP
      1. Pragma / Kompilatordirektiver
      2. Terminologi
      3. Feilsjekking
      4. Kritiske seksjoner:
      5. Smooth reduction
      6. Parallellisering av For-løkker:
      7. Schedule
        1. Schedule typer
      8. Låser; Atomic og Critical
      9. Når skal man bruke hva?
      10. Ting å merke seg:
  9. Extras:
    1. C
      1. Compiler Optimization flags
  10. Pensum:
    1. Grafikkprogrammering med Nvidia CUDA
    2. NVIDIA GPU Arkitektur
    3. Minnesystem på en Nvidia GPU
      1. Globalt minne
      2. Shared memory
      3. Registers
      4. Local memory
      5. L1- & L2 cache
      6. Constant memory
      7. Texture memory
    4. Programmeringsteknikk og optimalisering på GPU
      1. Warp scheduling
      2. Synchronization:
  11. GRAFIKKPROSESSOR:
‹

TDT4200: Parallelle beregninger

Tags:
+

Tips: Practice on exam questions through Kognita

KAPITTEL 1:

Why Parallel computing

Argumentene mot parallell programmering er ingen. Det finnes mange applikasjoner som ikke krever dette, og ikke har det implementert. Som utviklingen går nå vil man få fler og fler kjerner og ikke nødvendigvis raskere kjerner. Økningen i hastighet blir dermed gjennom flere kjerner.

Grunnen til dette er varme. De en-kjernede prosessorene blir for varme. Dette var et problem som ble klart på starten av 2000 tallet. Det er også problematisk med strømforbruk, som nå blir skyhøyt.

Problemer som er for store for dagens datamaskiner:

  • Klima analyse
  • Protein “folding”
  • Utforske nye medisiner
  • Enegriforskning
  • Dataanalyse der datasettene er store

Det er to typer parallellisering som er vanlig:

Task Parallelizm baserer seg på å dele opp flere oppgaver på mange kjerner der alle oppgavene kan kjøres samtidig. Data Parallelizm baserer seg på å dele opp selve datasettet over flere kjerner slik at de kan gjøre noen beregninger hver.

Parallelle programmer må dessuten kommunisere for å koordinere hvem som gjør hva og når de er ferdige. For at programmer skal være raske må man også forsøke å balansere lasten på de forskjellige kjernene ganske likt. Programmet er kun så raskt som sin svakeste kjerne. Synkronisering er også veldig viktig for å passe på at oppgaver blir utført korrekt og at det ikke blir noe skriving med data som kanskje ikke er klar for oppdatering. Synkronisering krever også kommunikasjon.

Tre typer parallelle systemer

Concurrent computing er maskiner som kjører mange individuelle programmer. Et vanlig eksempel er moderne OS. Parallel computing er programmer som kjører parallelt, der fler kjerner jobber med samme oppgave, eller fler maskiner jobber med samme oppgave. Distributed computing er systemer der mange programmer jobber individuelt men samarbeider for å løse et problem.

KAPITTEL 2:

Parallel software and hardware

Kapittel om Software og hardware som kreves for å kunne kjøre programmer i parallell.

The von Neumann architecture

Dette er den klassiske arkitekturen for en datamaskin. Man har en CPU med en eller flere kjerner, så har man minne som er koblet med en 2-veis kobling til CPU. Instruksjoner og data lagres i samme minneenhet. Minne kan hentes opp gjennom minneadresser som er tildelt programmet. Von Neumann modellen kjører kun en instruksjon om gangen, dette gjør den til en SISD modell; Single instruction, single data.

CPU er bestående av to enheter, ALU og Control unit. ALU (Arithmic logical unit) brukes til å faktisk utføre instruksjonene som blir sendt til prosessoren. Control-unit bestemmer hvilken oppgave som skal utføres neste. Dette gjør den ved å lagre minneadresser til programmer som skal kjøre i et register (raskeste formen for minne på datamaskinen).

Denne modellen har et stort problem: minne aksess er tregt. Von neumann modellen baserer seg på å hente ut data veldig hyppig, og oppgaver kan kreve enorme mengder data. Dette gjør at interconnect vil gjøre programmet veldig tregt. Denne flaskehalsen kalles “the von Neumann bottleneck” I 2010 hadde CPUen evnen til å utføre oppgaver 100 ganger raskere enn man kunne hente data fra minnet. Spesifikt er ikke båndbredden den største flaskehalsen på minnet, men ventetiden på data.

Modifikasjoner til von Neumann modellen

Modifikasjoner til von Neumann modellen er:

  • Caching
  • Virtuellt minne
  • Low-level parallelizm

Caching

Caching baserer seg på 2 prinsipper:

  • Ha minnet tilgjengelig nære prosessoren
  • Ha mer data der dataene trengs.

Cache er minnet som er enten ligger internt i CPU eller veldig nære. Det brukes til å mellomlagre data for oppgaver som skal utføres veldig snart. Cachen består av flere nivåer, der øvre nivåer er raskere og med mindre lagringskapasitet, mens nedre nivåer er tregere men har mer kapasitet. Grunnen for denne hiearkiske strukturen er økonomisk.

Nivåene er oftest navngitt “L1”, “L2”, “L3” osv. Det er vanligst med 3 nivåer av cache. Det kan være duplikater i de forskjellige nivåene. Alt som ligger i cache ligger også i hovedminnet (RAM). Data i hovedminnet er ansett som inkonsistent når det er kopiert over til cache. Det blir markert som dirty. Denne statusen forblir inntil endringene i cache blir flyttet/kopiert tilbake til hovedminne, eller droppet fra cache uten endringer.

Overføring fra hovedminnet til cache skjer gjennom cacheblocks/cachelines. Cachelines kommer i større bolker og tillater hurtigere og større overføringer (gjennom større “interconnect”) fra hovedminne over til cache. Cachelines eksisterer for å adressere “locality” problemet.

Locality er når man har akksessert minne et sted og skal akksessere mer minne et annet sted. Da forventer man gjerne at det minnet en skal lokalisere for neste instruksjon er i nærheten. Det finnes to typer Locality:

  • Spatial locality er når man leter etter noe som er i nærheten av minnet man tidligere har akksessert. Eksempel på dette er arrays, når man skal akksessere et entry i en array er det sannsynlig at man også straks skal akksessere neste entry. Derfor kan man hente inn større blokker av arrays slik at neste oppgave alltid ligger klart i cache.
  • Temporal locality er at minnet en forventer å bruke i fremtiden mest trolig er det samme minnet en har bruke i fortiden. Derfor burde minne som CPUen har tatt på ligge varmt i cache i en liten periode. Temporal locality forveksles av og til med prefetching, hvilket er en spekulativ cacheoptimalisering.

Når data for neste instruksjon skal hentes inn til registere sjekkes først cachen, nivå for nivå begynnende med de øverste nivåene. Om man finner det man leter etter i cache kalles dette for et “cache hit“, og om man må inn i hovedminnet for å hente data kalles dette for et “cache miss”.

Cache mapping

Det er tre måter å organisere dataene i cache. Som et eksempel skal vi forsøke å mappe en fire-linjers cache inn i et 16-linjers størrelse cache.

Direct mapping

Direkte mapping tilsier at man allitd skal lagre cachelinjer fra en index og i rekkefølge. Dette betyr at en 16 linjers cache kan maks inneholde 4 x 4 cachelinjer der hver av dem er plassert på divisjon med 4, så posison 0-3, 4-7, 8-11, 12-15.

Fult assossiativ mapping

I et slikt system kan 4-linjers cachen plasseres vilkårlig innefor en rekkevidde. Dette betyr at det ikke krever rekkefølge. Den første firelinjers cachen kan ha sin første kandidat på posisjon 0, 1, 2, 3. Når en av disse posisjonene er tatt settes neste på plass på en av de andre posisjonene (si 2 er tatt) 0, 1, 3 osv.

N-way set assosiativt

Denne fungerer ganske likt som Fult assosiativt, men her lagres mindre snitt av cachelines sammen i “set”. “ N “ sier til hvor store settet skal være. 2-way set for eksempel vil lagre en 4 linjers cache i 2 set, der hver av settene inneholder to verdier. Disse lagres også vilkårlig innenfor settet. Så et 2-way set vil kunne lagre verdiene til en 4-linjers cacheline med to set, plassert på index 0 og 2, og disse settene kan ha sine individuelle verdier plassert enten på posisjon 0 eller 1 innenfor sitt respektive sett.

Fordelen med de assosiative metodene er at man kan bestemme hvem som skal kastes ut på en mer dynamisk måte. Man må kaste minne for å frigjøre plass til nytt minne. Den mest vanlige heuristikken for å løse frigjøringsproblemet er “least recently used”.

Optimalisering ved hjelp av cache

Utvilkere har ikke direkte kontroll over cache, men på grunn av locality, og prinsippene back spacial locality og temporal locality så kan vi indirekte ta kontroll over cache.

Row-column major sortering baserer seg på å kjenne sitt programmeringsspråk og bruke 2-dimensjonale tabeller korrekt. I C er det row-major sortering, som betyr at en to dimensjonal array er lagret rad for rad i minnet. Om man deretter looper igjennom rad for rad ved ytre løkke vil man få fler cache-hits. Dette vil gå raskere enn om man hadde gått igjennom kolonne for kolonne, grunnet at det hadde blitt mange “cache-misses”.

Virtuelt minne

Virtuelt minne er ekstra minne som skal utvide hovedminnet. Hovedminnet deles av alle kjørende applikasjoner og kan dermed ha være for lite for alle applikasjoner. Virtuelt minne utvider kapasiteten ved å lage et swap-space som ligger på disk. Til swap-space kan man overføre minne som ikke har vært brukt på en stund, slik at datamaskinen ledig kapasitet for andre oppgaver. Dette er en stor flaskehals om det blir gjort feil, siden disk er MYE tregere enn hovedminnet.

For å holde styr på minnnet når man tar i bruk virtuelt minne kan man bruke to teknikker. Boken beskriver Pages som er måten virtuelt minne lagrer ting på. Dette er veldig store blokker bestående gjerne av mange KB. En page-table kan brukes for å holde styr på alle pages som ligger i swap-space, men siden en disk bruker fysiske adresser vil oversettingen av adresser fra page-table være tungt. CPU har dermed fått tildelt en egen cache kalt Translation-lookaside buffer (TLB) som holder på mange (16-512) adresser. På denne måten kan man enkelt hente ut adresser mye raskere.

Hele det virtuelle minnet baserer seg på spacial og temporal locality på den måten at det som ikke er relevant og ikke vil bli brukt i nærmeste fremtid kan legges i swap-space. Siden det er så sinnsykt dyrt å få en page-fault (at noe som skal inn i CPU cache ikke ligger i hovedminnet), må dette unngås, uansett hva.

Instruction-level parallelism

Denne typen endring av von Neumann modellen baserer seg på å kjøre flere instruksjoner samtidig på forskjellige Functional units. Det er to teknikker for dette (begge brukes i alle moderne prosessorer):

Pipelining

Pipelining baserer seg på at mange instruksjoner som er individuelle i seg selv kan gjøres parallelt. Eksempelet i boken viser til en addisjon i en løkke. Løkken er enkelt: $z[i] = a[i] + b[i]$ for en mendge tall.

For pipelining vil dette sees på som fler oppgaver. En oppgave vil være å hente ut $a[i]$ og $b[i]$ fra minnet. En annen vil være å analysere operatorene “+” og “=“. En tredje oppgave vil være å utføre addisjonen. Med pipelining kan analysen av operatorene skje samtidig som neste $a[i+1]$ og $b[i+1]$ hentes ut fra minnet. Analysen av instruksjonene for neste iterasjon kan også skje samtidig som utregningen skjer. Dette er mye raskere.

Multiple Issue

Multiple issue baserer seg på å utføre separete oppgaver samtidig i parallel internt i prosessoren. Pipelining deler opp en oppgave inn i mindre underoppgaver, mens multiple issue fordeler den store oppgaven på mange functional units. For eksempelet med addisjon i løkke over, vil multiple issue utføre $z[i] = a[i] + b[i]$ og $z[i+1] = a[i+1] + b[i+1]$ samtidig på hver enkelt av de functional units.

Dette kan åpenbart ikke utføres på alle oppgaver. Så det vanskelige med mulitple issue er å finne ut hvilke oppgaver som kan tåle utførelse out-of-order. For å gjøre analysen bruker man en teknikk som kalles spekulasjon. Denne teknikken utføres ved compile-time (static speculation) eller ved runtime (dynamic speculation). Spekulasjon analyserer koden for å se hvor multiple issue kan utnyttes. Der den finner steder den tenker er bra og legger den inn tester for å sjekke at resultatene er ekvivalente. Om de ikke er det retter den opp.

En prosessor som støtter dynamic speculation kalles superskalar.

Det er viktig at spekulasjon og multiple issue kan fuckes opp ved bruk av compiler optimizations.

Hardware multi-threading

Hardware multithreading baserer seg på å bytte threads der en thread blir stoppet grunnet f.eks. venting på I/O eller en cache-miss. Når en stopp som dette skjer, kan 1000-vis at instruksjoner rekke å bli utført før stoppet er over. Dette rettes opp med multithreading.

Fine-grained multithreading bytter tråd for hver eneste instruksjon. Dette fjerner helt problemet med stopp, men sakter ned threads som har klart mange instruksjoner etter hverandre veldig.

Coarse-grained multithreading bytter tråd kun når en i/o stopp skjer. Dette fjerner problemet med mange instruksjoner på en enkelt tråd.

Simulatanious multithreading baserer seg på superskalar prosessorer (prosessorer som støtter dynamisk multiple-issue) og forsøker å utføre oppgaver fra enkeltråden på en functional unit og oppgaver fra en annen tråd på en annen functional unit.

Parallel hardware

SIMD (Single instruction, multiple data)

SIMD systemer prosesserer forskjellige data med samme instruksjoner. Dette gjøres med prosessoren gjennom flere ALU (Arithimc logic unit) enheter. For slike problemer er f.eks. vektor addisjon i løkker perfekte problemer som kan løses enkelt. SIMD er av type data-parallelism. Dette er også instruksjonsmetoden som gjør at GPUer er så sinnsykt raskt.

Vector-processing units

Dette er egne prosesseringsenheter som er eksperter på å prosessere vektorer. Der CPU jobber på enkelt-data elementer vil en vektor-processing unit kunne jobbe på flere elementer samtidig (4 - 128 64-bits floats for eksempel). Denne typen prosessor har fordelen at det er SIMD, samme instruksjon på alle data, og den kan dermed planlegge minneaksess til å være optimalt. Den kan også utføre mange oppgaver i parallell.

Kravet til VPUer (Vector Processing units) er at de må ha en konsistent datastrukturer. Den takler strukterer der data er lagret med oppgitte strids, men hvis det er hulter-til-bulter med data i minnet vil den yte dårlig. VPUer er heller ikke veldig skalerbar på større problemer.

Graphical processing unit

GPUer har utrolig mange cores med mange ALU per core. De er utrolig gode på SIMD programmer (egentlig SIMT, Single Instruction, multiple thread). GPUen skalerer veldig bra til store programmer, og jo mer data, jo raskere er GPUen. GPU krever derimot at det er veldig store problemer. Om problemene er små vil GPU være treg grunnet lav klokkehasighet per thread og overhead for å overføre data mellom RAM og VRAM.

Mer spesifikt for dette faget: GPGPU (General Purpose GPU)

MIMD (Multiple instruction, multiple data)

MIMD systemer har fler prosessorer, hver av dem med sin egen ALU, cache og annet. En multicore prosessor er et eksempel på en MIMD om den brukes slik. Det er to typer MIMD systemer:

Shared memory:

Shared memory systems er systemer som deler minne mellom alle instruksjonssettene. De kan lese og skrive til forskjellige steder i samme minne hele tiden. Alle instruksjonsenheter her har en kobling sammen mellom hverandre (interconnect) som også kobler dem til en og samme minnelager. Et eksempel på dette er multicore prosessorer er hver prosessor har sitt eget L1 cache, men de er koblet sammen med resten av cache nivåene og har tilgang til samme minneblokk på hovedminnet. Det er to typer shared memory systems:

  • Uniform memory access (UMA) er når alle instruksjonenheter har tilgang til samme minnebank. Denne typen system er ofte raskere, tryggere (minnekonflikter) og bruker gjerne mindre minne overall.
  • Nonuniform memory access (NUMA) er når man må akksessere en minneblokk gjennom en annen instruksjonsenhet. Denne typen er mer risikabel enn UMA systemer, grunnet at minneakksess kan være ødeleggende for andre som skal akksessere minnet (minnekonflikter). Dessuten kan slike systemer bruke mer minne en UMA systemer.

Distributed memory:

Distributed memory systems er systemer som har individuelt minne og individuelle prosessorer for hver av sine systemer. Dette kan for-eksempel være cluster maskiner der de har mange shared memory systems I form av noder. Disse nodene er gjerne koblet sammen gjennom et interconnect grensensnitt, f.eks. Ethernett. Slike systemer er gjerne heterogene, forskjellige noder kan ha vidt forskjellig hardware.

Interconnect networks

Kommunikasjon i shared og distrubuted memory systems må skje veldig raskt:

Shared memory systems

Shared memory systems bruker busser mellom de forskjellige instruksjonsenhetene for å kommunisere. En buss er en parallel kobling. Jo flere som kobler seg på, jo mer venting er det på at man skal få lov å sende data over bussen, ettersom den ikke har kapasitet til alle. Det finnes to teknikker på å holde styr på hvem som har tilgang til hva.

Switches kan bytte mellom hvem som har tilgang til hvilken bus til hvilken tid. Denne vil gjerne ikke ha så god ytelse fordi at busser tildelt én prosessor kan blokkere for en annen.

Crossbar er en mye raskere og dyrere kobling. Denne bruker en slags bro over koblinger som er oppbrukt slik at man ikke blokkerer like mye når en buss er tildelt en instruksjonsenhet. Crossbar busser er mye raskere enn switches.

Distributed memory systems, DIRECT

Distributed memory systems kan ha to typer koblinger mellom hverandre, direct og indirect.

Direct har hver av sine koblinger koblet direkte til et par med CPU-Minne noder. Det er også to typer strukturer på koblingene, ring og toroidal mesh. Ring kan koble tre noder sammen i en ring. Torodial mesh kan koble 5 enheter inn i en ring, for så å koble sammen ringer. Dette blir for større systemer. Vi vil gjerne se hvor mange koblinger mellom ringene vi kan få. Dette gjøres ved å beregne bisection. Bisection er worst-case tilkobling, og finnes ved å ta kvadratroten av antall koblinger i en toroidal mesh.

Den beste typen tilkobling for distributed memory systems er ved å ha direct tilkobling mellom alle noder i nettverket. Dette vil være mest effektive og raskeste formen for kobling mellom distribuerte systemer. Dette er derimot upraktisk og dyrt for større systemer.

Hypercube er et eksempel på systemer der alle noder er koblet sammen: En hypercube er laget ved at 2 noder koblet sammen er en 1D hypercube, mens en 1D hypercube koblet til en annen 1D hypercube med korrekte koblinger er en 2D hypercube. 2 2D hypercubes koblet sammen blir en 3D hypercube osv. En hypercube er dermed $2d$ noder, der $d$ er antall dimensjoner. En slik kobling er i bruk i virkeligheten og er veldig dyrt. Det er også store krav til båndbredde på alle kabler.

Distributed memory systems, INDIRECT

Denne typen systemer er distribuerte systemer koblet sammen gjennom et switching netverk. Denne styrer hvem som kan snakke med hvem. Det finnes to slike systemer: Crossbar er akkurat det samme som for shared memory systems Omega network er et sett med færre crossbar switches som er koblet sammen for å lage mye kommunikasjon litt billigere. Omega nettverket har $2p \log_2(p)$ crossbar switcher.

Latency

Latency beskriver hvor lang tid det tar å overføre en melding fra en enhet til en annen. Dette kan ofte være bottleneck og er derfor veldig viktig å analysere. Vi kan beregne tiden det tar å overføre en melding, men MERK, her er ikke overhead på å sette opp melding og kommunikasjon tatt med:

Sendetid: $l + \frac{n}{b}$, der $l$ er latency i sekunder, $n$ er antall bytes som skal overførers og $b$ er bytes per sekund.

Cache coherence

Cache coherance er et problem som baserer seg på at to CPUer med separat cache kan ha samme variabel lagret. Hvis CPU1 endrer denne variabelen uten å synkronisere med cache til CPU2 vil det bli cache coherence problemer. Altså, verdien til variabelen vil ikke stemme for CPU2 og når cache er incoherent, hivlket leder til feil. Utvikleren/programmerenen har ikke muligheten til å styre cache, og kan dermed ikke rette opp i dette. Det er to vanlig løsninger for dette:

Snooping cache coherance baserer seg på at cores koblet sammen gjennom en buss vil kunne “broadcaste”/sende meldinger ut til alle andre når en verdi har blitt endret. "Snooping" er når andre cores lytter etter slike broadcast meldinger. Om noen har en variabel som har blitt endret vil denne variabelen bli markert som “invalid”. Merk: Det er ofte hele cachelines som blir broadcastet som endret. Dette er en tung operasjon som i store nettverk ikke lønner seg.


Directory based cache coherance baserer seg på en datastruktur som holder på informasjon om alle cachelines som er i bruk. Denne datastrukturen må da være en distribuert structur. Når en core henter ut data fra datastrukuren vil det markeres i datastrukturen. De andre kjernene som har akksess på samme cacheline vil bli fortalt at det har skjedd en endring.

False sharing

False sharing er et problem som skjer der cache coherence håndteres ved hjelp av cachelines (Cache opererer alltid med cachelines, ettersom cache er implementert i hardware). Når cachelines blir hentet opp i minnet til en core vil alle andre cores som bruker denne cacheline få sine cachelines invalidated. Dette betyr at de må hente inn sin versjon cachelinen på nytt.

Dette er først et problem når f.eks. flere cores jobber på samme array, der hele arrayen kan lastes inn i minnet. Om alle cores jobber med samme array, og alle henter inn arrayen som cacheline vil hver og en av dem måtte refreshe sin versjon hele tiden fordi den blir hentet opp av en annen core.

Grunnet til å bruke distributed memory over shared memory er kostnad. Det er ekstremt dyrt å lage interconnect for et ordentlig storskala shared memory system grunnet kostnaden til crossbars. Disse er dyre for enkeltmaskiner også, så for større clustere bruker man distributed memory fordi det er veldig billig i forhold.

Parallel Software

Boken vil hovedsakelig fokusere på SPMD (Single Program Multiple Data) som er f.eks. et program implementert i MPI, Pthreads eller openMP. Denne typen program støtter både data-parallelism og task-parallelism. Dette gjøres ved å lage egne brancher der man gjør forskjellige ting basert på tråd ID. Det er noen saker som skal inn for å gjøre et SPMD program data-parallelt:

Steg for å parallelisere en for-loop (embarrasingly parallel):

  • Del opp arbeidsmengden mellom prosesser/tråder. Dette må gjøres gjevnt (load balancing).
  • Synkroniser prosesser/tråder
  • Kommuniser mellom prosesser/tråder

Shared-memory programs

Disse programmene kjøres kun med tråder, siden prosesser ikke kan ha delt minne mellom seg. Vi kan gjøre variabler private for en enkelt tråd eller globale for alle tråder. Generelt er variabler på stakken private, og variabler på heapen/statiske variabler(i DATA segmentet) er globale/delte.

Kommunikasjon er gjerne gjort gjennom delte variabler. Det er to hovedmetoder for å bruke threads:

Dynamic threads er tråder man kan spawne/starte mens programmet kjører. Disse vil synkronisere seg og dø når oppgaven dens er ferdig. Dette er veldig effektivt bruk av ressursene til systemet. Det krever derimot litt overhead for å lage tråder. Trådene blir laget og data blir delt ut av master tråden.

Static threads er tråder som blir alle spawnet samtidig ved starten av programmet. Alle threads vil jobbe samtidig og leve helt til programmet er ferdig. Når det er ferdig vil det skje en synkronisering og programmet vil terminere (master kan kanskje gjøre noe cleanup). Dette er effektivt der det er veldig balanserte oppgaver slik at alle trådene jobber mye hele tiden. Det kan være veldig ineffektivt der tråder kan ende opp med å stå “idle” mens andre tråder er ferdig.

Begge metodene kan brukes, man må vurdere når man skal bruke hvilken.

Nondeterminism

Nondeterminism er når et program med to tråder/prosesser som jobber uavhengig av hverandre. Hvor fort en oppgave blir fullført er opp til den enkelte prosessen. Dette er vanligvis ikke noe problem, og er aldri noe problem for prosesser. Med et nondeterministic program vet man aldri hva utfallet av programmet vil bli.

Når man jobber mot globale variabler kan dette skape en race condition. En race condtion (ordet kommer fra hesteløp, horse race) oppstår i programmer der resultatet av programmet er avhengig av hvilken tråd om blir ferdig med arbeidet sitt først. Dette er ikke bra programmering. Deler av et program som skal utføre logikk som er essensiellt at det er synkronisert, og kun egentlig burde utføres av én av trådene, kalles critical section.

Å passe på at en critical section blir utført serielt, kun av en tråd, krever at vi gjør den delen av programmet mutually exclusive til den enkelte tråden som skal fullføre den delen av koden.

Mutual exclution locks (Mutex / locks)

Mutex er en lås som gjør at en bit av et program er synkronisert og utføres serielt. Dette implementeres ved å:

  • Der det er en kritisk del av programmet, sett opp en lås (mutex) før utførelse.
  • Få programmet til å "skaffe" låsen før den kritiske blokken
  • Alle andre tråder blir tvunget til å vente hvis låsen allerede er skaffet av noen andre.
  • Utfør den kritiske blokken av programmet.
  • Når den kritiske delen er fullført, frigjør låsen og send signal til de som venter på låsen.
  • Alle trådene kan nå fortsette med resten av programmet med parallell utførelse.

Busy wait er en annen teknikk for å passe på synkronisert utførelse. Dette involverer en while loop som ligger å spinner til loopens “condition” er blitt forfylt. Dette kan f.eks. gjøres gjennom en atomisk “klar” boolean variabel som kan settes true av en annen tråd når den enkelte tråden skal ut av løkken. Dette er bortkastet ressurser.

Andre måter å passe på kritiske seksjoner av programmet er via semaphores og transactions.

Thread safety

Thread safety er et utrykk som blir brukt for funksjoner som er trygge å bruke i en parallelt kontekst. Om en funksjon ikke er thread-safe betyr dette at den ikke kan brukes med multithreading. Det er mulig at et ikke-thread-safe program som kjører parallelt vil miste eller ødelegge data. Dette er ikke ønsket.

Distributed memory programs

Distribuert minne systemer jobber ved at de spawner flere prosesser. For SPMD skjer dette ved oppstart av programmet. For distributed memory programs er det mest brukte APIet kalt MPI (Message passing interface). Det er et par krav til slike Message passing APIer:

  • Det burde ha Send: Dette er oftest blocking, men trenger ikke være det.
  • Det burde ha Recieve: Dette er oftest blocking, men trenger ikke være det.
  • Det burde ha “collective” funksjoner som reduce og broadcast. Dette kan gjøres fra en prosess til mange prosesser.
  • Kommunikasjon er tungt og krever mye oppsett fra utvikleren. Dette er mye mer “lav nivå” enn andre APIer som f.eks. OpenMP.

Minne er også smertefult å styre. En må enten ha kopier av all nødvendig data for hver eneste tråd, eller sende data frem og tilbake hele tiden. Hva som lønner seg kommer ann på oppgaven, dataen og mengden kommunikasjon. Man ønsker gjerne så lite kommunikasjon som mulig, siden dette er blocking og vil la prosesser stå på vent.

Det finnes også programmeringsspråk som forsøker å lage shared memory programs for distributed memory systems. Disse er gjerne dårlige og gir tilsvarende resultater. Bedre å bare unngå disse. Andre systemer bruker også en blanding av shared og distributed memory systems. Dette er vanskelig å programmere men kan gi veldig god ytelse.

Input/output (I/O)

I/O er et vanskelig problem for parallelle systemer. Det er et par generelle regler som må følges:

  • Å lese data skal kun skje for en prosess / tråd. Dette er fordi de standard C funksjonene for I/O er laget for serielle programmer.
  • Standard out (konsollen) burde kun brukes av én prosess. Ved debug kan hvem som helst skrive til stdout, men dette krever som oftest markering av rank/tråd ID for hver utskrift. Alle tråder/prosesser har tilgang til stdout.
  • Å skrive til fil skal kun skje med en prosess per fil. Dette er fordi å skrive med flere prosesser er non-deterministic.

Performance / ytelse

Hvordan måle ytelsen for et system? Dette er jo hele grunnen til at vi lager parallelle programmer.

Speedup and efficiency

Linear speedup er speedup der speedup har det perfekte forholdet til antall cores. aka, hvis et serielt program tar $T_s$ tid, vil vårt parallelle program ta $T_p = T_s / n_{cores}$. Dette krever at programmet er helt uten overhead. Dette er i praksis umulig. Vi kan derfor ikke regne ut kjøretiden på et parallellt program med denne metoden.

Speedup er et regnestykke som kommer av antall ganger den serielle tiden går opp i den parallelle.

Dette vil gi $S=4$, altså en 4x speedup der programmet er akkurat fire ganger raskere på den parallelle versjonen vs den serielle versjonen. Det er viktig å merke seg at jo flere prosesser/tråder som jobber på et problem, jo mer overhead blir det på å lage alle prosessene/trådene. Dette betyr at $S$ blir mindre ved flere threads. Dette er ikke nødvendigvis korrekt presentasjon av programmets ytelse. Vi definerer også derfor efficiency

Amdahl’s lov

Amdahls lov sier at man ikke kan få en større speedup enn hvor stor del av programmet som er paralleliserbar. Om programmet du har skrevet har 90% av koden sin parallelliserbar kan man maksimalt få en speedup på 10x. Dette kommer av at den serielle delen av programmet uansett vil ta like lang tid, samme om hvor mange kjerner eller threads man kaster på problemet.

For et problem som er 90% parallelliserbart og tar 20 sekunder å kjøre serielt, vil man kunne få en en parallell kjøretid på $$T_{parallel} = 0.9 \cdot T_{serial}/p + 0.1 \cdot T_{serial} = 18/p + 2 $$ Man kan så regne speedup som vanlig:

$$ S = \frac{T_{serial}}{T_{parallel}} = \frac{20}{18/p + 2} \leq 10 $$

Merk at når $p$ blir større, altså når vi legger til flere cores, vil kjøretiden $T_{parallel}$ bli dominert av leddet $0.1 \cdot T_{serial}$ som vil gi en nedre begrensing på $T_{parallel}$. Dermed får vi en øvre grense på speedup, $S \leq 10$.

Amdahls lov sier at vi kan maksimalt få en speedup på $1/r$ der $r$ er den brøkdelen av programmet vårt som ikke lar seg parallellisere. I eksempelet ovenfor har vi $r = 1 / 10$ og får dermed at $S \leq 1 / r = 10$. Vi kan altså ikke få en større speedup enn 10x i eksempelet.

Gustafsons lov

Amdahls lov tar ikke problemstørrelsen inn i bildet og ser på speedup ved en konstant problemstørrelse. Ofte vil det være slik at om man øker problemstørrelsen vil den serielle brøkdelen av programmet bli mindre. Dette kan man utnytte, og det er akkurat dette Gustafsons lov tar for seg:

Gustafsons lov fikser det store problemet med Amdahls lov som antar at problemstørrelsen er gitt til en kjent størrelse. Gustafson's law tar høyde for dette og gir en bedre beregning av kjøretid. Man kan regne ut mulig speedup med Gustafson's law. La $P$ være antall prosessorer og $\alpha$ er den serielle brøkdelen av programmet. Da får vi:

$$ S = P - \alpha (P - 1)$$

Dette gir oss et lineært forhold mellom mulig speedup $S$ og problemstørrelsen $N$.

Scalablillity

Scalabillity er gitt ved formelen

TODO: MISSING

,der $n$ er problemstørrelsen og $p$ er antall prosessorer

Dette gir oss en efficiency for det nåværedne problemet, som sett tidligere. For å regne ut hvor skalerbart systemet er, kan man anaylsere hvordan efficiency endrer seg i forhold til problemstørrelse. Dette er gitt ved formelen:

TODO: MISSING

Der $x$ er antall ganger problemstørrelsen blir multiplisert, og $k$ er antall ganger fler cores. Ved denne formelen kan vi se to ting, om $x$ og $k$ øker likt og $E$ forblir det samme har vi weak scaling. Om vi kan øke $k$ uten å øke $x$ og samtidig få beholde samme $E$, vil vi ha strong scaling.

Weak scaling er når man må øke problemstørrelsen (xn) med samme rate som antall cores (kp) for å beholde efficiency (E).

Strong scaling er når man kan øke antall cores (kp) uten å øke problemstørrelsen (xn) og fortsatt ha samme efficiency(E).

Taking time:

Når vi tar tid er det viktig å tenke på hvorfor vi tar tid. Ønsker vi å se på tiden vi bruker på en enkelt funksjon eller ønsker vi å se hvor mye tid kommunikasjon bruker? Tid for maskinen skal taes med kun en kjerne. Vi bruker alltid funksjonen walltime.

Fosters methodology er en 4-stegs modell på å lage serielle programmer parallelle.

  • Partitioning: Identifiser oppgaver som kan kjøres parallellt.
  • Communication: Hvordan kommunikasjon trengs for å få oppgavene utført?
  • Aggregering: Kombiner oppgavene fra resultatet over inn i større oppgaver og se hvilken som må fullføres i forhold til resten.
  • Mapping: Gi oppgavene til forskjellige prosesser slik at datamengden blir veldig likt fordelt, og forsøk å holde kommunikasjonen til et minimum.

KAPITTEL 3:

Distributed-Memory programming with MPI.

Kapittel om Message Passing Interface (MPI) APIet.

MPI Basics, Getting started:

For å lage et program med MPI bruker man compileren “mpicc”. Denne er en wrapper for selve GCC compileren eller CLANG compileren. For å kjøre et MPI program kan man bruke “mpiexec”.

mpicc -g -wall -o mpi-basics MPI_basics.c    # Kompilere programmet
mpiexec -np 4 ./mpi-basics                   # Kjøre programmet

Disse linjene kompilerer og kjører programmet “mpi-basics”. Opsjonen -np står for *Number (of) processes*. Her blir det satt til 4 prosessorer. Programmet kjører så med fire instanser. De fleste implementasjoner av MPI støtter også mpirun, er opsjonen istedet heter -N.

Instansiere og avslutte MPI, det mest grunnleggende

For å starte å bruke MPI i et program må man inkludere mpi.h. Denne headerfila inneholder dekarasjonene til alle MPI funksjonene. Merk, alle MPI funksjoner begynner med MPI_ etterfulgt av funksjonsnavnet med stor forbokstav.

MPI startes ved bruk av

MPI_Init( int* argc_p, char*** argv_p );

Denne funksjonen gjør all nødvendig oppsett av MPI. Etterpå kan man ta i bruk MPI. Man må ikke bruke de to oppgitte parameterene og kan egentlig sette dem til NULL:

`MPI_Init(NULL, NULL);`

De to argumentene skal være samvarende til “argv” og “argc” i main metoden om de blir brukt.

Man kan avslutte MPI ved å bruke:

MPI_Finalize( void );

Denne funksjonen frier opp ressurser brukt av MPI, slik at minnet og alle variablene allokert med MPI blir frigjort.

Man skal aldri bruke MPI før MPI_Init eller etter MPI_Finalize. All kode som har med MPI og med parallellisering å gjøre skal ligge imellom disse to handlingen.

Communicators

Communicators i MPI er kanaler som kobler sammen forskjellige kjerner for kommunikasjon. Den mest vanlige er MPI_COMM_WORLD, som er en global kanal for alle kjerner.

Dette er en konstant definert i mpi.h. En kan selvfølgelig også lage sine egne communicators, som vi gjorde i innleveringen med bilder. (MPI_Cartesian_comm for eksempel)

Når man har bestemt hvilken communicator man skal bruke, kan man hente ut identifikatoren til kjernen (rank) og antall kjerner (size) som er med i kanalen med følgende funksjoner:

MPI_Comm_size( MPI_Comm comm, int* comm_sz_p );
MPI_Comm_rank( MPI_Comm comm, int* my_rank_p );

Eksempelbruk for MPI_COMM_WORLD:

int rank, size;
MPI_Comm_size( MPI_COMM_WORLD, &size );
MPI_Comm_rank( MPI_COMM_WORLD, &rank );

Send og Recieve:

MPI_Send og MPI_Recv er de to funksjonene som brukes til én-veis kommunikasjon. Denne typen kommunikasjon går fra kjernen som sender til kjernen som mottar.

MPI_Send(
    void*        buffer,       // The pointer to whatever data you are sending
    int          size,         // Number of elements if it is an array, set to 1 otherwise.
    MPI_Datatype type,         // Datatype, as defined by MPI
    int          dest,         // The destination rank
    int          tag,          // Tags brukes til å skille mellom like meldinger
    int          communicator  // The communicator, ex. MPI_COMM_WORLD
);

Denne signaturen definerer det vi trenger til å sende en melding med MPI. Merk: siden MPI_Datatype er definert, trenger man ikke å skrive hvor stor plass arrayet skal ta når man bruker size parameteret. Dette blir lengden på arrayen om du sender et array.

De forskjellige datatypene man kan bruke som er default i MPI er:

  • MPI_CHAR
  • MPI_UNSIGNED_CHAR
  • MPI_SHORT
  • MPI_UNSIGNED_SHORT
  • MPI_INT
  • MPI_UNSIGNED
  • MPI_LONG
  • MPI_UNSIGNED_LONG
  • MPI_LONG_LONG
  • MPI_UNSIGNED_LONG_LONG
  • MPI_FLOAT
  • MPI_DOUBLE
  • MPI_LONG_DOUBLE
  • MPI_BYTE
  • MPI_PACKED
  • MPI_Derived_datatype

Tags brukes til å differensiere mellom de forskjellige meldingene som kanskje blir sendt. Man kan sende flere meldinger en-vei, med samme sender og mottaker. Vi burde dermed ha en måte å skille på de forskjellige tilsynelatende like meldingene. Tags lar deg gjøre dette. Det anbefales å bruke en konstant til dette. Det finnes en 'wildcard' tag som kalles MPI_ANY_TAG, som gjør nettopp det den sier.

Mottaker må sette seg opp og gjøre klart for mottakelse:

MPI_Recv(
    void* buffer,          // Pre-allokert minne for mottakelse
    int size,              // Lengden på data som blir mottatt
    MPI_Datatype type,     // Datatype, en av dem i tabellen over
    int source,            // Rank på senderen av meldingen
    int tag,               // Tag for å skille på like meldinger
    MPI_Comm communicator, // comm-kanal, må være samme som hos sender
    MPI_Status* status     // status
);

Merk at dette er nesten identisk parameterliste med MPI_Send. Forskjellen er status. Det er også noen krav til parameterene: size må være lik ved begge partene, det samme gjelder communicator, datatype og tag. source skal være senderprosessen. Det er også viktig at området buffer peker på er enten like stor eller større en tilsvarende buffer hos sender-prosessen.

MPI_Status kan og er ofte sendt med MPI_STATUS_IGNORE. Dette betyr at man ignorerer argumentet. Man kan også bruke et statusobjekt. Statusobjekter inneholder viktig informasjon om sendingen, som source, tag og size. Dette kan virke som redundant informasjon, men når man f.eks. har brukt MPI_ANY_TAG er dette relevant for å hente ut informasjon om den mottatte sendingen.

Collectives

Hittil har vi kun sett på én-veis kommunikasjon mellom 2 parter. MPI_Send og MPI_Recv er kun mellom én sender og én mottaker. Dette er ikke optimalt når man skal gjøre masse-kommunikasjon. MPI har egne funksjoner som kan brukes for å gjøre massekommuniksjon:

For Trapezoid problemet, som er kodet i vedlegget, bruker vi send og recieve for alle worker-tråder inn til main-tråden. Dette er utrolig inneffektivt. Vi kan gjøre dette med en enkel funksjon fra biblioteket til MPI, som vil utføre den totale beregingen med en tre-struktur som vist i modellen under.

Dette gjøres med metoden:

Int MPI_Reduce(
       void*        inputdata,           // What is being sendt into reduction formula
       void*        outputdata,          // Where the result will be stored
       int          count,               // Number of elements to be reduced
       MPI_Datatype type,                // Type being reduced
       MPI_Op       operator,            // Type of reduction, i.e. sum, min, max, product, etc…
       int          destination_process, // Who the result will end up with
       MPI_Comm     comm                 // Communication channel.
);

Metoden burde gjelde for alle prosesser. Dette er da en global kommunikasjonsmetode som gjelder alle prosesser. Merk, operatoren MPI_Op er operatoren som skal utføres under reduksjonen. Denne kan man enten definere selv som et MPI_Op objekt, eller så kan man bruke en av disse medfølgende funksjonene:

Metode Beskrivelse
MPI_MAX Maximum value of all values
MPI_MIN Minimum value of all values
MPI_SUM Sum of all values
MPI_PROD Product of all values
MPI_LAND Logical AND
MPI_BAND Bitwise AND
MPI_LOR Logical OR
MPI_BOR Bitwise OR
MPI_LXOR Logical XOR
MPI_BXOR Bitwise XOR
MPI_MAXLOC Maximum and location of maximum
MPI_MINLOC Minimum and location of minimum

Det er også verdt å merke seg at dette kan gjøres på vektorer også, ved å bruke større size. Dette vil da gjelde for hvert enkelt element i vektoren.

Parameteren outputdata må legges inn av alle som deltar i MPI_Reduce. Denne parameteren vil kun få en verdi for master, slik at alle andre workers må skrive inn en verdi som parameter, men denne verdien kan være NULL, siden det ikke blir lagret noe der for workers uansett.

Det er også ikke tags på collective funksjoner. Det er ikke lov å bruke samme variabel får både inputdata og outputdata grunnet kravet om ingen aliasing.

All-reduce

En variant av MPI_Reduce, all-reduce, samler et totalt resultat, så distribuerer den resultatet til alle prosessene. Dette bruker en slags struktur kalt 'butterfly' der alle prosesser beregner den reduserte summen for alle andre tall. Dette er en massekommunikasjon.

int MPI_Allreduce(
    void*        inputdata,  // What is being sendt into reduction formula
    void*        outputdata, // Where the result will be stored
    int          count,      // Number of elements to be reduced
    MPI_Datatype type,       // Type being reduced
    MPI_Op       operator,   // Type of reduction, i.e. sum, min, max, product, etc…
    MPI_Comm     comm        // Communication channel.
);

Merk at den eneste forskjellen i parameterne her er at all-reduce ikke har noen mottaker, siden alle mottar samme data.

Broadcast

Broadcast sender data fra en prosess over til alle andre prosesser. Dette gjøres i en motsatt trestruktur av den sett ovenfor i reduce. Dette betyr at dataene blir distribuert så parallelt som mulig:

int MPI_Bcast(
    void* payload,          // Som alltid, data som skal sendes ut
    int    count,           // Lengde på array
    MPI_Datatype Datatype,  // Datatype
    int    source,          // Hvem som sender
    MPI_Comm comm);         // Kommunikasjonskanal.

Scatter

Scatter fordeler en mendge data utover mange enkelte prosesser. Dette brukes til å f.eks. fordele arbeidsmengde når man skal gjøre individuelle beregninger på en stor vektor. En master prosess sender ut en hel array av data, og hver enkelt prosess mottar kun den delen de trenger. I ekte tall blir dette $\frac{N}{\text{world size}}$ elementer, der $N$ er størrelsen på listen.

int MPI_Scatter(
    void*        payload,
    int          send_count,
    MPI_Datatype send_type,
    void*        package,
    int          recv_count,
    MPI_Datatype recv_type,
    int          source,
    MPI_Comm     comm);

Her er det en liste som blir sendt og en liste som blir mottatt for alle prosesser. Til og med master prosessen får sin del av datasettet inn via package parameteret. Størrelsen på package bufferet skal alltid være tilsvarende $\frac{N}{\text{world size}}$ eller større.

Gather og All-gather

Disse funksjonene mottar data fra alle andre prosesser inn i en prosess. Dataene blir alltid sortert etter ranken til prosessene. Når man gjør en MPI_Gather vil alle prosesser sende inn sine data, og master vil motta dataene deres sortert i en stor tabell, der først elementene til rank 0 kommer, så elementene sendt fra rank 1, så rank 2 osv. Allgather bygger videre på dette ved å i tillegg til å samle dataene, distribuere det ut igjen.

int MPI_Gather(
    void*         payload,     // Som alltid
    int           send_count,  // Som alltid
    MPI_Datatype  send_type,   // Som alltid
    void*         package,     // kan være NULL om du ikke er master
    int           recv_count,  // Må være total størrelse
    MPI_Datatype  recv_type,   // Som alltid
    int           destination, // Den prosessen som skal samle datene
    MPI_Comm      comm );      // Som alltid

Og allgather, som er veldig lik i signaturen, men inneholder ikke destinasjon:

int MPI_Allgather(
    void*        payload,    // Som alltid
    int          send_count, // Som alltid
    MPI_Datatype send_type,  // Som alltid
    void*        package,    // kan være null om du ikke er master
    int          recv_count, // Må være på total størrelse
    MPI_Datatype recv_type,  // Som alltid
    MPI_Comm     comm );     // Som alltid

Derived datatypes

Om man skal sende data som er forskjellige typer lønner det seg ikke å gjøre flere separate sendinger. Det er derfor gjort mulig å lage 'structs' med MPI. Dette kan gjøre en vanlig struct mulig å sende. Syntaksen for dette er:

int MPI_Create_struct(
    int           count,
    int*          array_of_blocklengths,
    MPI_Aint*     array_of_displacements,
    MPI_Datatype  array_of_datatypes,
    MPI_Datatype* new_datatype_object );

Her er variablene brukt annerledes enn i andre sammenhenger for MPI. Her lager man en struct der man kan sende det utover:

count viser til antall forskjellige variabler i structen. Hvis man skulle sendt int a, double b, string c ville man brukt count=3.

array_of_blocklengths inneholder hvor mange det er av hver datatype hvis de er arrays. Dette blir tilsvarende count i en send/recieve MPI funksjon. Om man kunn sender ett element per variabel, som i count eksempelet ville array_of_blocklengths være {1, 1, 1}.

array_of_displacements beskriver skillet/foringen/paddingen mellom de forskjellige dataene er i sendingen. Hvis man har vilkårlig mange av av en av datatypene er dette ikke helt åpenbart. For å hente ut disse adressene bruker vi en egen MPI metode:

int MPI_Get_address( void* location, MPI_Aint address );

Eksempel med int a, double b, string c:

MPI_Aint a_addr, b_addr, c_addr;
MPI_Get_address(&a, &a_addr);
MPI_Get_address(&b, &b_addr);
MPI_Get_address(&c, &c_addr);
array_of_displacements = {0, b_addr - a_addr, c_addr - a_addr};

array_of_datatypes inneholder datatypene til hver av de tre overnevnte variebalene i rekkefølgen som med de andre arrayene.

Når mån har definert en MPI_derived_type må man commite den før den er klar til bruk:

  int MPI_Type_commit( MPI_Datatype* type );

Feilhåntering

Som du kansje har sett returnerer alle MPI_* metodene en int. Denne inten er en feilkode som bør sjekkes:

int err = MPI_Send(...);
if (err != MPI_SUCCESS) handle(err);

Faglærer liker å bruke macroer for å håntere dette:

#define check(mpi_return_value) \
    if (int err = (mpi_return_value); err != MPI_SUCCESS) handle(err);

check(MPI_Send(...));

Feil det er lett å gjøre

Vranglås (deadlock) er en av de vanligste feilene i parallell programmering.

For å forklare dette bruker vi eksempelet med prosesser som er koblet sammen i en ringform. De skal sende elementer til den neste prosessen i ringen samtidig som de skal motta data fra den forrige.

Dette eksempelet blir lett til ringform fordi MPI_Send kan være blokkerende. Hvis alle noder sender til neste node først, vil ingen noengang komme seg til MPI_Recieve steget. Dette er en vranglås. Programmet vil henge eller kræsje. Dette kan enkelt løses ved å bruke MPI_Sendrecv. Denne metoden gjør både sending og mottakelse:

int MPI_Sendrecv(
    void*        send_buffer,
    int          send_count,
    MPI_Datatype send_type,
    int          destination,
    int          send_tag,
    void*        recv_buffer,
    int          recv_count,
    MPI_Datatype recv_type,
    int          source,
    int          recv_tag,
    MPI_Comm     comm,
    MPI_Status   status);

Som vi ser er dette bare en konkatinering av parameterlistene til send og recieve. Metoden vil synkronisere mottakelse slik at når mange meldigner kaller på denne metoden vil all konflikt som i eksempelet over forsvinne vekk. Magi!

Det er også to andre versjoner av de normale MPI_Send og MPI_Recv, og disse er MPI_Ssend og MPI_Srecv (S=Synchrounous). Denne er blokkerende helt til en Recv metode med sammenhengene parametere vil bli kalt. Om denne ikke noengang finner dette kallet vil programmet bare henge. Da vet vi at vi har deadlock. MPI_Isend og MPI_Irecv (I=Insynchrounous / ASynchrounous). Dette er den ikke-blokkerende varianten til de to metodene. Generelt farlig å bruke.

En annen løsning på ringproblemet er å bruke MPI_Sendrecv. Man kan også bruke det ved å skille mellom prossesser med oddetall og partall ranker:

if      (rank % 2 == 0) {MPI_Send(...); MPI_Recieve(...)}
else if (rank % 2 != 0) {MPI_Recieve(...); MPI_Send(...)}

KAPITTEL 4:

Shared-memory programming with Pthreads

I shared memory systemer er det brukt tråder istedenfor prosesser som i MPI. En prosess kjører sin egen instans av et program. Siden instansene er private, deler prosesser ingenting, og krever andre kommunikasjonskanaler enn delt minne for å sende data frem og tilbake. Prosesser inneholder også veldig mye informasjon om hva den gjør, inkl:

  • Minne til stack
  • Minne til heap
  • Deskriptorer
  • Sikkerhetsinformasjon
  • Informasjon om prosessens tilstand

Threads derimot holder ikke på alt av denne informasjonen. Threads har sin egen kallstack og program-counter. Dette gjør threads mye raskere og billigere å bruke (i forhold til maskinens ressurser). Threads lever under én prosess, så når man lager flere threads vil man ikke få flere instanser av det samme programmet. Hver thread deler mye (men ikke alt) av informasjonen, inkl. minnet.

Siden threads deler minne blir det mye problemer som må håndteres ved bl.a. overskriving. Pthreads er et API som gjelder for UNIX baserte systemer (ingen Windows støtte). Det finnes mange tilsvarende APIer.

For å starte å bruke pthreads må man bruke kompilatorflagget -lpthread:

gcc -g -Wall -o pthread_hello pth_hello.c -lpthread

Pthreads kjører ved at man bruker pthread_create() funksjonen. Denne vil starte en thread til som skal kjøre en spesifikk funksjon. Variabler deklarert inne i denne funksjonen vil bli private for hver thread. Dette grunnet at hver thread har sin individuelle stack.

Hver thread har altså scope rundt der de ble laget. Alle variabler som blir deklarert på stacken til en thread vil være privat. For å lage en thread bruker man syntaksen:

int pthread_create(
    pthread_t *,
    const pthread_attr_t *,
    void * (*)(void *),
    void *
);

Eksempel:

errcode = pthread_create(
    &thread_id,
    &thread_attribute,
    &thread_fun,
    &fun_arg
);

Vi begynner med parameterene fra toppen:

  • pthread_t objekter er objekter som holder på threads. Dette er en 'out' variabel og vil bli gitt en verdi når pthread_create kjører. Man må alltid allokere plass til pthread_t objektene slik at man får lagret alle threads. Dette gjøres vanligvis med malloc/calloc.
  • pthread_attr_t gjør noe, men boken beskriver det ikke.
  • Det tredje argumentet er pekeren/adressen til en funksjon, og denne funksjonen blir kjørt i tråden. Funksjoner som blir kjørt skal må ha denne signaturen slik: void* thread_function(void* arg_p); der thread_function navnet er valgfritt.
  • arg_p er de parameterne som funksjonen oppgitt i tredje parameter skal kalles med. Altså de parameterene som er i funksjonens prototype. Dette argumentet er av typen void*. Void pekere kan castes til alle typer objekter og er dermed dritt. Man bruker et slikt argument i funksjonsbeskrivelsen, men det kan bli utvidet til flere når man har castet.

En annen viktig ting om tråder er at utvikleren har ingen kontroll over hvilken tråd som kjører på hvilken kjerne. Alle kjerner blir tildelt tråder som arbeidsoppgaver av operativsystemet som kjører programmet. I situasjoner der mye arbeid foregår på maskinen kan mange tråder ende opp med å måtte kjøre på samme kjerne. Man kan også lage veldig mange tråder som vil bli fordelt utover mange kjerner av OSet programmet kjører i.

For å stoppe en tråd må man join'e den inn med main-tråden igen. For Pthreads gjøres dette med:

int pthread_join( pthread_t thread, void** return_value );

Første parameter viser til hvilken tråd objekt som skal join'e main-tråden. Det andre parameteret er en peker til der retur-verdien til tråden skal skrives.

Critical sections, race-conditions… how to be safe?

Critical sections er steder i programmet der det er helt kritisk at kun en tråd jobber om gangen. Dette er et fundamentalt problem i shared-memory systems: en kan ikke jobbe flere på samme variabel. Dette vil føre til uventet oppførsel fra programmet grunnet race-conditions (les over). Måtene å løse på dette er mange:

Busy-waiting

Busy-waiting baserer seg på at utvikler setter et flagg (av integer eller bool) som skal holde en tråd i sjakk slik at kritisk arbeid kan bli fullført. Ved compiler optimisations kan man helt ødelegge denne koden. Compiler kan endre rekkefølgen på koden der den ser at det vil gjøre registerforbruk bedre. Dette kan ende i at programmet henger. Når man gjør busy-waiting sover heller ikke tråden, den jobber konstant for å sjekke om flagget har endret seg. Dette koster ressursser. Den eneste fordelen busy-waiting har over mutex er at den kan forsikre rekkefølgen på neste tråd som utfører kritisk arbeid.

Mutex

Mutex er kort for mutually exclusive. Dette er en måte å gjøre kritiske seksjoner trygge, ved å passe på at en kodebit må anskaffe en lås, så kunn én tråd om gangen kan håntere minneområdet som låsen beskytter. Tråden som får gjøre dette er den som har nøkkelen. Det er tre komponenter til en mutex-lock: Selve nøkkelen, som kommer i form av et pthread_mutex_t objekt. Dette objektet må være globalt og må instansieres i programmet. Metodesignaturer:

int pthread_mutex_init(
    pthread_mutex_t mutex,            // Globalt mutex objekt
    const pthread_mutexattr_t* attr); // Blir ikke brukt i boken. NULL

// Låser alle tråder med mutex lock:
int pthread_mutex_lock( pthread_mutex_t mutex );

// Åpner opp for nestemann:
int pthread_mutex_unlock( pthread_mutex_t mutex );

// Ødelegger nøkkelen (firgjør minne osv.)
int pthread_mutex_destroy( pthread_mutex_t mutex );

Et eksempel på bruk av mutex:

pthread_mutex_t key;
int pthread_mutex_init(key, NULL);
//(…)
// Critical section starts:
pthread_mutex_lock(key, NULL);
// critical statements execute …
// Critical Section ends
pthread_mutex_unlock(key, NULL);
// (…) program finishes.
Freeing up memory and key to mutex:
pthread_mutex_destroy(key);

Mutex kan ikke forsikre noen rekkefølge mellom tråder, og gir bare tilgang videre til nestemann så fort som arbeidet er ferdig. Når de andre trådene venter vil de sove, og ikke ikke konstant spine og sjekke et boolsk utrykk. Dette er viktig, fordi når de trådene som gjør busy-waiting teknikken venter bruker de opp verdifull prosessorkraft. Det er også mulig at neste tråd i køen vil bli nedprioritert av prosessoren og da ikke få sjekke om det er dens tur. Dette betyr ekstra venting, selv når det ikke er noe grunn til å måtte vente.

Semaphores

Semaphores er flagg-integer som ikke tilhører noen. De har sine int-verdier koblet opp til spesielle betydninger. Intverdiene kan gå oppover til ukjent mengde, men vi skal se på en spesial-case av semaphores, binary-semaphores (hvordan mutex er laget). Disse består alltid av 2 verdier, 0 og 1:

0 = låst.
1 = ulåst.

Hvordan bruke disse verdiene? Det er fire metoder som er viktig for å bruke semaphores:

#include <semaphore.h>
int sem_init(                     // sem_open on OSX
        sem_t* semaphore,         // The actual semaphore object
        int shared,               // Will not be using this. Constant=0
        unsigned initial_value);  // one of the two statusvalues above

int sem_destroy(sem_t* semaphore); // Destroy semaphore sem_close on OSX
int sem_post(sem_t* semaphore);    // unlocks, will increment the semaphore and notify those waiting
int sem_wait(sem_t* semaphore);    // locks, will try to decrement the semaphore if positive, wait if 0 or below

Med denne informasjonen kan vi utforske hvordan dette er bedre enn mutex-låser og busy-wait. Vel, de tilhører ingen, i motsetning til mutex som blir låst av en bestemt tråd. Dette betyr at man kan utføre venting ved å bestemt la nestemann (som vi kan sette opp til å være hvem som helst vi ønsker) få slippe igjennom.

Når en tråd kaller på sem_wait vil den gjøre to forskjellige ting: Om verdien på semaphore som blir sent inn til sem_wait har verdien 0 (låst), vil den bli blokkert/stoppet. Om verdien på semaphoren er 1 (ulåst) vil den dekrementere verdien, altså sette den til 0 (låst) og fortsette med programmet.

Om en tråd kaller på sem_post vil den inkrementere verdien til semaphoren. Dette betyr at nestemann som er stoppet i sem_wait vil kunne fortsette programmet.

Hvordan synkronisere?

Synkronisering er viktig der vi ønsker at alle trådene skal være på samme nivå i koden. For å synkronisere trådene bruker vi et element kalt “barrier”. Dette er ikke default i alle versjoner av phtreads, slik at vi må implementere det selv. Det er ønskelig å bruke barrieres også til timing. Timing av oppgaver som bruker tråder ønsker vi gjerne at skal være synkroniserte for å få maksimal ytelse når vi måler tiden.

Løsning 1: Busy-waiting + mutex

Dette gjøres ved å ha en busy-waiting løkke like etter en kritisk seksjon. Denne kritiske seksjonen skal kun inneholde en teller. Denne telleren styrer når man kan dra fra Busy wait løkken. Se kode:

// (... some code)
pthread_mutex_lock(key);
counter++;                 // counter er global
pthread_mutex_unlock(key);

// Trådene stopper her, helt til alle har gått igjennom kritisk seksjon
while (counter < total_number_of_threads) ;

Koden har desverre det samme feilene som i vanlig busy-waiting, den kaster bort cpu-sykluser på ingenting. Om man har $n_{\text{threads}} > n_{\text{cores}}$ vil det også muligens ødelegge ytelsen på programmet mye. Det er også problemer med gjenbruk av tellervariabelen, slik at vi trenger mange slike teller per slik synkronisering.

Løsning 2: Semaphores

Denne løsningen er bedre enn den over, der vi får gjenbrukt flere av variablene og slipper unødvendig bruk av cpu-sykler mens vi venter. Løsningen baserer seg på en barriere semaphore og en counter semaphore:

sem_init(&count_sem, 0, 1);
sem_init(&barrier_sem, 0, 0);

// (… some code)
sem_wait(&count_sem);

// ONLY LAST THREAD:
if (counter == threadcount-1) {
    counter=0;
    sem_post(&count_sem);
    for (int j = 0; j < threadcount-1; j++)
        sem_post(&barrier_sem);
}
// EVERYONE ELSE:
else {
    counter++;
    sem_post(&count_sem);
    sem_wait(&barrier_sem);
}
// Synchronized…

I denne løsningen er de fleste variablene gjenbrukbare. Det eneste unntaket er barrier_sem.

Løsning 3: Condition variaber

Condition variabler er betingede variabler som er definert med pthreads APIet. Disse variablene har spesialbetingelser som bestemmer om man skal låse opp en mutex eller ikke. Disse variabelene er av typen pthread_cond_t og har sine egne funksjoner for å interageres med. pthread_cond_t er alltid assossiert med en pthread_mutex_t.

// For å låse en tråd må man bruke denne funksjonen:
int pthread_cond_wait(
    pthread_cond_t* condition_variable,
    pthread_mutex_t* mutex );

// Vil låse opp en av de allerede blokkerte trådene:
int pthread_cond_signal( phread_cond_t* condition_variable );

// Vil låse opp alle de blokkerte trådene:
int pthread_cond_broadcast( phtread_cond_t* condition_variable );

pthread_cond_wait vil stoppe en tråd. I realiten utfører pthread_cond_wait den følgende sekvensen av kode:

pthread_mutex_lock(&mutex);
sleep_wait_for_signal(&condition_variable);
pthread_mutex_unlock(&mutex);

Koden for å lage en barriere med condition variabler ser slik ut:

pthread_cond_t condition_variable;
pthread_mutex_t mutex;

// (*** some code)

pthread_mutex_lock(&mutex);
counter++;
if (counter == thread_count) {
    counter = 0;
    pthread_cond_broadcast(&condition_variable);
}
else {

    // Uforutsette hendelser kan gjøre at en mutex “unlocks”.
    // while løkke brukes derfor I tilfellet dette skjer, for å
    // forsikre. Om det skjer vil pthread_cont_wait() kalles igjen.

    while (pthread_cond_wait(&condition_variable, &mutex) != 0);
}
pthread_mutex_unlock(&mutex);

// SYNCHRONIZED!

Read / Write locks

Lese og skrivelåser er viktige for å holde en liste konsistene. Dette kan utføres ved å bruke mutex låser. Disse låsene kan låse en hel liste når en skriveoperasjon skal skje, siden det ville vært utrygt å bruke en liste mens noen skriver til den. Dette kan skje fordi delen av listen som er i bruk ligger i cache til en thread, slik at man ikke kan se den fra andre threads. Når en samtidig handling så skjer, kan det hende at “dirty” eller invalide data brukes.

Boken beskriver en lenket liste der man enten kan låse hele listen eller låse hver enkelt node, der en node er knyttet til en egen mutex. Dette vil gjøre at resten av listen kan brukes i parallel ved enkelte funksjoner. Med vanlige mutexer blir det vanskelig å skille mellom om en lås er satt der pga. Skriving eller lesing, der lesing er en helt ufarlig handling. Pthreads har en bedre løsning:

Pthreads read-write locks er spesialdefinerte låser som kan definere disse spesialtilfellene. Syntaks:

int pthread_rwlock_init(pthread_rwlock_t* mylock);
int pthread_rwlock_rdlock(pthread_rwlock_t* mylock); // lock object for reading, blocks if any write locks are held
int pthread_rwlock_wrlock(pthread_rwlock_t* mylock); // lock object for writing, blocks all other reads and writes
int pthread_rwlock_unlock(pthread_rwlock_t* mylock); // release the held lock
int pthread_rwlock_destroy(pthread_rwlock_t* mylock);

Cache coherence

Cache coherence er beskrevet tildigere, samme gjelder false sharing, men vi tar det opp igjen.

Cache coherence er når en tråd bruker samme element som en annen tråd i cache. Dette vil gjøre at vi ikke kan vite hvem som får ut sitt resultat. Uansett vil et av resultatene enten bli overskrevet eller feil. Dette kan løses ved å bruke snooping coherence, som holder øye med bussene for å se om noe oppdaterer seg. Hvis det gjør det vil man oppdatere sin egen cache deretter. Man kan også bruke directory based coherence som holder på en datatstuktur laget av hvem som bruker hva i cache.

False sharing

False sharing er et spesielt stort problem når det kommer til lister. Det er viktig å formatere listene korrekt. False sharing er når anti-cache coherence løsninger tvinger tråden til å oppdatere sin egen cacheline der en annen tråd bruker “tilsynelatende” den samme linjen. Dette skjer ved deling av variabeler, og da spesifikt med lister er dette et stort problem.

Om en cache kan hente ut 4 floats (veldig lite i realiteten) om gangen, og den gjøre det for b[0], b[1], b[2], b[3] og en annen tråd henter ut b[3], b[4], b[5], b[6] vil det skape en konflikt av typen false sharing. Siden b[3] er i begge tabellene vil den som lastet inn dataene først bli nødt til å refreshe sin liste. Det er veldig mulig at de ikke jobber direkte på samme data, men dette kan man ikke være sikker på. Dette er ikke et problem i så iten skala, og moderne prosessorer kan hente mye større cachelines.

Thread safety

Thread safety eller “reentrant” (synonym) er et utrykk som brukes til å beskrive om en funksjon eller en blokk med kode er trygg å bruke i parallell ved hjelp av threads. Mange funksjoner har alternative versjoner som er thread-safe. Disse har gjerne funksjoner som er navngitt med _r på slutten (r==reentrant).

KAPITTEL 5:

Shared-Memory Programming med OpenMP

OpenMP er også et API der modellen for systemet er basert på at mange kjerner har tilgang til delt minne.

OpenMP er mye mer høynivå enn det pthreads er, og ble utviklet fordi pthreads er for påtrengende på utviklerne. Dette sparer mye arbeid, men ulempen er tap av finkontroll og avansert funksjonalitet kan være vanskeligere å benytte.

OpenMP er også spesielt egnet til å gjøre et allerede serielt program om til et parallelt program med veldig lite ekstra kode. Dette er et av designmålene til OpenMP: parellelisere uten en eneste kodeendring i den serielle logikken. Dette er nokså unikt, der MPI og Pthreads ville vært veldig tungvindt i forhold.

Pragma / Kompilatordirektiver

OpenMP er ikke støttet av alle C og C++ kompilatorer (Støtte i Clang og MSVC er relativt nytt). Dette kan være problematisk for mange systemer.

OpenMP har alle sine kodelinjer skrevet som kompilatordirektiver (compiler directives/pragmas). Direktiver er kodelinjer som kan ignoreres av kompilatoren dersom den ikke har støtte for funksjonaliteten som ligger bak. Alle linjer med OpenMP kode begynner derfor med:

#pragma omp ...

, der omp er kort for OpenMP.

#pragma omp direktiver påvirker den neste C erkleringen/statementet:

#pragma omp parallel num_thread(8)
printf("foo\n");  // blir kjørt av 8 tråder
printf("bar\n");  // blir kjørt av 1 tråd

// C blokker regnes som ett "statement"
#pragma omp parallel num_thread(8)
{
    printf("foo\n");  // blir kjørt av 8 tråder
    printf("bar\n");  // blir kjørt av 8 tråder
}
// if, while og for løkker er også regnet som ét utrykk.

Programmer som skal bruke OpenMP må kompileres med utvidelen aktivert. For GCC brukes -fopenmp:

gcc -g -Wall -fopenmp -o omp_program omp_code.c

Terminologi

OpenMP setninger er bygget av directives og clauses. Et directive er funksjonen OpenMP skal utføre, og en clause er en parameter til funksjonen som endrer den på en eller annen måte:

#pragma omp parallel num_threads(20)
printf(“[%d/%d]: hello”, omp_get_thread_num(), omp_get_num_threads());

I koden over vil printf funksjonen kjøres parallell i 20 tråder. #pragma setningen har direktivet parallel og clause num_threads(20). Samlet konfigurerer disse paralleliteten. To andre funksjoner som er nevnt er hvordan få tak i rank og antall tråder i teamet.

Teams, master og slave er OpenMP-terminologien på hvem som er hvem i en parallell utførelse:

  • Master er hovedtråden, denne spawner alle de andre trådene.
  • Slave er en av trådene som har blitt spawnet.
  • Team er settet av alle trådene som jobber på oppgaven, kan inneholde både master og slaver.

Skopet for variabler er det samme som for pthreads: Hvis variablen er deklarert av tråden er den privat, ellers er den public. Public variabler kalles i OpenMP for Team-variabler.

Feilsjekking

OpenMP direktiver skal trygt kunne ignoreres er de ikke søttet. For pragmaer er dette trygt, men bruk av OpenMP funksjoner vil feile hvis de ikke er implementert.

Her sjekker vi om OpenMP er tilgjengelig under kompileringen ved bruk av C sin preprosessor:

#ifdef _OPENMP        // OpenMP kode
    int rank = omp_get_thread_num();
    int size = omp_get_num_threads();
#else                 // Kode for ikke-OpenMP
    int rank = 0;
    int size = 1;
#endif

Slik kan man også fritt bruke OpenMP kode der man ønsker, så lenge man også har feilsjekket dette og har noe å falle tilbake på.

Kritiske seksjoner:

Det er vell så viktig å håndere kristiske seksjoner i OpenMP som det er i Pthreads. For å passe på at en blokk med kode er utført låst og trygt bruker man det enkele critical clausen:

#pragma omp critical {
    x = 1;
    y = x + k;
}

Koden som er merket critical vil bli synkronisert på tilsvarende samme måte som mutex låste kodeblokker i phtreads.

Smooth reduction

Vi husker reduksjon/reduce fra MPI. Dette blir brukt til å redusere mange verdier ned til én. For shared-memory systemer er dilemmaet at variabler som blir redusert må være kritiske for å ikke bli overskrevet av hverandre.

Eksempel på reduserende kode (ikke best-practice) med OpenMP:

double global_result = 0.0;
#pragma omp parallel num_threads(4)
{
    double private_result += some_calculations(x, y);
    #pragma omp critical
    global_result += private_result;
}

// JEG LA TIL DENNE VERSJONEN SOM OGSÅ VIL UTFØRE BEREGNINGEN SERIELT (FEIL MÅTE):
#pragma omp parallel num_threads(4)
{
    #pragma omp critical
    global_result += some_calculations(x, y);
}

Reduksjon i OpenMP er smooth og koden over (utenom sidesporet) kan utføres enkelt ved å legge til en reduction clause:

#pragma omp parallel num_threads(4) reduction(+: global_result)
global_result += some_calculations(x, y);

Parallellisering av For-løkker:

This is the bread and butter for OpenMP

OpenMP har smooth funksjonalitet for å dele opp arbeidsmengden i for-løkker. Metoden deler opp arbeidet i blokker, likt fordelt mellom alle tråder, slik som vi har gjort når vi beregnet arbeidsmengden mellom flere tråder tidligere med $\text{workload}=\frac{\text{work}}{n_\text{workers}}$:

double global_result = 0.0;
#pragma omp parallel for num_threads(4) reduction(+: global_result)
for (int x = 0; x < 1000; x++) {
    global_result += some_calculations(x, y)
}

Arbeidet per tråd blir:

$$ \text{workload}=\frac{\text{work}}{n_\text{workers}} = \frac{1000}{4} = 250 $$

Merk: Slike #pragma omp parallel for løkker kan kun paralleliseres slik som vist over. Om det ikke er gitt hvor mange iterasjoner som skal kjøres, eller om det er flere utveier av løkken (break;), må man bruke et annet direktiv for å kjøre koden i parallel. Her vil gcc gi feilmelding ved kompilering.

Det er også andre ting å ta hensyn til, som dataavhengighet, men dette sier seg selv at man må ordne opp i. Dette er opp til utvikleren. Man vil ikke få feilmelding men man vil få rare resultater.

Private variabler kan kan komme fra utsiden også når dataavhengigheter oppstår. Da vil denne setningen være fin:

#pragma omp parallel for num_threads(4) reduction(+: global_result) private(y)
for (int x = 0; x < 1000; x++) {
    global_result += some_calculations(x, y)
}

Det er også mulig å bruke clausen default(none) som gjør at man må definere alle variabeler med private(x, y) eller shared(n) clausene. Her kan ingen variabler brukes uten å defineres i clausen.

En alternativ versjon av for direktivet i OpenMP er #pragma omp for istedenfor #pragma omp parallel for. Forskjellen mellom disse er at ved å legge til parallel vil oppgaven forke flere tråder. Uten parallel vil man enkelt kunne bruke de trådene som allerede er laget. Dette er mye mer ønskelig i mange situasjoner.

Schedule

Scheduling er for OpenMP bestemmelsen om hvordan arbeidsmengden i en løkke som bruker #pragma omp parallel for eller #pragma omp for for å dele ut arbeid over flere tråder. Det kan være ønskelig å ikke ha fordelingen som vist over, der alle får sin egen “blokk” av arbeidsmengden fordelt med $\text{workload}=\frac{\text{work}}{n_\text{workers}}$.

Noen ganger ønsker man syklisk fordeling der hver av trådene får neste indeks ledig i rekkefølgen, fordelt i en syklus. Dette kan være mer gunstig i situasjoner der arbeidsmengden på hver iterasjon varierer og man ikke vil vente på tråden som tar lengst tid.

Syntaks:

 // Schedule syntax: schedule(type, blocksize)
 #pragma omp parallel for num_threads(4) reduction(+: global_result) schedule(static, 1)
 for (int x = 0; x < 1000; x++) {
     global_result += some_calculations(x, y)
 }

blocksize er antall iterasjoner den skal få tildelt; hvor stor en blokk er. Jeg kan se for meg at dette kan hjelpe mot f.eks. false sharing. type er typen scheduling som brukes.

Schedule typer

  • static: Noen ganger ønsker man en syklisk fordeling der hver av trådene får neste indeks ledig i rekkefølgen, fordelt på en syklus. Dette kan være gunstig i situasjoner der arbeidsmengden på hver iterasjon varierer og man ikke vil vente på tråden som tar lengst tid.

  • dynamic og guided tildeler nye iterasjoner av løkken ettersom en tråd er ferdig. Når en tråd har utført en iterasjon vil den kunne forespørre neste. Dette kan være helt ukjent antall steg frem i løkken. Forskjellen mellom dynamic og guided er at guided bestemmer hvor store chucks man skal tildele om gangen for deg.

  • auto bestemmer hvilket schedule som skal brukes ved compiletime og/eller runtime..

  • runtime bestemmer ved runtime hvordan scheduling som skal brukes. Hvilken type som blir valgt er bestemt med environment variablene i skallet.

Det er også viktig å tenke på overhead:

default < static < dynamic < guided

Låser; Atomic og Critical

erm, jeg tror helle denne seksjonen er feil. critical er en mutex på en blokk, og atomic er det som er beskrevet på denne seksjonen som critical. -pbsds

Barrier er også implementert i OpenMP. Dette er mye smoothere enn i Pthreads:

#pragma omp barrier

atomic direktivet er en utvidelse av critical. Der critical mangler en mengde operatorer har atomic disse dekket. Følgende operatorer er støttet: +, *, -, /, &, ^, |, << og >>.

#pragma omp atomic {/* critical code */}

critical støtter kun utrykk på formen: x <op>= <expression>, x++, ++x, x-- og --x.

OpenMP har også direkte støtte for sine egne låser. De fungerer på nesten samme måte som de gjør med pthreads. Det er to typer låser i OpenMP: simple og nested. Forskjellen på disse to er at en nested låser kan låses mange ganger, mens en simple lås kan kun låses én gang. For å lage en lås bruker man objekter av typen omp_lock_t og disse funksjonene:

void omp_init_lock( omp_lock_t* lock );    // initialiere en lås
void omp_set_lock( omp_lock_t* lock );     // anskaffe en lås
void omp_unset_lock( omp_lock_t* lock );   // frigør en lås
void omp_destroy_lock( omp_lock_t* lock ); // destruere en lås

Når skal man bruke hva?

vel, man bruker atomic der det lar seg gjøre, siden denne har mest funksjonalitet og er raskere enn låser. Der man trenger mer enn én linje som er mutex vil man heller bruke låser. critical er også raskt, og brukes der de kan.

Ting å merke seg:

Man skal aldri bruke en variabel to ganger i en kritisk eller atomisk setning. Det er ikke rettferdig rekkefølge på hvem som får tilgang til en kritisk seksjon. Nøstede mutex er farlig grunnet deadlock.

Extras:

C

Compiler Optimization flags

Det er flagg man kan sette i C kompilatoren som vil gjøre flere endringer i programmet ditt under kompileringen. De følgende -O flaggene er egentlig bare samlinger av flere andre små optimaliseringsflagg:

  • gcc -O0 - Ingen optimaliseringer, C koden oversettes nesten direkte til maskinkode.
  • gcc -O1 - Aktiverer billige no-brainer optimaliseringer som constant folding og dead code elimination.
  • gcc -O2 - Ber kompilatoren om gjøre alle optimaliseringer som ikke er et “speed/space tradeoff”.
  • gcc -O3 - Her ber vi kompolatoren om å prøve mye hardere. Her kan kompileringstiden bli "lang".
  • gcc -Ofast - Intensiteten til -O3 med målet om best kjøretid på bekostning av programstørrelse.
  • gcc -Os - Intensiteten til -O3 med målet om minst programstørrelse på bekostning av kjøretid.

Pensum:

Grafikkprogrammering med Nvidia CUDA

Motivasjonen bak grafikkort i HPC er at de er mye raskere og billigere i med henhold til den regnekraften de har. Homogene systemer tar også mer og mer av i industrien. Et homogent system er et system som består av masse forskjellige maskiner, prosessorer og gpuer og jobber sammen i en HPC.

Moores law of extrapolation er Moores law for en énkjærnet prosessor. En enkjærnet prosessor som øker hastigheten for mye blir varmere enn en rakettmotor endepunktet der det er varmest.

NVIDIA GPU Arkitektur

Arkitekturen til en Nvidia GPU er bygd opp på følgende måte:

Grafikkprosessoren har mange kjerner fordelt utover streaming multiprocessors (SM). For forskjellige GPUer med samme arkitektur, er det samme antall kjerner per SM.

For eksempel Pascal arkitekturen har 128 cuda kjerner per SM. Så min GTX 1080 har 20 sm, og dermed 20*128 = 2560 cuda kjerner.

Men GPU gjør ikke alt sitt arbeid direkte med kjernene. Det er mye mer som ligger under. Hver SM inneholder grids. Et Grid betår av mange “thread blocks”. En threadblock er en gruppe på 32x32 tråder. Hver av disse kan utføre koden du skriver i CU filene. Arkitekturen kalles SIMT og er en form for SPMD, men bare litt annerledes.

GPU utfører koden i “warps”. En warp er en samling av tråder som blir instruert med samme “program counter”, samme kodelinje samtidig. Det er maksimalt 32 threads ber warp. Dette betyr at alle threads jobber med en enighet om hvilken kodelinje man skal utføre. Om dette ikke er casen, at man har en warp som utfører forskjellig arbeid på en og samme threadblock har man fått warp divergence.

Stikkord å kunne:

  • Thread
  • Block
  • Grid
  • Streaming multiprocessor
  • Warp
  • Warp divergence

Minnesystem på en Nvidia GPU

GPU består av mange fler nivåer minne enn det CPU-RAM modellen består av. Hierarkiet for minne i en GPU er:

  • Register (per tråd)
  • Local Memory (per tråd).
  • Global memory, minnet som er delt av alle SM
  • Shared memory / L1, L2 cache (varierer fra GPU - GPU hvordan dette er satt opp). Dette er raskt minne delt inni en block.
  • Constant memory, minne som er konstanter. Delt av alle SM
  • Read-only cache.

Det er høyere Delay på minnet i en GPU. Dette kommer av hardware limitasjoenr. Slike limitasjoner er også kalt latency. Her er CPU raskere enn GPU. Siden minnet er så mye tregere er det veldig viktig å styre minnebruk bra. Dette kan ofte være den største bottlenecken for GPU.

Globalt minne

Globalt minne er det tregeste minnet på GPUen. Det er også det minnet det er mest av. Det er tregt å akksessere, slik at vi ønsker å optimalisere hvordan dette minnet brukes. Dette gjøres ved å lage finne mønstre når man akksesserer minne gjennom en metode kalt Memory Coalecing.

Memory coalescing baserer seg på å lese inn så få cachelines som mulig. Dette er utført per warp. For å forklare dette på eksamen må du tegne bildet vist i powerpointene. Du skal hente inn minne helt rett - aligned med trådene. altså, minneakksess skal være sekvensiellt.

Shared memory

Shared memory er veldig raskt minne som ligger inni en SM. Dette minnet er delt over en block. Det er laget med samme hardware som L1 cache, som er veldig raskt. Dette er også programmerbart. Man ønsker å oppnå maskimalt bruk av shared memory ved å laste inn oppgaver fra globalt memory inn i shared memory, så kjøre beregninger med shared memory. Dette gjør at man har så få akksesser av globalt memory som mulig. Effektivt! Når man skriver til Shared memory er det utrolig viktig at man gjør “_syncthreads();” kall.

Bank conflicts kan oppstå når man skal lese fra shared memory med mange tråder. Når mange tråder skal lese fra shared memory må man passe på at de leser i parallell. Når alle trådene skal lese fra samme posisjon av minnet vil det bli seriell utførelse grunnet blokkering mens man leser fra minnet. Det er dermed lurt å passe på at alle leser å skriver til forskjellige deler av minnet. Man kan unngå dette ved å bruke padding teknikken, ved å legge på en ekstra byte.

Bank conflicts kan ikke oppstå noen andre steder enn shared memory. Dette er fordi det oppstår grunnet at fler tråder har tilgang til minnet. I Globalt minne er lesing gjort av warps for å minimere antall kall. Register minnet er kun mulig å akksessere av tråden det hører til.

Registers

Registrene er den raskeste formen for minne på en GPU. Det er i nærheten av 10x raskere enn shared memory. Det er tusenvis av disse per SM. Det er ca. 32 eller 64 av 32bits registre per tråd.

Local memory

Siden der er så lite minne per register har vi local memory. Dette er minne som skal supplere på registerminnet. Det lokale minnet er lagret på Globalt minne og er dermed utrolig tregt. Scope på dette minnet er samme som på registeret, kun per tråd.

Register spilling er når det ikke er fysisk nok lagringsplass for å lagre alle variabler som skal brukes i en beregning. Det overflødige, altså det som ikke får plass i registeret vil bli holdt i local memory. Vi må så laste inn disse dataene fra local memory inn i registere når vi trenger dem til matematikken. Dette er tregt.

L1- & L2 cache

Dette er cacher bygget opp av samme hardware som shared memory. De er litt forskjellige i dimensjoner. L1 cache er kun brukt til local memory. Den varierer i kapasitet, og det er plassert en av disse per Streaming multiprocessor. L2 cache er gjerne større enn L1 cache, men den er delt av alle SM. Den cacher både globale og local memory access.

Constant memory

Constant memory er en spesialisert del av det globale minnet med sin egen cache. Denne delen av minnet kan kun brukes til konstanter. Alle konstanter som skal være tilgjengelige gjennom Constant memory må være satt opp fra host-maskin først. Cache er på ca 8KB per SM

Texture memory

Texture memory er en spesialisert del av minnet laget spesielt for å lagre 1D, 2D og 3D data gjennom en egen “cuda arrays”. Dette er hovedsakelig brukt for interpolation på 1D, 2D og 3D arrrays. Read-only Cache er texture cache for Cuda kort med CC over 3.5. Read-only cache gjør det lettere å ta i burk denne typen minne. Her kan man laste inn konstanter og ikke kreve “static indexing!”.

Programmeringsteknikk og optimalisering på GPU

Det følgende er fra en blanding av Caltech forelesninger og Nvidia sine egne “talks”.

Warp scheduling

Hver gang et program skal kjøre samles det threads opp i warps. Warps kommer i grupper på 32. Hver warp må kjøre samme programkode, dette er beskrevet over. Warp scheduler er egne komponenter på grafikkortet som skal finne en kjerner som er ledige til å utføre en warp.

Når vi ser på arkitekuren til grafikkortene (tallene kommer fra GK110, kepler. Pascal har kodenavn GP10x) ser vi antallet warps som kan utføres per:

Warps per SM: threads / SM = 2048 / 32 = 64 warps.
Warps per block: threads / block = 1024(32x32x1) = 32 warps.

Vi ser dermed at hvor mange warps som kan kjøre på en Streaming multiprocessor er helt avhengig av GPU.

For å beregne hvor bra vi klarer å bruke GPUen ser vi på noe som heter occupancy. Occupancy (norsk: belegg / opptatthet) er hvor mye av gpuen vi utnytter om gangen. Dette er da hvor mange oppgaver i klarer å sette i gang fort nok slik at hele GPU brukes hele tiden. Vi regner occupancy slik:

Occupancy = warps per sm / max warps per sm = warps / 64 (kepler)

Occupancy oppgis som en andel av maksimal bruk av GPU. Vi vil derfor komme oss så nære 100% occupancy som mulig. Dette gjøres ved å queue nok warps.

“VI VIL HOLDE HVER AV MULTIPROSESSORENE SÅ OPPTATT SOM MULIG!” - MARK HARRIS, NVIDIA DEVELOPER TECHNOLOGIES

Det er to andre mål for hvor bra ytelse en GPU har. GFLOPS (Giga floating point operations per second) og bandwidth, hvor mye arbeid vi gjør i samtidighet. For oppgaver der det krever lite flops vil vi optimalisere bandwidth.

Synchronization:

GPU er dårlig på enkelt-oppgaver. Den jobber best i teams. Noen ganger er det f.eks. skrive-konflikter slik som i parallell programmering på CPU. Med CPU kan man enkelt skrive en lås ved bruk av mutex, semaphore eller busy-wait (ikke bruk busy-wait). Dette lønner seg ikke for en GPU der dette krever mye overhead som man ikke har rå til med mindre prosessorkraft per thread. Vi kan bruke Barrierer for å stoppe opp alle trådene og dermed synkronisere. Dette gjøres likt som i CPU programmering. “_syncthreads();”. Dette fungerer kun på block-level.

Som vi husker fra CPU programmering er en atomisk operasjon en operasjon som kun kan utføres serielt. Slike funksjoner kan være ønskelig på GPU også, men ikke på samme utførelse som på CPU. Cuda har egne funksjoner for atomic operasjoner:

atomic<op>( float* address_to_add_to, float number);
// Replace <op> with one: Add, Sub, Exch , Min, Max, Inc , Dec, And, Or, Xor

atomicMax(&x, y);

Dette vil gi bedre ytelse.

Hva hvis vi ønsker å droppe mange av threads når vi jobber med en oppgave?
Mange tilfeller, som reduksjon (gjøre mange verdier om til en verdi) vil man få færre og færre oppgaver per iterasjon i løkken. Gjennom occupancy prinsippet vet vi at vi får best ytelse jo fler warps som er i jobb. Når datamengden blir mindre og mindre vil mange threads bli idle (arbeidsledige). Dette kan ordnes ved å gjøre fler kall til en kernel, der man ved hvert kall reduserer størrelsen på block/threads i kallet. Dette vil gjøre at man kan stoppe en oppgave midt i for å så synkronsiere og utføre oppgaven videre med færre threads.

GRAFIKKPROSESSOR:

SAMMENLIKNING MELLOM OPENCL, CUDA OG AMD:

Hva er forskjellen i programmering? OpenCL krever mye mer Setup enn det cuda gjør. Dette er åpenbart at det blir slik, det er jo støttet mye videre enn cuda, der OpenCL kan kjøre på forskjellige prosessortyper (GPU og CPU) og på plattformer av alle typer. Cuda har mye mer finansiell støtte og har også kundestøtte der OpenCL er open-source og har ingen kundestøtte. Cuda har også større bibliotek enn OpenCL, som gjør at det er raskere i noen sammenhenger.

Man må ikke kompilere koden som skal kjøre på GPU ved runtime når man skal bruke CUDA, men dette må man med OpenCL. Det er veldig “verbose” å skrive opencl kode grunnet setup.

Written by

pbsds PR MatsMoll poppis op
Last updated: Mon, 29 Nov 2021 16:26:45 +0100 .
  • Contact
  • Twitter
  • Statistics
  • Report a bug
  • Wikipendium cc-by-sa
Wikipendium is ad-free and costs nothing to use. Please help keep Wikipendium alive by donating today!