Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-05-14
2001-11-20
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S136000, C711S160000
Reexamination Certificate
active
06321300
ABSTRACT:
FIELD OF THE INVENTION
This invention relates in general to computer systems having main and cache memories and in particular, to an apparatus and method for dynamically reconfigurable timed flushing of a queue of coalescing write buffers included in such a computer system.
BACKGROUND OF THE INVENTION
A queue of write buffers is commonly employed in cache designs to minimize central processing unit (CPU) pipeline stalls by queuing external bus write requests. Coalescing write buffers which coalesce, combine or merge writes before transmission are particularly useful to reduce the bus bandwidth requirements. Such write buffers allow temporally local writes to a limited number of small areas to be merged together before the data is sent to the external bus.
U.S. Pat. No. 5,561,780 describes a method and apparatus for combining uncacheable write data into cache-line-sized write buffers. As described therein, the uncacheable write data may be a stream of graphics data to be sent to an external frame buffer, or a string move or string write operation. A write buffer is evicted or flushed if the buffer is full of data or if new data is received which cannot be placed in a write buffer. The second situation occurs when all write buffers are allocated (i.e., already storing some data to be transmitted) and the new data cannot be merged into one of the allocated write buffers, because of an address mismatch. Such a situation is highly undesirable since it causes a CPU pipeline stall. Although data stored in partially filled write buffers may be evicted under certain circumstances including the occurrence of a synchronization fence, such provisions fail to guarantee the avoidance of the second situation described above.
SUMMARY OF THE INVENTION
Accordingly, two objects of the present invention are to provide an apparatus and method for dynamically reconfigurable timed flushing of a queue of coalescing write buffers to minimize pipeline stalls.
These and additional objects are accomplished by the various aspects of the present invention, wherein briefly stated, one aspect is an apparatus for dynamically reconfigurable timed flushing of a plurality of coalescing write buffers. Included in the apparatus are means for generating a time-out period inversely related to a count of allocated coalescing write buffers; means for determining a least recently written to allocated coalescing write buffer; and means for generating a signal to flush the least recently written to allocated coalescing write buffer when a period of time since the most recent write to one of the allocated coalescing write buffers exceeds the time-out period.
Another aspect of the invention is a method for dynamically reconfigurable timed flushing of a plurality of coalescing write buffers. The method starts by comparing an address of a buffered write operation against line addresses of allocated coalescing write buffers to determine whether there is a match. If there is a match, the method continues by writing at least a byte of data to corresponding byte locations in the allocated coalescing write buffer whose line address matched with the address of the buffered write operation; setting byte valid bits corresponding to the byte locations; resetting a counter associated with the allocated coalescing write buffer and employed to determine whether a time-out period has expired for the allocated coalescing write buffer; and activating a flip-flop input associated with the allocated coalescing write buffer for determining a least recently written to allocated coalescing write buffer.
On the other hand, if there is no match, the method proceeds by newly allocating an unallocated coalescing write buffer for storing the address of the buffered write operation; updating a state of the newly allocated coalescing write buffer to indicate its allocation; changing the time-out periods for counters associated with all allocated coalescing write buffers; writing at least a byte of data to corresponding byte locations in the newly allocated coalescing write buffer; setting byte valid bits corresponding to the byte locations; resetting a counter associated with the newly allocated coalescing write buffer and employed to determine whether a time-out period has expired for the newly allocated coalescing write buffer; and activating a flip-flop input associated with the newly allocated coalescing write buffer for determining a least recently written to allocated coalescing write buffer.
Preferably, the method also includes the step of detecting whether a time-out period has expired for one of the allocated coalescing write buffers. If a time-out period has expired, then the method proceeds by checking the states of all coalescing write buffers to determine which ones are allocated; determining a least recently written to allocated coalescing write buffer from outputs of flip-flops having inputs associated with the allocated coalescing write buffers; and generating a signal to flush the least recently written to allocated coalescing write buffer.
Still another aspect of the invention is a write buffer unit configured to operate in conjunction with a cache memory in a microprocessor system. Included in the write buffer unit are a controller; a plurality of coalescing write buffers coupled to the controller; means, including the controller, for generating a time-out period inversely related to a number totaling the allocated coalescing write buffers; means, including the controller, for determining a least recently written to allocated coalescing write buffer; and means, including the controller, for generating a signal to flush the least recently written to allocated coalescing write buffer when a period of time initiated by a most recent write to one of the allocated coalescing write buffers exceeds the time-out period.
Additional objects, features and advantages of the various aspects of the present invention will become apparent from the following description of its preferred embodiments, which description should be taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 5664148 (1997-09-01), Mulla et al.
patent: 6049798 (2000-04-01), Bishop et al.
patent: 6078587 (2000-06-01), Lynch et al.
patent: 6130759 (2000-10-01), Blair
Cho James Y.
Ornes Matthew D.
Chace Christian P.
Kim Matthew
Oblon & Spivak, McClelland, Maier & Neustadt P.C.
Rise Technology Company
LandOfFree
Apparatus and method for dynamically reconfigurable timed... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for dynamically reconfigurable timed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for dynamically reconfigurable timed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2571595