21.12.2016
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 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:
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.
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.
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ími daty by mohly být rovnou náhodně vygenerované body. Takto naivní přístup má ale dvě proti:
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 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);
}
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;
}
double sumpi = QtConcurrent::blockingFilteredReduced (
data, // Vstupní data
pi, // Map funkce
sum // Reduce funkce
);
double pi = 4.0 * sumpi / ((double)data.size());
#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;
}
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.
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é.
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.