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

?？?/p>

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

一項(xiàng)讓英特爾和蘋果先后栽倒的專利

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

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

再從技術(shù)層面上來看，752專利的標(biāo)題為“面向并行處理計(jì)算機(jī)的基于表的數(shù)據(jù)推測電路”，申請于1996年12月26日，批準(zhǔn)于1998年7月14日，是一項(xiàng)實(shí)打?qū)嵉奈⒔Y(jié)構(gòu)專利技術(shù)，用于幫助處理器進(jìn)行訪存地址依賴性分析。這個(gè)專利的背后積累了Gurindar Sohi和他指導(dǎo)的幾位博士生工作多年的研究成果，并非是一個(gè)花了幾天或者幾周簡單勾勒出爐，然后馬上申請專利坐等大魚上鉤的粗制濫造技術(shù)，而是一項(xiàng)貨真價(jià)實(shí)的技術(shù)研究成果。

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

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

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

眾所周知，亂序執(zhí)行處理器會維護(hù)一個(gè)大小不定（例如英特爾的SkyLake是212條指令）的窗口，在這個(gè)窗口內(nèi)部，所有指令在執(zhí)行資源允許、源數(shù)據(jù)準(zhǔn)備停當(dāng)?shù)那闆r下可以打亂次序執(zhí)行。但這樣的亂序操作方式在訪存指令上需要額外處理。

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

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

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

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

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

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

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

先戰(zhàn)英特爾

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

從時(shí)間線上簡單來看，英特爾注定是必?cái)o疑，這項(xiàng)技術(shù)確實(shí)是Gurindar Sohi等人的研究成果，看上去賠錢是合情合理天經(jīng)地義，但法庭審理過程中揭示的事情經(jīng)過則頗為糾結(jié)。

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

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

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

再戰(zhàn)蘋果

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

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

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

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

誰對誰錯

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