US 5,963,972 AGranted

Memory architecture dependent program mapping

AssigneeDigital Equipment Corporation

InventorsBradley Gene Calder, Amir Hooshang Hashemi, David Richard Kaeli

Life of this patent

Estimating the term…

Loading patent…

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.

Claims15

Dependent claims

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.

3 more elements

Dependencies are inferred from the claim text.