Závislost je špatná (pro váš program 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 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: