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

Ukázka kódu, ve které jednoduchá modifikace způsobila až 10-ti násobné zrychlení. Výpočet byl porovnán jak v jednovláknové tak vícevláknové aplikaci pomocí OpenMP v C++.

Š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(n3). 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.

Výsledky paralelního násobení matic

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í.

Přidat komentář

Právě odpovídáte na existující komentář. Zrušit

Komentáře

Michal Tichopad

14.11.2016 09:27

V rámci kterého předmětu to bylo? A v jakém kontextu?

Odpovědět

Pavel

http://www.kutac.cz/blog/ 14.11.2016 09:47

Paradigmata programování. No kontext.. Jednoduše jsme si ukazovali OpenMP, a protože jsme to nestihli celé, dostali jsme toto jako úkol. Další hodinu jsme brali zase něco jiného, konkrétně MPI. Byl to jen rychlý úvod :D

Novinky z blogu

LocalStorage a Lockr

Ukládání dat v prohlížeči pomocí LocalStorage má své úskalí. Od toho je tady mini knihovna, která tyto problémy řeší a hodně práci hodně...

Další články