V rámci Semináře současné matematiky (01SSM) jsem se dostal k zajímavé příležitosti – spolupracovat na Ústavu organické chemie a biochemie v oddělení výpočetní chemie. Nejdřív jsem si myslel, že vše půjde hladce a používaná metoda půjde jednoduše zrychlit. Průběžně jsem tento pocit ztrácel až jsem ho nakonec ztratil úplně.

Že je o urychlení velký zájem dokládá fakt, že výpočty běží na clusterech třeba i měsíc. Krátce k problému: jedná se o nalezení stabilního stavu molekuly, tedy takových souřadnic atomů, při kterých nabývá energie svého lokálního minima. K tomuto účelu zná druhák Newtonovu iterační metodu, ta se ukáže nepoužitelná hned ze dvou důvodů. Potřebný Hessián neumí používané placené binárky přímo vypočítat a i kdyby, s maticí řádově tisícových rozměrů není možné pracovat (narážíme dokonce i na omezení operační paměti, natož pak průtoky sběrnicí). Místo Newtonovy metody se používá její derivát, metoda L-BFGS, která místo Hessiánu počítá pouze s číslem jako jeho odhadem a omezenou historií kroků.

I přes takto beznadějný začátek jsem se nevzdal a začal hledat články. Bohužel, a tak to zkrátka chodí, se první vyzkoušená modifikace L-BFGS i přes autory slíbené urychlení ukázala jako bezvýznamná. Ve chvíli největší beznaděje a pocitu, že jsem budižkničemu, jsem objevil další článek, který se zaměřoval přímo na naši problematiku. Popsaná metoda se soustředí na nejslabší místo L-BFGS, místo číselného odhadu Hessiánu počítá numericky jeho aproximaci formou řídké matice. To by samo o sobě moc nepomohlo, počítání 3N gradientů dokáže zatopit i velkému clusteru, článek proto navíc popisuje, jak počítat víc diferencí najednou. A využívá k tomu krásnou matematiku – obarvování grafu.

Popsanou metodu jsme měli během loňského podzimu nakóděnou (Výpočet je řízen Ruby skriptem, doporučuju jako skriptovací jazyk!) a první výsledky ukázaly až 75% urychlení! Sice za cenu využití čtyř procesorových jader namísto jednoho (binárky neumí běžet paralelně…), s nedostatkem techniky však problém není, jde hlavně o čas. A že jsme byli zvědaví, jak rychle nová metoda poběží, nenapsali jsme jí zpočátku úplně poctivě celou. Čekali jsme proto po dopsání další urychlení, které ani přes využití více jader nepřišlo. Opět se prokázalo, že motorem pokroku je lenost! :) A právě lepší efektivita (už ne lenost…) nás vedla k sepsání článku. Teď už jen čekáme, zda bude přijat, a těšíme se na případné budoucí citace.

Závěrem bych vás chtěl všechny povzbudit, abyste se neostýchali jít psát bakalářku/diplomku na některý z ústavů Akademie věd!


Napsat komentář

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>