Bariéry, paralelní součet prefixů

Bariéra

• místo v programu, kde se čeká až k němu dojdou všechny procesy (laicky řešeno)
• jde o synchronizační mechanismus
• zajistí, že všechny procesy dojdou do daného bodu, než se bude pokračovat dál
• řešíme pomocí sdíleného počítadla, kterého hodnotu zvýšíme vždy když daný proces dojde do místa bariéry; čekáme dokud hodnota počítadlo nebude rovna počtu procesů a poté můžeme pokračovat
  • $n$ … počet procesů
  • $count$ … počet procesů, které dorazili k bariéře
  • $passsed[i]$ … proces $i$ prošel bariérou
  • 
  • problém: takto implementovanou bariéru můžeme použít pouze jednou

Info

Fetch and add Složená atomická operace FA(var, num).

• var je proměnná a num číslo.
• Atomicky provede následující kroky: zjistí hodnotu val proměnné var, zvýší hodnotu var o num a vrátí hodnotu val.

# Implementace bariéry
FA(count, 1)
await count == n

Znovupoužitelná bariéry

• Máme 2 počítadla a “prohodíme” jejich roli
• 

(Paralelní) součet prefixů

• Vstupem je pole čísel
• Výstupem je taktéž pole čísel, kde v každém políčku je následující prvkem součtem předchozích políček

y_0​=x_0 \\​​ y_i=y_i−1+x_i \\ Pro \; i = 1, 2, ..., n -1 \end{gather}

Triviální přístup

• Triviálním přístupem získáme lineární časovou složitost ($n$)
  • 

Paralelní přístup

• Postupujeme v krocích, kdy na konci kroku máme nové pole a součty v daném kroku můžeme spustit paralelně
• Sčítáme od konce vždy 2 prvky se zvětšující se vzdáleností ($1,2,4,8,...$)
• Korektní výsledky ale dostavám od začátku až nakonec
• Stačí pokud provedem $\lceil lo{g}_2(n)\rceil$ kroků, kde $n$ je délka pole ⇒ časová složitost se zlepší na $lo{g}_2(n)$
• Pseudokód:
  • 
• Náčrtek:
  •