Cache coherency arrangement to enhance inbound bandwidth

A cache coherency arrangement with support for pre-fetch ownership, to enhance inbound bandwidth for single leaf and multiple leaf, input-output interfaces, with shared memory space is disclosed. Embodiments comprise ownership stealing to enhance inbound bandwidth and to prevent or attenuate starvation of transactions or of an input-output interface for transactions.

FIELD OF INVENTION

The present invention is in the field of cache coherency. More particularly, the present invention provides a method, apparatus, system, and machine-readable medium for cache coherency with support for pre-fetch ownership, to enhance inbound bandwidth for single leaf and multiple leaf, input-output interfaces, with shared memory space.

BACKGROUND

Coherent transactions limit the bandwidth for transactions from a peripheral input-output (I/O) bus in processor-based systems such as desktop computers, laptop computers and servers. Processor-based systems typically have a host bus that couples a processor and main memory to ports for I/O devices. The I/O devices, such as Ethernet cards, couple to the host bus through an I/O controller or bridge via a bus such as a peripheral component interconnect (PCI) bus. The I/O bus has ordering rules that govern the order of handling of transactions so an I/O device may count on the ordering when issuing transactions. When the I/O devices may count on the ordering of transactions, I/O devices may issue transactions that would otherwise cause unpredictable results. For example, after an I/O device issues a read transaction for a memory line and subsequently issues a write transaction for the memory line, the I/O device expects the read completion to return the data prior to the new data being written. However, the host bus may be an unordered domain that does not guaranty that transactions are carried out in the order received from the PCI bus. In these situations, the I/O controller governs the order of transactions.

The I/O controller places the transactions in an ordering queue in the order received to govern the order of inbound transactions from an I/O bus, and waits to transmit the inbound transaction across the unordered interface until the ordering rules corresponding to each transaction are satisfied in the ordering queue. However, when multiple I/O devices transmit coherent transactions to the I/O controller, transactions unnecessarily wait in the ordering queue for coherent transactions with unrelated ordering requirements.

I/O devices continue to demand increasing bandwidth and unnecessary delay for transactions in an ordering queue is particularly wasteful. A conventional way to meet increasing demand for bandwidth is to increase the number of ports available for I/O devices at the I/O controller or memory controller for main system memory. The increase in ports, however, increases complexity and cost of such a memory controller and drives up overall system cost. Further, products with multiple ports may share memory space. When ports share the same memory space, I/O traffic is forwarded to an ordering queue to maintain transaction ordering as well as to avoid conflicts between accesses to shared memory space. Although bandwidth of the I/O controller may be increased, problems of unnecessary delay, complexity, and cost are compounded.

DETAILED DESCRIPTION OF EMBODIMENTS

The following is a detailed description of example embodiments of the invention depicted in the accompanying drawings. The example embodiments are in such detail as to clearly communicate the invention. However, the amount of detail offered is not intended to limit the anticipated variations of embodiments. The variations of embodiments anticipated for the present invention are too numerous to discuss individually so the detailed descriptions below are designed to make such embodiments obvious to a person of ordinary skill in the art.

Referring now toFIG. 1, there is shown an embodiment of a system to transact between an ordered and an unordered interface. The embodiment may comprise processors such as processors100,105,120, and125; processor interface circuitry, such as scalable node controllers110and130; memory114and134; input-output (I/O) hub circuitry, such as I/O hub140and I/O hub180; and I/O devices, such as bridges160,170, and190. In embodiments that may comprise more than one I/O hub, such as I/O hub140and I/O hub180, support circuitry for multiple I/O hubs may couple the processor interface circuitry with the multiple hubs to facilitate transactions between I/O hubs140and180and processors100,105,120, and125.

Scalable node controllers110and130may couple with processors100and105, and120and125, respectively, to apportion tasks between processors100,105,120, and125. In some of these embodiments, scalable node controller110may apportion processing requests between processor100and processor105, as well as between processors100and105and processors120and125, for instance, based upon the type of processing request and/or the backlog of processing requests for processors100and105and processors120and125.

In several embodiments, scalable node controller110may also coordinate access to memory114between processors,100and105, and I/O hubs,140and180. Support circuitry for multiple I/O hubs, scalability port switches116and136, may direct traffic to scalable node controllers110and130based upon a backlog of transactions. In addition, scalability port switches116and136may direct transactions from scalable node controllers110and130to I/O hubs140and180based upon destination addresses for the transactions. In many embodiments, memory114and memory134may share entries, or maintain copies of the same data. In several embodiments, memory114and memory134may comprise an entry that may not be shared so a write transaction may be forwarded to either memory114or memory134.

I/O hubs140and180may operate in a similar manner to bridge transactions between an ordered transactional domain and an unordered transactional domain by routing traffic between I/O devices and scalability ports. In some embodiments, I/O hubs140and180may provide peer-to-peer communication between I/O interfaces. In particular, I/O hub140may comprise unordered interface142, upbound path144, snoop filter146, a first leaf147comprising hub interface148and input-output interface150; and second leaf151comprising hub interface152and input-output interface154.

Unordered interface142may facilitate communication between I/O hub140and a scalable node controller such as110and130with circuitry for a scalability port protocol layer, a scalability port link layer, and a scalability port physical layer. In some embodiments, unordered interface142may comprise simultaneous bi-directional signaling. Unordered interface142may couple to scalability port switches116and136to transmit transactions between scalability node controllers110and130and agents162,164, and172. Transactions between unordered interface142and scalability node controllers110and130may transmit in no particular order or in an order based upon the availability of resources or ability for a target to complete a transaction. Transmission order may not be based upon, for instance, a particular transaction order according to ordering rules of an I/O interface, such as a PCI bus. For example, when agent162may initiate a transaction to write data to a memory line, agent162may transmit four packets to accomplish the write. Bridge160may receive the four packets in order and forward the packets in order to input-output interface150. Hub interface148may maintain the order of the four packets to forward to unordered interface142via upbound path144. Scalability port switch116may receive the packets from unordered interface142and transmit the packets to memory114and memory134.

