Grand Central Dispatch

30.8.2009 14:40 | Přečteno: 1708× | Apple | poslední úprava: 30.8.2009 18:19

V souvislosti s uvedením Snow Leoparda se často mluví o technologii Grand Central Dispatch. Jedná se o relativně komplikovanou záležitost a asi z toho důvodu komentátoři většinou pouze opakují obecný pois ze stránek Apple, nebo co zaslechnli na WWDC. O co tedy vlastně jde? Předně je třeba říct, že se nejedná o nic nového natož pak revolučního. Existuje už několik velmi podobných implementací, pokud např. znáte Intel TBB, Qt Concurrent, Clik++ pak nemusíte v podstatě dále číst.

Microsoft chystá do VS 2010 hezky vypadající implementaci Concurrency Runtime. Doporučují prohlédnout si příklad, oproti normálnímu C++ jsou tam navíc jen lambda výrazy, na kterých to celé stiojí. Jedná se o provedení nějaké operace nad prvky nějaké kolekce a to s takovou mírou paralelity, jakou uzná za vhodné operační systém (resp. nějaký runtime nad ním). A to vše bez použití (sprostého?) slova thread.

Tady je jiný hezký příklad, který při prohledávání stavového prostoru na místech, kde by se algoritmus mohl vydat různými směry tak se rozmnoží a výpočet pokračuje všemi možnými směry současně (něco milovníky NDTM ). A to aniž by se ve zdrojáku kdekoliv vyskytlo (sprosté?) slovo thread.

Z těch příkladů je patrné, že se jedná o vytvoření programovacího paradigmatu, který:

• umožní paralelizovat výpočet aniž by bylo patrné, že na pozadí jsou nějaké thready
• izoluje progrmátora od problému typu kolik jáder má procesor, na kterém běžím, kolik z nich je vytíženo
• slibuje nižší overhead než thready
• láká k paralelizaci aplikace na všech úrovních (Dostal server request? Vytvoř nový paralelizoatelný blok, který ho zpracuje. Je v rámci zpracování requestu nutno provést několik paralelizovatelných úloh? Vytvoř pro každou z nich samostatný blok. Je součásti některé z úloh nějaký paralelizovatelný algoritmus ale ty se bojíš, že počet současně zpracovávaných requestu * počet paralelizovaných úloh na jeden request dávno překročil počet jáder, které máš k dispozici? Zapomeň na to a paralelizuj.)

Konečně zpět k GCD. Je mechanismus, který pro každý proces využívající GCD spravuje thread pool a jednu nebo více front (s prioritami) obsahujících "bloky práce", které je třeba vykonat. GCD na základě dostupných zdrojů a znalosti front z jiných procesů vybírá bloky z front, přiřazuje je threadům z thread poolu a tím je provádí. Když programátor narazí na místo, které bybylo vhodné paralelizovat tak vytvoří několik "bloků práce" a hodí je do fronty případně může nechat vytvářet bloky v reakci na nějakou událost (např. časovač nebo socket). Čas na příklad.

Mějme cyklus

for (i = 0; i < count; i++) {

  //dělej něco s i

}

ve kterém nezáleží na pořadí provádění jednotlivých iterací. Pak ji můžeme paralelizovat takhle:

dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);

 

dispatch_apply(count, queue, ^(size_t i) {

   //dělej něco s i

});

dispatch_apply vytvoří count lambda výrazů a každému z nich předa příslušnou hodnotu parametru i (tím se z nich stanou bloky) a hodí je do fronty. Blok je closure, ani nevím, jak se to řekne česky. Skončí až se celá fronta vyprázdní. Blok nemusí být definován přímo v seznamu parametrů, tzn. jako anonymní, deklaruje a definuje se velice podobně jako ukazatel na funkci. Místo hvězdičky se píše stříška. Je to edy syntaktické rozšíření C, C++ a Objective-C. Více k tomu zde. C++0x lambdy vypadají jinak a nejsou closure.

To je celý základ, zbytek je omáčka okolo- lze definovat callback, který se zavolá po dokončení bloku, lze použít semafory k omezení přístupu k limitovaným zdrojům jako např. připojení k databázi, fronty lze pozastavit, určit priority...

Čekali jste něco, co samo pozná, co se kde dá paralelizovat, vyřeší race conditions a deadlocky? Doufám, že ne páč se nic takového nekoná. Čekali jste zajímavou implementaci abstrakce nad thready s plánováním ne na úrovni procesu ale na úrovni celého systému? Pak jste se trefili.

Největším problémem GCD podle mně je, že je ukrutně platformově závislý. V multiplatformních aplikacich se to z toho důvodu asi moc používat nebude.        

Komentáře

[Aleš Janda]

Díky za pěkný článek. Umí něco takového gcc?

[frEon]

Pekny clanek. Jinak closure je myslim cesky uzaver.

