Memory architecture dependent program mapping

• US 5,963,972 A
• Filed: 02/24/1997
• Issued: 10/05/1999
• Est. Priority Date: 02/24/1997
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.), Northeastern University
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Calder, Bradley Gene, Kaeli, David Richard, Hashemi, Amir Hooshang
• Primary Examiner(s): Cabeca, John W.
• Assistant Examiner(s): GOODARZI, NASSER MOAZZAMI
• Application Number:
  US08/806,891
• Time in Patent Office: 953 Days
• Field of Search: 711/129, 711/133, 711/158, 711/118, 395/581, 395/800.1, 395/495
• US Class Current: 711/129
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862

Abstract

In a computer implemented method, instructions of a program are mapped into a cache memory of a computer system. The cache memory is partitioned into a plurality fixed size lines for the convenience of accessing the instructions. Each block is assigned a different identification, for example a unique color. The program is partitioned into a plurality of instruction units, for example procedures or basic blocks. A flow graph is generated for the program. In the graph, nodes represent the instructions units, and edges directly connect nodes that have an execution relationship. Instruction units of directly connected nodes are mapped into blocks having different identifications or colors. An unavailable-set of identifications is maintained for each node. The unavailability-set of a particular node includes the identifications of blocks mapping instruction units directly connected to the particular node and which should not be used for the particular procedure in order to minimize cache conflicts during execution of the program.

Claims

1. A computer implemented method for mapping instructions of a program into a cache memory of a computer system, the cache memory being partitioned into a plurality of sections, at least two of said sections each having a respective plurality of blocks for accessing the instructions, comprising the steps of:

assigning a respective identification to each block, each of said at least two sections having an identical number of said blocks, and corresponding blocks of said at least two sections having identical respective identifications;

partitioning the program into a plurality of instruction units;

generating a flow graph for the program, the flow graph including a node for each instructions unit, and an edge connecting two nodes that have an execution relationship;

mapping instruction units of directly connected nodes into blocks of said at least two sections that have different respective identifications; and

moving at least one instruction unit of a first node mapped in said cache memory to a portion of said cache memory that does not include any blocks having identifications of other blocks mapping at least one other instruction unit of a second node, said first and second nodes being directly connected.

2. The method of claim 1 further comprising:

maintaining an unavailable-set for each node, the unavailability-set of a particular node including the identifications of blocks mapping instruction units directly connected to the particular node.

3. The method of claim 1 further comprising:

assigning a weight to each edge, the weight being proportional to a relative importance of the execution relationship between the two nodes directly connected by the edge.

4. The method of claim 3 wherein each execution unit is a procedure of the program, each edge is a procedure call, and the weight is proportional to the number of times the edge is traversed during execution of the program.

5. The method of claim 3 further comprising:

mapping the instruction units in an order according to the weights of the edges.

6. The method of claim 3 further comprising:

partitioning the instruction units into popular and unpopular sets, the instruction units of the popular set directly connected by edges having weights greater than a predetermined threshold value, and

mapping the instruction units of the popular set before the instruction units of the unpopular set.

7. The method of claim 1 further comprising:

selecting two instructions units which have not been mapped to the cache memory;

merging the nodes of the two selected instruction into a compound node; and

mapping to two selected instruction units to adjacent blocks.

8. The method of claim 7 further comprising:

selecting instruction units of two different compound nodes;

merging the instruction units of the two different compound nodes; and

determining a distance between the instructions of the two different compound nodes;

mapping the instruction units so that the distance between the instruction units of the two compound is minimized.

9. The method of claim 8 wherein each block includes a fixed number of bytes and the distance is measured as the number of bytes separating the middle of an instruction unit and the end of the merged compound nodes.

10. The method of claim 9 further comprising:

determining if there are any conflicts between the identification of the blocks into which the instruction units of the merged compound nodes are mapped;

separating the instructions units of the merged two compound nodes until there is no conflict; and

mapping an instruction unit of the unpopular set into the space separating the mapped instruction units.

11. The method of claim 1 further comprising:

selecting an unmapped instruction unit and an mapped instruction units of a compound node;

merging the unmapped unit and the compound node; and

determining a distance between the unmapped instruction unit and the compound node;

mapping instruction units so that the distance between the unmapped instruction unit and the compound node is minimized.

12. The method of claim 1 further comprising:

selecting mapped instruction units of the same compound node;

merging the unmapped unit and the compound node;

determining if the selected instruction units overlap in the blocks;

moving the instruction unit that is nearest to the end of the compound node until there is no conflict.

13. The method of claim 1 wherein the cache memory is a direct mapped cache, and each block is a cache line, and further comprising:

assigning a respective identification to each cache line.

14. The method of claim 1 wherein the cache memory is a set-associative cache, and further comprising:

assigning a respective identification to each set of the set-associative cache.

15. The method of claim 3 wherein each execution unit is a basic block, and further comprising:

generating an execution profile for the basic blocks; and

assigning weights to the edges based on the execution profile.