Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1997-08-26
2002-12-03
Bragdon, Reginald G. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S143000, C711S144000, C711S146000, C714S013000
Reexamination Certificate
active
06490657
ABSTRACT:
BACKGROUND OF THE INVENTION
This application is based on Japanese Patent Application No. 8-238,157, filed Sep. 9, 1996, the content of which is incorporated herein by reference.
The present invention relates to a cache flush apparatus for a cache memory having a snoop mechanism for maintaining data coherency and a fault tolerant computer system having the cache flush apparatus.
In general, a modern high-speed processor has a cache memory for temporarily holding data required by the processor in order to reduce the effective memory access latency. A cache memory holds data and the memory address at which the data is read out in a fixed size data storage unit called a cache block.
In a computer (more specifically a multi-processor computer) having a plurality of processors each of which has its own cache memory, a snoop mechanism is usually used to maintain data coherency among the cache memories. A snoop mechanism monitors the system bus to detect bus commands and if a bus command which requires some action of the cache memory is detected, the snoop mechanism does the required action such as replying to the bus command with data held in one of its cache blocks, discarding data in one of its cache blocks and the like.
The cache memory is classified into copy-back type and write-through type. While a write-through type cache memory writes back data into the main memory immediately when it is updated within the cache memory, a copy-back type cache memory postpones the write-back of data until it becomes necessary. Therefore, for a copy-back type cache memory, a cache block may hold updated data which has not been written back into the main memory yet. Such a cache block is called a dirty block and the state of such a cache block is called dirty.
A copy-back type cache memory requires a cache flush operation which writes back all the data updated solely within the cache memory into the main memory.
For example, data transfer between an input/output device without a memory coherency mechanism and the main memory requires a cache flush before the data transfer in order to assure that the main memory holds valid data. From now on, a “cache memory” means a copy-back type cache memory.
A cache flush is also necessary for a main memory based checkpoint/rollback type fault tolerant computer. Such a fault tolerant computer periodically creates a checkpoint within its main memory. When the computer detects some faults during the normal data processing, the computer rolls back its internal state to the most recent checkpoint and then restarts the normal data processing.
Since a checkpoint image created within the main memory should contain sufficient information to restart the normal data processing, it is necessary to perform a cache flush as a part of checkpoint creation.
A cache flush is usually performed by using machine instructions provided by the processor.
Intel Pentium™ processor and its successors, for example, provide a “wbinvd” (writeback & invalidate) instruction. The instruction writes back data of all the dirty blocks into the main memory and sets the state of every cache block invalid. Therefore, when a cache flush has been performed by executing the “wbinvd” instruction as a part of checkpoint creation, cache misses occur very frequently during the normal data processing which follows the checkpoint creation.
MIPS R4000™ processor, for example, provides a “secondary cache hit writeback” instruction. The operand of the instruction, different from the case of the “wbinvd” instruction, is a single cache block. The following is a sample program of a cache flush operation.
fcflush
li $4, 0
# start block address
li $5, CACHE_SIZE
# the number of blocks
loop:
cache
0xlb, 0($4)
# 2nd cache hit writeback
addu
$5, $5, 01
# decrement loop counter
bne
$5, 0, loop
#
addiu
$5, $4, 64
# increment block address
j
$31
# return subroutine
nop
With the foregoing program, “cache 0x1b, 0($4)” is the “secondary cache hit writeback” instruction. The instruction checks the state of the cache block of a secondary cache memory designated by the contents of the fourth register ($4). If the state is dirty, the data of the cache block is written-back into the main memory and the state of the cache block turns “clean-exclusive” or “shared”. The loop should be repeated as many as the number of the cache blocks of the secondary cache memory even if the number of dirty blocks is small. It should be mentioned that the execution time of a cache instruction is usually much longer than that of an ordinary instruction such as an arithmetic instruction.
SPARC V9™ processor does not provide any instruction for a cache flush. If a cache flush is necessary, a load instruction should be used so that the data within a dirty block is replaced by the data newly loaded into the cache block. Therefore, the inefficiency of a cache flush is apparently more critical than the case of Intel Pentium processor.
To accelerate a cache flush operation has been a concern for designers of a main memory based checkpointrol/back type fault-tolerant computer. Japanese patent disclosure (KOKAI) No. 5-6308, “Cache controller, fault tolerant computer and data transfer method”, Mitsubishi Denki Co. Ltd., proposed a cache controller with additional memory for storing the memory address at which a piece of data is updated. In a cache flush operation, while a conventional cache controller checks the state of every cache block and, if it is dirty, writes back the data held in the cache block, the proposed cache controller can use the addresses stored in the additional memory effectively. However, this method has a critical disadvantage that it requires a major modification of the present cache controller design, which is too costly.
BRIEF SUMMARY OF THE INVENTION
In view of the foregoing, the primary object of the present invention is to provide a cache flush apparatus applicable to a variety of commercial high speed microprocessors having cache memories. The cache flush apparatus, attached to the system bus, maintains the memory addresses held in dirty blocks within its own storage during the normal data processing. When a cache flush is required, the cache flush apparatus reads the memory addresses from the storage efficiently and issues bus commands each of which requires to write back data held in one of the dirty blocks. As a result, a dirty block becomes “shared” and it still holds the same data. For a non-dirty cache block, it remains unchanged.
According to a first aspect of the present invention, there is provided a cache flush apparatus for use in a computer having at least one processor provided with a copy-back type cache memory having a bus snoop mechanism, a main memory and a system bus for connecting the at least one processor and the main memory, the cache flush apparatus comprising:
update address registering means for monitoring the system bus to detect an update of data within the cache memory, selecting a region of the update address storage means according to a memory address MU at which the data has been updated and an identifier of a processor which has updated the data and storing the memory address MU as an update address in one of the entries of the selected region;
update address removing means for monitoring the system bus to detect a write-back of data from a dirty block, selecting a region of the update address storage means according to a memory address MW at which the data has been written back and an identifier of a processor from which the data has been written back, and removing the update address which is equal to the memory address MW and is stored in an entry of the selected region; and
flush executing means, in response to a request from the at least one processor, for issuing bus commands to the system bus each of which has one of the update addresses UA stored in the update address storage means and causes a write-back of data from the dirty block designated by the update address UA.
According to the first aspect of the present invention, the address of data held in a dirty b
Kano Takuya
Masubuchi Yoshio
Sakai Hiroshi
Bragdon Reginald G.
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
LandOfFree
Cache flush apparatus and computer system having the same 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 apparatus and computer system having the same, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache flush apparatus and computer system having the same will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2944760