Parallel computing - Parallel computing

IBM's Blue Gene/P massivt parallel supercomputer

Parallel computing er en beregningstype , hvor mange beregninger eller processer udføres samtidigt. Store problemer kan ofte opdeles i mindre, som derefter kan løses samtidigt. Der er flere forskellige former for parallel computing: bit-niveau , instruktionsniveau , data og opgaveparallellisme . Parallelisme har længe været ansat i højtydende computing , men har fået større interesse på grund af de fysiske begrænsninger, der forhindrer frekvensskalering . Da strømforbrug (og dermed varmegenerering) af computere er blevet en bekymring i de seneste år, er parallel computing blevet det dominerende paradigme inden for computerarkitektur , hovedsageligt i form af multi-core processorer .

Parallel computing er tæt forbundet med samtidige computere- de bruges ofte sammen og ofte sammenfaldende, selvom de to er forskellige: det er muligt at have parallelisme uden samtidighed (f.eks. Bit-niveau-parallelisme ) og samtidighed uden parallelisme (f.eks. Multitasking) ved tidsdeling på en single-core CPU). Ved parallel computing opdeles en beregningsopgave typisk i flere, ofte mange, meget lignende underopgaver, der kan behandles uafhængigt, og hvis resultater kombineres bagefter, efter afslutning. I modsætning hertil adresserer de forskellige processer ved samtidig computing ofte ikke relaterede opgaver; når de gør det, som det er typisk for distribueret computing , kan de separate opgaver have en varieret karakter og ofte kræve en vis kommunikation mellem processer under udførelsen.

Parallelle computere kan groft klassificeres efter det niveau, hvor hardwaren understøtter parallelisme, med multi-core- og multi-processor- computere, der har flere behandlingselementer inden for en enkelt maskine, mens klynger , MPP'er og gitre bruger flere computere til at arbejde på samme opgave. Specialiserede parallelle computerarkitekturer bruges undertiden sammen med traditionelle processorer til at accelerere specifikke opgaver.

I nogle tilfælde er parallelisme gennemsigtig for programmøren, f.eks. I bit-niveau eller instruktionsniveau-parallelisme, men eksplicit parallelle algoritmer , især dem, der bruger samtidighed, er sværere at skrive end sekventielle , fordi samtidighed introducerer flere nye klasser af potentiale software bugs , hvoraf raceforhold er de mest almindelige. Kommunikation og synkronisering mellem de forskellige delopgaver er typisk nogle af de største forhindringer for at få optimal parallel programydelse.

En teoretisk øvre grænse for hastigheden af et enkelt program som følge af parallelisering er givet af Amdahls lov .

Baggrund

Traditionelt er computersoftware blevet skrevet til seriel beregning . For at løse et problem konstrueres og implementeres en algoritme som en seriel strøm af instruktioner. Disse instruktioner udføres på en central behandlingsenhed på en computer. Kun en instruktion må udføres ad gangen - efter at instruktionen er færdig, udføres den næste.

Parallel computing bruger derimod flere behandlingselementer samtidigt til at løse et problem. Dette opnås ved at opdele problemet i uafhængige dele, så hvert behandlingselement kan udføre sin del af algoritmen samtidigt med de andre. Behandlingselementerne kan være forskellige og omfatte ressourcer, såsom en enkelt computer med flere processorer, flere netværkscomputere, specialiseret hardware eller en hvilken som helst kombination af ovenstående. Historisk set blev parallel computing brugt til videnskabelig computing og simulering af videnskabelige problemer, især inden for natur- og ingeniørvidenskab, såsom meteorologi . Dette førte til design af parallel hardware og software samt højtydende computing .

Frekvensskalering var den dominerende årsag til forbedringer i computerens ydeevne fra midten af ​​1980'erne og frem til 2004. Kørselstiden for et program er lig med antallet af instruktioner ganget med den gennemsnitlige tid pr. Instruktion. Vedligeholdelse af alt andet konstant, stigning af urfrekvensen reducerer den gennemsnitlige tid, det tager at udføre en instruktion. En stigning i frekvens reducerer dermed runtime for alle computerbundne programmer. Strømforbruget P af en chip er imidlertid givet ved ligningen P = C × V ² × F , hvor C er kapacitansen, der skiftes pr. Urcyklus (proportional med antallet af transistorer, hvis input ændres), V er spænding og F er processorfrekvensen (cyklusser pr. sekund). Stigninger i frekvens øger mængden af ​​strøm, der bruges i en processor. Stigende processorforbrug førte i sidste ende til Intels 8. maj 2004 aflysning af sine Tejas- og Jayhawk -processorer, hvilket generelt omtales som afslutningen på frekvensskalering som det dominerende computerarkitekturparadigme.

For at håndtere problemet med strømforbrug og overophedning begyndte de store centrale processorenhedsproducenter (CPU eller processor) at producere energieffektive processorer med flere kerner. Kernen er processorens computerenhed og i multi-core processorer er hver kerne uafhængig og kan få adgang til den samme hukommelse samtidigt. Multi-core processorer har bragt parallel computing til stationære computere . Således er parallelisering af serielle programmer blevet en almindelig programmeringsopgave. I 2012 blev quad-core processorer standard for stationære computere , mens servere har 10 og 12 core processorer. Fra Moores lov kan det forudsiges, at antallet af kerner pr. Processor vil fordobles hver 18. -24. Måned. Dette kan betyde, at en typisk processor efter 2020 vil have snesevis eller hundredvis af kerner.

Et operativsystem kan sikre, at forskellige opgaver og brugerprogrammer køres parallelt på de tilgængelige kerner. For at et serielt softwareprogram kan drage fuld fordel af multi-core-arkitekturen, skal programmereren imidlertid omstrukturere og parallelisere koden. En fremskyndelse af applikationssoftware-runtime vil ikke længere opnås gennem frekvensskala, i stedet skal programmerere parallelisere deres softwarekode for at drage fordel af den stigende computerkraft i multicore-arkitekturer.

