Parallell algoritme - Parallel algorithm
I informatikk er en parallell algoritme , i motsetning til en tradisjonell seriell algoritme , en algoritme som kan utføre flere operasjoner på en gitt tid. Det har vært en tradisjon innen informatikk å beskrive seriealgoritmer i abstrakte maskinmodeller, ofte den som kalles random-access machine . Tilsvarende har mange informatikaforskere brukt en såkalt parallell tilgangsmaskin (PRAM) som en parallell abstrakt maskin (delt minne).
Mange parallelle algoritmer blir utført samtidig - selv om generelt algoritmer er et tydelig begrep - og dermed er disse begrepene ofte sammenslåtte, med hvilket aspekt av en algoritme som er parallell og hvilken som er samtidig ikke skilles tydelig ut. Videre blir ikke-parallelle, ikke-samtidige algoritmer ofte referert til som " sekvensielle algoritmer ", i motsetning til samtidige algoritmer.
Parallelliserbarhet
Algoritmer varierer betydelig i hvor parallelliserbare de er, alt fra lett parallelliserbare til helt uforlignelige. Videre kan et gitt problem imøtekomme forskjellige algoritmer, som kan være mer eller mindre parallelliserbare.
Noen problemer er enkle å dele opp i stykker på denne måten - disse kalles pinlig parallelle problemer. Eksempler inkluderer mange algoritmer for å løse Rubiks kuber og finne verdier som resulterer i en gitt hash .
Noen problemer kan ikke deles opp i parallelle deler, da de krever resultatene fra et foregående trinn for å effektivt fortsette med neste trinn - disse kalles iboende serieproblem s. Eksempler inkluderer iterativenumeriske metoder, somNewtons metode, iterative løsninger påtre-kroppsproblemetog de fleste tilgjengelige algoritmer for å beregnepi(π). Noen sekvensielle algoritmer kan konverteres til parallelle algoritmer ved hjelp avautomatisk parallellisering.
Motivasjon
Parallelle algoritmer på individuelle enheter har blitt vanligere siden begynnelsen av 2000-tallet på grunn av betydelige forbedringer i flerbehandlingssystemer og fremveksten av flerkjerneprosessorer . Fram til slutten av 2004 økte ytelsen til enkeltkjerners prosessor raskt via frekvensskalering , og dermed var det lettere å konstruere en datamaskin med en enkelt rask kjerne enn en med mange langsommere kjerner med samme gjennomstrømning , så flerkjernesystemer var av mer begrenset bruk. Siden 2004 har frekvensskalering imidlertid truffet en vegg, og dermed har flerkjernesystemer blitt mer utbredt, noe som gjør parallelle algoritmer til mer generell bruk.
Problemer
Kommunikasjon
Kostnaden eller kompleksiteten til serielle algoritmer er estimert i forhold til plass (minne) og tid (prosessersykluser) de tar. Parallelle algoritmer trenger å optimalisere en ressurs til, kommunikasjonen mellom forskjellige prosessorer. Det er to måter parallelle prosessorer kommuniserer, delt minne eller overføring av meldinger.
Delt minnebehandling trenger ekstra låsing for dataene, pålegger overhead for ekstra prosessor- og bussykluser, og serierer også en del av algoritmen.
Meldingsutveksling behandlingen bruker kanaler og meldingsbokser, men denne forbindelse legger overføring overhead på bussen, ekstra minne behov for køer og meldingsbokser og latens i meldingene. Design av parallelle prosessorer bruker spesielle busser som tverrligger, slik at kommunikasjonsoverhead blir liten, men det er parallellalgoritmen som bestemmer trafikkvolumet.
Hvis kommunikasjonsomkostningene til flere prosessorer oppveier fordelen ved å legge til en annen prosessor, møter man parallell nedgang .
Lastbalansering
Et annet problem med parallelle algoritmer er å sikre at de er passende belastningsbalansert , ved å sikre at belastning (samlet arbeid) er balansert, i stedet for at inngangsstørrelsen blir balansert. For eksempel er det enkelt å dele alle tallene fra ett til hundre tusen for primalitet mellom prosessorer; men hvis tallene rett og slett er delt jevnt ut (1–1 000, 1001–2 000 osv.), vil arbeidsmengden være ubalansert, ettersom mindre tall er lettere å behandle av denne algoritmen (lettere å teste for primalitet), og dermed vil noen prosessorer få mer arbeid å gjøre enn de andre, som vil sitte inaktiv til de lastede prosessorene er ferdige.
Distribuerte algoritmer
En undertype av parallelle algoritmer, distribuerte algoritmer , er algoritmer designet for å fungere i klyngedatamaskiner og distribuerte databehandlingsmiljøer , der ytterligere bekymringer utenfor omfanget av "klassiske" parallelle algoritmer må tas opp.
Se også
- Multiple-agent system (MAS)
- Parallelle algoritmer for matriksmultiplikasjon
- Parallelle algoritmer for minimum spennende trær
- Parallell databehandling
- Parareal
Referanser
Eksterne linker
- Designe og bygge parallelle programmer , US Argonne National Laboratory
