透过专利看微处理器的技术发展(六)

摘要：本文在大量专利文献调研的基础上，通过跟踪Cache技术的专利，对Cache的起源、分层存储思想和Cache的几个优化技术进行了深入分析。这些优化技术包括Nonblocking Cache技术、Trace Cache技术、Victim Cache技术。通过对具有里程碑意义的几件专利的分析，为相关产品研发提供线索和思路。

关键词：专利文献；Cache；技术演进

Technology Development of Microprocessor from Patent（VI）

― Technology Development on Cache Patent

ZHANG Xu1，2, WU Xiao-dao1, XIE Xue-jun1

（1 Ministry of Industry and Information Technology Software

and Integrated Circuit Promotion Center, Beijing 100038, China；

2 Beijing Institute of Technology，School of control theory and control engineering, Beijing 100086, China）

Abstract: In this paper, a technology-depth analysis on Cache is made based on a series of patents of Cache. Through tracing some specific patents based on the search of a large number of patents, several important Cache related patents are introduced, including origin of Cache, hierarchical memory and Cache optimization technologies such as Trace Cache, Victim Cache and Nonblocking Cache. By analyzing the typical Cache patents, clues for new product development are provided.

Keywords: Patent document; Cache; Technology evolution

1引言

高速缓冲存储器（Cache）技术，主要是为了解决高速中央处理单元（CPU）和低速动态随机存储器（DRAM）内存之间速度匹配的问题，是提高系统性能，降低系统成本而采用的一项技术。典型的Cache如图1所示。

随着半导体加工工艺水平的不断提高，CPU和存储器的性能都有了很大提高。

CPU频率的提高，必然要求存储器存取速度提高和存储容量的增大。主存储器DRAM的发展，其容量提高较快，但读取时间的提高往往滞后，那么CPU与主存储器的不匹配随之产生，因此成为系统性能提升的瓶颈。二十年来，CPU设计的问题之一就是解决高速CPU和低速DRAM之间的平衡或匹配问题，在CPU和DRAM之间加入高速缓冲存储器（Cache）是一个被广泛使用的解决方案。

本文在分析Cache专利的基础上，寻找Cache技术的起源，发掘早期Cache技术的重要变革，探讨Cache设计中的关键优化技术的演进过程，特别研究了不同阶段关键技术的创新点，预测Cache优化技术发展趋势。

2Cache技术综述

Cache技术本质是以有效的方法构建基于存储器层次结构的高效存储系统。其基本思想基于局部性原理（空间局部性和时间局部性）。

Cache的组织技术主要有映射技术、多级Cache技术。映射技术即主存中的数据如何对应到Cache中。有三种对应方式：直接映射，全相联映射和组相连映射；多级Cache技术主要研究Cache的级数和每级Cache的容量。最新的处理器一般是将Cache集成到芯片内部，部分处理器甚至集成了两级到三级Cache。典型的如Intel的奔腾4（Pentium P4）处理器集成两级Cache[1]。

Cache的缺失替换技术基于：CPU访问的主存地址内容为保存在Cache中从而发生缺失，此时需从主存中调取相应数据块到Cache中，若Cache空间已满，需替换掉陈旧的信息块。替换策略通常有：先进先出（FIFO）法、随机法、最近最少使用（LRU）算法。

Cache一致性技术：在多处理器或多核处理器系统中，每个处理器或核有各自的Cache，但处理器一般共享主存储器，不仅Cache与共享存储器中同一数据拷贝可能不一致，而且由于多个处理机异步的相互独立操作，也使多个Cache中同一份存储块的拷贝可能不一致，从而出现了Cache一致性问题。为解决Cache与主存的不一致性，首先要选择合适的Cache更新算法：写回法、写直达法和写一次法。其次要选择合适的Cache一致性协议。所谓一致性协议，是指多个处理器在读写Cache时所遵守一定的法则以确保CPU每次都能访问到最近更新的数据。常用的协议有监听协议、基于目录的一致性协议。

Cache的优化技术：为提高Cache性能，高速缓冲存储器发展的每个阶段都提出了一系列Cache的优化技术，典型的有Nonblocking Cache、Trace Cache、Victim Cache、Pipelined Cache、Compiler- controlled prefetching、Hardware prefetching of instructions and data。本文重点研究前三种Cache优化技术。

3Cache专利技术演进

3.1 初期Cache专利技术分析