Upbound path144may comprise a path for hub interfaces148and152to issue transactions to unordered interface142and to snoop filter146. For example, upbound path144may carry inbound coherent requests to unordered interface142, as well as ownership requests and read cache entry invalidations from hub interfaces148and152to snoop filter146. In many embodiments, upbound path144may comprise a pending transaction buffer to store a pending transaction on unordered interface142until a scalability port switch116or136may retrieve or may be available to receive the pending transaction.

Further, when an I/O hub such as I/O hub140may couple more than one I/O interface,150and154, to scalability port switches116and136, I/O hub140may comprise arbitration circuitry to grant access of upbound path144to transactions of first leaf147and second leaf151. In many embodiments, arbitration circuitry may provide substantially equivalent access to unordered interface142. In other embodiments, arbitration circuitry may arbitrate between first leaf147and second leaf151based upon a priority associated with, or an agent coupled with, first leaf147and/or second leaf151.

Snoop filter146may issue ownership requests on behalf of transactions in hub interfaces148and152, return ownership completions to hub interfaces148and152, monitor pending transactions on unordered interface142, and respond to downbound snoop requests from unordered interface142or from a peer hub interface. In addition, snoop filter146may perform conflict checks between snoop requests, ownership requests, and ownerships of memory lines in memory114or memory134. For example, a write transaction waiting at hub interface148to write data to memory line one in memory114may reach a top of an ordering queue in hub interface148. After the write transaction may reach the top of the queue, hub interface148may request ownership of memory line one for the write transaction via snoop filter146. Snoop filter146may perform a conflict check with the ownership request and determine that the ownership request may conflict with the ownership of memory line one by a pending write transaction on unordered interface142. Snoop filter146may respond to the ownership request by transmitting an invalidation request to hub interface148.

Subsequently, hub interface148may reissue a request for ownership of memory line one for the write transaction and snoop filter146may perform a conflict check and determine that no conflict exists with an ownership by the write transaction. Then, snoop filter146may transmit a request for ownership to scalable node controller110via scalability port switch116. In response, snoop filter146may receive an ownership completion for memory line one and may return the ownership completion to hub interface148. In many embodiments, hub interface148may receive the ownership completion for a transaction and may modify the coherency state of the transaction to ‘exclusive’. In several of these embodiments, snoop filter146may maintain the coherency state of the transaction in a buffer.

Hub interfaces148and152may operate in a similar manner, to forward transactions from I/O interfaces150and154to unordered interface142. Hub interfaces148and152may maintain a transaction order for transactions received via I/O interfaces150and154in accordance with ordering rules associated with bridge160and bridge170, respectively. Hub interfaces148and152may also determine the coherency state of transactions received via I/O interfaces150and154. For example, hub interface148may receive a write transaction from agent164via bridge160and place the header for the write transaction in an inbound ordering queue, or, in some embodiments, an upbound ordering queue. Substantially simultaneously hub interface148may request ownership of the memory line associated the write transaction via snoop filter146. Requesting ownership when the write transaction may not satisfy ordering rules associated with I/O interface150, may be referred to as pre-fetching ownership. In alternate embodiments, when the inbound ordering queue is empty and no transactions are pending on unordered interface142, the write transaction may bypass the ordering queue and transmit to upbound path144to transmit across unordered interface142.

Snoop filter146may receive the request for ownership and perform a conflict check. In some instances, snoop filter146may determine a conflict with the ownership by the write transaction. Since the coherency state of the write transaction may be pending when received, snoop filter146may deny the request for ownership. After the transaction order of the write transaction may satisfy ordering rules, or in some embodiments after the write transaction reaches the top of the ordering queue, hub interface148may reissue a request for ownership and receive an ownership completion. In response to receiving the ownership completion for the write transaction, hub interface148may change the coherency state of the write transaction to ‘exclusive’ and then to ‘modified’. In some embodiments, when the transaction may be at the top of the ordering queue upon receipt of the ownership completion, hub interface148may change the coherency state of the write transaction directly to ‘modified’, making the data of the write transaction globally visible. In several embodiments, hub interface148may transmit the transaction header of the write transaction to snoop filter146to indicate the change in the coherency state to ‘modified’.

On the other hand, after hub interface148may receive the ownership completion in response to pre-fetching ownership, hub interface148may change the coherency state of the write transaction from a pending or non-ownership state to ‘exclusive’. Hub interface148may maintain the transaction in ‘exclusive’ state until the write transaction may satisfy associated ordering rules or the ownership may be invalidated or stolen. For example, ordering rules governing transactions received via bridge160from agent162may be independent or substantially independent from ordering rules governing transactions received from agent164. As a result, many embodiments allow a second transaction to steal or invalidate the ownership of the memory line by a first transaction to transmit to upbound path144when the ordering of the second transaction is independent or substantially independent from the ordering of the first transaction. Ownership stealing may prevent backup, starvation, deadlock, or stalling of the second transaction or the leaf comprising the second transaction as a result of the transaction order of the first transaction. In many of these embodiments, ownership may be stolen when the first transaction may reside in a different leaf from the second transaction and/or in the same leaf.

