高带宽压缩至编码的数据流的制作方法
高带宽压缩至编码的数据流的制作方法
【技术领域】
[0001] 本发明总体设及一种改进的数据处理装置和方法，更具体来说，设及高带宽压缩 至编码的数据流。
【背景技术】
[0002] Deflate是一种无损数据压缩算法，采用了LZ77算法和霍夫曼化uffman)编码的 组合。LZ77算法通过将重复出现的数据替换为对在输入（未压缩的）数据流中较早存在的 该数据的单一拷贝的引用而实现压缩。用一个称作长度-距离对的数字对编码一个匹配， 该相当于声明"每个下一个长度的字符，等于未压缩流中在其之后一定距离的字符"。"距 离"有时也被称为"偏址"（offset)。
[0003] 霍夫曼编码是一种用于无损数据压缩的滴编码算法。该个术语指的是用一个可变 长度代码表来编码一个源符号，其中，可变长度代码表已经被W特定的方式根据源符号的 每个可能值的发生的估计概率导出。
[0004] 在压缩块内，如果发现重复的字节序列（重复的字符串），则插入一个链接到相同 字符串的先前位置的反向引用（back-reference)。一个较早字符串的编码匹配，由长度 (3 - 258字节）和距离（1 - 32768字节）组成。可W跨任意数量的块作出相对的反向引用， 只要距离出现在解码的未压缩数据的最后32kB(称为滑动窗口）。
[0005] 第二压缩阶段包括用较短的表示来替代常用的符号，用较长的表示来替代不常用 的符号。霍夫曼编码创建一个无重叠区间（non-overlappingintervals)的无前缀树，其中 每个序列的长度与那个符号需要编码的概率成反比。符号要被编码的可能性越大，它的比 特序列化it-sequence)就越短。
【发明内容】
[0006] 在一个示例性实施例中，一种用于在数据处理系统中流水线式压缩多字节帖的方 法包含组合输入数据流中当前周期的数据与所述输入数据流中下一个周期的数据的至少 一部分，W构成数据帖。该方法进一步包含识别多个词典存储器的多个匹配。每个匹配与 该数据帖中的给定子字符串的一部分匹配。该方法进一步包含从该多个匹配中识别提供对 当前周期的数据的最佳覆盖的匹配子集。该方法进一步包含把该数据帖编码成编码的输出 数据流。
[0007]在另一个示例性实施例中，提供一种计算机程序产品，包含其中存储有计算机可 读程序的计算机可读介质。该计算机可读程序在计算设备上执行时使计算设备上文关于方 法示例性实施例所述的操作的各种操作或操作组合。
[000引在另一个示例性实施例中，提供一个系统/装置。该装置用于在数据处理系统中 流水线式压缩多字节帖，包含：词典查询/更新阶段，其包含多个词典存储器和相关逻辑； 匹配选择阶段，其包含多个比较电路和相关逻辑；和编码阶段。词典查询/更新阶段接收包 含输入数据流中当前周期的数据与所述输入数据流中下一个周期的数据的至少一部分组 合的数据帖，识别多个词典存储器的多个匹配。每个匹配与该数据帖中的给定子字符串的 一部分匹配。匹配选择阶段用多个比较电路从提供对当前周期的数据的最佳覆盖的多个匹 配中识别匹配的子集。编码阶段把该数据帖编码成编码的输出数据流。
[0009] 本发明的该些和其它特点和优点，将在W下对本发明的示例性实施例的详细说明 中描述，所属技术领域的普通技术人员从中也可W明了该些和其它特点和优点。
【附图说明】
[0010] 本发明及其优选应用方式、W及其进一步的目的和优点，可结合附图阅读下文对 示例性实施例的详细说明而得到最好的理解，附图中：
[0011] 图1表示一例在其中可W实现示例性实施例的各方面的分布式数据处理系统的 图示；
[0012] 图2是一例在其中可W实现示例性实施例的各方面的分布式数据处理系统的框 图；
[0013] 图3是表示按照一个示例性实施例的、处理一个任意长度的任意字节流并输出一 个压缩数据格式的字节流的机制的框图；
[0014]图4描述按照一个示例性实施例的、把一个输入数据流转换成两周期的数据帖的 转换阶段；
[0015] 图5描述按照一个示例性实施例的、为词典查询/更新生成地址；
[0016] 图6描述按照一个示例性实施例的词典查询/更新阶段；
[0017] 图7是表示按照一个示例性实施例的用于匹配选择的机制的框图；
[0018] 图8示出了按照一个示例性实施例的匹配选择和对准；和
[0019] 图9是表示按照一个示例性实施例的高带宽压缩至编码的数据流的机制的流程 图。
【具体实施方式】
[0020] 示例性实施例提供一种处理连续周期中的数据流W实现低延时和高吞吐率的机 审IJ。将词典组织成阵列，一个周期数据中的每个字节偏址对应一个阵列。若干阶段（stages) 要求有下个周期可立即用于相同阶段的结果。
[0021] 示例性实施例可W在许多不同类型的数据处理环境中使用。为了为描述示例性实 施例的特定元素和功能提供语境（context)，W下提供图1和2,作为可在其中实现示例性 实施例的各方面的环境的例子。应该明白，图1和2仅仅是例子，并非是提出或暗示对可在 其中实现示例性实施例的各方面的环境的任何限制。在不脱离本发明的精神和范围的情况 下可W对所示的环境作出许多修改。
[0022] 图1表示一例在其中可W实现示例性实施例的各方面的分布式数据处理系统的 图示。分布式数据处理系统100可W包括一个在其中可W实现示例性实施例的各方面的计 算机网络。分布式数据处理系统100包含至少一个网络102,该是提供分布式数据处理系统 100内连接在一起的各种设备和计算机之间的通信链路的媒介。网络102可W包括诸如电 线、无线通信链路、或光纤电缆的连接。
[0023] 在所示的例子中，服务器104和服务器106随存储单元108 -起连接到网络102。 此外，客户机11〇、112、和114也连接到网络102。该些客户机110、112、和114,例如可W是 个人电脑、网络计算机之类。在所示的例子中，服务器104向客户机110、112、和114提供 诸如引导文件、操作系统映像和应用程序的数据。在所示的例子中，客户机11〇、112、和114 是服务器104的客户机。分布式数据处理系统100可W包含额外的服务器、客户机、W及未 予示出的其它设备。
[0024] 在所示的例子中，分布式数据处理系统100是因特网与代表使用传输控制协议/ 因特网协议（TCP/I巧的一套协议相互通信的世界范围的网络和网关的网络102。在因特 网的核屯、是包括路由数据和消息的数W千计的商业、政府、教育计算机系统和其他计算机 系统的主要节点或主机之间的高速数据通信线路的骨干。当然，分布式数据处理系统100 的具体实现还可W包含许多不同类型的网络，例如内部网、局域网（LAN)、广域网（WAN),等 等。如上所述，图1意在举例，而不是对本发明的不同实施例的结构限定，因此，图1中所 示的特定元素，不应被视为对可W在其中实现本发明的示例性实施例的各方面的环境的限 制。
[0025] 图2是一例在其中可W实现示例性实施例的各方面的分布式数据处理系统的框 图。数据处理系统200是一例计算机，诸如图1中的客户机110,其中具有实现本发明的示 例性实施例的过程的计算机可用代码或指令。
[0026] 在所示的例子中，数据处理系统200采用包括北桥与存储器控制器中枢（NB/ MCH) 202和南桥与输入/输出（I/O)控制器中枢（SB/ICH) 204的中枢结构。处理单元206、 主存储器208和图形处理器210连接到NB/MCH202。图形处理器210也可W通过加速图形 端口（AGP)连接到NB/MCH202。
[0027] 在所示的例子中，局域网（LAN)适配器212连接到SB^CH204。音频适配器216、 键盘和鼠标适配器220、调制解调器222、只读存储器（ROM) 224、硬盘驱动器（皿D) 226,光驱 230、通用串行总线扣SB)端口和其他通信端口 232,W及PCI/PCIe设备234通过总线238 和总线240连接到SB/1CH204。PCI/PCIe设备例如可W包括W太网适配器、附加（add-in) 卡、W及笔记本电脑的PC卡。PCI使用一个卡式总线控制器，而PCIe则不是。ROM224例 如可W是闪速（flash)基本输入/输出系统炬10巧。
[0028] 皿D226和CD-ROM驱动器230通过总线240连接到SB/1CH204。皿D226和CD-ROM驱动器230可W使用例如集成驱动电子（I呢）或串行高级技术附件（SATA)接口。 超级I/0(SI0)设备236可W连接到SB/ICH204。
[0029] 操作系统在处理单元206上运行。操作系统协调并提供对图2中的数据处理系 统200内的各种部件的控制。作为客户机，操作系统可W是商业上可获得的操作系统，例如 MicrosoftWindows7 (Microsoft和Windo ws是微软公司在美国和其他国家的注册商标）。 面向对象的编程系统，如化va编程系统，可W与操作系统协作地运行，提供从在数据处理 系统200上执行的化va程序或应用程序的对操作系统的调用aava是甲骨文公司和/或 其关联公司的商标。）
[0030] 作为服务器，数据处理系统200可W是例如'IBM⑧eServer?系统P饭型计算机 系统，运行高级交互指令（AIX⑧）操作系统或Linux操作系统（IBM、eServer、系统P和AIX是国际商业机器公司在美国/其他国家的商标，Linux是LinusTorvalds在美国/其 他国家的注册商标）。数据处理系统200可W是处理单元202中包括多个处理器的对称多 处理器（SM巧系统。另外，也可W采用单处理器的系统。
[0031] 操作系统、面向对象的编程系统、W及应用或程序的指令，位于存储设备上，如皿D 226上，可W被装入主存储器208,供处理单元206执行。本发明的示例性实施例的过程可 W由处理单元206用计算机可用代码执行，计算机可用代码可位于存储器中，如主存储器 208、ROM224中，或位于例如一个或多个外围设备226和230。
[0032] 诸如图2中所示的总线238或总线240的总线系统，可包含一个或更多总线。当 然，总线系统可W采用用于实现与其附接的不同组件和设备之间的数据传输的任何类型的 通信组织或架构。诸如图2的调制解调器222或网络适配器212的通信单元，可W包括一 个或多个用于发送和接收数据的设备。存储器可W是例如主存储器208、R0M224或者诸如 见于图2的NB/MCH202中的高速缓存。
[0033] 所述技术领域的技术人员应当明白，图1和2中的硬件，可W因具体实现而异。其 它内部硬件或外设，诸如闪存、等同的非易失性存储器、或光盘驱动器之类，也可W在图1 和2中所示的硬件W外使用，或者代替所示的硬件。此外，在不脱离本发明的精神和范围的 情况下，也可W将示例性实施例的过程应用于多处理器数据处理系统，而不是先前提到的 SMP系统，
[0034] 此外，数据处理系统200可W采取多种不同数据处理系统的任何数据处理系统的 形式，包括客户端计算设备、服务器计算设备、平板电脑、笔记本电脑、电话或其它通信设 备、个人数字助理（PDA),等等。在一些示例性例子中，数据处理系统200可W是便携式计算 设备，其配置有闪存，用来提供例如存储操作系统文件和/或用户生成的数据的非易失性 存储器。实际上，数据处理系统200可W是任何已知或今后开发的数据处理系统，对其没有 结构性限制。
[0035] 数据处理系统200可能由于各种原因而需要数据压缩。例如，数据处理系统200 可W压缩存储到磁盘226的数据，或压缩在网络适配器212上发送的数据。
[0036] 图3是表示按照一个示例性实施例的、处理一个任意长度的任意字节流并输出一 个压缩数据格式的字节流的机制的框图。该机制连续地接受来自每一个周期的输入流的N 个字节，产生一个编码的输出流。该机制包括四个阶段（phases):词典查询/更新301，匹 配选择302,霍夫曼编码303,和末位/字节对准304。
[0037] 图4描述按照一个示例性实施例的、把一个输入数据流转换成两周期的数据帖的 转换阶段（phase)。阶段（stage)0400 接收N字节周期（N-bパecycles)C0、Cl、C2、C3。阶 段0转换机制400将该输入流转换成二周期帖（two-cycleframes)C0/C1、C1/C2、C2/C3。 [003引图5表示按照一个示例性实施例、为词典查询/更新生成地址。在词典查询/更新 阶段，该机制每一个周期检查两个连续周期的数据，即2N-1个字节。该机制考虑在产生跨 越周期边界的子字符串（第一个除外）的第一周期的数据的N个字节的每个字节处开始的 字节的每一个N字节的子字符串。因此，对于输入帖化/Ck+1，该机制考虑子字符串D0-DF。 该机制对每个子字符串执行哈希化ash)，W生成地址A0-AF。（为了方便表示，F=n-1。）
[0039] 图6描述按照一个示例性实施例的词典查询/更新阶段。阶段1词典查询/更新 机制600为每个N字节偏址位置（offsetpositions)提供一个N-读、1-写的词典存储器 (memories) 601、602、603。该机制用地址A0-AF在N个存储器的每个中查找每个N字节的 子字符串，返回多达N2个与先前看到的数据和在字节流中的先前位置的匹配（match)。词 典查询/更新机制600通过每个词典存储器601、602、603的N字节子字符串更新每个词典 存储器，W记录在字节流中出现过的子字符串W及在字节流中的位置，用于W后进行匹配 (matching)。
[0040] 因此，词典查询/更新机制600接收图5中的每个子字符串的地址A0-AF、数据 D0-DF和位置P0-PF。地址A0-AF是数据D0-DF的哈希。位置P0-PF是在字节流中的位置。 给定一个帖化/Ck+l，Pi= (Ck的位置）+i，其中每个Pi是第i个子字符串的位置值，其中 1 = 0至F。每个词典存储器601、602、603把数据和位置写至恪自的地址。因此，词典存储 器601在地址A0写入数据DO和位置P0,词典存储器602在地址A1写入数据D1和位置P1， 词典存储器603在地址AF写入数据DF和位置PF。
[0041] 每个词典存储器601、602、603在地址A0-AF执行N次读。存储器601在A0的读产 生有效位V00、读数据R00、位置值P00。存储器601在A1的读产生有效位V01、读数据R01、 位置值P01。存储器601在AF的读产生有效位V0F、读数据R0F、位置值P0F。
[0042] 存储器602在A0的读产生有效位V10、读数据R10、位置值P10。存储器611在A1 的读产生有效位V01、读数据R01、位置值P01。存储器601在AF的读产生有效位V1F、读数 据R1F、位置值P1F。
[0043] 存储器603在A0的读产生有效位VF0、读数据RF0、位置值PF0。存储器601在A1 的读产生有效位VF1、读数据RF1、位置值PF1。存储器601在AF的读产生有效位VFF、读数 据RFF、位置值PFF。
[0044] 该样，查询/更新阶段每个周期导致N次写和妒次读（N个子字符串，每个N次读）。 词典存储器601、602、603中的每个条目一开始是无效的。对词典存储器601、602、603的每 次写都断言（assert)有效位。该样，对于在给定地址处的读，有效位指示是否先前已经把 有效数据写到对应该地址的条目。
[0045] 图7是表示按照一个示例性实施例的用于匹配选择（matchselection)的机制的 框图。阶段2匹配选择机制700包含比较组件701、702、703。匹配选择机制700接收来自 词典存储器601、602、603的N个读数据集合。匹配选择机制700为每个读数据集合接收对 应的子字符串数据D0-DF。
[0046] 每个比较组件701、702、703将来自词典存储器601、602、603的有效读数据与子 字符串数据D0-DF比较。例如，比较组件701比较R00-R0F与子字符串数据DO。对于每个 R00-R0F，比较组件701确定从该子字符串的起始处开始，有多少连续的字节匹配。比较组 件701然后选择具有最长匹配的读数据R00-R0F。比较组件701然后输出最长的匹配M0-一 如果有的话，W及匹配的字节数B0。
[0047] 类似地，比较组件702比较R10-R1F与子字符串数据D1。对于每个R10-R1F，比较 组件702确定从该子字符串的起始处开始，有多少连续的字节匹配。比较组件702然后选 择具有最长匹配的读数据R10-R1F。比较组件702然后输出最长的匹配Ml-一如果有的话， W及匹配的字节数B1。
[0048] 比较组件703比较RF0-RFF与子字符串数据DF。对于每个RF0-RFF，比较组件703 确定从该子字符串的起始处开始，有多少连续的字节匹配。比较组件703然后选择具有最 长匹配的读数据RF0-RFF。比较组件703然后输出最长的匹配MF-一如果有的话，W及匹 配的字节数BF。
[0049] 图8示出了按照一个示例性实施例的匹配选择和对准（alignment)。假定某集合 有可能重叠的匹配A、B、C、D，匹配选择和对准阶段必须选择最大化地覆盖数据的匹配。如 图8所示的例子所见，匹配B与D重叠，匹配A与D重叠，匹配A与C重叠。该留下使用匹 配A和B、B和C或D和C。示例性实施例的机制选择的覆盖大部分原始数据的匹配的可能 组合。
[0050] 如图8中所见，匹配A和B提供最佳的覆盖，留下的不匹配字节最少。因为匹配A 越过周期边界4个字节，所W在下一个周期可W忽略头四个子字符串。
[0051] 因此，该示例性实施例的机制从N个字节偏址位置中选择最长的匹配，在该位置 潜在有N个字节匹配 ，该就把潜在的匹配的个数，从多达N2个减少到N个，当前周期中的每 个字节偏址对应一个。该机制选择该些匹配的一个子集，试图尽可能多地覆盖该2N-1个字 -H- T。
[0化2] 该机制寻找一个越过周期边界并且消耗尽可能多的当前周期的匹配。该机制然后 寻找额外的匹配W覆盖当前周期中更多的字节。该机制为下一个周期留下关于被越界覆盖 的字节的足够信息。
[0化3] 匹配选择对准阶段产生未被覆盖的字节和匹配的字节。在一个实施例中，示例性 实施例的机制W文字形式（asliterals)对当前周期中未被覆盖的字节进行霍夫曼编码。 示例性实施例的机制通过长度和距离编码匹配。
[0化4] 然后，位/字节包装（packing)阶段产生符合紧缩规范的字节序列。将当前周期 中的第一可变位宽度代码通过位移化itshifting)操作而对齐，产生若个字节，可能有部 分字节数剩下，要被添加到下一个周期的位。一个周期内的字节被累积，直到能在单一周期 内输出N个字节。
[0化5] 所属技术领域的技术人员知道，本发明可W实现为系统、方法或计算机程序产品。 因此，本发明的各个方面可W具体实现为W下形式，即；完全的硬件实施方式、完全的软件 实施方式（包括固件、驻留软件、微代码等），或硬件和软件方面结合的实施方式，该里可W 统称为"电路"、"模块"或"系统"。此外，在一些实施例中，本发明的各个方面还可W实现为 在一个或多个计算机可读介质的任何之一中的计算机程序产品的形式，该计算机可读介质 中包含计算机可用的程序代码。
[0化6] 可W采用一个或多个计算机可读介质的任意组合。计算机可读介质可W是计算 机可读信号介质或者计算机可读存储介质。计算机可读存储介质例如可W是一一但不限 于一一电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者任意W上的组合。计算 机可读存储介质的更具体的例子（非穷举的列表）包括；具有一个或多个导线的电连接、便 携式计算机盘、硬盘、随机存取存储器（RAM)、只读存储器（ROM)、可擦式可编程只读存储器 (EPROM或闪存）、光纤、便携式紧凑盘只读存储器（CD-ROM)、光存储器件、磁存储器件、或者 上述的任意合适的组合。在本文件中，计算机可读存储介质可W是任何包含或存储程序的 有形介质，该程序可W被指令执行系统、装置或者器件使用或者与其结合使用。
[0化7] 计算机可读的信号介质可W包括在基带中或者作为载波一部分传播的数据信号， 其中承载了计算机可读的程序代码。该种传播的数据信号可W采用多种形式，包括一一但 不限于一一电磁信号、光信号或上述的任意合适的组合。计算机可读的信号介质还可W是 计算机可读存储介质w外的任何计算机可读介质，该计算机可读介质可w发送、传播或者 传输用于由指令执行系统、装置或者器件使用或者与其结合使用的 [0化引计算机可读介质上包含的计算机代码可W用任何适当的介质传输，包括一-但不 限于一-无线、有线、光缆、RF等等，或者上述的任意合适的组合。
[0化9] 可-种或多种程序设计语言的任意组合来编写用于执行本发明操作的计算 机程序代码，所述程序设计语言包括面向对象的程序设计语言一诸如化va、Smallta化、C++ 等，还包括常规的过程式程序设计语言一诸如"C"语言或类似的程序设计语言。程序代码可 W完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、 部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。 在设及远程计算机的情形中，远程计算机可W通过任意种类的网络一一包括局域网（LAN) 或广域网（WAN)-连接到用户计算机，或者，可W连接到外部计算机（例如利用因特网服务 提供商来通过因特网连接）。
[0060] 下面将参照根据本发明的示例性实施例的方法、装置（系统）和计算机程序产品 的流程图和/或框图描述本发明。应当理解，流程图和/或框图的每个方框W及流程图和/ 或框图中各方框的组合，都可W由计算机程序指令实现。该些计算机程序指令可W提供给 通用计算机、专用计算机或其它可编程数据处理装置的处理器，从而生产出一种机器，使得 该些计算机程序指令在通过计算机或其它可编程数据处理装置的处理器执行时，产生了实 现流程图和/或框图中的一个或多个方框中规定的功能/动作的装置。
[0061] 也可W把该些计算机程序指令存储在计算机可读介质中，该些指令使得计算机、 其它可编程数据处理装置、或其他设备W特定方式工作，从而，存储在计算机可读介质中的 指令就产生出包括实现流程图和/或框图中的一个或多个方框中规定的功能/动作的指令 的制造品（articleofmanufacture)。
[0062] 也可W把该些计算机程序指令加载到计算机、其它可编程数据处理装置或其它设 备上，W致使在计算机、其它可编程数据处理装置或其它设备执行一系列操作步骤，W生成 计算机实现的过程，使得在计算机或其它可编程装置上执行的指令提供用于实现流程图和 /或框图中的一个或多个方框中规定的功能/动作的过程。
[0063] 图9是表示按照一个示例性实施例的高带宽压缩至编码的数据流的机制的流程 图。操作开始（框900)后，该机制将数据流的一部分转换为一个二周期帖（框901)。该 机制从第一个未编码字节开始（框902)，计算该帖中的数据的每个周期长度的子字符串的 哈希（框903)。该机制然后用哈希作为地址将数据的每个子字符串写到相应的词典存储 器（框904)。对于一个二周期帖一一其中每个周期是N个字节一一来说，该机制向N个词 典存储器的每一个写一个N字节的子字符串。
[0064] 该机制用所有计算出的哈希作为地址从所有词典存储器中读取数据的子字符串 (框905)。在框905,该机制从N个词典存储器进行N次读取，尽管该些读取中许多结果是 无效的数据。然后，该机制比较每个子字符串与从相应的词典存储器读取的数据（框906)， 选择在该子字符串的第一个字节处开始的连续字节的最长匹配（框907)。该机制于是有来 自每个词典存储器的一个匹配，一共N个匹配。
[0065] 之后，该机制选择该些匹配的一个子集（框908)。该机制选择匹配，W覆盖2N-1 个字节的尽可能多的字节。该机制首先可W先选择一个穿越周期边界并覆盖当前周期的尽 可能多的字节。该机制然后可w选择额外的匹配w覆盖当前周期的更多字节。该机制然后W文字形式编码不匹配的字节，并用长度信息和距离信息编码匹配（框909)，其中，长度指 示匹配的字节长度，距离引用数据流中数据的先前实例。然后，该机制进行位/字节对齐 (框 910)。
[0066] 该机制然后判定当前周期是否是最后周期（框911)。如果当前周期不是数据流中 的最后周期，该机制考虑数据流中的下一个周期（框912)，操作返回到框901，W将数据转 换为二周期帖。然后，对该下一个周期重复操作。如果在框911，当前周期是数据流中数据 的最后周期，则操作结束（框913)。
[0067] 附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法和计算机程 序产品的可能实现的体系架构、功能和操作。在该点上，流程图或框图中的每个方框可W 代表一个模块、程序段或代码的一部分，所述模块、程序段或代码的一部分包含一个或多个 用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所 标注的功能也可不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可W 基本并行地执行，它们有时也可W按相反的顺序执行，该依所设及的功能而定。也要注意的 是，框图和/或流程图中的每个方框、化及框图和/或流程图中的方框的组合，可W用执行 规定的功能或动作的专用的基于硬件的系统来实现，或者可W用专用硬件与计算机指令的 组合来实现。
[0068] 因此，示例性实施例提供用于高带宽压缩至编码的数据流的机制。该些机制在连 续的周期处理数据，实现低延迟、高吞吐率。对一个N字节的数据周期，该机制使用为该N 字节数据中的每个字节偏址执行N次读和一次写的N个词典存储器。
[0069] 如上所述，应该明白，示例性实施例可W采取完全硬件体现的形式、完全软件体现 的形式或包含硬件和软件两种元素的体现形式。在一个实施例中，示例性实施例的机制在 软件或程序代码中实现，包括但不限于固件、常驻软件、微代码，等等。
[0070] 适于存储和/或执行程序代码的将数据处理系统包括至少一个通过系统总线处 理器直接地或间接地禪合到存储单元的处理器。存储单元在程序代码的实际执行期间采用 的本地存储器、大容量存储器、W及高速缓冲存储器，后者为至少一些程序代码提供临时存 储W减少在执行期间代码必须从大容量存储器取出的次数。
[0071] 输入/输出或I/O设备（包括但不限于键盘、显示器、指点设备，等等）可W直接 地或通过中间的I/O控制器禪接到系统。网络适配器也可W禪接到系统，使数据处理系统 能通过专用或公共网络禪接到其它数据处理系统或远程打印机或存储设备。调制解调器、 电缆调制解调器和W太网卡只是当前可用的几类网络适配器。
[0072] 已经描述了本发明，W上描述是示例性和说明性的，而穷举性的，也并非是要把本 发明限定到所公开的形式。对于所属技术领域的普通技术人员来说，许多修改和变更都是 显而易见的。对实施例的选择和描述的方式，是为了最好地解释本发明的原理和实际应用， 使所属技术领域的普通技术人员能理解本发明具有为适合特定用途而作了各种修改的各 种实施方式。
【主权项】
1. 用于在数据处理系统中流水线式压缩多字节帧的方法，该方法包含： 组合输入数据流中当前周期的数据与所述输入数据流中下一个周期的数据的至少一 部分，以构成数据帧； 识别多个词典存储器的多个匹配，其中每个匹配与该数据帧中的给定子字符串的一部 分匹配； 从该多个匹配中识别提供对当前周期的数据的最佳覆盖的匹配子集；和 把该数据帧编码成编码的输出数据流。2. 按照权利要求1的方法，其中，组合输入数据流中当前周期的数据与输入数据流中 下一个周期的数据的至少一部分包含：构成多个子字符串，各子字符串始于当前周期的数 据的一个对应字节并有与当前周期的数据相等的长度。3. 按照权利要求1或2的方法，其中，该匹配子集穿过第一周期的数据和下一个周期的 数据之间的周期边界。4. 按照权利要求1至3的任何之一的方法，其中，把该数据帧编码成编码的输出数据流 包含： 用长度信息和距离信息编码该匹配子集的每个，以构成匹配编码的数据； 用无损压缩编码该输入数据流中的当前周期的数据中的不匹配数据，以构成压缩编码 的数据；和 在输出数据流中把匹配编码的数据与压缩编码的数据对准。5. 按照权利要求1至4的任何之一的方法，进一步包含： 根据多个子字符串中的每个给定子字符串生成地址，以构成多个地址。6. 按照权利要求5的方法，其中，生成地址包含对所述给定子字符串执行哈希。7. 按照权利要求5或6的方法，进一步包含： 用从给定子字符串生成的地址把每个给定子字符串和对应的位置值写到该多个词典 存储器中的对应的词典存储器。8. 按照权利要求5至7的任何之一的方法，其中，识别多个匹配包含： 用该多个地址读取该多个词典存储器内的每个给定词典存储器，以接收每个词典存储 器的零个或更多个有效条目。9. 按照权利要求8的方法，其中，识别多个匹配进一步包含： 对于每个具有至少一个有效条目的词典存储器，比较该至少一个有效条目与对应子字 符串；和 对于每个具有至少一个有效条目的词典存储器，根据从该对应子字符串起始处开始的 连续的匹配字节的数量选择最长的匹配，以构成多个匹配。10. 按照权利要求9的方法，其中，多个匹配的每个都有一个匹配长度值和一个位置 值，其中，长度值表示匹配数据的长度，位置值引用输入数据流中该匹配数据的在前出现。11. 用于在数据处理系统中流水线式压缩多字节帧的装置，该装置包含： 词典查询/更新阶段，包含多个词典存储器和相关逻辑； 匹配选择阶段，包含多个比较电路和相关逻辑；和 编码阶段， 其中，词典查询/更新阶段接收包含输入数据流中当前周期的数据与输入数据流中下 一个周期的数据的至少一部分组合的数据帧，识别多个词典存储器的多个匹配，其中每个 匹配与所述多个子字符串中的给定子字符串的一部分匹配； 其中，所述匹配选择阶段用多个比较电路从提供对当前周期的数据的最佳覆盖的多个 匹配中识别匹配的子集；和 其中，所述编码阶段把该数据帧编码成编码的输出数据流。12. 按照权利要求11的装置，其中，组合输入数据流中当前周期的数据与输入数据流 中下一个周期的数据的至少一部分包含：构成多个子字符串，各子字符串始于当前周期的 数据的对应字节并有与当前周期的数据相等的长度。13. 按照权利要求11或12的装置，其中，该匹配子集穿过第一周期的数据和下一个周 期的数据之间的周期边界。14. 按照权利要求11至13的任何之一的装置，其中，所述编码阶段用长度信息和距离 信息编码该匹配子集的每个，以构成匹配编码的数据，并用无损压缩编码该输入数据流中 的当前周期的数据中的不匹配数据，以构成压缩编码的数据。15. 按照权利要求14所述的装置，其中，所述编码阶段包含霍夫曼编码电路，并且其 中，编码阶段用霍夫曼编码电路编码不匹配数据。16. 按照权利要求11至15的任何之一的装置，进一步包含： 位/字节对准阶段，其中，位/字节对准阶段在输出数据流中把匹配编码的数据与压缩 编码的数据对准。17. 按照权利要求11至16的任何之一的装置，其中，所述词典查询/更新阶段根据多 个子字符串中的每个给定子字符串生成地址，以构成多个地址。18. 按照权利要求17的装置，其中，所述词典查询/更新阶段通过对所述给定子字符串 执行哈希来生成地址。19. 按照权利要求17或18的装置，其中，所述词典查询/更新阶段用从所述给定子字 符串生成的地址把每个给定子字符串和对应的位置值写到该多个词典存储器中的对应的 词典存储器。20. 按照权利要求17至19的任何之一的装置，其中，所述词典查询/更新阶段通过以 下方式识别多个匹配：用该多个地址读取该多个词典存储器内的每个给定词典存储器，以 接收每个词典存储器的零个或更多个有效条目。21. 按照权利要求20的装置，其中，匹配选择阶段通过以下方式识别匹配的子集：对于 每个具有至少一个有效条目的词典存储器，比较该至少一个有效条目与对应子字符串；和 对于每个具有至少一个有效条目的词典存储器，根据从该对应子字符串起始处开始的连续 的匹配字节的数量选择最长的匹配，以构成多个匹配。22. 按照权利要求21的装置，其中，所述多个匹配的每个都有一个匹配长度值和一个 位置值，其中，长度值表示匹配数据的长度，位置值引用输入数据流中该匹配数据的在前出 现。23. -种计算机程序产品，包含其中存储有计算机可读程序的计算机可读介质，其中， 计算机可读程序在计算设备上执行时使计算设备： 组合输入数据流中当前周期的数据与所述输入数据流中下一个周期的数据的至少一 部分，以构成数据帧； 识别多个词典存储器的多个匹配，其中每个匹配与该数据帧中的给定子字符串的一部 分匹配； 从该多个匹配中识别提供对当前周期的数据的最佳覆盖的匹配子集；和 把该数据帧编码成编码的输出数据流。24. 按照权利要求23的计算机程序产品，其中，组合输入数据流中当前周期的数据与 输入数据流中下一个周期的数据的至少一部分包含：构成多个子字符串，各子字符串始于 当前周期的数据的一个对应字节并有与当前周期的数据相等的长度。25. 按照权利要求23或24的计算机程序产品，其中，该匹配子集穿过第一周期的数据 和下一个周期的数据之间的周期边界。26. 按照权利要求23至25的任何之一的计算机程序产品，其中，把该数据帧编码成编 码的输出数据流包含： 用长度信息和距离信息编码该匹配子集的每个，以构成匹配编码的数据； 用无损压缩编码该输入数据流中的当前周期的数据中的不匹配数据，以构成压缩编码 的数据；和 在输出数据流中把匹配编码的数据与压缩编码的数据对准。27. 按照权利要求23至26的任何之一的计算机程序产品，进一步包含： 根据多个子字符串中的每个给定子字符串生成地址，以构成多个地址。28. 按照权利要求27的计算机程序产品，其中，生成地址包含对所述给定子字符串执 行哈希。29. 按照权利要求27或28的计算机程序产品，进一步包含： 用从给定子字符串生成的地址把每个给定子字符串和对应的位置值写到该多个词典 存储器中的对应的词典存储器。30. 按照权利要求27至29的任何之一的计算机程序产品，其中，识别多个匹配包含： 用该多个地址读取该多个词典存储器内的每个给定词典存储器，以接收每个词典存储 器的零个或更多个有效条目。31. 按照权利要求30的计算机程序产品，其中，识别多个匹配进一步包含： 对于每个具有至少一个有效条目的词典存储器，比较该至少一个有效条目与对应子字 符串；和 对于每个具有至少一个有效条目的词典存储器，根据从该对应子字符串起始处开始的 连续的匹配字节的数量选择最长的匹配，以构成多个匹配。32. 按照权利要求30的计算机程序产品，其中，多个匹配的每个都有一个匹配长度值 和一个位置值，其中，长度值表示匹配数据的长度，位置值引用输入数据流中该匹配数据的 在前出现。
【专利摘要】提供一种用于在数据处理系统中流水线式压缩多字节帧的机制。该机制组合输入数据流中当前周期的数据与所述输入数据流中下一个周期的数据的至少一部分，以构成数据帧。该机制识别多个词典存储器的多个匹配。每个匹配与该数据帧中的给定子字符串的一部分匹配。该机制从该多个匹配中识别提供对当前周期的数据的最佳覆盖的匹配子集。该机制把该数据帧编码成编码的输出数据流。
【IPC分类】H03M7/40
【公开号】CN104904123
【申请号】CN201380069224
【发明人】D·A·詹姆塞克, K·B·阿加瓦尔, H·P·霍夫施蒂, A·K·马丁
【申请人】国际商业机器公司
【公开日】2015年9月9日
【申请日】2013年12月2日
【公告号】DE112013006339T5, US8704686, WO2014106782A1
【技术领域】
[0001] 本发明总体设及一种改进的数据处理装置和方法，更具体来说，设及高带宽压缩 至编码的数据流。
【背景技术】
[0002] Deflate是一种无损数据压缩算法，采用了LZ77算法和霍夫曼化uffman)编码的 组合。LZ77算法通过将重复出现的数据替换为对在输入（未压缩的）数据流中较早存在的 该数据的单一拷贝的引用而实现压缩。用一个称作长度-距离对的数字对编码一个匹配， 该相当于声明"每个下一个长度的字符，等于未压缩流中在其之后一定距离的字符"。"距 离"有时也被称为"偏址"（offset)。
[0003] 霍夫曼编码是一种用于无损数据压缩的滴编码算法。该个术语指的是用一个可变 长度代码表来编码一个源符号，其中，可变长度代码表已经被W特定的方式根据源符号的 每个可能值的发生的估计概率导出。
[0004] 在压缩块内，如果发现重复的字节序列（重复的字符串），则插入一个链接到相同 字符串的先前位置的反向引用（back-reference)。一个较早字符串的编码匹配，由长度 (3 - 258字节）和距离（1 - 32768字节）组成。可W跨任意数量的块作出相对的反向引用， 只要距离出现在解码的未压缩数据的最后32kB(称为滑动窗口）。
[0005] 第二压缩阶段包括用较短的表示来替代常用的符号，用较长的表示来替代不常用 的符号。霍夫曼编码创建一个无重叠区间（non-overlappingintervals)的无前缀树，其中 每个序列的长度与那个符号需要编码的概率成反比。符号要被编码的可能性越大，它的比 特序列化it-sequence)就越短。
【发明内容】
[0006] 在一个示例性实施例中，一种用于在数据处理系统中流水线式压缩多字节帖的方 法包含组合输入数据流中当前周期的数据与所述输入数据流中下一个周期的数据的至少 一部分，W构成数据帖。该方法进一步包含识别多个词典存储器的多个匹配。每个匹配与 该数据帖中的给定子字符串的一部分匹配。该方法进一步包含从该多个匹配中识别提供对 当前周期的数据的最佳覆盖的匹配子集。该方法进一步包含把该数据帖编码成编码的输出 数据流。
[0007]在另一个示例性实施例中，提供一种计算机程序产品，包含其中存储有计算机可 读程序的计算机可读介质。该计算机可读程序在计算设备上执行时使计算设备上文关于方 法示例性实施例所述的操作的各种操作或操作组合。
[000引在另一个示例性实施例中，提供一个系统/装置。该装置用于在数据处理系统中 流水线式压缩多字节帖，包含：词典查询/更新阶段，其包含多个词典存储器和相关逻辑； 匹配选择阶段，其包含多个比较电路和相关逻辑；和编码阶段。词典查询/更新阶段接收包 含输入数据流中当前周期的数据与所述输入数据流中下一个周期的数据的至少一部分组 合的数据帖，识别多个词典存储器的多个匹配。每个匹配与该数据帖中的给定子字符串的 一部分匹配。匹配选择阶段用多个比较电路从提供对当前周期的数据的最佳覆盖的多个匹 配中识别匹配的子集。编码阶段把该数据帖编码成编码的输出数据流。
[0009] 本发明的该些和其它特点和优点，将在W下对本发明的示例性实施例的详细说明 中描述，所属技术领域的普通技术人员从中也可W明了该些和其它特点和优点。
【附图说明】
[0010] 本发明及其优选应用方式、W及其进一步的目的和优点，可结合附图阅读下文对 示例性实施例的详细说明而得到最好的理解，附图中：
[0011] 图1表示一例在其中可W实现示例性实施例的各方面的分布式数据处理系统的 图示；
[0012] 图2是一例在其中可W实现示例性实施例的各方面的分布式数据处理系统的框 图；
[0013] 图3是表示按照一个示例性实施例的、处理一个任意长度的任意字节流并输出一 个压缩数据格式的字节流的机制的框图；
[0014]图4描述按照一个示例性实施例的、把一个输入数据流转换成两周期的数据帖的 转换阶段；
[0015] 图5描述按照一个示例性实施例的、为词典查询/更新生成地址；
[0016] 图6描述按照一个示例性实施例的词典查询/更新阶段；
[0017] 图7是表示按照一个示例性实施例的用于匹配选择的机制的框图；
[0018] 图8示出了按照一个示例性实施例的匹配选择和对准；和
[0019] 图9是表示按照一个示例性实施例的高带宽压缩至编码的数据流的机制的流程 图。
【具体实施方式】
[0020] 示例性实施例提供一种处理连续周期中的数据流W实现低延时和高吞吐率的机 审IJ。将词典组织成阵列，一个周期数据中的每个字节偏址对应一个阵列。若干阶段（stages) 要求有下个周期可立即用于相同阶段的结果。
[0021] 示例性实施例可W在许多不同类型的数据处理环境中使用。为了为描述示例性实 施例的特定元素和功能提供语境（context)，W下提供图1和2,作为可在其中实现示例性 实施例的各方面的环境的例子。应该明白，图1和2仅仅是例子，并非是提出或暗示对可在 其中实现示例性实施例的各方面的环境的任何限制。在不脱离本发明的精神和范围的情况 下可W对所示的环境作出许多修改。
[0022] 图1表示一例在其中可W实现示例性实施例的各方面的分布式数据处理系统的 图示。分布式数据处理系统100可W包括一个在其中可W实现示例性实施例的各方面的计 算机网络。分布式数据处理系统100包含至少一个网络102,该是提供分布式数据处理系统 100内连接在一起的各种设备和计算机之间的通信链路的媒介。网络102可W包括诸如电 线、无线通信链路、或光纤电缆的连接。
[0023] 在所示的例子中，服务器104和服务器106随存储单元108 -起连接到网络102。 此外，客户机11〇、112、和114也连接到网络102。该些客户机110、112、和114,例如可W是 个人电脑、网络计算机之类。在所示的例子中，服务器104向客户机110、112、和114提供 诸如引导文件、操作系统映像和应用程序的数据。在所示的例子中，客户机11〇、112、和114 是服务器104的客户机。分布式数据处理系统100可W包含额外的服务器、客户机、W及未 予示出的其它设备。
[0024] 在所示的例子中，分布式数据处理系统100是因特网与代表使用传输控制协议/ 因特网协议（TCP/I巧的一套协议相互通信的世界范围的网络和网关的网络102。在因特 网的核屯、是包括路由数据和消息的数W千计的商业、政府、教育计算机系统和其他计算机 系统的主要节点或主机之间的高速数据通信线路的骨干。当然，分布式数据处理系统100 的具体实现还可W包含许多不同类型的网络，例如内部网、局域网（LAN)、广域网（WAN),等 等。如上所述，图1意在举例，而不是对本发明的不同实施例的结构限定，因此，图1中所 示的特定元素，不应被视为对可W在其中实现本发明的示例性实施例的各方面的环境的限 制。
[0025] 图2是一例在其中可W实现示例性实施例的各方面的分布式数据处理系统的框 图。数据处理系统200是一例计算机，诸如图1中的客户机110,其中具有实现本发明的示 例性实施例的过程的计算机可用代码或指令。
[0026] 在所示的例子中，数据处理系统200采用包括北桥与存储器控制器中枢（NB/ MCH) 202和南桥与输入/输出（I/O)控制器中枢（SB/ICH) 204的中枢结构。处理单元206、 主存储器208和图形处理器210连接到NB/MCH202。图形处理器210也可W通过加速图形 端口（AGP)连接到NB/MCH202。
[0027] 在所示的例子中，局域网（LAN)适配器212连接到SB^CH204。音频适配器216、 键盘和鼠标适配器220、调制解调器222、只读存储器（ROM) 224、硬盘驱动器（皿D) 226,光驱 230、通用串行总线扣SB)端口和其他通信端口 232,W及PCI/PCIe设备234通过总线238 和总线240连接到SB/1CH204。PCI/PCIe设备例如可W包括W太网适配器、附加（add-in) 卡、W及笔记本电脑的PC卡。PCI使用一个卡式总线控制器，而PCIe则不是。ROM224例 如可W是闪速（flash)基本输入/输出系统炬10巧。
[0028] 皿D226和CD-ROM驱动器230通过总线240连接到SB/1CH204。皿D226和CD-ROM驱动器230可W使用例如集成驱动电子（I呢）或串行高级技术附件（SATA)接口。 超级I/0(SI0)设备236可W连接到SB/ICH204。
[0029] 操作系统在处理单元206上运行。操作系统协调并提供对图2中的数据处理系 统200内的各种部件的控制。作为客户机，操作系统可W是商业上可获得的操作系统，例如 MicrosoftWindows7 (Microsoft和Windo ws是微软公司在美国和其他国家的注册商标）。 面向对象的编程系统，如化va编程系统，可W与操作系统协作地运行，提供从在数据处理 系统200上执行的化va程序或应用程序的对操作系统的调用aava是甲骨文公司和/或 其关联公司的商标。）
[0030] 作为服务器，数据处理系统200可W是例如'IBM⑧eServer?系统P饭型计算机 系统，运行高级交互指令（AIX⑧）操作系统或Linux操作系统（IBM、eServer、系统P和AIX是国际商业机器公司在美国/其他国家的商标，Linux是LinusTorvalds在美国/其 他国家的注册商标）。数据处理系统200可W是处理单元202中包括多个处理器的对称多 处理器（SM巧系统。另外，也可W采用单处理器的系统。
[0031] 操作系统、面向对象的编程系统、W及应用或程序的指令，位于存储设备上，如皿D 226上，可W被装入主存储器208,供处理单元206执行。本发明的示例性实施例的过程可 W由处理单元206用计算机可用代码执行，计算机可用代码可位于存储器中，如主存储器 208、ROM224中，或位于例如一个或多个外围设备226和230。
[0032] 诸如图2中所示的总线238或总线240的总线系统，可包含一个或更多总线。当 然，总线系统可W采用用于实现与其附接的不同组件和设备之间的数据传输的任何类型的 通信组织或架构。诸如图2的调制解调器222或网络适配器212的通信单元，可W包括一 个或多个用于发送和接收数据的设备。存储器可W是例如主存储器208、R0M224或者诸如 见于图2的NB/MCH202中的高速缓存。
[0033] 所述技术领域的技术人员应当明白，图1和2中的硬件，可W因具体实现而异。其 它内部硬件或外设，诸如闪存、等同的非易失性存储器、或光盘驱动器之类，也可W在图1 和2中所示的硬件W外使用，或者代替所示的硬件。此外，在不脱离本发明的精神和范围的 情况下，也可W将示例性实施例的过程应用于多处理器数据处理系统，而不是先前提到的 SMP系统，
[0034] 此外，数据处理系统200可W采取多种不同数据处理系统的任何数据处理系统的 形式，包括客户端计算设备、服务器计算设备、平板电脑、笔记本电脑、电话或其它通信设 备、个人数字助理（PDA),等等。在一些示例性例子中，数据处理系统200可W是便携式计算 设备，其配置有闪存，用来提供例如存储操作系统文件和/或用户生成的数据的非易失性 存储器。实际上，数据处理系统200可W是任何已知或今后开发的数据处理系统，对其没有 结构性限制。
[0035] 数据处理系统200可能由于各种原因而需要数据压缩。例如，数据处理系统200 可W压缩存储到磁盘226的数据，或压缩在网络适配器212上发送的数据。
[0036] 图3是表示按照一个示例性实施例的、处理一个任意长度的任意字节流并输出一 个压缩数据格式的字节流的机制的框图。该机制连续地接受来自每一个周期的输入流的N 个字节，产生一个编码的输出流。该机制包括四个阶段（phases):词典查询/更新301，匹 配选择302,霍夫曼编码303,和末位/字节对准304。
[0037] 图4描述按照一个示例性实施例的、把一个输入数据流转换成两周期的数据帖的 转换阶段（phase)。阶段（stage)0400 接收N字节周期（N-bパecycles)C0、Cl、C2、C3。阶 段0转换机制400将该输入流转换成二周期帖（two-cycleframes)C0/C1、C1/C2、C2/C3。 [003引图5表示按照一个示例性实施例、为词典查询/更新生成地址。在词典查询/更新 阶段，该机制每一个周期检查两个连续周期的数据，即2N-1个字节。该机制考虑在产生跨 越周期边界的子字符串（第一个除外）的第一周期的数据的N个字节的每个字节处开始的 字节的每一个N字节的子字符串。因此，对于输入帖化/Ck+1，该机制考虑子字符串D0-DF。 该机制对每个子字符串执行哈希化ash)，W生成地址A0-AF。（为了方便表示，F=n-1。）
[0039] 图6描述按照一个示例性实施例的词典查询/更新阶段。阶段1词典查询/更新 机制600为每个N字节偏址位置（offsetpositions)提供一个N-读、1-写的词典存储器 (memories) 601、602、603。该机制用地址A0-AF在N个存储器的每个中查找每个N字节的 子字符串，返回多达N2个与先前看到的数据和在字节流中的先前位置的匹配（match)。词 典查询/更新机制600通过每个词典存储器601、602、603的N字节子字符串更新每个词典 存储器，W记录在字节流中出现过的子字符串W及在字节流中的位置，用于W后进行匹配 (matching)。
[0040] 因此，词典查询/更新机制600接收图5中的每个子字符串的地址A0-AF、数据 D0-DF和位置P0-PF。地址A0-AF是数据D0-DF的哈希。位置P0-PF是在字节流中的位置。 给定一个帖化/Ck+l，Pi= (Ck的位置）+i，其中每个Pi是第i个子字符串的位置值，其中 1 = 0至F。每个词典存储器601、602、603把数据和位置写至恪自的地址。因此，词典存储 器601在地址A0写入数据DO和位置P0,词典存储器602在地址A1写入数据D1和位置P1， 词典存储器603在地址AF写入数据DF和位置PF。
[0041] 每个词典存储器601、602、603在地址A0-AF执行N次读。存储器601在A0的读产 生有效位V00、读数据R00、位置值P00。存储器601在A1的读产生有效位V01、读数据R01、 位置值P01。存储器601在AF的读产生有效位V0F、读数据R0F、位置值P0F。
[0042] 存储器602在A0的读产生有效位V10、读数据R10、位置值P10。存储器611在A1 的读产生有效位V01、读数据R01、位置值P01。存储器601在AF的读产生有效位V1F、读数 据R1F、位置值P1F。
[0043] 存储器603在A0的读产生有效位VF0、读数据RF0、位置值PF0。存储器601在A1 的读产生有效位VF1、读数据RF1、位置值PF1。存储器601在AF的读产生有效位VFF、读数 据RFF、位置值PFF。
[0044] 该样，查询/更新阶段每个周期导致N次写和妒次读（N个子字符串，每个N次读）。 词典存储器601、602、603中的每个条目一开始是无效的。对词典存储器601、602、603的每 次写都断言（assert)有效位。该样，对于在给定地址处的读，有效位指示是否先前已经把 有效数据写到对应该地址的条目。
[0045] 图7是表示按照一个示例性实施例的用于匹配选择（matchselection)的机制的 框图。阶段2匹配选择机制700包含比较组件701、702、703。匹配选择机制700接收来自 词典存储器601、602、603的N个读数据集合。匹配选择机制700为每个读数据集合接收对 应的子字符串数据D0-DF。
[0046] 每个比较组件701、702、703将来自词典存储器601、602、603的有效读数据与子 字符串数据D0-DF比较。例如，比较组件701比较R00-R0F与子字符串数据DO。对于每个 R00-R0F，比较组件701确定从该子字符串的起始处开始，有多少连续的字节匹配。比较组 件701然后选择具有最长匹配的读数据R00-R0F。比较组件701然后输出最长的匹配M0-一 如果有的话，W及匹配的字节数B0。
[0047] 类似地，比较组件702比较R10-R1F与子字符串数据D1。对于每个R10-R1F，比较 组件702确定从该子字符串的起始处开始，有多少连续的字节匹配。比较组件702然后选 择具有最长匹配的读数据R10-R1F。比较组件702然后输出最长的匹配Ml-一如果有的话， W及匹配的字节数B1。
[0048] 比较组件703比较RF0-RFF与子字符串数据DF。对于每个RF0-RFF，比较组件703 确定从该子字符串的起始处开始，有多少连续的字节匹配。比较组件703然后选择具有最 长匹配的读数据RF0-RFF。比较组件703然后输出最长的匹配MF-一如果有的话，W及匹 配的字节数BF。
[0049] 图8示出了按照一个示例性实施例的匹配选择和对准（alignment)。假定某集合 有可能重叠的匹配A、B、C、D，匹配选择和对准阶段必须选择最大化地覆盖数据的匹配。如 图8所示的例子所见，匹配B与D重叠，匹配A与D重叠，匹配A与C重叠。该留下使用匹 配A和B、B和C或D和C。示例性实施例的机制选择的覆盖大部分原始数据的匹配的可能 组合。
[0050] 如图8中所见，匹配A和B提供最佳的覆盖，留下的不匹配字节最少。因为匹配A 越过周期边界4个字节，所W在下一个周期可W忽略头四个子字符串。
[0051] 因此，该示例性实施例的机制从N个字节偏址位置中选择最长的匹配，在该位置 潜在有N个字节匹配 ，该就把潜在的匹配的个数，从多达N2个减少到N个，当前周期中的每 个字节偏址对应一个。该机制选择该些匹配的一个子集，试图尽可能多地覆盖该2N-1个字 -H- T。
[0化2] 该机制寻找一个越过周期边界并且消耗尽可能多的当前周期的匹配。该机制然后 寻找额外的匹配W覆盖当前周期中更多的字节。该机制为下一个周期留下关于被越界覆盖 的字节的足够信息。
[0化3] 匹配选择对准阶段产生未被覆盖的字节和匹配的字节。在一个实施例中，示例性 实施例的机制W文字形式（asliterals)对当前周期中未被覆盖的字节进行霍夫曼编码。 示例性实施例的机制通过长度和距离编码匹配。
[0化4] 然后，位/字节包装（packing)阶段产生符合紧缩规范的字节序列。将当前周期 中的第一可变位宽度代码通过位移化itshifting)操作而对齐，产生若个字节，可能有部 分字节数剩下，要被添加到下一个周期的位。一个周期内的字节被累积，直到能在单一周期 内输出N个字节。
[0化5] 所属技术领域的技术人员知道，本发明可W实现为系统、方法或计算机程序产品。 因此，本发明的各个方面可W具体实现为W下形式，即；完全的硬件实施方式、完全的软件 实施方式（包括固件、驻留软件、微代码等），或硬件和软件方面结合的实施方式，该里可W 统称为"电路"、"模块"或"系统"。此外，在一些实施例中，本发明的各个方面还可W实现为 在一个或多个计算机可读介质的任何之一中的计算机程序产品的形式，该计算机可读介质 中包含计算机可用的程序代码。
[0化6] 可W采用一个或多个计算机可读介质的任意组合。计算机可读介质可W是计算 机可读信号介质或者计算机可读存储介质。计算机可读存储介质例如可W是一一但不限 于一一电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者任意W上的组合。计算 机可读存储介质的更具体的例子（非穷举的列表）包括；具有一个或多个导线的电连接、便 携式计算机盘、硬盘、随机存取存储器（RAM)、只读存储器（ROM)、可擦式可编程只读存储器 (EPROM或闪存）、光纤、便携式紧凑盘只读存储器（CD-ROM)、光存储器件、磁存储器件、或者 上述的任意合适的组合。在本文件中，计算机可读存储介质可W是任何包含或存储程序的 有形介质，该程序可W被指令执行系统、装置或者器件使用或者与其结合使用。
[0化7] 计算机可读的信号介质可W包括在基带中或者作为载波一部分传播的数据信号， 其中承载了计算机可读的程序代码。该种传播的数据信号可W采用多种形式，包括一一但 不限于一一电磁信号、光信号或上述的任意合适的组合。计算机可读的信号介质还可W是 计算机可读存储介质w外的任何计算机可读介质，该计算机可读介质可w发送、传播或者 传输用于由指令执行系统、装置或者器件使用或者与其结合使用的 [0化引计算机可读介质上包含的计算机代码可W用任何适当的介质传输，包括一-但不 限于一-无线、有线、光缆、RF等等，或者上述的任意合适的组合。
[0化9] 可-种或多种程序设计语言的任意组合来编写用于执行本发明操作的计算 机程序代码，所述程序设计语言包括面向对象的程序设计语言一诸如化va、Smallta化、C++ 等，还包括常规的过程式程序设计语言一诸如"C"语言或类似的程序设计语言。程序代码可 W完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、 部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。 在设及远程计算机的情形中，远程计算机可W通过任意种类的网络一一包括局域网（LAN) 或广域网（WAN)-连接到用户计算机，或者，可W连接到外部计算机（例如利用因特网服务 提供商来通过因特网连接）。
[0060] 下面将参照根据本发明的示例性实施例的方法、装置（系统）和计算机程序产品 的流程图和/或框图描述本发明。应当理解，流程图和/或框图的每个方框W及流程图和/ 或框图中各方框的组合，都可W由计算机程序指令实现。该些计算机程序指令可W提供给 通用计算机、专用计算机或其它可编程数据处理装置的处理器，从而生产出一种机器，使得 该些计算机程序指令在通过计算机或其它可编程数据处理装置的处理器执行时，产生了实 现流程图和/或框图中的一个或多个方框中规定的功能/动作的装置。
[0061] 也可W把该些计算机程序指令存储在计算机可读介质中，该些指令使得计算机、 其它可编程数据处理装置、或其他设备W特定方式工作，从而，存储在计算机可读介质中的 指令就产生出包括实现流程图和/或框图中的一个或多个方框中规定的功能/动作的指令 的制造品（articleofmanufacture)。
[0062] 也可W把该些计算机程序指令加载到计算机、其它可编程数据处理装置或其它设 备上，W致使在计算机、其它可编程数据处理装置或其它设备执行一系列操作步骤，W生成 计算机实现的过程，使得在计算机或其它可编程装置上执行的指令提供用于实现流程图和 /或框图中的一个或多个方框中规定的功能/动作的过程。
[0063] 图9是表示按照一个示例性实施例的高带宽压缩至编码的数据流的机制的流程 图。操作开始（框900)后，该机制将数据流的一部分转换为一个二周期帖（框901)。该 机制从第一个未编码字节开始（框902)，计算该帖中的数据的每个周期长度的子字符串的 哈希（框903)。该机制然后用哈希作为地址将数据的每个子字符串写到相应的词典存储 器（框904)。对于一个二周期帖一一其中每个周期是N个字节一一来说，该机制向N个词 典存储器的每一个写一个N字节的子字符串。
[0064] 该机制用所有计算出的哈希作为地址从所有词典存储器中读取数据的子字符串 (框905)。在框905,该机制从N个词典存储器进行N次读取，尽管该些读取中许多结果是 无效的数据。然后，该机制比较每个子字符串与从相应的词典存储器读取的数据（框906)， 选择在该子字符串的第一个字节处开始的连续字节的最长匹配（框907)。该机制于是有来 自每个词典存储器的一个匹配，一共N个匹配。
[0065] 之后，该机制选择该些匹配的一个子集（框908)。该机制选择匹配，W覆盖2N-1 个字节的尽可能多的字节。该机制首先可W先选择一个穿越周期边界并覆盖当前周期的尽 可能多的字节。该机制然后可w选择额外的匹配w覆盖当前周期的更多字节。该机制然后W文字形式编码不匹配的字节，并用长度信息和距离信息编码匹配（框909)，其中，长度指 示匹配的字节长度，距离引用数据流中数据的先前实例。然后，该机制进行位/字节对齐 (框 910)。
[0066] 该机制然后判定当前周期是否是最后周期（框911)。如果当前周期不是数据流中 的最后周期，该机制考虑数据流中的下一个周期（框912)，操作返回到框901，W将数据转 换为二周期帖。然后，对该下一个周期重复操作。如果在框911，当前周期是数据流中数据 的最后周期，则操作结束（框913)。
[0067] 附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法和计算机程 序产品的可能实现的体系架构、功能和操作。在该点上，流程图或框图中的每个方框可W 代表一个模块、程序段或代码的一部分，所述模块、程序段或代码的一部分包含一个或多个 用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所 标注的功能也可不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可W 基本并行地执行，它们有时也可W按相反的顺序执行，该依所设及的功能而定。也要注意的 是，框图和/或流程图中的每个方框、化及框图和/或流程图中的方框的组合，可W用执行 规定的功能或动作的专用的基于硬件的系统来实现，或者可W用专用硬件与计算机指令的 组合来实现。
[0068] 因此，示例性实施例提供用于高带宽压缩至编码的数据流的机制。该些机制在连 续的周期处理数据，实现低延迟、高吞吐率。对一个N字节的数据周期，该机制使用为该N 字节数据中的每个字节偏址执行N次读和一次写的N个词典存储器。
[0069] 如上所述，应该明白，示例性实施例可W采取完全硬件体现的形式、完全软件体现 的形式或包含硬件和软件两种元素的体现形式。在一个实施例中，示例性实施例的机制在 软件或程序代码中实现，包括但不限于固件、常驻软件、微代码，等等。
[0070] 适于存储和/或执行程序代码的将数据处理系统包括至少一个通过系统总线处 理器直接地或间接地禪合到存储单元的处理器。存储单元在程序代码的实际执行期间采用 的本地存储器、大容量存储器、W及高速缓冲存储器，后者为至少一些程序代码提供临时存 储W减少在执行期间代码必须从大容量存储器取出的次数。
[0071] 输入/输出或I/O设备（包括但不限于键盘、显示器、指点设备，等等）可W直接 地或通过中间的I/O控制器禪接到系统。网络适配器也可W禪接到系统，使数据处理系统 能通过专用或公共网络禪接到其它数据处理系统或远程打印机或存储设备。调制解调器、 电缆调制解调器和W太网卡只是当前可用的几类网络适配器。
[0072] 已经描述了本发明，W上描述是示例性和说明性的，而穷举性的，也并非是要把本 发明限定到所公开的形式。对于所属技术领域的普通技术人员来说，许多修改和变更都是 显而易见的。对实施例的选择和描述的方式，是为了最好地解释本发明的原理和实际应用， 使所属技术领域的普通技术人员能理解本发明具有为适合特定用途而作了各种修改的各 种实施方式。
【主权项】
1. 用于在数据处理系统中流水线式压缩多字节帧的方法，该方法包含： 组合输入数据流中当前周期的数据与所述输入数据流中下一个周期的数据的至少一 部分，以构成数据帧； 识别多个词典存储器的多个匹配，其中每个匹配与该数据帧中的给定子字符串的一部 分匹配； 从该多个匹配中识别提供对当前周期的数据的最佳覆盖的匹配子集；和 把该数据帧编码成编码的输出数据流。2. 按照权利要求1的方法，其中，组合输入数据流中当前周期的数据与输入数据流中 下一个周期的数据的至少一部分包含：构成多个子字符串，各子字符串始于当前周期的数 据的一个对应字节并有与当前周期的数据相等的长度。3. 按照权利要求1或2的方法，其中，该匹配子集穿过第一周期的数据和下一个周期的 数据之间的周期边界。4. 按照权利要求1至3的任何之一的方法，其中，把该数据帧编码成编码的输出数据流 包含： 用长度信息和距离信息编码该匹配子集的每个，以构成匹配编码的数据； 用无损压缩编码该输入数据流中的当前周期的数据中的不匹配数据，以构成压缩编码 的数据；和 在输出数据流中把匹配编码的数据与压缩编码的数据对准。5. 按照权利要求1至4的任何之一的方法，进一步包含： 根据多个子字符串中的每个给定子字符串生成地址，以构成多个地址。6. 按照权利要求5的方法，其中，生成地址包含对所述给定子字符串执行哈希。7. 按照权利要求5或6的方法，进一步包含： 用从给定子字符串生成的地址把每个给定子字符串和对应的位置值写到该多个词典 存储器中的对应的词典存储器。8. 按照权利要求5至7的任何之一的方法，其中，识别多个匹配包含： 用该多个地址读取该多个词典存储器内的每个给定词典存储器，以接收每个词典存储 器的零个或更多个有效条目。9. 按照权利要求8的方法，其中，识别多个匹配进一步包含： 对于每个具有至少一个有效条目的词典存储器，比较该至少一个有效条目与对应子字 符串；和 对于每个具有至少一个有效条目的词典存储器，根据从该对应子字符串起始处开始的 连续的匹配字节的数量选择最长的匹配，以构成多个匹配。10. 按照权利要求9的方法，其中，多个匹配的每个都有一个匹配长度值和一个位置 值，其中，长度值表示匹配数据的长度，位置值引用输入数据流中该匹配数据的在前出现。11. 用于在数据处理系统中流水线式压缩多字节帧的装置，该装置包含： 词典查询/更新阶段，包含多个词典存储器和相关逻辑； 匹配选择阶段，包含多个比较电路和相关逻辑；和 编码阶段， 其中，词典查询/更新阶段接收包含输入数据流中当前周期的数据与输入数据流中下 一个周期的数据的至少一部分组合的数据帧，识别多个词典存储器的多个匹配，其中每个 匹配与所述多个子字符串中的给定子字符串的一部分匹配； 其中，所述匹配选择阶段用多个比较电路从提供对当前周期的数据的最佳覆盖的多个 匹配中识别匹配的子集；和 其中，所述编码阶段把该数据帧编码成编码的输出数据流。12. 按照权利要求11的装置，其中，组合输入数据流中当前周期的数据与输入数据流 中下一个周期的数据的至少一部分包含：构成多个子字符串，各子字符串始于当前周期的 数据的对应字节并有与当前周期的数据相等的长度。13. 按照权利要求11或12的装置，其中，该匹配子集穿过第一周期的数据和下一个周 期的数据之间的周期边界。14. 按照权利要求11至13的任何之一的装置，其中，所述编码阶段用长度信息和距离 信息编码该匹配子集的每个，以构成匹配编码的数据，并用无损压缩编码该输入数据流中 的当前周期的数据中的不匹配数据，以构成压缩编码的数据。15. 按照权利要求14所述的装置，其中，所述编码阶段包含霍夫曼编码电路，并且其 中，编码阶段用霍夫曼编码电路编码不匹配数据。16. 按照权利要求11至15的任何之一的装置，进一步包含： 位/字节对准阶段，其中，位/字节对准阶段在输出数据流中把匹配编码的数据与压缩 编码的数据对准。17. 按照权利要求11至16的任何之一的装置，其中，所述词典查询/更新阶段根据多 个子字符串中的每个给定子字符串生成地址，以构成多个地址。18. 按照权利要求17的装置，其中，所述词典查询/更新阶段通过对所述给定子字符串 执行哈希来生成地址。19. 按照权利要求17或18的装置，其中，所述词典查询/更新阶段用从所述给定子字 符串生成的地址把每个给定子字符串和对应的位置值写到该多个词典存储器中的对应的 词典存储器。20. 按照权利要求17至19的任何之一的装置，其中，所述词典查询/更新阶段通过以 下方式识别多个匹配：用该多个地址读取该多个词典存储器内的每个给定词典存储器，以 接收每个词典存储器的零个或更多个有效条目。21. 按照权利要求20的装置，其中，匹配选择阶段通过以下方式识别匹配的子集：对于 每个具有至少一个有效条目的词典存储器，比较该至少一个有效条目与对应子字符串；和 对于每个具有至少一个有效条目的词典存储器，根据从该对应子字符串起始处开始的连续 的匹配字节的数量选择最长的匹配，以构成多个匹配。22. 按照权利要求21的装置，其中，所述多个匹配的每个都有一个匹配长度值和一个 位置值，其中，长度值表示匹配数据的长度，位置值引用输入数据流中该匹配数据的在前出 现。23. -种计算机程序产品，包含其中存储有计算机可读程序的计算机可读介质，其中， 计算机可读程序在计算设备上执行时使计算设备： 组合输入数据流中当前周期的数据与所述输入数据流中下一个周期的数据的至少一 部分，以构成数据帧； 识别多个词典存储器的多个匹配，其中每个匹配与该数据帧中的给定子字符串的一部 分匹配； 从该多个匹配中识别提供对当前周期的数据的最佳覆盖的匹配子集；和 把该数据帧编码成编码的输出数据流。24. 按照权利要求23的计算机程序产品，其中，组合输入数据流中当前周期的数据与 输入数据流中下一个周期的数据的至少一部分包含：构成多个子字符串，各子字符串始于 当前周期的数据的一个对应字节并有与当前周期的数据相等的长度。25. 按照权利要求23或24的计算机程序产品，其中，该匹配子集穿过第一周期的数据 和下一个周期的数据之间的周期边界。26. 按照权利要求23至25的任何之一的计算机程序产品，其中，把该数据帧编码成编 码的输出数据流包含： 用长度信息和距离信息编码该匹配子集的每个，以构成匹配编码的数据； 用无损压缩编码该输入数据流中的当前周期的数据中的不匹配数据，以构成压缩编码 的数据；和 在输出数据流中把匹配编码的数据与压缩编码的数据对准。27. 按照权利要求23至26的任何之一的计算机程序产品，进一步包含： 根据多个子字符串中的每个给定子字符串生成地址，以构成多个地址。28. 按照权利要求27的计算机程序产品，其中，生成地址包含对所述给定子字符串执 行哈希。29. 按照权利要求27或28的计算机程序产品，进一步包含： 用从给定子字符串生成的地址把每个给定子字符串和对应的位置值写到该多个词典 存储器中的对应的词典存储器。30. 按照权利要求27至29的任何之一的计算机程序产品，其中，识别多个匹配包含： 用该多个地址读取该多个词典存储器内的每个给定词典存储器，以接收每个词典存储 器的零个或更多个有效条目。31. 按照权利要求30的计算机程序产品，其中，识别多个匹配进一步包含： 对于每个具有至少一个有效条目的词典存储器，比较该至少一个有效条目与对应子字 符串；和 对于每个具有至少一个有效条目的词典存储器，根据从该对应子字符串起始处开始的 连续的匹配字节的数量选择最长的匹配，以构成多个匹配。32. 按照权利要求30的计算机程序产品，其中，多个匹配的每个都有一个匹配长度值 和一个位置值，其中，长度值表示匹配数据的长度，位置值引用输入数据流中该匹配数据的 在前出现。
【专利摘要】提供一种用于在数据处理系统中流水线式压缩多字节帧的机制。该机制组合输入数据流中当前周期的数据与所述输入数据流中下一个周期的数据的至少一部分，以构成数据帧。该机制识别多个词典存储器的多个匹配。每个匹配与该数据帧中的给定子字符串的一部分匹配。该机制从该多个匹配中识别提供对当前周期的数据的最佳覆盖的匹配子集。该机制把该数据帧编码成编码的输出数据流。
【IPC分类】H03M7/40
【公开号】CN104904123
【申请号】CN201380069224
【发明人】D·A·詹姆塞克, K·B·阿加瓦尔, H·P·霍夫施蒂, A·K·马丁
【申请人】国际商业机器公司
【公开日】2015年9月9日
【申请日】2013年12月2日
【公告号】DE112013006339T5, US8704686, WO2014106782A1
最新回复(0)