PARALELISMUS V DIFERENCIÁLNÍ EVOLUCI A JEJICH ADAPTIVNÍCH VARIANTÁCH

PARALELISMUS V DIFERENCIÁLNÍ EVOLUCI A JEJICH ADAPTIVNÍCH VARIANTÁCH Jiří Bůžek Ostravská univerzita v Ostravě Katedra informatiky a počítačů 30. dubna 22, 701 03 Ostrava

Abstrakt: Tato práce se zabývá řešením paralelizace diferenciální evoluce a jejich adaptivních variant. Na základě profilovací analýzy byl sestaven obecný návrh pro implementaci paralelismu v DE. Implementována byla klasická DE a její adaptivní varianty jDE, b6e6rl a JADE. Paralelní algoritmy byly porovnány s jejich neparalelními variantami na šesti testovacích funkcích. Výsledku testů ukázaly, že všechny paralelní implementace se zpracovávaly rychleji. Klíčová slova: Diferenciální evoluce, paralelismus

1

Úvod

Jediným způsobem jak urychlit zpracování již optimalizovaného algoritmu je jeho paralelizace. Zrychlení jde dosáhnout například paralelním zpracováním p operací jedné nadřazené operace nebo paralelním zpracováním p ekvivalentních operací na více nezávislých výpočetních jednotkách. Řešení obtížných problémů globální optimalizace nebo problémů vyšších dimenzí je často velmi časově náročné. Zavedením paralelismu v doméně algoritmů Diferenciální evoluce má za cíl tuto časovou náročnost zkrátit použitím vhodné dekompozice algoritmů na úrovni datových struktur, tak aby bylo souběžné zpracovávání operací co nejefektivnější. Cílem této práce je implementovat paralelní varianty algortimů DE/rand/1/bin [5], b6e6rl [8], jDE [1], JADE s externím archívem [10] a vyřešit problémy s nimi spojené. Hlavním rysem při postupu řešení této problematiky je použití návrhových vzorů a best practices (postupy osvědčené z praxe), aby uživatelům byly doručeny algoritmy řešící problém globální optimalizace, které budou moci reálně použít nebo volně modifikovat. Jednotlivé paralelní implementace v jazyce C# jsou porovnány oproti svým neparalelním variantám. Přepokladem je, že se průměrné hodnoty počtu vyhodnocení účelové funkce a spolehlivosti budou za stejných podmínek rovnat a zároveň potřebný čas k ukončení běhu algortimu u paralelních variant bude nižší.

2

Analýza a návrh

Nad dvěma běhy varianty DE/rand/1/bin pro všechny testovací funkce podle [9], (D = 10) byla provedena profilovací analýza měřící počty volání a časování jednotlivých metod algoritmu. Řídící parametry byly nastaveny jako Cr = 0.5 a F = 0.5. Cílem této analýzy bylo zjistit, které části algoritmu zabírají největší režii.

generování náhodného čísla vyhodnocení účelové funkce (úzká závislost na typu) přistupování k populaci (přístupy do paměti)

průměrná režie v % 57 11 8.5

std. dev 15 3 3

Tabulka 1: profilovací analýza Podle tabulky 1. je časově nejnáročnější generování náhodných čísel, v průměru se vykonává 57% celkového času. Druhá časově nejnáročnější je metoda vyhodnocení účelové funkce (11% celkového času), za ní jsou agregované metody pro přístup k jedincům populace (8.5%). V poměru celkový uběhlý čas vs. počet volání je jednoznačně nejnákladnější vyhodnocení účelové funkce. Další metody neměly takový význam, aby byly do tabulky zahrnuty. Důležité je zmínit, že průměrná režie vyhodnocení účelové funkce je velmi závislá na její složitosti, proto by výpočetně složitější funkce měla výrazný vliv na výsledky analýzy. Můžeme předpokládat, že tato pozorování budou podobná i pro adaptivní varianty DE. Protože se chceme vyhnout globálním synchronizacím přístupů (zápis a čtení) k proměnným pomocí jejich zamykání, které je velmi časově nákladné, a