In the present embodiment, hub interface152may operate in a similar manner as hub interface148, but hub interface152may maintain a transaction order for transactions from bridge170according to ordering rules independent or substantially independent from ordering rules associated with hub interface148. As a result, the embodiment may take advantage of the unrelated transaction ordering between first leaf147and second leaf151by determining a coherency state for upbound transactions based upon a conflict and a transaction order, to take the ownership from the upbound transaction. For instance, agent172may initiate a write transaction to memory line one via bridge170and hub interface152may receive the write transaction. After hub interface152receives the write transaction, hub interface152may request ownership of memory line one via snoop filter146. The write transaction may receive an ownership completion although may also be placed in the bottom of an ordering queue of hub interface152. Agent162may request a read of memory line one of memory114and hub interface148may forward the read request to an ordering queue or a read bypass queue of hub interface148to maintain a transaction order according to an ordering rule associated with agent162. The read transaction for memory line one may reach the top of the ordering queue of hub interface148and may be forwarded to snoop filter146to initiate a conflict check before the write transaction may satisfy ordering rule(s) associated with agent172or reach the top of the ordering queue of hub interface152. In many of these embodiments, snoop filter146may comprise memory to store one or more read transactions or read transaction headers until the read transaction may be forwarded to unordered interface142and snoop filter146may apply back pressure to read transactions after a conflict between a read transaction received by snoop filter146may prevent the read transaction from being forwarded to unordered interface142. In alternative embodiments, snoop filter146may perform a conflict check before the read transaction or header of the read transaction may be forwarded to snoop filter146.

Snoop filter146may determine a conflict associated with the ownership of memory line one since the write transaction in hub interface152comprises ownership of memory line one. In response, snoop filter146may issue a request to invalidate the ownership by the write transaction in hub interface152. Hub interface152may determine that the transaction order of the write transaction still may not satisfy the ordering rules or the write transaction may not be at the top of the queue and may accept the invalidation of ownership, stealing or taking the ownership from the write transaction. Snoop filter146may respond to hub interface148with an indication that no conflicts exist and hub interface148may forward the read request to upbound path144. In alternative embodiments, after snoop filter146may determine a conflict and return a response to hub interface148indicating the conflict exists, hub interface148may reissue a request for the conflict check after snoop filter146receives an acceptance of the invalidation request from hub interface152for the write transaction.

In some embodiments, I/O hub140may comprise starvation circuitry to prevent starvation of a transaction or a leaf of transactions as a result of a determination of a coherency state for an upbound transaction based upon a conflict in the transaction order that invalidates ownership of a memory line by a transaction. For example, agent172may initiate a series of write transactions to memory line one of memory114. After the first, second, and third write transactions for agent172are queued in an ordering queue of hub interface152, agent162may initiate a fourth write transaction to memory line one of memory114and hub interface148may queue the fourth write transaction in an ordering queue of hub interface148. Ownership of memory line one may be pre-fetched for the first transaction. Hub interface148may then pre-fetch ownership for memory line one for the fourth write transaction. In response, snoop filter146may determine that ownership by the first write transaction may prevent the fourth write transaction from gaining ownership of memory line one.

After the fourth write transaction may reach the top of the ordering queue, hub interface148may reissue a request for ownership of memory line one. Snoop filter146may determine a conflict exists for the request with the first write transaction, which may be pending on unordered interface142, and deny the ownership request. Then, the first write transaction pending on unordered interface142may clear. However, arbitration circuitry of I/O hub140may grant access to upbound path144for hub interface152and hub interface152may comprise the second write transaction for memory line one which may change to a coherency state of ‘modified’. Hub interface148may reissue a request for ownership and snoop filter146may determine a conflict between the second write transaction, pending on unordered interface142. As a result, snoop filter146may deny the request for ownership by hub interface148again.

Starvation circuitry of I/O hub140may keep track of the number of denied requests for ownership by hub interface148. After the number of denied requests reaches a starvation count or limit, starvation circuitry may determine to take an action to prevent starvation of the fourth write transaction or of first leaf147. In some embodiments, the action of the starvation circuitry may stall inbound transactions to hub interfaces148and152via I/O interfaces150and154, to allow transactions in hub interface148and hub interface152to complete. In many embodiments, stalling inbound transactions may flush the upbound ordering queues of hub interfaces148and152. In other embodiments, starvation circuitry of I/O hub140may transmit a signal to arbitration circuitry of I/O hub140to provide a greater degree of access to upbound path144by hub interface148to prevent starvation. In one embodiment, starvation circuitry of snoop filter146may take more than one type of action to prevent starvation such as stalling inbound transactions to I/O interfaces150and154and/or modifying the degree of access to upbound path144that may be available to hub interface148.

In the present embodiment, bridges160,170and190, couple one or more agents162,164,172,192and194to I/O hubs140and180from an ordered transactional domain such as a peripheral component interconnect (PCI) bus, a universal serial bus (USB), and/or an infiniband channel. Agents162,164,172,192and194may transact upbound or peer-to-peer via I/O hubs140and180. In many of these embodiments, agents162,164,172,192, and194may transact with any processor and processors100,105,120, and125may transact with any agent.

Referring now toFIG. 2, there is shown an embodiment of an apparatus of an input-output hub to maintain ordering for transactions between an ordered transactional domain, I/O interfaces, and unordered transactional domain, unordered interface207. The embodiment may comprise unordered interface207, downbound snoop path200, upbound snoop path205, snoop filter210, coherency interface230, hub interface circuitry280, and upbound path220. Downbound snoop path200may comprise circuitry to transmit a snoop request from unordered interface207down to snoop filter210. Upbound snoop path205may provide a path between snoop filter210and a controller on the other side of unordered interface207to facilitate snoop request by snoop filter210and/or I/O devices coupled with leaves245,255,265and275. In some embodiments, upbound snoop path205may facilitate cache coherency requests. For example, a processor in the unordered transactional domain may comprise cache and snoop filter210may request invalidation of a cache line after a leaf such as leaf245may receive a write transaction for memory associated with that cache line.

