Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1998-07-13
2001-01-23
Yoo, Do Hyun (Department: 2759)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S144000, C711S145000, C710S107000
Reexamination Certificate
active
06178485
ABSTRACT:
BACKGROUND
CROSS-REFERENCE TO RELATED APPLICATIONS
The present patent application is related to Ser. No. 09/004,144, entitled “METHOD AND APPARATUS FOR EXECUTING MULTIPLY-INITIATED MULTIPLY-SOURCED VARIABLE DELAY SYSTEM BUS OPERATIONS” (Attorney Docket No. AT997814) which is hereby incorporated by reference herein.
The present patent application is related to Ser. No. 09/004,137, entitled “METHOD AND APPARATUS FOR EXECUTING MULTIPLY-INITIATED, SINGLY-SOURCED VARIABLE DELAY SYSTEM BUS OPERATIONS” (Attorney Docket No. AT997808) which is hereby incorporated by reference herein.
The present patent application is related to Ser. No. 09/004,146, entitled “METHOD AND APPARATUS FOR EXECUTING SINGLY-INITIATED, MULTIPLY-SOURCED VARIABLE DELAY SYSTEM BUS OPERATIONS” (Attorney Docket No. AT997497) which is hereby incorporated by reference herein.
The present patent application is related to Ser. No. 09/004,148, entitled “METHOD AND APPARATUS FOR EXECUTING MULTIPLY-INITIATED, MULTIPLY-SOURCED VARIABLE DELAY SYSTEM BUS OPERATIONS” (Attorney Docket No. AT996271) which is hereby incorporated by reference herein.
The present patent application is related to Ser. No. 09/004,147, entitled “METHOD AND APPARATUS FOR EXECUTING VARIABLE DELAY SYSTEM BUS OPERATIONS OF DIFFERING CHARACTER USING SHARED BUFFERS” (Attorney Docket No. AT997496) which is hereby incorporated by reference herein.
The present patent application is related to Ser. No. 09/004,149, entitled “METHOD AND APPARATUS FOR EXECUTING SINGLY-INITIATED SINGLY-SOURCED VARIABLE DELAY SYSTEM BUS OPERATIONS” (Attorney Docket No. AT996272) which is hereby incorporated by reference herein.
1. Field of the Present Invention
The present invention generally relates to data processing systems, and more specifically, to methods and apparatuses residing in such systems that prevent the occurrence of deadlock from the execution of singly-initiated singly-sourced variable delay system bus operations.
2. History of Related Art
The evolution of the computer industry has been driven by the insatiable appetite of the consumer for ever increased speed and functionality. One species which has evolved from the above is the multi-processor computer.
Multi-processor systems, in similarity to other types of computer systems, have many different areas that are ripe for improvements. One such area is the processing of variable delay system bus operations.
Modern multi-processor systems typically include a number of processing elements, and a main memory, each of which are connected by a series of buses that ultimately terminate in a common system bus. The processing elements usually include a processor having a predetermined amount of on-board cache and, in some cases, a cache hierarchy. The cache hierarchy, typically, includes a number of caches (e.g. level 0-2) which are interposed between the processor and the common system bus.
In general, operations, in such multi-processor systems, are performed by the processor, residing at the top of the cache hierarchy, placing an operation on the bus between the processor and the first off-board cache. The first off-board cache then propagates the operation, if necessary, to the next lower level cache, if it exists, which then repeats the propagation down the cache hierarchy, if necessary, until the operation finally arrives at the system bus.
Once the operation has arrived at the system bus, it is then snooped by all the caches monitoring the system bus. After a snooping cache detects an operation, it must determine whether or not the execution of the snooped operation can proceed. A cache may be unable or refuse to accept (execute) a snooped operation for any number of reasons. For example, the resources necessary to execute an operation, such as the cache directory or state machines to process the snooped operation may be busy with other work and unable to process the snooped operation. In general, most system bus protocols allow any operation to be refused when a bus participant is unable to process the operation.
If the snooping cache cannot process the operation, then it will send a “RETRY” signal on the system bus. The RETRY signal informs the initiator of the operation that execution thereof was unsuccessful, and that the operation should be re-tried, if still necessary, at a later point in time.
The amount of time that a participant has in order to make a decision concerning the acceptance of a snooped operation, and to send a snoop response (e.g. “RETRY”) is usually fixed for any given system via the bus protocol. Unfortunately, there are certain operations, due to their very nature, for which it is essentially impossible to determine the snoop response in the fixed period set by most bus protocols.
In example, the PowerPC™ architecture uses a TLBSYNC operation which requires that all TLBIE operations previously issued by the processor issuing the TLBSYNC have completed on all other processors in the system. As a direct result of the above requirement, all other processors in the system must be polled in order to determine if the previously issued TLBIE operations have completed. In this case, the TLBSYNC operation must be propagated from the system bus to the top of each of the cache hierarchies to interrogate the other processors in the system. Those skilled in the art will readily recognize that a variable amount of time is required in order to propagate the TLBSYNC operation from the system bus to the processors at the top of each of the cache hierarchies. Thus making it extremely difficult, if not impossible, to determine the “correct” snoop response (e.g. “RETRY/No RETRY”) within the fixed time period set by most bus protocols.
It is just these types of operations which increase the likelihood of a deadlock occurring within the system. For example, assume that an operation is placed on the system bus by one participant (i.e. an initiator) and snooped by two other participants (recipients). During the first initiation of the operation, both recipients snoop the operation, transmit a “RETRY” signal on the system bus, and begin propagating the operation to the top of their respective cache hierarchies.
Note that recipients must initially respond RETRY. For the TLBIE/TLBSYNC example, it is possible that there are previously unfinished TLBIE operations present in other processors and the TLBSYNC cannot be allowed to complete in the event unfinished TLBIE operations exist in the processors. The lowest level cache cannot determine whether previous TLBIE operations are present until the processors at the top of each of the cache hierarchies have been polled.
In response to receiving the RETRY signals, the initiator waits a potentially variable period of time before re-initiating the operation. In the current example, also assume that before the initiator re-attempts the operation, the first snooper finishes the execution thereof, and the second snooper fails to complete the execution of the operation. Thus, the scenario for the occurrence of a deadlock is created.
After the operation is re-attempted (second time) by the initiator, the second snooper transmits a “RETRY” signal on the system bus. Since the first snooper has already completed the operation (as first initiated), it accepts the re-attempt as a new operation, thus beginning again the propagation of the operation to the top of its cache hierarchy.
In the current example, further assume that the second snooper has now completed the operation (first attempt), and the initiator now has, once again, re-attempted (third attempt) the operation on the system bus. In this scenario, the second snooper accepts the re-attempt as a new operation, and the first snooper transmits a “RETRY” signal on the system bus.
Further assume that the first snooper has completed the operation (second attempt). Once again, the initiator re-attempts (fourth time) the operation on the system bus, and the above noted process repeats indefinitely. This type of repetition is known in the industry as a “Ping-Pong deadlock”.
Note that, in general, a Ping-Pong deadlock scenario can exist
Arimilli Ravi Kumar
Kaiser Eileen T.
Kaiser John Michael
Williams Derek Edward
Henkler Richard A.
International Business Machines - Corporation
Kaiser Eileen T.
McBurney Mark E.
Namazi Mehdi
LandOfFree
Method and apparatus for executing singly-initiated,... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for executing singly-initiated,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for executing singly-initiated,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2541565