Poznámky ke slajdům k přednášce, kterou jsem nikdy nepřednášel
Před nějakou dobou jsem na twitter hodil slajdy z lightning talku, který bych mohl mít na jOpenSpace, kdybych tam jel. Poskládal jsem ho za pár minut a byl strukturovaný jako seznam témat, o kterých bych mohl z patra mluvit, ale nebudu (možná jen pod pohrůžkou střelnou zbraní) a potom nakonec jedno téma, které si zaslouží rozvedení. Tento článek je komentář k jednotlivým slajdům.
- VON NEUMANN IS DEAD
První bod se věnoval novinkám a vývoji architektur CPU, GPU a dalších procesorů. Protože, ač to tak nemusí vypadat, děje se toho poměrně hodně. Chipzilla může mít problémy, ale to nic neznamená.
Vektorové procesory se vrací na výsluní. NEC vyrábí SX-Aurora TSUBASA (info), RISC-V finišuje Vector Extension Proposal a dokonce se pro ARM chytá vektorové rozšíření SVE. I Agner Fog přihodil své želízko do ohně s návrhem architektury ForwardCom, která také počítá s vektory.
Objevilo se několik zmínek o dataflow strojích. Microsoft už roky koketuje s experimentálním čipem E2 (který vzešel z výzkumného projektu TRIPS) a také se objevily kusé zprávy o projektu dataflow CPU od Intelu. Nebylo by to poprvé, co myšlenky Chipzilly zabrousily mimo svět x86.
Divoce se spekuluje o PIM neboli Processor-in-memory. V současných architekturách většinu energie spotřebují přesuny dat z RAM do procesoru a zpátky. Dává proto smysl obohatit paměť o výpočetní prostředky a přesunout na ně určité nepříliš komplikované kalkulace/transformace, zvlášť v době, kdy paměťové moduly mají několik vrstev propojených TSV a jedna z nich již obsahuje logiku.
První návrhy PIM čipů předpokládaly že na jednom kusu křemíku se bude vedle pamětí nacházet i hlavní vektorové CPU, které využije vysokou interní propustnost. To by znamenalo zcela novou architekturu a proto se nikdy nedočkaly realizace.
Modernější návrhy počítají s běžnými CPU doplněnými o chytré paměti. Jedna
publikace od Googlu ukázala, že PIM by mohla značně snížit spotřebu
energie a zrychlit některé aplikace na mobilních telefonech. Typicky všechny
rutiny, které se dotýkají velkého množství paměti by mohly benefitovat z PIM:
memset
, memmove
, transpozice matic, nulování paměti, rutiny garbage
collectoru (sen o HW podpoře pro GC žije dál). Reálná a použitelná
implementace má své problémy, které ke třeba vyřešit (koherence cache,
mapování virtuální paměti a TLB), ale i tak by to mělo stát za vynaložené
úsilí.
- YOU CANNOT SORT FOR SHIT
Tady bych se mohl věnovat některým řadícím algoritmům, které nejsou tak známé, jak by si zasloužily: 3-way radix quicksort, LSD radix sort, RMS, burst sort, radix sort na komprimovaných prefixech a paralelní řazení.
Ale možná nic z toho brzy nebude důležité. Google publikoval paper o tom, jak se stroj naučil řadící algoritmus efektivnější než quicksort.
- THERE WILL BE DAY WHEN TONY HOARE IS DEAD AND ALL HOPE IS LOST
Tony Hoare je jediný člověk, jehož wiki stránky pravidelně kontroluji, abych se přesvědčil, že je stále naživu. Bojím se světa ve kterém nebude bít srdce člověka, který objevil quicksort v roce 1959 jako sázku se svým nadřízeným. Tony Hoare dostal za úkol napsat shellsort, ale řekl, že má lepší a rychlejší algoritmus. Jeho šéf nevěřil a vsadil se o šestipenci, že to není možné. Tony sázku vyhrál a s ním i my všichni. V dnešní měně vsazená částka odpovídá přibližně polovině libry a tedy 16 korunám. Jeden z nejdůležitějších algoritmů nestál ani dvacku.
- YOUR CODE IS BUGGY AS FUCK BUT IT‘S SO SLOW NOBODY HAS PATIENCE TO USE IT ANYWAY
Tohle mělo být něco o benchmarkování, mechanical sympathy, virtuálních strojích a tak podobně, jak psát rychlý kód + zajímavosti a anomálie (jako třeba, že regexy jsou pomalé) na které jsem v poslední době narazil.
- IN 5 YEARS TIME YOU WILL BE REPLACED BY A COMPUTER SO WHY EVEN TRY
Něco o umělé inteligenci, automatizaci a nutnosti globálního komunismu. O tom píšu jinde..
- IF YOU CAN'T ENSURE SAFETY, AT LEAST YOU'VE GOT SPEED
Tady se konečně dostávám k pořadu večera: Odhadům a locality sensitive hashing – technice, která umožňuje rychle najít (většinu) podobných položek podle určité metriky bez toho, abych musel počítat podobnost se vším. LSH je založena na hašování, ale jiném než to, na kterém staví hashmapy. Klasická hash funkce nezachovává korelace vstupů – dva podobné vstupy nemají stejné hashe. LSH je vystaveno na opaku – hashe podobných vstupů jsou si podobné a čím jsou si vstupy podobnější, tím větší šance je, že hashe budou identické.
To bylo ale hlavní téma, ne jen série preambulí a nemám prostor tu psát víc.
+1: Za pozornost stojí tento článek, o tom jak rozšířit klasický minhash pro reálné váhy.