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

V paralelním počítání je zrnitost (nebo velikost zrna ) úkolu měřítkem množství práce (nebo výpočtu), které tento úkol provádí.

Další definice granularity bere v úvahu režii komunikace mezi více procesory nebo prvky zpracování. Granularitu definuje jako poměr času výpočtu k času komunikace, přičemž doba výpočtu je čas potřebný k provedení výpočtu úkolu a čas komunikace je čas potřebný k výměně dat mezi procesory.

Pokud je čas výpočtu a označuje čas komunikace, pak granularita G úkolu lze vypočítat jako:

Granularita se obvykle měří z hlediska počtu instrukcí provedených v konkrétním úkolu. Alternativně lze také určit granularitu z hlediska doby provádění programu, která kombinuje čas výpočtu a čas komunikace.

Typy paralelismu

V závislosti na množství práce, která je vykonávána paralelním úkolem, lze paralelismus rozdělit do tří kategorií: rovnoběžnost jemnozrnná, střednězrnná a hrubozrnná.

Jemnozrnný paralelismus

V jemnozrnném paralelismu je program rozdělen na velké množství malých úkolů. Tyto úkoly jsou jednotlivě přiřazovány 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. Jemně zrnitý rovnoběžnost tedy usnadňuje vyvažování zátěže .

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

Jemně zrnitý paralelismus se nejlépe využívá v architekturách, které podporují rychlou komunikaci. Pro jemnozrnný paralelismus je nejvhodnější architektura sdílené paměti, která má nízkou komunikační režii.

Pro programátory je obtížné detekovat paralelismus v programu, a proto je obvykle odpovědností překladatelů detekovat jemnozrnný paralelismus.

Příkladem jemnozrnného systému (zvenčí paralelní výpočetní domény) je systém neuronů v našem mozku .

Connection Machine (CM-2) a J-Machine jsou příklady jemnozrnných paralelních počítačů, které mají velikost zrna v rozmezí 4-5 μs.

Hrubozrnný paralelismus

V hrubozrnném paralelismu je program rozdělen na velké úkoly. Díky tomu probíhá v procesorech velké množství výpočtů. To může mít za následek nerovnováhu zatížení, kdy některé úkoly zpracovávají většinu dat, zatímco jiné mohou být nečinné. Hrubozrnný paralelismus dále 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.

Architektura předávání zpráv trvá dlouhou dobu, než je možné sdělovat data mezi procesy, což ji činí vhodnou pro hrubozrnný paralelismus.

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

Středně zrnitý paralelismus

Středně zrnitá rovnoběžnost se používá relativně k jemnozrnné a hrubozrnné rovnoběžnosti. Středně zrnitý rovnoběžnost je kompromisem mezi jemnozrnným a hrubozrnným paralelismem, kde máme velikost úkolu a komunikační čas větší než jemnozrnný paralelismus a nižší než hrubozrnný rovnoběžnost. Většina paralelních počítačů pro všeobecné použití spadá do této kategorie.

Intel iPSC je příkladem středně zrnitého paralelního počítače, který má velikost zrna přibližně 10 ms.

Příklad

Zvažte obrázek 10*10, který je třeba zpracovat, protož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. Ignorující režii komunikace, 100 procesorů dokáže zpracovat obraz 10*10 v 1 hodinovém cyklu. Každý procesor pracuje na 1 pixelu obrazu a poté sděluje výstup ostatním procesorům. Toto je příklad jemnozrnného paralelismu.

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

Hrubozrnný paralelismus: Pokud dále snížíme procesory na 2, pak zpracování zabere 50 hodinových cyklů. Každý procesor potřebuje zpracovat 50 prvků, což prodlužuje dobu výpočtu, ale režie komunikace klesá, protože se snižuje počet procesorů, které sdílejí data. Tento případ ukazuje hrubozrnný paralelismus.

Jemné zrno: Pseudokód pro 100 procesorů Střední zrno: Pseudokód pro 25 procesorů Hrubozrnný: Pseudokód pro 2 procesory
void main()
{
  switch (Processor_ID)
  {
    case 1: Compute element 1; break;
    case 2: Compute element 2; break;
    case 3: Compute element 3; break;
    .
    .
    .
    .
    case 100: Compute element 100; 
              break;
  }
}
void main()
{
  switch (Processor_ID)
  {
    case 1: Compute elements 1-4; break;
    case 2: Compute elements 5-8; break;
    case 3: Compute elements 9-12; break;
    .
    .
    case 25: Compute elements 97-100; 
             break;
  }
}
void main()
{
  switch (Processor_ID)
  {
    case 1: Compute elements 1-50; 
            break;
    case 2: Compute elements 51-100; 
            break;
  }
}
Výpočetní čas - 1 hodinový cyklus Výpočetní čas - 4 hodinové cykly Výpočetní čas - 50 hodinových cyklů

Úrovně paralelismu

Zrnitost je úzce svázána s úrovní zpracování. Program lze rozdělit do 4 úrovní paralelismu -

  1. Úroveň instrukce.
  2. Úroveň smyčky
  3. Sub-rutinní úroveň a
  4. Programová úroveň

Nejvyššího množství paralelismu je dosaženo na úrovni instrukcí , následuje paralelismus na úrovni smyčky . Na úrovni instrukcí a smyčky 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í.

Na úrovni sub-rutiny (nebo procedury) je velikost zrna obvykle několik tisíc instrukcí. Středně zrnitého paralelismu je dosaženo na sub-rutinní úrovni.

Na úrovni programu probíhá paralelní spouštění programů. Zrnitost se může pohybovat v řádu desítek tisíc instrukcí. Na této úrovni se používá hrubozrnný paralelismus.

Níže uvedená tabulka ukazuje vztah mezi úrovněmi rovnoběžnosti, velikostí zrn a stupněm rovnoběžnosti

Úrovně Velikost zrna Rovnoběžnost
Úroveň instrukce Pokuta Nejvyšší
Úroveň smyčky Pokuta Mírný
Sub-rutinní úroveň Střední Mírný
Programová úroveň Hrubý Nejméně

Vliv granularity na výkon

Zrnitost ovlivňuje výkon paralelních počítačů. Použití jemných zrn nebo malých úkolů vede k většímu paralelismu, a proto zvyšuje zrychlení . Synchronizační režie, strategie plánování atd. Však mohou negativně ovlivnit výkon jemnozrnných úkolů. Samotné zvyšování paralelismu nemůže poskytnout nejlepší výkon.

Aby se snížila režie komunikace, lze zvýšit zrnitost. Hrubozrnné úkoly mají menší režii komunikace, ale často způsobují nerovnováhu zatížení. Optimálního výkonu je tedy dosaženo mezi dvěma extrémy jemnozrnné a hrubozrnné rovnoběžnosti.

Různé studie navrhly jejich řešení, které pomůže určit nejlepší zrnitost pro podporu paralelního zpracování. Nalezení nejlepší zrnitosti závisí na řadě faktorů a velmi se liší problém od problému.

Viz také

Citace