21.12.2016

foto Petr Bravenec

Petr Bravenec
+420 777 566 384
petr.bravenec@hobrasoft.cz

V minulém článku o paralelním programování jsem ukázal na jednoduchém příkladu, jak lze na vícejádrovém procesoru v C++ a Qt velice snadno a rychle zmenšit velikou spoustu obrázků na disku. Použil jsem k tomu prostředky, které mi pro paralelní výpočty nabízí knihovna Qt.

Na psaní článků podobných jako je tento je nejhorší vymýšlet nějaké smysluplné příklady. Zmenšování obrázků v předchozí části je příklad praktický, ale moje PC při zmenšování tisícovky obrázků ani nepoznalo, že se něco děje. Zrychlení o tři vteřiny není výsledek, kvůli kterému bych se chtěl učit paralelní programování.

Pro další příklad jsem vymyslel úkol mnohem praktičtější a vyžadující mnohem více výpočetního výkonu - výpočet čísla π metodou Monte Carlo.

Metoda Monte Carlo

Metoda Monte Carlo na Wikipedii

Metoda Monte Carlo patří mezi simulační výpočetní postupy. Dá se využít v aplikacích typicky ve dvou různých případech:

  • Nikdo neví, jak se dá zadaná úloha vyřešit, nebo je kompletní řešení příliš složité. U konkrétních návrhů řešení se však dá snadno rozhodnout, jestli takové řešení vyhovuje nebo nevyhovuje.
  • Řešení je jednoduché, ale vstupních dat je tak obrovské množství, že je nemožné propočítat všechna řešení a najít optimální řešení.

Výpočet čísla π metodou Monte Carlo je prvním případem - programátor implementující výpočet neví, jak lze číslo π vypočítat, ale dokáže velmi snadno rozhodnout, jestli nějaký bod leží uvnitř kružnice, nebo vně kružnice.

Příklad druhý - výpočet čísla π metodou Monte Carlo

Pro výpočet čísla π metodou Monte Carlo nepotřebujete ani počítač. Stačí papír, pravítko, kružítko, hrst máku a hodně, hodně trpělivosti při počítání zrníček.

Na papír s narýsovanou kružnicí a čtvercem nasypeme mák a spočítáme, kolik zrníček máku dopadlo do čtverce a kolik do kružnice. Z poměru počtu zrníček pak lze snadno vypočítat číslo π. Celý postup lze zamozřejmě s mnohem menší námahou a s větší přesností implementovat v počítači.

Obrázek kružnice

Parametrická rovnice jednotkové kružnice o poloměru 1 se středem [0,0] je

x² + y² = 1

Pro každý náhodný bod o souřadnicích [x,y] dokážeme rozhodnout, jestli leží uvnitř kružnice či vně. U každého bodu mohou nastat dva stavy:

x² + y² <= 1    // bod leží uvnitř kružnice

nebo

x² + y² > 1     // bod leží vně kružnice

Plocha kružnice je vyjádřena vzorcem:

Sk = π r²

Pro jednotkovou kružnici můžeme rovnou napsat

Sk = π 

Na obrázku je kružnice vepsaná do čtverce o straně 2 a ploše 4. Plocha čtverce na obrázku je

Sč = (2r)² = 2² = 4

Poměr ploch čtverce a kružnice je

x = Sk / Sč  =  4 / π

takže

π = 4 / x

Pokud budeme náhodně generovat body v intervalu od [-1,-1] do [1,1], budou některé body ležet uvnitř kružnice, ale všechny budou ležet uvnitř čtverce. Pro přibližný výpočet čísla π tak stačí vygenerovat dostatečný počet náhodných bodů, spočítat, kolik z nich leží uvnitř kružnice a spočítat z jejich vzájemného poměru číslo π. Celé si to lze zjednodušit a generovat pouze body v intervalu od [0,0] do [1,1], potom π vypočteme přímo z počtu jednotlivých bodů:

π = 4 * Nk / Nč

Výsledek bude samozřejmě jen přibližný a jeho použitelnost bude silně záviset na kvalitě generátoru náhodných čísel a na počtu bodů.

Vstupní data

Vstupními daty by mohly být rovnou náhodně vygenerované body. Takto naivní přístup má ale dvě proti:

  • Všechny náhodně vygenerované body by spotřebovaly velké množství paměti a to zcela zbytečně.
  • Generování náhodných bodů by probíhalo před samotným paralelním výpočtem, v jednovláknové části aplikace. Tím by se celý výpočet výrazně zpomalil.

Vypadá to, že vstupní data prostě nejsou potřeba. Něco ale musí řídit náš výpočet. K tomu může posloužit jednoduchý QList, na jehož hodnotách jednoduše nezáleží. Stačí vyrobit QList dostatečně veliký. Jelikož nevím, jak bych udělal dostatečně velký QList přímo, pomohl jsem si jeho postupným sčítáním až na velikost 1024 členů:

QList<double> data = QList<double>() << 0;
for (int i=0; i<10; i++) {
    data += data;
    }

Výpočetní funkce

Výpočetní funkce vygeneruje náhodné x a y a zjistí, jestli bod leží uvnitř kružnice. Celý postup se v cyklu opakuje a po dostatečném počtu opakování (zde 16384) výpočetní funkce vrátí poměr počtu vygenerovaných bodů a počtu bodů uvnitř kružnice. Tento poměr by se měl blížit k číslu π. Všimněte si, že funkce vrací výsledek - budeme s ním v dalším kroku pracovat.

