Method of improving L1 icache performance with large programs

1 . A method of operating a computer system, the method comprising:

accessing a L1 icache that stores regular instructions and non-instruction information, wherein the non-instruction information comprises non-sequential addresses, and wherein the non-instruction information in the L1 icache further comprises: an address of a read request that results in a miss in the non-instruction information in the L1 icache, and an offset corresponding to the address of the read request that is used to identify a next memory address; and

prefetching the next memory address to be stored in the L1 icache, when the next memory address is not present in the L1 icache.

2 . The method of claim 1 , wherein the L1 icache includes a plurality of sets and a plurality of ways such that each set of the plurality of sets has a number of ways, the number of ways including a first number of ways for storing the regular instructions and a second number of ways for storing the non-instruction information.

3 . The method of claim 2 , further comprising:

determining whether the L1 icache has received a request to obtain an instruction located at a specific memory address;

determining whether the specific memory address is stored in the first number of ways of the number of ways in the L1 icache; and

outputting the instruction associated with the specific memory address to a processor when the specific memory address is stored in the L1 icache.

4 . The method of claim 1 , further comprising determining whether the address of the read request and the next memory address are sequential or non-sequential, wherein said determining includes determining whether a current value of a program counter is more than one greater than a last value of the program counter, a sequential address having a current value that is one greater than the last value, and a non-sequential address having a current value that is more than one greater than the last value.

5 . The method of claim 1 , further comprising, when the address of the read request and the next memory address are non-sequential:

accessing the non-instruction information in the L1 icache to identify the offset;

adding the offset to a program counter value representing the address of the read request, to determine the next memory address;

accessing a filter table to determine whether the next memory address is useful;

determining whether the next memory address is already present in the non-instruction information in the L1 icache when the next memory address is useful; and

prefetching the next memory address into the L1 icache when the next memory address is useful and not already present in the non-instruction information in the L1 icache.

6 . The method of claim 1 , further comprising, when the address of the read request and the next memory address are sequential:

accessing a filter table to determine whether the next memory address is useful;

determining whether the next memory address is already present in the non-instruction information in the L1 icache when the next memory address is useful; and

prefetching the next memory address into the L1 icache when the next memory address is useful and not already present in the non-instruction information in the L1 icache.

7 . The method of claim 1 , further comprising:

outputting a request to obtain an instruction associated with a specific memory address to a larger memory when the specific memory address is not stored in the L1 icache;

determining whether the specific memory address is sequential or non-sequential;

mapping a last memory address to the specific memory address to form mapped information when the specific memory address is non-sequential; and

storing the mapped information in a correlation table in the L1 icache.

8 . The method of claim 1 , wherein the non-instruction information comprises a prefetch correlation table, wherein the prefetch correlation table is an array comprising the non-sequential addresses, wherein the prefetch correlation table stores the offset, and wherein the offset is added to a program counter value that represents the address of the read request to determine the next memory address for said prefetching.

9 . The method of claim 1 , wherein the L1 icache includes a plurality of sets and a plurality of ways such that each set of the plurality of sets has a number of ways, the number of ways including a first number of ways reserved for storing the regular instructions and a second number of ways that are isolated from the first number of ways and reserved for storing the non-instruction information.

10 . The method of claim 1 , wherein the L1 icache includes a plurality of ways, wherein each way of the plurality of ways comprises a tag, and wherein the tag comprises a bit having a value that indicates whether a way of the plurality of ways stores a regular instruction or stores non-instruction information.

11 . A computer system, comprising:

a L1 icache that stores regular instructions and non-instruction information, wherein the non-instruction information comprises non-sequential addresses, and wherein the non-instruction information in the L1 icache further comprises: an address of a read request that results in a miss in the non-instruction information in the L1 icache, and an offset corresponding to the address of the read request that is used to identify a next memory address; and

a processor coupled to the L1 icache, the processor being configured to prefetch the next memory address to be stored in the non-instruction information in the L1 icache, when the next memory address is not present in the non-instruction information in the L1 icache.

12 . The computer system of claim 11 , wherein the L1 icache has a plurality of sets and a plurality of ways such that each set of the plurality of sets has a number of ways, the number of ways including a first number of ways for storing the regular instructions and a second number of ways for storing the non-instruction information.

