Optimized pre-fetch ordering using de-duplication information to enhance network performance

• US 9,471,582 B2
• Filed: 04/04/2013
• Issued: 10/18/2016
• Est. Priority Date: 04/04/2013
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gunda, Kalyan C., Jain, Mukti, Patil, Sandeep R., Shiraguppi, Riyazahamad M.
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): DAYE, CHELCIE L
• Application Number:
  US13/856,478
• Publication Number:
  US 20140304268A1
• Time in Patent Office: 1,293 Days
• Field of Search: 707/738, 707/692
• US Class Current: 1/1
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files

Abstract

A computer determines a degree of information duplication between at least two files included in an original pre-fetch list. The computer generates a re-ordered pre-fetch list by re-ordering the files included in the original pre-fetch list. The re-ordering is based, at least in part, on the degree of information duplication between the two files included in the original pre-fetch list. The files included in the original pre-fetch list are re-ordered by grouping files containing higher degrees of duplicate information closer together in the re-ordered pre-fetch list.

Claims

1. A method of optimizing an order of a pre-fetch list, the method comprising:

a computer determining a degree of information duplication between at least two files included in an original pre-fetch list;

the computer generating a re-ordered pre-fetch list by re-ordering the files included in the original pre-fetch list based, at least in part, on the degree of information duplication between the two files included in the original pre-fetch list, wherein the files included in the original pre-fetch list are re-ordered by grouping files containing higher degrees of duplicate information closer together in the re-ordered pre-fetch list;

the computer generating a weighted graph, wherein a node of the weighted graph is associated with a file included in the original pre-fetch list;

the computer connecting two or more nodes with a weighted edge wherein the weighted edge represents the degree of information duplication between two files respectively associated with the nodes;

the computer determining a weight for each sub-tree included in the weighted graph, wherein the weight for each sub-tree is based, at least in part, on a sum of weighted edges included in the sub-tree;

the computer generating an ordered sub list of nodes included in the sub-tree, wherein the ordered sub list of nodes is based, at least in part on, the weight of at least one edge associate with a given node; and

the computer generating a new pre-fetch list based, at least in part, on one or more sub-lists, wherein the sub-lists are added to the new pre-fetch list based on their associated sub-tree weights.

2. The method of claim 1, the method further including:

the computer determining a degree of separation between at least two files included in the original pre-fetch list that represents a number of files separating two given files included in the original pre-fetch list; and

the computer generating a re-ordered pre-fetch list by re-ordering the files included in the original pre-fetch list based, at least in part, on the degree of separation between the two files included in the original pre-fetch list.

3. The method of claim 1, the method further including:

the computer creating a virtual block list for at least one file included in the original pre-fetch list; and

the computer comparing the virtual block list of two or more files included in the original pre-fetch list.

4. The method of claim 1, the method further including:

the computer generating a list of unique physical blocks included in the two or more files included in the original pre-fetch list.

5. The method of claim 3, the method including:

the computer analyzing the virtual block list to identify one or more nodes to be included in a weighted graph.

6. A computer program product for optimizing an order of a pre-fetch list, the computer program product comprising:

one or more computer-readable storage-medium and program instructions stored on the one or more computer-readable storage medium, the program instructions comprising;

program instructions to determine a degree of information duplication between at least two files included in an original pre-fetch list;

program instructions to generate a re-ordered pre-fetch list by re-ordering the files included in the original pre-fetch list based, at least in part, on the degree of information duplication between the two files included in the original pre-fetch list, wherein the files included in the original pre-fetch list are re-ordered by grouping files containing higher degrees of duplicate information closer together in the re-ordered pre-fetch list;

program instructions to generate a weighted graph, wherein a node of the weighted graph is associated with a file included in the original pre-fetch list;

program instructions to connect two or more nodes with a weighted edge wherein the weighted edge represents the degree of information duplication between two files respectively associated with the nodes;

program instructions to determine a weight for each sub-tree included in the weighted graph, wherein the weight for each sub-tree is based, at least in part, on a sum of weighted edges included in the sub-tree;

program instructions to generate an ordered sub list of nodes included in the sub-tree, wherein the ordered sub list of nodes is based, at least in part on, the weight of at least one edge associate with a given node; and

program instructions to generate a new pre-fetch list based, at least in part, on one or more sub-lists, wherein the sub-lists are added to the new pre-fetch list based on their associated sub-tree weights.

7. The computer program product of claim 6, the program instructions further including:

program instructions to determine a degree of separation between at least two files included in the original pre-fetch list that represents a number of files separating two given files included in the original pre-fetch list; and

program instructions to generate a re-ordered pre-fetch list by re-ordering the files included in the original pre-fetch list based, at least in part, on the degree of separation between the two files included in the original pre-fetch list.

8. The computer program product of claim 6, the program instructions further including:

program instructions to create a virtual block list for at least one file included in the original pre-fetch list; and

program instructions to compare the virtual block list of two or more files included in the original pre-fetch list.

9. The computer program product of claim 6, the program instructions further including:

program instructions to generate a list of unique physical blocks included in the two or more files included in the original pre-fetch list.

10. The computer program product of claim 8, the program instructions further including:

program instructions to analyze the virtual block list to identify one or more nodes to be included in a weighted graph.

11. A computer system for optimizing an order of a pre-fetch list, the computer system comprising:

one or more computer processors;

one or more computer readable storage medium;

program instructions stored on the computer readable storage medium for execution by at least one of the one or more processors, the program instructions comprising;

program instructions to determine a degree of information duplication between at least two files included in an original pre-fetch list;

program instructions to generate a re-ordered pre-fetch list by re-ordering the files included in the original pre-fetch list based, at least in part, on the degree of information duplication between the two files included in the original pre-fetch list, wherein the files included in the original pre-fetch list are re-ordered by grouping files containing higher degrees of duplicate information closer together in the re-ordered pre-fetch list;

program instructions to generate a weighted graph, wherein a node of the weighted graph is associated with a file included in the original pre-fetch list;

program instructions to connect two or more nodes with a weighted edge wherein the weighted edge represents the degree of information duplication between two files respectively associated with the nodes;

program instructions to determine a weight for each sub-tree included in the weighted graph, wherein the weight for each sub-tree is based, at least in part, on a sum of weighted edges included in the sub-tree;

program instructions to generate an ordered sub list of nodes included in the sub-tree, wherein the ordered sub list of nodes is based, at least in part on, the weight of at least one edge associate with a given node; and

program instructions to generate a new pre-fetch list based, at least in part, on one or more sub-lists, wherein the sub-lists are added to the new pre-fetch list based on their associated sub-tree weights.

12. The computer system of claim 11, the program instructions further including:

program instructions to determine a degree of separation between at least two files included in the original pre-fetch list that represents a number of files separating two given files included in the original pre-fetch list; and

program instructions to generate a re-ordered pre-fetch list by re-ordering the files included in the original pre-fetch list based, at least in part, on the degree of separation between the two files included in the original pre-fetch list.

13. The computer system of claim 11, the program instructions further including:

program instructions to create a virtual block list for at least one file included in the original pre-fetch list;

program instructions to compare the virtual block list of two or more files included in the original pre-fetch list, and

program instructions to generate a list of unique physical blocks included in the two or more files included in the original pre-fetch list.

14. The computer system of claim 13, the program instructions further including:

program instructions to analyze the virtual block list to identify one or more nodes to be included in a weighted graph.