protože jsou výše zmíněné metody zhuštěné v oblastech mutace, křížení a selekce, bylo navrženo, že generování zkusmých vektorů se bude provádět souběžně (paralelně) na nezávislých výpočetních jednotkách. Algoritmus 1: paralelní varianta DE generuj počáteční populaci Pi = (x1 , x2 , . . . , xN p ); while ukončovací podmínky do for i := 1 to Np do generuj vektor v mutací ; vytvoř vektor u křížením x a xi ; if f (u) ≤ f (xi ) then do T zařaď u; else do T zařaď xi ; end P := T ; end Zvýrazněný obdelník v algoritmu 1. označuje cyklus for, který bude zpracováván paralelně. Všechno co leží vně je zpracováváno hlavním vláknem. Generování zkusmého vektoru, v nemž jsou zahrnuty rutiny mutace a křížení, se provádí nezávisle paralelně, žádná synchronizace není potřebná. Tento návrh bude výchozím řešením pro paralelizaci adaptivních variant DE.

3

Generování pseudonáhodných čísel

Prvním významným problémem, kterému je nutno čelit při paralelizaci stochastických simulací, je generování pseudonáhodných čísel. Bez zamykání vnitřních proměnných instance generátoru náhodných čísel může současný přístup různých vláken zapříčinit poškození vnitřního stavu instance. Tato situace může způsobit vyvolání výjimky nebo snížit kvalitu generovaných čísel. To vše závisí na implementaci generátoru. U varianty DE/rand/1/bin se průměrně vygeneruje D+4 náhodných čísel na jedno vyhodnocení účelové funkce. Synchronizace přístupu (zápis do proměnných) k jedné instanci generátoru je pro tento obrovský počet vygenerovaných čísel velmi nevýhodná. Řešením tohoto problému může být vytvoření instancí generátorů pro každé jednotlivé vlákno zvlášť, inicializovaných odlišnými hodnotami. U takových generátorů ale není zaručeno, že sekvence náhodných čísel budou splňovať tyto dané podmínky: • vygenerovaná čísla musí být z rovnoměrného rozdělení, • mezi sekvencemi nesmí existovat jakákoliv korelace, • generátory splňují statistiké testy na náhodnost. Algorimus Mrg32k3a [2] navržený Pierem L’Ecuyerem s periodou délky p ≈ 2191 je schopen vytvořit instance jejichž stavy jsou o Z, Z = 2127 kroků vpřed před poslední vytvořenou instancí. Při vytváření nové instance se generátor překlopí do Z -tého stavu, vypočtením Z -té iterace své funkce vycházející ze stavu posledně vytvořené instance. Mezi dvěma po sobě vytvořenými instancemi leží sekvence 2127 náhodných čísel, která je nezávislá na sekvenci druhé instance. Tyto instance splňují podmínku nezávislosti a jejich periody jsou dostatečné dlouhé. Modifikace tohoto algoritmu je použita v paralelních implementacích variant DE. Při inicializaci algoritmů je každému vláknu přizazena jeho vlastní instance. Jako generátor pseudonáhodných čísel pro neparalelní varianty byl použit algoritmus Mersenne Twister [3] s periodou p ≈ 219937 − 1.

4

Implementace

Všechny varianty DE byly implementovány v programovacím jazyce C# , použitý framework .NET 4.5 v prostředí Visual Studio 2010. Problém vygenerování zkusmého vektoru, který leží mimo D, je v implemenacích vyřešen metodou zrdcadlení. Složka vektoru, která leží mimo D je překlopena zpátky do D. Pro paralelizaci cyklu for viz. kapitola Analýza a návrh, byla podle [7] použita metoda Parallel.For jmenného prostoru System.Threading.Task z knihovny Task Parallel Library (TPL). Metoda Parallel.For přijímá tři argumenty: dvě celá čísla reprezentující hranici od-do a referenci na funkci, která se bude provádět v jednotlivých iteracích. Vnitřně metoda dynamicky přiřazuje volným vláknům úlohu vygenerování zkusmého vektoru a rutinu selekce. Cyklus není rozdělen do pevných statických částí, což zvyšuje efektivitu paralelního zpracovávání, protože vykonání nevhodně rozdělených statických bloků podobné délky může různým jádrům trvat různou dobu.

Jiná spuštěná úloha s vyšší prioritou může přerušit a předběhnout vykonávání bloku (preempce u operačních systémů). U variant DE/rand/1/bin a jDE není problém s použitím vzoru z kapitoly Analýza a návrh. U variant b6e6rl a JADE s externím archívem se ale vyskytují problémy, které znesnadňují použití tohoto vzoru.

4.1

b6e6rl