Amdahls lov og Gustafsons lov

En grafisk fremstilling af Amdahls lov . Hastigheden af ​​et program fra parallelisering er begrænset af, hvor meget af programmet, der kan paralleliseres. For eksempel, hvis 90% af programmet kan paralleliseres, ville den teoretiske maksimale hastighed ved hjælp af parallel computing være 10 gange, uanset hvor mange processorer der bruges.

Antag, at en opgave har to uafhængige dele, A og B . Del B tager cirka 25% af tiden for hele beregningen. Ved at arbejde meget hårdt kan man muligvis gøre denne del 5 gange hurtigere, men dette reducerer kun tiden for hele beregningen med lidt. I modsætning hertil kan det være nødvendigt at udføre mindre arbejde for at få del A til at være dobbelt så hurtig. Dette vil gøre beregningen meget hurtigere end ved at optimere del B , selvom hastigheden på del B er større i forhold til (5 gange versus 2 gange).

Optimalt ville hastigheden fra parallelisering være lineær - fordobling af antallet af behandlingselementer skulle halvere løbetiden, og fordoble den en anden gang skulle igen halvere løbetiden. Imidlertid opnår meget få parallelle algoritmer optimal hastighed. De fleste af dem har en næsten lineær hastighed for et lille antal behandlingselementer, som flader ud til en konstant værdi for et stort antal behandlingselementer.

Den potentielle hastighed af en algoritme på en parallel computerplatform er givet af Amdahls lov

${\ displaystyle S _ {\ text {latens}} (r) = {\ frac {1} {1-p+{\ frac {p} {s}}}},}$

hvor

• S _latenstid er den potentielle hastighedshastighed i latens i udførelsen af ​​hele opgaven;
• s er hastigheden i latens i udførelsen af ​​den paralleliserbare del af opgaven;
• p er procentdelen af ​​udførelsestiden for hele opgaven vedrørende den paralleliserbare del af opgaven før parallelisering .

Siden S _latens <1/(1 - p ) viser det, at en lille del af programmet, der ikke kan paralleliseres, vil begrænse den samlede hastighed, der er tilgængelig fra parallelisering. Et program, der løser et stort matematisk eller teknisk problem, vil typisk bestå af flere parallelliserbare dele og flere ikke-paralleliserbare (serielle) dele. Hvis den ikke-paralleliserbare del af et program tegner sig for 10% af driftstiden ( p = 0,9), kan vi ikke få mere end 10 gange hurtigere, uanset hvor mange processorer der tilføjes. Dette sætter en øvre grænse for nytten af ​​at tilføje flere parallelle udførelsesenheder. "Når en opgave ikke kan opdeles på grund af sekventielle begrænsninger, har anvendelsen af ​​mere indsats ingen effekt på skemaet. Et barns fødsel tager ni måneder, uanset hvor mange kvinder der er tildelt."

En grafisk fremstilling af Gustafsons lov

Amdahls lov gælder kun i tilfælde, hvor problemstørrelsen er rettet. I praksis, efterhånden som flere computerressourcer bliver tilgængelige, har de en tendens til at blive brugt til større problemer (større datasæt), og tiden brugt i den paralleliserbare del vokser ofte meget hurtigere end det iboende serielle arbejde. I dette tilfælde giver Gustafsons lov en mindre pessimistisk og mere realistisk vurdering af parallelle præstationer:

${\ displaystyle S _ {\ text {latens}} (r) = 1-p+sp.}$

Både Amdahls lov og Gustafsons lov antager, at spilletiden for den serielle del af programmet er uafhængig af antallet af processorer. Amdahls lov antager, at hele problemet er af fast størrelse, så den samlede mængde arbejde, der skal udføres parallelt, også er uafhængig af antallet af processorer , hvorimod Gustafsons lov forudsætter, at den samlede mængde arbejde, der skal udføres parallelt, varierer lineært med antallet af processorer .

Afhængigheder

Forståelse af dataafhængigheder er grundlæggende ved implementering af parallelle algoritmer . Intet program kan køre hurtigere end den længste kæde af afhængige beregninger (kendt som den kritiske vej ), da beregninger, der er afhængige af tidligere beregninger i kæden, skal udføres i rækkefølge. De fleste algoritmer består imidlertid ikke kun af en lang kæde af afhængige beregninger; der er normalt muligheder for at udføre uafhængige beregninger parallelt.

Lad P _i og P _j være to programsegmenter. Bernsteins forhold beskriver, hvornår de to er uafhængige og kan udføres parallelt. For P _i , lad I _i være alle inputvariablerne og O _i outputvariablerne, og ligeledes for P _j . P _i og P _j er uafhængige, hvis de tilfredsstiller

${\ displaystyle I_ {j} \ cap O_ {i} = \ varnothing,}$

${\ displaystyle I_ {i} \ cap O_ {j} = \ varnothing,}$

${\ displaystyle O_ {i} \ cap O_ {j} = \ varnothing.}$

Overtrædelse af den første betingelse indfører en flowafhængighed, der svarer til, at det første segment producerer et resultat, der bruges af det andet segment. Den anden betingelse repræsenterer en anti-afhængighed, når det andet segment producerer en variabel, der er nødvendig for det første segment. Den tredje og sidste betingelse repræsenterer en outputafhængighed: Når to segmenter skriver til det samme sted, kommer resultatet fra det logisk sidst udførte segment.

Overvej følgende funktioner, der demonstrerer flere slags afhængigheder:

1: function Dep(a, b)
2: c := a * b
3: d := 3 * c
4: end function

I dette eksempel kan instruktion 3 ikke udføres før (eller endda parallelt med) instruktion 2, fordi instruktion 3 anvender et resultat fra instruktion 2. Den overtræder betingelse 1 og indfører således en flowafhængighed.

1: function NoDep(a, b)
2: c := a * b
3: d := 3 * b
4: e := a + b
5: end function

I dette eksempel er der ingen afhængigheder mellem instruktionerne, så de kan alle køres parallelt.