[Ladicek]

Dobrý článek. Sice se v těch paralelizačních knihovnách nevyznám, ale nedávno jsem četl článek o KDEčkovém (i když tam prý žádná závislost na KDE není) ThreadWeaveru a bylo mi to hodně sympatické. Tohle mi připadá podobné A pokud to je na úrovni celého operačního systému, tím líp.

Je to mimochodem i jeden z pěkných případů použití lexikálních uzávěrů. Jako javista tiše závidím

[thingie]

Paralelizaci. (Ale třeba to fulltextové hledání zvládne nějak ošidit.)

[Yenda]

MS CR nestoji na lambda výrazech.  CR můžete používat i bez lambda, ale je to opruz -- prakticky stejně smutný případ jsou algoritmy v C++ STL.

Něco podobného umožňuje OMP, kde ten paralelismus vyjádříte pomocí #pragma (v C++) anotací a kompilátor si obstará veškerou "administrativu", jako správu vláken, dělení úlohy mezi vlákna, redukce, atd. Tuším, že úloha z MS dokumentace by vypadala přibližne takhle

array<int, 5> values = { 1, 2, 3, 4, 5 };
#pragma omp parallel for
for(int i = 0; i < 5; i++) {
  values[i] *=  values[i];
}
 

[Daniel Kvasnička ml.]

Největším problémem GCD podle mně je, že je ukrutně platformově závislý.

Jezkovy... to je prave jeho nejvetsi vyhodou. Jak jsi sam psal, v principu to neni nic zas tak prevratneho. V cem to ale prevratne je, je prave ta integrace do systemu a dostupnost pro kazdeho vyvojare a program pouzivajici 10.6. To same OpenCL. Nemusis resit nejaky vyber knihoven, verzi a podobnych kravin. Poridis si 10.6, na web napises, ze ho tvuj SW vyzaduje a tecka. Proc by to mel Apple delat multiplatformni? Co by z toho mel?

[kotyz]

Apple mozna nic, ale uzivatele ostatnich platforem by z toho mohli mit uzitek

[miho]

Ano, jistota, že každý uživatel 10.6 má GCD je výhodou. Optimistický odhad Applu je, že do roka bude mít 10.6 40 % uživatelů takže teď bude vytvářet aplikaci závislou na GCD jen dobrodruh. Není to nic proti Apple, naopak je to super výkon, za tři roky přešlo na Vistu jen 23 % uživatelů Windows. Stejně tak je super, že každý uživatel Windows má .net framework hned po instalaci systému. Jak to ale souvisí s větou, na kterou reaguješ?

Tu poslední otázku doufám nemyslíš vážně. Vzhledem k množství multiplatformního softu pro Mac OS je mimořádně hloupá.

[Daniel Kvasnička ml.]

Stejně tak je super, že každý uživatel Windows má .net framework hned po instalaci systému.

To je asi tak super, jako ze kazdy uzivatel Mac OS X ma Cocoa hned po instalaci systemu, nebo to same s Ubuntu a GTK+

Jak to ale souvisí s větou, na kterou reaguješ?

Souvisi to s ni tak, ze kdyby GCD mel byt multiplatformni, bylo by mnohem tezsi ho tolik zadratovat do systemu. Vzhledem k rozdilum mezi kernely jednotlivych mainstream OS...

Tu poslední otázku doufám nemyslíš vážně. Vzhledem k množství multiplatformního softu pro Mac OS je mimořádně hloupá.

Tak jeste jednou. Co by Apple mel z toho, kdyby GCD delal multiplatformni? Kudy by se mu vratily investice do takoveho podniku? Ze by multiplatformni aplikace, ktere jsou mj. i pro Mac, mohly pouzivat GCD i jinde nez na Macu? ... Multiplatformni aplikace samozrejme budou moci GCD i OpenCL pouzivat stejne jako aplikace nativni, akorat jen pokud pojedou na Macu. To je pro Apple prave konkurencni vyhoda.

[miho]

Využívat můžou ale dělat to nebudou. Pochybuju, že by kvůli jediné platformě začal v těch nejhlubších výpočetních vrstvách aplikace někdo #IFDEFovat.

[Daniel Kvasnička ml.]

No on ten rozdil je (a bude) na nekterych grafikach oproti CPU tak svinsky velky, ze u nekterych specifickych aplikaci se IFDEFovat bude, protoze by byl hrich to nevyuzit. Navic brzy urcite vzniknou wrappery pro dalsi jazyky (pro Javu uz tusim je, pro Obj-C samozrejme uz taktez) a tak to bude mozne vyresit i mene prasackym zpusobem nez prostym vetvenim programu.... proste budes mit rozhrani a nekolik implementaci, z nichz se spravna zvoli podle toho, na cem zrovna bezis...

[Daniel Kvasnička ml.]

To s tou grafikou bylo mysleno na OpenCL...