Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1998-01-27
2002-09-17
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S133000, C711S173000
Reexamination Certificate
active
06453385
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a cache system for operating between a processor and a main memory of a computer.
BACKGROUND TO THE INVENTION
As is well known in the art, cache memories are used in computer systems to decrease the access latency to certain data and code and to decrease the memory bandwidth used for that data and code. A cache memory can delay, aggregate and reorder memory accesses.
A cache memory operates between a processor and a main memory of a computer. Data and/or instructions which are required by the process running on the processor can be held in the cache while that process runs. An access to the cache is normally much quicker than an access to main memory. If the processor does not locate a required data item or instruction in the cache memory, it directly accesses main memory to retrieve it, and the requested data item or instruction is loaded into the cache. There are various known systems for using and refilling cache memories.
In order to rely on a cache in a real time system, the behaviour of the cache needs to be predictable. That is, there needs to be a reasonable degree of certainty that particular data items or instructions which are expected to be found in the cache will in fact be found there. Most existing refill mechanisms will normally always attempt to place in the cache a requested data item or instructions. In order to do this, they must delete other data items or instructions from the cache. This can result in items being deleted which were expected to be there for later use. This is particularly the case for a multi-tasking processor, or for a processor which has to handle interrupt processes or other unpredictable processes.
It is an object of the present invention to provide a cache system which obviates or reduces this disadvantage and provides greater predictability of caching behaviour.
SUMMARY OF THE INVENTION
According to one aspect of the present invention there is provided a cache system for operating between a processor and a main memory of a computer, the cache system comprising:
a cache memory having a set of cache partitions, each cache partition comprising a plurality of addressable storage locations for holding items fetched from said main memory for use by the processor,
a cache refill mechanism arranged to fetch an item from the main memory and to load said item into the cache memory at one of said addressable storage locations;
a cache partition access table holding in association with addresses of items to be cached respective multi-bit partition indicators identifying into which cache partition the item may be loaded,
wherein the cache refill mechanism is operable to allocate to each said item fetched from the main memory one or more of said cache partitions in dependence on the address of said item in the main memory.
It is thus quite possible for an item to have access to more than one partition of the cache, or indeed for an item not to be allowed access to the cache at all.
In the described embodiment, each address in main memory comprises a page number and a line in page number, the page numbers being held in a look-up table in association with their respective partition indicators.
In a virtual addressing system, the processor issues addresses comprising a virtual page number and line in page number. In that event, the system can comprise a translation look aside buffer for translating the virtual page number to a real page number for accessing the main memory, the translation look aside buffer also holding respective partition indicators in association with the real page numbers for identifying the cache partition into which the addressed item is to be loaded.
The line in page number of the items addressed can be used to identify the address storage location within the cache partition into which the item is to be located. That is, each cache partition is direct-mapped. It will be apparent that it is not necessary to use all of the end bits of the items address as the line in page number, but merely a set of appropriate bits. These will normally be near the least significant end of the address.
One or more cache partitions may be allocated to a page in main memory.
The system can include a cache access circuit which accesses items from the cache memory according to the address in main memory of said items and regardless of the cache partition in which the item is held in the cache memory. That is, the partition indicator is only used on refill and not on look-up. Thus, a cached item can be retrieved from its partition even if subsequent to its caching that partition is now allocated to a different set of addresses.
According to another aspect of the invention there is provided a method of operating a cache memory arranged between a processor and a main memory of a computer, wherein, when the processor requests an item from main memory using an address in main memory for said item and that item is not held in the cache memory, said item is fetched from the main memory and loaded into one of a plurality of addressable storage locations in the cache memory, the addressable storage locations being arranged as a set of cache partitions and wherein each address is associated with a multi-bit partition indicator identifying into which cache partition the item may be loaded so that one or more of said cache partitions is allocated to said item in dependence on the address of said item in main memory.
The main memory can hold a plurality of processes, each process including one or more sequence of instructions held at addresses in the main memory within a common page number. Cache partitions can be allocated by associating each cache partition with page numbers of a particular process in the main memory.
The number of addressable storage locations in each cache partition can be alterable. Also, the association of cache partitions to page numbers can be alterable while a process using these page numbers is being run by the processor.
The following described embodiment illustrates a cache system which gives protection of the contents of the cache against unexpected eviction by reading from or writing to cache lines from other pages of data which are placed in other partitions. It also provides a system in which the contents of the cache may be predicted.
For a better understanding of the present invention and to show how the same may be carried into effect, reference will now be made by way of example to the accompanying drawings.
REFERENCES:
patent: 4654782 (1987-03-01), Bannai et al.
patent: 4905141 (1990-02-01), Brenza
patent: 5487162 (1996-01-01), Tanaka et al.
patent: 5584014 (1996-12-01), Nayfeh et al.
patent: 5796944 (1998-08-01), Hill et al.
patent: 5875464 (1999-02-01), Kirk
patent: 2 311 880 (1997-10-01), None
European Search Report for European application No. 98 30 0518, search completed May 8, 1998.*
Standard Search Report for application No. RS 99958, search completed Feb. 20, 1998.*
European Search Report for European application No. 98 30 0515, search completed May 8, 1998.*
International Search Report for application No. PCT/GB98/00268, filed Jan. 29, 1998.*
Dongwook, K., et al., A Partitioned On-Chip Virtual Cache for Fast Processors, Journal of System Arch., vol. 43, No. 8, May 1997, pp. 519-531.*
Mueller F., Compiler Support for Software-Based Cache Partitioning, ACM Sigplan Notices, vol. 30, No. Nov. 1, 1995, pp. 125-133.*
Kirk D.B., Smart (Stragetic Memory Allocation for Real-Time) Cache Design, Proceedings of the Rea Times Systems Symposium, Dec. 5, 1989, pp. 229-237.*
Standard Search Report performed by the European Patent Office, dated Oct. 16, 1997.
Compiler Support for Software-Based Cache Partitioning, Frank Mueller, ACM SigPlan Notices, vol. 30 No. 11, Nov. 1995, pp. 125-133.
Barnaby Catherine
Farrall Glenn
Fel Bruno
May David
Sturges Andrew Craig
Moazzami Nasser
Morris James H.
SGS-Thomson Microelectronics Limited
Skrivanek, Jr. Robert A.
Wolf Greenfield & Sacks P.C.
LandOfFree
Cache system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cache system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2854571