Bernsteins forhold tillader ikke, at hukommelse deles mellem forskellige processer. Til det er nogle midler til at håndhæve en bestilling mellem adganger nødvendige, såsom semaforer , barrierer eller en anden synkroniseringsmetode .

Raceforhold, gensidig eksklusion, synkronisering og parallel opbremsning

Delopgaver i et parallelt program kaldes ofte tråde . Nogle parallelle computerarkitekturer bruger mindre, lette versioner af tråde kendt som fibre , mens andre bruger større versioner kendt som processer . Imidlertid accepteres "tråde" generelt som en generisk betegnelse for delopgaver. Tråde har ofte brug for synkroniseret adgang til et objekt eller en anden ressource , f.eks. Når de skal opdatere en variabel , der deles mellem dem. Uden synkronisering kan instruktionerne mellem de to tråde indflettes i enhver rækkefølge. Overvej f.eks. Følgende program:

Hvis instruktion 1B udføres mellem 1A og 3A, eller hvis instruktion 1A udføres mellem 1B og 3B, vil programmet producere forkerte data. Dette er kendt som en race betingelse . Programmereren skal bruge en lås til at give gensidig eksklusion . En lås er en programmeringssprogskonstruktion, der tillader en tråd at tage kontrol over en variabel og forhindre andre tråde i at læse eller skrive den, indtil variablen er låst op. Tråden, der holder låsen, kan frit udføre sit kritiske afsnit (afsnittet i et program, der kræver eksklusiv adgang til en variabel) og låse op for dataene, når de er færdige. For at garantere korrekt programudførelse kan ovenstående program derfor omskrives til at bruge låse:

Den ene tråd vil med succes låse variabel V, mens den anden tråd vil blive låst ude - kan ikke fortsætte, indtil V låses op igen. Dette garanterer korrekt udførelse af programmet. Låse kan være nødvendige for at sikre korrekt programkørsel, når tråde skal serialisere adgang til ressourcer, men deres anvendelse kan i høj grad bremse et program og kan påvirke dets pålidelighed .

Låsning af flere variabler ved hjælp af ikke-atomare låse introducerer muligheden for programmet dødvande . En atomlås låser flere variabler på én gang. Hvis den ikke kan låse dem alle, låser den ikke nogen af ​​dem. Hvis to tråde hver skal låse de samme to variabler ved hjælp af ikke-atomiske låse, er det muligt, at en tråd vil låse en af ​​dem, og den anden tråd vil låse den anden variabel. I et sådant tilfælde kan ingen af ​​trådene gennemføre, og resultaterne fastlåses.

Mange parallelle programmer kræver, at deres delopgaver fungerer synkront . Dette kræver brug af en barriere . Barrierer implementeres typisk ved hjælp af en lås eller en semafor . Én klasse algoritmer, kendt som låsfrie og ventefrie algoritmer , undgår helt brug af låse og barrierer. Denne fremgangsmåde er imidlertid generelt vanskelig at implementere og kræver korrekt konstruerede datastrukturer.

Ikke al parallelisering resulterer i hurtigere hastighed. Generelt, da en opgave er delt op i flere og flere tråde, bruger disse tråde en stadig større del af deres tid på at kommunikere med hinanden eller vente på hinanden for adgang til ressourcer. Når overhead fra ressourcekonflikt eller kommunikation dominerer den tid, der bruges på anden beregning, øges yderligere parallelisering (det vil sige opdeling af arbejdsbyrden over endnu flere tråde) i stedet for at reducere den tid, det tager at afslutte. Dette problem, kendt som parallel afmatning , kan i nogle tilfælde forbedres ved softwareanalyse og redesign.

Finkornet, grovkornet og pinlig parallelisme

Applikationer klassificeres ofte efter, hvor ofte deres delopgaver skal synkronisere eller kommunikere med hinanden. En applikation udviser finkornet parallelisme, hvis dens delopgaver skal kommunikere mange gange i sekundet; den udviser grovkornet parallelisme, hvis de ikke kommunikerer mange gange i sekundet, og den udviser pinlig parallelisme, hvis de sjældent eller aldrig skal kommunikere. Pinligt parallelle applikationer betragtes som de letteste at parallelisere.

Flynns taksonomi

Michael J. Flynn skabte et af de tidligste klassifikationssystemer til parallelle (og sekventielle) computere og programmer, nu kendt som Flynn's taksonomi . Flynn klassificerede programmer og computere efter, om de kørte ved hjælp af et enkelt sæt eller flere sæt instruktioner, og om disse instruktioner brugte et enkelt sæt eller flere datasæt.

SISD-klassificeringen (single-instruction-single-data) svarer til et helt sekventielt program. Single-instruction-multiple-data (SIMD) -klassificeringen er analog med at udføre den samme operation gentagne gange over et stort datasæt. Dette gøres almindeligvis i signalbehandlingsapplikationer . Multiple-instruction-single-data (MISD) er en sjældent anvendt klassifikation. Mens computerarkitekturer til at håndtere dette blev udtænkt (såsom systoliske arrays ), blev der kun få applikationer, der passede til denne klasse. Multiple-instruction-multiple-data (MIMD) programmer er langt den mest almindelige type parallelle programmer.

Ifølge David A. Patterson og John L. Hennessy , "Nogle maskiner er naturligvis hybrider af disse kategorier, men denne klassiske model har overlevet, fordi den er enkel, let at forstå og giver en god første tilnærmelse. Det er også - måske på grund af dets forståelighed - den mest anvendte ordning. "

Typer af parallelisme

Bit-niveau parallelisme

Taiwania 3 i Taiwan , en parallel supercomputerenhed, der sluttede sig til COVID-19- forskning.

