Využití dual-core procesoru při řešení časově náročných šachových úloh

(Dual core processor and solving of chess problems)

(Vaclav Kotesovec, 14.8.2007)

Summary:
  • Question: What is better? (for solving of two chess problems)
  • 1) run one program (Alybadix or Popeye) sequentially, use only one processor, but with full memory RAM
  • 2) run two programs simultaneously (Alybadix/Alybadix or Popeye/Alybadix or Popeye/Popeye), but each with only half of memory RAM
  • Answer: Two parallel programs using 100% of CPUs power are faster! Average acceleration is 1.5x (see also graphs).

    Je třeba předeslat, že tento článek se týká případu, kdy máme k testování sérii několika časově náročných šachových úloh (na desítky až stovky hodin počítačového času) a chceme co nejefektivněji počítačem přezkoušet více úloh. V případě jedné úlohy je samozřejmě nejlepší ji přidělit co nejvíce paměti a je jedno, zda ji řešíme jednojádrovým nebo dvoujádrovým procesorem, časy budou shodné. U mě je však situace taková, že mám stále ve frontě k přezkoušení více úloh a potřeba úspory času se jeví jako zásadní. Někdy se dají vhodným způsobem testování ušetřit desítky hodin.

    Závislost času řešení na velikosti paměti

    U počítače s dual-core procesorem (což je procesor se dvěma jádry) jsem řešil problém, zda je časově lepší
  • 1) spustit jeden program (Popeye, Alybadix, atd.), který bude mít k dispozici celou (volnou) paměť RAM, tj. řešit úlohy jednu za druhou sekvenčně.
    nebo
  • 2) využít na 100% kapacitu CPU dual core procesoru a spustit vedle sebe paralelně dva programy, přičemž ale každý z nich bude mít k dispozici v tomto případě pouze polovinu paměti RAM.

    U starších programů (typu VKSACH), které vystačily s 1 MB RAM, je odpověď na tuto otázku jednoznačná. Spuštění dvou programů paralelně bude 2x rychlejší. Jelikož ale modernější programy vydatně využívají tzv. hashování (kdy si program pamatuje část pozic, které již probíral v průběhu řešení), je čas řešení u těchto programů výrazně závislý na dostupné paměti RAM. Čím je této paměti více, tím se čas řešení zkracuje, tato závislost však (na rozdíl od výkonu CPU) není lineární. Otázkou nyní je, když programu zmenšíme paměť RAM na polovinu, o kolik bude pomalejší řešení. Naštěstí je to méně než 2x a díky tomu je možno naplno využít výkon dual-core procesorů!


    Tento graf ukazuje pro program Popeye závislost celkového času řešení na velikosti paměti RAM (používané pro hashování). Další grafy (také pro Alybadix) a vysvětlení některých pojmů je možno nalézt v mém článku z roku 2003 (see also) Hashing and pruning.

    Pro zvolenou úlohu (jeden h=5 s hodně kameny) by zde stačila paměť 724 MB RAM. Je vidět, že čas řešení s větší pamětí zůstává pak už stejný. Abychom mohli porovnávat různé programy a úlohy podle stejných měřítek, označme tuto paměť jako "potřebnou paměť" (necessary memory). Podle ní pak budeme normalizovat všechny hodnoty. Velmi často je "potřebná paměť" mnohem větší než celková dostupná fyzická paměť RAM.

    V následujícím grafu představuje osa x poměr: dostupná paměť RAM / potřebná paměť (v procentech). Např. 20% znamená, že při paměti RAM 1 GB by program potřeboval nejméně 5 GB na to, aby nemusel dělat žádný "pruning" (uvolnění části paměti po jejím zaplnění - Alybadix např. uvolňuje vždy 3/4 této paměti, 1/4 ponechává).
    Na ose y je příslušné zpomalení při poloviční paměti (tedy poměr časů tmem(x / 2) / tmem(x)). Případ, kdy je potřebná paměť pouze 1-2x větší než fyzická paměť RAM, není příliš zajímavý, takové řešení je velmi krátké (k zaplnění celé fyzické paměti RAM dojde obvykle už za pár minut). Nás nejvíce zajímají časově velmi náročné úlohy, jejichž kompletní přezkoušení trvají desítky až stovky hodin. Zde je potřebná paměť mnohem větší než fyzická paměť RAM a k pruningu dochází řádově sto i vícekrát. Tento případ odpovídá v grafu hodnotám blízko nule na ose x. Zde se stává vliv dostupné poloviny paměti RAM relativně menší a to tím víc, čím více "pruningů" je nutno provést (v limitě do nekonečna by byly oba časy řešení - s plnou i poloviční pamětí - shodné)

    Most interesting are values near zero (situation for very hard chess problems). Average slowdown is in this case only 1.3x, average acceleration is (1 + 1) / 1.3 ~ 1.5x

    Z grafu vidíme, že hodnota zpomalení pro poloviční paměť RAM nepřekročí hodnotu 2. Pokud tedy necháme běžet vedle sebe 2 programy, dosáhneme v součtu lepší čas. Situaci velmi časově náročných šachových úloh odpovídají v grafu hodnoty blízko nuly na ose x. Vidíme, že zpomalení se pohybuje v rozmezí 1.2 - 1.4 x (a je stabilnější v případě Alybadixu, Popeye se chovají "volatilněji"). Pokud budeme uvažovat průměrnou hodnotu zpomalení při poloviční paměti přibližně 1.3 x, vychází nám, že např. v případě dvou úloh, která by každá trvala 100 hodin strojového času, celkový čas při sériovém spuštění (nejdříve jedna, pak druhá) s plnou pamětí 100 + 100 = 200 hodin, v případě paralelního spuštění (oba programy současně) s poloviční pamětí čas 130 + 130 hodin, což v tomto případě ale není 260 hodin, ale stále jen 130 hodin, protože řešení obou úloh běželo paralelně. Dosáhli jsme tedy úspory cca (200 - 130) / 200 = 35% času. Nebo jinak, průměrné zrychlení je 200 / 130 ~ 1.5x. Tyto hodnoty mohou mít dost značný rozptyl podle jednotlivých úloh.

    Výsledky testů ukazují, že poloviční paměť sice řešení úloh trochu zpomalí, toto zpomalení není ale až tak výrazné a v případě dvou paralelně běžících programů dosáhneme v součtu lepšího času než pokud by oba programy běžely s celou pamětí sekvenčně za sebou.

    Režimy práce

    Při vlastním testování šachových úloh (nebo obecně spouštění i jiných časově náročných programů) je třeba rozlišit 2 režimy práce:
  • 1) je potřeba počítač dále používat i pro jiné věci (editování, poštu, prohlížení internetu, atd.). V tomto případě je nejlepší spustit pouze jeden řešící program (Alybadix, Popeye, ...) a zbytek kapacity dual-core procesoru využívat právě pro tyto činnosti. Mám vyzkoušeno, že řešení v tomto případě nijak nezdržuje jinou práci. Řešícímu programu doporučuji přidělit 70-80% paměti RAM a zbytek nechat systému a pro jiné činnosti. Např. u systému s 2GB RAM přiděluji šachovým programům 1600 MB RAM (v případě programu Popeye se to zadá parametrem "-maxmem 1600M").
  • 2) pokud na počítači nebudu delší dobu pracovat (spuštění přes noc, před odjezdem na dovolenou apod.) je situace jiná. V tu chvíli je třeba maximálně využít veškerý výkon počítače a pokud máme ve frontě více úloh k řešeni, doporučuji spustit 2 tasky paralelně (Alybadix/Alybadix nebo Popeye/Alybadix nebo Popeye/Popeye), každý s poloviční pamětí RAM (tak jak je popsáno výše).

    Porovnání programů podle operačních systémů

    Řešení Alybadixem je na jednojádrovém procesoru samozřejmě nejefektivnější pod DOSem, kde se zbytečně neztrácí čas režií systému Windows a plně se využije úplně celá paměť počítače. Co platilo pro jednojádrový procesor, nemusí už ale platit pro dvoujádrový. Pod DOSem se totiž nevyužije dvoujádrový procesor vůbec (jede pouze 1 z jader). Řešení pod DOSem bude tedy na dual-core procesoru i nadále nejrychlejší možností pouze v tom případě, pokud máme k řešení v danou chvíli pouze jednu šachovou úlohu a pokud počítač už k ničemu dalšímu nepotřebujeme.
    Pro Popeye již neexistuje verze, která by pod DOSem podporovala celou paměť, takže zde je spuštění pod Windows (nebo Linuxem) jedinou možností.

    Jak na výpadky napájení

    Další poznámky se týkají zajištění toho, aby se v případě výpadku napájení zachránilo aspoň to, co se do té doby vyřešilo a nebylo nutné (např. po návratu z dovolené) po takovém výpadku řešit vše znova.
    Hardwarově se tomu dá pomoct napájením počítače z UPS (nepřerušitelný zdroj napájení). UPSka vydrží napájet počítač při výpadku napájení (podle kapacity akumulátorů) obvykle několik minut. Tím se mohou překlenout krátkodobé výpadky v síti. Pro případ delšího výpadku je možné propojit UPS s počítačem sériovou linkou. UPSka potom vyšle při výpadku směrem do počítače informaci, že došlo k výpadku a kolik minut je schopna ještě počítač napájet. Při vhodném nastavení systému v menu "nastavení", "ovládací panely", "možnosti napájení", se dá zvolit, že v tomto případě dojde k hibernaci (přechodu do tzv. "režimu spánku"). Počítač uloží aktuální stav a celou paměť na disk (trvá cca 1 minutu podle velikosti paměti RAM) a po novém zapnutí pak pokračuje v činnosti od místa kde skončil. Toto zapnutí je bohužel (bez dalšího přídavného hardwaru) nutno udělat ručně, ale aspoň není ztraceno předchozí řešení do výpadku napájení. Při pokračování řešení může být v tomto případě problém pouze s čítačem spotřebovaného času (může být započtena i doba, kdy byl počítač hibernován).

    U některých typů šachových úloh je možno rozložit řešení do několik subúloh, např. provedením vždy prvního tahu a řešením série úloh o 1 tah kratších. Toto umožní, že při výpadku napájení bude uloženo řešení aspoň některých subúloh a bude třeba dořešit jen zbylé subúlohy. Má to však několik háčků. Příprava takových pozic je poměrně pracná. Navíc u programů využívajících hashovacích tabulek může být celkový čas řešení těchto subúloh podstatně delší než řešení původní (o 1 tah delší) úlohy, protože program musí tyto tabulky generovat pro každou subúlohu znovu a nemůže použít část již vypočítaných hodnot. Proto tuto metodu rozdělování úloh na subúlohy spíše nedoporučuji, ve speciálních případech ji přesto lze použít. Např. pokud je jediný možný první tah v pomocném matu nebo v sériovotahové úloze pouze proměna jediného pěšce, lze ji rozdělit na 4 podúlohy bez časové ztráty při řešení.

    Pár zajímavých tipů

    Na konec ještě několik drobných vylepšení, jak být v nepřítomnosti (třeba o dovolené) stále informován o stavu počítače.

  • Pokud máme internetové připojení na obou místech (např. doma, kde běží počítač přes modem a na dovolené z notebooku bezdrátově), existuje možnost nainstalovat na obou počítačích program, který umožňuje dálkové ovládání počítače přes internet (např. VNC - Virtual Network Computing). Po připojení vidím v okně na svém počítači desktop vzdáleného počítače a mohu jej na dálku ovládat. Toto není science fiction, již před několika lety jsem to právě s programem VNC testoval a chodilo to téměř v reálném čase.
    Spíše ale doporučuji bez obsluhy doma běžící počítač od internetu po dobu dovolené odpojit, aby byl ušetřen případnému napadení hackery...

  • Nedávno jsem ještě objevil pěknou možnost v programu SnagIt (verze 8). Tento program umí sejmout stav obrazovky (udělat tzv. screenshot) a uložit ho do souboru. To je celkem běžná věc (provede se 1x po stisku nějaké kombinace kláves). SnagIt ale umí udělat také periodickou kopii obrazovky ve zvoleném časovém intervalu (třeba 1x za hodinu). Nastaví se v menu "Tools", "Timer Setup" pomocí "Enable timer-activated capture" (před tím je nutno ještě nastavit "Output", kam se budou screenshoty ukládat). Tyto screenshoty je možno automaticky ukládat do souborů, jejichž jména obsahují číslování. SnagIt také umožňuje odesílat periodické screenshoty e-mailem!

    Doporučuji ukládání do souborů (třeba GIF), nevyžaduje to připojení na internet a je to velmi šikovné právě pro případ dlouhých řešení šachových úloh, zejména Alybadixem (Popeye ukládají výsledky průběžně na disk, takže tam tato metoda není nutná). Pokud by došlo k výpadku napájení nebo spadnutí počítače, budeme mít na disku alespoň informaci, jak daleko se program v řešení dostal (včetně historie kdy začal který tah atd., což se dá použít i k lepším odhadům celkového času řešení). Po výpadku nemusí být všechno ztraceno. V Alybadixu jde třeba zvolit pořadí kamenů, ve kterém se budou probírat. Pokud po výpadku zvolíme "Reversed order", bude se vše řešit z druhé strany a můžeme řešení ukončit, pokud program projde místem, kde předtím došlo k výpadku.

  • Poslední možností, která se může někdy hodit, je možnost automatického spuštění programu(ů) po zapnutí počítače. To provedeme umístěním do adresáře "StartUp" (v českých verzích Windows "Po spuštění") například souboru go.bat, který má třeba tento obsah:

    cd c:\py437\
    start pywin32.exe -maxmem 800M reseni1.py
    start pywin32.exe -maxmem 800M reseni2.py

    (příkaz "start" funguje bez waitu, tj. obě řešení dvěma programy Popeye se spustí paralelně, každé s 800 MB RAM)
    Pokud by se (v době nepřítomnosti) počítač z nějakého důvodu sám restartoval, také nemusí být zbývající čas hned ztracen a mohou zde být připraveny další úlohy k řešení.