Závislost je špatná (pro váš program i pro váš hardware)

15. 1. 2017

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 8x ale tady uvádím jen 4x 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: