用于执行存储器压缩的系统和方法与流程

用于执行存储器压缩的系统和方法
1.本技术是申请日为2018年7月26日、国家申请号为201810830354.7、发明名称为“用于执行存储器压缩的系统和方法”的中国专利申请的分案申请。
技术领域
2.本文描述的实施方案涉及计算系统的领域，并且更具体地，涉及有效地移动数据以用于存储和处理。


背景技术：

3.一般而言，多种计算系统包括处理器和存储器，并且处理器生成对指令和应用数据的访问请求，同时处理一个或多个软件应用程序。例如，当提取指令和数据时，处理器检查本地高速缓存存储器的分级结构，并且如果没有找到，则处理器向主存储器或其他存储装置(诸如cd-rom或硬盘驱动器)发布对期望的指令和数据的请求。
4.有时，在计算系统上同时运行的软件应用程序的数量达到可观的数量。此外，多种计算系统包括多个处理器，诸如中央处理单元(cpu)、数据并行处理器(如图形处理单元(gpu))、数字信号处理器(dsp)等。因而，用于处理多个软件应用程序的指令和数据的量显著增长。然而，本地高速缓存存储器中的存储器存储位置具有有限量的存储空间。因而，发生在本地高速缓存存储器和永久存储装置之间交换指令和数据。
5.等待将加载的请求的信息的交换和对应延迟减少计算系统的性能。为了减少特定数量的数据的存储量，数据被压缩。此类压缩利用了数据中包括的单独的数据位的重复序列。当将访问数据时，数据被解压缩，并且然后一旦访问已经完成，数据就可能被重新压缩。
6.一般而言，当诸如中央处理单元(cpu)的通用处理器正在执行软件例程以压缩和/或解压缩数据时，诸如中央处理单元(cpu)的通用处理器在操作的持续时间内被占据。附加地，在包括多个处理器的系统中，很多时候，cpu是支持检索、压缩和解压缩所期望的数据的唯一处理器。因而，在执行本地和网络数据检索和压缩中的一个或多个时，cpu部分或完全不可用。另外，其他处理器在等待cpu代表它们完成检索、压缩和解压缩操作时招致延迟。
7.鉴于上述情况，期望用于有效地移动数据以用于存储和处理的方法和机制。


技术实现要素：

