CN115438009B

CN115438009B - 基于simd指令集的数据块特征并行提取方法及差量压缩方法

Info

Publication number: CN115438009B
Application number: CN202211018482.4A
Authority: CN
Inventors: 王芳; 冯丹; 秦磊华; 施展; 王强; 严伟杰; 王丰; 刘昊
Original assignee: Huazhong University of Science and Technology
Current assignee: Huazhong University of Science and Technology
Priority date: 2022-08-24
Filing date: 2022-08-24
Publication date: 2025-11-25
Anticipated expiration: 2042-08-24
Also published as: CN115438009A

Abstract

本发明公开了一种基于SIMD指令集的数据块特征并行提取方法及差量压缩方法，属于计算机存储技术领域，包括：将数据块划分为等长的N个子块，相邻子块相互重叠；设置N个相同大小的滑动窗口在N个子块上自左向右同步滑动，滑动步长为K个字节，每滑动至一个位置，则将各窗口内左侧的K个字节并行加载到向量寄存器L中，将各窗口外右侧的K个字节并行加载到向量寄存器R中，之后逐字节、并行地从向量寄存器L和R取各子块相应的相应字节，以计算指纹，并更新各子块存储于向量寄存器F中的特征；当滑动窗口抵达子块尾部时，将F中的特征组合为数据块特征并写入内存。本发明能够在保证相似性检测的检测效果的前提下，有效提高相似性检测的吞吐量。

Description

基于SIMD指令集的数据块特征并行提取方法及差量压缩方法

技术领域

本发明属于计算机存储技术领域，更具体地，涉及一种基于SIMD指令集的数据块特征并行提取方法及差量压缩方法。

背景技术

随着信息技术的蓬勃发展和互联网的不断普及，企业与个人每天都会产生大量的数据。根据IDC的统计和预测，2018年全球数据产生量达到了 33ZB，而到了2025年，这一数字将达到惊人的175ZB，全球数据总量将迎来更大规模的爆发。根据微软的研究报告，企业和个人的存储设备中存在着大量的冗余数据，造成了存储资源的浪费。因此，差量压缩等冗余数据消除技术成了当前学术界和工业界研究的热点。差量压缩的压缩对象是相似的文件或数据块。为了尽可能提高差量压缩效果，并降低差量编码的计算开销，在差量压缩过程中常利用相似性检测技术来选取差量压缩的对象。

直接比较数据内容是判断两个文件或数据块之间相似度最简单的方法，但是这种方法过于耗时，无法满足大规模存储系统对于性能的要求。目前的存储系统主要使用文件或数据块的特征值来代替数据内容进行相似度判断。这一类相似性检测方法一般分为特征提取和特征匹配两个阶段。特征提取指的是从文件或数据块中提取出具有代表性的特征值的过程，而特征匹配指的是通过匹配特征值的方式查找相似文件或数据块的过程。

超级特征值法(Super-feature)是目前最常用的相似性检测方法，被广泛地应用在了存储系统中。在特征提取阶段中，超级特征值法首先采用基于Rabin指纹的滑动哈希算法来计算数据块中所有数据片段的Rabin指纹，接着对所有Rabin指纹进行N次线性变换操作，最后将每个线性变换操作所对应的最大的哈希值选为数据块的特征值。在特征提取阶段结束后，超级特征值法会将固定数量的特征值打包成多个超级特征值。如果两个数据块的某个超级特征值相同，则表示它们有很大的概率是相似的。这种打包策略将特征匹配过程简化为查询超级特征值索引，极大地降低了相似性检测的检测开销，取得了较好的检测效果。

然而，超级特征值法具有很大的计算开销，限制了数据块相似性检测的吞吐量，影响了后续差量压缩的执行效率。与此同时，随着SIMD(Single Instruction MultipleData，单指令多数据流)技术的不断发展，越来越多的研究人员已经开始利用硬件来优化冗余数据消除过程中的计算密集型环节，比如SS-CDC利用了AVX-512指令集和多线程技术来实现数据分块过程的两阶段并行，提高了分块吞吐量。类似数据分块，相似性检测中的数据块特征提取过程也属于冗余数据消除过程中的计算密集型环节，目前已有一部分工作致力于降低相似性检测方法在特征提取阶段的计算开销，但是这些工作都采用了串行的方式执行数据块的特征提取，而没有从并行化的角度优化现有的相似性检测方法。

因此，如何在保证相似性检测方法的检测效果的前提下，提高特征提取方法的吞吐量，是一个亟待解决的问题。

发明内容

