Parallellprosessering

Parallellprosessering er et begrep innen IT. Det går ut på å utføre en oppgave på en slik måte at den kan deles opp i flere deloppgaver, som utføres samtidig av flere prosessorer.

Parallellprosessering må ikke forveksles med multitasking, som er å dele en ressurs mellom flere oppgaver. Altså det motsatte av parallellprosessering, som er å dele én oppgave på flere ressurser.

Flere paradigmer for maskinarkitektur

Innen parallellprosessering operer man med flere grunnprinsipper, eller paradigmer. Med andre ord, det finnes flere måter å klassifisere typer parallellprosessering, arkitekturer, osv... Man kan skille mellom

• Tett koblede og løst koblede maskiner
• Måten instruksjoner og datastrømmer er organisert (Flynns taksonomi)
• Hvordan dataene og oppgaven partisjoneres
• Hvor parallelliseringen skjer

Flynns taksonomi

Flynns taksonomi deler parallellprosessering inn i fire typer, basert på partisjonering av data på den ene siden og oppsplitting av instruksjoner på den andre siden. Denne 2 dimensjonale inndelingen ble foreslått av Michael J. Flynn, ved Stanford Universitetet i 1966.

SISD – Single Instruction Stream, Single Data stream

Dette er den sekvensielle enprosessorarkitekturen, kun tatt med for å gjøre taksonomien komplett.

MIMD – Multiple Instruction Stream, Multiple Data stream

Dette er en type parallellprosessering hvor hver enkelt prosessor gjør forskjellige oppgaver på forskjellige data.

SIMD – Single Instruction Stream, Multiple Data stream

Dette er en type arkitektur, der flere prosessorer utfører samme instruksjonen, men på forskjellige datastrømmer. Denne krever at datastrømmene har likt format og struktur og er like i størrelse.

MISD – Multiple Instruction Stream, Single Data stream

Denne arkitekturen er bare mulig ved hjelp av pipeline prinsippet. Ellers ville det være en selvmotsigelse. Dvs, det er ikke mulig for to instruksjoner å utføre forskjellige instruksjoner på samme dataelement samtidig, og beholde en datastrøm ut.

Løst og tett koblede prosessorer

Løst og tett koblede maskiner har forskjellige ulemper og fordeler. Tett koblede maskiner kan løse langt flere oppgaver enn løst koblede, fordi overhead, ved kommunikasjonskostnaden mellom prosessorene, er dramatisk lavere. Ulempen med disse er betydelig mer kostbar maskinvare, programvare og meget høye nedskrivingskostnader. Sistnevnte representerer et risikoaspekt ved en slik investering som er en av de sterkeste motivasjonene for de mer løst koblede arkitekturene. Løst koblede arkitekturer som cluster og grid benytter langt billigere maskiner og kan skaleres uten for store kostnader.

Army of ants og Herd of elephants

Dette er noen analogier for å illustrere to tilnærminger til parallellprosessering. Army of ants er en type parallelliseringsstrategi som går ut på å ha et "massivt" antall billige prosessorer som er tett koblet for effektiv kommunikasjon dem imellom. Normalt en SIMD arkitektur. Analogien er spesielt god siden maur kommuniserer ved hjelp av utskilling av enzymer på kort avstand. De er individuelt svake, utfører en forsvinnende liten del av oppgavene i samfunnet, men er sterke sammen fordi de opptrer i et "massivt" antall.

Herds of elephants er en analogi for få, løst koblede prosessorer.

Elefanter er få i antall men individuelt sterke, utfører store oppgaver, og kan kommunisere på lang avstand.

Dette er typisk en MIMD konfigurasjon.

Massiv parallellprosessering

Massiv parallellprosessering eller massevis parallellprosessering (MPP) er en type parallellprosessering som benytter tett koblede prosessorer. Jo flere prosessorer, jo viktigere er det med god kommunikasjon dem imellom. Dette egner seg til problemer som har store mengder med ensartede data som skal prosesseres på samme måte. En typisk oppgave er strukturelle beregninger med mange parametre som representeres som matriser og vektorer.

Den mest berømte konfigurasjonen er the Connection machine produsert av Thinking Machines. Blant annet brukt til å produsere grafikken i Jurassic Park filmene. Andre produsenter er MasPar, som har navnet sitt etter konseptet.

Koblingsskjema

Et problem med tett koblede prosessorer er layout for koblingsmønsteret. Da kommunikasjonen mellom prosessorene er den mest kritiske faktoren, er det også viktig å finne et koblingsmønster som lar seg implementere effektivt.

De to vanligste formene er Grid (må ikke forveksles med grid computing) og hyperkube.

Hyperkube

Grid

