算力差两千倍的象棋惨败：麻省理工借国家级超算下棋，为什么反而逼出了现代操作系统的调度基石？

借了一台拥有 1824 个核心的超级计算机去下象棋，居然输给了一台普通家用电脑。

这是 1995 年世界计算机国际象棋锦标赛上的真实场面。

麻省理工为了拿下这个冠军，特意从桑迪亚国家实验室借来了当时全球算力第二的超算 Intel Paragon。

对面坐着的对手，跑在一台普通人书房里常见的个人电脑上，处理器只是一颗单核的英特尔奔腾 90。

一边是 182 GFLOPS 的国家级庞然大物，一边是 0.09 GFLOPS 的家用芯片。

两边的算力整整差了 2000 倍。

结果加赛一局定胜负，麻省理工这台超级巨兽被当场击溃。

麻省理工虽然输掉了那场比赛，但他们为了对付那台超算折腾出来的一套调度机制，却赢下了后来的整个软件工业。

这件事情要从多核计算的一个老毛病说起。

让 1824 个核心一起下棋，最卡手的地方不在算力大小，在怎么分工。

国际象棋的计算是一棵极不规则的搜索树。

有的分支走一步就被将军吃掉，计算立刻掐断；

有的分支两边反复纠缠，能向下蔓延出几百亿种走法。

在真正算到那一步之前，没有任何人能预判哪条路线简单，哪条路线是个无底洞。

这就带来了一个巨大的麻烦：这 1824 个核心怎么分活？

如果设一个总调度员，在中间给每个核心发号施令。

1800 多个核心每算完一步，都得跑回来找总调度员领新任务，光是排队通信，网络当场就瘫痪了。

那如果不设总调度员，在开局时把棋盘切成 1824 份，各自分一块去算呢？

更行不通。

分到简单死局的核心，一秒钟就算完了，只能坐在那里干等；

分到复杂局面的核心，一个人算到冒烟也算不完。

绝大部分算力都在无所事事地摸鱼。

麻省理工的查尔斯·雷瑟森团队想出了一个损招：工作窃取。

既然派活派不匀，那就彻底取消中央派活，让核心之间互相偷活。

他们给每个核心都配了一个双端队列。

平时大家各忙各的。

一个核心算出了新的棋局分支，就顺手塞进自己的队列底部。

自己继续干活的时候，优先从底部取最新的任务出来算，这叫后进先出。

为什么先算最新的？

因为刚放进去的任务，棋盘数据还在这个核心的缓存里热乎着，不需要重新去内存搬数据，算起来最顺手。

那如果一个核心手头的任务全部算完了呢？

它立刻变身成小偷。

它在系统里随机抓一个还在忙碌的核心，摸到对方队列的最顶端，偷一个任务出来自己跑。

注意这个细节：它不偷最新的任务，专挑对方手里最老的那批任务下手。

为什么要偷最老的？

因为越早生成的任务，在整棵决策树上的位置越高，底下连着的子分支就越多。

偷走一个大分支，足够这个闲着的核心埋头苦算很久，省得它一会儿又得跑出来偷第二次。

这套设计最精妙的地方，是调度成本全由闲人承担。

在传统系统里，正在干活的核心要停下来汇报进度、协调分配，频繁被打断。

但在工作窃取机制里，忙碌的核心连头都不用抬，只需要全速算自己的栈。

去找活、挑目标、发网络请求的所有麻烦，全部由那个闲着的核心自己扛。

反正你也是闲着的，你花时间去偷活，一点都不浪费有效的计算能力。

这套机制被麻省理工做成了一套名为 Cilk 的并行系统，装上了桑迪亚实验室的超算。

1824 个核心全速运转，互相偷活，把整台超算的效率压榨到了极限。

小组赛一路横扫，积分直接并列第一，把 IBM 深蓝的前身都挤到了身后。

可到了加赛决胜局，怎么就败给了一台奔腾 90 电脑呢？

因为国际象棋不是纯粹的算力比拼。

麻省理工这帮人是顶尖的计算机科学家，全部心思都在怎么把 1824 个芯片调度好、怎么让代码在多核之间偷活。

而对手 Fritz 3 的开发者弗朗斯·莫什，是个钻研了十几年棋谱的象棋专家。

Fritz 3 的算力虽然弱得可怜，但它的开局库、局面评估函数和走子逻辑，调校得极其老辣。

麻省理工的算法算得极深、极快，却在几个关键走法上选了不够高明的棋步；Fritz 算力虽小，每一步都踩在象棋大师的经验路线上。

麻省理工最终输掉了世界冠军的奖杯。

但三十年过去，那台拿了冠军的奔腾 90 电脑，早就进了博物馆；

麻省理工在那台超算上逼出来的工作窃取算法，却悄悄成了现代计算机工业的基石。

今天不管是 Go 语言底层的并发调度器、Java 里的并行计算框架，还是主流浏览器里的脚本引擎，底层骨架里依然跑着这套当年的偷活机制：

忙着的核心专心干活，闲下来的核心四处偷活。

棋赛输了，但这个偷活的机制，撑起了今天整个多核软件的世界。