Špatný program ani výkonný procesor nespraví

Ve škole jsme dostali úkol, naprogramovat násobení matic pomocí 3 cyklů, které poté provádíme v různém pořadí s paralelizací. Výsledky mě natolik překvapily, že jsem se rozhodl o nich napsat článek.

Tento příklad je trochu specifický, ale i při programování běžných algoritmů může špatný návrh systém značně zpomalit. Minimálně dobře ilustruje rychlost paměti v PC, která může za všechna zpomalení.

Výměna zanoření cyklů

Násobení matic je napsáno pomocí 3 zanořených cyklů s obtížností O(n³). Samozřejmě existují i rychlejší metody, zde ale šlo o něco jiného. Protože na pořadí nezáleží, klidně se cyklus mezi sebou mohou prohazovat, na výsledek to vliv mít nebude. Na rychlost výpočtu ale ano. Paralelizaci je vytvořena pomocí knihovny OpenMP která zpracovává preprocesorem #pragma omp direktivy.

int **m1, **m2, **resultMat;

#pragma omp parallel for
for (int row = 0; row < matrix_size; row++) {
    for (int col = 0; col < matrix_size; col++) {
        for (int pos = 0; pos < matrix_size; pos++) {
            resultMat[row][col] += m1[row][pos] * m2[pos][col];
        }
    }
}

Knihovně OpenMP lze také nastavit, kolik vláken má být použito. Proto tabulka obsahuje výsledky s 1, 2 a 8 vlákny a na procesoru se 2 fyzickými jádry, tak na procesoru se 2 fyzickými ale 4 logickými jádry. V obou případech násobené matice byly čtvercové o 1500 řádcích i sloupcích.

Důvod velkých rozdílů v hodnotách

V tabulce lze vidět, že pro různá pořadí cyklů jsou opravu značně rozdílné výsledky. Bez paralelizace mohlo dojít až k 10x zpomalení pokud jsme pořadí cyklu měli col_pos_row (vnějším cyklus prochází sloupce, prostřední pozici v řádku/sloupci a vnitřní cyklus řádky) vs. row_pos_col. Velmi podobné výsledky ale nastanou i při 8 paralelních vláknech.

Obrovské rozdíly mezi výsledky jsou způsobeny jednoduše pomalou pamětí RAM. Protože sekvenční přístup do paměti (čtení bloků jdoucích po sobě) je rychlejší než náhodné přístupy. Proto některé uskupení cyklů způsobní velké zpomalení/zrychlení než jiné.

Tímto problémem se běžně programátoři pracující na HPC zabývají. Ale i běžný programátor například v Javě si může vybrat, použije-li ArrayList (sekvenční přístup), nebo LinkedList (náhodný přístup).

Více vláken to může pěkně pokazit

Ve výsledcích jde vidět ještě jeden fakt. Pokud spouštíme více vláken, než je jader CPU, může dojít ke zpomalení. Proč? Protože vlákna na sebe čekají aby se přepla, a režije spojená s vlákny to celé trochu brzdí. 

---

Dnešní teoretickou hodinku bych zakončil, stačí to brát pouze jako menší osvětu. Já se prostě musel podělit o mé překvapení.