PRODUCING CHUNKS FROM INPUT DATA USING A PLURALITY OF PROCESSING ELEMENTS

• US 20100246709A1
• Filed: 03/27/2009
• Published: 09/30/2010
• Est. Priority Date: 03/27/2009
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Lillibridge, Mark David, Eshghi, Kave, Perry, Graham
• Granted Patent: US 7,979,491 B2
• Time in Patent Office: Days
• US Class Current: 375/295
• 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, 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.

2. The method of claim 1, wherein stitching the plurality of tentative sets of chunks together to produce the output set of chunks 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.

3. The method of claim 1, wherein stitching the plurality of tentative sets of chunks together to produce the output set of chunks 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.

4. The method of claim 3, 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.

10. The method of claim 1, further comprising:

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

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

12. 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.

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 that is based on a first one of the segments, and a second tentative set of chunks that is based on a second one of the segments;

extend the first tentative set until synchronization occurs; 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.

14. The computer of claim 13, wherein the synchronization comprises identifying 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.

15. The computer of claim 13, wherein synchronization is considered to occur when a timeout occurs.

16. The computer of claim 13, wherein the processing elements are to further use information of the second tentative set when extending the first tentative set.

17. 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.

18. An article comprising at least one computer-readable storage medium containing instructions that when executed cause a computer to:

process segments, by a plurality of processing elements in parallel, of the input data to identify chunk boundaries, wherein the processing produces at least a first tentative set of chunks that is based on at least first and second ones of the segments, and a second tentative set of chunks that is based on at least the second segment; and

perform harmonization to resolve inconsistencies in the chunk boundaries identified by the first and second tentative sets.

19. The article of claim 18, wherein 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 identifying a 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.

20. The article of claim 18, wherein 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