Fra fremkomsten af meget storstilet integration (VLSI) computer-chip-fremstillingsteknologi i 1970'erne til omkring 1986 blev hastigheden i computerarkitekturen drevet af en fordobling af computerordstørrelse- mængden af ​​information, processoren kan manipulere pr. Cyklus. Forøgelse af ordstørrelsen reducerer antallet af instruktioner, processoren skal udføre for at udføre en operation på variabler, hvis størrelser er større end ordets længde. For eksempel, hvor en 8-bit processor skal tilføje to 16-bit heltal , skal processoren først tilføje de 8 lavere ordens bits fra hvert heltal ved hjælp af standardadditionsinstruktionen, derefter tilføje de 8 højere ordens bits ved hjælp af et add-with -carry instruktion og carry bit fra den lavere orden tilføjelse; således kræver en 8-bit processor to instruktioner for at fuldføre en enkelt operation, hvor en 16-bit processor ville være i stand til at fuldføre operationen med en enkelt instruktion.

Historisk set blev 4-bit mikroprocessorer erstattet med 8-bit, derefter 16-bit og derefter 32-bit mikroprocessorer. Denne tendens sluttede generelt med introduktionen af ​​32-bit processorer, som har været en standard inden for generel computing i to årtier. Først i begyndelsen af ​​2000'erne, med fremkomsten af x86-64- arkitekturer, blev 64-bit processorer almindelige.

Instruktion-niveau parallelisme

En kanonisk processor uden pipeline . Det tager fem urcyklusser at fuldføre en instruktion, og dermed kan processoren udstede subskalaær ydelse ( IPC = 0,2 <1 ).

Et computerprogram er i det væsentlige en strøm af instruktioner udført af en processor. Uden parallelisme på instruktionsniveau kan en processor kun udstede mindre end én instruktion pr. Urcyklus ( IPC <1 ). Disse processorer er kendt som subskalære processorer. Disse instruktioner kan ombestilles og kombineres i grupper, der derefter udføres parallelt uden at ændre programmets resultat. Dette er kendt som instruktion-niveau parallelisme. Fremskridt inden for parallelisme på instruktionsniveau dominerede computerarkitektur fra midten af ​​1980'erne til midten af ​​1990'erne.

En kanonisk fem-trins pipelineret processor. I bedste tilfælde tager det en urcyklus at fuldføre en instruktion, og dermed kan processoren udstede skalær ydelse ( IPC = 1 ).

Alle moderne processorer har instruktioner i flere trin . Hvert trin i pipelinen svarer til en anden handling, processoren udfører på denne instruktion i dette trin; en processor med en N -trin pipeline kan have op til N forskellige instruktioner på forskellige trin af færdiggørelsen og kan dermed udsende en instruktion pr. urcyklus ( IPC = 1 ). Disse processorer er kendt som skalarprocessorer . Det kanoniske eksempel på en pipelineret processor er en RISC -processor med fem faser: instruktionshentning (IF), instruktionsafkodning (ID), eksekvering (EX), hukommelsesadgang (MEM) og registerskrivning (WB). Den Pentium 4 -processor havde en 35-trins pipeline.

En kanonisk fem-trins pipelineret processor med to eksekveringsenheder. I bedste tilfælde tager det en urcyklus at fuldføre to instruktioner, og dermed kan processoren udstede superkalar ydeevne ( IPC = 2> 1 ).

De fleste moderne processorer har også flere eksekveringsenheder . De kombinerer normalt denne funktion med pipelining og kan dermed udstede mere end én instruktion pr. Urcyklus ( IPC> 1 ). Disse processorer er kendt som superscalar processorer. Superscalar processorer adskiller sig fra multi-core processorer ved at de flere eksekveringsenheder ikke er hele processorer (dvs. processorenheder). Instruktioner kan kun grupperes, hvis der ikke er nogen dataafhængighed mellem dem. Scoreboarding og Tomasulo-algoritmen (som ligner scoreboarding, men gør brug af omdøbning af registre ) er to af de mest almindelige teknikker til implementering af ordreudførelse og parallelisme på instruktionsniveau.

Opgave parallelisme

Opgaveparallellisme er karakteristisk for et parallelprogram, at "helt forskellige beregninger kan udføres på enten de samme eller forskellige datasæt". Dette står i kontrast til dataparallellisme, hvor den samme beregning udføres på de samme eller forskellige datasæt. Opgaveparallellisme involverer nedbrydning af en opgave i underopgaver og derefter allokere hver delopgave til en processor til udførelse. Processorerne ville derefter udføre disse underopgaver samtidigt og ofte i samarbejde. Opgaveparallellisme skalerer normalt ikke med størrelsen på et problem.

Superordniveau parallelisme

Superordniveau parallelisme er en vektoriseringsteknik baseret på sløjfeudrulning og grundlæggende blokvektorisering. Det adskiller sig fra loop -vektoriseringsalgoritmer ved, at det kan udnytte parallelisme af inline -kode , såsom manipulering af koordinater, farvekanaler eller i sløjfer, der rulles ud i hånden.

Hardware

Hukommelse og kommunikation

Hovedhukommelsen i en parallelcomputer er enten delt hukommelse (delt mellem alle behandlingselementer i et enkelt adresserum ) eller distribueret hukommelse (hvor hvert behandlingselement har sit eget lokale adresserum). Distribueret hukommelse refererer til det faktum, at hukommelsen er logisk distribueret, men ofte indebærer, at den også er fysisk distribueret. Distribueret delt hukommelse og hukommelsesvirtualisering kombinerer de to tilgange, hvor behandlingselementet har sin egen lokale hukommelse og adgang til hukommelsen på ikke-lokale processorer. Adgang til lokal hukommelse er typisk hurtigere end adgang til ikke-lokal hukommelse. På supercomputerne kan distribueret delt hukommelsesplads implementeres ved hjælp af programmeringsmodellen, f.eks. PGAS . Denne model giver processer på en beregningsknude adgang til transparent adgang til fjernhukommelsen i en anden beregningsknude. Alle beregningsknudepunkter er også forbundet til et eksternt delt hukommelsessystem via højhastighedsforbindelse, f.eks. Infiniband , dette eksterne delte hukommelsessystem er kendt som burst-buffer , som typisk er bygget af arrays af ikke-flygtig hukommelse, fysisk fordelt på flere I/ O noder.

