Parallel algoritme - Parallel algorithm

I datalogi er en parallel algoritme , i modsætning til en traditionel seriel algoritme , en algoritme, der kan udføre flere operationer på et givet tidspunkt. Det har været en tradition inden for datalogi at beskrive serielle algoritmer i abstrakte maskinemodeller, ofte den, der er kendt som tilfældig adgangsmaskine . Tilsvarende har mange datalogiforskere brugt en såkaldt parallel random-access machine (PRAM) som en parallel abstrakt maskine (delt hukommelse).

Mange parallelle algoritmer udføres samtidigt - skønt generelt algoritmer samtidig er et særskilt koncept - og dermed er disse begreber ofte sammenflettet, med hvilket aspekt af en algoritme er parallel, og som er samtidig ikke skelnes klart. Yderligere kaldes ikke-parallelle, ikke-samtidige algoritmer ofte som " sekventielle algoritmer " i modsætning til samtidige algoritmer.

Parallelisering

Se også: Analyse af parallelle algoritmer

Algoritmer varierer betydeligt i hvor paralleliserbare de er, lige fra let paralleliserbare til helt uforlignelige. Yderligere kan et givet problem rumme forskellige algoritmer, som kan være mere eller mindre paralleliserbare.

Nogle problemer er lette at opdele i stykker på denne måde - disse kaldes pinligt parallelle problemer. Eksempler inkluderer mange algoritmer til at løse Rubiks terninger og finde værdier, der resulterer i en given hash .

Nogle problemer kan ikke opdeles i parallelle dele, da de kræver resultaterne fra et foregående trin for effektivt at fortsætte med det næste trin - disse kaldes iboende serielt problem s. Eksempler inkluderer iterativenumeriske metoder, såsomNewtons metode, iterative løsninger påtre-kropsproblemetog de fleste af de tilgængelige algoritmer til beregning afpi(π). Nogle sekventielle algoritmer kan konverteres til parallelle algoritmer ved hjælp afautomatisk parallelisering.

Motivering

Parallelle algoritmer på individuelle enheder er blevet mere almindelige siden begyndelsen af ​​2000'erne på grund af væsentlige forbedringer i multiprocessing- systemer og fremkomsten af multi-core processorer. Indtil udgangen af ​​2004 steg single-core processorens ydeevne hurtigt via frekvensskalering , og det var således lettere at konstruere en computer med en enkelt hurtig kerne end en med mange langsommere kerner med samme gennemløb , så multicore-systemer var mere begrænsede brug. Siden 2004 har frekvensskalering imidlertid ramt en mur, og dermed er multicore-systemer blevet mere udbredte, hvilket gør parallelle algoritmer til mere generel brug.

Problemer

Meddelelse

Omkostningerne eller kompleksiteten ved serielle algoritmer estimeres i form af det rum (hukommelse) og tid (processorcyklusser), de tager. Parallelle algoritmer har brug for at optimere endnu en ressource, kommunikationen mellem forskellige processorer. Der er to måder, som parallelle processorer kommunikerer, delt hukommelse eller videregivelse af meddelelser.

Delt hukommelsesbehandling har brug for yderligere låsning af dataene, pålægger omkostningerne ved yderligere processor- og buscyklusser og serierer også en del af algoritmen.

Beskedoverførselsbehandling bruger kanaler og meddelelsesbokse, men denne kommunikation tilføjer overførselsoverhead på bussen, yderligere hukommelsesbehov for køer og meddelelsesbokse og latens i meddelelserne. Design af parallelle processorer bruger specielle busser som tværbjælke, så kommunikationsomkostningerne bliver små, men det er den parallelle algoritme, der bestemmer trafikmængden.

Hvis kommunikationsomkostningerne for yderligere processorer opvejer fordelen ved at tilføje en anden processor, støder man på parallel afmatning .

Belastningsafbalancering

Hovedartikel: Load balancing (computing)

Et andet problem med parallelle algoritmer er at sikre, at de er passende belastningsafbalanceret , ved at sikre, at belastning (samlet arbejde) er afbalanceret, snarere end at inputstørrelsen er afbalanceret. For eksempel er det let at opdele alle numre fra et til hundrede tusinde for primalitet mellem processorer; men hvis tallene simpelthen fordeles jævnt (1–1.000, 1.001-2.000 osv.), vil mængden af ​​arbejde være ubalanceret, da mindre antal er lettere at behandle med denne algoritme (lettere at teste for primalitet), og således får nogle processorer mere arbejde at gøre end de andre, som vil være inaktiv, indtil de indlæste processorer er færdige.

Distribuerede algoritmer

Hovedartikel: Distribueret algoritme

En undertype af parallelle algoritmer, distribuerede algoritmer , er algoritmer designet til at arbejde i klyngecomputering og distribuerede computermiljøer , hvor yderligere bekymringer uden for rækkevidden af ​​"klassiske" parallelle algoritmer skal løses.

Se også

Referencer

eksterne links