訪存地址依賴性分析技術 起底讓英特爾和蘋果賠數億美金的“752專利”

希卡力

近日，威斯康辛的地方法院宣布，蘋果在自家旗下的A系列處理器中侵犯威斯康辛大學麥迪遜分校的處理器微結構技術專利，被判賠償2.34億美元。七年前，英特爾也倒在了同一個專利上，支付了不明數額的巨款與威斯康辛大學麥迪遜分校達成和解。這項技術究竟是什么來頭，使得英特爾和蘋果在這一點上先后栽倒？本文將為讀者們進行追根究底的分析。

一項讓英特爾和蘋果先后栽倒的專利

美國專利編號US5781752（按照報道此案的慣例，以下簡稱為752專利），持有人為威斯康辛大學麥迪遜分校的研究基金會WARF。它如同幽靈一般在七年時間里兩度發起進攻，向法院起訴英特爾和蘋果兩家芯片設計巨頭侵犯自己所持有的752專利，并都在庭審中以壓倒性優勢擊潰了兩家巨頭的設計專家與龐大律師團隊的共同辯護，領走了數億美元的專利侵權賠償。在許多不明真相的報道和充滿誤解的傳言中，這只不過是一個專利流氓兩度敲詐巨頭公司得手的案例，然而事實真相遠非“專利流氓”四個字能夠概括。

從專利持有人的身份上來說，威斯康辛大學麥迪遜分校從上世紀80年代后就一直站在計算機體系結構與處理器微結構研究的最前沿，除了這一項專利以外還誕生了眾多影響力極為顯赫的研究成果，例如每一本教科書中都占有一席之地的3C-高速緩存命中率分析模型、體系結構研究中常用的瑞士軍刀“Gem5”模擬器、亂序多發射微結構中至關重要的重排序緩沖區（ROB）、解耦式結構等等都出自這所學校的前沿研究項目，旗下擁有多位已在圈內“開宗立派”的元老級學者。這一專利的發明者之一Gurindar Sohi便是威斯康辛麥迪遜最耀眼的明星之一，他在上世紀80年代中后期到90年代中后期的亂序多發射微結構框架的探索中做出了諸多杰出貢獻，從支持精確異常的亂序執行到高速緩存系統的非阻塞式設計，幾乎各個層面都有他留下的足跡。他也憑借這些貢獻拿到了2011年的計算機體系結構領域最高獎Eckert-Mauchly Award，可以說是一位與亂序多發射微結構框架一同成名的先驅。從這個層面上來說，威斯康辛一方的形象已經和“專利流氓”給人的固有印象相去甚遠。

再從技術層面上來看，752專利的標題為“面向并行處理計算機的基于表的數據推測電路”，申請于1996年12月26日，批準于1998年7月14日，是一項實打實的微結構專利技術，用于幫助處理器進行訪存地址依賴性分析。這個專利的背后積累了Gurindar Sohi和他指導的幾位博士生工作多年的研究成果，并非是一個花了幾天或者幾周簡單勾勒出爐，然后馬上申請專利坐等大魚上鉤的粗制濫造技術，而是一項貨真價實的技術研究成果。

在752專利這件事情上，除了“專利流氓”的說法不確外，此前的坊間傳聞和媒體報道充斥著其他誤解。由于申請年代的關系，專利標題中并沒有標明訪存地址依賴性分析的相關術語（memory disambiguation），而是代之以當時具備特殊含義的“數據推測”（data speculation）。可能受到“數據推測”這一關鍵詞的誤導，這項專利被傳聞與分支預測有關。事實上，處理器內部的推測性執行（speculation execution）技術有很多種，分支預測只是其中一種，分支預測往往被歸類為控制流推測，而數據推測是與控制流推測相獨立的另一種推測性執行，兩者同為推測性執行但是推測的目標和手段都不相同，并沒有什么直接關聯。并且準確來說，752專利的真實應用場景是在處理器核心內部的load/store單元當中，亦非標題中比較寬泛模糊的“并行處理計算機”。

為了更好地了解752專利的真正價值，介紹威斯康辛一方與英特爾和蘋果的法庭交鋒，做出一個更加公正的描述作鋪墊，我們需要首先介紹一些基本的訪存地址依賴性分析的知識，才能看清這兩次技術意味濃厚的爭論背后的真相。

訪存地址依賴性分析與752專利詳解

