访存地址依赖性分析技术 起底让英特尔和苹果赔数亿美金的“752专利”

　　近日，威斯康辛的地方法院宣布，苹果在自家旗下的A系列处理器中侵犯威斯康辛大学麦迪逊分校的处理器微结构技术专利，被判赔偿2.34亿美元。七年前，英特尔也倒在了同一个专利上，支付了不明数额的巨款与威斯康辛大学麦迪逊分校达成和解。这项技术究竟是什么来头，使得英特尔和苹果在这一点上先后栽倒？本文将为读者们进行追根究底的分析。

　　一项让英特尔和苹果先后栽倒的专利

　　美国专利编号US5781752（按照报道此案的惯例，以下简称为752专利），持有人为威斯康辛大学麦迪逊分校的研究基金会WARF。它如同幽灵一般在七年时间里两度发起进攻，向法院起诉英特尔和苹果两家芯片设计巨头侵犯自己所持有的752专利，并都在庭审中以压倒性优势击溃了两家巨头的设计专家与庞大律师团队的共同辩护，领走了数亿美元的专利侵权赔偿。在许多不明真相的报道和充满误解的传言中，这只不过是一个专利流氓两度敲诈巨头公司得手的案例，然而事实真相远非“专利流氓”四个字能够概括。

　　从专利持有人的身份上来说，威斯康辛大学麦迪逊分校从上世纪80年代后就一直站在计算机体系结构与处理器微结构研究的最前沿，除了这一项专利以外还诞生了众多影响力极为显赫的研究成果，例如每一本教科书中都占有一席之地的3C-高速缓存命中率分析模型、体系结构研究中常用的瑞士军刀“Gem5”模拟器、乱序多发射微结构中至关重要的重排序缓冲区（ROB）、解耦式结构等等都出自这所学校的前沿研究项目，旗下拥有多位已在圈内“开宗立派”的元老级学者。这一专利的发明者之一Gurindar Sohi便是威斯康辛麦迪逊最耀眼的明星之一，他在上世纪80年代中后期到90年代中后期的乱序多发射微结构框架的探索中做出了诸多杰出贡献，从支持精确异常的乱序执行到高速缓存系统的非阻塞式设计，几乎各个层面都有他留下的足迹。他也凭借这些贡献拿到了2011年的计算机体系结构领域最高奖Eckert–Mauchly Award，可以说是一位与乱序多发射微结构框架一同成名的先驱。从这个层面上来说，威斯康辛一方的形象已经和“专利流氓”给人的固有印象相去甚远。

　　再从技术层面上来看，752专利的标题为“面向并行处理计算机的基于表的数据推测电路”（Table Based Data Speculation Circuit for Parallel Processing Computer），申请于1996年12月26日，批准于1998年7月14日，是一项实打实的微结构专利技术，用于帮助处理器进行访存地址依赖性分析。这个专利的背后积累了Gurindar Sohi和他指导的几位博士生工作多年的研究成果，并非是一个花了几天或者几周简单勾勒出炉，然后马上申请专利坐等大鱼上钩的粗制滥造技术，而是一项货真价实的技术研究成果。

　　在752专利这件事情上，除了“专利流氓”的说法不确外，此前的坊间传闻和媒体报道充斥着其他误解。由于申请年代的关系，专利标题中并没有标明访存地址依赖性分析的相关术语(memory disambiguation)，而是代之以当时具备特殊含义的“数据推测”(dataspeculation)。可能受到“数据推测”这一关键词的误导，这项专利被传闻与分支预测有关。事实上，处理器内部的推测性执行(speculation execution)技术有很多种，分支预测只是其中一种，分支预测往往被归类为控制流推测，而数据推测是与控制流推测相独立的另一种推测性执行，两者同为推测性执行但是推测的目标和手段都不相同，并没有什么直接关联。并且准确来说，752专利的真实应用场景是在处理器核心内部的load/store单元当中，亦非标题中比较宽泛模糊的“并行处理计算机”。

　　为了更好地了解752专利的真正价值，介绍威斯康辛一方与英特尔和苹果的法庭交锋，做出一个更加公正的描述作铺垫，我们需要首先介绍一些基本的访存地址依赖性分析的知识，才能看清这两次技术意味浓厚的争论背后的真相。

　　访存地址依赖性分析与752专利详解

　　众所周知，乱序执行处理器会维护一个大小不定（例如英特尔的SkyLake是212条指令）的窗口，在这个窗口内部，所有指令在执行资源允许、源数据准备停当的情况下可以打乱次序执行。但这样的乱序操作方式在访存指令上需要额外处理。

　　例如在图2左侧这样的一段访存序列上，如果我们能用某种方式在执行期间获知ad dr1与ad dr2是不同的地址，那么我们就能够把这段指令序列重新排序成右边的样子，将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 Alpha21264都使用了这种设计。

