NP-hard: Nenasytitelná touha

Mluvíme s Tomášem Kubátem, šéfem divize Hybridní IT v české pobočce HPE a nejdřív ze všeho nám naznačí preferovaný titulek titulku společného textu. Takže se trochu bojíme zeptat. Zní to poněkud choulostivě, jako kdyby to patřilo do takové té kategorie pro dospělé. Jak tohle souvisí s Hewlett Packard Enterprise? Je to skutečně pro dospělé? „To víte, že je to pro dospělé, ale jinak než se vám zdá,“ odpovídá Tomáš Kubát.

Tak o co jde?

Odpovím rébusem: v malém je to banální a ve velkém neřešitelné. Tedy v přijatelném čase. Tím vám ale napovídám málo. Když vypijete lahev vína s absolventem MatFyz, on vám vysvětlí NP-hard detailně. Pro tento okamžik nám ale stačí vědět, že NP-hard je typ obtížně (hard) řešitelného problému. Například – když budete mít za úkol navštívit 4 města a ujet co nejméně km, vyřešíte to z hlavy. Když ale těch měst bude 15, musíte hledat nejlepší z více než 43 miliard možných tras. Potíž je, že na to není lepší metoda řešení, než vyzkoušet všechny možnosti a určit tu nejlepší. Říká se tomu také problém obchodního cestujícího.

Vzhledem k tomu, že už nějakou dobu vnímáme HPE jako leadera v oblasti high performance computingu, očekáváme, že řešení bude v superpočítačích s mnoha jádry…

Když zadání roste lineárně, složitost úlohy roste exponenciálně. Superpočítače jsou skvělé pro mnohé úlohy. Ale pro existující úlohy tohoto typu asi není na světě dost superpočítačů, ani dost jejich výkonu a ani dost Temelínů, které by je krmily elektřinou. Čím víc výsledků těchto úloh potřebujeme, tím víc nenasytitelná je ta touha to nějak vypočítat.

A trápí nás to vůbec? Tak se třeba smíříme s tím, že se při distribuci zásilek najede trochu víc kilometrů. Vždyť s tím žijeme po léta. Proč ne ještě chvíli?

Tento typ úlohy se nám opakuje v mnoha oborech – když se dělá genová analýza virů při vývoji léčiv, když se dělá návrh struktury počítačových čipů vysoké integrace, když se optimalizuje využití přenosového pásma radiové komunikace, když se optimalizují a plánují linky a také palubní personál pro letecký provoz. A potřebujeme ta řešení nalézat.

Tak co s tím?

Ten problém je ve větvení při klasickém počítačovém zpracování. Každý další krok řešení problému znamená jeho rozvětvení a tím (v přijatelném čase) až nezvládnutelnou složitost. Kdybychom ale měli nějaké systémy, které si s tím větvením poradí jiným přirozenějším způsobem svého zpracování, tak by to byla cesta.

Jak jiným způsobem?

Lidský mozek má energetický příkon asi 20W. Řekněte výrobci počítačů, že má k dispozici 20 wattů a ať sestaví počítač, který umí totéž jako lidský mozek. Jaký bude výsledek? Ten počítač nebude ani tak malý jako mozek, ani tak „chytrý“ a ani nebude mít tak malou spotřebu. Proč? Protože mozek pracuje na jiném principu. Možná, že pro správné a na halíř přesné zpracování účetní uzávěrky firmy je ten princip počítače vhodnější, ale pro jiné úlohy ne. Tak co kdybychom se s technologií přiblížili ke způsobu zpracování, který používá mozek?

Něco kolem neuronových sítí?

Ano, neuronové sítě jsou ve středu zájmu vědců, kteří řeší třeba strojové učení (Machine Learning), a kteří řeší i úlohy NP-hard. Využívají mimo jiné Hopfieldovy neuronové sítě, která je charakteristická svou vnitřní zpětnovazební strukturou a která je vhodná pro iterační řešení optimalizačních úloh. A tady mě to vrací k Hewlett Packard Enterprise. Totiž dostat algoritmy té neuronové sítě do SW a nechat to počítač vyřešit je obvyklý přístup, ale už jsme si na začátku řekli, že to není cesta.  V HPE ale pracujeme na hardwarovém akcelerátoru.

Akcelerátory jsou v IT světě ale poměrně běžné.

Samozřejmě, že ano. Zde ale tentokrát mluvíme nikoliv o běžných (digitálních) akcelerátorech, ale o akcelerátoru, který pracuje v analogovém režimu. Je to pole analogových nelineárních non-volatilních paměťových elementů. Takové pole s obsluhujícími obvody představuje implementaci Hopfieldovy neuronové sítě a ona vnitřní zpětná vazba je tam zajištěna hardwarově a paralelně. Funguje to proto velmi rychle a s malou spotřebou energie. Spotřeba energie je to nejdůležitější – při klasickém digitálním zpracování dnes již dovedeme dosáhnout značné paralelnosti a teoreticky dovedeme nasadit neomezeně počítačových jader. Nakonec nás ale reálně zabrzdí spotřeba elektřiny. A zde díky analogovému režimu dosahujeme zásadně vyšší paralelnosti při spotřebě energie 10 000 krát nižší než v klasickém digitálním modelu. Jsou tam i zajímavé technické vychytávky: Při řešení optimalizační úlohy ta neuronová síť vybavuje výsledky, které mohou být lokálními minimy, my ale hledáme absolutní minimum. Proto se pomocí speciálního vzruchu iniciují další iterace výpočtu a v tom pomáhá vlastní šum obvodů, který umíme zapnout a vypnout. Je to jako kdybychom chtěli, aby se kulička na nerovném povrchu skutálela do důlku, ale ona se zastaví na nerovnosti povrchu. Když s tím trochu zatřeseme, obnovíme kuliččino hledání důlku.

Až to bude hotové, jak ten akcelerátor bude vypadat?

Bude více fyzických provedení. Jedním bude třeba PCI-Express karta. Pokud potřebujeme akcelerátor dát do již existujícího zařízení, toto se jeví jako řešení. Druhým provedením budou čipy, které se stanou součástí návrhu a budou při výrobě zabudovány do specializovaných zařízení (třeba lékařských nebo komunikačních). Třetím formátem budou akcelerátory podporující standard Gen-Z, které se stanou součástí architektur Memory Driven Computing. Velmi důležitá je ale vyrobitelnost: všechny tyto akcelerátory se dají vyrábět existující technologií výroby čipů, takže to dává dobrý předpoklad k nízké ceně.

Zní to velmi pozitivně.

V HPE jsme velmi úspěšní s našimi nynějšími produkty. A moc mě těší, že naše laboratoře nejen dál rozvíjejí existující technologie, ale jdou dál a pracují na věcech skutečně nových, s novými principy. Jsme inženýrská firma, k nám to patří!