Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2001-08-09
2004-10-26
Padmanabhan, Mano (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S119000, C711S152000, C707S793000, C710S200000
Reexamination Certificate
active
06810464
ABSTRACT:
A portion of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to multiprocessor computer system architecture and more particularly to systems and methods for reducing access time to memory cells containing highly utilized locks in order to improve throughput.
2. Background Information
In U.S. Pat. No. 6,052,760, issued to Bauman et al, (and commonly assigned to Unisys Corporation with the instant patent and hereby incorporated herein in its entirety by this reference), a system for providing identifiable software locks in a multiprocessor system with a memory hierarchy having independently functioning data caches and a main memory is described. This Bauman system required significant processing cycle time for discovering whether data was locked, if the data was owned by remote processors in Bauman's system. The instant invention overcomes this significant limitation.
Other systems for providing locks over data in multiprocessor systems having first and second level caches are described in U.S. Pat. Nos. 6,006,299 issued to Wang et al, and 5,175,837 issued to Amold et al, both of which are also incorporated herein by this reference. Arnold provides a lock directory in a single system controller unit (SCU) which handles the entire main memory but in granularity like that of the “CPU cache block” as opposed to providing a single lock bit for each location in the main memory. The directory in the SCU of Arnold is defined by a plurality of lock bits a particular one of which is interrogated to determine if a lock request should be granted, and which notifies a requesting port of the denial if denied, and which sets the particular bit if the lock request is granted, locking the entire cache-sized memory area for the requestor. In a multiprocessor system of indeterminate number of instruction processors (because they may be swapped out for repair, or because the basic design does not change with increase or decrease of processor number), it is an awkward construction to provide a single SCU type controller to funnel all memory lock requests through. Too, with systems that have cross-bar interconnects between each processor and the entire main memory unit, instead of busses between main memory and the instruction processors and their caches, the bottleneck of such an arrangement is not tolerable in its affect on overall performance since it would force all calls for locks on areas of memory through a single pathway.
These Bauman and Arnold patents appear to be relevant to a different level of lock than is this disclosure. The Bauman and Arnold patents are not setting software locks, per se, rather those patents appear to be describing a decision process for which processors may attempt locking-type instructions on the addressed memory.
U.S. Pat. No. 6,148,300, Singhal et al, (incorporated herein by this reference) describes some of the problems associated with locks and how to handle multiple waiting contenders for software locks. While it describes the problems well and the prior art, it handles contention by allocation, rather than managing to avoid some of the problem altogether. Another U.S. Patent, No. 5,875,485, Matsumoto (hereby also incorporated by reference) uses the standard system bus for transmitting lock information and appears to require transmission of all information with a lock when a lock is moved.
Locking-type instructions are indivisible: that is, the processor must be able to test the value, and depending on the results of the test, set a new value. These patents are setting a “hardware lock” to permit the lock instructions to execute indivisibly. When the lock instruction completes, whether it was successful or unsuccessful, the “hardware lock” is cleared. This permits only one processor to execute a lock instruction on one location at a time; multiple processors can execute lock instructions at the same time if the locks are affecting different addresses-or in the case of Amold-affecting different cache lines.
So, the “hardware lock” is set and cleared for the duration of the lock instruction. Software still must determine the result of its lock instruction to see if the lock is locked. The hardware lock is “up” (“up” is just a state which can have various other names such as “active” or “set”) for just a couple of cycles while the lock instruction executes. A software lock may be up for a few instructions, or the software lock may be up for thousands of instructions. (If each hardware lock instruction is a couple of cycles, then the software lock must be up for twice that long just to lock and unlock the lock, and not counting any cycles for operations on associated data or of instructions streams while the software lock is locked).
Hardware locks and software locks, though closely related, are usually considered very different entities, but identifying the above-referenced patents permits a useful description of the background for this invention.
This patent teaches a way for hardware to allow only one processor to execute a lock instruction on a location at a time and to have hardware know the result of the software lock as one combined operation.
Accordingly, a system for quickly handling lock requests in a multi-tiered memory, multi-processor system where each instruction processor has direct access to the main memory through its hierarchy of caches is desired.
Additionally, in use of two second level cache machines with a central main memory and third level caches, somewhat less than but approximating half the time a memory segment is called for, the item needed is in the distant cache. This causes longer access times and hence a reduction in performance of around 10%. The concern for larger scale machines, with many more instruction processors and many more caches, is that if we see a 10% decrease in performance using two caches, the effect of 16 or 32 caches is very likely to be much worse. Even worse performance can be found in machines where particular areas need to be used over and over by all the processors, such as shared data structure segments that contain commonly used with operating system functions like dispatching queues and buffer allocation functions.
So, there is clearly a need for improvement not addressed in the prior art.
REFERENCES:
patent: 5175837 (1992-12-01), Arnold et al.
patent: 5551046 (1996-08-01), Mohan et al.
patent: 5586331 (1996-12-01), Levenstein
patent: 5590326 (1996-12-01), Manabe
patent: 5761712 (1998-06-01), Tran et al.
patent: 5875485 (1999-02-01), Matsumoto
patent: 5983225 (1999-11-01), Anfindsen
patent: 6006299 (1999-12-01), Wang et al.
patent: 6052760 (2000-04-01), Bauman et al.
patent: 6078982 (2000-06-01), Du et al.
patent: 6108654 (2000-08-01), Chan et al.
patent: 6148300 (2000-11-01), Singhal et al.
patent: 6189078 (2001-02-01), Bauman et al.
patent: 6405274 (2002-06-01), Chan
patent: 6473819 (2002-10-01), Jackson et al.
patent: 6496909 (2002-12-01), Schimmel
patent: 6546443 (2003-04-01), Kakivaya et al.
patent: 2002/0065968 (2002-05-01), Bryant et al.
Mitchell A. Bauman et al., filed Aug. 30, 2000, Leaky Cache Mechanism, U.S. patent application Ser. No. 09/650,730.
Sipple Ralph E.
Ward Wayne D.
Atlass Michael B.
Padmanabhan Mano
Song Jasmine
Starr Mark T.
Unisys Corporation
LandOfFree
Multiprocessor computer system for processing communal locks... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiprocessor computer system for processing communal locks..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiprocessor computer system for processing communal locks... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3329661