Ve variantě b6e6rl se po události výběru úspěšné strategie provádí aktualizace H normalizovaných pravděpodobností, případně se provádí resetování na jejich výchozí hodnoty. Problémem je, že ve výchozí implementaci, souběžné generování zkusmých vektorů a rutina selekce způsobují současný přístup vláken k poli, v němž jsou uloženy hodnoty počtu výběrů strategií. Během inkrementování počtu výběrů jedné strategie současný přístup dvou a více vláken nastaví tuto proměnou na hodnotu, kterou nemůžeme jasně určit. Synchronizace přístupů k proměnným je v tomto případě nevýhodná, proto byl tento problém vyřešen přesunutím aktualizací pravděpodobností za paralelní cyklus For, tzn. aktualizace pravděpodobností bude provedena po každém vygenerování nové populace.

4.2

JADE

U varianty JADE je problémem existence externího archívu A. Přistupování k externímu archívu je nutno synchronizovat, nebo použít dynamickou datovou strukturu, která je vláknově bezpečná. Jako vhodná struktura podle [4] pro řešení implementace externího archívu byla vybrána struktura ConcurrentDictionary a to kvůli tomu, že scénář použití této struktury je velmi podobný s požadovanou implementací archívu. Implementace archívu vyžaduje mnoho čtení prvků a mnoho aktualizací nad prvky množiny archívu A. ConcurrentDictionary vyřešila daný problém, ale řešení zamykáním kritických bloků algoritmu přineslo mnohem lepší výsledky v podobě výrazného zrychlení. Zamykání archívu, proti vstupním a vystupním operacím, se provádí pří vybírání vektoru x ˜r2,g ze sjednocení množin P ∪A, za podmínky když náhodně vygenerovaný index r2 ukazuje do množiny archívu A. Další zamykání se provádí po události, kdy je vygenerován úspěšný zkusmý vektor a vektor staré populace xi je poté vkládán do A.

5

Experimentální testování

Podle [9] bylo všech osm implementovaných variant DE, paralelních a neparalelních, otestováno na šesti různých testovacích funkcích. Vstupní parametry byly nastaveny na doporučené hodnoty také podle [9]. Pro každou variantu bylo provedeno 100 opakování, za stejných podmínek Np = 60 a D = 30. U každé paralelní varianty je předpokladem, že spolehlivost a průměrné hodnoty počtu vyhodnocení účelové funkce budou podobné s hodnotami její neparalelní implementace.

5.1

DE/rand/1/bin

ackley dejong1 griewank rastrigin rosen schwefel

neparalení R 0 100 100 0 0 100

varianta nf e 600000 33679 47005 600000 600000 71898

paralení R 0 100 100 0 0 100

(a) výsledky testování

varianta nf e 600000 33245 47775 600000 600000 71213


neparalení varianta (čas v ms) 7105 344 666 6757 5567 803

paralení varianta (čas v ms) 3460 206 348 3684 3360 377

(b) průměrná délka trvání běhů algoritmu

Tabulka 2: DE/rand/1/bin Hodnoty počtu průměrných vyhodnocení účelové funkce nf e a spolehlivosti R se mezi paralelní a neparalelní variantou DE/rand/1/bin velmi podobají. Průměrná doba, za kterou se běh algoritmu ukončí, je pro všechny testovací funkce nejnižší u paralelní varianty.

5.2

jDE


neparalení varianta R nf e 100 72927 100 24487 99 32616 100 62144 99 44672 100 71898

paralení varianta R nf e 100 81544 100 25700 100 34426 99 63454 100 44740 100 71213






Tabulka 3: jDE Hodnoty počtu průměrných vyhodnocení účelové funkce nf e a spolehlivosti R se mezi paralelní a neparalelní variantou jDE podobají. Vyjímku tvoří testovací funkce ackley u níž je průměrný počet vyhodnocení účelové funkce paralelní varianty vyrazně vyšší než u neparalelní varianty. Průměrná doba, za kterou se běh algoritmu ukončí, je pro všechny testovací funkce nejnižší u paralelní varianty. Obě implementace fungují principiálně stejně, rozdíly mezi průměrnými počty vyhodnocení účelové funkce u testovací funkce ackley mohou být způsobeny použitím dvou různých generátorů náhodných čísel v závislosti na použitých vstupních parametrech. Pro kontrolu spávnosti výsledků bylo měření provedeno třikrát, naměřené hodnoty se výrazně nelišily.

5.3

b6e6rl


neparalení varianta nf e R 100 96100 100 40281 99 61096 100 78188 100 148219 100 66770







Tabulka 4: b6e6rl Hodnoty počtu průměrných vyhodnocení účelové funkce nf e a spolehlivosti R se mezi paralelní a neparalelní variantou b6e6rl velmi podobají. Průměrná doba, za kterou se běh algoritmu ukončí, je pro všechny testovací funkce nejnižší u paralelní varianty. Přesunutí metody aktualizace pravděpodobností výběru strategií nemělo významný na průměrný počet vyhodnocení účelové funkce.