针对现有技术的缺陷和改进需求，本发明提供了一种基于SIMD指令集的数据块特征并行提取方法及差量压缩方法，其目的在于，有效解决数据块相似性检测过程中特征提取的时间延迟问题，从而在保证差量压缩中相似性检测的检测效果的前提下，有效提高相似性检测的吞吐量。

为实现上述目的，按照本发明的一个方面，提供了一种基于SIMD指令集的数据块特征并行提取方法，包括：

将数据块等分为N个互不重叠的数据片段后，将第1个数据片段的右边界向右偏移M字节，将第2～N个数据片段的左边界分别向左偏移M字节，得到N个子块；

设置N个大小为W字节的滑动窗口在N个子块上自左向右同步滑动，滑动步长为K个字节；滑动窗口每滑动至一个位置，则将各滑动窗口内左侧的K个字节并行加载到向量寄存器L中，将各滑动窗口外右侧的K个字节并行加载到向量寄存器R中，之后逐字节、并行地从向量寄存器L和R 取各子块相应的相应字节，以计算各子块相应字节处的指纹，并基于指纹计算结果更新各子块的特征；各子块的特征存储于向量寄存器F中；

当滑动窗口抵达各子块最右侧时，将向量寄存器F中各子块的特征组合为数据块特征并写入内存；

其中，N、W、M和K均为正整数，并且M小于数据片段长度，N*K 不超过SIMD指令集中并行数据加载指令一次可加载的字节数。

进一步地，M＝W-n；n为正整数，且n<W。

进一步地，n＝1。

进一步地，将各滑动窗口内左侧的K个字节并行加载到向量寄存器L 中，以及将各滑动窗口外右侧的K个字节并行加载到向量寄存器R中，均通过gather指令完成。

进一步地，N＝16，K＝4；或者，N＝8，K＝8。

进一步地，W＝48，或者，W＝32。

进一步地，并行地从向量寄存器L和R取各子块相应的相应字节，通过and指令完成。

进一步地，对于单个子块，从向量寄存器L和R中取出的第P个字节进行Rabin指纹计算后，所得到的指纹计算结果作为该子块相应字节处的指纹；

其中，P＝1、2……K。

进一步地，基于指纹计算结果更新各子块的特征，包括：

对于每一个子块B_i，将所计算的指纹M_i与向量寄存器F中存储的特征 F_i进行比较，若M_i>F_i，则将向量寄存器F中存储的特征F_i对应替换为所计算的指纹M_i，否则，向量寄存器F中存储的特征F_i保持不变。

按照本发明的另一个方面，提供了一种差量压缩方法，包括：

利用本发明提供的上述基于SIMD指令集的数据块特征并行提取方法对各数据块进行特征提取；

对提取得到的数据块特征进行特征匹配，得到基本数据块及其相似数据块；

对相似数据块与对应基本数据块之间的差量进行差量编码，得到差量编码数据块，分别存储基本数据块和对应的差量编码数据块，完成差量压缩。

按照本发明的又一个方面，提供了一种存储控制器，包括处理器和计算机可读存储介质；

计算机可读存储介质中存储有计算机程序；处理器用于读取计算机可读存储介质中存储的计算机程序，执行本发明提供的上述基于SIMD指令集的数据块特征并行提取方法，和/或本发明提供的上述差量压缩方法。

总体而言，通过本发明所构思的以上技术方案，能够取得以下有益效果：

(1)本发明通过将数据块划分为子块，并利用SIMD指令集并行提取多个子块的特征，最终由各子块的特征共同构成整个数据块的特征；本发明对数据块划分所得的子块中，每个子块保留了上一个子块末尾的字节信息，由此保留了指纹计算过程中的内容依赖性，消除了分块操作对边界处指纹计算的影响，取得了和传统的串行特征提取方法相同的提取效果；传统的采用串行方式进行数据块特征提取的方法，在特征提取的过程中，指纹和特征值计算的次数等于数据块的长度，而本发明将数据块的特征提取过程并行化，其中指纹和特征值计算的次数为子块的长度，因此，可以获得远高于传统串行特征提取方法的吞吐量。总的来说，本发明能够在保证特征提取效果的基础上，有效提高特征提取的吞吐量，从而在保证差量压缩中相似性检测的检测效果的前提下，有效提高相似性检测的吞吐量。

(2)本发明在分块的过程中，通过控制数据分片边界的偏移量不超过滑动窗口的大小，使得第2～N个子块中，相邻子块之间的重叠区域的大小不足一个滑动窗口的大小，由此能够保证后续指纹计算过程中，不会出现重复计算的情况；在其优选方案中，该偏移量比窗口长度少1个字节，由此能够在避免出现重复指纹计算的情况下，最大程度上保留前后内容之间的依赖性，保证特征提取的效果。