Výpočetní funkce provádí 16384 výpočtů. Velikost množiny vstupních dat je 1024 členů. Celkově se tedy provádí výpočet 16 777 216 krát. Při podobných výpočtech je potřeba vhodně nastavit poměr počtu vstupních členů a počet výpočtů v jednom běhu map funkce. Velký počet vstupních dat vede vede k větší spotřebě paměti a pravděpodobně i k větší spotřebě strojového času potřebného pro řízení výpočtu. Velký počet výpočtů v jednom běhu map funkce zase může vést k příliš dlouhému běhu, což může zdržovat v případě, že se rozhodneme výpočet přerušit (ukážeme si v některém z dalších dílů).

double pi(int) {
    const int count = 16384;
    int incircle = 0;
    for (int i=0; i<count; i++) {
        double x=((double)rand()/(double)RAND_MAX);
        double y=((double)rand()/(double)RAND_MAX);
        if (x*x + y*y <= 1) {
            incircle += 1;
            }
        }
    return ((double)incircle) / ((double)count);
}

Redukční funkce

Po provedení map funkce nad celou vstupní množinou dat dostaneme seznam různých návrhů, jak by asi mohlo číslo π vypadat. Každá vypočtená hodnota se bude lišit. K našemu požadovanému výsledku by se mohl nejlépe přibližovat jejich průměr. Spočítat průměr z vypočtených hodnot je úkolem redukční funkce. Jde se na to trochu oklikou - redukční funkce spočítá pouze sumu všech návrhů, pro správný výsledek je nutné po redukci vydělit sumu počtem vstupních údajů.

void sum(double& sum, const double& pi) {
    sum += pi;
}

Spuštění paralelního výpočtu

double sumpi = QtConcurrent::blockingFilteredReduced (
    data,   // Vstupní data
    pi,     // Map funkce
    sum     // Reduce funkce
    );
double pi = 4.0 * sumpi / ((double)data.size());

Kompletní zdrojový tvar

#include <QtConcurrent>
#include <QDebug>

double pi(double) {
    const int count = 16384;
    int incircle = 0;
    for (int i=0; i<count; i++) {
        double x=((double)rand()/(double)RAND_MAX);
        double y=((double)rand()/(double)RAND_MAX);
        if (x*x + y*y <= 1) {
            incircle += 1;
            }
        }
    return ((double)incircle) / ((double)count) ;
}

void sum(double& sum, const double& pi) {
    sum += pi;
}

int main(int argc, char **argv) {
    QCoreApplication app(argc, argv);
    QList<double> data = QList<double>() << 0.0;
    for (int i=0; i<10; i++) {
        data += data;
        }

    double sumpi = QtConcurrent::blockingMappedReduced (data, pi, sum);
    double pi = 4.0 * sumpi / ((double)data.size());
    qDebug() << pi;
}

Výsledky

Tentokrát jsem se nezdržoval vyvíjením jednovláknové verze. Program provádí pouze matematické výpočty v procesoru, mělo by tedy stačit porovnat pouze spotřebovaný strojový čas a celkový čas potřebný pro běh programu:

time ./pi
3.14131

real    0m10.001s
user    0m13.769s
sys     1m0.080s

Celkově se spotřeboval strojový čas 73.849s, což hezky koresponduje s počtem jader, které se zúčastnily výpočtu (8 jader). Je až obdivuhodné, že procesor AMD FX-8350 dovede v tomto typu úlohy vytížit jádra tak dokonale - osm jader v procesoru má k dispozici pouze čtyři FPU výpočetní jednotky. Každá dvojice jader je zde ve stejné pozici, jako dva žáčci sedící v jedné lavici, dělící se společně o jednu kalkulačku.

Všimněte si spotřebovaného systémového času - předpokládám, že většina systémového času jde na vrub generování náhodných čísel. To je také jeden z důvodů, proč je potřeba přesunout generování náhodných čísel do paraleního výpočtu. Generování náhodných čísel zde zabere zhruba 6/7 veškerého strojového času. Pravděpodobně je to také příčina tak skvělého urychlení i přes to, že procesor disponuje pouze čtyřmi FPU - většina strojového času byla spotřebována na celočíselné výpočty, jádra se nemusela dělit o FPU a paralelní výpočet tak mohl jet na plné pecky.

Přesnost výsledku

Účelem tohoto článku je ukázat postupy při paralelním programování v Qt. Hodnocení přesnosti výpočtu čísla π je zde proto tak trochu navíc. Při několika spuštěních byly postupně vypočteny tyto hodnoty:
3.14131
3.142
3.14162
3.14176
3.14185
3.14148
3.14209

Je vidět, že metoda Monte Carlo dává pouze přibližné výsledky. Přesto se dá říci, že i takto jednoduchá metoda dokáže najít hodnotu čísla π s přibližně stejnou přesností, s jakou ji má v hlavě uloženu průměrný inženýr.

Význam metody Monte Carlo nespočívá v přesnosti - její význam spočívá v tom, že nám dokáže poskytnout alespoň přibližné výsledky v situacích, kdy je jiné řešení obtížné, nereálné či neznámé.

Odkazy

Závěr

Tento článek je jedním z několika článků o paralelním programování v Qt. Sledujte tyto stránky, sledujte náš Twitter. Další díly budou následovat.

Hobrasoft s.r.o. | Kontakt