Granularity (paralelní výpočet) - Granularity (parallel computing)

v paralelní výpočty, zrnitost (nebo obilí velikost) a úkol je míra množství práce (nebo výpočtu), která je daným úkolem provedena.[1]

Jiná definice podrobnosti bere v úvahu komunikaci nad hlavou mezi více procesory nebo prvky zpracování. Definuje zrnitost jako poměr doby výpočtu k době komunikace, přičemž doba výpočtu je doba potřebná k provedení výpočtu úkolu a doba komunikace je doba potřebná k výměně dat mezi procesory.[2]

Li je doba výpočtu a označuje komunikační čas, pak Granularity G úkolu lze vypočítat jako:[2]

Granularita se obvykle měří z hlediska počtu pokynů provedených v konkrétní úloze.[1] Alternativně lze granularitu specifikovat také z hlediska doby provádění programu kombinující výpočetní čas a komunikační čas.[1]

Druhy paralelismu

V závislosti na množství práce, která je prováděna paralelním úkolem, lze paralelismus rozdělit do tří kategorií: jemnozrnný, středně zrnitý a hrubozrnný paralelismus.

Jemnozrnný paralelismus

V jemnozrnném paralelismu je program rozdělen na velké množství malých úkolů. Tyto úkoly jsou jednotlivě přiřazeny mnoha procesorům. Množství práce spojené s paralelním úkolem je nízké a práce je rovnoměrně rozdělena mezi procesory. Proto usnadňuje jemnozrnný paralelismus vyvažování zátěže.[3]

Protože každý úkol zpracovává méně dat, je počet procesorů potřebných k provedení úplného zpracování vysoký. To zase zvyšuje režii komunikace a synchronizace.

Jemnozrnný paralelismus se nejlépe využívá v architekturách, které podporují rychlou komunikaci. Sdílená paměť architektura, která má nízkou komunikační režii, je nejvhodnější pro jemnozrnný paralelismus.

Pro programátory je obtížné detekovat paralelismus v programu, proto je obvykle překladače odpovědnost za detekci jemnozrnného paralelismu.[1]

Příkladem jemnozrnného systému (mimo doménu paralelní výpočetní techniky) je systém neurony v našem mozek.[4]

Připojovací stroj (CM-2) a J-Machine jsou příklady jemnozrnných paralelních počítačů, které mají velikost zrn v rozmezí 4-5 μs.[1]

Hrubozrnný paralelismus

V hrubozrnném paralelismu je program rozdělen na velké úkoly. Z tohoto důvodu probíhá v procesorech velké množství výpočtů. To může mít za následek nerovnováhu zatížení, kdy určité úkoly zpracovávají většinu dat, zatímco jiné mohou být nečinné. Dále hrubozrnný paralelismus nedokáže využít paralelismus v programu, protože většina výpočtu se provádí postupně na procesoru. Výhodou tohoto typu paralelismu je nízká režie komunikace a synchronizace.

Předávání zpráv architektura komunikuje data mezi procesy dlouho, takže je vhodná pro hrubozrnný paralelismus.[1]

Cray Y-MP je příklad hrubozrnného paralelního počítače, který má velikost zrna asi 20 s.[1]

Středně zrnitý paralelismus

Středně zrnitý paralelismus se používá relativně k jemnozrnnému a hrubozrnnému paralelismu. Středně zrnitý paralelismus je kompromisem mezi jemnozrnným a hrubozrnným paralelismem, kde máme velikost úkolu a čas komunikace větší než jemnozrnný paralelismus a nižší než hrubozrnný paralelismus. Většina univerzálních paralelních počítačů spadá do této kategorie.[4]

Intel iPSC je příklad středně zrnitého paralelního počítače, který má velikost zrna asi 10 ms.[1]

Příklad

Zvažte obrázek 10 * 10, který je třeba zpracovat, vzhledem k tomu, že zpracování 100 pixelů je na sobě nezávislé.

Jemnozrnný paralelismus: Předpokládejme, že existuje 100 procesorů, které jsou zodpovědné za zpracování obrazu 10 * 10. Ignorování režie komunikace, 100 procesorů dokáže zpracovat obraz 10 * 10 v 1 hodinovém cyklu. Každý procesor pracuje na 1 pixelu obrazu a poté komunikuje výstup s dalšími procesory. Toto je příklad jemnozrnného paralelismu.

Středně zrnitý paralelismus: Vezměte v úvahu, že obraz 10 * 10 zpracovává 25 procesorů. Zpracování obrazu bude nyní trvat 4 hodinové cykly. Toto je příklad středně zrnitého paralelismu.

Hrubozrnný paralelismus: Dále, pokud snížíme procesory na 2, bude zpracování trvat 50 hodinových cyklů. Každý procesor musí zpracovat 50 prvků, což zvyšuje výpočetní dobu, ale komunikační režie klesá s tím, jak se snižuje počet procesorů, které sdílejí data. Tento případ ilustruje hrubozrnný paralelismus.

