Method and system for incrementally improving a program layout

• US 6,381,740 B1
• Filed: 09/16/1997
• Issued: 04/30/2002
• Est. Priority Date: 09/16/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Miller, John W., Douceur, John R., Fitzgerald, Robert P.
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): Opie, George L
• Application Number:
  US08/931,151
• Time in Patent Office: 1,687 Days
• Field of Search: 395/670, 395/709, 364/513, 709/300, 717/4, 717/5, 717/8, 717/9, 716/8, 716/9, 716/12, 702/182, 700/28
• US Class Current: 717/151
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836

Abstract

A method and system for incrementally improving the layout of a program image of a computer program to reduce the working set. The system iteratively selects pairs of basic blocks and reorders the basic blocks in the range delimited by the selected pair of basic blocks. The system selects the pairs of basic blocks so that the working set of the computer program is improved by reordering the basic block in the range. Thus, during each iteration, the working set is improved. The system continues with these iterations until a termination condition (e.g., number of iterations) is satisfied. In one embodiment, during each iteration the system designates one of the basic blocks as an initial anchor basic block. The system then repeats the following until the same range of basic blocks is identified twice in a row. The system first finds a basic block such that when the basic blocks in the range from the anchor basic block to the found basic block are reordered, the working set is more favorable than reordering any other range that ends with the anchor basic block. The system then designates the found basic block as the new anchor basic block. When the same range is found twice in a row, the system reorders the basic blocks in the range. This process is repeated for each iteration until a termination condition is satisfied. The resulting reordered program image has its working set improved.

Claims

1. A method in a computer system for incrementally improving the layout of a program image of a computer program to reduce the working set, the program image having basic blocks, each basic block having a temporal usage vector indicating time intervals during which the basic block is accessed, the method comprising:

repeating the following until a termination condition is satisfied,

designating one of the basic blocks as an initial anchor basic block;

repeating the following until the same range of basic blocks is identified twice in a row,

finding a basic block such that when the basic blocks in the range from the anchor basic block to the found basic block are reordered, the working set is reduced, wherein the act of finding includes finding the basic block with a desired metric value that is calculated from a permutation type and further wherein the anchor basic block and at least two found basic blocks in the repetition delimit ranges having different sizes selected from a group consisting of reflect and swap; and

designating the found basic block as the new anchor basic block; and

reordering the basic blocks in the range of basic blocks that has been identified twice in a row.

2. The method of claim 1 wherein the designating of one of the basic blocks as an initial anchor basic block includes randomly generating pairs of basic blocks, selecting the pair of basic blocks such that when the basic blocks delimited by the pair of basic blocks are reordered, the working set of the computer program is smaller than the working set resulting from reordering of the basic blocks delimited by another generated pair of basic blocks, and designating one of the basic blocks of the selected pair as the initial anchor basic block.

3. The method of claim 1 wherein the effect on the working set of reordering the basic blocks is indicated by a space-time product metric function.

4. The method of claim 3 wherein the space-time product metric function is a weighted space-time product metric function.

5. The method of claim 1 wherein the reordering of the basic blocks in a range is the swapping of the position of the basic blocks that delimit the range.

6. The method of claim 1 wherein the reordering of the basic blocks in a range is the reflecting of the position of the basic blocks in the range.

7. The method of claim 1 including calculating an estimated size for each basic block by calculating the actual size for each basic block based on the current layout of the program image.

8. The method of claim 7 wherein the actual size of each basic block is calculated by invoking a linker.

9. The method of claim 7 wherein the calculating of the estimated size is perform only once.

10. The method of claim 7 wherein the calculating of the estimated size is performed at a frequency that reduces when no estimated size of a basic block changes.

11. The method of claim 1 wherein the termination condition is a predefined number of repetitions.

12. The method of claim 1 wherein the termination conditions is expiration of predefined time period.

13. The method of claim 1 wherein the termination condition is a predefined evaluation of the program layout.

14. The method of claim 1 wherein the termination condition is based on the rate of improvement of the working set.

