Cilk - Cilk

Cilk , Cilk ++ a Cilk Plus jsou univerzální programovací jazyky určené pro vícevláknové paralelní výpočty . Jsou založeny na programovacích jazycích C a C ++ , které rozšiřují o konstrukce pro vyjádření paralelních smyček a idiom spojení vidlice .

Původně vyvinut v 90. letech na Massachusetts Institute of Technology (MIT) ve skupině Charlese E. Leisersona , byl Cilk později prodán jako Cilk ++ spinoffovou společností Cilk Arts. Tuto společnost následně získala společnost Intel , která zvýšila kompatibilitu se stávajícím kódem C a C ++ a výsledkem byla Cilk Plus.

Dějiny

MIT Cilk

Programovací jazyk Cilk vyrostl ze tří samostatných projektů v laboratoři MIT pro informatiku:

• Teoretická práce na plánování vícevláknových aplikací.
• StarTech - paralelní šachový program postavený na běhu na modelu Connection Machine společnosti CM-5 společnosti Thinking Machines Corporation.
• PCM / Threaded-C - balíček na bázi C pro plánování vláken ve stylu pokračování předávání na CM-5

V dubnu 1994 byly tyto tři projekty spojeny a pokřtěny „Cilk“. Jméno Cilk není zkratka, ale narážka na „hezká vlákna“ ( hedvábí ) a programovací jazyk C. Kompilátor Cilk-1 byl vydán v září 1994.

Původní jazyk Cilk byl založen na ANSI C s přidáním klíčových slov specifických pro Cilk, které signalizují paralelismus. Když jsou klíčová slova Cilk odstraněna ze zdrojového kódu Cilk, výsledkem by měl být vždy platný program C, nazývaný sériová eliminace (nebo C elision ) úplného programu Cilk, se stejnou sémantikou jako program Cilk běžící na jednom procesoru. I přes několik podobností, Cilk není v přímém vztahu k AT & T Bell Labs Současné C .

Cilk byl implementován jako překladač do jazyka C zaměřený na GNU C Compiler (GCC). Poslední verze, Cilk 5.4.6, je k dispozici v MIT Computer Science and Artificial Intelligence Laboratory (CSAIL), ale již není podporována.

Přehlídkou schopností Cilka byl paralelní šachový program Cilkchess, který v 90. letech získal několik počítačových šachových cen, včetně Open Dutch Computer Chess Championship z roku 1996.

Cilk Arts a Cilk ++

Před c.  V roce 2006 byl trh společnosti Cilk omezen na vysoce výkonné výpočty. Vznik vícejádrových procesorů v běžných počítačích znamenal, že každý rok byly dodávány stovky milionů nových paralelních počítačů. Cilk Arts bylo založeno, aby tuto příležitost využilo: v roce 2006 Leiserson zahájil Cilk Arts, aby vytvořil a uvedl na trh moderní verzi Cilk, která podporuje komerční potřeby nastupující generace programátorů. Společnost uzavřela kolo rizikového financování série A v říjnu 2007 a její produkt Cilk ++ 1.0 byl dodán v prosinci 2008.

Cilk ++ se od Cilka liší několika způsoby: podpora C ++, podpora smyček a hyperobjekty  - nový konstrukt navržený k řešení problémů s datovými rasami vytvořených paralelními přístupy ke globálním proměnným. Cilk ++ byl proprietární software . Stejně jako jeho předchůdce byl implementován jako kompilátor Cilk-to-C ++. Podporoval překladače Microsoft a GNU.

Intel Cilk Plus

Dne 31. července 2009 společnost Cilk Arts na svých webových stránkách oznámila, že její produkty a technický tým jsou nyní součástí společnosti Intel Corp. Na začátku roku 2010 začala webová stránka Cilk na webu www.cilk.compřesměrovávat na web Intel (počátkem roku 2017 se původní webová stránka Cilk již se nerozlišuje na hostitele). Intel a Cilk Arts tuto technologii integrovali a vylepšili, což mělo za následek vydání Intel Cilk Plus ze září 2010 . Cilk Plus přijímá zjednodušení navržená společností Cilk Arts v Cilk ++, aby eliminovala potřebu několika původních klíčových slov Cilk a přidala schopnost rozmnožit funkce a vypořádat se s proměnnými zapojenými do redukčních operací. Cilk Plus se liší od Cilk a Cilk ++ přidáním rozšíření pole, začleněním do komerčního kompilátoru (od společnosti Intel) a kompatibilitou se stávajícími debuggery.