5.4

JADE


neparalení varianta R nf e 100 73859 100 13284 89 22348 100 67408 97 77022 82 57168







Tabulka 5: JADE

Hodnoty počtu průměrných vyhodnocení účelové funkce nf e a spolehlivosti R se mezi paralelní a neparalelní variantou JADE velmi podobají. Průměrná doba, za kterou se běh algoritmu ukončí, je pro všechny testovací funkce nejnižší u paralelní varianty. Globální synchronizace čtení a zápisu prvků do externího archívu negativně neovlivnila počty vyhodnocení účelové funkce ani spolehlivost.

5.5

Shrnutí

Všechny implementace paralelních variant DE jsou časově méně naročnejší než jejich neparalelní varianty. Ve všech případech, kromě varianty jDE (testovací funkce ackley), jsou spolehlivost nalezení přijatelného řešení a počty vyhodnocení účelové funkce podobné. Testování algoritmů probíhalo na osobním počítači s 64-bit operačním systémem Windows 7 Professional, dvoujádrovým procesorem Intel Core i3 (4 logické jednotky), při průměrném 45% výtížení 4GB RAM paměti. Průměrné délky trvání běhů paralelních implementací jsou zhurba o polovinu kratší než délky trvání u neparalelních. Profilovací analýzou bylo zjištěno, že hruba 43% celkového času vykonávání algoritmu zabrala režie spojená s přiřazováním úloh vláknům a s voláním obslužných metod z jmenného prostoru System.Threading. Tyto systémové rutiny nemůže uživatel přímo ovlivnit. U varianty JADE se navíc v průměru 14% celkového času běhu algoritmu čekalo na uvolňování synchronizačních zámků nad množinou A. Z těchto důvodů nebylo dosaženo lepšího zrychlení.

6

Závěr

Bylo implementováno celkem osm algoritmů diferenciální evoluce. Všechny paralelní varianty se při experimentálním testování projevily jako rychlejší. Během práce se podařilo navrhnout funkční vzor pro paralelizaci existujících algoritmů DE a zároveň byly vyřešeny problémy globální synchronizace proměnných u variant b6e6rl a JADE. V této práci se autor nezabýval problémem False Sharing [6]. Při budoucím postupu by se měl tento problém, pokud se v implementacích vyskytuje, přednostně vyřešit. Implementované algoritmy by také měly být otestovány na širším spektru testovacích problémů. Zdrojové kódy algoritmů, dokumentace, API a příklady použití jsou dostupné volně ke stažení na adrese http://adaptivedenet.codeplex.com/.

Reference [1] Janez Brest, Saso Greiner, Borko Boskovic, Marjan Mernik, and Viljem Zumer. Self-adapting control parameters in differential evolution: A comparative study on numerical benchmark problems. Evolutionary Computation, IEEE Transactions on, 10(6):646–657, 2006. [2] Pierre L’ecuyer, Richard Simard, E Jack Chen, and W David Kelton. An object-oriented random-number package with many long streams and substreams. Operations Research, 50(6):1073–1075, 2002. [3] Makoto Matsumoto and Takuji Nishimura. Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation (TOMACS), 8(1):3–30, 1998. [4] Microsoft MSDN. When to use a thread-safe collection @ONLINE, December 2012. [5] Rainer Storn and Kenneth Price. Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization, 11(4):341–359, 1997. [6] Stephen Toub, Igor Ostrovsky, and Huseyin Yildiz. . net matters-false sharing. MSDN magazine, page 153, 2008. [7] Stephen Toub and Parallel Computing Platform. Patterns of parallel programming. Microsoft Corporation, 2010. [8] Josef Tvrdık. Self-adaptive variants of differential evolution with exponential crossover,. Analele of West University Timisoara, Series Mathematics-Informatics, 47:151–168, 2009. [9] Josef Tvrdík, Radka Poláková, Jiří Veselsk` y, and Petr Bujok. Adaptive variants of differential evolution: Towards control-parameter-free optimizers. In Handbook of Optimization, pages 423–449. Springer, 2013.

[10] Jingqiao Zhang and Arthur C Sanderson. Jade: adaptive differential evolution with optional external archive. Evolutionary Computation, IEEE Transactions on, 13(5):945–958, 2009.

PARALELISMUS V DIFERENCIÁLNÍ EVOLUCI A JEJICH ADAPTIVNÍCH VARIANTÁCH

Recommend Documents