Cache control circuit having a pseudo random address generator

• US 5,875,465 A
• Filed: 04/03/1997
• Issued: 02/23/1999
• Est. Priority Date: 04/03/1996
• Status: Expired due to Term

• Current Assignee: Arm Limited (SoftBank Group Corp.)
• Original Assignee: Arm Limited (SoftBank Group Corp.)
• Inventors: Larri, Guy, Watt, Simon Charles, Kilpatrick, Michael Thomas
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): Nguyen, Hiep T.
• Application Number:
  US08/832,091
• Time in Patent Office: 691 Days
• Field of Search: 711/133, 711/134, 711/123, 711/128, 711/129, 711/145, 711/163, 711/171, 711/173, 365/717.01, 365/717.03
• US Class Current: 711/134
• CPC Class Codes: G06F 12/0848 Partitioned cache, e.g. separate instruction and operand caches
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel

Abstract

A data processing system incorporating a cache memory 2 and a central processing unit. A storage control circuit 10 is responsive to a programmable partition setting PartVal to partition the cache memory between instruction words and data words in dependence upon whether the central processing unit 4 indicates with signal I/D whether the word to be stored within the cache memory 2 resulted from an instruction word cache miss or data word cache miss. The cache memory array 2 may have a programmably sized portion locked down so that it is not replaced. The selection within the complementary programmable range where overwriting takes place uses a pseudo random selection technique using pseudo random number generator in the form of a linear feedback shift register triggering incrementing of a counter.

Claims

1. Apparatus for data processing comprising:

a cache memory having X cache storage locations each storing a data line including one or more data words;

a storage control circuit for controlling storage of a new line within said cache memory following a cache miss including selection of a cache storage location to be overwritten when said new line is stored in said cache memory;

wherein said storage control circuit includes a pseudo random number generator comprising a counter triggered to change a stored value by counting through one or more values in response to a pseudo random bit stream output from a pseudo random bit stream generator and said storage control circuit pseudo randomly selects said cache storage location using said stored value from a programmable range of cache storage locations A to B within said X cache storage locations of said cache memory, cache storage locations outside of said programmable range being unavailable to be overwritten, A and B being stored within respective end point registers and used as wrap values for said counter.

2. Apparatus as claimed in claim 1, wherein said storage control circuit is responsive to a programmable replacement algorithm flag to select said cache storage location with an alternative algorithm.

3. Apparatus as claimed in claim 2, wherein said alternative algorithm is sequential selection of adjacent storage locations.

4. Apparatus as claimed in claim 3, wherein when said sequential selection reaches an end of said programmable range of cache storage locations, said sequential selection wraps to another end of said programmable range.

5. Apparatus as claimed in claim 1, wherein one of A and B is a fixed value.

6. Apparatus as claimed in claim 1, wherein said pseudo random bit stream generator is a linear feedback shift register.

7. Apparatus as claimed in claim 1, wherein said pseudo random number generator is continuously operated and said stored value is used to select said cache storage location to be overwritten when needed by said storage control circuit.

8. Apparatus as claimed in claim 1, wherein said counter value is changed by one step in its counting sequence independently of said pseudo random number generator each time a cache storage location is overwritten.

9. Apparatus as claimed in claim 3, wherein said counter value is changed by one step in its counting sequence independently of said pseudo random number generator each time a cache storage location is overwritten and said pseudo random bit stream output is gated by said programmable replacement algorithm flag such that said pseudo random bit stream does not trigger said counter to change when said programmable replacement algorithm flag is set to select sequential selection.

10. Apparatus as claimed in claim 1, wherein said storage control circuit is operable in a lockdown write mode in which cache storage locations can be selected for loading under program control including cache storage locations outside of said programmable range.

11. Apparatus as claimed in claim 10, wherein a cache storage location is addressed for overwriting by a programmable lockdown address location register, and said storage control circuit includes a lockdown write mode flag which is stored in a lockdown mode register which can be modified under program control, and said storage control circuit selects said cache storage location to be overwritten using either said stored value in said counter or a value stored in said programmable lockdown address location register in dependence upon said lockdown write mode flag.

12. Apparatus as claimed in claim 11, wherein one of said end point registers is reused to serve as said programmable lockdown address location register.

13. Apparatus as claimed in claim 1, wherein

said storage control circuit is responsive to a programmable replacement algorithm flag to select said cache storage location with an alternative algorithm;

said alternative algorithm is sequential selection of adjacent storage locations;

when said sequential selection reaches an end of said programmable range of cache storage locations, said sequential selection wraps to another end of said programmable range;

one of A and B is a fixed value;

said pseudo random number generator is continuously operated and said stored value is used to select said cache storage location to be overwritten when needed by said storage control circuit;

said counter value is changed by one step in its counting sequence independently of said pseudo random number generator each time a cache storage location is overwritten;

said storage control circuit is operable in a lockdown write mode in which cache storage locations can be selected for loading under program control including cache storage locations outside of said programmable range;

a cache storage location is addressed for overwriting by a programmable lockdown address location register, and said storage control circuit includes a lockdown write mode flag which is stored in a lockdown mode register which can be modified under program control, and said storage control circuit selects said cache storage location to be overwritten using either said stored value in said counter or a value stored in said programmable lockdown address location register in dependence upon said lockdown write mode flag; and

one of said end point registers is reused to serve as said programmable lockdown address location register.

14. Apparatus as claimed in claim 1, wherein said cache miss results from a cache request to a new word from one of a plurality of request sources and said storage control circuit is responsive to a programmable partition setting to divide said cache memory into a plurality of portions each with a storage capacity controlled by said programmable partition setting and said storage control circuit selects in which of said plurality of portions to store said new word in dependence upon which of said plurality of request sources requested said new word.

15. Apparatus as claimed in claim 14, wherein said cache request searches all of said portions for said new word to determine if a cache miss has occurred.

16. Apparatus as claimed in claim 14, wherein said cache memory is an N-way associative cache memory, where N is an integer value greater than 1, and each of said plurality of portions has a storage capacity selectable in steps of 1/N of the total cache memory storage capacity.

17. Apparatus as claimed in claim 14, comprising a central processing unit having a data request source for requesting new data words and an instruction request source for requesting new instruction words.

18. Apparatus as claimed in claim 17, wherein said cache memory has a data word portion and an instruction word portion, said programmable partition setting controlling division of capacity of said cache memory between data words and instruction words.

19. Apparatus as claimed in claim 14, wherein said storage control circuit selects which currently stored word within said selected portion of said cache memory to overwrite with said new word using independent algorithms for each of said plurality of portions.

20. A method of processing data, said method comprising the steps of:

storing data lines comprising one or more data words in a cache memory having X cache line storage locations; and

controlling, with a storage control circuit, storage of a new line within said cache memory following a cache miss including selection of a cache storage location to be overwritten when said new line is stored in said cache memory;

wherein said storage control circuit includes a pseudo random number generator comprising a counter triggered to change a stored value by counting through one or more values in response to pseudo random bit stream output from a pseudo random bit stream generator and said storage control circuit pseudo randomly selects said cache storage location using said stored value from a programmable range of cache storage locations A to B within said X cache line storage locations of said cache memory, cache storage locations outside of said programmable range being unavailable to be overwritten, A and B being stored within respective end point registers and used as wrap values for said counter.

21. A method as claimed in claim 20, wherein said pseudo random bit stream is generated using a linear feedback shift register.