OPTIMIZED PRE-FETCH ORDERING USING DE-DUPLICATION INFORMATION TO ENHANCE NETWORK PERFORMANCE

• US 20140304268A1
• Filed: 04/04/2013
• Published: 10/09/2014
• Est. Priority Date: 04/04/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gunda, Kalyan C., Patil, Sandeep R., Shiraguppi, Riyazahamad M., Jain, Mukti
• Granted Patent: US 9,471,582 B2
• Time in Patent Office: Days
• US Class Current: 707/738
• 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; 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 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.

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 generating a weighted graph, wherein a node of the weighted graph is associated with a file included in the original pre-fetch list; and

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.

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

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.

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

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

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

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

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

one or more computer-readable storage media and program instructions stored on the one or more computer-readable storage media, 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; 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 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.

9. The computer program product of claim 8, 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.

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

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; and

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.

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

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 program product of claim 8, 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.

13. The computer program product of claim 8, 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.

14. The computer program product of claim 12, 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.

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

program instructions to determine a degree of information duplication between at least two files included in an 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 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.

16. The computer system of claim 15, 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.

17. The computer system of claim 15, the program instructions further including:

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; and

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.

18. The computer system of claim 17, the program instructions further including:

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.

19. The computer system of claim 15, 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.

20. The computer system of claim 19, 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.