Bariéra (počítačová věda) - Barrier (computer science)

v paralelní výpočty, a bariéra je typ synchronizace metoda. Bariéra pro skupinu vláken nebo procesů ve zdrojovém kódu znamená, že jakékoli vlákno / proces se musí v tomto bodě zastavit a nemůže pokračovat, dokud všechny ostatní vlákna / procesy nedosáhnou této bariéry.

Mnoho kolektivních rutin a paralelních jazyků založených na směrnicích klade implicitní překážky. Například paralela dělat zapojte se Fortran s OpenMP nebude povoleno pokračovat v žádném vlákně, dokud nebude dokončena poslední iterace. To v případě, že se program spoléhá na výsledek smyčky bezprostředně po jejím dokončení. v předávání zpráv, jakákoli globální komunikace (například redukce nebo rozptyl) může znamenat překážku.

Implementace

Základní bariéra má hlavně dvě proměnné, z nichž jedna zaznamenává stav povolení / zastavení bariéry, druhá udržuje celkový počet vláken, která do bariéry vstoupila. Stav bariéry byl inicializován tak, aby byl „zastaven“ prvními vlákny přicházejícími do bariéry. Kdykoli vlákno vstoupí, na základě počtu vláken již v bariéře, pouze pokud je to poslední, vlákno nastaví stav bariéry na „projít“, aby se všechna vlákna mohla dostat z bariéry. Na druhou stranu, když příchozí vlákno není poslední, je zachyceno v bariéře a neustále testuje, zda se stav bariéry změnil ze „zastavit“ na „projít“, a dostane se, až když se stav bariéry změní na "složit". Následující kód C ++ ukazuje tento postup.[1][2]

 1 struktur typ_ bariéry 2 { 3     // kolik procesorů vstoupilo do bariéry 4     // inicializace na 0 5     int come_counter; 6     // kolik procesorů tuto bariéru opustilo 7     // inicializovat na p 8     int leave_counter; 9     int vlajka;10     std::mutex zámek;11 };12 13 // bariéra pro p procesory14 prázdnota bariéra(typ_bariéry* b, int str)15 {16     b->zámek.zámek();17     -li (b->leave_counter == str)18     {19         -li (b->come_counter == 0) // žádná jiná vlákna v bariéře20         {21             b->vlajka = 0; // první příchozí smaže vlajku22         }23         jiný24         {25             b->zámek.odemknout();26             zatímco (b->leave_counter != str); // před vyčištěním počkejte, až všichni odejdou27             b->zámek.zámek();28             b->vlajka = 0; // první příchozí smaže vlajku29         }30     }31     b->come_counter++;32     int dorazil = b->come_counter;33     b->zámek.odemknout();34     -li (dorazil == str) // poslední příchozí nastaví příznak35     {36         b->come_counter = 0;37         b->leave_counter = 1;38         b->vlajka = 1;39     }40     jiný41     {42         zatímco (b->vlajka == 0); // čekání na vlajku43         b->zámek.zámek();44         b->leave_counter++;45         b->zámek.odemknout();46     }47 }

Potenciální problémy jsou následující:

  1. Když jsou implementovány sekvenční bariéry používající stejnou stavovou proměnnou pass / block, a zablokování se může stát v první bariéře, kdykoli vlákno dosáhne druhé a stále existují vlákna, která se nedostala z první bariéry.
  2. Vzhledem k tomu, že všechna vlákna opakovaně přistupují ke globální proměnné pro pass / stop, je komunikační provoz poměrně vysoký, což snižuje škálovatelnost.

Následující centralizovaná bariéra Sense-Reversal je navržena k vyřešení prvního problému. A druhý problém lze vyřešit přeskupením vláken a použitím víceúrovňové bariéry, např. Kombinace stromové bariéry. Také hardwarové implementace mohou mít výhodu vyšší škálovatelnost.

Centralizovaná bariéra pro smysl zvratu

Centralizovaná bariéra Sense-Reversal řeší potenciální problém zablokování vznikající při použití postupných bariér. Namísto použití stejné hodnoty k reprezentaci pass / stop používají sekvenční bariéry opačné hodnoty pro stav pass / stop. Například pokud bariéra 1 používá 0 k zastavení vláken, bariéra 2 použije 1 k zastavení vláken a bariéra 3 použije 0 k opětovnému zastavení vláken a tak dále.[3] Následující kód C ++ to ukazuje.[1][4][2]

 1 struktur typ_ bariéry 2 { 3     int čelit; // inicializace na 0 4     int vlajka; // inicializace na 0 5     std::mutex zámek; 6 }; 7  8 int local_sense = 0; // soukromé na procesor 9 10 // bariéra pro p procesory11 prázdnota bariéra(typ_ bariéry* b, int str)12 {13     local_sense = 1 - local_sense;14     b->zámek.zámek();15     b->čelit++;16     int dorazil = b->čelit;17     -li (dorazil == str) // poslední příchozí nastaví příznak18     {19         b->zámek.odemknout();20         b->čelit = 0;21         // paměťový plot, aby se zajistilo, že změna bude přepočítána22         // je vidět před změnou příznaku23         b->vlajka = local_sense;24     }25     jiný26     {27         b->zámek.odemknout();28         zatímco (b->vlajka != local_sense); // čekání na vlajku29     }30 }

Kombinace stromové bariéry

Combining Tree Barrier je hierarchický způsob implementace bariéry k vyřešení škálovatelnost vyhýbáním se případu, že se všechna vlákna točí na stejném místě.[3]

V bariéře k-Tree jsou všechna vlákna rovnoměrně rozdělena do podskupin k vláken a v těchto podskupinách se provádí synchronizace prvního kola. Jakmile všechny podskupiny provedou synchronizaci, první vlákno v každé podskupině přejde na druhou úroveň pro další synchronizaci. Na druhé úrovni, stejně jako na první úrovni, vlákna vytvářejí nové podskupiny vláken k a synchronizují se ve skupinách, přičemž posílají jedno vlákno v každé podskupině na další úroveň atd. Nakonec je v konečné úrovni synchronizována pouze jedna podskupina. Po synchronizaci na poslední úrovni se uvolňovací signál přenáší do vyšších úrovní a všechna vlákna se dostanou přes bariéru.[4][5]

Implementace hardwarové bariéry

Hardwarová bariéra používá hardware k implementaci výše uvedeného základního modelu bariéry.[1]

Nejjednodušší implementace hardwaru používá k přenosu signálu vyhrazené vodiče k implementaci bariéry. Tento vyhrazený vodič provádí operaci OR / AND, aby fungoval jako příznaky pass / block a čítač vláken. U malých systémů takový model funguje a rychlost komunikace není velkým problémem. Ve velkých víceprocesorových systémech může tato hardwarová konstrukce způsobit, že implementace bariéry bude mít vysokou latenci. Síťové připojení mezi procesory je jednou implementací ke snížení latence, což je analogické s Combining Tree Barrier.[6]

Viz také

Reference

  1. ^ A b C Solihin, Yan (01.01.2015). Základy paralelní vícejádrové architektury (1. vyd.). Chapman & Hall / CRC. ISBN  978-1482211184.
  2. ^ A b „Implementace bariér“. Univerzita Carnegie Mellon.
  3. ^ A b Culler, David (1998). Paralelní počítačová architektura, hardwarový / softwarový přístup. ISBN  978-1558603431.
  4. ^ A b Nanjegowda, Ramachandra; Hernandez, Oscar; Chapman, Barbara; Jin, Haoqiang H. (06.06.2009). Müller, Matthias S .; Supinski, Bronis R. de; Chapman, Barbara M. (eds.). Vývoj OpenMP ve věku extrémního paralelismu. Přednášky z informatiky. Springer Berlin Heidelberg. str.42 –52. doi:10.1007/978-3-642-02303-3_4. ISBN  9783642022845.
  5. ^ Nikolopoulos, Dimitrios S .; Papatheodorou, Theodore S. (01.01.1999). Kvantitativní architektonické vyhodnocení synchronizačních algoritmů a disciplín na systémech ccNUMA: Případ SGI Origin2000. Sborník ze 13. mezinárodní konference o superpočítačích. ICS '99. New York, NY, USA: ACM. 319–328. doi:10.1145/305138.305209. ISBN  978-1581131642.
  6. ^ N.R. Adiga a kol. Přehled superpočítače BlueGene / L. Sborník z konference o vysoce výkonných sítích a počítačích, 2002.

[1]

  1. ^ „Parallel Programming with Barrier Synchronization“. Březen 2012.