真正最難修復(fù)的 bug，其解決靠的已經(jīng)不是個(gè)人英雄主義的單打獨(dú)斗，而是全世界頂尖高手集體智慧的「飽和式搶救」了。

這種 bug 的解決，甚至能直接使其解決者自此一戰(zhàn)而揚(yáng)名天下。

1994 年著名的 Intel CPU 浮點(diǎn)運(yùn)算 bug，就是這樣的傳奇 bug。

緣起

當(dāng)時(shí)，Intel 為奔騰 CPU 的浮點(diǎn)除法指令 FDIV 加入了一種新型的實(shí)現(xiàn)。這是 Sweeney-Robertson-Tocher（SRT）算法的一種高性能變體，依賴了一個(gè)共有 2048 項(xiàng)的硬件查找表。因?yàn)檫@種算法只會(huì)訪問整個(gè) 128x16 尺寸查找表中的一個(gè)梯形子集，所以這 2048 項(xiàng)中只有略多于一半的項(xiàng)會(huì)被用到。由于一些意外，這 1066 項(xiàng)中有 5 項(xiàng)的值被錯(cuò)誤地設(shè)置為 0（而不是正確的 2），因此可能導(dǎo)致運(yùn)算結(jié)果的錯(cuò)誤。但是，這些錯(cuò)誤的索引只會(huì)在極少數(shù)情況下被訪問到，以至于這個(gè)問題沒有被 Intel 研發(fā)流程中的隨機(jī)測(cè)試所發(fā)現(xiàn)。更可怕的是，在除法算法的前 8 個(gè)執(zhí)行步驟中，錯(cuò)誤的這幾項(xiàng)還永遠(yuǎn)不會(huì)被訪問到，因此錯(cuò)誤結(jié)果與真實(shí)結(jié)果之間僅有輕微的差異——這種差異對(duì)于高精度計(jì)算來說可能非常關(guān)鍵，但普通場(chǎng)景下幾乎不可能發(fā)現(xiàn)（據(jù)稱概率是每 90 億次運(yùn)算出現(xiàn)一次，相當(dāng)于七百年一遇）。

這是人們事后從上帝視角給出的復(fù)盤。假如你根本不知道硬件電路中埋著這樣的一個(gè)雷，你覺得寫應(yīng)用層業(yè)務(wù)遇到問題時(shí)該從何下手呢？

察覺

這個(gè) bug 雖然非常隱蔽，但卻沒有躲過美國林奇堡學(xué)院 Thomas Nicely 教授善于察覺要素的眼睛。他在多臺(tái)計(jì)算機(jī)上運(yùn)行同樣的算法來對(duì)孿生質(zhì)數(shù)的商進(jìn)行求和時(shí)，發(fā)現(xiàn)計(jì)算結(jié)果在不同機(jī)器之間存在差異。

Nicely 花了幾個(gè)月的時(shí)間（注意時(shí)間單位是月）來檢查可能的差異原因，最終認(rèn)為問題來自于使用了奔騰 CPU 的系統(tǒng)。發(fā)現(xiàn)問題之后，他在 1994 年的 10 月 24 日（程序員節(jié)）向 Intel 提出了反饋，并于 10 月 30 日向其他的一些聯(lián)系人發(fā)送了報(bào)告問題的電子郵件，其中有一名收件人將其內(nèi)容轉(zhuǎn)發(fā)到了 CompuServe 網(wǎng)絡(luò)上。電子工程時(shí)報(bào)的記者 Alex Wolfe 發(fā)現(xiàn)了這個(gè)帖子，并將其轉(zhuǎn)發(fā)給了挪威工程師 Terje Mathisen。在收到消息后的幾個(gè)小時(shí)內(nèi)，Mathisen 就成功復(fù)現(xiàn)了 Nicely 教授的例子。他用匯編語言寫了一個(gè)簡(jiǎn)單的測(cè)試用例，于 11 月 3 日在新聞組 comp.sys.intel 內(nèi)發(fā)布了一系列關(guān)于 FDIV 指令錯(cuò)誤的帖子。一天后，德國的 Andreas Kaiser 找到了 20 多個(gè)特殊的數(shù)字，這些數(shù)字的倒數(shù)在奔騰 CPU 上的計(jì)算精度只達(dá)到了單精度（也就是 32 位 float 的水平，精確到小數(shù)點(diǎn)后 7 位）。

