Parallel processing of input data to locate landmarks for chunks

• US 8,001,273 B2
• Filed: 03/16/2009
• Issued: 08/16/2011
• Est. Priority Date: 03/16/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
• Primary Examiner(s): EL CHANTI, HUSSEIN A
• Application Number:
  US12/404,842
• Publication Number:
  US 20100235485A1
• Time in Patent Office: 883 Days
• Field of Search: 709/230, 709/246
• US Class Current: 709/246
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

Input data is divided into a plurality of segments, which are processed, in parallel, by respective first processing elements to locate landmarks in the segments. At least one other processing element is used to produce chunks from the input data based on positions of the landmarks provided by the first processing elements.

Claims

1. A method, comprising:

dividing input data into a plurality of segments;

processing the plurality of segments, in parallel, by respective first processing elements to locate landmarks in the segments, wherein the first processing elements include corresponding processors or cores of at least one processor, wherein locating the landmarks comprises;

computing a fingerprint on corresponding local content of the input data, wherein the corresponding local content is defined by a sliding window, and

designating a position associated with the corresponding local content as a landmark if the corresponding computed fingerprint satisfies a criterion; and

using at least one other processing element to produce chunks from the input data based on positions of the landmarks provided by the first processing elements.

2. The method of claim 1, wherein producing the chunks comprises using the landmarks to derive chunk boundaries of the chunks, wherein not all landmarks are chunk boundaries.

3. The method of claim 2, wherein deriving the chunk boundaries using the landmarks comprises considering preset minimum and maximum chunk sizes.

4. The method of claim 1, further comprising:

generating at least one list by the first processing elements, wherein the list identifies the located landmarks.

5. The method of claim 1, wherein processing the plurality of segments, in parallel, by the respective first processing elements comprises processing the plurality of segments by the processors.

6. The method of claim 1, wherein processing the plurality of segments, in parallel, by the respective first processing elements comprises processing the plurality of segments by the cores.

7. The method of claim 1, further comprising performing a data backup or archiving operation that includes the dividing, processing, and using tasks.

8. The method of claim 1, wherein each of at least some of the chunks includes a respective partition of the input data defined by chunk boundaries corresponding to positions of a respective pair of the landmarks.

9. A system comprising:

a plurality of processing elements, wherein the processing elements include corresponding processors or cores of at least one processor; and

landmark locating software instances executable on a subset of the plurality of processing elements to;

process, in parallel, corresponding segments of input data to find landmarks in the corresponding segments, wherein finding the landmarks comprises;

computing a fingerprint on corresponding local content of the input data, wherein the corresponding local content is defined by a sliding window, and

designating a position associated with the corresponding local content as a landmark if the corresponding computed fingerprint satisfies a criterion, and

generate an output identifying the landmarks;

at least one chunking software instance executable on at least another one of the plurality of processing elements to;

divide the input data into chunks based on the output identifying the landmarks.

10. The system of claim 9, wherein the output identifying the landmarks includes a plurality of landmark lists generated by respective landmark locating software instances, and wherein each of the landmark lists identifies respective landmarks.

11. The system of claim 9, wherein the segments of the input data are interleaved with respect to each other.

12. The system of claim 9, wherein the at least one chunking software instance is to derive chunk boundaries of the chunks based on the identified landmarks.

13. The system of claim 9, further comprising a network interface to receive the input data from multiple computers over a network, wherein the system is to perform backup copying or archiving of the input data.

14. The system of claim 9, wherein chunk boundaries defining respective ones of the chunks are derived from the landmarks in which preset minimum and maximum chunk sizes are considered.

15. The system of claim 9, wherein each of at least some of the chunks includes a respective partition of the input data defined by chunk boundaries corresponding to positions of a respective pair of the landmarks.

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

process a plurality of segments of input data, in parallel, by respective first processing elements to locate landmarks in the segments, wherein locating the landmarks comprises;

computing a fingerprint on corresponding local content of the input data, wherein the corresponding local content are defined by a sliding window,

designating a position associated with the corresponding local content as a landmark if the corresponding computed fingerprint satisfies a criterion; and

use at least one other processing element to produce chunks from the input data based on output of the first processing elements.

17. The article of claim 16, wherein the instructions when executed cause the computer to further derive chunk boundaries using the landmarks in which preset minimum and maximum chunk sizes are considered, the chunk boundaries defining the chunks.

18. The article of claim 16, wherein the instructions when executed cause the computer to further perform a data backup or archiving operation that includes the processing and using tasks.

19. The article of claim 16, wherein each of at least some of the chunks includes a respective partition of the input data defined by chunk boundaries corresponding to positions of a respective pair of the landmarks.