Memory control within data processing systems

• US 20020188809A1
• Filed: 07/25/2002
• Published: 12/12/2002
• Est. Priority Date: 01/19/1999
• Status: Active Grant

• Current Assignee: Arm Limited (SoftBank Group Corp.)
• Original Assignee: Arm Limited (SoftBank Group Corp.)
• Inventors: Kershaw, Daniel
• Granted Patent: US 6,684,302 B2
• Time in Patent Office: Days
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/127 using additional replacement algorithms
• CPC Class Codes: G06F 13/18 based on priority control G06F13/1605 takes precedence

Abstract

A data processing system 2 is described including a cache memory 8 and a plurality of DRAM banks 16, 18, 20, 22. A victim select circuit 32 within a cache controller 10 selects victim cache storage lines 28 upon a cache miss such that unlocked cache storage lines are selected in preference to locked cache storage lines, non-dirty cache storage lines are selected in preference to dirty cache storage lines, and cache storage lines requiring a write back to a non-busy DRAM bank are selected in preference to cached storage lines requiring a write back to a busy DRAM storage bank. A DRAM controller 24 is provided that continuously performs a background processing operation whereby dirty cache storage lines 28 within a cache memory 8 are written back to their respective DRAM banks 16, 18, 20, 22 when these are not busy performing other operations and when the cache storage line has a least recently used value below a certain threshold. A bus arbitration circuit 12 is provided that rearbitrates bus master priorities in dependence upon determined latencies for respective memory access requests. As an example, if a high priority memory access request results a cache miss, with a lower priority memory access request resulting in a cache hit, then the lower priority memory access request will be re-arbitrated to be performed ahead of the normally higher priority memory access request and may be finished before that higher priority memory access request starts to return data words to a data bus 14.

Claims

1. Data processing apparatus comprising:

(i) a cache memory having a plurality of cache storage lines;

(ii) a plurality of main memory units operable to store data words to be cached within said cache memory; and

(iii) a cache victim select circuit for selecting a victim cache storage line into which one or more data words are to be transferred from one of said main memory units following a cache miss;

wherein

(iv) said cache victim select circuit is responsive to an operational state of at least one of said main memory units when selecting said victim cache storage line.

2. Data processing apparatus as claimed in claim 1, wherein said cache memory is a write back cache memory.

3. Data processing apparatus as claimed in claim 1, wherein said operational state is whether or not said at least one main memory unit is busy exchanging one or more data words with said cache memory.

4. Data processing apparatus as claimed in claim 3, wherein said plurality of main memory units are operable to independently and concurrently transfer data words to said cache memory.

5. Data processing apparatus as claimed in claim 1, wherein said cache victim select circuit is responsive to whether or not a cache storage line is dirty in that it contains one or more data words that have been changed since they were transferred to said cache memory from one of said plurality of main memory units and require writing back to one of said main memory units when they are replaced within said cache memory and selects a victim cache storage line that is not dirty in preference to a cache storage line that is dirty.

6. Data processing apparatus as claimed in claim 1, comprising a plurality of data word requesting units that may each request exchange of one or more data words stored within said cache memory.

7. Data processing apparatus as claimed in claim 6, wherein one of said data word requesting units is a central processing unit.

8. Data processing apparatus as claimed in claim 6, wherein one of said data word requesting units is a video display driving circuit.

9. Data processing apparatus as claimed in claim 6, wherein one or more cache storage lines may be locked for preferential use by one of said data word requesting units.

10. Data processing apparatus as claimed in claim 1, wherein said cache victim select circuit is responsive to which of said plurality of cache storage lines was least recently used when selecting said victim cache storage line such that a cache storage line less recently used is selected as said victim cache storage line in preference to a cache storage line more recently used.

11. Data processing apparatus as claimed in claim 5, wherein one or more cache storage lines may be locked for preferential use by one of said data word requesting units, and said cache victim select circuit is responsive to which of said plurality of cache storage lines was least recently used when selecting said victim cache storage line such that a cache storage line less recently used is selected as said victim cache storage line in preference to a cache storage line more recently used and said cache victim select circuit selects as said victim cache storage line that cache storage line having properties placing it highest in a list of N properties, where 1≦

N≦

6, said list of N properties being formed of the N highest properties in the list;

(i) least recently used line that is not locked and is not dirty;

(ii) least recently used line that is not locked, is dirty and can be written back to a main memory unit that is not busy;

(iii) least recently used line that is not locked, is dirty and has to be written back to a main memory unit that is busy;

(iv) least recently used line that is locked and is not dirty;

(v) least recently used line that is locked, is dirty and can be written back to a main memory unit that is not busy;