Cilk Plus byl poprvé implementován v kompilátoru Intel C ++ vydáním kompilátoru Intel v programu Intel Composer XE 2010. Implementaci open source (s licencí BSD ) společnost Intel přispěla do GNU Compiler Collection (GCC), která dodávala podporu Cilk Plus ve verzi 4.9, kromě klíčového slova _Cilk_for , které bylo přidáno v GCC 5.0. V únoru 2013 společnost Intel oznámila vidlici Clang s podporou Cilk Plus. Intel Compiler, ale ne implementace open source, přichází s detektorem rasy a analyzátorem výkonu.

Společnost Intel ji později přerušila a doporučila svým uživatelům přejít na místo toho pomocí OpenMP nebo vlastní knihovny TBB společnosti Intel pro potřeby paralelního programování.

Rozdíly mezi verzemi

V původní implementaci MIT Cilk je ve skutečnosti první klíčové slovo Cilk cilk, které identifikuje funkci napsanou v Cilku. Vzhledem k tomu, že procedury Cilk mohou přímo volat procedury C, ale procedury C nemohou přímo volat nebo plodit procedury Cilk, je toto klíčové slovo potřeba k odlišení kódu Cilk od kódu C. Cilk Plus odstraní toto omezení i cilkklíčové slovo, takže funkce C a C ++ mohou volat do kódu Cilk Plus a naopak.

Zastarávání

V květnu 2017 byl vydán GCC 7.1 a označil podporu Cilk Plus za zastaralou. Samotný Intel v září 2017 oznámil, že s vydáním Nástrojů pro vývoj softwaru Intel od roku 2018 ukončí podporu Cilk Plus. V květnu 2018 vyšlo GCC 8.1 s odstraněnou podporou Cilk Plus.

Jazykové funkce

Princip konstrukce Cilk jazyka spočívá v tom, že programátor by měl být zodpovědný za odhalení paralelismu, identifikaci prvků, které lze bezpečně provést paralelně; poté by mělo být ponecháno na běhovém prostředí, zejména plánovači , aby se během provádění rozhodlo, jak skutečně rozdělit práci mezi procesory. Je to proto, že tyto odpovědnosti jsou odděleny, že program Cilk může běžet bez přepisování na libovolný počet procesorů, včetně jednoho.

Paralelnost úkolů: založit a synchronizovat

Hlavním přírůstkem Cilk k C jsou dvě klíčová slova, která společně umožňují psaní paralelních programů úloh.

• Potěr klíčových slov, když předcházející volání funkce ( potěr f (x) ), znamená to, že volání funkce ( f (x) ) se může bezpečně vedeny paralelně s závěrky následujících jej ve volání funkce. Upozorňujeme, že plánovač není povinen spouštět tento postup paralelně; klíčové slovo pouze upozorní plánovače, že tak může učinit.
• Příkaz synchronizace označuje, že provádění aktuální funkce nemůže pokračovat, dokud nebudou dokončena všechna dříve vytvořená volání funkcí. Toto je příklad bariérové metody.

(V Cilk Plus jsou klíčová slova napsána _Cilk_spawn a _Cilk_sync , nebo cilk_spawn a cilk_sync, pokud jsou zahrnuta záhlaví Cilk Plus.)

Níže je rekurzivní implementace funkce Fibonacci v Cilku s paralelními rekurzivními voláními, která demonstrují spawn a synchronizují klíčová slova. Původní Cilk vyžadoval, aby každá funkce používající tyto byla opatřena poznámkami s klíčovým slovem cilk , které je od Cilk Plus pryč. (Kód programu Cilk není očíslován; čísla byla přidána pouze pro snazší sledování diskuse.)

cilk int fib(int n) {
    if (n < 2) {
        return n;
    }
    else {
       int x, y;

       x = spawn fib(n - 1);
       y = spawn fib(n - 2);

       sync;

       return x + y;
    }
}