3.1.1早期的分级存储系统中的Cache雏形

Cache技术是多级存储思想的延伸。多级存储的概念由Kilburn于1962年首次提出。Kilburn在文章中提出在系统中加入快速取数存储器以构成两级存储机制。在此之后，早期的多级存储设备的专利开始出现。1966年，由美国BURROUGHS公司提出了专利号为3292153，名称为“Memory system”的专利申请[2]。该专利被引证113次。专利中提出了一种存储器系统。其结构如图2所示。

该系统中设置了两级存储器，分别为高速存储器（标号为图2中的11），和低速存储器（标号为10）。两级存储器最大的特点是速度不同，实现的代价不同，SRAM每个位（bit）需要4个或6个晶体管实现，面积代价很大，集成在片内就很昂贵，因此一般只使用很小的容量，面积小但速度快，低速的则相反。采用该装置后，每次数据访问首先查找高速存储装置，如果命中则不需要访问低速装置，从而速度提高很多。Cache正是源于这种思路。

基于此思想，分层存储开始在数据处理系统（Data Processing System）中应用。数据处理系统包括：一个中央处理单元、一个缓冲存储器、一个主存储器等装置。较早的数据处理系统中的分级存储系统中展示了Cache的思想。国际商业机器公司（IBM）于1971年提出了专利号为3693165，名称为“PARALLEL ADDRESSING OF A STORAGE HIERARCHY IN A DATA PROCESSING SYSTEM USING VIRTUAL ADDRESSING”的专利申请[3]。该专利被引证61次，如图3所示。

该数据处理系统中，包含一个介于CPU与主存（Main Store）之间的高速的缓冲存储装置（Buffer Store）。系统中，处理单元使用虚拟地址访问容量有限的高速缓存，同时访问低速的主存储器。这样当高速缓存没有命中时也不会影响访问主存储器的速度。专利中还采用了地址比较机制用来比较地址控制信息与地址信息。可以看出早期的数据处理系统中形成了Cache的雏形。

3.1.2最早商用的Cache

在分层存储思想的基础上，1968年，一个里程碑式的发明在国际商业机器公司诞生。IBM大型机System/360 85研制成功，该大型机引入了高速缓存存储器，该高速缓存采用64位双极型阵列，具有64个存储单元和664个器件。这是Cache技术的首次商业应用。在该系统中Cache以高于以前12倍的速度提供高优先级的数据，为当今CPU技术中的高速缓冲存储器研发奠定了基础。

本章首先分析几篇典型的早期分层存储系统专利，从Cache思想起源的角度研究早期Cache的技术背景，然后分析了由IBM研发的最早商用的Cache系统。从中我们可以看到由分层存储系统到Cache的最早商业应用，短短的几年时间，Cache的优势已经初现端倪。在当今处理器领域，处理器与主存储器的速度差距逐渐增大，Cache的引入弥补了这种差距， Cache的重要性也随之增加。整个系统的性能也将与Cache息息相关。

3.2 近期Cache专利优化技术跟踪分析

3.2.1 NonblockingCache

在传统的系统中，当Cache缺失发生时，处理器必须先停顿，然后从主存储器中调度缺失的数据块以执行下面的指令。超标量体系结构处理器允许指令乱序执行，CPU无须在Cache失效时停顿。缺失发生后，CPU在等待数据Cache给出数据的同时，从指令Cache中取指令继续工作，相当于Cache缺失被屏蔽了。该Cache技术为Nonblocking Cache。如果采用Nonblocking Cache，就可能把CPU的性能提高很多，因为这种Cache在失效时仍允许CPU进行其它的命中访问。如果让Cache允许多个失效重叠，即支持多重缺失下的命中和缺失情况下的再次缺失，则可进一步减少实际缺失开销。不过，这种方法只有在存储器能处理多个缺失的情况下才能带来好处。

Nonblocking Cache是在1981由kroft第一次提出。数据控制公司（control data corporation）于1980年提出专利号为4370710，名称为“Cache memory organization utilizing miss information holding registers to prevent lockup from cache misses”的专利申请[4]。该专利被引证52次。该申请提出Nonblocking Cache的思想和实现方法，如图4所示。

