Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus access regulation
Reexamination Certificate
1999-11-09
2002-11-12
Ray, Gopal C. (Department: 2181)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus access regulation
C709S241000, C370S450000, C710S105000
Reexamination Certificate
active
06480915
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention generally relates to processing of global operations in multiprocessor systems and in particular to employing tokens to permit speculative execution of global operations within multiprocessor systems. Still more particularly, the present invention relates to implementing a bus protocol and token manager employing tokens for speculative execution of global operations within a multiprocessor system.
2. Description of the Related Art
Many operations performed within multiprocessor systems may be executed locally by a single processor without immediately involving or affecting other processors within the system. For example, a processor may write a modified cache line to a local cache without making the write operation immediately visible to all other processors. A write-back of the modified data to system memory may be deferred until a later time or combined, through a modified intervention, with a subsequent read operation by a different processor for the same cache line.
However, processors within multiprocessor systems periodically execute operations which must be globally visible to all other processors within the system. By their nature, these operations require the involvement of all other processors. For example, within the PowerPC architecture, a processor may execute an instruction cache clock invalidate (ICBI), translation lookaside buffer invalidate (TLBI), or synchronization (SYNCH) operation. A synchronizing operation, for instance, may be employed to allow prior instructions within an instruction stream executing on a pipelined, out-of-order multiprocessor system to complete before performing a context switch.
Existing designs for multiprocessor systems support global operations by implementing a queue for such operations within each processor for every other processor within the system. That is, a processor within a system havign three other processors will include three queues for snooping global operations. The depth of each snoop queue will equal the latency of the combined response in order to prevent system livelocks. Thus, where a system requires five bus cycles to generate a combined response to an address transaction, the global operation queues will have a pipeline which is five levels deep.
This approach to supporting global operations is extremely hardware intensive and is not scalable. As the operating frequency and the number of processors within a system increases, driving the latency of a combined response up to close to 100 cycles, the approach described above becomes unwieldy. As the window for the combined response becomes larger, snooper implementations become more complex and costly.
It would be desirable, therefore, to to broadcst global operations in a highly scalable multiprocessor system while keeping masters and snoopers as simple as possible but also preventing system livelocks. It would also be desirable to decouple the depth of snoop queues from the width of address to combined response windows, and to maintain high frequency oepration while increasing the number of processor in a system supporting global operations.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to provide improved processing of global operations in multiprocessor systems.
It is another object of the present invention to provide a mechanism for employing tokens to permit speculative execution of global operations within multiprocessor systems.
It is yet another object of the present invention to provide a bus protocol and token manager employing tokens for speculative execution of global operations within a multiprocessor system.
The foregoing objects are achieved as is now described. Serialization of global operations within a multiprocessor system is achieved utilizing a single token, requiring a bus master to acquire the token for completion of each individual global operation initiated by that bus master. A combined token and operation request, in which a token request and an operation request are transmitted in a single bus transaction, is employed once for a global operation, to initiate the global operation for the first time. A token manager determines whether the token is available or checked out and responds to the token portion of the combined request. Snoopers respond to the operation portion of the combined request depending on whether they are busy. If the entire combined request is retried, a token request (only) is employed to request the token and, when the token is acquired, an operation request (only) is employed to request the operation. If the token portion of the combined request is acknowledged but the operation portion is retried, an operation request (only) is transmitted. If the entire combined request is acknowledged or once a subsequent operation request is acknowledged, which implies release of the token, the operation is treated as completed. Snoopers speculatively process the operation for the combined request if not busy. The token manager allows only one bus master to own the token at a time, and infers release of the token from a combined response acknowledging a combined request or an operation request.
The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 4870704 (1989-09-01), Matelan et al.
patent: 5568620 (1996-10-01), Sarangdhar et al.
patent: 5682512 (1997-10-01), Tetrick
patent: 5761734 (1998-06-01), Pfeffer et al.
patent: 5774700 (1998-06-01), Fisch et al.
patent: 5852747 (1998-12-01), Bennett et al.
patent: 5903738 (1999-05-01), Sarangdhar et al.
patent: 6079013 (2000-06-01), Webb et al.
patent: 6119219 (2000-09-01), Webb et al.
patent: 6141743 (2000-10-01), Strongin
Arimilli Ravi Kumar
Dodson John Steven
Joyner Jody B.
Lewis Jerry Don
Bracewell & Patterson L.L.P.
International Business Machines - Corporation
Ray Gopal C.
Salys Casimer K.
LandOfFree
Bus protocol and token manager for SMP execution of global... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Bus protocol and token manager for SMP execution of global..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bus protocol and token manager for SMP execution of global... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2976768