眾所周知，亂序執行處理器會維護一個大小不定（例如英特爾的SkyLake是212條指令）的窗口，在這個窗口內部，所有指令在執行資源允許、源數據準備停當的情況下可以打亂次序執行。但這樣的亂序操作方式在訪存指令上需要額外處理。

例如在圖2左側這樣的一段訪存序列上，如果我們能用某種方式在執行期間獲知addr1與addr2是不同的地址，那么我們就能夠把這段指令序列重新排序成右邊的樣子，將load指令提前到store指令之前開始執行，而不必等待store指令完成。但是如果addr1與addr2是相同的地址，我們就不能進行這樣的重排序了，而是只能依照左側的原始執行順序來操作，讓store指令將數據存儲在addr1上，然后load指令再從addr2（與addr1相等）上把剛剛存儲下來的新數據取回來使用，如果load指令被提前執行，就會取到addr2上的錯誤數據，使得程序執行出錯。

可以看到，依靠打亂指令執行次序發掘訪存指令的指令級并行度的關鍵在于，我們能否擁有這樣一種能力，在執行期間去動態地判斷每一對load/store指令之間是否存在這樣的地址依賴性，這被稱為訪存地址依賴性分析，是現代高性能微處理器的load/store單元的重要能力之一。

訪存地址依賴性分析主要有兩種做法，第一種是非推測式的，也就是在執行每一條指令之前，都已經對各個load/store指令的地址依賴性胸有成竹，保證執行中不會出錯，這種做法由于偏向保守，性能往往不佳。AMD的K6/K8和MIPS的R10000采用的就是這種設計。第二種是推測式的，在訪存指令發射前，對各個load/store指令的依賴性分析是沒有完成的，但是為了更高性能，允許沒有完成相關性分析的load指令推測性地開始裝載數據，這被稱為推測性訪存地址依賴性分析。有仿真測試表明，在一定的微結構設置參數下，這樣的推測性發射可以平均增加31%的IPC。2006年公布的Core微結構和1996年的DEC Alpha 21264都使用了這種設計。endprint

“推測性訪存依賴性分析”中的“推測”，指的是推測性地認為load指令與先前的store指令擁有截然不同的訪問地址。顯然，推測錯誤的情況是存在的，在依賴性分析完成后，若發現已經開始執行的load指令存在與先前的store指令的依賴關系，就要沖刷流水線，從錯誤發射的load指令處開始重新執行。這個方案是存在改良空間的。威斯康辛大學麥迪遜分校的Gurindar Sohi等人正是在這個基礎上做出了出色的分析和改進。

首先他們觀察到，在亂序執行窗口大小增加后，錯誤推測的數量會大大增加，錯誤率在1%～10%之間，并且隨著亂序執行窗口的增大而變得更加嚴重。進一步的分析發現，往往超過99.9%的錯誤推測都誕生在極少部分的load/store指令對上，如圖3，并且這些錯誤推測的發生點往往具有時間上的局部性。因此只要有很小的一張記錄表就能把最近發生的絕大多數的錯誤預測都記錄下來。基于這樣的測試和觀察，他們提出了日后被批準為752專利的改良設計。

首先，新設計增加了一張預測失誤表，記錄先前曾經有哪些load/store指令有過錯誤推測的情況，如果在同一對load/store指令上連續出現3次錯誤推測，就認為這一對指令上再進行推測已經無意義，不再進行推測轉而使用一種特別設計的同步機制，并為這種指令引入第二張表，被稱為同步表，被記錄在案的load/store指令對只能按照先store再load的次序執行，保證了執行正確性，也避免了沖刷流水線的開銷。這樣的設計有兩方面的好處，第一是降低了依賴性推測的錯誤率，另一個是降低了推測失敗后的開銷。

這個設計在模擬器上的初步測試結果是喜憂參半，好的一面是，specint 92/95上得到了5%～40%不等的加速，甚至在有的子項上逼近了理論最優值，但也有個別benchmark上，新設計并沒能幫助提升依賴性分析的性能，反而出現了大幅度的性能下降。

先戰英特爾

在1996年年底，我們剛才介紹的這項設計申請了專利，并于1998年年中獲得了通過，整套設計方案和初步模擬測試結果發表在了計算機體系結構國際頂級學術會議ISCA 1997上。2006年，英特爾發布了Core 2芯片，該專利的主要發明人Gurindar Sohi等人獲知Intel使用了這項技術，于是告上法庭。