8.设想用于有效地移动数据以用于存储和处理的系统和方法。在各种实施方案中，计算系统包括存储器、高速缓存存储器和处理器。响应于接收到压缩指令，处理器将来自存储器的数据提取到高速缓存存储器中。在一些实施方案中，数据被划分为多个输入字。随后，处理器将来自高速缓存存储器的多个输入字加载到处理器内的读取缓冲器中。处理器内的压缩单元包括用于执行压缩指令的电路。因而，当压缩单元处理压缩指令时，处理器可用于处理其他操作。
9.在实施方案中，压缩单元选择多个字中的两个或更多个输入字以用作分配的输入字。压缩单元包括用于执行压缩算法的操作的多个硬件通道。多个硬件通道的两个或更多
个硬件通道中的每个被分配给所选择的两个或更多个输入字中的相应一个。两个或更多个硬件通道中的每个至少基于其分配的输入字生成相应的压缩的包。为了生成压缩的包，每个硬件通道使用值以与分配的字相比较以确定组内依赖关系。然而，在各种实施方案中，在确定带有相同索引的第一组字的组内依赖关系之前，针对较新的第二组字访问字典，第二组中的每个字具有相同的索引。
10.压缩单元将压缩的包组合成一组压缩的包。在一些实施方案中，压缩单元还将两个或更多个组组合成封包组，并且将封包组写入到写入缓冲器。在稍后时间，处理器将封包组从写入缓冲器发送到目标存储位置。
11.在各种实施方案中，当处理每个分配的输入字时，通过与先前看到的数据进行比较搜索数据位的重复序列。在一些实施方案中，先前看到的数据存储在称为字典的数据结构(例如，诸如表)的条目中。在一些实施方案中，多个硬件通道执行基于统计的压缩算法和基于字典的压缩算法的组合的步骤。在一些实施方案中，分配给两个或更多个硬件通道的两个或更多个选择的输入字中的每个具有指向表的多个条目中的相同条目的对应索引。在一些实施方案中，从字典中读取表的相同条目的内容一次，用于处理当前分配给两个或更多个硬件通道的输入字。在实施方案中，带有两个或更多个分配的输入字中的最旧输入字的硬件通道生成单个读取请求。附加地，带有两个或更多个分配的输入字中的最新输入字的硬件通道生成对在完成两个或更多个分配的输入字的压缩时更新表的单个写入请求。因而，针对存储在表中的序列的用于串行实施的多个读取和写入请求被减少到用于使用多个硬件通道并行实施的单个读取请求和单个写入请求。
12.在另外的实施方案中，处理器还包括利用多个硬件通道的解压缩单元。响应于接收到解压缩指令，处理器提取压缩的包，并且处理器内的解压缩单元包括用于执行解压缩指令的电路。因而，当解压缩单元处理解压缩指令时，处理器可用于处理其他操作。解压缩单元的多个硬件通道中的每个基于压缩的包生成字。
13.在参考以下描述和附图时还将了解这些和其他实施方案。
附图说明
14.通过结合附图参考以下描述，可更好地理解方法和机制的上面的和另外的优点，其中：
15.图1是处理器核心的一个实施方案的框图。
16.图2是压缩/解压缩单元的一个实施方案的框图。
17.图3是压缩的信息的一个实施方案的框图。
18.图4是压缩引擎的一个实施方案的框图。
19.图5是压缩处理的一个实施方案的框图。
20.图6是压缩处理的另一实施方案的框图。
21.图7是压缩处理的另一实施方案的框图。
22.图8是压缩处理的另一实施方案的框图。
23.图9是用于有效压缩数据的方法的一个实施方案的流程图。
24.图10是解压缩处理的一个实施方案的框图。
25.图11是用于有效地解压缩数据的方法的一个实施方案的流程图。
26.图12是压缩处理的另一实施方案的框图。
27.图13是解压缩处理的另一实施方案的框图。
28.图14是压缩处理的另一实施方案的框图。
29.虽然本公开所述的实施方案可受各种修改形式和另选形式的影响，但其具体实施方案在附图中以举例的方式示出并将在本文详细描述。然而，应当理解，附图和对其的详细描述并非旨在将实施方案限制为所公开的特定形式，而相反，本发明旨在覆盖落入所附权利要求书的实质和范围内的所有修改、等同物和另选方案。如在本专利申请中所使用的那样，以准许的意义(即，意味着具有可能性)而非强制的意义(即，意味着必须)使用字“可”。类似地，字“包括”(“include”、“including”和“includes”)意味着包括但不限于。
30.各种单元、电路或其他部件可被描述为“被配置为”执行一个或多个任务。在此类上下文中，“被配置为”是一般意味着“具有”在操作期间执行一个或多个任务的“电路”的结构的宽泛表述。如此，即使在单元/电路/部件当前未接通时，单元/电路/部件也可被配置为执行任务。一般来讲，形成对应于“被配置为”的结构的电路可包括硬件电路。类似地，为了描述中方便，可将各种单元/电路/部件描述为执行一个或多个任务。此类描述应当被解释为包括短语“被配置为”。表述被配置为执行一个或多个任务的单元/电路/部件明确地旨在对该单元/电路/部件不调用35u.s.c.
§
112(f)。
具体实施方式
31.在以下描述中，阐述了许多具体细节以提供对本公开中描述的实施方案的透彻理解。然而，本领域的普通技术人员将认识到，可在没有这些具体细节的情况下实践实施方案。在一些实例中，为了便于例示且避免模糊实施方案的描述，没有详细示出众所周知的电路、结构和技术。
32.参考图1，示出了例示处理器核心100的一个实施方案的框图。在例示的实施方案中，处理器核心100包括指令提取单元(ifu)110、核心接口170、压缩/解压缩单元180、执行单元130和末级高速缓存190。执行单元130耦接到加载存储单元(lsu)150，加载存储单元(lsu)150也耦接以将数据发送回到执行单元130。另外，lsu 150耦接到核心接口170，核心接口170继而可耦接到末级高速缓存190。在例示的实施方案中，末级高速缓存190包括总线接口单元(biu)195，总线接口单元(biu)195经由片上网络(例如，诸如图1所示的内部总线105)耦接到主存储器。应当注意，图1中所示的实施方案仅为示例，并且为了清楚起见已经省略了一些电路块。在其他实施方案中，可采用不同数量的电路块和不同的电路块布置。
33.在一些实施方案中，处理器核心100是计算系统中的独立处理器。在其他实施方案中，处理器核心100是多核处理器的多个核心中的一个。在其他实施方案中，包括处理器核心100的多核处理器是片上系统(soc)上的多个管芯中的一个。在各种实施方案中，处理器核心100用于台式计算机、便携式计算机、平板计算机、智能电话、移动设备、服务器、外围设备或其他内的计算系统中。
34.在各种实施方案中，压缩/解压缩单元180使处理器核心100的其余部分卸载而不能实行压缩/解压缩算法的操作。因而，当压缩/解压缩单元180处理压缩/解压缩算法时，处理器核心100的其余部分可用于处理其他操作。在一些实施方案中，压缩/解压缩单元180基于多种基于字典的算法中的一个，压缩和解压缩数据。在其他实施方案中，压缩/解压缩单
元180基于使用基于统计的算法和基于字典(基于表)的算法的组合的多种混合算法中的一个，压缩和解压缩数据。如本文所使用的，“字典”(也称为“表”)是包括多个条目的数据结构(基于硬件和/或软件的)，其中每个条目被配置为存储已经历压缩过程的数据值。在压缩过程期间，将要压缩的数据值与存储在字典中的值进行比较，以确定之前是否已看到它们(例如，全部或部分)。
35.如图所示，压缩/解压缩单元180包括压缩引擎182和解压缩引擎184。引擎182和引擎184中的每个包括用于压缩/解压缩算法操作的并行处理的多个硬件通道。因而，在压缩/解压缩操作期间吞吐量增加，因为由多个硬件通道同时压缩/解压缩数据的多个部分。在实施方案中，发送用于压缩的数据的每个部分是已知大小的输入字。在一个示例中，32位输入字是数据的一部分，但是多种其他大小是可能的和可设想的。
36.在一些实施方案中，算法操作是流水线，这还增加了吞吐量。另外，虽然在当前分配给压缩引擎182的硬件通道的多个输入字之间存在依赖关系，但是在实施方案中，在确定第一组的输入字之间的依赖关系之前将不同的第二组输入字分配给硬件通道。于是，虽然第二组依赖于由第一组的字典更新，但是在确定第一组的输入字之间的依赖关系之前，将第二组分配给压缩引擎182的硬件通道。由于引擎182和引擎184的相对高的吞吐量，所以准许用于处理多个软件应用程序的指令和数据量增长，而在本地高速缓存存储器和永久存储装置之间没有长延迟交换，但是本地高速缓存存储器中的存储器存储位置具有有限量的存储空间。
37.如下面更详细地描述的，压缩/解压缩单元180响应于检测到用于处理器核心100的指令集架构(isa)中定义的压缩或解压缩命令/指令，一次将一页数据压缩或解压缩为一组多个输入字。在一些实施方案中，可将附加指令添加到处理器核心100的isa中。在各种实施方案中，分别将带有指示编码/压缩和解码/解压缩的操作码的两个指令添加到isa用于执行数据压缩和解压缩。在一些实施方案中，指令使用指定源页面的地址和存储器中的目的地或目标页面的地址的一个或多个参数。在一些实施方案中，两个指令中的每个被转变成多个微操作，微操作也被称为“微操作(micro-ops)”。压缩/解压缩单元180处理微操作。
38.在各种实施方案中，压缩/解压缩单元180向末级高速缓存190提供信息以预取一页数据用于压缩或解压缩。在一些情况下，对该页数据的请求可通过总线接口单元(biu)195发送到主存储器。预取的该页数据可存储在末级高速缓存190或另一合适的位置中。一旦预取的该页数据已经存储在末级高速缓存190中，该页就可被传送到包括在压缩/解压缩单元180中的读取缓冲器。引擎182和引擎184中的一个处理接收的该页。在另外描述引擎182和引擎184之前，首先提供处理器核心100的其余部分的另外的描述。
39.指令提取单元(ifu)110向处理器核心100的其余部分提供指令用于执行。在例示的实施方案中，ifu 110可被配置为执行与从高速缓存或存储器提取指令、从各种线程中选择指令用于执行，以及在将指令发布到各种功能单元用于执行之前对此类指令进行解码有关的各种操作。ifu 110还包括指令高速缓存114。在一个实施方案中，ifu 110可包括用于以下的逻辑：维持对应于由处理器核心100执行的每个线程的提取地址(例如，从程序计数器导出的)；以及根据那些提取地址协调从指令缓存114检索指令。附加地，在一些实施方案中，ifu 110可包括虚拟指令地址到物理地址的映射的一部分。例如，映射的该部分可存储在指令转换后备缓冲器(itlb)诸如itlb 115中。
40.执行单元130可被配置为执行且提供从ifu 110发布的某些类型的指令的结果。在一个实施方案中，执行单元130可被配置为执行在实施的isa中定义的某些整数类型和浮点指令，诸如算术指令、逻辑指令和移位指令。设想在一些实施方案中，处理器核心100可包括多于一个执行单元，并且执行单元中的每个在功能上可为对称的或可不是对称的。
41.加载存储单元(lsu)150可被配置为处理数据存储器引用，诸如整数和浮点加载和存储指令。在一些实施方案中，lsu 150也可被配置为帮助处理源自ifu 110的指令高速缓存114未命中。lsu 150包括数据高速缓存152，以及被配置为检测高速缓存未命中且经由高速缓存接口170响应地请求来自特定高速缓存存储器的数据的逻辑。在一个实施方案中，数据高速缓存152可被配置为直写高速缓存，其中所有存储被写入到特定高速缓存存储器，而不管所有存储是否命中数据高速缓存152。在其他实施方案中，数据高速缓存152可实施为回写高速缓存。
42.在一个实施方案中，lsu 150可包括未命中队列，未命中队列被配置为存储在数据高速缓存152中未命中的未决存储器访问的记录，使得其中未命中是未决的附加存储器访问目标存储器地址可不生成附加的高速缓存请求通信。在例示的实施方案中，可由一个或多个执行单元130中的一个执行加载/存储指令的地址生成。依赖于由指令指定的寻址模式，一个或多个执行单元130中的一个可实行算术(例如，诸如将索引值添加到基值)以产生期望的地址。另外，在一些实施方案中，lsu 150可包括被配置为将由一个或多个执行单元130生成的虚拟数据地址转换为物理地址的逻辑。例如，在本实施方案中，lsu 150包括数据转换后备缓冲器(dtlb)153。
43.转向图2，例示了例示压缩/解压缩单元200的一个实施方案的框图。在各种实施方案中，压缩/解压缩单元200可对应于如图1的实施方案中所描绘的压缩/解压缩单元180。在例示的实施方案中，压缩/解压缩单元200包括读取缓冲器201、压缩引擎204、解压缩引擎203、字典210、多路复用电路205、写入缓冲器206、有限状态机电路208和预取电路209。应当注意，在图2的框图中描绘的实施方案仅是示例。在其他实施方案中，不同的电路块和不同的电路块布置是可能的和可设想的。
44.读取缓冲器201可包括多个条目，诸如例如条目202a和条目202b，一页数据的部分可被存储到多个条目中。在各种实施方案中，可组织条目以允许并行处理多个数据字。例如，在一些实施方案中，条目可被布置成允许由压缩引擎204或解压缩引擎203读取给定数量的32位数据字。在一些情况下，由压缩引擎204或解压缩引擎203读取四个32位数据字。在其他情况下，另一数量的数据字是可能的和可设想的。读取缓冲器201还可被配置为从压缩引擎204和解压缩引擎203中的每个接收就绪信号，就绪信号指示那些引擎中的多个并行硬件通道准备好接收更多数据。
45.在一些情况下，如果读取缓冲器201没有准备好接收请求的数据，则数据可保持在包括在总线接口单元(biu)中的缓冲器中。在实施方案中，biu可耦接到通信总线，该通信总线允许数据在各种高速缓存存储器和系统存储器之间移动。在一些实施方案中，读取缓冲器201可使用基于信用的系统以从低级高速缓存存储器(例如，诸如数据高速缓存252)请求数据。如下面更详细描述的，压缩引擎204和解压缩引擎203中的每个可被配置为分别压缩或解压缩从读取缓冲器201接收的数据的部分。在一些实施方案中，压缩引擎204和解压缩引擎203基于多种基于字典的算法中的一个，压缩和解压缩数据。在其他实施方案中，压缩
引擎204和解压缩引擎203基于使用基于统计的算法和基于字典的算法的组合的多种混合算法中的一个，压缩和解压缩数据。
46.在各种实施方案中，字典210可包括多个条目，多个条目中的每个条目对应于给定索引且被配置为存储通常使用的位序列。在一些实施方案中，每个条目可被配置为存储索引。在其他实施方案中，条目不存储索引。在一些情况下，字典210可实施为内容可寻址存储器(cam)，使用从将压缩的特定数据字的位创建的散列输出访问内容可寻址存储器(cam)。在其他情况下，字典210可实施为直接映射数据存储结构，诸如表，其中表条目保持对应于索引的常数。例如，在字典210的使用中，表条目7保持字典210的第七条目。因而，条目中不存储索引值。可根据各种设计样式中的一种来设计字典210。例如，字典210可包括多个锁存器、触发器、随机存取存储器(ram)单元，或被配置为存储包括在各种条目中的单独的数据位的其他合适的存储电路。
47.作为压缩和解压缩操作的部分，压缩引擎204和解压缩引擎203可访问字典210。在压缩和解压缩操作期间，压缩引擎204和解压缩引擎203可更新字典210中的一个或多个条目，以便改进后续压缩操作。在一些实施方案中，压缩操作和解压缩操作是流水线，这还增加了吞吐量。另外，虽然在当前分配给压缩引擎203的硬件通道的多个输入字之间存在依赖关系，但是在实施方案中，在确定第一组的输入字之间的依赖关系之前将不同的第二组输入字分配给硬件通道。于是，虽然第二组依赖于由第一组的字典210的更新，但是在确定第一组的输入字之间的依赖关系之前，将第二组分配给压缩引擎203的硬件通道。
48.多路复用电路205可包括多个单独的数据位多路复用电路，多个单独的数据位多路复用电路允许依赖于正在执行的命令从压缩引擎204或解压缩引擎203中选择输出。有限状态机电路208可被配置为生成多个信号以控制包括在压缩/解压缩单元200中的各种其他电路块的操作。在各种实施方案中，有限状态机电路208可从指令提取单元和信号预取电路209接收压缩和解压缩指令/命令，以启动预取在接收的命令中指定的一页数据。有限状态机电路208可附加地控制将来自写入缓冲器206的数据复制到目标存储位置。在各种实施方案中，有限状态机电路208可包括被配置为实行上面提及的功能的多个顺序和组合逻辑电路。
49.预取电路209可包括可被配置为将多个行提取到低级高速缓存(诸如例如如图2的实施方案中所示的数据高速缓存252)中的顺序和组合逻辑电路的任何合适的组合。在一些实施方案中，预取电路209可基于多个可用信用，将预取请求发送到计算系统。在一些实施方案中，预取电路209可依赖于步距值执行预取。例如，在压缩的情况下，处理器核心可预取期望的页中的第一n(其中n是正整数)行，并且预取电路209可在每行已经被预取后，按步距递增从源地址加n到期望的该页数据的结束进行预取。
50.转向图3，示出例示压缩的信息300的一个实施方案的框图。在实施方案中，压缩的信息300包括压缩的包301-压缩的包305、一组压缩的包310和一组压缩的包330中的一个或多个。图3中描绘的压缩的信息类型仅是示例。在其他实施方案中，压缩/解压缩单元生成且使用不同的包类型，不同的包类型可包括命令和数据的不同布置。
51.在各种实施方案中，依赖于与字典比较的结果，每个压缩的包包括命令和可能的其他附加信息。在实施方案中，每个命令是对特定包类型编码的数据位的组合。如果正在操作的数据的一部分的数据位全为零，则压缩的包301可用于数据的该部分的压缩的该页数
据中。压缩的包301仅包括指定未压缩文件中的所有数据位为零的命令。
52.当将数据的一部分与字典进行比较时，在一些实施方案中，存在三种可能性中的一种。如果数据的一部分中的数据位的序列与字典中的任何条目不匹配，则发生未命中，并且压缩的包302可用于数据的一部分的压缩的该页数据中。压缩的包302包括指出在字典中未找到该位序列的命令，以及数据的原始部分(字)的副本。应当注意，在一些实施方案中，未命中可导致压缩引擎修改字典以包括将允许与数据的一部分匹配的新条目，假如空间在字典中是可用的。在其他实施方案中，未命中导致压缩引擎用字的副本的数据替换字典的条目。由从该字的数据生成的索引指向该条目。
53.如果数据的一部分与字典中的现有条目匹配，则发生命中，并且压缩的包303可用于数据的一部分的压缩的该页数据中。压缩的包303包括指示数据的一部分与字典中的条目匹配的命令，以及指向字典中的匹配条目的索引。在各种实施方案中，索引可为数据的一部分的散列。
54.在一些情况下，数据的一部分可与字典中的条目部分地匹配。当这发生时，压缩的包304可用于数据的一部分的压缩的该页数据中。压缩的包304可包括指出部分命中的命令，以及对应于与数据的一部分部分匹配的字典中的条目的索引或散列，以及与条目不匹配的来自数据的一部分的部分字。在各种实施方案中，依赖于任何合适的标准，在数据的一部分和字典中的给定条目之间匹配的数据位的数量可为可调整的。
55.在一些实施方案中，压缩的包301(零)和压缩的包303(命中)中的每个不修改字典，而压缩的包302(未命中)和压缩的包304(部分命中)确实具有存储在字典中的信息。在实施方案中，如较早描述的，整个32位字(或其他选择的字长)存储在字典中。在一些实施方案中，写入字典的字替换从字典读取的字且用于实行字典字与正在处理的当前组中的字之间的比较。在一个示例中，如果当前组中的三个字中的每个具有相同的索引，诸如索引7，则诸如通过读取请求来访问字典的条目7。从字典中检索条目7中的字，并且将该字与当前组中的三个字进行比较。
56.如果当前组的前两个字与来自字典的条目7的字匹配，则两个比较导致命中，并且为这两个字中的每个生成压缩的包303。对这两个字不执行字典的修改。然而，如果当前组的第三字与来自条目7的字不匹配，则比较导致未命中，并且为该第三字生成压缩的包302。另外，该第三字被添加到字典。在实施方案中，该第三字替换字典的条目7中的字。因而，为该第三字更新字典。
57.类似于上面的示例，部分命中比较结果也致使更新字典。如果第三字的一部分与条目7中的字匹配，但另一不同的部分不匹配，则该比较导致部分命中。针对部分命中，生成压缩的包304。在示例中，如果当前组中的32位第三字的位10到位31与从字典的条目7检索的32位字的位10到位31匹配，则比较导致部分命中。位0到位9存储在压缩的包304中，而该第三字的整个32位替换字典的条目7中的字。
58.如在图3中例示的实施方案中可看到的那样，压缩的包303(命中)和压缩的包304(部分命中)中的每个存储所生成的索引。因而，在稍后的解压缩操作期间，不再生索引，因为可从压缩的包中检索索引。压缩的包301(零)不存储索引，但是在稍后的解压缩操作期间，不再生索引。压缩的包302(未命中)不存储所生成的索引。因而，在稍后的解压缩操作期间，从压缩的包302中的字的内容再生索引。
59.也可采用第五类型的包。压缩的包305可包括指示重复包的数量的计数的命令。此类包可用于用指示特定包在序列中出现多少次的行程编码(rle)包之后的特定包替换多个相同包。通过采用rle包，可通过仅存储序列中重复包的单个副本以及包将重复的次数而不是重复包的所有实例来实现另外的压缩。
60.在一些实施方案中，压缩的包诸如图3中所示的那些可组合以形成组。该组压缩的包310描绘了一组压缩的包的特定实施方案。在例示的实施方案中，压缩的包312、压缩的包314、压缩的包316和压缩的包318被级联在一起成为可写入目标存储位置中的单个组。然而，在一些情况下，可期望将命令与各种压缩的包中的其对应的有效载荷分离。在图3中例示采用这样的技术的一组压缩的包330的实施方案。在例示的实施方案中，有效负载332a、有效负载334a、有效负载336a和有效负载338a被级联在一起。类似地，然后可将对应于有效载荷332a到有效载荷338a的命令cmd 332b、命令cmd 334b、命令cmd 336b和命令cmd 338b级联到先前级联的有效载荷上。
61.转向图4，例示了例示压缩引擎400的一个实施方案的框图。在各种实施方案中，压缩引擎400对应于如图2的实施方案中所示的压缩引擎204。在例示的实施方案中，硬件通道400包括读取接口401、包生成器402、rle过滤器404、包缓冲器404、组生成器405和写入接口406。在各种实施方案中，部件401到部件406中的每个包括多个硬件通道。应当注意，图4中所示的实施方案仅是示例。在其他实施方案中，可采用不同的电路块和不同的电路块布置。
62.在各种实施方案中，读取接口401从读取缓冲器(诸如例如如图2中所示的读取缓冲器201)读取多个字。例如，在一些实施方案中，读取接口401可从读取缓冲器并行读取四个32位字。在其他实施方案中，另一数量的字和另一字大小是可能的和可设想的。读取接口401可附加地对从读取缓冲器读取的数据执行一些检查。例如，读取接口401可检查以确定字中的一个字是否包含带有零检测逻辑的全零。另外，读取接口401可检查字中的任一个与其它字中的一个或多个相同还是部分相同。
63.另外，读取接口401可计算将与字典查找一起使用的散列或索引，并且检查以看到字中的任一个是否具有相同的索引。在一个示例中，4位索引用于访问直接映射的16条目字典。在一些实施方案中，读取接口401可在给定42位字的特定位之间执行异或布尔运算，以便生成4位索引。在其他实施方案中，读取接口401基于字的特定位来访问散列表以生成索引。在其他实施方案中，对给定字的特定位执行散列函数以生成索引。另外，表查找、多种散列函数中的一个和多种布尔逻辑函数中的一个中的一个或多个的组合被用于生成索引。当生成用于访问字典的索引时，压缩引擎400执行基于统计的压缩算法和基于字典的压缩算法的组合。
64.在实施方案中，由读取接口401读取一组的字，使得最左侧的字是该组的最旧的字，并且最右侧的字是该组的最新的字。最旧的字和最新的字之间的字以类似的方式排序。在其他实施方案中，最右侧的字是该组的最旧的字，并且最左侧的字是该组的最新的字。在一些实施方案中，当两个或更多个字具有相同的索引时，单个读取请求被发送到字典，而不是多个读取请求，其中一个读取请求来自每个字。在实施方案中，读取接口401仅为带有相同索引的两个或更多个字中的最旧字生成读取请求，并且代表带有相同索引的两个或更多个中的其他字将带有生成的索引的读取请求发送到字典。
65.读取接口401可包括多个触发器电路、锁存器和其他顺序元件，以便在将字发送到
包生成器402之前存储字。另外，在一些实施方案中，读取接口401包括两个或更多个流水线级。因而，在实施方案中，对字典的特定条目的内容的读取请求(诸如代表带有相同索引的两个或更多个字)被存储在第一流水线级结束时的流水线顺序元件中。在稍后的第二流水线级中将读取请求发送到字典，而从读取缓冲器读取下一组字，并且为下一个组生成索引。
66.在各种实施方案中，包生成器402为从读取接口401接收的字中的每个生成压缩的包。包生成器402通过将给定字与字典中的一个或多个条目进行比较，生成类似于图3中所描绘的包的包。在一个实施方案中，使用基于cam的比较电路将给定字与字典中的每个条目进行比较。在其他实施方案中，指定字典的特定条目的索引用于访问字典，并用于检索用于在比较中使用的字。然而，针对由多个硬件通道的并行执行，包生成器402通过将给定字与来自另一硬件通道的字而不是从字典中检索的内容进行比较，生成类似于图3中所描绘的包的包。选择逻辑基于多个硬件通道的流水线级的加载。稍后用示例提供另外的细节。包生成器402可基于所执行的比较来确定适当的命令和有效载荷。包生成器402也可包括多个触发器电路，用于在将生成的包发送到rle过滤器403之前存储生成的包。
67.rle过滤器403可包括被配置为跟踪类似包的序列的顺序逻辑电路或状态机。类似的包可为例如零(zero)包(即，包括所有零数据位的包)的序列，或到相同字典索引的hit包的序列。一旦检测到可能序列的开始，诸如例如zero包，rle过滤器403就可跟踪序列中的后续数量的包。一旦序列结束，rle过滤器403就可生成指示复制特定包的次数的rle包。可存储序列中的初始包和rle包，从而减少需要存储的包的数量。可在解压缩期间使用rle包以生成开始该序列的包的附加副本。
68.包缓冲器404可包括在由组生成器405的组生成之前存储包所必需的多个触发器或其他合适的存储电路。在各种实施方案中，组生成器405可包括多个多路复用电路和移位寄存器。多路复用电路和移位寄存器以及其他逻辑电路可被布置为允许形成一组包。在一些实施方案中，该组包的格式可对应于图3中所示的包组的格式。
69.写入接口406可包括多个缓冲器，组在多个缓冲器中被封包。在各种实施方案中，写入接口406可将多个组封包到单个缓冲器中直到缓冲器为满，就在这时，缓冲器的内容可被写入到等待被复制到目标存储位置中的写入缓冲器。由于包可为各种大小，所以组也可为各种大小。如此，多个组可组合在单个缓冲器中。包括在写入接口406中的缓冲器可被布置为允许写入接口406内的流水线操作。
70.现在参考图5，示出了例示压缩处理500的一个实施方案的框图。在例示的实施方案中，对混合压缩算法执行串行执行，该混合压缩算法使用基于统计的压缩算法和基于字典的压缩算法的组合。如图所示，使用被称为“通道0”的单个硬件通道。后来，提供在多个硬件通道中带有并行执行的压缩处理。虽然将通道0示出四次，但是这是为了便于例示，并且在该例示的示例中仅使用单个硬件通道。被压缩的数据的部分称为字。如图所示，字典510将最近看到的字存储在多个条目中。在所示的示例中，字典510是直接映射的数据存储结构，诸如表。字典510可包括多个锁存器、触发器、随机存取存储器(ram)单元，或被配置为存储包括在各种条目中的单独数据位的其他合适的存储电路。
71.如图所示，在时间t0，通道0加载有字0＝c。这里，“c”用作用于表示多位值的一般值。这里不使用十六进制和其他表示。例如，值“c”可表示32位字。在时间t1，通过散列函数生成索引，并且得到的索引是7。在时间t2，生成读取请求。读取请求将索引指定为7。将读取
请求发送到字典510，并且访问条目7。存储在条目7中的值(该值为值c)被复制且返回到通道0。
72.在时间t3，通道0中的比较逻辑比较两个值。第一值是从字典510的条目7中检索的值c。第二值是字0的值，该值是c。比较结果是命中。在时间t4，通道0内的逻辑确定不存在字典510的更新。在时间t5，开始两个操作。第一操作是用字1＝c加载通道0。第二操作为字0构建包。关于第一操作，针对字0＝c的情况，不对字典510执行更新。然而，如果更新确实发生在时间t4，然后那些更新需要在对字1＝c的任何读取请求被发送到字典510之前完成。在通道0的第二个副本中示出用字1＝c加载通道0。关于第二操作，在实施方案中，所生成的压缩的包类似于图3中所描绘的那些。例如，可为字0生成压缩的包303。
73.如图所示，在时间t5，通道0加载有字1＝c。再次，在通道0的第二副本中示出用字1＝c加载通道0。由散列函数生成索引，并且得到的索引是7。在时间t6(为了便于例示而未示出)，生成读取请求。读取请求将索引指定为7。将读取请求发送到字典510，并且访问条目7。存储在条目7中的值(该值为值c)被复制且返回到通道0。在时间t7(未示出)，通道0中的比较逻辑比较两个值。第一值是从字典510的条目7中检索的值c。第二值是字1的值，该值是c。比较结果是命中。
74.在时间t8(未示出)，通道0内的逻辑确定不存在字典510的更新。在时间t9(未示出)，开始两个操作。第一操作是用字2＝c加载通道0。第二操作是为字1构建包。对字2和字3重复操作。如图所示，时间t1和时间t5处的操作可并行完成，所以虽然用单个硬件通道示出了串行实施，但是在为较早的字生成压缩的包之前，后续字的处理可开始。于是，可在指示的时间(诸如时间t1到时间t5)之间以及在指示的时间内使用其他流水线级。例如，在时间t1，第一流水线级可加载字，并且第二流水线级可生成索引。然而，字之间存在依赖关系，诸如基于比较结果更新字典510和从字典510读取条目。
75.现在参考图6，示出了例示压缩处理600的另一实施方案的框图。在例示的实施方案中，对混合压缩算法执行串行执行，该混合压缩算法使用基于统计的压缩算法和基于字典的压缩算法的组合。如图所示，使用被称为“通道0”的单个硬件通道。较早描述的字典510被相同地编号。
76.如图所示，在时间t0，通道0加载有字0＝a。在时间t1到时间t5执行的操作与图5中描述的相同。然而，这里，存储在字典510的条目7中的值是a。在时间t5，通道0加载有字1＝b。虽然值b与值a不同，但是由散列函数使用的值b的子集生成相同的索引，该索引为7。在一个示例中，子集是32位字的位10到位17。因而，在时间t7(未示出，但相当于时间t3)，比较逻辑将字1的值b和从字典510的条目7中检索的值a进行比较。在该示例中，比较结果是未命中。部分命中的比较结果也是可能的，但在该示例中，使用了未命中。在时间t8，字典510的条目7用字1的值b更新，因为字1现在是最近看到的字。
77.在时间t9，通道0加载有字2＝b，并且由散列函数生成索引7。因而，在稍后的时间t11(未示出，但相当于时间t3)，比较逻辑将字2的值b和从字典510的条目7中检索的值b进行比较。比较结果是命中。于是，字典510不需要更新。
78.在时间t13，通道0加载有字3＝c。虽然值c与值a和值b不同，但是由散列函数使用的值c的子集生成相同的索引，该索引为7。因而，在时间t15(未示出，但相当于时间t3)，比较逻辑将字3的值c和从字典510的条目7中检索的值b进行比较。在该示例中，比较结果是未
命中。部分命中的比较结果也是可能的，但在该示例中，使用了未命中。在时间t16，字典510的条目7用字3的值c更新，因为字3现在是最近看到的字。如在该示例中可看到的，字之间存在依赖关系，诸如基于比较结果更新字典510和从字典510读取条目。然而，读取给定字的字典510的条目与为比给定字更旧的且在给定字之前处理的字生成压缩的包无关。
79.现在参考图7，示出了例示压缩处理700的一个实施方案的框图。在例示的实施方案中，对混合压缩算法执行并行执行，该混合压缩算法使用基于统计的压缩算法和基于字典的压缩算法的组合。如图所示，使用被称为“通道0”、“通道1”、“通道2”和“通道3”的多个硬件通道。虽然在例示的实施方案中示出了四个硬件通道，但是另一数量的多个硬件通道是可能的和可设想的。较早描述的字典510被相同地编号。
80.如较早描述的，可在指示的时间之间(诸如时间t1到时间t5中的每个之间)以及在指示的时间内使用流水线级。例如，在时间t1，第一流水线级可加载多个字，并且第二流水线级可为多个加载的字中的每个生成索引。另外，指示的时间中的一个或多个可放置在相同的流水线级中。例如，如果操作在给定时钟循环内完成，则在时间t3和时间t4处实行的操作可组合在单个流水线级中。如图所示，在时间t0，通道0到通道3中的每个加载有字0到字3中的相应一个。在该示例中，字0到字3中的每一个具有值c。
81.在带有一些调整的情况下，在时间t1到时间t5为通道0到通道3的给定硬件通道执行的操作与图5中被描述用于单个硬件通道的相同。例如，在时间t2，代表硬件通道通道0到通道3从通道0将单个读取请求发送到字典510。在各种实施方案中，压缩引擎中的控制逻辑确定通道0到通道3的每个硬件通道访问字典510的相同条目。在各种实施方案中，在硬件电路中实施控制逻辑。因而，已知通道0具有一组字字0到字3中的最旧的字。在这种情况下，字0是最旧的字，字0被加载到通道0中。
82.另外，控制逻辑确定通道3具有该组字字0到字3中的最新的字。在这种情况下，字3是最新的字，字3被加载在通道3中。在第一组字(诸如字0到字3)和第二组字(诸如带有字4到字7的稍后的一组加载的字)之间存在依赖关系。在图7的例示的实施方案中，比较结果不指示需要更新字典510。然而，如果将字3＝c的值发送到字典510以更新字典510的条目7，则不发生损坏。
83.基于字0到字3的比较结果的字典510的更新需要在将对稍后字4到字7中的任一个的读取请求发送到字典510之前完成。然而，依赖关系基于由当前最新的字(该当前最新的字为字3)更新字典510，而不是字0到字3中任两个字之间的依赖关系。下一个示例突出了该事实。
84.现在参考图8，示出了例示压缩处理800的另一实施方案的框图。在例示的实施方案中，使用硬件通道通道0到通道3和字典510，并行执行再次被执行以用于混合压缩算法。如图所示，在时间t0，通道0到通道3中的每个加载有字0到字3中的相应的一个。在该示例中，字0具有值a，字1和字2中的每个具有值b，并且字3具有值c。字典510的条目7具有值a。在带有一些调整的情况下，在时间t1到时间t5为通道0到通道3中的给定的硬件通道执行的操作与较早描述的相同。在时间t1，当发现通道0到通道3中的每个生成相同的索引7时，在各种实施方案中，在电路中实施的控制逻辑确定通道0具有带有相同索引的一组字字0到字3中的最旧的字。附加地，控制逻辑确定通道3具有带有相同索引的一组字字0到字3中的最新的字。
85.在一些实施方案中，当字0到字3中的至少一个字不具有与另一字相同的索引时，该至少一个字还没有传递到下一个流水线级，以便仅同时处理带有相同索引的一组字。例如，如果字3具有索引12，则字0到字2可传递到下一个流水线级，用于访问字典510，而字3等待。然而，字3仍然在稍后的字4前面沿着流水线级移动。在其他实施方案中，当字3具有不同的索引(诸如索引12)时，当其他字在他们当中具有相同的索引7时，字3传递到下一个流水线级。在此类情况下，字典510为双端口的以支持两个同时访问，或者字3在该稍后的流水线级中等待访问字典510。
86.在另一示例中，当字1具有索引12而字0、字2和字3中的每个具有索引7时，在一些实施方案中，字0被独自发送到下一个流水线级。在稍后的时钟循环中，字1被独自发送到下一个流水线级。在稍后的流水线级中，字2和字3中的每个被发送到下一个流水线级。因而，维持字0到字3的排序，并且压缩的包的生成具有相同的次序。在其他实施方案中，字0、字2和字3中的每个在下一个流水线级中一起被发送，但是指示被维持指定字1比字0较新且比字2更旧。在其他实施方案中，将字0到字3中的每个发送到下一个流水线级，并且字典510是双端口的以支持两个同时访问。
87.返回到字0到字3中的每个具有相同索引7的示例，在时间t2，代表硬件通道通道0到通道3，将单个读取请求从通道0发送到字典510。在时间t3，应当注意，在通道0到通道3中执行的比较中的每个是在通道的相应字的值和从字典510的条目7检索的值之间。因而，虽然在字0到字3的每个之间存在依赖关系，但是来自字典510的条目7的值a的副本用于通道0到通道3的每个中。例如，再次简要地参考图6，在串行执行期间，当考虑字之间的依赖关系时，将字2和字3中的每个与值b相比较。字典510的更新发生在字0到字3中的每个的串行处理之间。然而，这里在图8中，在并行执行期间，将字2和字3中的每个与值a(值a是字典510的条目7的副本)相比较，而尚未对字典510执行更新。虽然字0到字3和条目7的初始值是相同的，但是用由多个硬件通道并行执行在图8中示出的比较结果与用由单个硬件通道串行执行在图6中示出的比较结果不同。
88.图6中的比较结果可用于为字0到字3中的每个生成压缩的包，而图8中的比较结果不能用于为字0到字3中的每个生成压缩的包。然而，再次允许稍后第二组字(诸如字4到字7)中的任一个访问字典510依赖于由当前最新的字(该当前最新的字为字3)更新字典510，而不是字0到字3的任何两个字之间的依赖关系。因而，一旦已知由当前最新的字(该当前最新的字为字3)更新字典510，就准许稍后第二组字(诸如字4到字7)访问字典510。例如，可将最新字的更新转发(旁路)到来自稍后第二组字(诸如字4到字7)的读取请求。
89.在例示的实施方案中，在时间t4，已知字3是带有相同索引(7)的一组字(字0到字3)中的最新的字，并且另外，已知针对该组字发生至少一个更新。例如，未命中的比较结果指示将更新字典510。如较早描述的，部分命中的比较结果也指示将更新字典510。虽然至少一个字典更新的指示可不用于生成压缩的包，但是该指示可用于确定是否将更新字典510。在该示例中，除了确定更新是用值c写入条目7之外，控制逻辑确定发生字典510的更新。因而，在时间t5，为字0到字3中的每个生成压缩的包，而同时，稍后第二组字4到字7被加载到通道0到通道3中。
90.在一些实施方案中，在时间t4，将稍后第二组字4到字7加载到通道0到通道3中，并且通过散列函数找到相应的索引。在时间t5的时候，如果字4到字7具有相同的索引，则代表
字4到字7，将读取请求发送到字典510。此外，如果字4到字7也具有相同的索引7，则可将对应于字3的更新转发到该读取请求。因而，虽然在对字4到字7的读取请求之前尚未确定字0到字3之间的依赖关系，但是针对字4到字7，通道0到通道3在时间t6使用值c用于比较。
91.在一些实施方案中，不存在用于生成压缩的包的可观数量的时间约束。当对成组的压缩的包执行多次传递时，可隐藏用于生成压缩的包的延迟。因而，在时间t5，当处理已经在第二组字4到字7上开始时，用于确定字0到字7之间的真实依赖关系的控制逻辑可开始处理。例如，完成找到用于比较操作的真实依赖值。再次简要地参考图6，字2和字3中的每个的真实依赖值是值b而不是值a。值b是字1的值，字1是比字2更旧的字中的最新的字。字0和字1中的每个比字2更旧，并且字1是这两个字中的最新的字。类似地，字0、字1和字2中的每个都比字3更旧，并且字2是这三个字中的最新的字。字2的值也是b，并且字2的值是用于字3的比较操作的真实依赖值。
92.用于找到真实依赖值的控制逻辑可包括比较逻辑和多路复用器电路。用于找到真实依赖值的延迟可为可观的，尤其是随着硬件通道的数量增加。不是在处理第一组字0到字3和第二组字4到字7之间添加该延迟，而是可在稍后组内固定操作和后续压缩的包生成中移除和隐藏该延迟。应当注意，针对加载到通道0中的字不会发生固定，因为在一些实施方案中，加载到通道0中的字始终是特定索引的最旧的字。因而，比较操作的真实依赖值始终是从字典510读取的值或从先前字的处理转发(旁路)的值。
93.现在参考图9，示出了用于有效压缩数据的方法900的一个实施方案的一般化流程图。为了讨论的目的，以顺序的次序示出了该实施方案中(以及用于图11)的步骤。然而，在其他实施方案中，一些步骤可以与所示次序不同的次序发生，可并发执行一些步骤，一些步骤可与其他步骤组合，并且一些步骤可不存在。
94.在一些实施方案中，指令提取单元从指令高速缓存或系统存储器中的其他合适位置接收指令。该指令被解码且确定为压缩指令(框902)。在实施方案中，压缩/解压缩单元的压缩引擎将源数据(诸如源页面)加载(预取)到源缓冲器中(框904)。在一些实施方案中，源数据首先存储在数据高速缓存中，并且然后稍后存储在压缩/解压缩单元中的读取缓冲器中。在实施方案中，由处理器核心预取第一数量的行，并且稍后由包括在压缩/解压缩单元中的专用电路预取剩余在期望的该页源数据中的剩余行。专用电路可使用预先确定的步距值进行预取，该预先确定的步距值针对压缩和解压缩操作可为不同的。
95.多个硬件通道中的至少两个或更多个硬件通道被分配有源数据的相应字(框906)。在一些实施方案中，源数据被划分为部分诸如固定大小的字。为每个字确定特定索引，其中索引指定将访问的字典的条目(框908)。字典存储压缩或解压缩操作期间最近看到的字。如较早描述的，字内的特定位字段与散列函数一起使用以生成索引。针对第一组字，访问字典，第一组中的每个字具有相同的第一索引(框910)。例如，代表带有相同索引的第一组中的多个字，将单个读取请求发送到字典。
96.在确定第一组的真实组内依赖关系之前，针对第二组字，访问字典，第二组中的每个字具有相同的索引(框912)。在各种实施方案中，第一组和第二组中的每个具有相同的索引，并且因此访问字典中的相同条目。针对第一组的给定字，真实组内依赖关系是比第一组的给定字更旧的字中的每个的比较结果和字典更新。给定字的比较结果和字典更新是比第一组中的给定字较新的字的真实组内依赖关系的部分。第一组的真实组依赖关系用于为第
一组生成压缩的包，并且为后续和较新的第二组正确更新字典。然而，当已知第一组的最新的字且发现针对第一组发生至少一个字典更新时，尽管还未知第一组的真实组内依赖关系，但是现在已知第二组需要的字典更新。第二组需要的字典更新是被写入由第一组的索引指向的字典的条目中的第一组的最新的字的值。在各种实施方案中，第一组的最新的字的值被转发(旁路)到第二组，而实际上在稍后或同时发生字典更新。
97.为第一组和第二组中的每个中的字生成压缩的包(或“压缩包”)(框914)。在各种实施方案中，为至少第一组执行组内固定操作。在实施方案中，在压缩操作的处理期间，基于将第一组的每个字与存储在由第一组的索引指向的字典条目中的字的副本进行比较，生成至少一个字典更新的指示。在组内固定(定位(fixup))操作期间，通过找到用于与第一组的每个字进行比较的真实值来找到真实组内依赖关系。在一些实施方案中，第一组的给定字的真实值是比第一组的给定字更旧的最新字的值。
98.如较早描述的，用于找到用于与第一组中的给定字进行比较的真实组内依赖值的控制逻辑可包括比较逻辑和多路复用器电路。用于找到真实组内依赖值的延迟可为可观的，尤其是随着硬件通道的数量增加。不是在第一组和第二组的处理之间添加该延迟，而是可在稍后组内固定操作中移除和隐藏该延迟。在提供压缩操作的其他示例之前，接下来描述解压缩操作的示例。
99.现在转向图10，示出了例示解压缩处理1000的一个实施方案的框图。在例示的实施方案中，再次对混合压缩算法执行并行执行。这里，并行硬件通道通道0到通道3用于解压缩引擎中。虽然在例示的实施方案中示出了四个硬件通道，但是另一数量的多个硬件通道是可能的和可设想的。较早描述的字典510被相同地编号。类似于压缩引擎的硬件通道，解压缩引擎的硬件通道可使用流水线级。
100.如图所示，通道0被分配带有指定命中的cmd(命令)和索引7的包0。虽然在名称中没有使用“压缩的”，但是包0到包3中的每个是如较早描述的生成的压缩的包。通道1被分配带有指定未命中的cmd和带有值b的有效载荷的包1。通道2被分配带有指定命中的cmd和索引7的包2，并且通道3被分配带有指定未命中的cmd和带有值c的有效载荷的包3。字典510的条目7初始存储值a。在时间t1，不带有索引的包具有从相应的有效载荷生成的索引。可再次使用较早描述的索引生成操作。如图所示，包1和包3中的每个具有生成的索引7。
101.在各种实施方案中，解压缩引擎中的控制逻辑确定通道0到通道3的每个硬件通道由于具有相同的索引7而访问字典510的相同条目。在各种实施方案中，在硬件电路中实施控制逻辑。因而，已知通道0具有最旧的包，并且通道3具有包0到包3的最新的包。在时间t2，代表硬件通道通道0和通道2，将单个读取请求从通道0发送到字典510。包1和包3中的每个具有有效载荷，并且因此，不需要针对对应于压缩的包的字访问字典510。如图所示，通道0和通道2中的每个从字典510的条目7接收值a作为解压缩的字。
102.再次简要地参考图6，可看到字2具有值b。因而，针对图10中的字2，解压缩引擎具有错误值a。如果在时间t2考虑了真实组内依赖关系，则值b将被确定用于字2。然而，类似于压缩引擎且为了实现相对高的吞吐量，解压缩引擎此时不确定真实组内依赖关系。允许稍后第二组包(诸如包4到包7)的任何包访问字典510依赖于由当前最新包(当前最新包为包3)更新字典510，而不是包0到包3的任何两个包之间的依赖关系。因而，一旦已知由当前最新的包(当前最新的包为包3)更新字典510，就准许稍后第二组包(诸如包4到包7)访问字典
510。例如，可将最新包的更新转发(旁路)到来自稍后第二组包的读取请求。
103.在例示的实施方案中，在时间t3，已知包3是带有相同索引(7)的包0到包3的最新包，并且另外，已知针对该组包发生至少一个更新。例如，未命中的命令(cmd)指示将更新字典510。如较早描述的，部分命中的命令也指示将更新字典510。虽然至少一个字典更新的指示可不用于生成解压缩的字，但是该指示可用于确定是否将更新字典510。
104.在该示例中，除了确定更新是用值c写入条目7之外，控制逻辑确定发生字典510的更新。因而，在时间t4，为包0、包1和包3中的每个生成解压缩的字，并且将解压缩的字写入写入缓冲器中，同时稍后第二组包4到包7被加载到通道0到通道3中。如果使用转发(旁路)，则第二组包4到包7甚至更早地加载到通道0到通道3中。在一些实施方案中，针对包0到包3中的每个，无条件地发生组内定位操作。在其他实施方案中，该组中的最旧的包(诸如包0)跳过该操作。此外，包的命令可用于确定特定包是否需要组内定位。例如，未命中命令指示有效载荷具有正确的解压缩的字。相比之下，命中命令指示正确的解压缩的字在字典510中，并且从字典510读取的数据此时可不正确，因为此时没有考虑真实组内依赖关系以在稍后的时间内隐藏延迟。
105.现在参考图11，示出了用于有效压缩数据的方法1100的一个实施方案的一般化流程图。在一些实施方案中，指令提取单元从指令高速缓存或系统存储器中的其他合适位置接收指令。指令被解码且确定为解压缩指令(框1102)。在实施方案中，压缩/解压缩单元的解压缩引擎将源数据(诸如压缩的包的源页面)加载(预取)到源缓冲器中(框1104)。在一些实施方案中，源数据首先存储在数据高速缓存中，并且然后稍后存储在压缩/解压缩单元中的读取缓冲器中。针对压缩引擎类似的，可使用多种方法以将数据预取到源缓冲器中。
106.多个硬件通道中的至少两个或更多个硬件通道被分配有源数据的相应压缩的包(框1106)。针对没有指定用于访问字典的索引的压缩的包，确定特定索引(框1108)。字典存储压缩或解压缩操作期间最近看到的包。如较早描述的，包内的特定位字段与散列函数一起使用以生成索引。针对第一组包，访问字典，第一组中的每个包具有相同的第一索引(框1110)。例如，代表带有相同索引的第一组中的多个包，单个读取请求被发送到字典，并且不包括带有解压缩的字的有效载荷。
107.在确定第一组的真实组内依赖关系之前，针对第二组包，访问字典，第二组中的每个包具有相同的索引(框1112)。在各种实施方案中，第一组和第二组中的每个具有相同的索引，并且因此访问字典中的相同条目。针对第一组的给定包，真实组内依赖关系是作为包中的命令提供的比较结果和比第一组的给定包更旧的包中的每个的字典更新。给定包的比较结果和字典更新是比第一组中的给定包更新的包的真实组内依赖关系的部分。第一组的真实组依赖关系用于为第一组生成解压缩的字，并且为后续和较新的第二组正确更新字典。然而，当已知第一组的最新的包且在压缩期间发现第一组发生至少一个字典更新时，尽管还不知第一组的真实组内依赖关系，但是现在已知第二组需要的字典更新。第二组需要的字典更新是被写入由第一组的索引指向的字典的条目中的第一组的最新的包的解压缩的字的值。在各种实施方案中，第一组的最新的包的值被转发(旁路)到第二组，而实际上在稍后或同时发生字典更新。
108.为第一组和第二组中的每个中的包生成解压缩的字(框1114)。在各种实施方案中，对至少第一组执行组内固定操作。类似于压缩引擎的组内固定(定位)操作，解压缩引擎
的组内固定(定位)操作通过找到第一组的每个包的解压缩的字的真实源，确定真实组内依赖关系。在一些实施方案中，第一组的给定包的真实值是比第一组的给定包更旧的最新包的值。
109.如较早描述的，用于找到用于与第一组中的给定包进行比较的真实组内依赖值的控制逻辑可包括比较逻辑和多路复用器电路。用于找到真实组内依赖值的延迟可为可观的，尤其是随着硬件通道的数量增加。不是在第一组和第二组的处理之间添加该延迟，而是可在稍后组内固定操作中移除和隐藏该延迟。
110.现在参考图12，示出了例示压缩处理1200的一个实施方案的框图。在例示的实施方案中，使用硬件通道通道0到通道3和字典510，并行执行再次被执行以用于混合压缩算法。如图所示，在时间t0，通道0到通道3中的每个加载有字0到字3中的相应的一个。字0到字3的值与图8的例示的实施方案中使用的值相同。在带有一些调整的情况下，在时间t1到时间t5为通道0到通道3的给定硬件通道执行的操作与较早描述的相同。
111.在该例示的实施方案中，在时间t2，通道1到通道3确定用于与分配给通道的字的值相比较的真实组内依赖关系值。如较早描述的，在一些实施方案中，仅带有相同索引的字在流水线中一起前进。此外，较早描述了给定字的真实组内依赖值是比给定字更旧的字中的最新的。因而，由于将字分配给通道且仅允许带有相同索引的字在流水线中一起前进，所以真实依赖值是相邻通道中的字。预先已知，在通道0中字0的真实依赖值是从字典510读取的字，并且通道1中字1的真实依赖值是通道0中的字0，并且通道2中的字2的真实依赖值是通道1中的字1，并且通道3中的字3的真实依赖值是通道2中的字2。没有使用多路复用电路和比较器。相反，可使用直接线路。于是，在生成压缩的包之前不需要组内定位操作。
112.现在转向图13，示出了例示解压缩处理1300的一个实施方案的框图。在例示的实施方案中，使用硬件通道通道0到通道3和字典510，并行执行再次被执行以用于混合解压缩算法。如图所示，在时间t0，通道0到通道3中的每个加载有包0到包3中的相应的一个。包0到包3的值与图10的例示的实施方案中使用的值相同。在带有一些调整的情况下，在时间t1到时间t4为通道0到通道3的给定硬件通道执行的操作与较早描述的相同。
113.在例示的实施方案中，在时间t2，通道1到通道3确定用于生成其解压缩的字的真实组内依赖关系值。如较早描述的，在一些实施方案中，仅带有相同索引的包在流水线中一起前进。此外，较早描述了给定包的真实组内依赖值是比给定包更旧的包中的最新的。因而，由于将包分配给通道且仅允许带有相同索引的包在流水线中一起前进，所以在针对分配的包中的每个索引已知的时间t1之后，包的命令(cmd)用于在有效载荷(cmd＝未命中)和来自相邻通道的解压缩的字(cmd＝命中)之间进行选择。已知在时间t1和时间t2之间，在通道0中的包0的真实解压缩的字是从字典510读取的包，并且在通道1中的包1的真实解压缩的字是通道1的有效载荷，并且通道2中的包2的真实解压缩的字是通道3的有效载荷。一些多路复用电路和比较器用于cmd值。然而，延迟可仍然相当小，并且因此，在将解压缩的字存储在写入缓冲器中之前，不需要组内定位操作。
114.现在参考图14，示出了例示压缩处理1400的一个实施方案的框图。在例示的实施方案中，使用硬件通道通道0到通道3和字典510，并行执行再次被执行以用于混合压缩算法。如图所示，在时间t0，通道0到通道3中的每个加载有字0到字3中的相应的一个。字0到字3的值与图8和图12的例示的实施方案中使用的值相同。除了以不同次序实行，在时间t1到
时间t5为通道0到通道3的给定硬件通道执行的操作与较早描述的相同。
115.如较早描述的，可提前已知，通道0具有字0到字3中最旧的字，并且通道3具有字0到字3中最新的字。在时间t2，将单个读取请求从通道0发送到字典510。此外，在时间t2，最新的字(最新的字为字3)的值被存储用于字典510的稍后更新。例如，字3的值c可存储在寄存器中以用于写入字典510的条目7且用于将值c转发(旁路)到带有字4到字7的较新的第二组。在时间t4，开始用于找到真实组内依赖值的确定。在一些实施方案中，时间t4处的处理步骤持续两个或更多个流水线级。在时间t5完成比较，并且生成压缩的包，而不执行组内定位操作。
116.在各种实施方案中，软件应用程序的程序指令可用于实施先前描述的方法和/或机制。程序指令可以诸如c的高级编程语言来描述硬件的行为。另选地，可使用硬件设计语言(hdl)，诸如verilog。程序指令可存储在非暂态计算机可读存储介质上。许多类型的存储介质是可用的。在使用期间，可由计算机访问存储介质，以将程序指令和所附数据提供给计算机用于程序执行。在一些实施方案中，合成工具读取程序指令，以便产生包括来自合成库的门列表的网表。
117.应该强调，上述实施方案仅是具体实施的非限制性实施例。一旦充分了解上面的公开，许多变型和修改对于本领域的技术人员而言将变得显而易见。本发明旨在使以下权利要求书被解释为涵盖所有此类变型和修改。