Snoop filter210may comprise conflict circuitry218and buffer212. Conflict circuitry218may determine conflicts between downbound snoop requests, inbound read transactions, inbound write transactions, and upbound transactions. Further, conflict circuitry218may comprise circuitry to respond to downbound snoop requests. Conflict circuitry218may couple with buffer212to store the coherency states and associate the coherency states with entries in upbound ordering first-in, first-out (FIFO) queues240,250,260, and270.

Buffer212may comprise a reverse routing field to store locations of entries in ordering queues. For example, after snoop filter210may receive an ownership completion across unordered interface207, snoop filter210may use the reverse routing field, stored in buffer212when the request for ownership was issued, to forward the completion across coherency interface230to the target entry of an ordering queue, e.g. the entry in the upbound ordering FIFO queues240,250,260, and270with a write transaction header that is associated with the ownership request.

Further, conflict circuitry218may issue an invalidation request to hub interface circuitry280to invalidate an ‘exclusive’ coherency state of a transaction in an upbound ordering FIFO queue wherein the coherency state conflicts with ownership of the memory line by another transaction. For example, snoop filter210may receive a downbound snoop request via downbound snoop path200and conflict circuitry218may compare the address of the memory line associated with the downbound snoop request against addresses in buffer212. After conflict circuitry218may determine that a transaction in upbound ordering FIFO queue240may own the memory line, conflict circuitry218may initiate a request to invalidate the ownership, or ‘exclusive’ coherency state, using the reverse routing field. Conflict circuitry218may transmit the invalidation request via coherency interface230. Hub interface circuitry280may respond to the request to invalidate via coherency interface230, with an acceptance or rejection of the request. Conflict circuitry218may update a coherency state stored in buffer212accordingly.

Coherency interface230may relay internal coherency completion and invalidation requests from snoop filter210to hub interface circuitry280. These coherency requests may be generated by snoop filter210and may be the result of an ownership completion, a downbound snoop request, or an inbound coherent transaction. In some embodiments, coherency interface230may couple with buffer212to relay coherency requests. In particular, coherency interface230may couple with a reverse routing field in buffer212that addresses a specific entry in upbound ordering FIFO queues240,250,260, and270; and a request field of buffer212to indicate whether a transaction with hub interface circuitry280may be an ownership completion or an invalidation request. For example, after snoop filter210receives an ownership completion across unordered interface207, snoop filter210may use the routing field to forward the completion across coherency interface230to hub interface circuitry280. The ownership completion may be addressed to the entry in upbound ordering FIFO queue240,250,260, or270based upon an association stored in buffer212.

Further, coherency interface230may couple with a response field in buffer212to indicate whether hub interface circuitry280may accept or reject an invalidation request. For example, hub interface circuitry280may receive a first transaction, request ownership for a memory line associated with the first transaction, and place the header of the first transaction in upbound ordering FIFO queue240. After conflict circuitry218may determine a conflict associated with ownership of the memory line by the first transaction as a result of ownership by a second transaction in upbound ordering FIFO queue260, snoop filter210may issue an invalidation request for the second transaction. Coherency interface230may relay the invalidation request to hub interface circuitry280and address the request according to the contents of the reverse routing field in buffer212. Hub interface circuitry280may accept the invalidation of ownership and respond to the request with an indication of acceptance. As a result, coherency interface230may route the indication of acceptance to the response field.

Hub interface circuitry280may maintain ordering of an upbound transaction as specified by ordering rules, such as PCI ordering rules, and determine a coherency state of the upbound transaction. Hub interface circuitry280may comprise upbound ordering FIFO queues240,250,260, and270, to maintain a transaction order for upbound transactions according to the ordering rules and to store the coherency state and source identification (ID) for each upbound transaction. The source ID may associate an agent, or I/O device, with a transaction.

In the present embodiment, hub interface circuitry280may comprise four leaves,245,255,265, and275, wherein the leaves maintain transaction orders for transactions received from I/O interfaces247,257,267, and277, respectively. Further, a leaf, such as leaf245, may maintain an ordering for transaction received from the same source agent. For example, leaf245may receive transactions from agent number one and transactions from agent number two. The transactions orders maintained for agent number one and agent number two may be independent unless the transactions are associated with the same memory line. As a result, transactions from agent number one may satisfy their corresponding ordering rules and be transmitted to the unordered interface without regard to transactions from agent number two sitting in an upbound ordering FIFO queue. In addition, division of the transactions into leaves may facilitate transactions of one leaf, such as leaf255, independent of a transaction order for transactions of a second leaf, such as leaf245, when the transactions in leaf255may satisfy relevant ordering rules to transmit across unordered interface207.

Hub interface circuitry280may provide circuitry to determine a coherency state for an inbound transaction and respond to coherency requests issued across coherency interface230from snoop filter210. For example, when snoop filter210may send an ownership completion, hub interface circuitry280may accept the completion and update the status of the targeted inbound transaction as owning the memory line, or change the coherency state of the targeted inbound transaction from a non-ownership coherency state to ‘exclusive’, an ownership coherency state. On the other hand, in situations where snoop filter210may send an invalidation request targeting an inbound write transaction that has a a non-ownership coherency state, hub interface circuitry280may accept the invalidation and reissue a request for ownership after the inbound write transaction may reach the top of an upbound ordering FIFO queue240,250,260, or270.