该系统维持了一个缺失信息寄存器组，当发生Cache缺失时记录所需信息。相当于一个中断保护寄存器，保存中断发生时的上下文信息。一个输入堆栈被引入，目的是与Cache memory并行接收主存储器中的数据。当发生缺失时，把内容发往输入堆栈，配合其它装置进行缺失处理，而Cache继续应对另外的数据请求。Nonblocking Cache的引入具有重大意义，从高端通用处理器到嵌入式处理器，这项技术被广泛使用。

正如专利号为4370710的系统所示，Nonblocking Cache使系统在缺失率无法继续减少的情况下，性能极大提高。现代处理器中Cache缺失的代价是设计中需要考虑的重要因素。因此Nonblocking Cache技术将会有更广阔的应用空间。

3.2.2 VictimCache

Cache的性能日益重要，尤其是在现代高级处理器中。在1980年后的十年中，处理器指令执行周期下降速度远远超过主存储器访问时间的下降速度。CISC处理器和RISC处理器的思想被融入到单个处理器中。每条指令执行所耗费的机器周期数量急剧下降。对于RISC体系结构特性的处理器，每当发生一次缺失，缺失损失是100个指令周期甚至更多，严重影响了处理器性能的提高。一种能减少冲突失效次数而又不影响时钟频率的方法是：在 Cache 和它与下一级存储器的数据通路之间增设一个全相联的 Cache ，称为Victim Cache。最早的Victim Cache 是由Jouppi于1990年提出的。

数字设备公司（Digital Equipment Corporation）于1990年提出专利号为5261066，名称为“Data processing system and method with small fully-associative cache and prefetch buffers”的专利申请[5]。该专利被引用130次。该专利的发明者Jouppi提出了Victim Cache，如图5所示。

图5的存储系统中，一个缺失Cache处于一级Cache存储器和主存储器之间。缺失Cache容量较一级Cache小，一级Cache由数据和指令Cache组成。当一级Cache缺失发生时，告知缺失Cache和主存储器。专利研究得出数据冲突缺失是影响性能的主要因素。为了更好发挥缺失Cache的性能，将缺失Cache组织成较小的全映射Cache形式，称之为Victim Cache。如果一级Cache发生缺失，那么继续到Victim Cache中寻找所需数据。Victim Cache组织情况如图6所示。

图6中数字52代表Victim Cache，是采用全映射组织。一级Cache采用直接映射组织。Victim Cache 中

存放由于失效而被丢弃（替换）的那些块。发生失效时，在访问下一级存储器之前，先检查 Victim Cache 中是否含有所需的块[6]，如果有，就将该块与 Cache 中某个块做交换。Jouppi发现，含1到5项的 Victim Cache 对减少冲突失效很有效，尤其是对于那些小型的直接映象数据 Cache 更是如此。对于不同的程序，一个项数为4的 Victim Cache能使一个4KB直接映象数据 Cache 的冲突失效减少20%～90%。

3.2.3 Trace Cache

在早期的Cache组织优化技术方面，研究的重点放在如何使得主存储器与Cache中的内容相对应。常用的有直接映射、全映射和组相连映射。这些方法使得Cache中的每行按虚拟地址或者物理地址顺序存放数据或者指令。随着超标量处理器的出现和发展，这些组织方式已经不能满足处理器的需求了。尤其是当缺失的代价变得难以忍受时，一种新的优化技术应运而生，这就是Trace Cache。英特尔公司于1994年提出专利号为5381533，名称为“Dynamic flow instruction cache memory organized around trace segments independent of virtual address line”的专利申请[7]。该专利被引证52次。专利中提出的Trace Cache如图7所示。

图7展示了最早的Trace Cache技术。该技术用在超标量体系结构的计算机中。总线30代表CPU的输出，提供必须执行的指令和指令所对应的地址。“Cache Memory”是一个双端口Cache。两个端口都有各自的数据线和地址线。端口1与CPU和主存储器交互。端口2与一个线缓冲（Line Buffer）相连。在实际操作中，Cache的输入来自“Line Buffer”，然后“Line Buffer”将数据和地址送往Cache。Cache与Line Buffer之间的传递内容包括分支预测指令，下一地址和踪迹（Trace）。这三项内容被组织放入“Line Buffer”。

