Doted jsme pocitali jen na jednom jadru, v jednom threadu - ale moderni
procesory umoznuji paralelne vykonavat treba ctyri nebo osm threadu!
V idealnim pripade by nas program mel pocitat 8x rychleji - bohuzel
ovsem spoustu algoritmu neumime dobre paralelizovat, a i u tech ostatnich
paralelizujeme jenom cast programu - treba priprava a postprocessing dat
se casto paralelizuje spatne. Nebude to tedy tak idealni (vygooglete
si Amdahl's Law), presto ale se stestim dosahneme nekolikanasobneho
zrychleni.

(Co kdyz chceme distribuovat vypocet do velkeho clusteru? To je to, co
v dnesni dobe znamena "superpocitac", spoustu samostatnych pocitacu
propojenych mezi sebou rychlou siti a treba se sitovym filesystemem.
Na vedecke vypocty se pouziva obvykle framework MPI, ktery umoznuje
snadnou komunikaci mezi instancemi a synchronizaci datovych struktur.
Co se tyce konceptualniho navrhu dobre paralelizovatelnych a
distribuovatelnych algoritmu, poucne muze byt si neco precist
o "map-reduce" design patternu.)

Budeme predpokladat, ze dokazeme ulohu rozdelit takovym zpusobem, aby
na sobe thready byly vicemene nezavisle. Pokud spolu museji komunikovat
a koordinovat se mezi sebou, je treba pouzit nejaka synchronizacni
primitiva, ktere jsou nad ramec nasi prednasky - viz predmety
Programovani v UNIXu a Programovani v paralelnim prostredi. Pokud thready
jen sdileji nejakou datovou strukturu, mozna se pri jejim pristupu za
ruznych specialnich okolnosti nemuseji koordinovat a statci pouzit
atomicke instrukce.


Pro jednoduche programy je nejprimocarejsi cesta pomoci OpenMP,
maleho rozsireni jazyka C (a jinych) pro paralelizaci. Napr. mame-li
funkci foo(), muzeme ji zavolat vicekrat paralelne pomoci

	#pragma omp parallel
		foo();

Prelozit pak program musime s parametrem -fopenmp.

Treba iterace for-cyklu pak zparalelizujme jako

	#pragma omp parallel for
	for (int i = 0; i < 1000; i++)
		foo(i);

Zapisuji-li jednotlive iterace nejaka spolecna data tak, ze by mohlo
dochazet ke konfliktum, je nutne upravit konkretni rezim pro jednotlive
promenne, treba jako

	int sum = 0;
	#pragma omp parallel for reduce(+:sum)
	for (int i = 0; i < 1000; i++)
		sum += i;

Vsimnete si, ze nikde nespecifikujeme, kolik threadu ma vlastne
paralelne bezet. OpenMP runtime to zkousi na zaklade informaci od systemu
uhodnout sam, muzeme ale pocet threadu i rucne nastavit volanim funkce
nebo pomoci promenne prostredi. Detaily o OpenMP se doctete v jeho
specifikaci na http://openmp.org/, pro rychlou orientaci doporucuji
OpenMP Summary Card http://openmp.org/mp-documents/OpenMP3.1-CCard.pdf.


"Plnotucnou" metodou pro paralelizaci je pak v UNIXovem prostredi
pouziti knihovny pthreads. Ta nabizi funkci pro vytvareni threadu
(kazdy thread vykonava danou funkci), sbirani threadu, synchronizaci
atd. Tato metoda je vhodna v pripade, ze chceme mit nad thready
plnou kontrolu a praci mezi ne delime netrivialne. Na druhou stranu
je nutny overhead s vytvarenim a sberem threadu, ktery v malem
programu znamena docela dost "hlucheho" kodu, a rozdeleni prace
musime vzdy zajistit rucne.

Ekvivalent posledniho OpenMP cyklu se sumaci bude (kompilujte s -pthread):

#include <pthread.h>

#define MAXVAL 100000
#define THREADS 8

void *
sum_thread(void *arg)
{
	/* XXX: super-ugly metoda predavani cisla threadu, v praxi vsak
	 * hojne vyuzivana, neni-li potreba prenaset vetsi kontext */
        intptr_t thread_id = (intptr_t) arg;
        intptr_t sum = 0;

	/* Rozdeleni prace mezi thready. */
        int segment = MAXVAL / THREADS;
        int min = thread_id * segment;
        int max = (thread_id + 1) * segment;

        for (int j = min; j < max; j++)
                sum += j;

        printf("tid=%d [%d,%d] sum=%d\n", thread_id, min, max - 1, sum);
        return (void *) sum;
}

int main(void)
{
        int sum = 0;
        pthread_t pids[THREADS];

        for (intptr_t i = 0; i < THREADS; i++)
                pthread_create(&pids[i], NULL, sum_thread, (void*) i);

        for (int i = 0; i < THREADS; i++) {
                intptr_t sum1 = 0;
		/* Pocka na dobehnuti threadu a pak po nem uklidi. */
                pthread_join(pids[i], (void *) &sum1);
                sum += sum1;
        }

        printf("%d\n", sum);
}

nebo trochu cistsi:

#include <stdint.h>
#include <stdio.h>
#include <pthread.h>

#define MAXVAL 10000000
#define THREADS 8

void *
sum_thread(void *arg)
{
        uint64_t thread_id =*( (uint64_t*) arg);
        uint64_t *sum = arg;
        uint64_t sum_ = 0;
        
        uint64_t segment = MAXVAL / THREADS;
        uint64_t min = thread_id * segment;
        uint64_t max = (thread_id + 1) * segment;
        
        for (int j = min; j < max; j++)
                sum_ += j;

	*sum=sum_;    
        printf("tid=%llu [%llu,%llu] sum=%llu\n", thread_id, min, max - 1, *sum);
}       

int main(void)
{
        uint64_t sum = 0;
        pthread_t pids[THREADS];
        uint64_t sums[THREADS];
        
        for (uint64_t i = 0; i < THREADS; i++){
                sums[i]=i;
                pthread_create(&pids[i], NULL, sum_thread, &sums[i]);
        }       
       
        for (int i = 0; i < THREADS; i++) {
                pthread_join(pids[i], NULL);
                sum += sums[i];
        }

        printf("%llu\n", sum);
}