Method and apparatus for indexing, accessing and updating a memory

Claim 3

The method of claim 1 wherein each of said branch cache data entries contains a branch target address whose corresponding branch instruction is contained in one of said instruction cache data entries.

Claim 4

A cache memory system for a pipelined digital computer, comprising: instruction cache means having a plurality of instruction cache locations for storing a plurality of instruction cache data entries, each of said instruction cache data entries having an associated coupling bit field, each of said instruction cache locations accessible by a first index, branch cache set means having a plurality of branch cache locations for storing a plurality of branch cache data entries, a plurality of said branch cache data entries having a corresponding instruction cache data entry, each of said branch cache locations accessible by a second index comprising a portion of the first index of said corresponding instruction cache data entry, said branch cache data entries each including a back pointer field, means responsive to one of said first indexes for accessing one of said corresponding instruction cache data entries, means responsive to the second index and backpointer field of said at least one branch cache data entry for reconstructing the first index of said corresponding instruction cache data entry, and means responsive to said reconstructed first index for accessing the instruction cache location containing said corresponding instruction cache data entry and for initializing said associated coupling bit field,

Claim 5

A cache memory system for a pipelined digital computer, comprising: instruction cache means having a plurality of instruction cache locations for storing a plurality of instruction cache data entries, each of said instruction cache data entries having an associated coupling bit field, each of said instruction cache locations accessible by a first index, branch cache set means having a plurality of branch cache locations for storing a plurality of branch cache data entries, a plurality of said branch cache data entries having a corresponding instruction cache data entry, each of said branch cache locations accessible by a second index comprising a portion of the first index of said corresponding instruction cache data entry, said branch cache data entries each including a back pointer field, means responsive to one of said first indexes for accessing one of said corresponding instruction cache data entries, means responsive to the second index and backpointer field of said at least one branch cache data entry for reconstructing the first index of said corresponding instruction cache data entry, and means responsive to said reconstructed first index for accessing the instruction cache location containing said corresponding instruction cache data entry and for initializing said associated coupling bit field,

Claim 6

The cache memory system of claim 3 in which said corresponding instruction cache data entry comprises a branch instruction.

Claim 7

The cache memory system of claim 4 wherein said corresponding instruction cache data entry further comprises a coupling bit field.

Claim 8

The cache memory system of claim 5 wherein said at least one branch cache data entry further comprises a branch target address, whose corresponding branch instruction is contained in said corresponding instruction cache data entry.

Claim 9

The cache memory system of claim 5 wherein the coupling bit field of a said corresponding instruction cache data entry contains a binary expression indicating which of said plurality of branch cache means contains said at least one branch cache data entry.

Claim 10

The cache memory system of claim 3 wherein the first index of said corresponding instruction cache data entry comprises m instruction address bits of the instruction contained therein, where m is a position integer than one.

Claim 11

The cache memory system of claim 8 wherein the second index of said at least one branch cache data entry comprises n bits of the first index of said corresponding instruction cache entry, wherein n is a positive integer greater that zero but less than m.

Claim 12

The cache memory system of claim 9 wherein the backpointer field of said at least one branch cache data entry comprises the instruction address bits of said first index which are not present in the second index of said at least one branch cache data entry.

Claim 13

The cache memory system of claim 10 wherein said means for reconstructing said first index includes circuitry for combining the instruction address bits contained in the second index and backpointer field of said at least one branch cache data entry to generate the index of said corresponding instruction cache data entry.

Claim 14

The cache memory system of claim 11 wherein said means responsive to said reconstructed first index comprises circuitry for re-accessing said corresponding instruction cache data entry and circuitry for initializing the associated coupling bit field of said corresponding instruction cache data entry.

Claim 15

The cache memory system of claim 3 wherein said associated coupling bit fields are stored in a third memory means having a plurality of third locations, each of said third locations accessible by the first index of the instruction cache entry associated with said coupling bit field.

Claim 16

A cache memory system for a pipelined computer comprising: an instruction cache means having a plurality of indexed instruction cache locations, each containing at least an instruction and a coupling bit field, each instruction cache location having a first index comprising instruction address bits of the instruction contained therein; a branch cache set means having a plurality of indexed branch cache locations each containing at least a branch target address and a backpointer field, each branch cache location having a corresponding instruction cache location which contains a branch instruction, each branch cache location having a second index comprising a portion of the first index of its corresponding instruction cache location; and a first control circuit means, responsive to the first index and coupling bit field of one of said corresponding instruction cache locations for identifying at least one of said branch cache locations which contains a corresponding branch target address; a second control circuit means, responsive to the second index and backpointer field of said at least one branch cache location for reconstructing the first index of said corresponding instruction cache location in which a corresponding branch instruction is stored, and an update circuit means, responsive to said reconstructed first index for accessing said corresponding instruction cache location and modifying the coupling bit field contained therein.

Claim 17

A cache memory system for a pipelined computer comprising: an instruction cache means having a plurality of indexed instruction cache locations, each containing at least an instruction and a coupling bit field, each instruction cache location having a first index comprising instruction address bits of the instruction contained therein; a branch cache set means having a plurality of indexed branch cache locations each containing at least a branch target address and a backpointer field, each branch cache location having a corresponding instruction cache location which contains a branch instruction, each branch cache location having a second index comprising a portion of the first index of its corresponding instruction cache location; and a first control circuit means, responsive to the first index and coupling bit field of one of said corresponding instruction cache locations for identifying at least one of said branch cache locations which contains a corresponding branch target address; a second control circuit means, responsive to the second index and backpointer field of said at least one branch cache location for reconstructing the first index of said corresponding instruction cache location in which a corresponding branch instruction is stored, and an update circuit means, responsive to said reconstructed first index for accessing said corresponding instruction cache location and modifying the coupling bit field contained therein.

Claim 18

The cache memory system of claim 14 wherein the first index of said corresponding instruction cache location comprises the m least significant instruction address bit of the instruction contained in said corresponding instruction cache location, where m is a positive integer greater than one.

Claim 19

The cache memory system of claim 15 wherein the second index of said at least one branch cache location comprises the n least significant instruction address bits of the corresponding first index, where n is a positive integer greater than zero but less than m.

Claim 20

The cache memory system of claim 16 wherein the backpointer field of said at least one branch cache location comprises the q most significant instruction address bits of the corresponding first index, where q is a positive integer greater than one and is equal to m minus n.

Claim 21

The cache memory system of claim 17 wherein said second control circuit means combines the m address bits of said second index wit the q address bits of said backpointer field of said at least one branch cache location to form the first index of said corresponding instruction cache location.

Claim 22

The cache memory system of claim 14 wherein said coupling bit field of an instruction cache location comprises a digital expression indicating which of said branch cache set means includes said at least one branch cache location containing a branch target address for the branch instruction stored in said corresponding instruction cache location.

Claim 23

The cache memory system of claim 19 wherein said coupling bit field comprises a plurality of bits, each of said bits representing a branch cache means, the binary value of each of said bits indicating whether the represented branch cache means contains a branch cache location corresponding to the instruction cache location in which the coupling bit field resides.