Tomas Oberhuber's Homepage

Efektivita větší než jedna

Při paralelizaci algoritmů se zavádí veličina známá jako efektivita. Ta teoreticky nemůže být větší než jedna, ale v praxi je možno takovéto hodnoty dosáhnout. Je v tom ovšem háček. Tento fenomén se vyskytuje zjednodušeně řečeno vždy při prohledávání stavového stromu do hloubky.

Například hledám-li nejkratší cestu v bludišti prohledáváním do hloubky s velkou maximální hloubkou hledání, některé (,,slepé“) větve procházím neúměrně dlouho. Teprve až když narazím na větev odpovídající cestě ven, můžu hloubku hledání snížit na hloubku této cesty a
prohledání zbývajících větví stromu se tak urychlí. Nyní takovéto hledání paralelizuji: za předpokladu, že mám tolik procesů, kolik vede z kořene stromu větví, můžu prohledáním každé jedné této větve pověřit jeden proces. Proces, kterému připadla nejkratší cesta, oznámí ostatním procesům, že můžou hloubku prohledávání snížit a i ostatní procesy skončí prohledávání v krátkém čase.

Problém je zde ovšem v tom, že při hledání nejkratší cesty je mnohem rychlejší prohledávání do šířky (kterému se paralelizované hledání do hloubky trochu přibližuje). Při paralelizaci prohledávání do šířky se efektivita nad 1 nedostane. I tak ale může být paralelizace přínosem – vzhledem k tomu, že prohledávání do šířky je náročné na paměť, a tak, v případě distribuované paměti, můžu díky paralelizaci dostupnou paměť zvětšit.

U šachů je problém podobný. Povaha minimaxu vyžaduje hledání do hloubky. Při použítí alfa-bety a paralelizace by se ovšem měl projevit ,,efekt hledání do šířky“ a alespoň v některých případech by měla být efektivita větší než jedna.

Implementace paralelního algoritmu

V nejjednodušší verzi paralelizace šachového programu předpokládám, že procesů je maximálně tolik, kolik je možných tahů z výchozí pozice. Každému procesu přidělím jeden nebo více tahů k prohledání. Všem procesům by mělo být známo s co největší aktuálností nejvyšší ohodnocení (parametr alfa) ze všech tahů, které všechny procesy zatím prohledaly. Čím lepší ohodnocení nejlepšího tahu, tím rychlejší prohledání tahů dalších. Tato implementace je velmi podobná případu s hledáním nejkatší cesty v bludišti, kdy místo nejlepšího ohodnocení tahu by všechny procesy znaly nejkratší dosud nalezenou cestu.

Výsledky

Paralelní verzi jsem zatím testoval jen při spuštění více procesů na jednom (jednojádrovém) procesoru. Za určitých zjednodušujících předpokladů můžu předpokládat, že efektivita paralelizace E > 1 právě když paralelní verze je při tomto spuštění rychlejší než sekvenční.Testoval jsem na 2 výchozích pozicích, kdy nejlepší tahy (bílý je na tahu ve výchozí pozici) vedou k výhře bílého
(matu) ve třech tazích (pěti “půltazích”), respektive po dvou tazích (třech “půltazích”). Testoval jsem s různou maximální hloubkou hledání ve stavovém stromu a s různým počtem spuštěných procesů. Uvádím výsledný čas výpočtu v sekundách:

Test: Bílý dává mat ve 2 tazích

Hloubka hledání = 4

Hloubka hledání = 5

Test: Bílý dává mat ve 3 tazích
Hloubka hledání = 6

Hloubka hledání = 7

Domovovská stránka projektu je zde.