Kalšana un meklēšana, kas nopelna savu apliecinājumu
The old trick problem
Every serious software system has a few pieces of code that matter far more than their size suggests. A loop that runs millions of times. A bit operation in a compression path. A small matrix routine. A modular arithmetic kernel. The sort of thing that looks harmless in code review and then quietly decides the energy bill, the latency budget, or the number of machines you need to buy. Very democratic, software. One tiny function can ruin the meeting for everyone.
Historically, those kernels are improved by people. A senior engineer remembers a trick from a paper. Someone digs through an old forum post. A benchmark suite is written. A few candidates are tried. The fastest one wins if it still appears correct. Then the organization freezes it, because touching it again feels like poking a sleeping transformer with a fork.
Forge is research into a better version of that process. It is a program synthesis engine for small, critical implementations: give it a typed specificationand properties, let it search candidate programs, measure and compare tradeoffs, verify equivalence, then lower the discovered implementation to targets that matter. The important word is not search. The important word is still. It still has to be correct.
This is why Forge lives in research. It is not a public product button where someone types make faster and receives a miracle. It is a synthesis workbench for partner experiments, kernel discovery, and research on how far automated search can go when it is tied to verification instead of benchmark theatre.
A specification is the starting line
Optimization without a specification is just gambling with nicer variable names. The moment a clever candidate appears, the team needs to know what it is meant to preserve. Does it handle every input or only the friendly ones from the benchmark? Does itrespect overflow behaviour? Is the algebraic identity valid under the representation actually used? Does it keep the same semantics when lowered to a different backend?
Forge starts from typed expressions and properties because the search needs a boundary. The boundary says what counts as equivalent. Without it, the engine can find something astonishingly fast by deleting half the work. Computers are excellent at malicious compliance when the contract is vague.
The search side is deliberately plural. Enumerative search is useful when the space is small enough to cover. CEGIS is useful when counterexamples can guide refinement. Genetic programming and MCTS explore differently. ML-guided search can learn cost models and prioritize promising regions. None of these is universally best. That is not a weakness. It is how search behaves in the real world. If one hammer solved every kernel, toolboxes would be very boring and hardware vendors would be unemployed.
The research question is how to combine those engines with enough proof pressure that the result is not merely clever. A synthesized kernel has to survive both the happy-path benchmark and the unhappy-path verifier. Otherwise the improvement is not engineering. It is a magic trick with a maintenance cost.
The verifier is the adult in the room
Forge izmanto verifikācijas kopumu, jo neviena atsevišķa pārbaude nav pietiekama visām jomām. Ātri piemēri ir lēti un noderīgi. Īpašību testi atklāj plašas kļūdu klases un samazina pretpiemērus līdz kaut kam, ko cilvēks var izlasīt. SMT risinātāji, piemēram, Z3 un CVC5, var pierādīt ekvivalenci, ja kodējums ir apstrādājams. Izsmeļoša pārbaude ir praktiska mazām jomām. E-grafu vienādības saturācija sniedz vēl vienu ceļu caur algebrisko ekvivalenci.
Šis kopums ir svarīgs, jo kodoli neizdodas kaitinošos veidos. Kandidāts var izturēt visus parastos etalonus un tomēr būt nepareizs malas gadījumā. Tas var būt pareizs neparakstītiem ievaddatiem un nepareizs parakstītiem. Tas var būt pareizs matemātiskā laukā un nepareizs pēc tam, kad izvēlētais attēlojums pārpildās. Tas var būt pareizs pirms pazemināšanas un smalki nepareizs pēc instrukciju atlases lēmuma. Verifikators pastāv tāpēc, ka optimisms nav testēšanas stratēģija. Mēs pārbaudījām. Atkārtoti. Tas joprojām ir patiess.
Ir arī praktisks iemesls paturēt vairākus pierādījumu ceļus. Formālās metodes ir spēcīgas, bet tās nav bezmaksas. Daži kodējumi pārsniedz laika ierobežojumu. Dažas jomas ir pārāk lielas izsmeļošai pārbaudei. Dažas īpašības ir vieglāk vispirms pārbaudīt varbūtības ceļā un pierādīt vēlāk. Forge uztver verifikāciju kā piltuvi, nevis tīrības rituālu. Lētas pārbaudes noraida acīmredzamas muļķības. Stingrākas pārbaudes aizsargā galīgo kandidātu.
Ātrs nav viens skaitlis
Veiktspējas darbs kļūst smieklīgs, ja vienam rādītājam ļauj dominēt visās sarunās. Latence ir svarīga. Darbību skaits ir svarīgs. Atmiņas patēriņš ir svarīgs. Reģistru spiediens ir svarīgs. Kompilācijas laiks dažreiz ir svarīgs. Pārnesamība ir svarīga, ja vienam kodolam ir jādarbojas vairākos aizmugures posmos. Kandidāts, kas uzvar latencē, sadedzinot reģistrus kā mazu ugunskuru, var būt nepareizs faktiskajam mērķim. Kandidāts, kas ir mazs, bet lēns, var būt noderīgs citur. Konteksts joprojām ir nepārspēts.
Tāpēc Forge ietvarā optimizācija tiek formulēta kā Pareto problēma. Dzinējs var meklēt starp mērķiem, nevis izlikties, ka pastāv viens universāls rādītājs, ko nodevis ļoti pārliecināta izklājlapa. Noderīgais rezultāts ne vienmēr ir vienīgais ātrākais kandidāts. Dažreiz tā ir kandidātu saime ar redzamiem kompromisiem, lai inženieris varētu izvēlēties to, kas atbilst izvietošanas ierobežojumam.
Tas ir arī iemesls, kāpēc man nepatīk kaili ātruma solījumi emuāra ierakstos. Pētniecības lapa var aprakstīt iekšējās cerības un eksperimentālos mērķus, bet publiskiem apgalvojumiem ir vajadzīgi svaigi izpildījumi, pašreizējā aparatūra, pašreizējie kompilatora karodziņi un precīzs darba slodzes konteksts. Citādi skaitlis kļūst par suvenīru. Suvenīri ir jauki. Tie nav arhitektūra.
Godīgais apgalvojums tik un tā ir spēcīgāks: Forge ir par to, lai meklēšana būtu reproducējama, salīdzināma un pārbaudāma. Kad kandidāts uzvar, mums vajadzētu zināt, kuru mērķi tas uzvarēja, kurus kandidātus tas pārspēja, kurš verifikators to pieņēma un kuram aizmugures posmam tas ir paredzēts. Tas ir daudz noderīgāk nekā skaitlis, kas peld cauri slaidu komplektam, izskatoties dārgs.
Pazemināšana ir vieta, kur pierādījumi tiek pārbaudīti
Atklāta implementācija ir noderīga tikai tad, ja tā izdzīvo ceļu līdz reāliem mērķiem. Forge pētniecība aptver nolaišanu uz backendiem, piemēram, x86-64, RISC-V, WASM, Vulkan GPU ceļiem, C un Verilog. Šis mērķu saraksts nav tikai dekorācija. Katram backendam ir savi ierobežojumi, instrukciju formas, atmiņas uzvedība un kļūmju režīmi. Vienai un tai pašai specifikācijai ir jāsaglabā sava nozīme, kamēr implementācija kļūst par kaut ko tādu, ko mērķis patiešām var izpildīt.
Šeit sintēze savienojas ar pārējo Dweve steku. Core vēlas efektīvas iekšējās cilpas. Numerus rūpējas par deterministiskiem skaitliskiem kodoliem. BitWeave vēlas bināro vektoru un matricu operācijas, kas netērē CPU resursus. Kera rūpējas par aprēķinu grafiku nolaišanu uz reālu aparatūru. Forge var apgādāt šos slāņus tikai tad, ja ģenerētā implementācija ir vairāk nekā ātra. Tai jābūt ekvivalentai, pietiekami pārnesamai izvēlētajam mērķim un pārbaudāmai, kad kaut kas mainās.
Ko tas maina komandām
Komandai interesantā pārmaiņa nav tā, ka mašīna var atklāt ātrāku kodolu. Tā ir tā, ka darbs ar kodoliem kļūst mazāk atkarīgs no folkloras. Tā vietā, lai viens eksperts atcerētos pareizo triku, process kļūst: formulē līgumu, meklē telpu, mēra kandidātus, pierāda ekvivalenci, ieraksta kompromisu un ģenerē mērķa kodu. Cilvēki joprojām izlemj. Viņi tikai pārtrauc visu atklāšanu darīt ar rokām.
Tas ir svarīgi operācijām, jo veiktspējas parāds ir dārgs tādā veidā, ko organizācijas bieži slēpj. Lēns kodols nozīmē vairāk serveru. Vairāk serveru nozīmē vairāk izmaksu, vairāk enerģijas, vairāk izvietošanas sarežģītības un vairāk trokšņa plānošanā. Nepareiza optimizācija kļūst par incidentiem. Pareizs, bet nedokumentēts triks kļūst par nākotnes migrācijas risku. Forge ir pētniecība, kā samazināt šo novēršamo muļķību kaudzi.
Ir arī kultūras pārmaiņa. Manuāls veiktspējas darbs bieži atalgo varoņdarbus. Kāds pazūd alā un atgriežas ar gudru bitu triku. Visi aplaudē, neviens to pilnībā nesaprot, un uzņēmums ir ieguvis mazu svētu priekšmetu. Forge virza procesu uz pierādījumiem: šeit ir specifikācija, šeit ir meklēšanas ceļš, šeit ir noraidītie kandidāti, šeit ir verifikators, šeit ir izvēlētais backends. Mazāk mitoloģijas. Vairāk čeku.
Kur darbs joprojām ir grūts
Nekas no tā nepadara sintēzi vieglu. Specifikācijas ir grūtas. Ja specifikācija ir nepareiza, dzinējs var uzticīgi atklāt nepareizo lietu. Meklēšanas telpas var eksplodēt. Risinātāji var pārsniegt laika ierobežojumu. Izmaksu modeļi var maldināt. Backendi var atklāt detaļas, par kurām abstraktā izteiksme nerūpējās. Verifikācija var būt spēcīga vienā jomā un neveikla citā. Ikviens, kurš pārdod programmu sintēzi kā tirdzniecības automātu optimālam kodam, vai nu izlaiž grūtās daļas, vai arī iekasē papildu maksu par vilšanos.
Forge ir interesanta tieši tāpēc, ka tā tieši saskaras ar šīm grūtajām daļām. Tā apvieno vairākas meklēšanas stratēģijas. Tā tur verifikāciju tuvu. Tā attiecas uz mērķiem kā kompromisiem. Tā mērķē uz reāliem backendiem. Tā paliek pētniecības programma, jo mēs joprojām mācāmies, kur atrodas robeža starp automatizētu atklāšanu, cilvēka spriedumu, risinātāju ierobežojumiem un izvietošanas realitāti.
Šo robežu ir vērts izpētīt. Programmatūras nozarei ir pārāk daudz mazu karstu cilpu, pārāk daudz dublētas veiktspējas folkloras un pārāk daudz optimizāciju, kurām neviens vairs negrib pieskarties. Ja Forge var pārvērst pat daļu no šī darba atkārtojamā pierādījumu procesā, rezultāts nav tikai ātrāks kods. Tas ir mierīgāks kods. Mierīgāks kods ir nenovērtēts, galvenokārt tiem, kurus nav izsaukuši pulksten 02:17.
Kas nepieciešams labam Forge izpildes procesam
Nopietns Forge eksperiments sākas pirms dzinēja palaišanas. Komandai ir jāsniedz reāls kodols, nevis neskaidra sūdzība par veiktspēju. Ir nepieciešami reprezentatīvi ievaddati, zināmi robežgadījumi, mērķa aparatūra, pašreizējie etaloni un biznesa iemesls, kāpēc šis kodols ir svarīgs. Pretējā gadījumā sintēzes dzinējs var pavadīt daudz laika, risinot problēmu, kuras nevienam patiesībā nav. Pētniecības rīki nav imūni pret nevērtīgiem ievaddatiem. Tie tikai padara nevērtīgo informāciju dārgāku, lai to pārbaudītu.
Visnoderīgākais ievaddatu veids ir neliels, skaidrs līgums. Ko funkcijai vajadzētu aprēķināt? Kuri algebriskie likumi ir svarīgi? Kura pārpildes uzvedība ir apzināta? Kuri diapazoni nav iespējami pēc konstrukcijas, un kuri vienkārši neparādījās pēdējā testa izpildē? Kuri rezultāti var pieļaut tuvinājumu, un kuri nevar? Komanda, kas nevar atbildēt uz šiem jautājumiem, iespējams, vēl nav saskārusies ar optimizācijas problēmu. Tai ir produkta precizēšanas problēma kompilatora maskā.
Labam izpildes procesam ir nepieciešama arī mērķa nostāja. x86-64 un RISC-V nav viens un tas pats. WASM ir atšķirīgi ierobežojumi. Vulkan GPU ceļi rūpējas par formām un atmiņas pārvietošanu. Verilog rada aparatūras jautājumus, kurus parastās lietojumprogrammu komandas reti izbauda pirms kafijas. Forge var izpētīt mērķa pazemināšanu, bet tas nevar noteikt organizatoriskās prioritātes. Ja pārnesamība ir svarīgāka par ātrumu vienā mērķī, pasakiet to. Ja latentums ir svarīgāks par atmiņu, pasakiet to. Ja reģistru spiediens ir praktiskais ierobežojums, pasakiet arī to. Dzinējs ir spēcīgs, nevis telepātisks.
Rezultāts būtu jāuztver kā pierādījumu pakete. Kandidāts, mērķis, pierādījuma ceļš, noraidītie pretpiemēri, aizmugure, etalona konteksts un atklātie ierobežojumi. Šī pakete ļauj cilvēkiem pieņemt saprātīgu lēmumu. Dažreiz uzvarošais gājiens ir pieņemt kandidātu. Dažreiz ir paturēt veco kodolu, jo pārnesamības kompromiss nav tā vērts. Dažreiz atklājums ir tāds, ka specifikācija bija pārāk vaļīga. Visi trīs iznākumi ir noderīgi. Tikai viens no tiem izskatās aizraujoši demonstrācijā, tāpēc demonstrācijas ir slikts inženierijas aizstājējs.
Mācība
Forge mācība ir vienkārša: veiktspēja nedrīkst apsteigt pierādījumu. Meklēšana ir spēcīga, bet meklēšanas dzinējs bez pārbaudes ir tikai ļoti enerģisks veids, kā radīt kļūdas. Pārbaude ir spēcīga, bet bez meklēšanas tā gaida, kamēr cilvēki tai atnesīs kandidātus. Forge apvieno abus un jautā, kādus kodolus mēs varam atklāt, kad mašīnai ir atļauts izpētīt, bet nav atļauts melot.
Tā ir pētniecība, ko ir vērts veikt. Tipētas specifikācijas, kandidātu meklēšana, pierādījumu piltuves, Pareto mērķi un aizmugures pazemināšana. Ne maģija. Ne produkta īsceļš. Veids, kā izveidot labāku mazu kodu ar pievienotiem pierādījumiem.