Produsenten NCUBE har navnet sitt etter hyperkube-skjemaet.

For å kommunisere sender prosessorene meldinger seg imellom. I en hyperkube med N prosessorer er avstanden aldri større enn log N. I en grid er avstanden < $sqrtN$

Cluster-prosessering

En regneklynge (engelsk: cluster) er en samling med løst koblede datamaskiner i et nettverk, med relativt stor båndbredde, som samarbeider om å løse en oppgave.

Grid-prosessering

Grid prosessering er den mest løst koblede, og mest distribuerte, formen for parallellprosessering. Typisk distribuert på mange uavhengige datamaskiner på internett.

Minneorganisering

Et fundamentalt problem er hvordan man skal unngå interferens mellom prosessorene. Spesielt påvirker dette minnehåndteringen.

SMP (Symmetric Multi Processing)

Denne konfigurasjonen, som blant annet brukes i multi core prosessorer, tillater to eller flere ensartede prosessorer til å aksessere et felles minne. For å gjøre dette mulig, må tilgangen til de enkelte minnesegmentene administreres strengt. Tidligere var dette en stor programmeringsmessig utfordring, men nå gjøres som oftest i operativsystemet.

NUMA (Non Uniform Memory access)

I non uniform memory access tildeles hver prosessor, eller gruppe av prosessorer, sitt eget minne. Tilgang til dette minnet fra andre prosessorer må gjøres via prosessoren som eier minnet.

Flere typer partisjonering

For å kunne dele en oppgave mellom flere prosessorer må input partisjoneres, slik at en prosessor har sin partisjon. Det finnes to forskjellige måter å partisjonere på

Partisjonering i uavhengige datastrømmer

Når man partisjonerer i uavhengige datastrømmer, finner man et nøkkelbegrep som man kan partisjonere på i datastrømmen. Nøkkelen må være slik at hver partisjon er uavhengig av hverandre. Dette gjelder typene MIMD og SIMD.

Pipelining

Pipelining er analogi til flyten av væske gjennom et rørsystem. Dette er et samlebåndsprinsipp, der resultatet av en operasjon er input til den neste. Denne formen for parallellisering er nyttig når det er høy grad av avhengighet mellom dataene, og følgelig vanskelig å finne en partisjoneringnøkkel. Den er også effektiv når prosesseringen

I tilfellet MISD ovenfor partisjoneres ikke dataene, men det er regler for hvilke prosessorer som kan aksessere hvilket minneområde.

Lavnivå pipelining

På lavnivå (prosessornivå) finnes det egne prosessorer som er designet for å kunne utføre flere basisoperasjoner samtidig. Dette slik at, i utgangspunktet, sekvensielle programmer kan starte på neste instruksjon i programmet for forrige dataelement. For eksempel følgende programinstruksjon:

      A[i]=(B[i]+C[i]*D[i])/E[i] ...;

Samtidig som addisjonen for A[i] utføres, utføres multiplikasjonen for A[i+1] og divisjonen for A[i+2], etc... Logikken for å fordele disse oppgavene er innebygget i kompilatoren. Maskiner som bruker denne formen for pipelining kalles gjerne for vektormaskiner. Den mest kjente produsenten er Cray Inc.

Høynivå pipelining

Ved høynivå pipelining praktiseres en bufring av datastrømmen, slik at flere ensartede buffre sendes i sekvens gjennom pipen. Hvert buffer prosesseres av en separat prosessor som så sender halvfabrikerte data videre til neste prosessor i pipen.

Hvor skjer parallelliseringen?

Parallelliseringen har, siden parallellprosessering kom på moten på midten av 80-tallet, flyttet seg mer og mer fra selve programmene og mot operativsystemet. Det faktum at maskinvaren utviklet seg raskere enn programvareutviklerne klarte å følge etter, gjorde at man krevde mer automatikk i parallelliseringen.

I operativsystemet

To og 4 kjerners CPUer har kommet på markedet de senere årene, og operativsystemene har fulgt etter med innebygd parallellisering av programmer.

Parallelle rammeverk

En annen variant er parallelle rammeverk som mottar halvkompilert kode, som så parallelliseres til å kjøre på vertsmaskinen(e).

Gevinst ved parallellisering

Speedup

Speedup er definert som

        Speedup = T1 / TN
        Hvor T1 er tiden det tar med 1 prosessor og TN er tiden det tar med N prosessorer.

Amdahls lov

Amdahls lov, etter maskinarkitekten Gene Amdahl, sier hvor stor speedup man kan oppnå ved å parallellisere et program. Hvis P er andelen prosesseringsinstruksjoner som kan skje i parallell, og S (= 1-P) er andelen som må skje sekvensielt, så er speedup:

Speedup = 1/((1-P) + P/S)