En logisk visning af en ikke-ensartet hukommelsesadgang (NUMA) arkitektur. Processorer i det ene bibliotek kan få adgang til bibliotekets hukommelse med mindre forsinkelse, end de kan få adgang til hukommelse i det andet biblioteks hukommelse.

Computerarkitekturer, hvor hvert element i hovedhukommelsen kan tilgås med lige latens og båndbredde , kaldes UMA -systemer ( uniform memory access ). Det kan typisk kun opnås ved et delt hukommelsessystem , hvor hukommelsen ikke er fysisk fordelt. Et system, der ikke har denne egenskab, er kendt som en ikke-ensartet hukommelsesadgang (NUMA) arkitektur. Distribuerede hukommelsessystemer har ikke-ensartet hukommelsesadgang.

Computersystemer gør brug af cacher - små og hurtige hukommelser placeret tæt på processoren, som gemmer midlertidige kopier af hukommelsesværdier (i nærheden i både fysisk og logisk forstand). Parallelle computersystemer har problemer med caches, der kan gemme den samme værdi på mere end ét sted, med mulighed for forkert programkørsel. Disse computere kræver et cache -kohærenssystem , som holder styr på cachelagrede værdier og strategisk renser dem og dermed sikrer korrekt programkørsel. Bus -snooping er en af ​​de mest almindelige metoder til at holde styr på, hvilke værdier der tilgås (og dermed bør renses). Design af store, højtydende cache-kohærenssystemer er et meget vanskeligt problem inden for computerarkitektur. Som et resultat skaleres computerhukommelser for delt hukommelse ikke så godt som distribuerede hukommelsessystemer.

Processor -processor og processor -hukommelseskommunikation kan implementeres i hardware på flere måder, herunder via delt (enten multiportet eller multiplexeret ) hukommelse, en tværstangskontakt , en delt bus eller et sammenkoblingsnetværk af et utal af topologier, herunder stjerne , ring , træ , hypercube , fat hypercube (en hypercube med mere end en processor ved en knude) eller n-dimensionel mesh .

Parallelle computere baseret på sammenkoblede netværk skal have en eller anden form for routing for at muliggøre overførsel af meddelelser mellem noder, der ikke er direkte forbundet. Det medium, der bruges til kommunikation mellem processorerne, er sandsynligvis hierarkisk i store multiprocessormaskiner.

Klasser af parallelle computere

Parallelle computere kan groft klassificeres efter det niveau, hvor hardwaren understøtter parallelisme. Denne klassificering er stort set analog med afstanden mellem grundlæggende computerknudepunkter. Disse udelukker ikke hinanden; for eksempel er klynger af symmetriske multiprocessorer relativt almindelige.

Multi-core computing

En multi-core processor er en processor, der indeholder flere processorenheder (kaldet "kerner") på den samme chip. Denne processor adskiller sig fra en superskalar processor, som indeholder flere eksekveringsenheder og kan udstede flere instruktioner pr. Urcyklus fra en instruktionsstrøm (tråd); derimod kan en multi-core processor udstede flere instruktioner pr. urcyklus fra flere instruktionsstrømme. IBM 's Cell-mikroprocessor , designet til brug i Sony PlayStation 3 , er en fremtrædende multi-core processor. Hver kerne i en multi-core processor kan muligvis også være superskalar-det vil sige i hver urcyklus kan hver kerne udstede flere instruktioner fra en tråd.

Samtidig multithreading (hvoraf Intels Hyper-Threading er den bedst kendte) var en tidlig form for pseudo-multi-coreisme. En processor, der er i stand til samtidig multitrådning, omfatter flere eksekveringsenheder i den samme behandlingsenhed - det vil sige, at den har en superskalar arkitektur - og kan udstede flere instruktioner pr. Urcyklus fra flere tråde. Temporal multithreading på den anden side inkluderer en enkelt eksekveringsenhed i den samme behandlingsenhed og kan udstede en instruktion ad gangen fra flere tråde.

Symmetrisk multiprocessering

En symmetrisk multiprocessor (SMP) er et computersystem med flere identiske processorer, der deler hukommelse og forbinder via en bus . Busstrid forhindrer busarkitekturer i at skalere. Som et resultat omfatter SMP'er generelt ikke mere end 32 processorer. På grund af processorernes lille størrelse og den betydelige reduktion i kravene til busbåndbredde opnået ved store caches er sådanne symmetriske multiprocessorer ekstremt omkostningseffektive, forudsat at der findes en tilstrækkelig mængde hukommelsesbåndbredde.

Distribueret computing

En distribueret computer (også kendt som en distribueret hukommelsesmultiprocessor) er et distribueret hukommelsescomputersystem, hvor behandlingselementerne er forbundet med et netværk. Distribuerede computere er meget skalerbare. Udtrykkene " samtidige computere ", "parallelle computere" og "distribueret computing" har meget overlapning, og der findes ingen klar sondring mellem dem. Det samme system kan karakteriseres både som "parallelt" og "distribueret"; processorer i et typisk distribueret system kører parallelt parallelt.

Cluster computing

En Beowulf -klynge

En klynge er en gruppe løst koblede computere, der arbejder tæt sammen, så de i nogle henseender kan betragtes som en enkelt computer. Klynger består af flere enkeltstående maskiner, der er forbundet med et netværk. Mens maskiner i en klynge ikke behøver at være symmetriske, er belastningsbalancering vanskeligere, hvis de ikke er det. Den mest almindelige type klynge er Beowulf-klyngen , som er en klynge , der er implementeret på flere identiske kommercielle off-the-shelf- computere, der er forbundet med et TCP/IP Ethernet- lokalnetværk . Beowulf -teknologien blev oprindeligt udviklet af Thomas Sterling og Donald Becker . 87% af alle Top500 supercomputere er klynger. De resterende er Massively Parallel Processors, forklaret nedenfor.