(vi) least recently used line that is locked, is dirty and has to be written back to a main memory unit that is busy.

12. Data processing apparatus as claimed in claim 5, wherein one or more cache storage lines may be locked for preferential use by one of said data word requesting units and said cache victim select circuit selects as said victim cache storage line that cache storage line having properties placing it highest in a list of N properties, where 1≦

N≦

6, said list of N properties being formed of the N highest properties in the list;

(i) randomly selected from those cache storage lines that are not locked and are not dirty;

(ii) randomly selected from those cache storage lines that are not locked, are dirty and can be written back to a main memory unit that is not busy;

(iii) randomly selected from those cache storage lines that are not locked, are dirty and have to be written back to a main memory unit that is busy;

(iv) randomly selected from those cache storage lines that are locked and are not dirty;

(v) randomly selected from those cache storage lines that are dirty and can be written back to a main memory unit that is not busy;

(vi) randomly selected from those cache storage lines that are locked, are dirty and have to be written back to a main memory unit that is busy.

13. Data processing apparatus as claimed in claim 5, wherein one or more cache storage lines may be locked for preferential use by one of said data word requesting units and said cache victim select circuit selects as said victim cache storage line that cache storage line having properties placing it highest in a list of N properties, where 1≦

N≦

6, said list of N properties being formed of the N highest properties in the list;

(i) selected in sequence from those cache storage lines that are not locked and are not dirty;

(ii) selected in sequence from those cache storage lines that are not locked, are dirty and can be written back to a main memory unit that is not busy;

(iii) selected in sequence from those cache storage lines that are not locked, are dirty and have to be written back to a main memory unit that is busy;

(iv) selected in sequence from those cache storage lines that are locked and are not dirty;

(v) selected in sequence from those cache storage lines that are locked, are dirty and can be written back to a main memory unit that is not busy;

(vi) selected in sequence from those cache storage lines that are dirty and have to be written back to a main memory unit that is busy.

14. Data processing apparatus as claimed in claim 1, wherein said plurality of main memory units are a plurality of banks of dynamic random access memory.

15. Data processing apparatus as claimed in claim 14, wherein a refresh of data values held within a bank of dynamic random access memory can take place concurrently with an access to a cached data value within said cache memory corresponding to a data value within said bank of dynamic random access memory.

16. Data processing apparatus as claimed in claim 1, wherein said plurality of main memory units are a plurality of flash memory.

17. Data processing apparatus as claimed in claim 1, wherein said plurality of main memory units are provided together with said cache memory on an integrated circuit.

18. Data processing apparatus as claimed in claim 6, wherein said plurality of main memory units are provided together with said cache memory on an integrated circuit and said plurality of data word requesting units are also provided on said integrated circuit.

42. Data processing apparatus as claimed in claim 1 and claim 20.

43. Data processing apparatus as claimed in claim 1 and claim 31.

45. A data processing method as claimed in claim 19 and claim 30.

46. A data processing method as claimed in claim 19 and claim 41.

19. A data processing method comprising the steps of:

(i) storing data words within a plurality of cache storage lines of a cache memory;

(ii) storing in a plurality of main memory units said data words to be cached within said cache memory; and

(iii) selecting a victim cache storage line into which one or more data words are to be transferred from one of said main memory units following a cache miss;

wherein

(iv) said selection is responsive to an operational state of at least one of said main memory units when selecting said victim cache storage line.

20. A data processing apparatus comprising:

(i) a write back cache memory having a plurality of cache storage lines;

(ii) at least one main memory unit operable to store data words to be cached within said cache memory, a cache storage line being dirty if it contains any data words that have been changed since they were transferred from said at least one main memory unit to said cache storage line; and

(iii) a background operation control circuit for triggering writing back of data words from dirty cache storage lines to said at least one main memory unit as a background process, cache storage lines written back using said background process becoming not dirty and continuing to store said data words that were written back.

21. Data processing apparatus as claimed in claim 20, wherein said at least one main memory unit comprises a plurality of main memory units.

22. Data processing apparatus as claimed in claim 21, wherein said plurality of main memory units are operable to independently and concurrently transfer data words to said cache memory.

23. Data processing apparatus as claimed in claim 20, wherein said background operation control circuit is responsive to how recently data words from a dirty cache storage line were used when determining whether said dirty cache storage line should be written back to said at least one main memory unit, dirty cache storage lines more recently used than a threshold level not being written back to said at least one main memory unit.

24. Data processing apparatus as claimed in claim 20, wherein a main memory unit is busy when it is exchanging one or more data words with said cache memory, said background operation control circuit being operable not to trigger write back operations to a busy a main memory unit.

