Patent ID: 7469332

Claim:
A method for adaptively mapping an instruction cache, comprising: receiving addresses from a program counter, each address corresponding to a location in a system memory where an instruction is stored; defining a plurality of mapping functions, wherein each mapping function which maps different bits of an address received from the program counter into a tag to identify an instruction stored in the system memory at the address provided by the program counter and an index to identify a location in an instruction cache for storing the instruction and the tag; each mapping function mapping a different number of address bits into the tag and into the index so that a different number of collisions will occur under each different mapping functions; observing, for each of the plurality of mapping functions, during execution of multiple programs, a mapping of a sequence of addresses from the program counter to determine, for each mapping function, a number of collisions; wherein a collision is an occurrence of an address from the program counter mapping to an index where the location in an instruction cache corresponding to the index is full of valid instructions; determining from the observations a first mapping function of the plurality of mapping functions that reduces collisions, the first mapping function determining which bits of the instruction address are deemed to be the tag, and which bits are deemed to be the cache address; and dynamically remapping according to the first mapping function determined to reduce collisions, by determining which bits of the instruction address are deemed to be the tag, and which bits are deemed to be the cache address in order to minimize collisions as determined by the observations; writing instructions to the cache according to the first mapping function that is observed to reduce collisions without relinking a program; determining from the observations of the mapping of instructions into the cache a mapping of the system memory address bits to a tag and an index that reduce collisions with steady state code; and changing the mapping function implemented by an address mapper and flushing the instruction cache when the mapping function is changed.