15. The method of claim 1 wherein the finding of the basic block finds the basic block such that when the basic blocks in the range are reordered the working set is smaller than the working set that would result from reordering of a range delimited by any other basic block.

16. The method of claim 1 wherein the effect on the working set of reordering the basic blocks takes into consideration the alignment constraints of the basic blocks.

17. The method of claim 1 wherein the temporal usage vectors are coalesced when the usage for each basic block is the same for multiple bit positions.

18. The method of claim 17 wherein the coalescing is performed only if the bit positions are adjacent.

19. The method of claim 1 wherein the finding of a basic block searches increasingly smaller distances between basic blocks based on the distance between previous anchor basic blocks and found basic blocks.

20. The method of claim 1 wherein the effect on the working set of basic blocks on pages before the page that contains the range delimited by the anchor basic block and another basic block are not recalculated.

21. The method of claim 1 wherein the effect on the working set of basic blocks on pages after the page that contains the range delimited by the anchor basic block and another basic block are only recalculated if an improvement is found in the delimited range.

22. The method of claim 1 wherein the effect on the working set for each possible temporal usage patterns of a group of time intervals is pre-calculated.

23. The method of claim 1 wherein the effect on the working set for each possible temporal usage pattern of the group is represented by a state machine table that indicates how to combine effects of temporal usage patterns of previous time intervals.

53. The method of claim 1, wherein the permutation type is selected from a group including reflect and swap.

24. A method in a computer system for identifying basic blocks of a program image of a computer program that, when reordered from an initial order, will reduce the working set of the computer program, the method comprising:

selecting an anchor basic block;

evaluating the effect on the working set of reordering the basic blocks in a plurality of ranges of basic blocks that are delimited at one end by the selected anchor basic block, wherein at least two ranges in the plurality of ranges are of different sizes;

selecting the range of basic blocks whose reordering would have an effect on the working set that is estimated to be more favorable than the other ranges;

selecting as the next anchor basic block the basic block at the other end of the range from the anchor basic block; and

repeating the evaluating and selecting until the same range is selected twice in a row whereby the range that is selected twice in a row is the identified range.

25. A method in a computer system for improving the organization of ordered data, the method comprising:

selecting an anchor position within the data;

for each of a plurality of end positions within the data, rating a reorganization of the data between the anchor position and the end position, wherein the act of rating includes rating with a desired metric value that is calculated from a permutation type and further wherein the anchor position and at least two end positions in the plurality of end positions delimit subranges of data having different sizes selected from a group consisting of reflect and swap;

selecting as a new anchor position the end position of the data whose reorganization has the highest rating;

repeating the rating and selecting of a new anchor position until the selected end position is the same as the previous anchor position; and

permuting the data between the anchor position and the end position, thus reordering the data.

26. The method of claim 25 wherein the data represents data objects.

27. The method of claim 26 wherein the reorganization includes permuting the data objects.

28. The method of claim 26 wherein the reorganization includes coalescing two data objects into a single data object.

29. The method of claim 26 wherein the reorganization includes splitting a data object into two data objects.

30. The method of claim 26 wherein the data objects are basic blocks of a program image.

31. The method of claim 30 wherein the reorganization includes coalescing two data objects into a single data object.

32. The method of claim 30 wherein the reorganization includes splitting a data object into two data objects.

33. The method of claim 26 wherein the rating rates the effect of the reorganization on paging.

34. The method of claim 26 wherein the rating rates the effect of the reorganization on caching.

54. The method of claim 25, wherein the permutation type is selected from a group including reflect and swap.

35. A computer-readable medium containing instructions for causing a computer system to identify basic blocks of a program image of a computer program that, when reordered from an initial order, will reduce the working set of the computer program, by:

selecting an anchor basic block;

evaluating the effect on the working set of reordering the basic blocks in a plurality of ranges of basic blocks that are delimited at one end by the selected anchor basic block, wherein at least two ranges in the plurality of ranges are of different sizes;

selecting the range of basic blocks whose reordering would have an effect on the working set that is estimated to be more favorable than the other ranges;

selecting as the next anchor basic block the basic block at the other end of the range from the anchor basic block; and

