Parallel algoritme
Inden for datalogi er en parallel algoritme , i modsætning til traditionelle sekventielle algoritmer , en algoritme , der kan implementeres i dele på mange forskellige computerenheder, efterfulgt af at kombinere de opnåede resultater og opnå det korrekte resultat.
Nogle algoritmer er ret nemme at opdele i uafhængigt eksekverbare bidder. For eksempel kan man fordele arbejdet med at kontrollere alle tal fra 1 til 100.000 for at se, hvilke af dem der er primtal , ved at tildele hver tilgængelig processor en delmængde af tal og derefter kombinere de resulterende sæt af primtal (f.eks. GIMPS- projektet implementeres på lignende måde ).
På den anden side tillader de fleste af de kendte algoritmer til beregning af værdien af pi ikke opdeling i parallelle dele, da de kræver resultatet af den tidligere iteration af algoritmen. Iterative numeriske metoder , som for eksempel Newtons metode eller tre-kropsproblemet , er også rene sekventielle algoritmer. Nogle eksempler på rekursive algoritmer er ret svære at parallelisere. Et eksempel er dybde-først søgning på grafer .
Parallelle algoritmer er meget vigtige på grund af den konstante forbedring af multiprocessorsystemer og stigningen i antallet af kerner i moderne processorer. Det er normalt nemmere at designe en computer med en hurtig processor end en med mange langsomme processorer (forudsat at den samme ydeevne opnås ). Imidlertid øges ydeevnen af processorer hovedsageligt på grund af forbedringen af den tekniske proces (reduktion af produktionsstandarder), som hindres af fysiske begrænsninger på størrelsen af mikrokredsløbselementer og varmeafledning. Disse begrænsninger kan overvindes ved at skifte til multiprocessing, hvilket er effektivt selv for små computersystemer.
Kompleksiteten af sekventielle algoritmer er udtrykt i mængden af brugt hukommelse og den tid (antal processorcyklusser), der kræves for at udføre algoritmen. Parallelle algoritmer kræver, at der tages hensyn til brugen af en anden ressource: undersystemet for kommunikation mellem forskellige processorer. Der er to måder at kommunikere mellem processorer på: delt hukommelse og meddelelsesoverførsel.
Delte hukommelsessystemer kræver indførelse af yderligere låse for de data, der behandles, hvilket pålægger visse begrænsninger ved brug af yderligere processorer.
Beskedsystemer bruger begreberne kanaler og beskedblokke, hvilket skaber ekstra trafik på bussen og kræver ekstra hukommelse til at sætte beskeder i kø. Ved udformningen af moderne processorer kan specielle kontakter (tværbjælker) tilvejebringes for at reducere virkningen af meddelelsesudveksling på udførelsen af en opgave.
Et andet problem forbundet med brugen af parallelle algoritmer er belastningsbalancering . For eksempel er søgning efter primtal i området 1 til 100000 let at fordele blandt de tilgængelige processorer, men nogle processorer kan få mere arbejde, mens andre vil afslutte behandlingen tidligere og være inaktive. Belastningsbalanceringsproblemer forværres yderligere, når der bruges heterogene computermiljøer, hvor computerelementer adskiller sig væsentligt i ydeevne og tilgængelighed (for eksempel i netsystemer ).
En række parallelle algoritmer, kaldet distribuerede algoritmer , er specielt udviklet til brug på klynger og i distribuerede computersystemer , under hensyntagen til en række funktioner ved en sådan behandling.