Obsah
1. Programovací jazyk Julia: paralelní programování (pokračování)
3. Makro @parallel určené pro provedení paralelních výpočtů
5. Zásadní rozdíly mezi klasickou „sériovou“ smyčkou a paralelním výpočtem
6. Koncept koprogramů v programovacím jazyce Julia
9. Realizace jednoduchého producenta a konzumenta
10. Demonstrační příklad – generátor Fibonacciho posloupnosti
11. Předání parametru či parametrů do koprogramu
12. Složitější příklad – generátor geometrické řady
13. Použití většího množství producentů ve stejný okamžik
1. Programovací jazyk Julia: paralelní programování (pokračování)
Mezi další technologie nabízené programovacím jazykem Julia patří funkce vyššího řádu pmap(), velmi užitečné a snadno použitelné makro @parallel, které se v některých případech kombinuje s makrem @sync a v neposlední řadě taktéž koncept takzvaných koprogramů (coroutines). Dnes se s těmito technologiemi seznámíme s využitím několika demonstračních příkladů. Na těchto technologiích je zajímavé především to, že umožňují konstrukci i poměrně složitých paralelních algoritmů, a to bez nutnosti používat nízkoúrovňový přístup založený na vláknech, zámcích či semaforech.
2. Funkce pmap()
O funkci pmap() jsme se již zmínili ve třetí části tohoto seriálu, takže si jen ve stručnosti připomeňme, že se jedná o paralelní variantu funkce map, tedy o funkci vyššího řádu, která dokáže aplikovat jinou uživatelem zvolenou funkci na sekvenci či pole:
help?> pmap search: pmap promote_shape repmat typemax permutations SparseMatrix .. pmap(f, lsts...; err_retry=true, err_stop=false, pids=workers()) Transform collections ``lsts`` by applying ``f`` to each element in parallel. (Note that ``f`` must be made available to all worker processes) If ``nprocs() > 1``, the calling process will be dedicated to assigning tasks. All other available processes will be used as parallel workers, or on the processes specified by ``pids``.
Funkce pmap() dokáže provádět výpočty paralelně, což znamená, že se výpočty předají v daný okamžik volným workerům. Mezi jednu z podmínek, které je nutné splnit, patří to, že funkce, která se má předat dalším workerkům, v nich musí být dostupná (zjednodušeně řečeno – workery musí znát její zdrojový kód či bajtkód). Distribuci libovolné funkce mezi workery zajišťuje makro @everywhere:
help?> @everywhere @everywhere Execute an expression on all processes. Errors on any of the processes are collected into a CompositeException and thrown.
Ve třetí části jsme si otestovali paralelní výpočet Ackermannovy funkce, protože vyhodnocení této funkce je i přes její jednoduchý zápis poměrně zdlouhavé (a taktéž náročné na kapacitu zásobníku):
@everywhere(function ackermann(m,n)
if m == 0
return n + 1
elseif n == 0
return ackermann(m-1,1)
else
return ackermann(m-1,ackermann(m,n-1))
end
end)
Sériový výpočet hodnot Ackermannovy funkce pro parametry [4,1], [4,2], [4,3] a [4,4] bude vypadat takto:
map(x->ackermann(4,x), 1:4)
Po spuštění interpretru a čtyř workerů příkazem…
julia -p 4
…je již možné použít paralelní verzi funkce map:
pmap(x->ackermann(4,x), 1:4)
Pozor však na to, aby se při výpočtech nepřistupovalo ke sdíleným datům!
3. Makro @parallel určené pro provedení paralelních výpočtů
V mnoha výpočtech může být výhodnější použití makra nazvaného @parallel, které se zapisuje formou „paralelní“ smyčky. Zatímco se funkce pmap() používá spíše pro déletrvající a složité výpočty, je makro @paralell užitečné ve chvíli, kdy se má provést velký počet poměrně jednoduchých výpočtů (součet, vyhodnocení krátké funkce atd.) Zápis paralelní smyčky se v mnoha ohledech podobá zápisu klasické sériové smyčky:
help?> @parallel @parallel A parallel for loop. The specified range is partitioned and locally executed across all workers. In case an optional reducer function is specified, @parallel performs local reductions on each worker with a final reduction on the calling process.
Základní použití tohoto makra může vypadat následovně:
@parallel for i=1:100000
i*2
end
1-element Array{Any,1}:
RemoteRef{Channel{Any}}(1,1,14)
Povšimněte si, že se vrátil pouze objekt, s nímž jsme se již setkali předminule – vzdálená reference. Je tomu tak z toho důvodu, že makro @parallel spustí vzdálené výpočty a ihned skončí bez čekání na jejich dokončení. Pokud potřebujete počkat na dokončení, lze použít makro @sync, které již taktéž známe:
@sync @parallel for i=1:100000
i*2
end
4. Makro @parallel a reducery
Toto makra dokáže na paralelně vypočtený výsledek aplikovat takzvaný reducer, což je nějaká funkce používaná typicky ve funkci vyššího řádu reduce. Pokud například potřebujeme (v jednom procesu a vláknu) sečíst deset členů aritmetické řady, stačí použít:
julia> reduce(+, 1:10) 55
Připomeňme si, že + je obyčejná funkce, která se dá navíc zapsat jako operátor, což je ovšem jen syntaktický cukr.
Podobně lze vypočítat faktoriál šesti:
julia> reduce(*, 1:6) 720
Paralelní výpočet s reducerem vypadá odlišně:
@parallel (*) for i=1:6
i
end
720
Zde je nutné si uvědomit, že paralelně běží vlastně pouze výraz uvnitř smyčky, což je v tomto případě pouze vyhodnocení hodnoty proměnné. Samozřejmě ale výpočet může být složitější, například součet druhých mocnin hodnot jedna až deset:
@parallel (+) for i=1:10
i*i
end
385
Právě pro podobné účely – velmi jednoduché výpočty typu i*i – bylo makro @parallel vytvořeno.
5. Zásadní rozdíly mezi klasickou „sériovou“ smyčkou a paralelním výpočtem
Při použití makra @parallel je zapotřebí si dát pozor na to, že i když zápis vypadá podobně jako běžná programová smyčka, je zde zásadní technologický rozdíl – výpočty jsou spouštěny paralelně na nezávislých workerech, což mohou být buď samostatné procesy či dokonce procesy na odlišných počítačích (opět viz předminulou část seriálu). To znamená, že tyto workery nemají automatický přístup ke všem datům používaným na jiných workerech. Pokud se k datům pouze přistupuje v režimu čtení, není to tak velký problém:
a = obrovské_pole
@parallel (+) for i=1:100000
i*(a[i])
end
Ovšem při zápisu dochází k problémům, protože každý worker si vytvoří svoji kopii původního pole, ale zpětně nedojde k žádnému spojení výsledků (ostatně to by nebylo obecně možné):
a = zeros(100000)
@parallel for i=1:100000
a[i] = i
end
Podobné výpočty není vhodné s využitím @parallel realizovat.
6. Koncept koprogramů v programovacím jazyce Julia
V programovacím jazyku Julia je kromě podpory skutečných paralelně běžících výpočtů implementována i podpora pro takzvané koprogramy (coroutines). Koprogram je možné chápat jako zobecnění podprogramu, procedury, funkce či metody. Volání běžných podprogramů a návrat z nich je řízen s využitím zásobníku (stack), a to velmi jednoduše a na současných mikroprocesorech i poměrně efektivně – při každém volání podprogramu je adresa aktuálního místa, kde se výpočet nachází, uložena na zásobník a při ukončení podprogramu je tato adresa ze zásobníku vyjmuta a řízení se vrátí na (přesněji těsně za) místo, ve kterém byl podprogram, metoda či funkce volána.
To mj. znamená, že podprogram má jen jeden vstupní bod a při ukončení podprogramu se musí v případě potřeby podprogram opět zavolat od tohoto vstupního bodu (přerušený výpočet, například příkazem return či break, nelze po návratu z podprogramu dokončit), což odpovídá klasicky chápanému strukturovanému programování. Díky tomu, že jednou přerušený podprogram již není možné obnovit, může celá aplikace používat pouze jediný zásobník pro předávání parametrů i návratových hodnot (výjimkou jsou samozřejmě uzávěry, jejichž lokální proměnné nejsou ukládány na zásobník, ale na haldu – heap).
Naproti tomu v případě použití koprogramů je možné jednoduchým způsobem definovat libovolné množství vstupních bodů, které se mohou nacházet v jejich těle na prakticky libovolném místě (včetně a vlastně především vnitřních částí programových smyček). Činnost koprogramu lze v těchto bodech přerušit a vrátit řízení volajícímu programu, ovšem s tím, že se vnitřní stav koprogramu zachová a běh koprogramu tak lze od tohoto bodu znovu spustit (nespouští se tedy od svého začátku, ale od bodu, kde byl výpočet přerušen). Navíc je možné v těchto bodech předávat parametry jak z volajícího programu do koprogramu, tak i opačným směrem – toto předání parametrů je bezpečné (mohli bychom říci jazykem Javistů threadsafe, i když koprogramy nepoužívají vlákna operačního systému). V podstatě se jedná o jediný (a dostatečný) synchronizační mechanismus, který je při práci s koprogramy zapotřebí. Vzhledem k tomu, že je nutné uchovávat stav koprogramu i tehdy, když je jeho výpočet přerušen, musí mít koprogramy vlastní zásobník, který je v operační paměti alokován ve chvíli, kdy je koprogram vytvořen (o jeho dealokaci se typicky postará garbage collector).
7. Koprogramy versus vlákna
S využitím koprogramů je možné velmi jednoduše implementovat kooperativní multithreading, ovšem s tím omezením, že se ve skutečnosti nepoužívají vlákna (threads) operačního systému, protože volající program je při zavolání koprogramu pozastaven, aby mohl počkat na výsledek jeho běhu. To na jednu stranu zjednodušuje implementaci, na stranu druhou se nevyužívá všech možností moderních vícejádrových mikroprocesorů. Ovšem programátor může použít koprogramy ve chvíli, kdy potřebuje řídit takové výpočty, u nichž není zcela zřejmé, jak přesně má proběhnout jejich paralelizace (některé vlákno totiž může dokončit výpočet dříve než vlákna další).
Další možné použití koprogramů souvisí s problémy typu producent-konzument, což je téma, kterému se budeme podrobněji věnovat v navazujících kapitolách, protože jazyk Julia obsahuje několik funkcí a maker, které lze velmi jednoduše využít a aplikovat na úlohy typu producent-konzument. Specifickým příkladem využití koprogramů může být realizace generátorů, například generátor nějaké matematické řady, v případě potřeby i nekonečné (ve skutečnosti jsou koprogramy silnějším nástrojem než generátory).
8. Producenti a konzumenti
V jazyce Julia nalezneme dvě funkce, které jsou velmi užitečné právě při řešení úloh typu producent-konzument. Jména těchto funkcí si zapamatujete velmi jednoduše – produce() a consume(). První z těchto funkcí se používá v kódu producenta pro poskytnutí dat, druhá v kódu konzumenta pro přečtení dat:
help?> produce search: produce produce(value) Send the given value to the last consume call, switching to the consumer task. If the next consume call passes any values, they are returned by produce.
Zavolání funkce produce() daný koprogram (resp. dané vlákno) pozastaví a předá řízení konzumentovi, který musí někdy zavolat funkci consume() a přečíst si předaná data:
help?> consume search: consume TypeConstructor consume(task, values...) Receive the next value passed to produce by the specified task. Additional arguments may be passed, to be returned from the last produce call in the producer.
Důležité je, aby byl producent či konzument vytvořen formou koprogramu. Toho dosáhneme snadno, protože v programovacím jazyku Julia jsou koprogramy realizovány objekty typu Task, které „obalují“ funkci, která představuje tělo koprogramu. Pro vytvoření nového objektu typu Task použijeme následující konstruktor:
help?> Task search: Task task_local_storage @task istaskdone istaskstarted current_task Task(func) Create a Task (i.e. thread, or coroutine) to execute the given function (which must be callable with no arguments). The task exits when this function returns.
Řešení úlohy typu producent-konzument tedy může vypadat následovně:
- Producent je tvořen funkcí volající ve svém těle produce() s nějakou hodnotou.
- Producent běží ve vlastní úloze (Task).
- Ve chvíli, kdy se zavolá produce(), se přepne kontext na konzumenta.
- Konzument v programové smyčce načítá data z producenta funkcíconsume().
9. Realizace jednoduchého producenta a konzumenta
Funkce, která představuje producenta, může být velmi jednoduchá, například:
function test_producer()
produce("jedna")
produce("dva")
produce("tri")
end
Funkci musíme „obalit“ do úlohy:
julia> p=Task(test_producer) Task (runnable) @0x00007fd3bc7f4e20
Povšimněte si, že jsme se vrátili zpět do interaktivní smyčky REPL. Nyní již můžeme od producenta žádat jednotlivé hodnoty:
julia> consume(p) "jedna" julia> consume(p) "dva" julia> consume(p) "tri" julia> consume(p) () julia> consume(p) ()
Po získání třech hodnot ve skutečnosti producent skončil a vrací se prázdná sekvence (funkce consume v tomto případě neblokuje další výpočty).
Alternativně je možné postupně přečíst pouze hodnoty skutečně vytvářené producentem, a to následovně:
julia> p=Task(test_producer)
Task (runnable) @0x00007fd3bc7f4e20
for p in Task(test_producer)
println(p)
end
jedna
dva
tri
Na tomto příkladu je možné patrné, proč jsem se zmínil o tom, že generátory jsou speciálním případem koprogramů.
10. Demonstrační příklad – generátor Fibonacciho posloupnosti
Podívejme se nyní na příklad praktičtější úlohy typu producent-konzument. Producentem bude funkce, která postupně vytváří hodnoty patřící do Fibonacciho posloupnosti. Zajímavé je, že se vytváří nekonečná posloupnost (ve funkci je nekonečná smyčka), ovšem hodnoty se tvoří „na požádání“, tedy až jiný kód zavolá funkci consume(). Nemusíme se tedy bát, že se zaplní paměť nebo dojde k jiné nepříjemnosti – vše je řízeno konzumentem, pokud ten nebude volat consume() v nekonečné smyčce, bude producent jen čekat na přepnutí kontextu:
function fibonacci_producer()
x,y = (0,1)
while (true)
produce(y)
x,y=(y,x+y)
end
end
Dále vytvoříme objekt typu Task s producentem. Tím se vlastně z naší obyčejné funkce stane koprogram, který je ihned spuštěn a zastaví se na prvním výskytu produce():
p=Task(fibonacci_producer) Task (runnable) @0x00007fd3bc7f52d0
Nyní již můžeme v konzumentovi získávat generované hodnoty. Prvních deset prvků Fibonacciho posloupnosti se přečte takto:
for i = 1:10
println(consume(p))
end
1
1
2
3
5
8
13
21
34
55
11. Předání parametru či parametrů do koprogramu
Přímé vytvoření koprogramu s využitím konstruktoru Task s sebou přináší jeden problém – jak je možné předat producentovi parametry, když samotný konstruktor Task nic takového neumožňuje? (viz výše uvedený výpis z nápovědy). Řešení tohoto problému existuje hned několik, ovšem nejjednodušší je použití makra @task, které provede potřebné obalení konstruktoru:
help?> @task @task Wrap an expression in a Task without executing it, and return the Task. This only creates a task, and does not run it.
Volání makra @task vypadá následovně:
@task jméno_funkce_producenta(parametry)
Povšimněte si rozdílu oproti přímému volání konstruktoru Task:
Task(jméno_funkce_producenta)
12. Složitější příklad – generátor geometrické řady
Makro @task vyzkoušíme na dalším příkladu. Bude se jednat o generátor geometrické řady, přičemž při inicializaci tohoto generátoru určíme jak počáteční hodnotu (prvního prvku), tak i kvocient. Realizace je skutečně triviální, vlastně ještě jednodušší, než tomu bylo v případě Fibonacciho posloupnosti:
function geometric_sequence_producer(initial_value, common_ratio)
x=initial_value
while (true)
produce(x)
x=x*common_ratio
end
end
Vzhledem k tomu, že tato funkce vyžaduje dva parametry, použijeme pro vytvoření úlohy/koprogramu s producentem makro @task, a to následovně:
julia> p=@task geometric_sequence_producer(1, 2) Task (runnable) @0x00007fd3baf3daa0
Nyní již můžeme snadno získávat prvky této řady:
julia> for i=1:10
@printf("%2d: %10d\n", i, consume(p))
end
1: 1
2: 2
3: 4
4: 8
5: 16
6: 32
7: 64
8: 128
9: 256
10: 512
13. Použití většího množství producentů ve stejný okamžik
Povšimněte si, že samotná funkce, která popisuje chování producenta, si svůj stav pamatuje pouze v parametrech a lokálních proměnných. Nepřistupuje se k žádné globální proměnné ani se funkci nepředává žádný sdílený objekt:
function geometric_sequence_producer(initial_value, common_ratio)
x=initial_value
while (true)
produce(x)
x=x*common_ratio
end
end
To nám mj. umožňuje si vytvořit libovolné množství producentů, z nichž každý bude pracovat zcela nezávisle na ostatních producentech. Vytvořme si tedy tři producenty, každý pro generování odlišné geometrické řady:
julia> p1=@task geometric_sequence_producer(1, 2) Task (runnable) @0x00007fd3baf3daa0 julia> p2=@task geometric_sequence_producer(10, 1/2) Task (runnable) @0x00007fd3baf3ddc0 julia> p3=@task geometric_sequence_producer(3, 3) Task (runnable) @0x00007fd3baf3df50
Vyzkoušejme si nyní, že producenti skutečně pracují nezávisle na sobě:
for i=1:10
@printf("%2d: %10d %10.5f %10d\n", i, consume(p1), consume(p2), consume(p3))
end
1: 1 10.00000 3 2: 2 5.00000 9 3: 4 2.50000 27 4: 8 1.25000 81 5: 16 0.62500 243 6: 32 0.31250 729 7: 64 0.15625 2187 8: 128 0.07813 6561 9: 256 0.03906 19683 10: 512 0.01953 59049
14. Odkazy na Internetu
- Concurrency (computer science)
https://en.wikipedia.org/wiki/Category:Concurrency_%28computer_science%29 - Tasks (aka Coroutines) [Julia]
http://julia.readthedocs.io/en/latest/manual/control-flow/#man-tasks - Koprogram
https://cs.wikipedia.org/wiki/Koprogram - Coroutine
https://en.wikipedia.org/wiki/Coroutine - Coroutines in C
http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html - S-expression (Wikipedia)
https://en.wikipedia.org/wiki/S-expression - S-Expressions (Rosetta Code)
http://rosettacode.org/wiki/S-Expressions - Metaprogramming (Julia)
http://julia.readthedocs.io/en/latest/manual/metaprogramming/ - Introducing Julia/Metaprogramming
https://en.wikibooks.org/wiki/Introducing_Julia/Metaprogramming - Tutorial for the Common Lisp Loop Macro
http://www.ai.sri.com/pkarp/loop.html - Clojure Macro Tutorial (Part I, Getting the Compiler to Write Your Code For You)
http://www.learningclojure.com/2010/09/clojure-macro-tutorial-part-i-getting.html - Clojure Macro Tutorial (Part II: The Compiler Strikes Back)
http://www.learningclojure.com/2010/09/clojure-macro-tutorial-part-ii-compiler.html - Clojure Macro Tutorial (Part III: Syntax Quote)
http://www.learningclojure.com/2010/09/clojure-macro-tutorial-part-ii-syntax.html - Clojure Macros and Metaprogramming
http://clojure-doc.org/articles/language/macros.html - Tech behind Tech: Clojure Macros Simplified
http://techbehindtech.com/2010/09/28/clojure-macros-simplified/ - Fatvat – Exploring functional programming: Clojure Macros
http://www.fatvat.co.uk/2009/02/clojure-macros.html - CS 2101 Parallel Computing with Julia
https://www.coursehero.com/file/11508091/CS-2101-Parallel-Computing-with-Julia/ - Julia By Example
https://samuelcolvin.github.io/JuliaByExample/ - Tasks and Parallel Computing
http://docs.julialang.org/en/release-0.4/stdlib/parallel/ - clock(3) – Linux man page
http://linux.die.net/man/3/clock - rand_r(3) – Linux man page
http://linux.die.net/man/3/rand_r - atan2(3) – Linux man page
http://linux.die.net/man/3/atan2 - Calling C and Fortran Code
http://docs.julialang.org/en/release-0.4/manual/calling-c-and-fortran-code/?highlight=symbol - Array Programming
https://en.wikipedia.org/wiki/Array_programming - Discovering Array Languages
http://archive.vector.org.uk/art10008110 - no stinking loops – Kalothi
http://www.nsl.com/ - Vector (obsahuje odkazy na články, knihy a blogy o programovacích jazycích APL, J a K)
http://www.vector.org.uk/ - APL Interpreters
http://www.vector.org.uk/?area=interpreters - APL_(programming_language
http://en.wikipedia.org/wiki/APL_(programming_language - APL FAQ
http://www.faqs.org/faqs/apl-faq/ - APL FAQ (nejnovější verze)
http://home.earthlink.net/~swsirlin/apl.faq.html - A+
http://www.aplusdev.org/ - APLX
http://www.microapl.co.uk/ - FreeAPL
http://www.pyr.fi/apl/index.htm - J: a modern, high-level, general-purpose, high-performance programming language
http://www.jsoftware.com/ - K, Kdb: an APL derivative for Solaris, Linux, Windows
http://www.kx.com - openAPL (GPL)
http://sourceforge.net/projects/openapl - Parrot APL (GPL)
http://www.parrotcode.org/ - Learning J (Roger Stokes)
http://www.jsoftware.com/help/learning/contents.htm - Rosetta Code
http://rosettacode.org/wiki/Main_Page - Why APL
http://www.acm.org/sigapl/whyapl.htm - Introducing Julia/Functions
https://en.wikibooks.org/wiki/Introducing_Julia/Functions - Functions (Julia documentation)
http://docs.julialang.org/en/release-0.4/manual/functions/ - Evaluate binomial coefficients
http://rosettacode.org/wiki/Evaluate_binomial_coefficients - Ackermann function
http://rosettacode.org/wiki/Ackermann_function - Julia (front page)
http://julialang.org/ - Julia – dokumentace
http://docs.julialang.org/en/release-0.4/ - Julia – repositář na GitHubu
https://github.com/JuliaLang/julia - Julia (programming language)
https://en.wikipedia.org/wiki/Julia_%28programming_language%29 - IJulia
https://github.com/JuliaLang/IJulia.jl - Introducing Julia
https://en.wikibooks.org/wiki/Introducing_Julia - Julia: the REPL
https://en.wikibooks.org/wiki/Introducing_Julia/The_REPL - Month of Julia
https://github.com/DataWookie/MonthOfJulia - Learn X in Y minutes (where X=Julia)
https://learnxinyminutes.com/docs/julia/ - New Julia language seeks to be the C for scientists
http://www.infoworld.com/article/2616709/application-development/new-julia-language-seeks-to-be-the-c-for-scientists.html - Julia: A Fast Dynamic Language for Technical Computing
http://karpinski.org/publications/2012/julia-a-fast-dynamic-language - The LLVM Compiler Infrastructure
http://llvm.org/ - Julia: benchmarks
http://julialang.org/benchmarks/ - Type system
https://en.wikipedia.org/wiki/Type_system - Half-precision floating-point format
https://en.wikipedia.org/wiki/Half-precision_floating-point_format
ČLÁNKY DO MAILU