第118章 大杀器（1/2）

第二张图，是ps-kernelv0.2的工具链图。

关於软体与底层微內核的博弈，是从废土第五年正式打响的。

江临没有再碰sort5。

那个问题已经在陈启明的办公室里演示过。

办公室那半个小时的惊艷，解决的仅仅是学术界最基础的问题：“这条路在理论上能不能走通”

第九次废土要解决的，是：“这套系统，到底能不能放大”

现实总是毫不留情。

第一版试图规模化的搜索器，在第六年迎来了轰轰烈烈的全面崩溃。

系统崩溃的原因，並非零一验证器证明速度太慢，也不是他建立的硬体代价模型不够精確。

而是候选指令还没有来得及排队进入验证器，前端的生成器就已经因为组合爆炸，將状態空间膨胀到了一个工作站內存根本无法承受的黑洞级別。

sort8还能靠著压榨交换文件的i/o勉强跑完。

可一旦触及dian9，状態树就开始扭曲变形。

等他试著展开一个哪怕附加了限制条件的-k小內核时，生成器吐出的垃圾候选代码在几个小时內把几块tb级企业硬碟彻底写满，交换分区被打穿，日誌系统开始报错，最终进程被ookiller杀掉，工作站在持续i/o雪崩中卡死。

这次失败，不仅没有让江临沮丧，反而让他感到兴奋。

裴礪的判断是精准的。

真正挡在ps-kernel前面的，不是某一段晦涩难懂的代码，而是不可阻挡的数学规律。

状態空间爆炸。

第八年，江临果断在代码库中按下刪除键，將枚举指令序列这条传统的暴力穷举旧路线抹除。

搜索的核心对象，被他从具体的代码改成了抽象的语义等价类。

不再让生成器像个傻子一样去枚举每一种可能的寄存器分配或指令顺序。

而是引入等价图，也就是e-graph式的表示方法，再叠加规范化哈希、对称归约和支配关係剪枝。

在同一组数学输入输出语义下，那些能够被证明只差在寄存器命名、无依赖指令重排、冗余中间量或局部等价重写上的候选序列，会被摺叠到同一个状態节点里。

生成器吐出的不再是一行行c代码或汇编。

而是一张巨大的状態图。

每一个节点，不再代表一段具体代码，而代表一组输入输出语义相同、並且已经被规范化的中间状態。

每一条边，才真正对应著一次实质性的，可落地的底层原语变换或机器指令变换。

搜索空间，在废土的第八年，第一次被从物理意义上狠狠压了下来。

第十一年，为了进一步对抗时间的消耗，江临在系统底层加入了证据缓存机制。

过去，每一次搜索遇到相似的结构，系统都要重新调用z3求解器去证明一次。

现在，所有被验证过的等价状態，其证明过程会被序列化后永久存储。

局部原语的证明可以像搭积木一样被復用。

底层子网络的正確性证明，可以直接作为更大规模网络组成部分的前置证据。

ps-kernel开始发生蜕变。

它不再像一个每次都从头推到尾的笨拙搜索器，开始像一台拥有记忆，会自动积累中间定理的智能证明机器。

第十三年，江临將庞大而混沌的证明系统挥刀斩断，清晰地拆分成三层。

第一层，抽象原语层。

排序、选择、求秩、中位数、-k等微內核，首先在纯粹的数学语义上被定义得滴水不漏。

输入的数据分布是什么

输出的排序稳定性要求是什么

是否允许数组中存在重复值

算法边界是否存在哨兵机制

最重要的是，整数比较、浮点运算中的非数字以及带符號零的特殊值处理，必须在这一层就明確分流。

第二层，源码与中间表示层。

到了这一层，无论是c代码、llvir，还是手工编写的trsic內联函数，都绝对不允许用一句轻飘飘的它看起来等价糊弄过去。

c语言標准中恶名昭彰的未定义行为、有符號整数溢出的未定义行为、无符號整数的模迴绕语义、不同宽度整数转换时的截断规则、浮点比较中的nan传播、正负零排序、捨入模式、异常標誌，以及不同平台对denoral数的处理，全都要在这一层被数学逻辑无情地拆开揉碎，確保ir在被声明的语义子集內，与上层抽象语义保持一致。

第三层，机器码层。

本章未完，点击下一页继续阅读。