Fine-grain: Pseudokód pro 100 procesorůStřední zrno: Pseudokód pro 25 procesorůCoarse-grain: Pseudokód pro 2 procesory
prázdnota hlavní(){  přepínač (ID procesoru)  {    případ 1: Vypočítat živel 1; přestávka;    případ 2: Vypočítat živel 2; přestávka;    případ 3: Vypočítat živel 3; přestávka;    .    .    .    .    případ 100: Vypočítat živel 100;               přestávka;  }}
prázdnota hlavní(){  přepínač (ID procesoru)  {    případ 1: Vypočítat elementy 1-4; přestávka;    případ 2: Vypočítat elementy 5-8; přestávka;    případ 3: Vypočítat elementy 9-12; přestávka;    .    .    případ 25: Vypočítat elementy 97-100;              přestávka;  }}
prázdnota hlavní(){  přepínač (ID procesoru)  {    případ 1: Vypočítat elementy 1-50;             přestávka;    případ 2: Vypočítat elementy 51-100;             přestávka;  }}
Čas výpočtu - 1 hodinový cyklusVýpočetní doba - 4 hodinové cyklyVýpočetní doba - 50 hodinových cyklů

Úrovně paralelismu

Granularita úzce souvisí s úrovní zpracování. Program lze rozdělit do 4 úrovní paralelismu -

  1. Úroveň instrukce.
  2. Úroveň smyčky
  3. Dílčí úroveň a
  4. Programová úroveň

Nejvyššího množství paralelismu je dosaženo při návod úrovni, následuje na úrovni smyčky rovnoběžnost. Na úrovni instrukcí a smyček je dosaženo jemnozrnného paralelismu. Typická velikost zrna na úrovni instrukcí je 20 instrukcí, zatímco velikost zrna na úrovni smyčky je 500 instrukcí.[1]

Na podprogram (nebo postup) úroveň zrnitosti je obvykle několik tisíc pokynů. Středně zrnitého paralelismu je dosaženo na dílčí rutinní úrovni.[1]

Na programová úroveň, probíhá paralelní provádění programů. Granularita může být v rozmezí desítek tisíc pokynů.[1] Na této úrovni se používá hrubozrnný paralelismus.

Níže uvedená tabulka ukazuje vztah mezi úrovněmi paralelismu, velikostí zrna a stupněm paralelismu

ÚrovněVelikost zrnaRovnoběžnost
Úroveň instrukcePokutaNejvyšší
Úroveň smyčkyPokutaMírný
Dílčí úroveňStředníMírný
Programová úroveňHrubýNejméně

Dopad členitosti na výkon

Granularity ovlivňuje výkon paralelních počítačů. Použití jemných zrn nebo malých úkolů má za následek větší paralelismus, a tím zvyšuje zrychlit. Režie synchronizace však plánování strategie atd. mohou negativně ovlivnit výkon jemnozrnných úkolů. Samotné zvýšení paralelismu nemůže podat nejlepší výkon.[5]

Aby se snížila režie komunikace, lze zvýšit granularitu. Hrubozrnné úkoly mají menší komunikační režii, ale často způsobují nerovnováhu zátěže. Optimálního výkonu je tedy dosaženo mezi dvěma extrémy jemnozrnného a hrubozrnného paralelismu.[6]

Různé studie[5][7][8] navrhli své řešení, které pomůže určit nejlepší granularitu pro podporu paralelního zpracování. Nalezení nejlepší velikosti zrna závisí na řadě faktorů a od problému k problému se velmi liší.

Viz také

Citace

  1. ^ A b C d E F G h i j k Hwang, Kai (1992). Pokročilá architektura počítače: paralelismus, škálovatelnost, programovatelnost (1. vyd.). McGraw-Hill Higher Education. ISBN  978-0070316225.
  2. ^ A b Kwiatkowski, Jan (9. září 2001). Hodnocení paralelních programů měřením jeho granularity. Paralelní zpracování a aplikovaná matematika. Přednášky z informatiky. 2328. str. 145–153. doi:10.1007/3-540-48086-2_16. ISBN  9783540437925. ISBN  9783540480860.
  3. ^ Barney, Blaise. Úvod do paralelního výpočtu.
  4. ^ A b Miller, Russ; Stout, Quentin F. (1996). Paralelní algoritmy pro pravidelné architektury: Mřížky a pyramidy. Cambridge, Massachusetts: MIT Press. str. 5–6. ISBN  9780262132336.
  5. ^ A b Chen, Ding-Kai; Su, Hong-Men; Yew, Pen-Chung (1. ledna 1990). "Dopad synchronizace a granularity na paralelní systémy". Sborník ze 17. výročního mezinárodního symposia o počítačové architektuře. 18 (2SI): 239–248. CiteSeerX  10.1.1.51.3389. doi:10.1145/325164.325150.
  6. ^ Yeung, Donald; Dally, William J .; Agarwal, Anant. "Jak vybrat velikost zrna paralelního počítače". CiteSeerX  10.1.1.66.3298. Citovat deník vyžaduje | deník = (Pomoc)
  7. ^ McCreary, Carolyn; Gill, Helen (1. září 1989). "Automatické stanovení velikosti zrna pro efektivní paralelní zpracování". Commun. ACM. 32 (9): 1073–1078. doi:10.1145/66451.66454. ISSN  0001-0782.
  8. ^ Kruatrachue, Boontee; Lewis, Ted (1. ledna 1988). "Určení velikosti zrna pro paralelní zpracování". Software IEEE. 5 (1): 23–32. doi:10.1109/52.1991. ISSN  0740-7459.