Modifikasjoner til von Neumann modellen

Modifikasjoner til von Neumann modellen er:

• Caching
• Virtuellt minne
• Low-level parallelizm

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”.

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.

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:

Interconnect networks

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

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.

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.

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.

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:

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(...));

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:

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 );

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);

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.

// (... 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) ;

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…

// 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_mutex_lock(&mutex);
sleep_wait_for_signal(&condition_variable);
pthread_mutex_unlock(&mutex);

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!

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.

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.

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.

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!”.

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.