Producing chunks from input data using a plurality of processing elements

• US 7,979,491 B2
• Filed: 03/27/2009
• Issued: 07/12/2011
• Est. Priority Date: 03/27/2009
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Perry, Graham, Lillibridge, Mark David, Eshghi, Kave
• Primary Examiner(s): EL CHANTI, HUSSEIN A
• Application Number:
  US12/412,821
• Publication Number:
  US 20100246709A1
• Time in Patent Office: 837 Days
• Field of Search: 709/203, 709/223, 709/224, 709/205, 709/226
• US Class Current: 709/205
• CPC Class Codes: G06F 16/90348 by searching ordered data, e.g. alpha-numerically ordered data

Abstract

Input data is divided into multiple segments that are processed by processing elements of a computer. The processing of the segments produces a plurality of tentative sets of chunks. The plurality of tentative sets of chunks are stitched together to produce an output set of chunks.

Claims

1. A method executed by a computer including a plurality of processing elements, comprising:

dividing input data into a plurality of segments;

processing the plurality of segments, in parallel, by the processing elements in the computer, wherein processing the plurality of segments produces a plurality of tentative sets of chunks defined by respective chunk boundaries, wherein at least one of the plurality of tentative sets includes a chunk defined by a particular chunk boundary that would not have been identified as a chunk boundary if the input data were sequentially processed by a single one of the processing elements; and

stitching the plurality of tentative sets of chunks together to produce an output set of chunks, wherein the stitching comprises;

creating a combined set of chunks by combining the plurality of tentative sets of chunks; and

merging two adjacent or overlapping chunks from different tentative sets of chunks into a single chunk if a size of a resulting chunk from the merging would not exceed a predetermined maximum chunk size.

2. The method of claim 1, further comprising:

each of the processing elements using an end of the corresponding segment as a chunk boundary.

3. The method of claim 1, further comprising:

detecting a start of a region of one of the segments that is a landmark-free region; and

in response to detecting the start of such landmark-free region, using a specialized algorithm to process the landmark-free region.

10. The method of claim 2, further comprising using information of the second tentative set when finding chunk boundaries during processing to extend the first tentative set.

4. A method executed by a computer including a plurality of processing elements, comprising:

dividing input data into a plurality of segments;

processing the plurality of segments, in parallel, by the processing elements in the computer, wherein processing the plurality of segments produces a plurality of tentative sets of chunks; and

stitching the plurality of tentative sets of chunks together to produce an output set of chunks, wherein the stitching comprises;

extending a first of the tentative sets of chunks until the first tentative set of chunks reaches a synchronization point with respect to a second of the tentative sets, wherein the extended first tentative set of chunks is based on at least first and second ones of the plurality of segments, wherein the second tentative set is based on at least the second segment, and wherein stitching the plurality of tentative sets of chunks further comprises removing inconsistencies in chunks identified by the extended first tentative set and the second tentative set.

5. The method of claim 4, further comprising a first of the plurality of processing elements processing the first segment, and a second of the plurality of processing elements processing the second segment, wherein extending the first tentative set of chunks comprises the first processing element further processing at least part of the second segment.

6. The method of claim 4, further comprising a first of the plurality of processing elements processing the first segment, and a second of the plurality of processing elements processing the second segment without using information from the first segment, wherein extending the first tentative set of chunks comprises one of the plurality of processing elements processing at least part of the second segment using information from the first segment.

7. The method of claim 4, wherein the synchronization point is a point that is a chunk boundary of a chunk contained in the extended first tentative set of chunks and of a chunk contained in the second tentative set.

8. The method of claim 7, wherein extending the first tentative set further comprises:

providing a timeout counter; and

upon expiration of the timeout counter, if a synchronization point has not been reached yet, using the next boundary identified in the second tentative set as the synchronization point.

9. The method of claim 4, wherein stitching the tentative sets of chunks together further comprises choosing which chunks of the extended first tentative set and the second tentative set to include in the output set of chunks based on their relation to the synchronization point.

11. The method of claim 4, further comprising:

each of the processing elements using an end of the corresponding segment as a chunk boundary.

12. The method of claim 4, further comprising:

detecting a start of a region of one of the segments that is a landmark-free region; and

in response to detecting the start of such landmark-free region, using a specialized algorithm to process the landmark-free region.

13. A computer comprising:

a storage device to store input data; and

a plurality of processing elements to;

process segments of the input data to identify tentative chunk boundaries, wherein the processing produces at least a first tentative set of chunks defined by a first group of the tentative chunk boundaries that is based on a first one of the segments, and a second tentative set of chunks defined by a second group of the tentative chunk boundaries that is based on a second one of the segments;

extend the first tentative set until synchronization occurs, wherein the synchronization comprises identifying a point that is a chunk boundary of a chunk contained in the extended first tentative set and of a chunk contained in the second tentative set, wherein the extended first tentative set of chunks is based on at least the first and second segments; and

select a set of the chunking boundaries identified by the extended first tentative set or the second tentative set to provide as part of an output set of chunking boundaries, wherein the selecting comprises removing inconsistencies in chunks identified by the extended first tentative set and the second tentative set.

14. The computer of claim 13, wherein the processing elements are to further:

detect a start of a region of one of the segments that is a landmark-free region; and

in response to detecting the start of such landmark-free region, use a specialized algorithm to process the landmark-free region.

15. The computer of claim 13, wherein the second tentative set includes a chunk defined by a particular chunk boundary that would not have been identified as a chunk boundary if the input data were sequentially processed by a single one of the processing elements.

16. An article comprising at least one non-transitory computer-readable storage medium storing instructions that when executed cause a computer to:

process segments, by a plurality of processing elements in parallel, of input data to identify chunk boundaries defining respective chunks, wherein the processing produces at least a first tentative set of the chunks that is based on at least first and second ones of the segments, and a second tentative set of the chunks that is based on at least the second segment, and wherein the processing comprises extending the first tentative set until the first tentative set reaches a synchronization point with respect to the second tentative set; and

stitch at least the first and second tentative sets of chunks together to produce an output set of chunks, wherein the stitching comprises performing harmonization to resolve inconsistencies in the chunk boundaries identified by the first and second tentative sets.

17. The article of claim 16, wherein the processing comprises identifying the synchronization point as a first common chunking boundary in the second segment that will be part of each of the first and second tentative sets.

18. The article of claim 16, wherein the processing to produce at least the first tentative set of chunks that is based on at least the first and second ones of the segments comprises using a timeout counter.

19. The article of claim 16, wherein the second tentative set includes a chunk defined by a particular chunk boundary that would not have been identified as a chunk boundary if the input data were sequentially processed by a single one of the processing elements.