repeating the evaluating and selecting until the same range is selected twice in a row whereby the range that is selected twice in a row in the identified range.

36. A computer system for improving the working set of a computer program, the computer program having code portions arranged in a first order, comprising:

a selection component that selects two code portions such that if the code portions delimited by the two code portions in the first order are permuted by a predefined permutation algorithm then the working set of the computer program is improved; and

a permutation component that permutes the code portions delimited by the two selected code portions in accordance with the predefined permutation algorithm to arrange the code portions of the computer program in a second order distinct from the first order.

37. A computer-readable medium containing instructions for causing a computer system to improve the organization of ordered data objects, by:

selecting an anchor data object;

for each of a plurality of end data objects,

rating a reorganization of the data objects between the anchor data object and the end data object, wherein the act of rating includes rating with a desired metric value that is calculated from a permutation type and further wherein the anchor data object and at least two end data objects in the plurality of end data objects delimit subranges of data objects having different sizes selected from a group consisting of reflect and swap;

selecting as a new anchor data object the end data object whose reorganization has the highest rating;

repeating the rating and selecting of a new anchor data object until the selected end data object is the same as the previous anchor data object; and

permuting the data between the anchor position and the end position, thus reordering the data.

38. The computer-readable medium of claim 37 wherein the reorganization includes permuting the data objects.

39. The computer-readable medium of claim 37 wherein the reorganization includes coalescing two data objects into a single data object.

40. The computer-readable medium of claim 37 wherein the reorganization includes splitting a data object into two data objects.

41. The computer-readable medium of claim 37 wherein the data objects are basic blocks of a program image.

42. The computer-readable medium of claim 41 wherein the reorganization includes coalescing two data objects into a single data object.

43. The computer-readable medium of claim 41 wherein the reorganization includes splitting a data object into two data objects.

44. The computer-readable medium of claim 37 wherein the rating rates the effect of the reorganization on paging.

45. The computer-readable medium of claim 37 wherein the rating rates the effect of the reorganization on caching.

55. The method of claim 37, wherein the permutation type is selected from a group including reflect and swap.

46. A computer-readable medium containing instructions for causing a computer system to incrementally improve the layout of a program image of a computer program to reduce the working set, the program image having basic blocks, each basic block having a temporal usage vector indicating time intervals during which the basic block is accessed, by:

repeating the following until a termination condition is satisfied,

designating one of the basic blocks as an initial anchor basic block;

repeating the following until the same range of basic blocks is identified twice in a row,

finding a basic block such that when the basic blocks in the range from the anchor basic block to the found basic block are reordered, the working set is reduced, wherein the act of finding includes finding the basic block with a desired metric value that is calculated from a permutation type and further wherein the anchor basic block and at least two found basic blocks in the repetition delimit ranges having different sizes selected from a group consisting of reflect and swap; and

designating the found basic block as the new anchor basic block; and

reordering the basic blocks in the range of basic blocks that has been identified twice in a row.

47. The computer-readable medium of claim 46 wherein the designating of one of the basic blocks as an initial anchor basic block includes randomly generating pairs of basic blocks, selecting the pair of basic blocks such that when the basic blocks delimited by the pair of basic blocks are reordered, the working set of the computer program is smaller than the working set resulting from reordering of the basic blocks delimited by another generated pair of basic blocks, and designating one of the basic blocks of the selected pair as the initial anchor basic block.

48. The computer-readable medium of claim 46 wherein the effect on the working set of reordering the basic blocks is indicated by a space-time product metric function.

49. The computer-readable medium of claim 48 wherein the space-time product metric function is a weighted space-time product metric function.

50. The computer-readable medium of claim 46 wherein the reordering of the basic blocks in a range is the swapping of the data position of the basic blocks that delimit the range.

51. The computer-readable medium of claim 46 wherein the reordering of the basic blocks in a range is the reflecting of the data position of the basic blocks in the range.

52. The computer-readable medium of claim 46 including calculating an estimated size for each basic block by calculating the actual size for each basic block based on the current layout of the program image.

56. The method of claim 46, wherein the permutation type is selected from a group including reflect and swap.