On the other hand, when snoop filter210may send an invalidation request targeting an inbound write transaction that owns the memory line, but the transaction is not at the top of an upbound ordering FIFO queue, or is not in flight to snoop filter210, hub interface circuitry280may accept the invalidation and reissue a request for ownership after the transaction reaches the top of the corresponding upbound ordering FIFO queue240,250,260, or270. Accepting invalidation for a transaction that owns a memory line, takes away, or steals, the ownership from the transaction.

In the present embodiment, when the snoop filter210may send an invalidation request targeting an inbound write transaction that owns the memory line and the inbound write transaction may either be at the top of upbound ordering FIFO queue240,250,260, or270or in flight to snoop filter210, then hub interface circuitry280may reject the invalidation request and snoop filter210may wait for the inbound write transaction to be received. For example, when a write transaction reaches the top of an upbound ordering FIFO queue in leaf245, the write transaction may satisfy ordering rules to transmit to unordered interface207, so hub interface circuitry280may transition the write transaction to a coherency state of modified and forward an indication of the modified coherency state to snoop filter210via upbound path220. However, while the indication from hub interface circuitry280may transmit to snoop filter210, snoop filter210may issue a request for invalidation of that write transaction to hub interface circuitry280in response to a second transaction. In many embodiments, hub interface circuitry280may reject the request for invalidation once a transaction reaches the top of an upbound ordering FIFO queue240,250,260, or270, and the transaction owns a memory line. In these embodiments, the ownership of the memory line by such a transaction may not be stolen.

In some embodiments, hub interface circuitry280may comprise arbitration circuitry222and starvation circuitry214. Arbitration circuitry222may arbitrate access to upbound path220between leaves245,255,265, and275of hub interface circuitry280. Starvation circuitry214may couple with conflict circuitry218and buffer212to prevent starvation of a transaction or a leaf of transactions. In many embodiments, starvation circuitry214may monitor the number of invalidations transmitted and/or accepted by hub interface circuitry280for a transaction or a leaf. For example, arbitration circuitry222may arbitrate substantially equivalent access between leaves245,255,265and275for transmission of transactions from an upbound ordering FIFO queue through upbound path220to unordered interface207. After leaf245comprises a write transaction at the top of upbound ordering FIFO queue240, hub interface circuitry280may request ownership of the memory line associated with the write transaction via snoop filter210. Conflict circuitry218may recognize a conflict between a pending transaction in pending transaction buffer226and a request for ownership by the write transaction at the top of upbound ordering FIFO queue240. In response, conflict circuitry218may transmit an indication via coherency interface230denying the request for ownership.

Subsequently, arbitration circuitry222may grant access to leaf255and leaf265and the pending transaction in pending transaction buffer226may transmit across an unordered interface207. An inbound transaction in leaf275at the top of upbound ordering FIFO queue270may transmit to upbound path220and may be stored in pending transaction buffer226. After arbitration circuitry222grants access to leaf245, snoop filter210may again respond to the request for ownership with an invalidation since a transaction pending on unordered interface207may be associated with the same memory line. Starvation circuitry214may monitor the number of invalidations accepted by hub interface circuitry280for the transaction at the top of upbound ordering FIFO queue240and after the number of invalidations reaches a starvation number, starvation circuitry214may stall all or substantially all of the I/O interfaces to flush upbound ordering FIFO queues240,250,260, and270. Thus, the transactions associated with upbound ordering FIFO queue240may clear before additional write and/or read transactions may be received via I/O interfaces247,257,267, and277. In some embodiments, starvation circuitry214may couple with arbitration circuitry222to modify the level of access arbitrated to leaf245and/or stall I/O interfaces247,257,267, and277.

After a transaction reaches the top of an upbound ordering FIFO queue240,250,260, or270, the transaction may transmit to upbound path220. Upbound path220may comprise pending data buffer224and pending transaction buffer226. Pending data buffer224may receive and store data associated with upbound transaction awaiting transmission across unordered interface207. Pending transaction buffer226may store a transaction header for a transaction pending on unordered interface207. For example, after leaf245may receive an upbound transaction, hub interface circuitry280may place the header of the transaction in the corresponding upbound ordering FIFO queue and transmit the data associated with the header to pending data buffer224. At some point, the header may be forwarded to pending transaction buffer226to await transmission across unordered interface207. Then, after unordered interface may receive the transaction, the data may transmit across unordered interface207. In several embodiments, pending data buffer224may comprise a separate buffer for leaves245,255,265, and275. Alternatively, pending data buffer224may comprise mechanisms such as pointers to associate a section of a buffer with a leaf.

Referring now toFIG. 3, there is shown an embodiment of a single leaf conflict in a determination of a coherency state for an upbound transaction. InFIG. 3, hub interface320may receive a transaction322and transaction322may receive ownership of memory line one. Subsequently, hub interface320may receive an upbound transaction324and may request ownership for memory line one via snoop filter310. Snoop filter310may deny the request for ownership of memory line one while transaction322owns memory line one. Snoop filter310may receive a downbound snoop request300for memory line one and may transmit a request315for invalidation of the ownership of memory line one by transaction322. Hub interface320may respond to the request326for invalidation with an acceptance while transaction322may not satisfy ordering rules. As a result, snoop filter310may respond to downbound snoop request305with an invalid response to indicate that a pending write transaction may have ownership of that memory line and, in some embodiments, with the data associated with transaction322.