13 . The computer system of claim 12 , wherein the processor is further configured to:

determine whether the L1 icache has received a request to obtain an instruction located at a specific memory address;

determine whether the specific memory address is stored in the first number of ways of the number of ways in the L1 icache; and

output the instruction associated with the specific memory address to the processor when the specific memory address is stored in the L1 icache.

14 . The computer system of claim 11 , wherein the processor determines whether the address of the read request and the next memory address are sequential or non-sequential by determining whether a current value of a program counter is more than one greater than a last value of the program counter, a sequential address having a current value that is one greater than the last value, and a non-sequential address having a current value that is more than one greater than the last value.

15 . The computer system of claim 11 , wherein when the address of the read request and the next memory address are non-sequential, the processor is further configured to:

access the non-instruction information in the L1 icache to identify the offset;

add the offset to a program counter value representing the address of the read request, to determine the next memory address;

access a filter table to determine whether the next memory address is useful;

determine whether the next memory address is already present in the non-instruction information in the L1 icache when the next memory address is useful; and

prefetch the next memory address into the L1 icache when the next memory address is useful and not already present in the non-instruction information in the L1 icache.

16 . The computer system of claim 11 , wherein when the address of the read request and the next memory address are sequential, the processor is further configured to:

access a filter table to determine whether the next memory address is useful;

determine whether the next memory address is already present in the non-instruction information in the L1 icache when the next memory address is useful; and

prefetch the next memory address into the L1 icache when the next memory address is useful and not already present in the non-instruction information in the L1 icache.

17 . A non-transitory computer-readable medium having computer-readable instructions stored thereon which, when executed by a processor, cause the processor to execute a method of cache prefetching, the method comprising:

accessing a L1 icache that stores regular instructions and non-instruction information, wherein the non-instruction information comprises non-sequential addresses, and wherein the non-instruction information in the L1 icache further comprises: an address of a read request that results in a miss in the non-instruction information in the L1 icache, and an offset corresponding to the address of the read request that is used to identify a next memory address; and

prefetching the next memory address to be stored in the non-instruction information in the L1 icache, when the next memory address is not present in the non-instruction information in the L1 icache.

18 . The non-transitory computer-readable medium of claim 17 , wherein the L1 icache includes a plurality of sets and a plurality of ways such that each set of the plurality of sets has a number of ways, the number of ways including a first number of ways for storing the regular instructions and a second number of ways for storing the non-instruction information.

19 . The non-transitory computer-readable medium of claim 18 , wherein the method further comprises:

determining whether the L1 icache has received a request to obtain an instruction located at a specific memory address;

determining whether the specific memory address is stored in the first number of ways of the number of ways in the L1 icache; and

outputting the instruction associated with the specific memory address to the processor when the specific memory address is stored in the L1 icache.

20 . The non-transitory computer-readable medium of claim 17 , wherein the method further comprises determining whether the address of the read request and the next memory address are sequential or non-sequential, and wherein said determining includes determining whether a current value of a program counter is more than one greater than a last value of the program counter, a sequential address having a current value that is one greater than the last value, and a non-sequential address having a current value that is more than one greater than the last value.

21 . The non-transitory computer-readable medium of claim 17 , wherein when the address of the read request and the next memory address are non-sequential, the method further comprises:

accessing the non-instruction information in the L1 cache to identify the offset;

adding the offset to a program counter value representing the address of the read request, to determine the next memory address;

accessing a filter table to determine whether the next memory address is useful;

determining whether the next memory address is already present in the non-instruction information in the L1 icache when the next memory address is useful; and

prefetching the next memory address into the L1 icache when the next memory address is useful and not already present in the non-instruction information in the L1 icache.

22 . The non-transitory computer-readable medium of claim 17 , wherein when the address of the read request and the next memory address are sequential, the method further comprises:

accessing a filter table to determine whether the next memory address is useful;

determining whether the next memory address is already present in the non-instruction information in the L1 icache when the next memory address is useful; and

prefetching the next memory address into the L1 icache when the next memory address is useful and not already present in the non-instruction information in the L1 icache.