附图说明

图1为本发明实施例提供的基于SIMD指令集的数据块特征并行提取方法流程图；

图2为本发明实施例提供的子块划分方法示意图；

图3为本发明实施例提供的基于AVX-512指令集中的gather指令加载各个子块的字节数据到向量寄存器的示意图；

图4为本发明实施例提供的基于AVX-512指令集中的and指令从向量寄存器中选出字节数据计算Rabin指纹和更新特征值的示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

在本发明中，本发明及附图中的术语“第一”、“第二”等(如果存在)是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。

为了解决现有的差量压缩技术因采用串行化的数据块特征提取方法而导致相似性检测吞吐率低的技术问题，本发明提供了一种基于SIMD指令集的数据块特征并行提取方法及差量压缩方法，其整体思路在于：利用 SIMD指令集中数据记载指令的并行性，将数据块划分为重叠的多个子块，以保留前后数据之间的内容依赖性，并对多个子块进行并行地特征提取，从而在保证特征提取效果的基础上，有效提高特征提取的吞吐率。

本发明可基于任意一种支持并行数据加载指令的SIMD指令集实现，不失一般性地，在以下实施例中，均以AVX-512这一特定的SIMD指令集为例进行说明。容易理解的是，在以下实施例中，数据块的“左”、“右”分别表示低地址端和高地址端。

以下为实施例。

实施例1：

一种基于SIMD指令集的数据块特征并行提取方法，其流程图如图1 所示。

本实施例首先将数据划分为多个相互重叠的子块。AVX-512指令集中的并行数据加载指令，即gather指令，可以一次性从16个子块并行加载4 字节的数据，或从8个子块并行加载8字节的数据，为了充分利用该并行性，作为一种优选的实施方式，本实施例中，具体设置划分所得重叠子块的数量为N＝16，并且后续每次将字节数据加载到向量寄存器中时，各子块被加载的字节数为K＝4；

基于上述参数设定，如图2所示，本实施例具体通过如下方式将数据块划分为16个存在重叠的子块：

将数据块等分为16个互不重叠的数据片段后，将第1个数据片段的右边界向右偏移M字节，将第2～16个数据片段的左边界分别向左偏移M字节，得到16个子块，依次记为子块0～子块15；M为正整数，且M小于数据片段长度；

本实施例所得的16个子块中，第1个子块与第二个子块间重叠区域的大小为2M个字节，其他相邻子块之间的重叠区域的大小是M个字节，也即是说，每个子块保留了上一个子块末尾的字节信息。

子块划分结束后，如图3所示，设置16个大小为W字节的滑动窗口在 16个子块上自左向右同步滑动，滑动步长为K个字节；与各个子块每次被加载的字节数相对应地，本实施例中，滑动窗口的滑动步长为K＝4；可选地，本实施例中，滑动窗口的大小为W＝48字节；

滑动窗口每滑动至一个位置，则利用gather指令将各滑动窗口内左侧的K个字节(即将离开滑动窗口的字节数据)，并行加载到向量寄存器L 中，利用gather指令将各滑动窗口外右侧的K个字节(即将进入滑动窗口的字节数据)并行加载到向量寄存器R中，之后逐字节、并行地从向量寄存器L和R取各子块相应的相应字节，以计算各子块相应字节处的指纹，并基于指纹计算结果更新各子块的特征；各子块的特征存储于向量寄存器F 中；

由于在后续计算指纹时，需要同时利用滑动窗口周围的字节计算生成，具有依赖性，若直接将数据块划分为互不重叠的数据片段后并行计算，会给指纹计算带来误差，造成后续检测结果的不准确，本实施例所提供的重叠子块，由于每个子块保留了上一个子块末尾的字节信息，能够保留前后数据之间的依赖性，消除分块边界操作对边界出Rabin指纹计算的影响；为了避免在针对滑动窗口周围的数据进行指纹计算时，出现重复的计算，本实施例在划分重叠子块时，会控制子块边界的偏移量小于滑动窗口的字节长度，本实施例中，该偏移量具体为M＝W-1＝47；除了第一个子块外，每个子块的前M个字节计算得出的哈希值不参与特征值计算。

参阅图1和图4，上述基于滑动窗口计算指纹并更新特征的过程具体包括如下步骤：

(S0)将各滑动窗口内左侧的K个字节并行加载到向量寄存器L中，将各滑动窗口外右侧的K个字节并行加载到向量寄存器R中；

(S1)初始化P＝1；

(S2)从向量寄存器L中取各子块的第P个字节，并从向量寄存器R 中取各子块的第P个字节，对于每一个子块，利用Rabin哈希函数对其从向量寄存器中读取的两个字节计算哈希值，得到对应的指纹；为了提取特定位置的字节，本实施例中，利用and指令将从向量寄存器L和R中选出第P个字节的数据进行Rabin指纹计算；

