Temporal affinity analysis using reuse signatures

• US 7,356,805 B2
• Filed: 01/02/2004
• Issued: 04/08/2008
• Est. Priority Date: 01/02/2003
• Status: Expired due to Fees

• Current Assignee: University of Rochester
• Original Assignee: University of Rochester
• Inventors: Zhong, Yutao, Ding, Chen
• Primary Examiner(s): Dam; Tuan
• Assistant Examiner(s): RUTTEN, JAMES D
• Application Number:
  US10/750,552
• Publication Number:
  US 20040260517A1
• Time in Patent Office: 1,558 Days
• Field of Search: 717/130, 717/131, 717/128, 717/154, 711/159
• US Class Current: 717/128
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2201/885 Monitoring specific for caches
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862

Abstract

Reuse distance is the number of data which are accessed between accesses of a datum. The computation of reuse distance uses a search tree and is carried out through approximate analysis, pattern recognition, or distance-based sampling. The reuse distance can be used to detect reference affinity, that is, to detect which data are accessed together.

Claims

1. A method for analyzing reuse patterns of accesses of data by a program naming on a computing device, the computing device having a memory in which the data are stored and from which the data are accessed, the method comprising:

(a) running the program on the computing device;

(b) monitoring the accesses of the data by the program during step (a); and

