Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus access regulation
Reexamination Certificate
1998-12-03
2001-06-05
Lefkowitz, Sumati (Department: 2181)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus access regulation
C710S120000
Reexamination Certificate
active
06243781
ABSTRACT:
BACKGROUND INFORMATION
This invention is generally related to computer systems and more particularly to techniques for avoiding deadlock when performing bus transactions from an outbound pipe of a bridge.
Computer systems use a bridge between two buses to allow devices on one bus to communicate with devices on the other bus.
FIG. 1
shows such a conventional computer system
102
which complies with the popular
Peripheral Components Interconnect (PCI) Specification
, Revision 2.1, Jun. 1, 1995. The system
102
has a processor
104
, which in certain cases is called the host processor, coupled to a host bus
105
. A memory
112
normally comprising Dynamic Random Access Memory (DRAM) stores programs to be executed by the processor. The memory can be accessed by the processor
104
via a chip set
108
which provides transfer logic for transactions between the host bus
105
and a PCI bus
116
and between the PCI bus
116
and the memory
112
. An I/O bridge
124
gives access to a legacy bus
128
.
The following example illustrates the problem of deadlock encountered when performing multiple types of bus transactions. The chip set
108
can process multiple transactions using a pipe.
FIG. 2
shows the status of an inbound pipe
130
and an outbound pipe
134
. Also shown are outbound pipes
138
and
142
in the I/O bridge
124
and PCI device
120
, respectively. The pipes contain several pending requests for transactions which have resulted in a deadlock condition.
Each outbound pipe has a number of entries where each entry can hold transaction information (e.g., request packets containing target address and command information) and transaction data (e.g., data packets containing the transaction data) for posted and non-posted transactions. Posted writes include P-Writes
1
through
3
. P-Writes
1
and
2
were initiated by the processor
104
and are directed at a target, e.g. the I/O bridge
124
or the PCI device
120
, on the PCI bus
116
. P-Writes
1
and
2
are known as downstream transactions. In contrast, P-Write
3
was initiated on the legacy bus
128
and is directed at the main memory
112
. Thus, P-Write
3
is an upstream transaction. Examples of non-posted transactions are NP Read
1
in pipe
134
and NP Read
2
in pipe
142
. An outbound pipe may also hold return data (as data packets) for a non-posted transaction, such as Read Return
1
a
and
1
b
in pipe
138
, Read Return
2
in pipe
134
, and Read Return
1
in pipe
142
.
Normally, each PCI resource has both an inbound and outbound pipe. The inbound pipe
130
is used to store request packets for upstream non-posted read transactions, return data for downstream non-posted transactions (e.g., Read Return
1
a
for NP Read
1
in the chip set
108
), and requests and associated data for upstream posted write transactions. All of the read return data, as specified in the non-posted read transaction, must be received by the chip set and held in an inbound pipe before it is made available to the processor which returns to fetch it.
Although not yet completed, P-Write
3
is targeting the chip set
108
such that the data for this transaction would be stored in the inbound pipe
130
when completed. The transaction information and data stored in the inbound and outbound pipes are processed in a first in first out (FIFO) manner. Thus, for example, in outbound pipe
134
, NP Read
1
must be completed before any subsequent transactions or data, such as P-Write
1
, in the pipe
134
can be performed on the PCI bus
116
.
Two different deadlock conditions are illustrated in FIG.
2
. In the first deadlock condition, the pipe
134
has requested read data for the NP Read
1
transaction, directed at the I/O bridge
124
. The outbound pipe
138
of the bridge
124
has delivered part of the read data as Read Return
1
a
to the inbound pipe
130
. However, the second part of the read data, Read Return
1
b
, became available after P-Write
3
was enqueued in the pipe
138
. Thus, any further requests for NP Read
1
by the outbound pipe
134
will be signaled a retry, because P-Write
3
is blocking the pipe
138
. Also, any requests for P-Write
3
by the pipe
138
are signaled a retry, because NP Read
1
is blocking the inbound pipe
130
. As a result, no data can be transferred to or from the chip set
108
and the I/O bridge
124
.
The second deadlock condition illustrated in
FIG. 2
occurs when NP Read
1
is directed at PCI device
120
rather than at the I/O bridge
124
. The Read Return
1
data for that transaction, however, became available after NP Read
2
was enqueued in the outbound pipe
142
of the PCI device
120
. Thus, any requests for NP Read
1
are signaled a retry, because NP Read
2
is blocking pipe
142
. Similarly, any requests for NP Read
2
are signaled a retry, because NP Read
1
is blocking pipe
134
. Once again, no data can be transferred to and from chip set
108
.
One way to avoid the above-described first deadlock condition is to configure a PCI resource as to preclude any posted write from entering the resource's outbound pipe when a non-posted read request has been received over the bus and read return data for that read have not all been completed to the requesting master. A different way to avoid the second deadlock condition is to configure the PCI resource to time out the NP Read at the head of its outbound pipe after a large number of retried attempts. Upon the time out event, the NP Read request packet is discarded from the head of the outbound pipe and the discard status is communicated to control logic at the other side of the pipe to re-issue the same NP Read request. However, the first deadlock-avoidance technique fails to make optimal use of the full capacity of the outbound pipe because the pipe is permitted to hold only the single, non-posted read return. The second deadlock avoidance technique described above is performance-limiting as it allows the NP Read transaction at the head of the outbound pipe to be fruitlessly attempted for a relatively long time at the expense of blocking progress of transactions behind the NP Read and causing the pipe to back up. Therefore, there is a need for a technique of avoiding deadlocks that makes efficient use of the outbound pipe.
SUMMARY
An embodiment of the invention is directed to a method of processing bus transactions by making at least one attempt to perform a first non-posted transaction from an outbound pipe, the outbound pipe having entries corresponding to at least one posted transaction and at least one non-posted transaction, the posted and non-posted transactions to be performed in a first-in first-out manner, bypassing the first transaction in response to it being rejected, performing at least one other transaction from the outbound pipe, and performing the first transaction after performing the other transactions.
These and other features as well as advantages of the different embodiments of the invention will be apparent by referring to the drawings, detailed description and claims below.
REFERENCES:
patent: 5524220 (1996-06-01), Verma et al.
patent: 5546546 (1996-08-01), Bell et al.
patent: 5613075 (1997-03-01), Wade et al.
patent: 5638534 (1997-06-01), Mote, Jr.
patent: 5694556 (1997-12-01), Neal et al.
patent: 5870567 (1999-02-01), Hausauer et al.
patent: 5938739 (1999-08-01), Collins et al.
patent: 5953538 (1999-09-01), Duncan et al.
patent: 6076130 (2000-06-01), Sharma
patent: 6085274 (2000-07-01), Seeman
patent: 6098134 (2000-08-01), Michels et al.
patent: 6138192 (2000-10-01), Hausauer
Solaris, E. & Willse, G., “PCI Platform Hardware Architecture,” PCI Hardware and Software Architecture & Design, 3rd Edition, Annabooks (1996), pp. 21-23.
Bogin Zohar
Gadagkar Ashish
Gandhi Wishwesh
Lent David D.
Trieu Tuong
Blakely , Sokoloff, Taylor & Zafman LLP
Intel Corporation
Lefkowitz Sumati
LandOfFree
Avoiding deadlock by storing non-posted transactions in an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Avoiding deadlock by storing non-posted transactions in an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Avoiding deadlock by storing non-posted transactions in an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2546641