(S3)判断当前字节是否是数据块后15个子块的前47个字节，若是，则直接转入步骤(S5)，否则，转入步骤(S4)；

(S4)根据所计算的指纹更新向量寄存器F中子块的特征值；具体地，将各子块的指纹与向量寄存器F中各子块对应的特征值进行比较，若指纹值大于特征值，将向量寄存器F中的特征值更新为对应子块的指纹，否则，向量寄存器F中的特征值保持不变；

(S5)若P＝K，则当前滑动窗口内的字节数据指纹计算结束，转入步骤(S6)；否则，令P＝P+1，之后转入步骤(S2)；

(S6)将各滑动窗口同时向右滑动K个字节，并判断滑动窗口是否抵达子块的尾部，若是，则将向量寄存器F中各子块的特征组合为数据块特征并写入内存，数据块特征提取结束；否则，转入步骤(S0)。

实施例2：

一种差量压缩方法，包括：

利用上述实施例1提供的基于SIMD指令集的数据块特征并行提取方法对各数据块进行特征提取；

实施例3：

一种存储控制器，包括处理器和计算机可读存储介质；

计算机可读存储介质中存储有计算机程序；处理器用于读取计算机可读存储介质中存储的计算机程序，执行上述实施例1提供的基于SIMD指令集的数据块特征并行提取方法，和/或上述实施例2提供的差量压缩方法。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。

Claims

1.一种基于SIMD指令集的数据块特征并行提取方法，其特征在于，包括：

设置N个大小为W字节的滑动窗口在N个子块上自左向右同步滑动，滑动步长为K个字节；滑动窗口每滑动至一个位置，则将各滑动窗口内左侧的K个字节并行加载到向量寄存器L中，将各滑动窗口外右侧的K个字节并行加载到向量寄存器R中，之后逐字节、并行地从向量寄存器L和R取各子块相应的相应字节，以计算各子块相应字节处的指纹，并基于指纹计算结果更新各子块的特征；各子块的特征存储于向量寄存器F中；

当滑动窗口抵达各子块最右侧时，将所述向量寄存器F中各子块的特征组合为数据块特征并写入内存；

其中，N、W、M和K均为正整数，并且M小于数据片段长度，N*K不超过SIMD指令集中并行数据加载指令一次可加载的字节数。

2.如权利要求1所述的基于SIMD指令集的数据块特征并行提取方法，其特征在于，M＝W-n；n为正整数，且n<W。

3.如权利要求1所述的基于SIMD指令集的数据块特征并行提取方法，其特征在于，n＝1。

4.如权利要求1～3任一项所述的基于SIMD指令集的数据块特征并行提取方法，其特征在于，将各滑动窗口内左侧的K个字节并行加载到向量寄存器L中，以及将各滑动窗口外右侧的K个字节并行加载到向量寄存器R中，均通过gather指令完成。

5.如权利要求4所述的基于SIMD指令集的数据块特征并行提取方法，其特征在于，N＝16，K＝4；或者，N＝8，K＝8。

6.如权利要求3所述的基于SIMD指令集的数据块特征并行提取方法，其特征在于，并行地从向量寄存器L和R取各子块相应的相应字节，通过and指令完成。

7.如权利要求6所述的基于SIMD指令集的数据块特征并行提取方法，其特征在于，对于单个子块，从向量寄存器L和R中取出的第P个字节进行Rabin指纹计算后，所得到的指纹计算结果作为该子块相应字节处的指纹；

其中，P＝1、2……K。

8.如权利要求7所述的基于SIMD指令集的数据块特征并行提取方法，其特征在于，基于指纹计算结果更新各子块的特征，包括：

对于每一个子块B_i，将所计算的指纹M_i与所述向量寄存器F中存储的特征F_i进行比较，若M_i>F_i，则将所述向量寄存器F中存储的特征F_i对应替换为所计算的指纹M_i，否则，所述向量寄存器F中存储的特征F_i保持不变。

9.一种差量压缩方法，其特征在于，包括：

利用权利要求1～8任一项所述的基于SIMD指令集的数据块特征并行提取方法对各数据块进行特征提取；

10.一种存储控制器，其特征在于，包括处理器和计算机可读存储介质；

所述计算机可读存储介质中存储有计算机程序；所述处理器用于读取所述计算机可读存储介质中存储的计算机程序，执行权利要求1～8任一项所述的基于SIMD指令集的数据块特征并行提取方法，和/或权利要求9所述的差量压缩方法。