Paralelní algoritmus - Parallel algorithm

Ve výpočetní technice je paralelní algoritmus , na rozdíl od tradičního sériového algoritmu , algoritmus, který může provádět více operací v daném čase. V počítačových vědách bylo tradicí popisovat sériové algoritmy v abstraktních modelech strojů , často známých jako stroje s náhodným přístupem . Podobně mnoho vědců z oblasti výpočetní techniky použilo takzvaný paralelní stroj s náhodným přístupem (PRAM) jako paralelní abstraktní stroj (sdílená paměť).

Mnoho paralelních algoritmů se provádí souběžně - i když obecně jsou souběžné algoritmy odlišným konceptem - a proto jsou tyto koncepty často sjednoceny, s nimiž je aspekt algoritmu paralelní a který současně není jasně rozlišen. Neparalelní, nesouběžné algoritmy jsou dále často označovány jako „ sekvenční algoritmy “, na rozdíl od souběžných algoritmů.

Paralelizovatelnost

Algoritmy se významně liší v tom, jak jsou paralelizovatelné, od snadno paralelizovatelných po zcela neporovnatelné. Dále může daný problém pojmout různé algoritmy, které mohou být více či méně paralelizovatelné.

Některé problémy lze tímto způsobem snadno rozdělit na kousky - říká se jim trapně paralelní problémy. Mezi příklady patří mnoho algoritmů k řešení Rubikových kostek a hledání hodnot, jejichž výsledkem je daný hash .

Některé problémy nelze rozdělit na paralelní části, protože pro efektivní pokračování v dalším kroku vyžadují výsledky z předchozího kroku - ty se nazývají neodmyslitelně sériový problém s. Mezi příklady patří iterativnínumerické metody, jako jeNewtonova metoda, iterativní řešeníproblémusetřemi tělya většina dostupných algoritmů pro výpočet(π). Některé sekvenční algoritmy lze převést na paralelní algoritmy pomocíautomatické paralelizace.

Motivace

Paralelní algoritmy na jednotlivých zařízeních se staly běžnějšími od počátku 20. let 20. století kvůli podstatným vylepšením systémů s více procesory a nárůstu vícejádrových procesorů. Až do konce roku 2004 se výkon jednojádrového procesoru rychle zvyšoval pomocí škálování frekvencí , a proto bylo snazší sestrojit počítač s jedním rychlým jádrem než s mnoha pomalejšími jádry se stejnou propustností , takže vícejádrové systémy byly omezenější použití. Od roku 2004 však frekvenční škálování narazilo na zeď, a tak se vícejádrové systémy staly rozšířenějšími, což umožnilo paralelnější algoritmy použít obecněji.

Problémy

Sdělení

Cena nebo složitost sériových algoritmů se odhaduje z hlediska prostoru (paměti) a času (cykly procesoru), které zabírají. Paralelní algoritmy potřebují optimalizovat ještě jeden zdroj, komunikaci mezi různými procesory. Existují dva způsoby komunikace paralelních procesorů, sdílení paměti nebo předávání zpráv.

Zpracování sdílené paměti vyžaduje další uzamčení dat, ukládá režii dalších cyklů procesoru a sběrnice a také serializuje určitou část algoritmu.

Zpracování předávání zpráv používá kanály a schránky zpráv, ale tato komunikace přidává režii přenosu na sběrnici, potřebu další paměti pro fronty a schránky zpráv a latenci ve zprávách. Designy paralelních procesorů používají speciální sběrnice, jako je příčka, takže komunikační režie bude malá, ale o objemu provozu rozhoduje paralelní algoritmus.

Pokud komunikační režie dalších procesorů převáží výhodu přidání dalšího procesoru, narazí na paralelní zpomalení .

Vyrovnávání zatížení

Dalším problémem paralelních algoritmů je zajistit, aby byly vhodně vyváženy zátěží tím, že zajistí vyvážení zátěže (celkové práce), nikoli vyvážení velikosti vstupu. Například kontrola primitivnosti všech čísel od jednoho do sto tisíc je snadné rozdělit mezi procesory; pokud jsou však čísla rovnoměrně rozdělena rovnoměrně (1–1 000, 1 001–2 000 atd.), bude množství práce nevyvážené, protože menší počet je díky tomuto algoritmu snazší zpracovat (snazší je otestovat primitivitu) některé procesory tak získají více práce než ostatní, které budou nečinné, dokud se načtené procesory nedokončí.

Distribuované algoritmy

Podtyp paralelních algoritmů, distribuované algoritmy , jsou algoritmy navržené pro práci v prostředí klastrových výpočtů a distribuovaných výpočtů , kde je třeba řešit další obavy nad rámec „klasických“ paralelních algoritmů.

Viz také

Reference

externí odkazy