定位

與此同時(shí)，加州 Vitesse 半導(dǎo)體公司的 FPU（浮點(diǎn)單元）設(shè)計(jì)師 Tim Coe 從 Kaiser 給出的列表中找到了線索，分析推斷出了 Intel 的 FPU 設(shè)計(jì)師們是如何設(shè)計(jì)除法電路的。他正確地推測(cè)，奔騰 CPU 的除法指令采用了基數(shù)為 4 的 SRT 算法，每個(gè)時(shí)鐘周期會(huì)產(chǎn)生兩個(gè) bit 的商。這樣可以讓奔騰 CPU 的除法速度達(dá)到過去相同時(shí)鐘速率下 Intel 芯片的兩倍。

Coe 創(chuàng)建了一個(gè)模型，以此解釋了 Kaiser 所報(bào)告的誤差。他還發(fā)現(xiàn)，如果對(duì)于分子不為 1 的除法運(yùn)算，這還可能帶來更大的相對(duì)誤差?；谶@個(gè)模型，他找到了一對(duì)七位整數(shù)，它們的商 4195835/3145727 可能是最壞情況下的錯(cuò)誤實(shí)例。Coe 于 11 月 14 日將這個(gè)例子發(fā)布到了 comp.sys.intel 新聞組上。

在 Coe 發(fā)帖前幾天，美國麻省一家公司的老板 Cleve Moler 從另一個(gè)渠道得知了 FDIV 的錯(cuò)誤。Moler 起初只是對(duì)此感到好奇，并未實(shí)際參與。但 Coe 發(fā)布的問題定位，使 Moler 的興趣大大提升。11 月 15 日，Moler 在新聞組上發(fā)帖，總結(jié)了截至當(dāng)時(shí) Nicely 和 Coe 各自案例中的已知情況，并找到了這兩種情況下的 bug 規(guī)律，即除數(shù)都略少于 3 乘以 2 的某個(gè)整數(shù)次冪——這個(gè) Moler 可不是土老板，他當(dāng)過斯坦福的數(shù)學(xué)教授。

舉個(gè)例子，2^20 = 1048576，而上面的除數(shù) 3145727 除以 3，則是 1048575.666666……像不像是給數(shù)學(xué)家玩的密室逃脫游戲？

輿情

11 月 7 日，參與反饋 bug 的 Wolfe 在電子工程時(shí)報(bào)上報(bào)道了此事，關(guān)于奔騰 CPU 這個(gè) bug 的消息，迅速在互聯(lián)網(wǎng)上流傳了開來。

11 月 22 日，美國 NASA 噴氣推進(jìn)實(shí)驗(yàn)室（JPL）的兩位工程師向采購部門提出建議，認(rèn)為實(shí)驗(yàn)室應(yīng)該停止訂購使用奔騰芯片的計(jì)算機(jī)。CNN 的記者聽說了 JPL 的決定，于是找到 Moler 進(jìn)行了采訪。當(dāng)天晚上，CNN 在電視節(jié)目上報(bào)道了奔騰 CPU 的這個(gè) bug，將事態(tài)升級(jí)為了國民級(jí)新聞。到了兩天之后的感恩節(jié)，包括紐約時(shí)報(bào)和波士頓環(huán)球報(bào)在內(nèi)的主流媒體都對(duì)此進(jìn)行了報(bào)道。在接下來的幾周內(nèi)，更是出現(xiàn)了數(shù)百篇關(guān)于此事的文章。

注意這時(shí)整個(gè)社會(huì)都在 BB，但這個(gè) bug 仍然沒有解決。

拆彈