從時間線上簡單來看，英特爾注定是必敗無疑，這項技術確實是Gurindar Sohi等人的研究成果，看上去賠錢是合情合理天經地義，但法庭審理過程中揭示的事情經過則頗為糾結。

1994年時，Gurindar Sohi教授憑借著先前的一系列杰出研究工作已然成名，吸引了英特爾一方的注意力，于是英特爾一方主動提出資助Gurindar Sohi教授的研究計劃。教授欣然同意，其手下掌管的研究小組從1994年開始接受英特爾的資助，總額約十萬美元，為期三年。在1994-1996年的三年資助中，英特爾始終沒有提及要在資助計劃中附帶對專利授權交換的要求，甚至在1996年的項目資助文件中主動聲明不染指相關權益，只在1994和1995年的資助文件中有一些模糊地要求“無障礙獲取相關研究成果”的條款。從開始接受資助到訴訟開始前，Gurindar Sohi教授和英特爾維持了非常好的伙伴關系。他多次應邀前往英特爾總部作報告介紹自己的研究成果，另一方面也接收來自英特爾的工程師來到自己門下攻讀博士學位，以及輸送畢業的博士返回英特爾繼續工作，從英特爾索要評選終身教職和政府研究基金所需的推薦信等，光看這段時間的合作關系幾乎很難想象到十年之后的對簿公堂。

在1994年資助開始時，Gurindar Sohi組的主要精力是放在一個被稱為multiscalar的模擬器搭建項目上，與英特爾一方報告的研究內容也主要基于這個模擬器項目，并未提及訪存依賴性分析的內容。到了1995年10月，Gurindar Sohi與他指導的學生們才開始考慮訪存依賴性分析，并在1996年3月完成了相關工作，于是訪存依賴性分析的內容只寫進了1996年，也就是最后一年的項目報告里面讓英特爾一方獲悉，并且當時沒有提及這項技術已經開始了申請專利的流程。據法庭審理查明，Gurindar Sohi多次在英特爾總部報告這項技術，并于1997年某個時候向英特爾表明過這項技術已經申請專利（當時尚未正式獲批）。2000年左右時，處于合作蜜月期的威斯康辛一派和英特爾甚至形成了私下的“君子協定”，Gurindar Sohi教授曾向英特爾一方的員工表示：他不會激進地追求專利，當這種情形不可避免時，則會提前通知英特爾—方。而英特爾一方則在沒有正式法律授權的情況下，于2001年開始了Core微結構的移動版Merom的開發工作，并于2003年左右（法庭審理中對這個時間點有爭議）開始著手Merom的訪存依賴性分析部分。在此期間威斯康辛麥迪遜一方曾主動發信提供752專利的授權，未獲英特爾重視，而當英特爾一方主動接觸威斯康辛麥迪遜一方希望得到多個專利的一攬子授權時，威斯康辛麥迪遜一方也并未同意在一攬子授權中包含752專利，于是英特爾的開發工作一直在沒有得到正式專利授權的情況下進行，直至事發。

事情鬧到對簿公堂，而英特爾卻由于種種原因一直沒有從自己昔日的合作伙伴處得到法律承認的授權，顯然已經處于十分不利的局面。在法庭交鋒中，英特爾開啟了一主一從兩條辯護戰線，主線是從1994-1995年的項目資助文件中尋找條款漏洞，試圖證明當時的項目資助是帶有交換專利授權條件的，另一條從線則是以技術為主，試圖引入DEC Alpha 21264的類似設計（已于1994年申請專利）證明752專利是無效專利，與先前的專利工作沖突。在筆者閱讀到的27頁的庭審記錄中，有一多半的篇幅是雙方在就主線問題來回拉鋸，遺憾的是英特爾一方在項目資助時多次明確表示過這是無條件的禮物性資金，僅有的要求是要投入到體系結構相關的研究當中并且英特爾可以獲取研究成果，并未附帶任何其他條件。這樣一來使得英特爾一方的主線辯護十分被動，主線掙扎良久宣告失敗以后，英特爾一方又開始轉向從線，但此時已經引發法官反感，因為主線實際上是在嘗試證明英特爾得到了某種形式的隱含授權，但從線卻是在證明752專利無效，某種程度上自相矛盾，于是從線的掙扎也沒過幾個回合就宣告失敗。英特爾一方最后選擇了支付數額不明的賠償金進行庭外和解。外媒報道這一賠償金的具體數額有上億美元。endprint

