Závislost je špatná (pro vaše programy i pro váš hardware)

Když jsem nedávno civěl do zdrojáků knihovny breeze, narazil jsem na kód pro slakární součin, který vypadal zhruba takhle:

double sum0, sum1, sum2, sum3 = 0.0;

// ...

for(int i = 0; i < length; i += 4) {
        sum0 += a[i+0] * b[i+0];
        sum1 += a[i+1] * b[i+1];
        sum2 += a[i+2] * b[i+2];
        sum3 += a[i+3] * b[i+3];
}

// ...

return sum0 + sum1 + sum2 + sum3;

Jde o tuto smyčku, čtyřikrát odrolovanou (ve zdrojácích je to 8× ale tady uvádím jen 4× kvůli prostoru):

double sum = 0.0;
for (int i = 0; i < length; i++) {
        sum += a[i] * b[i];
}

Zajímavé je, že součet se neprovádí do jedné proměnné, ale paralelně do čtyř s tím, že na konci funkce se částečné součty zkombinují.

Chvíli jsem dumal nad tím, proč je to napsané zrovna takhle a pak mi došlo, že je to vlastně docela chytrá optimalizace, která zkracuje řetězy závislostí mezi jednotlivými operacemi a může tak vést k většímu instrukčnímu paralelismu.

Když vezmu kód, který sčítá do jedné proměnné

double sum = 0.0;

for (int i = 0; i < length; i += 4) {
        sum += a[i+0] * b[i+0];
        sum += a[i+1] * b[i+1];
        sum += a[i+2] * b[i+2];
        sum += a[i+3] * b[i+3];
}

závislosti mezi jednotlivými operacemi vypadají takhle:

Schéma ukazuje dvě iterace odrolované smyčky a je na něm jasně vidět řetěz sčítání, který musí být proveden sekvenčně. Wide issue a out-of-order procesory, které dokážou odbavit několik nezávislých operací v jenom taktu, teoreticky můžou vykonat všechny čtyři násobení a i += 4 paralelně. Součty však musí počítat sekvenčně.

Naproti tomu verze s částečnými součty má tento graf závislostí:

Jak je vidět, součty na sobě vzájemně nezávisí a hardware je může provést paralelně, jakmile je předchozí várka součtů hotová. A co víc, tento kód má jen jeden krok k plné vektorizaci pomocí FMA instrukcí.

Kompilátor tuto optimalizaci ale nemůže provést jen tak. Floating point operace nejsou komutativní nebo asociativní a když změním pořadí v jakém provádím součty, dostanu lehce odlišný výsledek. V tomhle případě to nevadí a explicitně paralelní verze je tedy preferovaná.

To je jen další příklad, že nejlépe se paralelizují nezávislé operace a platí to na všech úrovních – pro paralelizaci na úrovni strojů, vláken nebo instrukcí.


Dále k tématu:

Flattr this!

This entry was posted in CPU. Bookmark the permalink.

2 Responses to Závislost je špatná (pro vaše programy i pro váš hardware)

  1. v6ak says:

    Nekomutativita floating point sčítání – tady jde IMHO pouze o chybějící asociativitu. Pokud to skutečně není komutativní, pak existují x a y takové, že x+y ≠ y + x. Což IMHO ani podle IEEE 754 není pravda. Operace není asociativní, což znamená, že existují x, y a z taková, že (x+y)+z ≠ x+(y+z), což kvůli zaokrouhlování existují.

    Odkázaný test odhaluje jen to, že komutativita nebo asociativita nesedí. Už ale neříká, co nesedí. V rámci komutativity mohu z a+(b+(c+(d+…))) udělat třeba (b+(c+(d+…))) + a, případně mohu upravovat vnitřek závorky, ale už se mi proměnná a nedostane nikam doprostřed výrazu (což shuffle klidně udělá). Na to bychom už potřebovali například asociativitu.

    Na druhou stranu, právě asociativita je to, co pro jednoduchou paralelizaci potřebujeme. Komutativitu nepotřebujeme, aspoň ne nutně, i když se někdy hodí.

Leave a Reply

Your email address will not be published. Required fields are marked *