Pokud byl tento kód spuštěn jediným procesorem k určení hodnoty fib (2) , tento procesor by vytvořil rámec pro fib (2) a provedl řádky 1 až 5. Na řádku 6 by vytvořil mezery v rámci pro držet hodnoty x a y . Na řádku 8 by procesor musel pozastavit aktuální rámec, vytvořit nový rámec pro provedení procedury fib (1) , spustit kód tohoto rámce až do dosažení návratového příkazu a poté obnovit rámec fib (2) pomocí hodnotu fib (1) umístěno do FIB (2) je x variabilní. Na dalším řádku, musela by znovu pozastavit vykonat lež (0) a umístěte výsledek fib (2) ‚s y proměnnou.

Když je kód spuštěn na víceprocesorovém počítači, provádění však probíhá jinak. Jeden procesor zahájí provádění fib (2) ; když dosáhne řádku 8, klíčové slovo spawn upravující volání fib (n-1) řekne procesoru, že může bezpečně dát práci druhému procesoru: tento druhý procesor může vytvořit rámec pro fib (1) , provést jeho kód a po dokončení uložit jeho výsledek do rámce fib (2) ; první procesor pokračuje ve provádění kódu fib (2) současně. Zpracovatel není povinen přiřadit jinde vytvořenou proceduru; pokud má stroj pouze dva procesory a druhý je stále zaneprázdněn na fib (1), když se procesor provádějící fib (2) dostane k volání procedury, první procesor pozastaví fib (2) a provede samotný fib (0) , protože bylo by to, kdyby to byl jediný procesor. Samozřejmě, pokud je k dispozici jiný procesor, bude povolán do provozu a všechny tři procesory budou současně spouštět samostatné rámce.

(Předchozí popis není zcela přesný. I když běžná terminologie pro diskusi o Cilkovi odkazuje na procesory, které se rozhodnou založit práci s jinými procesory, je to vlastně plánovač, který přiřazuje procedury procesorům k provedení pomocí politiky zvané work- krádež , popsáno později.)

Pokud by procesor provádějící fib (2) provedl řádek 13 dříve, než oba ostatní procesory dokončí své rámce, vygenerovalo by to nesprávný výsledek nebo chybu; fib (2) by se snažit přidat hodnoty uložené v x a y , ale jeden nebo oba z těchto hodnot by chybět. To je účel klíčového slova sync , které vidíme na řádku 11: říká procesoru provádějícímu rámec, že ​​musí pozastavit své vlastní provádění, dokud se nevrátí všechna volání procedur, která se objevila. Když fib (2) se nechá probíhat kolem synchronizační příkazu v potrubí 11, může být jen proto, že malá lež (1) a fib (0) dokončení a umístí své výsledky v x a y , takže je bezpečně provádět výpočty na ty Výsledek.

Výše uvedený příklad kódu používá syntaxi Cilk-5. Původní Cilk (Cilk-1) používal poněkud odlišnou syntaxi, která vyžadovala programování ve stylu explicitního předávání pokračování , a příklady Fibonacci vypadají takto:

thread fib(cont int k, int n)
{
    if (n < 2) {
        send_argument(k, n);
    }
    else {
        cont int x, y;
        spawn_next sum(k, ?x, ?y);
        spawn fib(x, n - 1);
        spawn fib(y, n - 2);
    }
}

thread sum(cont int k, int x, int y)
{
     send_argument(k, x + y);
}

Uvnitř FIB je rekurzivní případ, spawn_next klíčové slovo označuje vytvoření nástupce závitu (na rozdíl od dětských vláken, vytvořených potěr ), které provádí součet podprogram po čekání na pokračování proměnných x a y , které mají být vyplněny rekurzivní hovory. Základní případ a součet používají operaci send_argument (k, n) k nastavení jejich pokračovací proměnné k na hodnotu n , čímž účinně „vrací“ hodnotu do následného vlákna.

Vstupy

Dvě zbývající klíčová slova Cilk jsou o něco pokročilejší a týkají se použití vstupů . Obvykle, když je vytvořena procedura Cilk, může vrátit své výsledky do nadřazené procedury pouze tak, že tyto výsledky vložíte do proměnné v nadřazeném rámci, protože jsme v příkladu přiřadili výsledky našich vytvořených volání procedur v příkladu xa y.