Fordi grid computing -systemer (beskrevet nedenfor) let kan håndtere pinligt parallelle problemer, er moderne klynger typisk designet til at håndtere mere vanskelige problemer - problemer, der kræver, at noder oftere deler resultater med hinanden oftere. Dette kræver en høj båndbredde og, endnu vigtigere, et lav- latency- forbindelsesnetværk. Mange historiske og nuværende supercomputere bruger tilpasset højtydende netværkshardware, der er specielt designet til klynge-computing, f.eks. Cray Gemini-netværket. Fra 2014 bruger de fleste nuværende supercomputere noget standard netværkshardware fra hylden, ofte Myrinet , InfiniBand eller Gigabit Ethernet .

Massivt parallel computing

Et skab fra IBM 's Blue Gene/L massivt parallel supercomputer

En massivt parallel processor (MPP) er en enkelt computer med mange netværksprocessorer. MPP'er har mange af de samme egenskaber som klynger, men MPP'er har specialiserede sammenkoblingsnetværk (hvorimod klynger bruger råvarehardware til netværk). MPP'er har også en tendens til at være større end klynger, der typisk har "langt flere" end 100 processorer. I en MPP indeholder "hver CPU sin egen hukommelse og kopi af operativsystemet og applikationen. Hvert undersystem kommunikerer med de andre via en højhastighedsforbindelse."

IBM 's Blue Gene/L , den femte hurtigste supercomputer i verden ifølge TOP500 -ranglisten i juni 2009 , er en MPP.

Grid computing

Grid computing er den mest distribuerede form for parallel computing. Det gør brug af computere, der kommunikerer over internettet til at arbejde på et givet problem. På grund af den lave båndbredde og ekstremt høje latenstid på Internettet beskæftiger distribueret computing sig typisk kun med pinligt parallelle problemer. Mange distribuerede computerapplikationer er blevet oprettet, hvoraf SETI@home og Folding@home er de mest kendte eksempler.

De fleste grid computing -applikationer bruger middleware (software, der sidder mellem operativsystemet og applikationen til at styre netværksressourcer og standardisere software -interface). Den mest almindelige distribuerede computermidtware er Berkeley Open Infrastructure for Network Computing (BOINC). Ofte gør distribueret computersoftware brug af "reservedele", der udfører beregninger på tidspunkter, hvor en computer er i tomgang.

Specialiserede parallelle computere

Inden for parallel computing er der specialiserede parallelle enheder, der forbliver nicheområder af interesse. Selvom de ikke er domænespecifikke , har de en tendens til kun at være gældende for nogle få klasser af parallelle problemer.

Omkonfigurerbar computing med feltprogrammerbare gate-arrays

Rekonfigurerbar computing er brugen af ​​et feltprogrammerbart gate-array (FPGA) som en co-processor til en computer til generelle formål. En FPGA er i det væsentlige en computerchip, der kan rewire sig selv til en given opgave.

FPGA'er kan programmeres med hardware -beskrivelsessprog såsom VHDL eller Verilog . Programmering på disse sprog kan dog være kedelig. Flere leverandører har oprettet C til HDL -sprog, der forsøger at efterligne syntaksen og semantikken i C -programmeringssproget , som de fleste programmører kender. De mest kendte C til HDL-sprog er Mitrion-C , Impulse C , DIME-C og Handel-C . Specifikke undersæt af SystemC baseret på C ++ kan også bruges til dette formål.

AMDs beslutning om at åbne HyperTransport- teknologien for tredjepartsleverandører er blevet teknologien til rekonfigurerbar computing med høj ydeevne. Ifølge Michael R. D'Amour, Chief Operating Officer for DRC Computer Corporation , "da vi først gik ind i AMD, kaldte de os ' stikkontakterne for stikkontakter '. Nu kalder de os deres partnere. "

Almindelig beregning på grafikprocessorenheder (GPGPU)

Nvidias Tesla GPGPU -kort

Almindelig beregning på grafikbehandlingsenheder (GPGPU) er en temmelig nylig tendens inden for computerteknisk forskning. GPU'er er medprocessorer, der er stærkt optimeret til computergrafikbehandling . Computergrafikbehandling er et felt domineret af dataparallelle operationer - især lineære algebra -matrixoperationer .

I de tidlige dage brugte GPGPU -programmer de normale grafiske API'er til udførelse af programmer. Imidlertid er flere nye programmeringssprog og platforme blevet bygget til generel beregning på GPU'er med både Nvidia og AMD, der frigiver programmeringsmiljøer med henholdsvis CUDA og Stream SDK . Andre GPU -programmeringssprog inkluderer BrookGPU , PeakStream og RapidMind . Nvidia har også frigivet specifikke produkter til beregning i deres Tesla -serie . Teknologikonsortiet Khronos Group har frigivet OpenCL -specifikationen, som er en ramme for at skrive programmer, der udføres på tværs af platforme bestående af CPU'er og GPU'er. AMD , Apple , Intel , Nvidia og andre understøtter OpenCL .

Applikationsspecifikke integrerede kredsløb

Adskillige applikationsspecifikke integrerede kredsløb (ASIC) metoder er blevet udtænkt til håndtering af parallelle applikationer.

Fordi en ASIC (per definition) er specifik for en given applikation, kan den optimeres fuldt ud til den pågældende applikation. Som et resultat, for en given applikation, har en ASIC en tendens til at udkonkurrere en computer til generelle formål. ASIC'er skabes imidlertid ved UV -fotolitografi . Denne proces kræver et maskesæt, som kan være ekstremt dyrt. Et maske sæt kan koste over en million amerikanske dollars. (Jo mindre transistorer, der kræves til chippen, desto dyrere bliver masken.) I mellemtiden øger ydeevnen i generel computing over tid (som beskrevet i Moores lov ) kun disse udvisninger på en eller to chipgenerationer. . Høje startomkostninger og tendensen til at blive overhalet af Moores lovbaserede computere til almindelige formål har gjort ASIC uopnåelige for de fleste parallelle computerapplikationer. Nogle er dog blevet bygget. Et eksempel er PFLOPS RIKEN MDGRAPE-3- maskinen, der bruger brugerdefinerede ASIC'er til molekylær dynamiksimulering .

