Paralelní (skoro)SHA

Máme ve škole takový zajímavý předmět. Jmenuje se Algoritmy a jejich implementace, letos byl vyučován poprvé a jeho náplň byla vskutku zajímavá a různorodá. MJ a Pasky se totiž pokoušeli o nemožné: Během semestru nás učili céčko pořádně (v prvních třech přednáškách se probíraly zajímavé části svaté knihy C99, časem došlo i na rozšíření gcc). Strávili spoustu času vyvracením toho, co nás učili na Principech, OZD a podobných přednáškách a ukazovali, jak je to doopravdy. Povídali nám o cachích, pamětích, procesorech (pozvali Honzu Hubičku ochotného podělit se o všechno, na co nepodepsal NDA). Učili jsme se, jak při programování znalost těchto věcí používat. Dozvěděli jsme se třeba, jak rychle třídit, nebo jak se počítá na grafických kartách.

Požadavkem ke zkoušce je aplikovat nabyté znalosti a napsat s jejich využitím něco zajímavého. Dlouho jsem si lámala hlavu, co by to mělo být: Všechna ta třídění, stromy či násobení matic sice skýtají spousty prostoru pro optimalizace, ale je to poněkud fádní. Nakonec jsem přece jen zavadila o nápad, který se mi zalíbil: Co takhle zkusit si spočítat SHA paralelně?

Tedy, spočítat SHA paralelně samozřejmě ve skutečnosti nejde. Můžeme ale udělat obezličku: Rozdělit si vstup na bloky, spočítat paralelně hashe bloků a hashe těchto hashů vydávat jako výsledek. Pokud umíme SSE, můžeme navíc místo jednoho hashe bloku počítat rovnou čtyři proložené naráz, výsledek zahashovat a dál postupovat jako v minulém případě.

Což zní zatraceně jednoduše. Přesto to nakonec vydalo na pár večerů zábavy: Nejprve zamotat se do pavučiny vlastních vláken (hmm, takové věci se opravdu dají psát buď jednoduše nebo blbě... nebo oboje), potom věštit z kávové sedliny (pardon, ze souboru emmintrin.h), vymýšlet, jak to slepit, aby to bylo aspoň trochu efektivní, přijít na to, proč to funguje jen jako poněkud pomalý generátor náhodných čísel, a proč to dává jiné výsledky než referenční implementace SHA1 (fakt pěkně blbě se to debuguje). Prostě, přestože to vypadá jako maličkost, jeden na tom naloví mnohem víc expů, než by čekal. Opravdu, schválně si něco takového zkuste napsat taky.

Výsledek splnil očekávání - na mém quadu (ha, konečně můžu zaměstnat nějakým vlastním výtvorem všechna jádra) to běží tak devětkrát rychleji než normální shasum. Ostatně, pokud máte mašinku, co umí SSE, má 32bitové inty a gcc, můžete si to vyzkoušet.

A pokud náhodou zrovna taky studujete na matfyzu, nejste hackeři, co mají x86 a spol. mašinky v malíčku a chcete s tím aspoň trochu něco dělat, nezapomeňte si příští zimu zapsat předmět Algoritmy a jejich implementace.

Toto je reklamní článek předmětu NDMI074 :-)