Alternativou je použít přívod. Vstup je funkce interní pro Cilkovu proceduru, která zpracovává výsledky vyvolaného volání procedury při jejich návratu. Jedním z hlavních důvodů, proč používat vstupy, je to, že všechny vstupy procedury zaručeně fungují atomicky, pokud jde o sebe navzájem a nadřazenou proceduru, čímž se zabrání chybám, které by mohly nastat, pokud by se více návratových procedur pokusilo aktualizovat stejné proměnné v rodičovský snímek současně.

• inletKlíčových slov určuje funkci definovanou v rámci postupu jako vstup.
• abortKlíčové slovo může být použit pouze uvnitř vstupu; informuje plánovač, že jakékoli další procedury, které byly vytvořeny nadřazenou procedurou, lze bezpečně zrušit.

Když se z Cilk stal Cilk ++, byly odstraněny přívody a nejsou přítomny v Cilk Plus.

Paralelní smyčky

Cilk ++ přidal další konstrukci, paralelní smyčku, označenou cilk_for v Cilk Plus. Tyto smyčky vypadají

void loop(int *a, int n)
{
    #pragma cilk grainsize = 100  // optional
    cilk_for (int i = 0; i < n; i++) {
        a[i] = f(a[i]);
    }
}

To implementuje idiom paralelní mapy : tělo smyčky, zde volání f následované přiřazením k poli a , je provedeno pro každou hodnotu i od nuly do n v neurčitém pořadí. Volitelný „zrnitosti“ pragma určuje zhrubnutí : všechna dílčí pole sto nebo méně prvků je postupně zpracovávají. Ačkoli specifikace Cilk neurčuje přesné chování konstruktu, typickou implementací je rekurze rozděl a panuj, jako by programátor psal

static void recursion(int *a, int start, int end)
{
    if (end - start <= 100) {  // The 100 here is the grainsize.
        for (int i = start; i < end; i++) {
            a[i] = f(a[i]);
        }
    }
    else {
        int midpoint = start + (end - start) / 2;
        cilk_spawn recursion(a, start, midpoint);
        recursion(a, midpoint, end);
        cilk_sync;
    }
}

void loop(int *a, int n)
{
    recursion(a, 0, n);
}

Důvody pro generování programu rozděl a panuj, spíše než zjevná alternativa, smyčka, která vyvolá tělo smyčky jako funkci, spočívá jak v manipulaci s velikostí zrna, tak v efektivitě: dělat všechny tření v jediném úkolu způsobí načtení vyvažování úzkého místa.

Přehled různých paralelních smyček konstruktů na HPCwire zjištěno, že cilk_for konstrukt být docela obecně, ale poznamenat, že popis Cilk Plus ani stanoveno, že jeho iterace musí být údaje nezávislý, takže kompilátor nemůže automaticky vektorizovat si cilk_for smyčku. Přezkum také zaznamenal skutečnost, že redukce (např. Součty nad poli) vyžadují další kód.

Reduktory a hyperobjekty

Cilk ++ přidal druh objektů zvaných hyperobjekty , které umožňují více pramenům sdílet stav bez podmínek závodu a bez použití explicitních zámků. Každé vlákno má pohled na hyperobjekt, který může použít a aktualizovat; když se prameny synchronizují, pohledy se kombinují způsobem určeným programátorem.

Nejběžnějším typem hyperobjektu je reduktor, který odpovídá redukční klauzuli v OpenMP nebo algebraickému pojmu monoid . Každý reduktor má prvek identity a asociativní operaci, která kombinuje dvě hodnoty. Archetypální reduktor je součet čísel: prvek identity je nula a asociativní operace redukce vypočítá součet. Tento reduktor je zabudován do Cilk ++ a Cilk Plus:

// Compute ∑ foo(i) for i from 0 to N, in parallel.
cilk::reducer_opadd<float> result(0);
cilk_for (int i = 0; i < N; i++)
    result += foo(i);

K vytvoření propojených seznamů nebo řetězců lze použít další redukce a programátoři mohou definovat vlastní redukce.