Vektor processorer

The Cray-1 er en vektor processor

En vektorprocessor er en CPU eller et computersystem, der kan udføre den samme instruktion om store datasæt. Vektorprocessorer har operationer på højt niveau, der arbejder på lineære arrays med tal eller vektorer. Et eksempel på en vektoroperation er A = B × C , hvor A , B og C hver er 64-elementers vektorer med 64-bit floating-point tal. De er tæt forbundet med Flynns SIMD -klassificering.

Cray- computere blev berømt for deres vektorbehandlingscomputere i 1970'erne og 1980'erne. Men vektorprocessorer - både som CPU'er og som fulde computersystemer - er generelt forsvundet. Moderne processor instruktionssæt inkluderer nogle vektor behandlingsinstruktioner, såsom med Freescale Semiconductor 's AltiVec og Intel ' s Streaming SIMD Extensions (SSE).

Software

Parallelle programmeringssprog

Samtidig programmeringssprog , biblioteker , API'er og parallelle programmeringsmodeller (såsom algoritmiske skeletter ) er blevet oprettet til programmering af parallelle computere. Disse kan generelt opdeles i klasser baseret på de antagelser, de gør om den underliggende hukommelsesarkitektur - delt hukommelse, distribueret hukommelse eller delt distribueret hukommelse. Programmeringssprog til delt hukommelse kommunikerer ved at manipulere delte hukommelsesvariabler. Distribueret hukommelse bruger beskedoverførsel . POSIX Threads og OpenMP er to af de mest udbredte API'er til delt hukommelse, hvorimod Message Passing Interface (MPI) er den mest udbredte meddelelsesformidlende system-API. Et begreb, der bruges til programmering af parallelle programmer, er det fremtidige koncept , hvor en del af et program lover at levere et påkrævet datum til en anden del af et program på et senere tidspunkt.

CAPS- repræsentant og Pathscale koordinerer også deres bestræbelser på at gøre hybrid multi-core parallel programmering (HMPP) direktiver til en åben standard kaldet OpenHMPP . Den OpenHMPP-direktivbaserede programmeringsmodel tilbyder en syntaks til effektivt at aflaste beregninger på hardwareacceleratorer og optimere databevægelse til/fra hardwarehukommelsen. OpenHMPP -direktiver beskriver fjernprocedurekald (RPC) på en accelerator (f.eks. GPU) eller mere generelt et sæt kerner. Direktiverne kommenterer C- eller Fortran -koder for at beskrive to sæt funktionaliteter: aflæsning af procedurer (betegnet kodeletter) på en ekstern enhed og optimering af dataoverførsler mellem CPU'ens hovedhukommelse og acceleratorhukommelsen.

Stigningen af ​​forbruger -GPU'er har ført til understøttelse af computerkerner , enten i grafiske API'er (kaldet compute shaders ), i dedikerede API'er (f.eks. OpenCL ) eller i andre sprogudvidelser.

Automatisk parallelisering

Automatisk parallelisering af et sekventielt program af en kompilator er den "hellige gral" for parallel computing, især med den førnævnte grænse for processorfrekvens. På trods af årtiers arbejde med kompilatorforskere har automatisk parallelisering kun haft begrænset succes.

