Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-01-15
2002-07-09
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
Reexamination Certificate
active
06418515
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a cache flush unit and method for use in a computer system constituted by a uniprocessor or a multiprocessor having a cache.
In a general computer, a cache for temporarily storing data required by the processor is used to increase the speed of access from the processor to the main memory. Normally, the cache holds data as data units with a predetermined size, which are called cache blocks. The cache also holds management information called a cache tag to manage the correspondence between cache block data stored in the cache and data in the main memory, and whether the data is changed by the processor, i.e., different from contents in the main memory (modified state or dirty state).
A computer system having a plurality of processors (multiprocessor system) often uses caches each having a snoop mechanism to guarantee data consistency among the plurality of caches. In the snoop mechanism, each bus snooper monitors whether a bus command (or a transaction) issued onto the bus influences data stored in its own cache or whether the data stored in its own cache need be returned as a response, and invalidates the data, as needed.
In a copy-back type cache, i.e., a cache which does not immediately reflect data updating by the processor to the main memory, there is case where data (modified data) changed on the cache by the processor to have contents different from those in the main memory must be explicitly written back in the main memory. This operation is required to, e.g., transfer data held by the cache to an input/output device having no snoop mechanism. The operation of writing modified data, which is held by the cache, back in the main memory is called cache flush. A modified cache block is called a modified block.
Cache flush is especially required for a computer using the checkpoint method. In a checkpoint type computer which restarts processing from checkpoint time acquired in advance when some fault occurs in the computer, all modified data which are present only in the cache must be written back (cache flush) in the main memory at each checkpoint time.
To implement the cache flush operation, a system for causing the processor to execute a cache flush instruction or a system for causing a cache flush unit to execute a cache flush instruction is used.
In the method of causing the processor to execute the cache flush instruction, the processor cannot execute another program while it is executing cache flush. Since primary data processing must be stopped, the performance of the entire system degrades. In some processors, all caches are invalidated after executing the cache flush instruction. If all caches are invalidated, all instructions and data must be read out from the main memory again to restart processing, resulting in an increase in overhead in restarting processing. Especially, the system for causing the processor to execute the cache flush instruction cannot employ a two-phase checkpoint scheme (checkpoint acquisition system (Japanese Patent Application No. 7-151739)) which is effective to shorten the cache flush time.
On the other hand, in the system using a cache flush unit, the cache flush unit has a storage section for holding address information associated with a modified block on the cache, and a time is wasted to search for the storage position of the modified block held by the storage section. That is, in checkpoint processing, addresses of all modified blocks must be sequentially read out from the recording means to execute cache flush, and searching for the storage positions of the modified blocks takes a considerable time. This increases overhead especially in checkpoint processing.
BRIEF SUMMARY OF THE INVENTION
Accordingly, it is an object of the present invention to provide a cache flush unit and method which implement fast cache flush and decrease the overhead in checkpoint processing.
According to one aspect of the present invention, there is provided a cache flush unit for use in a computer system having at least one processor with a cache, comprising first storage means for storing address information, associated with modified blocks of caches of all processors, in entries in units of cache lines, and second storage means for storing information to be used to search for an index of one of the entries on the first storage means, one entry containing an address of at least one modified block, wherein the address of the modified block is quickly read out by using the information in the second storage means.
According to another aspect of the present invention, there is provided a cache flush unit for use in a computer system having at least one processor with a cache, comprising first storage means for storing address information, associated with modified blocks of caches of all processors, in entries in units of cache lines, and second storage means for storing, as information to be used to search for an index of one of the entries on the first storage means, one entry containing an address of at least one modified block, data having a value obtained by ORing modified bits of all processors in the entries together with the index, wherein the address of the modified block is quickly read out by using the information in the second storage means.
The cache flush unit may further comprise a first index counter used to search for each index stored in the first storage means in cache flush, and a second index counter used to search for each index stored in the second storage means in cache flush, and the index counters may be selectively used in accordance with a cache flush scheme.
In the cache flush unit, data may be written in the second storage means in units of bits in updating the information.
The cache flush unit may further comprise a write-back buffer group having two hierarchies to sequentially hold write-back requests for the modified blocks, a first hierarchy may have two buffers. One is cache flush processing buffer which is used for cache flush transactions and the other is normal processing buffer which is used for bus transactions issued by processors or other bus agents, and a second hierarchy may have a common buffer.
The cache flush unit may further comprise means for limiting a speed for sending write-back requests for the modified blocks in cache flush.
In the cache flush unit, the data stored in the second storage means may have a plurality of bits holding a plurality of values obtained by ORing the modified bits and also have another bit holding a value obtained by ORing values of the plurality of bits.
In the cache flush unit, only when the OR of the modified bits changes in updating information in the first storage means in normal processing, updating of the information in the second storage means may be requested.
In the cache flush unit, an address map of the information stored in the second storage means may be mapped from a most significant bit side of the index in the first storage means.
In the cache flush unit, index match (index conflict) in the second storage means may be decreased by searching the index in the first storage means using data obtained by replacing upper bits and lower bits of an index output from the first index counter.
The cache flush unit may further comprise means for dynamically switching a cache capacity managed by the first storage means so that the cache capacity is increased to suppress degradation in system performance before switching, and the cache capacity is decreased to shorten a cache flush time after switching.
The cache flush unit may further comprise means for dynamically switching a modified block storage area of the cache managed by the first storage means so that the address information is managed using areas of all processors before switching, and the address information is managed using a storage area of one processor after switching, thereby decreasing an apparent cache capacity.
In the cache flush unit, index match (index conflict) in the second storage means may be decreased by searching the index in the first storage mean
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Kabushiki Kaisha Toshiba
Moazzami Nasser
Yoo Do Hyun
LandOfFree
Cache flush unit 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 flush unit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache flush unit will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2887833