再戰蘋果

事件沉寂六年以后的2014年，威斯康辛麥迪遜—方再度得知蘋果的A7/A8/A9系列處理器中使用了752專利描述的技術，于是再度告上法院。近日宣判的結果是蘋果敗訴，賠償2.34億美元。

相對于與英特爾一方的訴訟，與蘋果一方的訴訟則明顯技術性更強，蘋果與752專利并無什么研究資助上的瓜葛，與Gurindar Sohi教授本人也沒有什么“君子協定”的感情牌可以打，于是從頭到尾只有一個辯護方向：通過引入其他先前相似專利來論證752專利無效，也就是英特爾曾經嘗試但是沒有成功的路線。其中最受關注的就是自七年前英特爾辯護團隊發現的、由DEC Alpha 21264采用并申請了專利的相似技術，專利號為US5619662（下文稱為662專利）。

英特爾和蘋果的辯護團隊先后注意到這一項專利的理由都是顯而易見的：它提供了與752專利近似的，記錄過往錯誤推測、躲避將來錯誤推測的功能。可以說英特爾的辯護團隊提前六年為蘋果發掘出了一根救命稻草，如果662專利的功能與752專利被認為重合，那么1994年申請的662專利將壓過威斯康辛麥迪遜一派于1996年申請的752專利，752專利會被判為無效專利，而蘋果就很有可能免于受罰。

法庭交鋒變成了雙方辯護律師和微結構設計專家來回拉鋸的戰場，問題的焦點最后歸結到一個核心上：752專利的設計，允許load/store單元持續性地動態檢測同一個load/store指令對的錯誤推測情況，在出現多次連續錯誤預測之后若是出現了多次連續正確預測，這個load/store指令對又可以被重新記錄為允許進行提前發射的指令對，若是多次連續正確預測后又出現了多次錯誤預測，還可以再踢回不允許提前發射的類別。而662專利的預測器則沒有提供這樣的持續檢測能力，任何一個指令對出現了一次錯誤推測以后，就會被永遠推進不允許提前發射的類別，直到許多個周期后記錄表進行一次周期性的清空操作。這樣一來662專利就沒有威脅到752專利的核心價值，這一關鍵性的差別使得法官心中的天平開始向威斯康辛麥迪遜傾斜，加上752專利中還提供了推測失敗時進行同步操作的第二層優化，這是此前其他專利都沒有涉及到的，于是法官最后采納了威斯康辛一方的意見，認為662專利只是752專利的相關前導工作，752專利的核心價值完好，蘋果一方構筑的防御就此崩潰。

誰對誰錯

相信看到這里，讀者們已經可以做出屬于自己的判斷。遺憾的是，目前公布的法庭文件中并未透露幾個關鍵問題的答案，例如威斯康辛麥迪遜一方是如何獲知蘋果和英特爾使用了自家專利的？蘋果和英特爾的處理器實現并不公開，有可能是威斯康辛一方通過自己的人脈關系網獲得的確認，或者有極少的可能在這一設計中埋藏了后門，以至于無論是蘋果還是英特爾都并未在庭審過程中作出任何抵賴，直接默認了自己的確使用了752專利的事實；另一個問題是威斯康辛一方先前與英特爾的甜蜜合作為何終止，最終導致雙方翻臉對簿公堂？圈內傳聞威斯康辛一方作為頂尖公立研究型大學，難以從聯邦政府獲得足夠預算，于是只能采取類似這樣合法但是不合情的方式獲取一些資金支持。從法律角度上看，威斯康辛一方這么做并無過錯，這一設計的確是威斯康辛麥迪遜的研究成果，完全受到法律保護，這也是法院兩度判決威斯康辛勝訴的原因。但是從情理上看，這一事例也有不良影響，一些圈內人士對此頗有微詞，認為威斯康辛作為一所享有盛譽的學校，從政府和社會獲取研究資金，其成果理應作為公開的知識，以開放的姿態回饋社會，而不是用專利的方式來爭奪金錢利益。752專利會不會在將來再度以這種形式出山，下一個被卷入官司的又會是哪家公司，仍未可知，但筆者相信時間會圍繞這項技術展開的一系列爭斗給出最公正徹底的評價。endprint