0xDEADBEEF

[RSS]
««« »»»

Poznámky ke slajdům k přednášce, kterou jsem nikdy nepřednášel

12. 1. 2019

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.

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í.

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.

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.

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ímavostianomálie (jako třeba, že regexy jsou pomalé) na které jsem v poslední době narazil.

Něco o umělé inteligenci, automatizaci a nutnosti komunismu. O tom píšu jinde..

Tady se konečně dostávám k pořadu večera: Odhadůmlocality 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.

píše k47 (@kaja47, k47)