下面分析该专利中的Cache技术与早期技术的不同之处，从而得出专利的创新点。早期的Cache技术是简单的将处理器产生的物理地址或者虚拟地址发出给Cache，然后Cache比较自身维护的信息，如果匹配，那么命中，否则发生缺失。Cache是根据预先决定的地址来进行顺序线性组织的。然而实际程序中往往包含很多分支指令，每50到60条指令后一般可能有一条分支指令。当分支发生时，下一条将要执行的指令（针对指令Cache）可能在Cache的另外的行中或者根本不在Cache中。那么发生Cache缺失从而产生的代价将是巨大的。相比而言，本专利中提出的Trace Cache技术是一种动态的Cache组织技术。Cache的行的组织是根据实际程序的执行情况进行动态组织。如果程序中有分支发生，那么Cache组织时根据分支的可能转移结果来把下一条需要执行的指令组织到一行中或这一个Cache块中。因此该技术有利于减少Cache的缺失。如7图所示，处理器先把Line Buffer当作暂时的Cache，然后再根据已经执行的指令来组织Cache Memory。

由上面分析，我们可以看出第一份Trace Cache专利给系统带来了性能的极大提高，以至于现代的Pentium 4处理器中采用了该技术。

本章分析了三种典型Cache优化技术，从Cache组织和缺失减少的角度阐述分析了三篇具有里程碑式的专利。可以看到，Cache的组织技术与处理器的结构和指令集密切相关，当新的处理器结构不断推出时，Cache将需要被重新组织和优化。

4小结

本文通过检索美国的Cache专利并对其进行筛选和梳理，总结Cache的技术背景和关键优化技术的发展历程。进而以三大关键技术为例，具体分析了专利中的优化技术。从1968年出现第一个商用的Cache，到90年代年涌现出大量的Cache优化技术的专利，Cache优化技术不断推陈出新。由Nonblocking Cache到Victim Cache，再到Trace Cache，每一个Cache组织方式的改变都引起了系统性能的极大提升。尤其是现在的处理器设计中，如何综合考虑硬件与软件的关系，如何优化Cache以更好的适应应用程序来达到程序的提速是关键之处，也是将来Cache领域需要深入的问题。当今处理器的架构日益复杂，多核处理器已经成为发展趋势，这种复杂体系结构的处理器也需要有更加新的Cache组织以及优化的技术，因此可见未来的处理器设计中，Cache组织优化技术将会有更大的发展空间。

下期预告

理解Cache技术演进的基础上，追溯Cache思想的来源，深入典型Cache优化的技术发展，对专利文献更进一步分析，我们还能发现哪些更为值得关注的技术趋势？下期中，我们将以美国Cache相关专利为样本，继续分析Cache优化技术演进，对比其各阶段优化技术，分析各自的技术优势，预测其研发趋势，敬请期待。

参考文献

[1] T.KILBURN. 取数时间很短的数字计算机存储器（阿特拉斯计算机固定存储器）, 计算机研究与发展. 1962年06期.

[2] Rorbert S.Barton , Altadena,Calif. Memory System.US.3292153[P].1966.12.13.

[3] Reiley; Forrest A., Richcreek; James T. Parallel Addressing of a Storage Hierarchy in a Data Processing System Using Virtual Addressing.US.3693165[P].1971.6.29.

[4] Kroft; David.Cache memory organization utilizing miss information holding registers to prevent lockup from cache misses.US.4370710[P].1980.8.26.

[5] Jouppi,Norman . Data processing system and method with small fully-associative cache and prefetch buffers.US. 5261066 [P].1993.11.09.

[6]Wilkes.Slave Memories and Dynamic Storage Allocation. Trans.IEEE vol EC-14 page 270.1965.

[7] Peleg, Alexander . Dynamic flow instruction cache memory organized around trace segments independent of virtual address line.US. 5381533 [P].1995.01.10.

作者简介

张旭，工业和信息化部软件与集成电路促进中心专利分析师，集成电路设计专业，研究方向为控制工程和微处理器设计，主要从事处理器技术领域的专利分析。

武晓岛，工业和信息化部软件与集成电路促进中心项目经理、专利分析师，计算机应用技术专业，主要从事高端通用芯片技术领域的专利分析。

谢学军，工业和信息化部软件与集成电路促进中心主任助理，微电子学与固体电子学专业博士，知识产权司法鉴定人，负责建立国家IP核库，IP核评测与验证系统，承担科技部863项目“IP评测及规范化技术研究”，参与国家知识产权战略规划中的“集成电路知识产权战略研究”的撰写，参与2006、2007年电子发展基金项目“集成电路知识产权分析”，承接“国家软件与集成电路公共服务平台”中集成电路子平台建设。