0xDEADBEEF

[RSS]
««« »»»

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

12. 1. 2019

Před ně­ja­kou dobou jsem na twit­ter hodil slajdy z li­ght­ning talku, který bych mohl mít na jO­pen­Space, kdy­bych tam jel. Po­sklá­dal jsem ho za pár minut a byl struk­tu­ro­vaný jako seznam témat, o kte­rých bych mohl z patra mluvit, ale nebudu (možná jen pod po­hrůž­kou střel­nou zbraní) a potom na­ko­nec jedno téma, které si za­slouží roz­ve­dení. Tento článek je ko­men­tář k jed­not­li­vým slaj­dům.

První bod se vě­no­val no­vin­kám a vývoji ar­chi­tek­tur CPU, GPU a dal­ších pro­ce­sorů. Pro­tože, ač to tak nemusí vy­pa­dat, děje se toho po­měrně hodně. Chi­p­zilla může mít pro­blémy, ale to nic ne­zna­mená.

Vek­to­rové pro­ce­sory se vrací na vý­sluní. NEC vyrábí SX-Aurora TSUBASA (info), RISC-V fi­ni­šuje Vector Ex­tension Pro­po­sal a do­konce se pro ARM chytá vek­to­rové roz­ší­ření SVE. I Agner Fog při­ho­dil své že­lízko do ohně s ná­vrhem ar­chi­tek­tury For­ward­Com, která také počítá s vek­tory.

Ob­je­vilo se ně­ko­lik zmínek o da­ta­flow stro­jích. Micro­soft už roky ko­ke­tuje s ex­pe­ri­men­tál­ním čipem E2 (který vzešel z vý­zkum­ného pro­jektu TRIPS) a také se ob­je­vily kusé zprávy o pro­jektu da­ta­flow CPU od Intelu. Nebylo by to poprvé, co myš­lenky Chi­p­zilly za­brousily mimo svět x86.

Divoce se spe­ku­luje o PIM neboli Pro­ces­sor-in-memory. V sou­čas­ných ar­chi­tek­tu­rách vět­šinu ener­gie spo­tře­bují pře­suny dat z RAM do pro­ce­soru a zpátky. Dává proto smysl obo­ha­tit paměť o vý­po­četní pro­středky a pře­su­nout na ně určité ne­pří­liš kom­pli­ko­vané kal­ku­lace/trans­for­mace, zvlášť v době, kdy pa­mě­ťové moduly mají ně­ko­lik vrstev pro­po­je­ných TSV a jedna z nich již ob­sa­huje logiku.

První návrhy PIM čipů před­po­klá­daly že na jednom kusu kře­míku se bude vedle pamětí na­chá­zet i hlavní vek­to­rové CPU, které vy­u­žije vy­so­kou in­terní pro­pust­nost. To by zna­me­nalo zcela novou ar­chi­tek­turu a proto se nikdy ne­do­čkaly re­a­li­zace.

Mo­der­nější návrhy po­čí­tají s běž­nými CPU do­pl­ně­nými o chytré paměti. Jedna pu­b­li­kace od Googlu uká­zala, že PIM by mohla značně snížit spo­třebu ener­gie a zrych­lit ně­které apli­kace na mo­bil­ních te­le­fo­nech. Ty­picky všechny rutiny, které se do­tý­kají vel­kého množ­ství paměti by mohly be­ne­fi­to­vat z PIM: memset, memmove, trans­po­zice matic, nu­lo­vání paměti, rutiny gar­bage collec­toru (sen o HW pod­poře pro GC žije dál). Reálná a po­u­ži­telná im­ple­men­tace má své pro­blémy, které ke třeba vy­ře­šit (ko­he­rence cache, ma­po­vání vir­tu­ální paměti a TLB), ale i tak by to mělo stát za vy­na­lo­žené úsilí.

Tady bych se mohl vě­no­vat ně­kte­rým řa­dí­cím al­go­ritmům, které nejsou tak známé, jak by si za­slou­žily: 3-way radix quicksort, LSD radix sort, RMS, burst sort, radix sort na kom­pri­mo­va­ných pre­fi­xech a pa­ra­lelní řazení.

Ale možná nic z toho brzy nebude dů­le­žité. Google pu­b­li­ko­val paper o tom, jak se stroj naučil řadící al­go­rit­mus efek­tiv­nější než quicksort.

Tony Hoare je jediný člověk, jehož wiki stránky pra­vi­delně kon­t­ro­luji, abych se pře­svěd­čil, že je stále naživu. Bojím se světa ve kterém nebude bít srdce člo­věka, který ob­je­vil quicksort v roce 1959 jako sázku se svým nad­ří­ze­ným. Tony Hoare dostal za úkol napsat shell­sort, ale řekl, že má lepší a rych­lejší al­go­rit­mus. Jeho šéf ne­vě­řil a vsadil se o šes­ti­penci, že to není možné. Tony sázku vyhrál a s ním i my všichni. V dnešní měně vsa­zená částka od­po­vídá při­bližně po­lo­vině libry a tedy 16 ko­runám. Jeden z nej­dů­le­ži­těj­ších al­go­ritmů nestál ani dvacku.

Tohle mělo být něco o ben­chmar­ko­vání, me­cha­ni­cal sym­pathy, vir­tu­ál­ních stro­jích a tak po­dobně, jak psát rychlý kód + za­jí­ma­vostiano­má­lie (jako třeba, že regexy jsou pomalé) na které jsem v po­slední době na­ra­zil.

Něco o umělé in­te­li­genci, au­to­ma­ti­zaci a nut­nosti ko­mu­nismu. O tom píšu jinde..

Tady se ko­nečně do­stá­vám k pořadu večera: Od­ha­důmlo­ca­lity sensi­tive ha­shing – tech­nice, která umož­ňuje rychle najít (vět­šinu) po­dob­ných po­lo­žek podle určité me­t­riky bez toho, abych musel po­čí­tat po­dob­nost se vším. LSH je za­lo­žena na ha­šo­vání, ale jiném než to, na kterém staví ha­shmapy. Kla­sická hash funkce ne­za­cho­vává ko­re­lace vstupů – dva po­dobné vstupy nemají stejné hashe. LSH je vy­sta­veno na opaku – hashe po­dob­ných vstupů jsou si po­dobné a čím jsou si vstupy po­dob­nější, tím větší šance je, že hashe budou iden­tické.

To bylo ale hlavní téma, ne jen série pre­am­bulí a nemám pro­stor tu psát víc.


+1: Za po­zor­nost stojí tento článek, o tom jak roz­ší­řit kla­sický minhash pro reálné váhy.

píše k47 (@kaja47, k47)