Omezením hyperobjektů je to, že poskytují pouze omezenou rozhodnost . Burckhardt a kol. poukazují na to, že i redukce součtu může mít za následek nedeterministické chování, což ukazuje program, který může v závislosti na časovém pořadí vytvořit buď 1 nebo 2 :

void add1(cilk::reducer_opadd<int> &r) { r++; }
// ...
cilk::reducer_opadd<int> r(0);
cilk_spawn add1(r);
if (r == 0) { r++; }
cilk_sync;
output(r.get_value());

Pole notace

Intel Cilk Plus přidává notaci k vyjádření operací na vysoké úrovni na celých polích nebo částech polí ; např. funkce axpy - style, která je obvykle zapsána

 // y ← α x + y
 void axpy(int n, float alpha, const float *x, float *y)
 {
     for (int i = 0; i < n; i++) {
         y[i] += alpha * x[i];
     }
 }

lze v Cilk Plus vyjádřit jako

y[0:n] += alpha * x[0:n];

Tato notace pomáhá kompilátoru efektivně vektorizovat aplikaci. Intel Cilk Plus umožňuje paralelní použití operací C / C ++ na více prvků pole a také poskytuje sadu vestavěných funkcí, které lze použít k provedení vektorových posunů, otáčení a redukcí. Podobné funkce existují ve Fortranu 90 ; Cilk Plus se liší v tom, že nikdy nepřiděluje dočasná pole, takže využití paměti je snadnější předvídat.

Elementární funkce

V Cilk Plus je elementární funkce běžná funkce, kterou lze vyvolat buď na skalárních argumentech, nebo na paralelních prvcích pole. Jsou podobné funkcím jádra OpenCL .

#pragma simd

Tato pragma dává kompilátoru oprávnění vektorizovat smyčku i v případech, kdy by automatická vektorizace mohla selhat. Je to nejjednodušší způsob, jak ručně použít vektorizaci.

Krádež práce

Plánovač Cilk používá zásadu nazvanou „krádež práce“, aby efektivně rozdělil provádění procedur mezi více procesorů. Opět je nejjednodušší pochopit, když se nejprve podíváme na to, jak se Cilk kód provádí na jednom procesoru.

Procesor udržuje zásobník, na který umístí každý rámec, který musí pozastavit, aby mohl zpracovat volání procedury. Pokud provádí fib (2) a narazí na rekurzivní volání fib (1) , uloží stav fib (2) , včetně jeho proměnných a místa, kde kód pozastavil provádění, a umístí tento stav do zásobníku. Nebude pozastaven stav ze zásobníku a pokračovat v provádění, dokud nebude plně provedeno volání procedury, která způsobila pozastavení, a všechny procedury volané postupně touto procedurou.

S více procesory se věci samozřejmě mění. Každý procesor má stále zásobník pro ukládání rámců, jejichž provádění bylo pozastaveno; tyto komíny jsou však spíš jako dequesy , v nichž lze pozastavené stavy z obou konců odstranit. Procesor může stále odstraňovat pouze stavy ze svého vlastního zásobníku ze stejného konce, na který je staví; jakýkoli procesor, který právě nepracuje (dokončil svou vlastní práci nebo jí dosud nebyl přidělen žádný), si náhodně vybere jiný procesor prostřednictvím plánovače a pokusí se „ukrást“ práci z opačného konce jejich zásobníku - pozastavené stavy, které poté může krádežní procesor začít provádět. Státy, které jsou odcizeny, jsou stavy, ze kterých byl procesor ukraden, aby se dostali k poslednímu provedení.

Viz také

• Grand Central Dispatch
• Souběžné sbírky Intel (CnC)
• Intel Parallel Building Blocks (PBB)
  • Stavební bloky Intel Array (ArBB)
• Intel Parallel Studio
• NESL
• OpenMP
• Paralelní výpočty
• Síťový paralelní programovací systém C ++
• Závitové stavební bloky (TBB)
• Unified Parallel C.

Reference

externí odkazy

• Oficiální web pro Cilk Plus
• Web Cilk Project na MIT
• Arch D. Robison, „Cilk Plus: Podpora jazyků pro paralelní vlákna a vektory“ a „Paralelní programování s Cilk Plus“ , 16. července 2012.