×

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
First Claim
Patent Images

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.

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×