Alternatively, hub interface320may modify the coherency state of upbound transaction324from a non-ownership state to ‘exclusive’ prior to receiving a downbound snoop request300. As a result, after snoop filter310may issue a request for invalidation315to hub interface320to invalidate the ownership by upbound transaction324, hub interface320may respond to the request326with an acceptance. Snoop filter310may then respond to downbound snoop request305with an invalidation to indicate that data of a write transaction may not be globally visible for memory line one.

Referring now toFIG. 4, there is shown an embodiment of a single leaf conflict in a determination of a coherency state for an upbound transaction. The embodiment depicts a situation wherein hub interface420may receive upbound transaction424and may pre-fetch ownership, or request ownership426of a memory line, for upbound transaction424. Snoop filter410may receive the request for ownership426, perform an internal conflict check, and determine that pending transaction on unordered interface400conflicts with the ownership request for upbound transaction424. Snoop filter410may respond415to the ownership request415with a denial, or invalidation request. After hub interface420may receive an invalidation request for upbound transaction424, wherein upbound transaction424has a non-ownership coherency state, hub interface420may accept the invalidation and may reissue an ownership request for upbound transaction424after upbound transaction424may satisfy associated ordering rules.

Referring now toFIG. 5, there is shown an embodiment of a multiple leaf conflict in a determination of a coherency state for an upbound transaction. The embodiment comprises a snoop filter510, hub interface520representing a first leaf, and a hub interface530representing a second leaf. Hub interface520may comprise two transactions, transaction522with a coherency state of ‘exclusive’ for memory line one and upbound transaction525with a coherency state of ‘exclusive’ for memory line two. Hub interface530may then receive a write transaction535and request ownership for the memory line associated with write transaction535, memory line two. Snoop filter510may perform a conflict check and determine that memory line two associated with write transaction535may also be associated with transaction525and upbound transaction525may have a coherency state of ‘exclusive’. In response, snoop filter510may issue a request to invalidate the ownership515of the memory line by upbound transaction525. Since upbound transaction525has not reached the top of an ordering queue, hub interface520may respond to the request526for invalidation of ownership with an acceptance, stealing the ownership in favor of write transaction535. Then, snoop filter510may respond to the request555for ownership with an ownership completion. Upon receiving the ownership completion, hub interface530may determine the coherency state of write transaction535, changing the coherency state to ‘exclusive’.

Subsequently, upbound transaction525may reach the top of the corresponding ordering queue and hub interface520may issue a request for ownership of memory line two. Snoop filter510may determine a conflict between a request for ownership by upbound transaction525and the ownership of the memory line by write transaction535and may issue a request to invalidate the ownership of memory line two by write transaction535. Hub interface530may respond with an acceptance wherein write transaction535may not satisfy associated ordering rules. Snoop filter510may request ownership of memory line two and, after receiving the ownership completion from the unordered interface, respond to hub interface520with an ownership completion. Hub interface520may determine the coherency state of upbound transaction525to change from a non-ownership state to ‘exclusive’ upon receipt of the ownership completion. Alternatively, when hub interface520may receive write transaction535, upbound transaction525may satisfy ordering rules. As a result, hub interface520may respond to a request for invalidation from snoop filter510with a rejection and write transaction535may maintain a non-ownership coherency state until hub interface530may reissue a request for ownership of memory line two.

Referring now toFIG. 6, there is shown an embodiment of a multiple leaf conflict and a determination of a coherency state for an upbound transaction. The embodiment comprises a snoop filter610, hub interface620, and hub interface630. Hub interface620may comprise two transactions, transaction622and upbound transaction624. Upbound transaction624may not satisfy associated ordering rules until transaction622may transmit upbound to the unordered interface. Hub interface630may comprise a read transaction636to read the memory line associated with upbound transaction624. Hub interface630may forward640the read transaction636to snoop filter610and snoop filter610may determine a conflict between read transaction636and the ownership of the memory line by upbound transaction624. In response, snoop filter610may issue a request to invalidate the ownership616of the memory line by upbound transaction624and hub interface620may respond626with an acceptance of the invalidation since upbound transaction624may not satisfy associated ordering rules. Snoop filter610may then transmit the read transaction upbound to the unordered interface.

Alternatively, when hub interface630may forward640read transaction636to snoop filter610, snoop filter610may determine that a conflict exists with upbound transaction624, and snoop filter610may request an invalidation616of the ownership by upbound transaction624. Hub interface620may determine that upbound transaction624may satisfy ordering rules and reject the request for invalidation626of the ownership by upbound transaction624. Snoop filter610may respond applying back pressure to read transactions in and/or being accepted by hub interface620and hub interface630. Snoop filter610may discontinue the back pressure after transactions622,624, and636are pending on the unordered interface.

Referring now toFIG. 7, there is shown a flow chart of an embodiment to maintain ordering for transactions and to transact between an ordered interface and an unordered interface. The embodiment comprises maintaining a transaction order for an upbound transaction based upon an ordering of an input-output interface to transmit the upbound transaction to an unordered interface700; determining a conflict associated with an ownership of a memory line by the upbound transaction710; determining a coherency state for the upbound transaction based upon the conflict and the transaction order, to take the ownership from the upbound transaction740; and limiting the number of invalidations to send to the upbound transaction to prevent starvation780. Maintaining a transaction order700may maintain a transaction order according to ordering rules associated with the transaction to prevent problems associated with performing transactions from an ordered interface out of order. For example, an agent on an ordered interface, such as an input-output device coupled with a bridge, may issue a series of write transactions and, assuming that the transactions will be performed in order, issue a last transaction to read the same memory contents. If the transactions are received by the unordered interface in an order other than the order they are issued, the read may return unpredictable data.