技术特征：
1.一种装置，包括：表，所述表包括多个条目；和压缩电路，所述压缩电路包括多个硬件通道，其中响应于接收到压缩指令的指示，所述压缩电路被配置为：将第一组两个或更多个输入字分配给所述多个硬件通道；响应于确定第一组两个或更多个输入字中的至少第一输入字和第二输入字对应于所述表的相同条目，针对第一输入字和第二输入字生成：针对所述表的单个读取请求；和针对所述表的单个写入请求；以及针对第一输入字和第二输入字中的每一个生成压缩包。2.根据权利要求1所述的装置，其中所述压缩电路还被配置为针对被分配给所述多个通道中的通道的每个字生成索引。3.根据权利要求2所述的装置，其中为了确定第一组两个或更多个输入字中的第一输入字和第二输入字对应于所述表的相同条目，所述压缩电路被配置为确定第一输入字和第二输入字具有相同的索引。4.根据权利要求1所述的装置，其中所述压缩电路被配置为至少部分地基于给定输入字的散列来生成对应于所述给定输入字的索引。5.根据权利要求1所述的装置，其中所述压缩电路被配置为在确定第一组的输入字之间的依赖关系之前，确定是否用第一组的输入字中的任何输入字来更新所述表。6.根据权利要求5所述的装置，其中所述压缩电路被配置为：将多个输入字中的第二组输入字分配给第一多个硬件通道，其中第二组与第一组不同；其中针对将访问的每个表条目，所述压缩电路还被配置为：确定第一组的最新输入字；以及在确定第一组的输入字之间的依赖关系之前，将所述最新字转发到第二组。7.根据权利要求6所述的装置，其中针对将访问的每个表条目，所述压缩电路还被配置为：确定第一组的最旧输入字；以及仅从所述多个硬件通道中分配给所述最旧输入字的硬件通道发送针对所述表中的输入字的读取请求。8.一种方法，包括：在包括多个条目的表中存储输入字；以及响应于接收到压缩指令的指示：将第一组两个或更多个输入字分配给多个硬件通道；响应于确定第一组两个或更多个输入字中的至少第一输入字和第二输入字对应于所述表的相同条目，针对第一输入字和第二输入字生成：针对所述表的单个读取请求；和针对所述表的单个写入请求；以及针对第一输入字和第二输入字中的每一个生成压缩包。
9.根据权利要求8所述的方法，还包括针对被分配给所述多个通道中的通道的每个字生成索引。10.根据权利要求9所述的方法，其中为了确定第一组两个或更多个输入字中的第一输入字和第二输入字对应于所述表的相同条目，所述方法包括确定第一输入字和第二输入字具有相同的索引。11.根据权利要求8所述的方法，还包括至少部分地基于给定输入字的散列来生成对应于所述给定输入字的索引。12.根据权利要求8所述的方法，还包括在确定第一组的输入字之间的依赖关系之前，确定是否用第一组的输入字中的任何输入字来更新所述表。13.根据权利要求12所述的方法，还包括：将多个输入字中的第二组输入字分配给所述多个硬件通道，其中第二组与第一组不同；以及针对将访问的每个表条目：确定第一组的最新输入字；以及在确定第一组的输入字之间的依赖关系之前，将所述最新字转发到第二组。14.根据权利要求13所述的方法，其中针对将访问的每个表条目，所述方法还包括：确定第一组的最旧输入字；以及仅从所述多个硬件通道中分配给所述最旧输入字的硬件通道发送针对所述表中的输入字的读取请求。15.一种系统，包括：存储器；高速缓存，所述高速缓存耦接到存储器；和处理器，所述处理器耦接到所述存储器和所述高速缓存，其中所述处理器被配置为：将第一组两个或更多个输入字分配给多个硬件通道；响应于确定第一组两个或更多个输入字中的至少第一输入字和第二输入字对应于表的相同条目，针对第一输入字和第二输入字生成：针对所述表的单个读取请求；和针对所述表的单个写入请求；以及针对第一输入字和第二输入字中的每一个生成压缩包。16.根据权利要求15所述的系统，其中所述处理器还被配置为针对被分配给所述多个通道中的通道的每个字生成索引。17.根据权利要求16所述的系统，其中为了确定第一组两个或更多个输入字中的第一输入字和第二输入字对应于所述表的相同条目，所述处理器被配置为确定第一输入字和第二输入字具有相同的索引。18.根据权利要求15所述的系统，其中所述处理器被配置为至少部分地基于给定输入字的散列来生成对应于所述给定输入字的索引。19.根据权利要求15所述的系统，其中所述处理器被配置为在确定第一组的输入字之间的依赖关系之前，确定是否用第一组的输入字中的任何输入字来更新所述表。20.根据权利要求19所述的系统，其中所述处理器被配置为：
将多个输入字中的第二组输入字分配给第一多个硬件通道，其中第二组与第一组不同；其中针对将访问的每个表条目，所述处理器还被配置为：确定第一组的最新输入字；以及在确定第一组的输入字之间的依赖关系之前，将所述最新字转发到第二组。

技术总结
本发明涉及用于执行存储器压缩的系统和方法。描述了用于高效地移动数据以用于存储和处理的系统、装置和方法。在各种实施方案中，处理器内的压缩单元包括多个硬件通道，选择两个或更多个输入字以进行压缩，并且用于将它们分配给多个硬件通道中的两个或更多个。当处理每个分配的输入字时，将每个字与表的多个条目的条目进行比较。如果确定分配的输入字中的每个索引表的相同条目，则带有最旧输入字的硬件通道生成针对表条目的单个读取请求，并且带有最新输入字的硬件通道生成针对在完成压缩时更新表条目的单个写入请求。每个硬件通道基于其分配的输入字生成压缩的包。分配的输入字生成压缩的包。分配的输入字生成压缩的包。


技术研发人员：A
受保护的技术使用者：苹果公司
技术研发日：2018.07.26
技术公布日：2023/10/8