基于自己找到的規(guī)律，Moler 開始與 Coe、Mathisen、Peter Tang（來自美國阿貢國家實(shí)驗(yàn)室），以及 Intel 的幾位軟硬件工程師合作，嘗試解決這個(gè) FDIV 錯(cuò)誤。只要解決了這個(gè) bug，還能一并解決掉奔騰 CPU 上由此產(chǎn)生的片上正切、正交和求余指令的衍生 bug。到 12 月 5 日，他們開發(fā)出了一種巧妙的修復(fù)方法：檢查除數(shù)有效位部分的的高四位（浮點(diǎn)數(shù)有效位部分即 fraction，如下圖示例中的紅色部分），如果它們是 0001、0100、0111、1010 或 1101，那么就在執(zhí)行除法運(yùn)算之前，將除數(shù)和被除數(shù)都同乘以 15/16。在這五種情況下，這種乘以 15/16 的效果都能使除數(shù)從「危險(xiǎn)」?fàn)顟B(tài)轉(zhuǎn)入「安全」?fàn)顟B(tài)。這時(shí)可以保證縮放后操作數(shù)的商，始終能與原始操作數(shù)的正確商相同。幾天后他們進(jìn)一步優(yōu)化了算法，只有當(dāng)除數(shù)有效位的八個(gè)高位是 00011111、01001111、01111111、10101111 或 11011111 時(shí)，才將操作數(shù)按 15/16 縮放，從而大大減少了額外的運(yùn)算。這項(xiàng)優(yōu)化技術(shù)被公布到了新聞組，可供全社會(huì)無償自由使用。

32 位單精度浮點(diǎn)數(shù)結(jié)構(gòu)，后 23 位為有效位

于是，報(bào)道「該公司修復(fù)了 Intel 奔騰 CPU 浮點(diǎn)數(shù) bug」的新聞，迅速登上了包括紐約時(shí)報(bào)在內(nèi)的各大主流媒體。

這家當(dāng)時(shí)還名不見經(jīng)傳的小公司，由此正式出現(xiàn)在了公眾視野之中。

總結(jié)

這個(gè) FDIV bug 事件，實(shí)在有眾多傳奇之處：

• 極其隱蔽的 bug 來源

• 極長的定位時(shí)間

• 世界各地高手（數(shù)學(xué)家與軟硬件工程師）跨領(lǐng)域的接力式努力

• 堪稱奇技淫巧的黑魔法 fix

• 轟動(dòng)性的媒體傳播效應(yīng)

這簡(jiǎn)直是個(gè)教科書級(jí)的程序員題材電影劇本啊……

只剩下最后一個(gè)問題了，解決 bug 的這家公司到底是什么呢？

你可能早已經(jīng)看出來了，它就是出品 MATLAB 的 MathWorks。

對(duì)，就是那個(gè)中國限購的 MATLAB——很多年以后，它將以另一種形式再次出現(xiàn)在中國公眾的茶余飯后談資中，但那就是另一個(gè)話題了。

你看，我們天天講的自主研發(fā)，可真不止是件喊口號(hào)的事情呀。

后記

Intel 因?yàn)檫@個(gè) FDIV bug 事件虧了近 5 億美元，但 MATLAB 則成為了此事的最大贏家。1994 年的 MathWorks 只是個(gè) 200 多人規(guī)模的小公司，而今天它已經(jīng)是有超過 5000 名員工的世界巨頭了。

在 MathWorks 成立近 40 年后，當(dāng)年親自下一線修 bug 的美國工程院院士 Moler，又自己動(dòng)手為 MATLAB 語言撰寫了歷史研究文獻(xiàn)《A History of MATLAB》。在這份去掉參考文獻(xiàn)約 40 多頁的資料中，對(duì)這個(gè) FDIV bug 的介紹橫跨了整整 3 頁。這個(gè) bug 的難度與歷史地位，由此可見一斑。

《A History of MATLAB》的 4.5 節(jié)是本文的主要內(nèi)容來源。