Maintaining a transaction order for an upbound transaction based upon an ordering of an input-output interface to transmit the upbound transaction to an unordered interface700may comprise placing the upbound transaction in a queue705. Placing the upbound transaction in a queue705may allow the transactions to be transmitted to the unordered interface in the order the transactions are received from the ordered interface or the I/O interface. Maintaining the order as received from the I/O interface and allowing one transaction to issue from the queue at a time may maintain the order from the ordered interface. In some embodiments, after receiving a completion for the first transaction, the second transaction may issue to the unordered interface. In other embodiments, after the first transaction may issue, the second write transaction may issue.

Determining a conflict associated with an ownership of a memory line by the upbound transaction710may perform a conflict check in response to a request associated with an ownership of the memory line such as a pre-fetch of ownership for a new transaction, receipt of a read transaction or a header of a read transaction of the memory line, or a snoop request. Determining a conflict710may comprise determining the conflict between the ownership by the upbound transaction and a request by an inbound read transaction715; determining the conflict between the ownership by the upbound transaction and an inbound ownership request from a second input-output interface720; determining a conflict between the ownership by the upbound transaction and a downbound snoop request725; and determining the conflict between a request for the ownership by the upbound transaction and the ownership by a pending inbound transaction on the unordered interface730.

Determining the conflict between the ownership by the upbound transaction and a request by an inbound read transaction715may comprise performing a conflict check for a read transaction to determine whether a write may be pending for a memory line associated with the read transaction. In some embodiments, a snoop filter may perform the conflict check after the read transaction, or a header therefore, may be forwarded from the top of an ordering queue to the snoop filter.

Determining the conflict between the ownership by the upbound transaction and an inbound ownership request from a second input-output interface720may comprise pre-fetching ownership of the memory line by the upbound transaction and subsequently receiving an ownership request for an inbound transaction by a second hub interface. The second hub interface may attempt to pre-fetch ownership for the second transaction and a snoop filter may compare the memory line associated with the second transaction against memory contents of a buffer in the snoop filter comprising coherency states associated with memory lines of pending transactions.

Determining the conflict between the ownership by the upbound transaction and a downbound snoop request725may comprise determining the coherency state associated with a memory line subject to a downbound snoop request and the upbound transaction. In some embodiments, the upbound transaction may be associated with an ‘exclusive’ or a ‘modified’ coherency state, or the equivalent, or be pending on the unordered interface.

Determining the conflict between a request for the ownership by the upbound transaction and the ownership by a pending inbound transaction on the unordered interface730may comprise receiving a write transaction from an I/O interface, and attempting to pre-fetch ownership for the upbound transaction wherein the upbound transaction is associated with the same memory line as a pending inbound transaction on the unordered interface. The conflict check may determine whether the transactions may be associated with independent ordering rules. Embodiments may comprise a cache in a hub interface or coupled with a hub interface to respond to the subsequent anticipated read transactions rather than transmitting an anticipated read transaction upbound.

Determining a coherency state for the upbound transaction based upon the conflict in the transaction order, to take the ownership from the upbound transaction740may resolve the conflict by determining whether the upbound transaction may have ownership or may not. Determining a coherency state for the upbound transaction740may comprise applying back-pressure to subsequent read transactions from input-output devices until the conflict is cleared745; issuing an invalidation request for the upbound transaction750; changing the coherency state of the upbound transaction from exclusive to steal the ownership from the upbound transaction; and reissuing a request for the ownership by the upbound transaction760. Applying back-pressure745may comprise slowing or stopping inbound read transactions from I/O devices to flush ordering queues. In some embodiments, applying back-pressure745may prevent starvation of the read transaction by a series of write transactions to the same memory line. In other embodiments, backpressure may be applied to upbound transactions.

Issuing an invalidation request for the upbound transaction750may issue a request to steal ownership from the upbound transaction in favor of a second transaction if the upbound transaction may not satisfy ordering rules. Issuing an invalidation request for the upbound transaction750may comprise rejecting an invalidation request for the upbound transaction, wherein the upbound transaction is near the top of a queue755.

Rejecting an invalidation request for the upbound transaction, wherein the upbound transaction is near the top of a queue755may comprise rejecting the invalidation request and maintaining ownership of the memory line by the upbound transaction after the upbound transaction may reach or approach the top of an ordering queue. After the upbound transaction has reached or approached the top of an ordering queue, in some embodiments, the upbound transaction may satisfy associated ordering rules. For example, the snoop filter may receive a downbound snoop request for memory line one and perform a conflicts check that determines the upbound transaction owns memory line one. The snoop filter may issue a request to invalidate the ownership by the upbound transaction, but, the hub interface may reject the invalidation request when the upbound transaction is near or at the top of the ordering queue. As a result, the downbound snoop request may receive an indication that a write transaction or upbound transaction is pending for the same memory line and/or the data associated with the upbound transaction, without requesting ownership of the memory line again.

Changing the coherency state of the upbound transaction from exclusive to steal the ownership from the upbound transaction; and reissuing a request for the ownership by the upbound transaction760may steal or take the ownership from the upbound transaction in favor of an unrelated transaction in regards to ordering rules, to allow the unrelated transaction to transmit upbound to the unordered interface without having to wait for the upbound transaction to satisfy ordering rules. In some embodiments, changing the coherency state of the upbound transaction from exclusive760may comprise sending an inbound read transaction upbound765and issuing an invalid response to a downbound snoop request770.

