Concurrent segmentation using vector processing

• US 10,437,817 B2
• Filed: 08/27/2018
• Issued: 10/08/2019
• Est. Priority Date: 04/19/2016
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Hirsch, Michael, Toaff, Yair, David, Yehonatan
• Primary Examiner(s): Ortiz Ditren, Belix M
• Application Number:
  US16/113,151
• Publication Number:
  US 20180365284A1
• Time in Patent Office: 407 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: H03M 7/3091 Data deduplication

Abstract

A system for segmenting an input data stream, comprising a processor adapted to split an input data stream to a plurality of data sub-streams such that each of the plurality of data sub-streams has an overlapping portion with a consecutive data sub-stream of the plurality of data sub-streams, create concurrently a plurality of segmented data sub-streams by concurrently segmenting the plurality of data sub-streams each in one of a plurality of processing pipelines of the processor and join the plurality of segmented data sub-streams to create a segmented data stream by synchronizing a sequencing of each of the plurality of segmented data sub-streams according to one or more overlapping segments in the overlapping portion of each two consecutive data sub-streams of the plurality of data sub-streams.

Claims

1. A computing system for segmenting an input data stream, comprising:

a vector processor including a plurality of processing pipelines, the vector processor configured to;

split an input data stream to a plurality of data sub-streams, wherein each data sub-stream of the plurality of data sub-streams has an overlapping portion that overlaps with another data sub-stream of the plurality of data sub-streams;

create a plurality of segmented data sub-streams by concurrently segmenting each of the data sub-streams of the plurality of data sub-streams into a corresponding processing pipeline of the plurality of processing pipelines of the vector processor; and

join the segmented data sub-streams in the plurality of segmented data sub-streams to create a segmented data stream by synchronizing a sequencing of the segmented data sub-streams in the plurality of segmented data sub-streams according to at least one overlapping portion of two data sub-streams.

2. The computing system according to claim 1, wherein the vector processor is a single-instruction-multiple-data (SIMD) processor.

3. The computing system according to claim 1, wherein each data sub-stream of the plurality of data sub-streams includes data items, and the vector processor is further configured to:

for each data sub-stream of the plurality of data sub-streams, segment the data sub-stream by calculating a rolling hash value for a rolling sequence applied over each data sequence of a plurality of data sequences of consecutive data items of the data sub-stream, and designate each of the plurality of data sequences as a variable size segment when the rolling hash value complies with at least one segmentation criterion, wherein the rolling sequence comprises a subset of consecutive data items of a respective data sequence.

4. The computing system according to claim 3, wherein each of the plurality of data sequences includes a pre-defined minimum number of the consecutive data items.

5. The computing system according to claim 3, wherein the vector processor is further configured to:

designate at least one large sequence of the plurality of data sequences as the variable size segment in response to determining that a number of the consecutive data items of the at least one large sequence exceeds a pre-defined maximum value before detecting compliance of the rolling hash value with the at least one segmentation criterion.

6. The computing system according to claim 1, wherein the vector processor is further configured to:

sequentially segment the input data stream in response to determining that the synchronizing the sequencing of the segmented data sub-streams fails.

7. A method for segmenting an input data stream, comprising:

splitting an input data stream to a plurality of data sub-streams, wherein each data sub-stream of the plurality of data sub-streams has an overlapping portion that overlaps with a data sub-stream of the plurality of data sub-streams;

creating a plurality of segmented data sub-streams by concurrently segmenting each of the data subs-streams of the plurality of data sub-streams into a corresponding processing pipeline of a plurality of processing pipelines of a vector processor; and

joining the segmented data sub-streams in the plurality of segmented data sub-streams to create a segmented data stream by synchronizing a sequencing of the segmented data sub-streams in the plurality of segmented data sub-streams according to at least one overlapping portion of two data sub-streams.

8. The method according to claim 7, wherein the vector processor is a single-instruction-multiple-data (SIMD) processor.

9. The method according to claim 7, wherein each data sub-stream of the plurality of data sub-streams includes data items, and the method further comprises:

for each data sub-stream of the plurality of data sub-streams, segmenting the data sub-stream by calculating a rolling hash value for a rolling sequence applied over each data sequence of a plurality of data sequences of consecutive data items of the data sub-stream, and designating each of the plurality of data sequences as a variable size segment when the rolling hash value complies with at least one segmentation criterion, wherein the rolling sequence comprises a subset of consecutive data items of a respective data sequence.

10. The method according to claim 9, wherein each of the plurality of data sequences includes a pre-defined minimum number of the consecutive data items.

11. The method according to claim 9, further comprising:

designating at least one large sequence of the plurality of data sequences as the variable size segment in response to determining that a number of the consecutive data items of the at least one large sequence exceeds a pre-defined maximum value before detecting compliance of the rolling hash value with the at least one segmentation criterion.

12. The method according to claim 7, wherein the input data stream is sequentially segmented in response to determining that the synchronizing the sequencing of the segmented data sub-streams fails.

13. A non-transitory computer readable storage medium storing instructions that, when executed, cause a vector processor to segment an input data stream, by performing the steps of:

splitting an input data stream to a plurality of data sub-streams, wherein each data sub-stream of the plurality of data sub-streams has an overlapping portion that overlaps with a data sub-stream of the plurality of data sub-streams;

creating a plurality of segmented data sub-streams by concurrently segmenting each of the data subs-streams of the plurality of data sub-streams into a corresponding processing pipeline of a plurality of processing pipelines of a processor; and

joining the segmented data sub-streams in the plurality of segmented data sub-streams to create a segmented data stream by synchronizing a sequencing of the segmented data sub-streams in the plurality of segmented data sub-streams according to at least one overlapping portion of two data sub-streams.

14. The computer readable storage medium according to claim 13, wherein the vector processor is a single-instruction-multiple-data (SIMD) processor.

15. The computer readable storage medium according to claim 13, wherein each data sub-stream of the plurality of data sub-streams includes data items, and the steps further comprise:

for each data sub-stream of the plurality of data sub-streams, segmenting the data sub-stream by calculating a rolling hash value for a rolling sequence applied over each data sequence of a plurality of data sequences of consecutive data items of the data sub-stream, and designating each of the plurality of data sequences as a variable size segment when the rolling hash value complies with at least one segmentation criterion, wherein the rolling sequence comprises a subset of consecutive data items of a respective data sequence.

16. The computer readable storage medium according to claim 15, wherein each of the plurality of data sequences includes a pre-defined minimum number of the consecutive data items.

17. The computer readable storage medium according to claim 15, wherein the steps further comprise:

designating at least one large sequence of the plurality of data sequences as the variable size segment in response to determining that a number of the consecutive data items of the at least one large sequence exceeds a pre-defined maximum value before detecting compliance of the rolling hash value with the at least one segmentation criterion.

18. The computer readable storage medium according to claim 13, wherein the input data stream is sequentially segmented in response to determining that the synchronizing the sequencing of the segmented data sub-streams fails.