Mainstream parallelle programmeringssprog forbliver enten eksplicit parallelle eller (i bedste fald) delvist implicitte , hvor en programmerer giver kompilatoren direktiver for parallelisering. Der findes et par fuldstændigt implicitte parallelle programmeringssprog- SISAL , Parallel Haskell , SequenceL , System C (til FPGA'er ), Mitrion-C , VHDL og Verilog .

Kontrol af applikationer

Når et computersystem vokser i kompleksitet, falder den gennemsnitlige tid mellem fejl normalt. Applikationskontrolpunkt er en teknik, hvorved computersystemet tager et "øjebliksbillede" af applikationen - en oversigt over alle aktuelle ressourceallokeringer og variable tilstande, der ligner en kernedump - -; disse oplysninger kan bruges til at gendanne programmet, hvis computeren skulle mislykkes. Applikationskontrol betyder, at programmet kun skal genstarte fra sit sidste kontrolpunkt frem for begyndelsen. Selvom checkpointing giver fordele i en række forskellige situationer, er det især nyttigt i meget parallelle systemer med et stort antal processorer, der bruges til højtydende computing .

Algoritmiske metoder

Efterhånden som parallelle computere bliver større og hurtigere, er vi nu i stand til at løse problemer, der tidligere havde taget for lang tid at køre. Så forskellige områder som bioinformatik (til proteinfoldning og sekvensanalyse ) og økonomi (til matematisk finansiering ) har udnyttet parallel computing. Almindelige typer problemer i parallelle computerapplikationer omfatter:

• Tæt lineær algebra
• Sparsom lineær algebra
• Spektrale metoder (såsom Cooley - Tukey hurtig Fourier -transformation )
• N -kropsproblemer (f.eks. Barnes – Hut -simulering )
• strukturerede netproblemer (f.eks. Gitter Boltzmann -metoder )
• Ustrukturerede netproblemer (f.eks. Fundet i endelige elementanalyser )
• Monte Carlo metode
• Kombinationel logik (f.eks. Brute-force kryptografiske teknikker )
• Grafoverskridelse (f.eks. Sorteringsalgoritmer )
• Dynamisk programmering
• Gren og bundne metoder
• Grafiske modeller (såsom detektering af skjulte Markov -modeller og konstruktion af bayesiske netværk )
• Endelig tilstandsmaskine simulering

Fejltolerance

Parallel computing kan også anvendes til design af fejltolerante computersystemer , især via lockstep- systemer, der udfører den samme operation parallelt. Dette giver redundans , hvis en komponent fejler, og tillader også automatisk fejlopdagelse og fejlkorrektion, hvis resultaterne er forskellige. Disse metoder kan bruges til at forhindre forstyrrelser i enkeltstående hændelser forårsaget af forbigående fejl. Selvom der kan være behov for yderligere foranstaltninger i integrerede eller specialiserede systemer, kan denne metode give en omkostningseffektiv tilgang til at opnå n-modulær redundans i kommercielle off-the-shelf-systemer.

Historie

ILLIAC IV , "den mest berygtede af supercomputere"

Oprindelsen til sand (MIMD) parallelisme går tilbage til Luigi Federico Menabrea og hans Sketch of the Analytic Engine Opfundet af Charles Babbage .

I april 1958 diskuterede Stanley Gill (Ferranti) parallelprogrammering og behovet for forgrening og ventetid. Også i 1958 diskuterede IBM -forskerne John Cocke og Daniel Slotnick brugen af ​​parallelisme i numeriske beregninger for første gang. Burroughs Corporation introducerede D825 i 1962, en computer med fire processorer, der fik adgang til op til 16 hukommelsesmoduler via en tværstangskontakt . I 1967 offentliggjorde Amdahl og Slotnick en debat om muligheden for parallel behandling på American Federation of Information Processing Societies Conference. Det var under denne debat, at Amdahls lov blev udformet til at definere grænsen for hastighed på grund af parallelisme.

I 1969 introducerede Honeywell sit første Multics -system, et symmetrisk multiprocessorsystem, der kan køre op til otte processorer parallelt. C.mmp , et multi-processor-projekt ved Carnegie Mellon University i 1970'erne, var blandt de første multiprocessorer med mere end et par processorer. Den første busforbundne multiprocessor med snooping caches var Synapse N+1 i 1984.

SIMD -parallelle computere kan spores tilbage til 1970'erne. Motivationen bag tidlige SIMD -computere var at amortisere portforsinkelsen på processorens styreenhed over flere instruktioner. I 1964 havde Slotnick foreslået at bygge en massivt parallel computer til Lawrence Livermore National Laboratory . Hans design blev finansieret af US Air Force , som var den tidligste SIMD-parallel-computing-indsats, ILLIAC IV . Nøglen til dens design var en temmelig høj parallelisme med op til 256 processorer, som tillod maskinen at arbejde på store datasæt i det, der senere skulle blive kendt som vektorbehandling . Imidlertid blev ILLIAC IV kaldt "den mest berygtede af supercomputere", fordi projektet kun var en fjerdedel afsluttet, men tog 11 år og kostede næsten fire gange det oprindelige skøn. Da den endelig var klar til at køre sin første rigtige applikation i 1976, blev den bedre end eksisterende kommercielle supercomputere såsom Cray-1 .

Biologisk hjerne som massivt parallel computer

I begyndelsen af ​​1970'erne, på MIT Computer Science and Artificial Intelligence Laboratory, begyndte Marvin Minsky og Seymour Papert at udvikle Society of Mind -teorien, der betragter den biologiske hjerne som massivt parallel computer . I 1986 udgav Minsky The Society of Mind , der hævder, at "sind er dannet af mange små agenter, hver for sig tankeløse". Teorien forsøger at forklare, hvordan det, vi kalder intelligens, kan være et produkt af samspillet mellem ikke-intelligente dele. Minsky siger, at den største kilde til ideer om teorien kom fra hans arbejde med at forsøge at skabe en maskine, der bruger en robotarm, et videokamera og en computer til at bygge med børns blokke.

Lignende modeller (som også ser den biologiske hjerne som en massivt parallel computer, dvs. hjernen består af en konstellation af uafhængige eller semi-uafhængige agenter) blev også beskrevet af:

• Thomas R. Blakeslee,
• Michael S. Gazzaniga ,
• Robert E. Ornstein ,
• Ernest Hilgard ,
• Michio Kaku ,
• George Ivanovich Gurdjieff ,
• Neurokluster hjernemodel.

Se også

Referencer

Yderligere læsning

• Rodriguez, C .; Villagra, M .; Baran, B. (29. august 2008). "Asynkrone teamalgoritmer til boolsk tilfredshed". Bioinspirerede modeller af netværk, informations- og computersystemer, 2007. Bionetics 2007. 2nd : 66–69. doi : 10.1109/BIMNICS.2007.4610083 . S2CID  15185219 .
• Sechin, A .; Parallel computing i fotogrammetri. GIM International. #1, 2016, s. 21–23.

eksterne links

Lyt til denne artikel ( 54 minutter )

Denne lydfil blev oprettet ud fra en revision af denne artikel af 21. august 2013 og afspejler ikke efterfølgende ændringer. ( 2013-08-21 )

( Lydhjælp  · Flere talte artikler )

• Instruktionsvideoer om CAF i Fortran Standard af John Reid (se tillæg B)
• Parallel computing hos Curlie
• Lawrence Livermore National Laboratory: Introduktion til parallel computing
• Design og opbygning af parallelle programmer, af Ian Foster
• Internet Parallel Computing Archive
• Parallelt behandlingsemneområde ved IEEE Distributed Computing Online
• Parallel computing fungerer gratis online bog
• Grænser for supercomputerende gratis onlinebøger, der dækker emner som algoritmer og industrielle applikationer
• Universal Parallel Computing Research Center
• Kursus i parallel programmering ved Columbia University (i samarbejde med IBM TJ Watson X10 -projekt)
• Parallelt og distribueret Gröbner baserer beregning i JAS , se også Gröbner -grundlag
• Kursus i parallel computing ved University of Wisconsin-Madison
• Berkeley Par Lab: fremskridt i det parallelle computerlandskab , redaktører: David Patterson, Dennis Gannon og Michael Wrinn, 23. august 2013
• Problemet med multicore , af David Patterson, sendt 30. juni 2010
• Parallel computing: En udsigt fra Techsevi
• Introduktion til parallel computing
• Coursera: Parallel programmering
• Parallel computing: En udsigt fra Gyan Grih