Sending an inbound read transaction upbound765may comprise sending an unrelated inbound read transaction upbound to the unordered interface when the upbound transaction has ownership of the memory line associated with the inbound read transaction. For example, the upbound transaction may be a write transaction to a memory line and the inbound read transaction for the same memory line may satisfy ordering rules. No conflict may exist wherein the ordering rules of the write transaction and the read transaction are unrelated or substantially unrelated. In other situations, the snoop filter may request that the hub interface invalidate the ownership of the memory line by the upbound transaction. The hub interface may accept the invalidation of the ownership; stealing the ownership from the upbound transaction in favor of the inbound read transaction. As a result, the inbound read transaction may transmit upbound and the upbound transaction may regain ownership by reissuing a request for the ownership.

Issuing an invalid response to a downbound snoop request770may comprise responding to a downbound snoop request with an indication that a transaction with ownership of the memory line may be pending, may not be globally visible, or may not exist. For example, a hub interface may pre-fetch ownership of a memory line for an upbound transaction via the snoop filter. The snoop filter may receive a response from the unordered interface comprising an ownership completion and forward the ownership completion to the hub interface. After receiving the ownership completion, the hub interface may modify the coherency state of the upbound transaction from a pending state to ‘exclusive’. Subsequently, a peer hub interface, or a second hub interface, may transmit a snoop request to the snoop filter for the same memory line. The snoop filter, in response, may request to invalidate the ownership by the upbound transaction and when the upbound transaction may not satisfy an ordering rule, the hub interface associated with the upbound transaction may steal the ownership from the upbound transaction and respond to the snoop filter with an acceptance. The snoop filter may then respond to the downbound snoop request via the second or peer hub interface to indicate that the upbound transaction is not visible.

Limiting a number of invalidations to send to the upbound transaction to prevent starvation780may monitor the number of times an invalidation request is sent to a transaction and/or the number of times a hub interface responds to a request to invalidate with an acceptance. Limiting a number of invalidations780may monitor starvation of a leaf, starvation of a type of transaction, and/or starvation of the upbound transaction. Limiting a number of invalidations780may comprise stalling the input-output interface to transmit the upbound transaction to the unordered interface785. Stalling the input-output interface785may comprise stalling one or more types of transactions from crossing the input-output interface into a hub interface. In some embodiments, stalling the input-output interface785may comprise stalling more than one input-output interface to flush the transactions in the hub interfaces. In other embodiments, stalling the input-output interface785may comprise stalling one or more input-output interfaces until the upbound transaction may transmit upbound to the unordered interface or stalling until the upbound transaction may transmit across the unordered interface.

Referring now toFIG. 8, a machine-readable medium embodiment of the present invention is shown. A machine-readable medium includes any mechanism that provides (i.e. stores and or transmits) information in a form readable by a machine (e.g., a computer), that when executed by the machine, may perform the functions described herein. For example, a machine-readable medium may include read only memory (ROM); random access memory (RAM); magnetic disk storage media; optical storage media; flash memory devices; electrical, optical, acoustical or other form of propagated signals (e.g. carrier waves, infrared signals, digital signals, etc.); etc. . . . Several embodiments of the present invention may comprise more than one machine-readable medium depending on the design of the machine.

In particular,FIG. 8shows an embodiment of a machine-readable medium800comprising instructions for maintaining a transaction order for an upbound transaction based upon an ordering of an input-output interface to transmit the upbound transaction to an unordered interface810; determining a conflict associated with an ownership of a memory line by the upbound transaction820; determining a coherency state for the upbound transaction based upon the conflict and the transaction order, to take the ownership from the upbound transaction830; and pre-fetching the ownership for the upbound transaction840. Maintaining a transaction order810may comprise instructions for maintaining an upbound transaction in an upbound transaction ordering queue until the upbound transaction may satisfy ordering rules associated with the corresponding input-output interface. In some embodiments, instructions for maintaining a transaction order for an upbound transaction based upon an ordering of an input-output interface to transmit the upbound transaction to an unordered interface810may comprise instructions for maintaining related transactions in an order received from an input-output interface and allowing subsequent, unrelated transactions to bypass when the subsequent, unrelated transaction may satisfy the ordering of the input-output interface.

Determining a conflict associated with an ownership of a memory line by the upbound transaction820may comprise instructions for comparing the memory line with a memory line of another transaction and determining that an ownership of the memory line by the upbound transaction conflicts. For example, determining a conflict associated with an ownership820may comprise instructions for comparing a request for ownership by the upbound transaction against a coherency state associated with the memory line subject to the upbound transaction, or instructions for comparing a conflict check of a memory line or an ownership request for a memory line against the coherency state of the upbound transaction.

Determining a coherency state for the upbound transaction based upon the conflict and the transaction order, to take the ownership from the upbound transaction830may comprise instructions for accepting an ownership completion and updating the coherency state of the targeted write transaction from pending to owned, or exclusive. In addition, determining a coherency state830may comprise instructions for stealing the ownership from the upbound transaction when the upbound transaction owns the memory line but the upbound transaction is not at the top of the upbound ordering queue, nor in flight from the upbound ordering queue to the snoop filter, or may not satisfy corresponding ordering rules for the upbound transaction. On the other hand, the instructions may comprise rejecting the invalidation request when the upbound transaction owns the line, or has a coherency state of ‘exclusive’, or when the upbound transaction is at the top of the upbound ordering queue or in flight to the snoop filter.

Pre-fetching the ownership for the upbound transaction840may comprise instructions for issuing the request for ownership of a memory line associated with the upbound transaction when the upbound transaction may be received by a hub interface via the input-output interface. Pre-fetching the ownership for the upbound transaction840may further comprise instructions for accepting an invalidation of the request for ownership from the snoop filter. In alternative embodiments, pre-fetching the ownership for the upbound transaction840may comprise instructions for pre-fetching the ownership for the upbound transaction after the hub interface may receive the upbound transaction.