1. Field of Use
The present invention relates to computer systems and more particularly to a cache system for use in such systems.
2. Prior Art
More and more computer systems include processors which are capable of executing instructions at a higher and higher rates as compared with the speed of high capacity main memory systems. To improve instruction execution speed, these systems utilize low capacity, high speed cache memories. The cache memories are used to store a limited number of instructions and/or data blocks. For each memory read operation, the processor checks the cache memory to determine if the information is stored there (a hit occurred). When there is a hit condition, the information will be read out from cache memory; otherwise (a miss condition), it will be fetched from main memory.
With such higher and higher processor instruction execution rates, the cache hit rate becomes extremely important in terms of both processor and system performance. That is, a hit rate less than 95 percent can result in a substantial decrease in overall system performance. This is particularly true in the case of multiprocessing systems.
Normally, the processor addresses the main and cache memories using a virtual address defining a relative memory location. The real or physical address defining an actual memory location is obtained by translating the virtual address. The virtual address normally includes segment, page and word address bits. The word address bits are not translated but the segment and page address bits are translated by an address translation buffer (ATB) or a memory management unit (MMU).
Since main memory is much larger than the cache memory, there are several common mapping techniques used for efficiently mapping information from main memory into the cache memory. A number of these techniques are described in an article by C. J. Conti entitled, "Concepts for Buffer Storage," published in the March 1969 issue of IEEE Computer Group News. One technique is the sector technique in which the cache and main memories are divided into a number of sections or pages, each of which consists of a large number of blocks. A main memory sector or page is mapped into any one of the sectors or the cache memory a block at a time. Each block resident in the cache memory has a tag associated with it for determining when the block is in cache memory. The cache memory is capable of holding only a small number of sectors, and each cache sector, at any given time, can contain only blocks from the same main memory sector. The search in the sector organized cache is fully associative in that any block potentially can be found in any one of the cache sectors.
While the system requires only one tag per sector and one validity bit per block, all of the tags of all of the blocks stored in the cache memory must be searched which is time-consuming or requires additional hardware.
In another technique, that of set associative, the cache and main memories are divided into a plurality of sets of blocks. A main memory block may be mapped into any one of the cache blocks in one set. While this technique reduces the amount of hardware required by the fully associative technique, it still requires a tag for each stored block. Therefore, the number of entries within a set is increased. This is accompanied by a factorial increase in comparison hardware.
In another technique, that of direct mapping, any main memory block can be placed in only one cache block. That is, each main memory block is preassigned a certain cache memory location. Therefore, searching is faster and requires a small amount of hardware. While the arrangement has these advantages, it is said to lack flexibility. Therefore, the set associative technique has been employed using a limited number of entries per set.
In order to provide a balance between the extremes in cache organizations in transferring too much data or requiring a large number of tags, one system employs a set associative sector cache. This system is disclosed in U.S. Pat. No. 4,493,026. While effeciency is achieved over the fully associative technique, the system still limits the number of entries per set and limits the amount of blocks of data which can be stored.
It is accordingly a primary object of this invention to provide an improved page or sector cache unit.
It is a further object of this invention to provide a cache unit for a processing unit which requires a small number of tags thus minimizing the amount of hardware circuits and cost.
It is another further object of the present invention to provide a cache unit which can be used for storing instructions or data and is usable in a multiprocessing system.
It is still a further object of the present invention to provide a fast access cache unit capable of storing data for a number of pages with great flexibility.