　　“推测性访存依赖性分析”中的“推测”，指的是推测性地认为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年年中获得了通过，整套设计方案和初步模拟测试结果发表在了计算机体系结构国际顶级学术会议I SCA 1997上。2006年，英特尔发布了Core 2芯片，该专利的主要发明人GurindarSohi等人获知Intel使用了这项技术，于是告上法庭。

　　从时间线上简单来看，英特尔注定是必败无疑，这项技术确实是Gurindar Sohi等人的研究成果，看上去赔钱是合情合理天经地义，但法庭审理过程中揭示的事情经过则颇为纠结。

　　1994年时，Gurindar Sohi教授凭借着先前的一系列杰出研究工作已然成名，吸引了英特尔一方的注意力，于是英特尔一方主动提出资助Gurindar Sohi教授的研究计划。教授欣然同意，其手下掌管的研究小组从1994年开始接受英特尔的资助，总额约十万美元，为期三年。在1994-1996年的三年资助中，英特尔始终没有提及要在资助计划中附带对专利授权交换的要求，甚至在1996年的项目资助文件中主动声明不染指相关权益，只在1994和1995年的资助文件中有一些模糊地要求“无障碍获取相关研究成果”的条款。从开始接受资助到诉讼开始前，Gurindar Sohi教授和英特尔维持了非常好的伙伴关系。他多次应邀前往英特尔总部作报告介绍自己的研究成果，另一方面也接收来自英特尔的工程师来到自己门下攻读博士学位，以及输送毕业的博士返回英特尔继续工作，从英特尔索要评选终身教职和政府研究基金所注定是必败无疑，这项技术确实是Gurindar Sohi等人的研究成果，看上去赔钱是合情合理天经地义，但法庭审理过程中揭示的事情经过则颇为纠结。

　　1994年时，GurindarSohi教授凭借着先前的一系列杰出研究工作已然成名，吸引了英特尔一方的注意力，于是英特尔一方主动提出资助Gurindar Sohi教授的研究计划。教授欣然同意，其手下掌管的研究小组从1994年开始接受英特尔的资助，总额约十万美元，为期三年。在1994-1996年的三年资助中，英特尔始终没有提及要在资助计划中附带对专利授权交换的要求，甚至在1996年的项目资助文件中主动声明不染指相关权益，只在1994和1995年的资助文件中有一些模糊地要求“无障碍获取相关研究成果”的条款。从开始接受资助到诉讼开始前，Gurindar Sohi教授和英特尔维持了非常好的伙伴关系。他多次应邀前往英特尔总部作报告介绍自己的研究成果，另一方面也接收来自英特尔的工程师来到自己门下攻读博士学位，以及输送毕业的博士返回英特尔继续工作，从英特尔索要评选终身教职和政府研究基金所却由于种种原因一直没有从自己昔日的合作伙伴处得到法律承认的授权，显然已经处于十分不利的局面。在法庭交锋中，英特尔开启了一主一从两条辩护战线，主线是从1994-1995年的项目资助文件中寻找条款漏洞，试图证明当时的项目资助是带有交换专利授权条件的，另一条从线则是以技术为主，试图引入DEC Alpha 21264的类似设计（已于1994年申请专利）证明752专利是无效专利，与先前的专利工作冲突。在笔者阅读到的27页的庭审记录中，有一多半的篇幅是双方在就主线问题来回拉锯，遗憾的是英特尔一方在项目资助时多次明确表示过这是无条件的礼物性资金，仅有的要求是要投入到体系结构相关的研究当中并且英特尔可以获取研究成果，并未附带任何其他条件。这样一来使得英特尔一方的主线辩护十分被动，主线挣扎良久宣告失败以后，英特尔一方又开始转向从线，但此时已经引发法官反感，因为主线实际上是在尝试证明英特尔得到了某种形式的隐含授权，但从线却是在证明752专利无效，某种程度上自相矛盾，于是从线的挣扎也没过几个回合就宣告失败。英特尔一方最后选择了支付数额不明的赔偿金进行庭外和解。外媒报道这一赔偿金的具体数额有上亿美元。

　　再战苹果

　　事件沉寂六年以后的2014年，威斯康辛麦迪逊一方再度得知苹果的A7/A8/A9系列处理器中使用了752专利描述的技术，于是再度告上法院。近日宣判的结果是苹果败诉，赔偿2.34亿美元。

　　相对于与英特尔一方的诉讼，与苹果一方的诉讼则明显技术性更强，苹果与752专利并无什么研究资助上的瓜葛，与GurindarSohi教授本人也没有什么“君子协定”的感情牌可以打，于是从头到尾只有一个辩护方向：通过引入其他先前相似专利来论证752专利无效，也就是英特尔曾经尝试但是没有成功的路线。其中最受关注的就是自七年前英特尔辩护团队发现的、由DECAlpha21264采用并申请了专利的相似技术，专利号为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专利会不会在将来再度以这种形式出山，下一个被卷入官司的又会是哪家公司，仍未可知，但笔者相信时间会围绕这项技术展开的一系列争斗给出最公正彻底的评价。

　　文、图/希卡力