PARALLEL PROCESSING OF INPUT DATA TO LOCATE LANDMARKS FOR CHUNKS

• US 20100235485A1
• Filed: 03/16/2009
• Published: 09/16/2010
• 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
• Granted Patent: US 8,001,273 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• 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 executed by a computer, 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; 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 creating 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 locating the landmarks comprises applying a function on corresponding local content of the input data, wherein the corresponding local content is defined by a sliding window.

6. The method of claim 5, wherein applying the function comprises computing a fingerprint.

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

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

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

10. A system comprising:

a plurality of processing elements; 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, 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.

11. The system of claim 10, 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.

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

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

14. The system of claim 10, 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.

15. The system of claim 10, wherein chunk boundaries are derived from the landmarks in which preset minimum and maximum chunk sizes are considered.

16. The system of claim 10, wherein the landmarks are located by applying a function on corresponding local content of the input data, wherein the corresponding local content are defined by a sliding window.

17. The system of claim 16, wherein the applied function comprises a fingerprint.

18. An article comprising at least one 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 applying a function on corresponding local content of the input data, wherein the corresponding local content are defined by a sliding window; and

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

19. The article of claim 18, further deriving chunk boundaries using the landmarks in which preset minimum and maximum chunk sizes are considered.

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