(c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein step (c) comprises;

determining a last access time of each of the data;

organizing a search tree from the last accesses, wherein the search tree comprises a node for each of the data, the node comprising the last access time and a weight of a sub-tree of the node; and

compressing the search tree in accordance with a bounded relative error.

2. The method of claim 1, wherein the search tree is compressed by (i) determining a capacity of each node in accordance with the reuse distance and the bounded relative error and (ii) merging adjacent ones of the nodes in accordance with the capacities of the nodes.

3. A method for analyzing reuse patterns of accesses of data by a program running on a computing device, the computing device having a memory in which the data are stored and from which the data are accessed, the method comprising:

(a) running the program on the computing device;

(b) monitoring the accesses of the data by the program during step (a); and

(c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein step (c) comprises;

determining a last access time of each of the data;

maintaining a trace storing the last access times of the last C accesses of the data, where C is a cut-off distance; and

maintaining a search tree storing access times other than the last C accesses, each node in the search wee having a capacity B, where B is a bounded absolute error.

4. A method for analyzing reuse patterns of accesses of data by a program running on a computing device, the computing device having a memory in which the data are stored and from which the data are accessed, the method comprising:

(a) running the program on the computing device;

(b) monitoring the accesses of the data by the program during step (a);

(c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein step (c) comprises;

determining a last access time of each of the data;

maintaining a trace storing the last access times of the last C accesses of the data, where C is a cut-off distance; and

maintaining a search tree storing access times other than the last C accesses, each node in the search tree having a capacity B, where B is a bounded absolute error; and

(d) determining a reuse pattern from the reuse distances determined in step (c), wherein step (d) comprises forming a reuse distance histogram of the reuse distances by absolute ranges of the reuse distances, and wherein step (d) further comprises forming a reference histogram of the reuse distances by percentile ranges of the reuse distances.

5. The method of claim 4, wherein the reference histogram is formed for a plurality of training inputs.

6. The method of claim 5, wherein step (d) further comprises using the reference histograms for the plurality of training inputs to map data size to the reuse distance.

7. The method of claim 6, wherein the data size is mapped to the reuse distance through linear fitting.

8. A method for analyzing reuse patterns of accesses of data by a program running on a computing device, the computing device having a memory in which the data are stored and from which the data are accessed, the method comprising:

(a) running the program on the computing device;

(b) monitoring the accesses of the data by the program during step (a);

(c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein step (c) comprises;

determining a last access time of each of the data;

maintaining a trace storing the last access times of the last C accesses of the data, where C is a cut-off distance; and

maintaining a search tree storing access times other than the last C accesses, each node in the search tree having a capacity B, where B is a bounded absolute error;

(d) determining a reuse pattern from the reuse distances determined in step (c), wherein step (d) comprises forming a reuse distance histogram of the reuse distances by absolute ranges of the reuse distances; and

(e) from the reuse distance histogram, forming an affinity group of at least two data which are always accessed within a distance k of one another, wherein k is a predetermined quantity.

9. The method of claim 8, wherein step (e) comprises selecting the data in the affinity group such that the data in the affinity group have average reuse distances which fulfill a necessary condition with respect to k.

10. The method of claim 9 wherein the necessary condition is that the average reuse distances differ by no more than k.

11. The method of claim 9, wherein:

the reuse distance histogram comprises B bins; and

the necessary condition is that differences between the average reuse distances, summed over all of the bins, do not exceed kB.

12. The method of claim 11, wherein step (e) comprises:

(i) initially treating each of the data as an affinity group;

(ii) traversing all of the affinity groups and merging any two affinity groups for which the necessary condition is met; and

(iii) performing step (e)(ii) until no more of the affinity groups can be merged.

13. The method of claim 8, wherein step (e) is performed a plurality of times for different values of k.

14. A method for analyzing reuse patterns of accesses of data by a program running on a computing device, the computing device having a memory in which the data are stored and from which the data are accessed, the method comprising:

(a) running the program on the computing device;

(b) monitoring the accesses of the data by the program during step (a);

(c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein step (c) comprises;

determining a last access time of each of the data;

maintaining a trace storing the last access times of the last C accesses of the data, where C is a cut-off distance; and

maintaining a search tree storing access times other than the last C accesses, each node in the search tree having a capacity B, where B is a bounded absolute error;

(d) comparing reuse signatures of the data to determine whether two or more of the data have reuse signatures which differ by less than a predetermined percentage; and

(e) for any two or more of the data whose reuse signatures differ by less than said predetermined percentage, identifying a reference affinity among said two or more data.

15. A computing device capable of analyzing reuse patterns of accesses of data by a program running on a computing device, the computing device comprising:

a memory in which the data are stored and from which the data are accessed; and

a processor, in communication with the memory, for;

(a) running the program on the computing device;

(b) monitoring the accesses of the data by the program during step (a); and

(c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein the processor performs step (c) by;

determining a last access time of each of the data;

organizing a search free from the last accesses, wherein the search tree comprises a node for each of the data, the node comprising the last access time and a weight of a sub-tree of the node; and

compressing the search tree in accordance with a bounded relative error.

16. The computing device of claim 15, wherein the search tree is compressed by (i) determining a capacity of each node in accordance with the reuse distance and the bounded relative error and (ii) merging adjacent ones of the nodes in accordance with the capacities of the nodes.

17. A computing device capable of analyzing reuse patterns of accesses of data by a program running on a computing device, the computing device comprising:

a memory in which the data are stored and from which the data are accessed; and

a processor, in communication with the memory, for;

(a) running the program on the computing device;

(b) monitoring the accesses of the data by the program during step (a); and

(c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein the processor performs step (c) by;

maintaining a trace storing the last access times of the last C accesses of the data, where C is a cut-off distance; and

maintaining a search tree storing access times other than the last C accesses, each node in the search free having a capacity B, where B is a bounded absolute error.

18. A computing device capable of analyzing reuse patterns of accesses of data by a program running on a computing device, the computing device comprising:

a memory in which the data are stored and from which the data are accessed; and

a processor, in communication with the memory, for;

(a) running the program on the computing device;

(b) monitoring the accesses of the data by the program during step (a);

(c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein step (c) comprises;

determining a last access time of each of the data;

maintaining a trace storing the last access times of the last C accesses of the data, where C is a cut-off distance; and

maintaining a search tree storing access times other than the last C accesses, each node in the search free having a capacity B, where B is a bounded absolute error; and

(d) determining a reuse pattern from the reuse distances determined in step (c), wherein the processor performs step (d) by forming a reuse distance histogram of the reuse distances by absolute ranges of the reuse distances, and wherein the processor further performs step (d) by forming a reference histogram of the reuse distances by percentile ranges of the reuse distances.

19. The computing device of claim 18, wherein the reference histogram is formed for a plurality of training inputs.

20. The computing device of claim 19, wherein the processor performs step (d) further by using the reference histograms for the plurality of training inputs to map data size to the reuse distance.

21. The computing device of claim 20, wherein the data size is mapped to the reuse distance through linear fitting.

22. A computing device capable of analyzing reuse patterns of accesses of data by a program running on a computing device, the computing device comprising:

a memory in which the data are stored and from which the data are accessed; and

a processor, in communication with the memory, for;

(a) running the program on the computing device;

(b) monitoring the accesses of the data by the program during step (a);

(c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein step (c) comprises;

determining a last access time of each of the data;

maintaining a trace storing the last access times of the last C accesses of the data, where C is a cut-off distance; and

maintaining a search tree storing access times other than the last C accesses, each node in the search tree having a capacity B, where B is a bounded absolute error;

(d) determining a reuse pattern from the reuse distances determined in step (c), wherein the processor performs step (d) by forming a reuse distance histogram of the reuse distances by absolute ranges of the reuse distances, and

(e) from the reuse distance histogram, forming an affinity group of at least two data which are always accessed within a distance k of one another, wherein k is a predetermined quantity.

23. The computing device of claim 22, wherein the processor performs step (e) by selecting the data in the affinity group such that the data in the affinity group have average reuse distances which fulfill a necessary condition with respect to k.

24. The computing device of claim 23, wherein the necessary condition is that the average reuse distances differ by no more than k.

25. The computing device of claim 23, wherein:

the reuse distance histogram comprises B bins; and

the necessary condition is that differences between the average reuse distances, summed over all of the bins, do not exceed kB.

26. The computing device of claim 25, wherein the processor performs step (e) by:

(i) initially treating each of the data as an affinity group;

(ii) traversing all of the affinity groups and merging any two affinity groups for which the necessary condition is met; and

(iii) performing step (e)(ii) until no more of the affinity groups can be merged.

27. The computing device of claim 26, wherein step (e) is performed a plurality of times for different values of k.

28. A computing device capable of analyzing reuse patterns of accesses of data by a program running on a computing device, the computing device comprising:

a memory in which the data are stored and from which the data are accessed; and

a processor, in communication with the memory, for;

(a) running the program on the computing device;

(b) monitoring the accesses of the data by the program during step (a);

(c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein step (c) comprises;

determining a last access time of each of the data;

maintaining a trace storing the last access times of the last C accesses of the data, where C is a cut-off distance; and

maintaining a search tree storing access times other than the last C accesses, each node in the search tree having a capacity B, where B is a bounded absolute error;

(d) comparing reuse signatures of the data to determine whether two or more of the data have reuse signatures which differ by less than a predetermined percentage; and

(e) for any two or more of the data whose reuse signatures differ by less than said predetermined percentage, identifying a reference affinity among said two or more data.

29. A method for analyzing affinities among a plurality of events, the method comprising:

(a) monitoring occurrences of the events;

(b) determining a reoccurrence distance for each event, the reoccurrence distance being a number of distinct ones of the plurality of events which occur between two occurrences of said each event, wherein step (b) comprises;

determining a last occurrence of each of the events;

maintaining a trace storing the last occurrences of the last C events, where C is a cut-off distance; and

maintaining a search tree storing occurrences other than the last C occurrences, each node in the search tree having a capacity B, where B is a bounded absolute error; and

(c) determining, from the reoccurrence distance determined in step (b), an affinity among at least two of the events, the affinity being a tendency of said at least two of the events to occur together.

30. The method of claim 29, wherein step (c) comprises determining the affinity such that said events always occur within a distance k of each other, wherein k is a predetermined quantity and the distance is a number of distinct events occurring between occurrences of said at least two of the events.

31. The method of claim 29, wherein step (c) comprises comparing reoccurrence signatures of the events to determine whether said two or more of the events have reoccurrence signatures which differ by less than a predetermined percentage.

32. A method for analyzing reuse patterns of accesses of data by a program running on a computing device, the computing device having a memory in which the data are stored and from which the data are accessed, the method comprising:

(a) running the program on the computing device;

(b) monitoring the accesses of the data by the program during step (a);

(c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein step (c) comprises;

determining a last access time of each of the data;

organizing a search free from the last accesses, wherein the search tree comprises a node for each of the data, the node comprising the last access time and a weight of a sub-tree of the node; and

compressing the search tree in accordance with a bounded relative error; and

(d) determining a reuse pattern from the reuse distances determined in step (c), wherein step (d) comprises forming a reuse distance histogram of the reuse distances by absolute ranges of the reuse distances, and wherein step (d) further comprises forming a reference histogram of the reuse distances by percentile ranges of the reuse distances.

33. The method of claim 32, wherein the reference histogram is formed for a plurality of training inputs.

34. The method of claim 33, wherein step (d) further comprises using the reference histograms for the plurality of training inputs to map data size to the reuse distance.

35. The method of claim 34, wherein the data size is mapped to the reuse distance through linear fitting.

36. A method for analyzing reuse patterns of accesses of data by a program running on a computing device, the computing device having a memory in which the data are stored and from which the data are accessed, the method comprising:

(a) running the program on the computing device;

(b) monitoring the accesses of the data by the program during step (a);

(c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein step (c) comprises;

determining a last access time of each of the data;

organizing a search free from the last accesses, wherein the search tree comprises a node for each of the data, the node comprising the last access time and a weight of a sub-tree of the node; and

compressing the search tree in accordance with a bounded relative error;

(d) determining a reuse pattern from the reuse distances determining in step (c), wherein step (d) comprises forming a reuse distance histogram of the reuse distances by absolute ranges of the reuse distances; and

(e) from the reuse distance histogram, forming an affinity group of at least two data which are always accessed within a distance k of one another, wherein k is a predetermined quantity.

37. The method of claim 36, wherein step (e) comprises selecting the data in the affinity group such that the data in the affinity group have average reuse distances which fulfill a necessary condition with respect to k.

38. The method of claim 37, wherein the necessary condition is that the average reuse distances differ by no more than k.

39. The method of claim 37, wherein:

the reuse distance histogram comprises B bins; and

the necessary condition is that differences between the average reuse distances, summed over all of the bins, do not exceed kB.

40. The method of claim 39, wherein step (e) comprises:

(i) initially treating each of the data as an affinity group;

(ii) traversing all of the affinity groups and merging any two affinity groups for which the necessary condition is met; and

(iii) performing step (e)(ii) until no more of the affinity groups can be merged.

41. The method of claim 36, wherein step (e) is performed a plurality of times for different values of k.

42. A method for analyzing reuse patterns of accesses of data by a program running on a computing device, the computing device having a memory in which the data are stored and from which the data are accessed, the method comprising:

(a) running the program on the computing device;

(b) monitoring the accesses of the data by the program during step (a);

(c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein step (c) comprises;

determining a last access time of each of the data;

organizing a search tree from the last accesses, wherein the search tree comprises a node for each of the data, the node comprising the last access time and a weight of a sub-tree of the node; and

compressing the search tree in accordance with a bounded relative error;

(d) comparing reuse signatures of the data to determine whether two or more of the data have reuse signatures which differ by less than a predetermined percentage; and

(e) for any two or more of the data whose reuse signatures differ by less than said predetermined percentage, identifying a reference affinity among said two or more data.

43. A computing device capable of analyzing reuse patterns of accesses of data by a program running on a computing device, the computing device comprising:

a memory in which the data are stored and from which the data are accessed; and

a processor, in communication with the memory, for;

(a) running the program on the computing device;

(b) monitoring the accesses of the data by the program during step (a);

(c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein step (c) comprises;

determining a last access time of each of the data;

organizing a search tree from the last accesses, wherein the search tree comprises a node for each of the data, the node comprising the last access time and a weight of a sub-tree of the node; and

compressing the search tree in accordance with a bounded relative error; and

(d) determining a reuse pattern from the reuse distances determined in step (c), wherein the processor performs step (d) by forming a reuse distance histogram of the reuse distances by absolute ranges of the reuse distances, and wherein the processor further performs step (d) by forming a reference histogram of the reuse distances by percentile ranges of the reuse distances.

44. The computing device of claim 43, wherein the reference histogram is formed for a plurality of training inputs.

45. The computing device of claim 44, wherein the processor performs step (d) further by using the reference histograms for the plurality of training inputs to map data size to the reuse distance.

46. The computing device of claim 45, wherein the data size is mapped to the reuse distance through linear fitting.

47. A computing device capable of analyzing reuse patterns of accesses of data by a program running on a computing device, the computing device comprising:

a memory in which the data are stored and from which the data are accessed; and

a processor, in communication with the memory, for;

(a) running the program on the computing device;

(b) monitoring the accesses of the data by the program during step (a);

(c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein step (c) comprises;

determining a last access time of each of the data;

organizing a search tree from the last accesses, wherein the search tree comprises a node for each of the data, the node comprising the last access time and a weight of a sub-tree of the node; and

compressing the search free in accordance with a bounded relative error;

(d) determining a reuse pattern from the reuse distances determined in step (c), wherein the processor performs step (d) by forming a reuse distance histogram of the reuse distances by absolute ranges of the reuse distances, and

(e) from the reuse distance histogram, forming an affinity group of at least two data which are always accessed within a distance k of one another, wherein k is a predetermined quantity.

48. The computing device of claim 47, wherein the processor performs step (e) by selecting the data in the affinity group such that the data in the affinity group have average reuse distances which fulfill a necessary condition with respect to k.

49. The computing device of claim 48, wherein the necessary condition is that the average reuse distances differ by no more than k.

50. The computing device of claim 48, wherein:

the reuse distance histogram comprises B bins; and

the necessary condition is that differences between the average reuse distances, summed over all of the bins, do not exceed kB.

51. The computing device of claim 50, wherein the processor performs step (e) by:

(i) initially treating each of the data as an affinity group;

(ii) traversing all of the affinity groups and merging any two affinity groups for which the necessary condition is met; and

(iii) performing step (e)(ii) until no more of the affinity groups can be merged.

52. The computing device of claim 51, wherein step (e) is performed a plurality of times for different values of k.

53. A computing device capable of analyzing reuse patterns of accesses of data by a program running on a computing device, the computing device comprising:

a memory in which the data are stored and from which the data are accessed; and

a processor, in communication with the memory, for;

(a) running the program on the computing device;

(b) monitoring the accesses of the data by the program during step (a);

(c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein step (c) comprises;

determining a last access time of each of the data;

organizing a search tree from the last accesses, wherein the search tree comprises a node for each of the data, the node comprising the last access time and a weight of a sub-tree of the node; and

compressing the search tree in accordance with a bounded relative error;

(d) comparing reuse signatures of the data to determine whether two or more of the data have reuse signatures which differ by less than a predetermined percentage; and

(e) for any two or more of the data whose reuse signatures differ by less than said predetermined percentage, identifying a reference affinity among said two or more data.

54. A method for analyzing affinities among a plurality of events, the method comprising:

(a) monitoring occurrences of the events;

(b) determining a reoccurrence distance for each event, the reoccurrence distance being a number of distinct ones of the plurality of events which occur between two occurrences of said each event, wherein step (b) comprises;

determining a last occurrence of each of the events;

organizing a search free from the last occurrences, wherein the search tree comprises a node for each of the events, the node comprising the last occurrence and a weight of a sub-tree of the node; and

compressing the search free in accordance with a bounded relative error; and

(c) determining, from the reoccurrence distance determined in step (b), an affinity among at least two of the events, the affinity being a tendency of said at least two of the events to occur together.

55. The method of claim 54, wherein step (c) comprises determining the affinity such that said events always occur within a distance k of each other, wherein It is a predetermined quantity and the distance is a number of distinct events occurring between occurrences of said at least two of the events.

56. The method of claim 54, wherein step (c) comprises comparing reoccurrence signatures of the events to determine whether said two or more of the events have reoccurrence signatures which differ by less than a predetermined percentage.