25. Data processing apparatus as claimed in claim 20, wherein said at least one main memory unit is a bank of dynamic random access memory.

26. Data processing apparatus as claimed in claim 20, wherein said at least one main memory unit is provided together with said cache memory on an integrated circuit.

27. Data processing apparatus as claimed in claim 26, comprising at least one data word requesting unit that may request exchange of one or more data words with said cache memory, said at least one data word requesting unit being also provided on said integrated circuit.

28. Data processing apparatus as claimed in claim 27, wherein said at least one data word requesting unit includes a central processing unit.

29. Data processing apparatus as claimed in claim 27, wherein said at least one said data word requesting unit includes a video display driving circuit.

44. Data processing apparatus as claimed in claim 20 and claim 31.

30. A data processing method comprising the steps of:

(i) storing data words within a plurality of cache storage lines of a write back cache memory;

(ii) storing in at least one main memory unit said data words to be cached within said cache memory, a cache storage line being dirty if it contains any data words that have been changed since they were transferred from said at least one main memory unit to said cache storage line; and

(iii) writing back data words from dirty cache storage lines to said at least one main memory unit as a background process, cache storage lines written back using said background process becoming not dirty and continuing to store said data words that were written back.

47. A data processing method as claimed in claim 30 and claim 41.

31. Data processing apparatus comprising:

(i) a memory circuit;

(ii) a data bus coupled to said memory circuit;

(iii) a plurality of bus master circuits coupled to said data bus for issuing memory access requests to said memory circuit via said data bus;

(iv) a bus arbitration circuit for controlling in accordance with a hierarchy of bus master priorities which bus master is granted priority in gaining use of said data bus when more two or more bus masters issue temporally overlapping memory access requests;

wherein

(v) said bus arbitration circuit is responsive to a determination of latency of pending memory access requests to re-arbitrate priority in gaining use of said data bus between bus masters such that a first bus master circuit having a first pending memory access request and a lower position in said hierarchy than a second bus master circuit having a second pending memory access request may gain use of said data bus ahead of said second bus master circuit if said first memory access request has a lower latency than said second memory access request.

32. Data processing apparatus as claimed in claim 31, wherein said first bus master circuit is given use of said data bus ahead of said second bus master circuit when said first memory access request has a latency such that it may be completed before said second memory access request is ready to transfer data words via said data bus.

33. Data processing apparatus as claimed in claim 31, wherein said memory circuit comprises a cache memory and a main memory.

34. Data processing apparatus as claimed in claim 33, wherein when said second memory access request results in a cache miss so that a main memory access is required, said bus arbitration circuit re-arbitrates priority such that if said second memory access request results in a cache miss, then said first bus master circuit will gain use of said data bus ahead of said first bus master circuit.

35. Data processing apparatus as claimed in claim 31, wherein said memory circuit comprises a plurality of main memory units, said plurality of main memory units being operable to independently and concurrently service respective memory access requests.

36. Data processing apparatus as claimed in claim 35, wherein, if said second memory access request is to a main memory unit that is already busy servicing another memory access request and said second memory access request is to a main memory unit that is not already busy servicing a memory access request such that said second memory access request has a lower latency than said first memory access request, then said bus arbitration circuit re-arbitrates between said plurality of bus master circuits such that said second bus master circuit gains use of said data bus ahead of said first bus master circuit.

37. Data processing apparatus as claimed in claim 35, wherein said plurality of main memory units are a plurality of banks of dynamic random access memory.

38. Data processing apparatus as claimed in claim 31, wherein said memory circuit, said data bus, said plurality of bus master circuits and said bus arbitration circuit are provided together on an integrated circuit.

39. Data processing apparatus as claimed in claim 31, wherein said plurality of bus master circuits include a central processing unit.

40. Data processing apparatus as claimed in claim 31, wherein said plurality of bus master circuits include a video display driving circuit.

41. A data processing method comprising the steps of:

(i) issuing memory access requests from a plurality of bus master circuits to a memory circuit via a data bus;

(ii) controlling, in accordance with a hierarchy of bus master priorities, which bus master is granted priority in gaining use of said data bus when more two or more bus masters issue temporally overlapping memory access requests;

wherein

(iii) in response to a determination of latency of pending memory access requests, priority in gaining use of said data bus between bus masters is re-arbitrated such that a first bus master circuit having a first pending memory access request and a lower position in said hierarchy than a second bus master circuit having a second pending memory access request may gain use of said data bus ahead of said second bus master circuit if said first memory access request has a lower latency than said second memory access request.