Fortran a paralelní programování¶
Témata¶
OpenMP pro CPU
Autoparalelizace a vektorizace
OpenACC a OpenMP pro GPU
MPI
Coarray Fortran (CAF)
CUDA Fortran pro GPU
Python: Numba, f2py
Paralelizované knihovny numerických metod (BLAS a LAPACK, Intel MKL, CUDA knihovny, CULA, IMSL)
Amdahlův a Gustafsonův zákon¶
Smysl paralelizace, spočívající ve zrychlení počítačových úloh, a její limity kvantifikují následující dva tzv. zákony.
Amdahlův zákon udává celkové zrychlení \(S(n)\) úlohy, složené ze sériové a paralelní části, v závislosti na zrychlení \(s(n)\) samotné paralelní části; \(n\) značí počet procesorů. Zapíšeme čas běhu úlohy jako součet časů běhu sériové a paralelní části, \(T(n)=t_s+t_p(n)\), zavedeme poměr časů běhu paralelní části a celé úlohy \(p=t_p(1)/T(1)\) a zrychlení paralelní části \(s(n)=t_p(1)/t_p(n)\) a vypočteme \(p/s(n)=t_p(n)/T(1)\). Pak celkové zrychlení úlohy je
Obrázek \(S(n)\) pro vybraná \(p\) je na wikipedii. Při \(n\to\infty\) je i \(s(n)\to\infty\) a \(\displaystyle S(n)\to\frac1{1-p}\), tedy při \(p=0\) je \(S(n)=1\), při \(p=50\%\) konverguje \(S(n)\) ke \(2\), při \(p=90\%\) k \(10\) a při \(p=95\%\) k \(20\). Celkové zrychlení úlohy je i v limitě neomezených zdrojů omezené, Amdahlův zákon může působit pesimisticky.
Byl proto navržen jiný, prý realističtější Gustafsonův zákon, který zafixuje čas určený úloze (na rozdíl od Amdahlova zákona, který fixuje velikost úlohy) a stanoví zrychlení při \(n\) procesorech jako podíl vykonaných prací za daný čas, \(S(n)=W(n)/W(1)\). (Zrychlení podle Amdahla je podílem převrácených hodnot časů při dané práci.) Při podílu práce paralelní části na celkové práci definovaném jako \(p=W_p(1)/W(1)\) a zrychlení paralelní části \(s(n)=W_p(n)/W_p(1)\) můžeme psát pro celkovou práci složenou ze sériové a paralelní části pro 1 procesor \(W(1)=(1-p)W(1)+pW(1)\) a pro \(n\) procesorů \(W(n)=(1-p)W(1)+ps(n)W(1)\) a odtud
Při \(s(n)=n\) máme \(S(n)=1-p+np=n-(1-p)(n-1)\), čehož obrázek je opět na wiki. Gustafsonem definované zrychlení úlohy roste s počtem procesorů lineárně k nekonečnu, a to potěší více než Amdahlova limita.