Paralelní algoritmus
V informatice je paralelní algoritmus , na rozdíl od tradičních sekvenčních algoritmů , algoritmem , který lze implementovat po částech na mnoha různých počítačových zařízeních, po kterých následuje spojení získaných výsledků a získání správného výsledku.
Některé algoritmy lze poměrně snadno rozdělit na samostatně spustitelné části. Například rozdělení práce na kontrolu všech čísel od 1 do 100 000, aby bylo možné zjistit, která z nich jsou prvočísla , lze provést tak, že každému dostupnému procesoru přiřadíte určitou podmnožinu čísel a výsledné sady prvočísel zkombinujete (například projekt GIMPS je implementován podobným způsobem ) .
Na druhou stranu většina známých algoritmů pro výpočet hodnoty pí neumožňuje rozdělení na paralelní části, protože vyžadují výsledek předchozí iterace algoritmu. Iterativní numerické metody , jako je například Newtonova metoda nebo problém tří těles , jsou také čistě sekvenční algoritmy. Některé příklady rekurzivních algoritmů je poměrně obtížné paralelizovat. Jedním z příkladů je hloubkové vyhledávání v grafech .
Paralelní algoritmy jsou velmi důležité kvůli neustálému zlepšování víceprocesorových systémů a zvyšování počtu jader v moderních procesorech. Obvykle je jednodušší navrhnout počítač s jedním rychlým procesorem než s mnoha pomalými procesory (za předpokladu, že je dosaženo stejného výkonu ). Výkon procesorů se však zvyšuje především z důvodu zlepšení technického procesu (snížení výrobních standardů), kterému brání fyzikální omezení velikosti mikroobvodových prvků a odvodu tepla. Tato omezení lze překonat přechodem na multiprocesing, který je účinný i pro malé výpočetní systémy.
Složitost sekvenčních algoritmů je vyjádřena množstvím použité paměti a časem (počet cyklů procesoru) potřebným k provedení algoritmu. Paralelní algoritmy vyžadují zohlednění použití jiného zdroje: subsystému komunikace mezi různými procesory. Existují dva způsoby komunikace mezi procesory: sdílená paměť a předávání zpráv.
Systémy sdílené paměti vyžadují zavedení dalších zámků pro zpracovávaná data, což ukládá určitá omezení při použití dalších procesorů.
Systémy zasílání zpráv používají koncepty kanálů a bloků zpráv, což vytváří další provoz na sběrnici a vyžaduje další paměť pro řazení zpráv do fronty. V návrhu moderních procesorů mohou být poskytnuty speciální přepínače (crossbars), aby se snížil dopad výměny zpráv na dobu provádění úlohy.
Dalším problémem spojeným s používáním paralelních algoritmů je vyvažování zátěže . Například hledání prvočísel v rozsahu 1 až 100 000 lze snadno rozdělit mezi dostupné procesory, ale některé procesory mohou dostat více práce, zatímco jiné dokončí zpracování dříve a budou nečinné. Problémy s vyrovnáváním zátěže se dále prohlubují při použití heterogenních výpočetních prostředí, ve kterých se výpočetní prvky výrazně liší výkonem a dostupností (například v gridových systémech).
Různé paralelní algoritmy, nazývané distribuované algoritmy , jsou speciálně vyvinuty pro použití na klastrech a v distribuovaných počítačových systémech , přičemž je třeba vzít v úvahu řadu vlastností takového zpracování.