Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-05-17
2003-07-15
Portka, Gary (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S171000, C711S173000
Reexamination Certificate
active
06594729
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 OF 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 behavior 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 behavior.
SUMMARY OF THE INVENTION
In general, the present invention provides 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,
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 one arrangement, a cache partition access table holds in association with addresses of items to be cached respective multi-bit partition indicators identifying into which cache partition the item may be loaded. In the described embodiment of this arrangement, 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.
In another arrangement, a set of partition selector bits which are held as part of the virtual address itself. This set of partition selector bits is used to generate a partition mask which is used to control access to the cache.
In both arrangements, the line-in-page number of the items addressed can be used to identify the addressable storage location within the cache partition into which the item is to be located. That is, each cache partition could be direct-mapped. It will be apparent that it is not necessary to use all of the end bits-of the item's 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. Moreover, it will be appreciated that within a cache partition the addressing mechanism need not be direct mapped but could be fully associative.
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 one or more of said cache partitions is allocated to said item in dependence on the address of said item in main memory.
In one arrangement described herein, each address is associated with a multi-bit partition indicator identifying into which cache partition the item may be loaded. The partition indicator is held in a cache partition access table in association with the addresses of items to be cached. In another arrangement described herein, a set of partition selector bits is held as part of the virtual address itself. This set of partition selector bits is used to generate a partition mask for controlling access to the cache.
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 ability to provide flexible partitioning of a cache as described herein serves a number of useful purposes.
Inter-thread partitioning can be used to prevent trashing of the entire cache when accessing a large array. This is particularly effective when the routine is reading or writing each element only once.
Inter-thread partitioning prevents the caching behavior of a critical process being perturbed by the cache activities of other processes. For instance, a real time task would not wish critical data to be removed from the cache.
If a single cache is used to hold both data and instructions, it is possible to partition the cache so that the data and instructions use different partitions.
The following described embodiments illustrate 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: 4463424 (1984-07-01), Mattson et al.
patent: 4654782 (1987
May David
Sturges Andrew Craig
Moazzami Nasser
Morris James H.
Portka Gary
Skrivanek, Jr. Robert A.
STMicroelectronics Limited
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-3085859