funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

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

15. 1. 2017 — k47

Když jsem ne­dávno civěl do zdro­jáků knihovny breeze, na­ra­zil jsem na kód pro sla­kární součin, který vy­pa­dal 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­ři­krát odro­lo­va­nou (ve zdro­já­cích je to 8x ale tady uvádím jen 4x kvůli pro­storu):

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

Za­jí­mavé je, že součet se ne­pro­vádí do jedné pro­měnné, ale pa­ra­lelně do čtyř s tím, že na konci funkce se čás­tečné součty zkom­bi­nují.

Chvíli jsem dumal nad tím, proč je to na­psané zrovna takhle a pak mi došlo, že je to vlastně docela chytrá op­ti­ma­li­zace, která zkra­cuje řetězy zá­vis­lostí mezi jed­not­li­vými ope­ra­cemi a může tak vést k vět­šímu in­strukč­nímu pa­ra­le­lismu.

Když vezmu kód, který sčítá do jedné pro­mě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á­vis­losti mezi jed­not­li­vými ope­ra­cemi vy­pa­dají takhle:

Schéma uka­zuje dvě ite­race odro­lo­vané smyčky a je na něm jasně vidět řetěz sčí­tání, který musí být pro­ve­den sek­venčně. Wide issueout-of-order pro­ce­sory, které do­ká­žou od­ba­vit ně­ko­lik ne­zá­vis­lých ope­rací v jenom taktu, te­o­re­ticky můžou vy­ko­nat všechny čtyři ná­so­bení a i += 4 pa­ra­lelně. Součty však musí po­čí­tat sek­venčně.

Na­proti tomu verze s čás­teč­nými součty má tento graf zá­vis­lostí:

Jak je vidět, součty na sobě vzá­jemně ne­zá­visí a hard­ware je může pro­vést pa­ra­lelně, jakmile je před­chozí várka součtů hotová. A co víc, tento kód má jen jeden krok k plné vek­to­ri­zaci pomocí FMA in­strukcí.

Kom­pi­lá­tor tuto op­ti­ma­li­zaci ale nemůže pro­vést jen tak. Flo­a­ting point ope­race nejsou ko­mu­ta­tivní nebo aso­ci­a­tivní a když změním pořadí v jakém pro­vá­dím součty, do­stanu lehce od­lišný vý­sle­dek. V tomhle pří­padě to nevadí a ex­pli­citně pa­ra­lelní verze je tedy pre­fe­ro­vaná.

To je jen další pří­klad, že nej­lépe se pa­ra­le­li­zují ne­zá­vislé ope­race a platí to na všech úrov­ních – pro pa­ra­le­li­zaci na úrovni strojů, vláken nebo in­strukcí.


Dále k tématu:

@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články