Kování a hledání, které si svůj důkaz zaslouží
Starý trik s problémem
Každý vážný softwarový systém má pár kusů kódu, které jsou důležitější, než by jejich velikost napovídala. Smyčka, která se spustí milionkrát. Bitová operace v kompresní cestě. Malá maticová rutina. Modulární aritmetické jádro. Něco, co při code review vypadá neškodně a pak tiše rozhoduje o účtu za energii, rozpočtu na latenci nebo počtu strojů, které musíte koupit. Software je velmi demokratický. Jedna malá funkce může zkazit schůzku všem.
Historicky tato jádra vylepšují lidé. Zkušený inženýr si vzpomene na trik z článku. Někdo prohledá staré fórum. Napíše se benchmarková sada. Vyzkouší se pár kandidátů. Nejrychlejší vyhraje, pokud stále vypadá správně. Pak organizace výsledek zmrazí, protože se ho znovu dotknout je jako píchat vidličkou do spícího transformátoru.
Forge je výzkum lepší verze tohoto procesu. Je to nástroj pro syntézu programů pro malé, kritické implementace: dejte mu typovou specifikaci a vlastnosti, nechte ho prohledávat kandidátní programy, měřit a porovnávat kompromisy, ověřit ekvivalenci a pak sestavit objevenou implementaci pro cíle, na kterých záleží. Důležité slovo není hledání. Důležité slovo je stále. Stále musí být správný.
Proto Forge žije ve výzkumu. Není to veřejné tlačítko produktu, kde někdo napíše udělej rychlejší a dostane zázrak. Je to pracovní stůl pro syntézu pro partnerské experimenty, objevování jader a výzkum toho, jak daleko může automatizované hledání zajít, když je svázáno s ověřováním místo s divadlem benchmarků.
Specifikace je startovní čára
Optimalizace bez specifikace je jen hazard s hezčími názvy proměnných. Jakmile se objeví chytrý kandidát, tým musí vědět, co má zachovat. Zpracovává každý vstup, nebo jen ty přátelské z benchmarku? Respektuje chování při přetečení? Platí algebraická identita pro reprezentaci, která se skutečně používá? Zachovává stejnou sémantiku při sestavení pro jiný backend?
Forge začíná od typových výrazů a vlastností, protože hledání potřebuje hranici. Hranice říká, co se počítá jako ekvivalentní. Bez ní může nástroj najít něco ohromně rychlého tím, že smaže polovinu práce. Počítače jsou vynikající ve zlomyslné poslušnosti, když je smlouva vágní.
Hledací stránka je záměrně v množném čísle. Enumerativní hledání je užitečné, když je prostor dost malý na pokrytí. CEGIS je užitečný, když mohou protipříklady vést zpřesňování. Genetické programování a MCTS prozkoumávají jinak. Hledání řízené strojovým učením se může naučit nákladové modely a upřednostnit slibné oblasti. Žádný z těchto přístupů není univerzálně nejlepší. To není slabost. Tak se hledání chová v reálném světě. Kdyby jedno kladivo vyřešilo každé jádro, byly by nástrojové boxy velmi nudné a výrobci hardwaru by byli bez práce.
Výzkumná otázka je, jak tyto nástroje kombinovat s dostatečným tlakem na důkazy, aby výsledek nebyl jen chytrý. Syntetizované jádro musí přežít jak benchmark na šťastné cestě, tak ověřovač na nešťastné cestě. Jinak to zlepšení není inženýrství. Je to kouzelnický trik s náklady na údržbu.
Ověřovač je dospělý v místnosti
Forge používá ověřovací zásobník, protože žádná jediná kontrola nestačí pro všechny oblasti. Rychlé příklady jsou levné a užitečné. Testy vlastností odhalí široké třídy chyb a zmenší protipříklady na něco, co si člověk dokáže přečíst. Řešiče SMT, jako jsou Z3 a CVC5, dokážou dokázat ekvivalenci tam, kde je kódování zvládnutelné. Vyčerpávající kontrola je praktická pro malé oblasti. E-graph saturace ekvivalence nabízí další cestu k algebraické ekvivalenci.
Zásobník je důležitý, protože jádra selhávají otravnými způsoby. Kandidát může projít všemi běžnými benchmarky a přesto být chybný v okrajovém případě. Může být správný pro čísla bez znaménka a chybný pro čísla se znaménkem. Může být správný v matematickém tělese a chybný poté, co zvolená reprezentace přeteče. Může být správný před snižováním úrovně a nenápadně chybný po rozhodnutí o výběru instrukcí. Ověřovač existuje, protože optimismus není testovací strategie. Zkontrolovali jsme to. Opakovaně. Stále to platí.
Existuje také praktický důvod mít několik cest k důkazu. Formální metody jsou mocné, ale nejsou zadarmo. Některá kódování vyprší. Některé oblasti jsou příliš velké pro vyčerpávající kontrolu. Některé vlastnosti je snazší nejprve testovat pravděpodobnostně a dokázat později. Forge zachází s ověřováním jako s trychtýřem, ne jako s rituálem čistoty. Levné kontroly odmítnou zjevné nesmysly. Silnější kontroly chrání finálního kandidáta.
Rychlé není jedno číslo
Práce na výkonu začne být směšná, když jedna metrika smí dominovat každé konverzaci. Latence záleží. Počet operací záleží. Využití paměti záleží. Tlak na registry záleží. Čas kompilace někdy záleží. Přenositelnost záleží, když stejné jádro musí žít na více než jednom backendu. Kandidát, který vyhraje na latenci tím, že pálí registry jako malý táborák, může být pro skutečný cíl špatný. Kandidát, který je malý, ale pomalý, může být užitečný jinde. Kontext zůstává neporažen.
Forge proto rámuje optimalizaci jako problém Pareto. Engine může prohledávat napříč cíli, místo aby předstíral, že existuje jedno univerzální skóre seslané velmi sebevědomou tabulkou. Užitečným výstupem není vždy jediný nejrychlejší kandidát. Někdy je to rodina kandidátů s viditelnými kompromisy, aby si inženýr mohl vybrat toho, který odpovídá omezením nasazení.
To je také důvod, proč nemám rád holá tvrzení o zrychlení v příspěvcích na blogu. Výzkumná stránka může popisovat interní očekávání a experimentální cíle, ale veřejná tvrzení potřebují čerstvé běhy, aktuální hardware, aktuální přepínače kompilátoru a přesný kontext pracovní zátěže. Jinak se z čísla stane suvenýr. Suvenýry jsou hezké. Nejsou to architektura.
Upřímné tvrzení je stejně silnější: Forge je o tom, aby bylo vyhledávání reprodukovatelné, srovnatelné a ověřitelné. Když kandidát vyhraje, měli bychom vědět, kterou metriku vyhrál, které kandidáty porazil, který ověřovač ho přijal a na který backend cílí. To je mnohem užitečnější než číslo plující prezentací a vypadající draze.
Snižování úrovně je místo, kde se důkazy jdou testovat
Objevená implementace je užitečná jen tehdy, pokud přežije cestu ke skutečným cílům. Výzkum Forge pokrývá snižování úrovně na backendy, jako jsou x86-64, RISC-V, WASM, cesty GPU Vulkan, C a Verilog. Tento seznam cílů není jen dekorace. Každý backend má svá vlastní omezení, tvary instrukcí, chování paměti a režimy selhání. Stejná specifikace si musí zachovat svůj význam, zatímco se implementace stane něčím, co cíl skutečně dokáže spustit.
Právě zde se syntéza propojuje se zbytkem zásobníku Dweve. Core chce efektivní vnitřní smyčky. Numerus se stará o deterministická numerická jádra. BitWeave chce binární vektorové a maticové operace, které neplýtvají výkonem CPU. Kera se stará o snižování výpočetních grafů na skutečný hardware. Forge může tyto vrstvy zásobovat, jen pokud je generovaná implementace víc než jen rychlá. Musí být ekvivalentní, dostatečně přenosná pro zvolený cíl a kontrolovatelná, když se něco změní.
Co to mění pro týmy
Pro tým není zajímavý posun v tom, že by stroj mohl objevit rychlejší jádro. Je v tom, že práce na jádrech se stává méně závislou na folklóru. Místo jednoho experta, který si pamatuje správný trik, se proces stává: definujte kontrakt, prohledejte prostor, změřte kandidáty, dokažte ekvivalenci, zaznamenejte kompromis a vygenerujte cílový kód. Lidé stále rozhodují. Jen přestanou dělat všechno objevování ručně.
To je důležité pro provoz, protože dluh na výkonu je drahý způsobem, který organizace často skrývají. Pomalé jádro znamená více serverů. Více serverů znamená více nákladů, více energie, větší složitost nasazení a více šumu v plánování. Špatná optimalizace znamená incidenty. Správný, ale nedokumentovaný trik znamená budoucí riziko migrace. Forge je výzkum, jak tuto hromadu zbytečných nesmyslů zmenšit.
Je tu i kulturní změna. Ruční práce na výkonu často odměňuje hrdinství. Někdo zmizí do jeskyně a vrátí se s chytrým hackem. Všichni tleskají, nikdo tomu úplně nerozumí a firma získala malý posvátný předmět. Forge posouvá proces směrem k důkazům: tady je specifikace, tady je cesta hledání, tady jsou odmítnutí kandidáti, tady je verifikátor, tady je vybraný backend. Méně mytologie. Více účtenek.
Kde je práce stále obtížná
Nic z toho nedělá syntézu snadnou. Specifikace jsou obtížné. Pokud je specifikace špatná, může engine věrně objevit špatnou věc. Prostory hledání mohou explodovat. Řešiče mohou vypršet. Modely nákladů mohou klamat. Backendy mohou odhalit detaily, které abstraktní vyjádření nezajímaly. Verifikace může být silná v jedné doméně a neohrabaná v jiné. Každý, kdo prodává syntézu programů jako prodejní automat na optimální kód, buď přeskočí obtížné části, nebo si účtuje příplatek za zklamání.
Forge je zajímavý právě proto, že čelí těmto obtížným částem přímo. Kombinuje několik strategií hledání. Drží verifikaci blízko. S cíli zachází jako s kompromisy. Míří na skutečné backendy. Zůstává výzkumným programem, protože se stále učíme, kde leží hranice mezi automatizovaným objevováním, lidským úsudkem, limity řešičů a realitou nasazení.
Tuto hranici stojí za to prozkoumat. Softwarový průmysl má příliš mnoho malých horkých smyček, příliš mnoho duplikovaného výkonnostního folklóru a příliš mnoho optimalizací, kterých se už nikdo nechce dotknout. Pokud Forge dokáže proměnit byť jen část této práce v opakovatelný proces založený na důkazech, výsledkem není jen rychlejší kód. Je to klidnější kód. Klidnější kód je nedoceněný, většinou lidmi, kteří nebyli voláni ve 02:17.
Co potřebuje dobrý běh Forge
Vážný experiment s Forge začíná dřív, než se spustí engine. Tým musí přinést skutečné jádro, ne vágní stížnost na výkon. Potřebuje reprezentativní vstupy, známé okrajové případy, cílový hardware, aktuální benchmarky a obchodní důvod, proč na tomto jádru záleží. Jinak může syntézní engine strávit spoustu času řešením problému, který ve skutečnosti nikdo nemá. Výzkumné nástroje nejsou imunní vůči nekvalitním vstupům. Jen dělají kontrolu těch nekvalitních vstupů dražší.
Nejužitečnější vstup je malá, ostrá specifikace. Co má funkce počítat? Která algebraická pravidla jsou důležitá? Které přetečení je záměrné? Které rozsahy jsou vyloučené konstrukcí a které se jen nevyskytly v posledním testovacím běhu? Které výstupy snesou aproximaci a které ne? Tým, který na tyto otázky neumí odpovědět, pravděpodobně ještě nemá problém s optimalizací. Má problém s vyjasněním produktu, který se převlékl za kompilátor.
Dobrý běh také potřebuje cílovou pozici. x86-64 a RISC-V nejsou totéž. WASM má jiná omezení. GPU cesty ve Vulkanu se zajímají o tvary a pohyb paměti. Verilog přináší hardwarové otázky, které běžné aplikační týmy málokdy řeší před ranní kávou. Forge umí prozkoumat cílové snižování úrovně, ale nemůže rozhodovat o organizačních prioritách. Pokud je důležitější přenositelnost než rychlost na jedné platformě, řekněte to. Pokud má přednost latence před pamětí, řekněte to. Pokud je praktickým limitem tlak na registry, řekněte i to. Engine je výkonný, ne věštec.
S výstupem by se mělo zacházet jako s balíčkem důkazů. Kandidát, cíl, cesta k důkazu, zamítnuté protipříklady, backend, kontext benchmarku a otevřené výhrady. Tento balíček umožňuje lidem učinit rozumné rozhodnutí. Někdy je vítězným tahem přijmout kandidáta. Někdy je lepší ponechat staré jádro, protože kompromis v přenositelnosti za to nestojí. Někdy je zjištěním, že specifikace byla příliš volná. Všechny tři výsledky jsou užitečné. Jen jeden z nich vypadá na demu zajímavě, a proto jsou dema špatnou náhradou za inženýrskou práci.
Ponaučení
Ponaučení z Forge je jednoduché: výkon by neměl předbíhat důkazy. Vyhledávání je mocné, ale vyhledávací engine bez ověřování je jen velmi energický způsob, jak vytvářet chyby. Ověřování je mocné, ale bez vyhledávání čeká, až mu lidé přinesou kandidáty. Forge dává obojí dohromady a ptá se, jaká jádra dokážeme objevit, když stroj smí prozkoumávat, ale nesmí lhát.
To je výzkum, který stojí za to dělat. Typované specifikace, vyhledávání kandidátů, trychtýře důkazů, Paretovy cíle a snižování úrovně backendu. Žádná magie. Žádná zkratka k produktu. Způsob, jak vytvořit lepší malý kód s připojenými důkazy.