System to optimally order cycles originating from a single physical link

A method and architecture optimizes transaction ordering in a hierarchical bridge environment. A parent-bridge is one level above a child-bridge, which in turn is one level above a grand-child component. The parent-bridge is a bridge-bridge. The child-bridge can be a bus-bridge or a bridge-bridge. The grand-child component can be a bus, a bus-bridge or a bridge-bridge. A parent-bridge is connected to a child-bridge via child-links, the child-bridge connected to grandchild-links, and the parent-bridge having multiple transaction order queues (TOQs) per child-link. Ideally, the parent-bridge has one TOQ for each grandchild-link where the parent-bridge applies separate transaction ordering for each of the grandchild-links. However, at a minimum, the system uses at least two TOQs per child-link, and as such, provides a higher level of transaction throughput than systems using one TOQ per child-link. The child-bridge sends a signal to the parent-bridge identifying from which grandchild-link a transaction was sent.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention relates to ordering cycles originating from multiple subordinate devices.

2. Description of the Related Art

Modern computer systems generally include input/output (I/O) devices that are connected to a central processing unit (CPU) via a system bus. The system bus operates to transfer addresses, data and control signals between the CPU and the I/O devices. Many modern computer systems include multiple buses, each in turn, with multiple I/O devices. Typically, any particular I/O device is coupled to only a single bus.

Bus bridges(bus-bridges) are often used in these multiple-bus systems to connect the multiple I/O devices connected to the multiple buses. “Bridge brides”(bridge-brides) are also often used in such systems to connect bus-bridges and thus handle communications from an even greater number of I/O devices. The commands transferred through both of these types of bridges frequently have data associated with them (e.g., read or write commands). The rate at which this multi-bridge architecture can process the communications generated from its multiple I/O devices directly affects the overall system performance. There is a constant demand for increasing the performance of modern computer systems generally. One way to achieve greater performance is to increase the rate at which communications from the I/O devices are processed.

As shown inFIG. 1, multi-bridge architectures can be viewed as having several different levels. A level0containing buses122and124and devices112A–112F, which may be collectively referenced as112, a level1containing bus-bridges139and a level2including bridge-bridges149. Level0includes I/O devices112connected to buses122and124. At level1, bus-bridge139is connected to the buses122and124of level0. Further, the bus-bridge139has a transaction order queues (TOQ)131and transaction buffers186for each bus-bridge/bus link, such as bus-bridge/bus link162. TOQ131stores transaction buffer identifiers for certain transactions to ensure that system ordering rules, such as PCI and PCI-X ordering rules, are not violated. The purpose of the TOQ131is to ensure that transactions will execute in an order consistent with the system ordering rules. As such, not all transactions go into the TOQ, only those for which ordering rules apply. In contrast, transaction buffers store transaction information, such as cycle address, command, data, and the like. Next, level2contains one or more bridge-bridges, which may be represented by bridge-bridge149. Bridge-bridge149is connected to one or more bus-bridges, such as bus-bridge139from level1. Each bridge-bridge/bus-bridge link, such as bridge-bridge/bus-bridge link152between bridge-bridge149and bus-bridge152, has one representative TOQ, which is TOQ142, and one transaction buffer, such as transactional buffer180, in the corresponding bridge-bridge149. An inherent difference between bus-bridge139and bridge-bridge149is that bus-bridge139connect a series of buses122and124, while bridge-bridge149connect a series of bridges. The bus-bridge's139direct link to buses122and124assures that bus-bridge139always know from which one of the buses122and124a transaction originated. Bridge-bridge149, in contrast, does not have a separate link for each of the buses122and124, and as such, are not inherently able to identify the bus source of any transaction. This inability to identify the bus source negatively impacts the ability for ordering transactions at the bridge-bridge level, and as such, also unnecessarily limits the corresponding transactional throughput of the entire system.

Transaction ordering, as discussed in more detail in the two U.S. patent applications incorporated below: U.S. patent application Ser. No. 09/749,111 by Paras Shah, “Relaxed Read Completion Ordering in a System Using a Transaction Order Queue,” filed Dec. 26, 2000, and issued into U.S. Pat. No. 6,615,295 on Sep. 2, 2003, and U.S. patent application Ser. No. 09/779,424, entitled “Enhancement to Transaction Order Queue,” filed Feb. 8, 2001, orders a set of transactions based on a predefined set of rules. These rules are designed to achieve optimum transaction ordering where a single TOQ receives transactions originating from a single bus. However, where a TOQ receives transactions originating from multiple buses, optimum transaction ordering is lost and the overall transaction throughput is reduced. In further detail, and as shown inFIG. 1, TOQs142and131, are used in two different types of bridges in two different levels. The first bridge, in level2, is a bridge-bridge149, where single TOQs142are used per each bridge-bridge/bus-bridge link (child-link)152, regardless of the number of buses122and124attached to the corresponding bus-bridge139. The second bridge, at level1, is a bus-bridge139where single TOQs131are used for each bus-bridge/bus link (grandchild-link)160. In the case of a bus-bridge139, where there exists a one-to-one ratio between TOQs131and132and buses122and124, a TOQ131, as designed, is limited to ordering the transactions from a single bus, and as such, is able to perform at its top design efficiency. However, in the case of a bridge-bridge149, where there exists a one-to-many ratio between TOQs142to buses122and124, a TOQ142is required to process transactions from multiple busses122and124over a single child-link152. Specifically, TOQ142for example, is required to process transactions from multiple buses122and124, and treat every transaction received through child-link152, whether from bus122or bus124, as though it originated from a single bus, and as such, the TOQ142is unable to function at its intended efficiency. In other words, because the bridge-bridge149is unable to discern between transactions of different buses122and124connected to a bus-bridge139, the bridge-bridge149must order such transactions as though they occurred on the same bus, bus122for example. Because of this, unnecessary blocking occurs where a blocking condition on one bus, bus122for example, is imposed, across the entire child-link, child-link152for example, effecting every attached bus122and124, and unnecessarily reduces transaction throughput.

SUMMARY OF THE INVENTION

Briefly, the illustrative system comprises a method and architecture for optimizing transaction ordering operations in a hierarchical bridge environment. The architecture includes at least a first bridge (parent-bridge), connected to a second bridge (child-bridge) via a link (child-link), and the child-bridge is connected to a transaction link (grandchild-link), where a parent-bridge has a set of buffers for each child-link to hold incoming transactions. For each child-link, the parent-bridge has at least two TOQs to provide separate transaction ordering for the child-links that communicate transactions from multiple different transaction sources, i.e., multiple grandchild-links.

In the illustrative system's most efficient operation, for every grandchild-link from the child-bridge, the parent-bridge maintains a dedicated TOQ. In providing a TOQ for each grandchild-link the parent-bridge is able to apply transaction order rules across the transactions from the individual grandchild-links in essentially the same manner as if the individual grandchild-links were each separately directly connected to the parent-bridge (i.e., child-links). This design essentially allows a parent-bridge to handle the transaction ordering of additional grandchild-links, without the need to connect such grandchild-links directly to the parent-bridge. Therefore, a parent-bridge with a fixed amount of child-links can virtually increase its number of child-links by utilizing this multiple TOQ concept that essentially allows the parent-bridge to mimic the order processing that would take place if each separate grandchild-link had its own dedicated child-link to the parent-bridge. At a minimum, the illustrative system utilizes at least a two-to-one ratio of TOQs per child-link, and not less than a one-to-one ratio of TOQs per associated grandchild-link, and as such, is guaranteed to provide a higher level of transaction throughput than current one-to-one ratio TOQ-to-child-link systems.

Unlike the current systems that do not provide the means for a parent bridge to discern between the source of any communication received through child-link, the illustrative system provides such a means by transmitting an additional identification signal from the child-bridge to the parent-bridge. Thus, a signal can be passed from any child-bridge to its parent-bridge where the signal identifies from which particular grandchild-link a communication originated. Such a signal can be passed whether the parent-bridge is in level2and the child-bridge is in level1, or parent-bridge is in level3and child-bridge is in level2, or the parent-bridge is at any level “n” and child-bridge is at any level n−1.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENT

The following related patent application are hereby incorporated by reference as if set forth in its entirety:

FIG. 2, illustrates a typical multi-bridge architecture400implemented according to the disclosed techniques. For purposes of explanation, specific embodiments are set forth to provide a thorough understanding of the present invention. However, it will be understood by one skilled in the art, from reading the disclosure, that the invention may be practiced without these details. Further, although the embodiments are described including three levels of bridges, most, if not all, aspects of the system illustrated apply to systems using two or more levels of bridges. Moreover, well-known elements, devices, process steps, and the like, and including, but not limited to, bridge and transaction order queue design, are not set forth in detail in order to avoid obscuring the disclosed system. As used herein, the “child-link” generally refers to the connection between the parent-bridge and child-bridge, including the link interface of the parent-bridge or the link interface of the child-bridge. Also, the term “grandchild-link” generally refers to the connection between the child-bridge and the grandchild component, including the link interface of the child-bridge or the link interface of the grandchild component. InFIG. 2, the multi-tier bridge architecture400in the illustrated embodiment is made up of 3 levels:0,1and2.

Level0represents a common architecture present in modem computer systems, (seeFIG. 1and buses122and124and devices112), where multiple buses280are coupled with multiple I/O devices290. Next, level1, also a common architecture present in modem computer systems, (seeFIG. 1bus-bridge139), contains multiple bus-bridges260connected via grandchild-links295to multiple buses280where each such grandchild-link295has its own TOQs270for ordering the transactions for each individual bus280. Also, each child-bridge260has one transaction buffer, i.e.352, for each grandchild link, i.e.,296. Level1's architecture, which provides a TOQ270for each connected bus280, allows transaction ordering to occur in its most efficient form, i.e., one TOQ per one bus.

Finally, inFIG. 2, level2represents a disclosed embodiment which utilizes a bridge-bridge232with child-links285to the multiple bus-bridges260in level1. Here, each child-link285to bus-bridges260, has its own set of TOQs320and its own transaction buffer349. The number of TOQs240in any such set320is equal to the number of buses280attached via grand-child links295to the bus-bridge260. In operation, when a new transaction is received by a transaction buffer, i.e.,349, the buffer contacts the appropriate TOQ320, based on the grand-child link295the transaction originated. This one-to-one ratio of TOQs-to-buses at a bridge-bridge level (level2), unlike simply a one-to-one ratio of TOQs-to-bus-bridge, allows pure transaction ordering, (i.e., one TOQ per bus), to occur in a bridge located at least one level deeper than the architecture shown inFIG. 1. As such, FIG.2's level2design represents a more efficient design than that shown in FIG.1's level2design. Specifically, the potential blocking of any particular bus's transactions by another bus, as discussed above in relation toFIG. 1, is no longer present with the design disclosed inFIG. 2, i.e., where the disclosed multiple-TOQ concept is present.

In further detail, level2's TOQs are broken into as many sets320as there are child-links285. Four child-links286,287,288and289in parent-bridge232are shown, and each link has an associated TOQ set320:321,322,323and324respectively, as well as their own transaction buffers349. Each of these respective child-links286,287,288and289includes multiple channels, such as channels225A–225N,226A–226N,227A–227N, and228A–228N. Further, within each TOQ set320are as many TOQs as there are grand-child links295for the associated child-link285. For example, TOQ set321, associated with child-link286, and where such child-link286has four grand child links associated thereto:296,297,298and299, is made up of four TOQs:241,242,243and244. It should be noted that TOQ243is drawn in phantom form to show that it could represent multiple TOQs to assure that there were an equal amount of TOQs in set321as grand-child links associated with child-link286. Each of the TOQ sets320contains a phantom TOQ for the same purpose. The remaining TOQ sets disclosed are as follows: TOQ set322contains TOQs245,246,247and248; TOQ set323, representing none or more TOQ sets320, contains TOQs249,250,251and252; and TOQ set324contains TOQs253,254,255and256. Each of these TOQs241–256may include a TOQ identifier, such as TOQ identifiers441–456, which are discussed below in greater detail. Other embodiments may use less than one TOQ per grand-child link295for the associated child-link285, but a minimum of two such TOQs are needed to optimize transaction ordering. Further, other multi-TOQ architectures may use more or less number of links to more or less number of child bridges.

As discussed above, each of the TOQs240in parent-bridge232correspond with a grandchild-link295. As such, each TOQ240is matched with a grandchild-link295. A matching can be achieved in variety of ways. A matching can occur where the child-bridge transmits or originates a transaction identifier that is a predefined address of an associated TOQ240. For example, in the case of TOQ set321having four TOQs241,242,243and244, TOQ could have corresponding addresses 00, 01, 10 and 11. Thus, at the same time that child-bridge260is transmitting a transaction over child-link286, the child-link286could transmit address 01 on a transaction identifier communication link, (two unused channels, such as channels225A and225B, on child-link286for example), such that parent-bridge232routes the transmission to TOQ242. It is also contemplated that rather than identifying a TOQ by an address, it may be identified with a stored key or transaction order queue identifier, such as the keys or TOQ identifiers441–456. Here, using the same transaction identifier01, if each TOQ240had associated with it a key, the parent-bridge232could compare an incoming transaction identifier with each of the keys of each TOQ, and where there was a match, the parent-bridge would route the corresponding transmission to that TOQ, in this example again, TOQ242. It is also contemplated that where a transaction is transmitted with a transaction identifier that does not match a key in any one of the TOQs240, that the parent-bridge would route the transaction to a default TOQ, for example, TOQ241. This assures that all transactions are handled.

In theory, the number of TOQs one could place within bridge-bridge232is limitless. However, in reality the number of TOQs employed in bridge-bridge232is limited by chip hardware constrains, such as size and complexity, and/or the ability and efficiency of uniquely identifying a transaction from a particular bus. In the disclosed embodiment, it is contemplated that a transaction is identified through a simultaneous transmission of an identifier from associated bus-bridge260to bridge-bridge232through an unused channel, such as one of the channels225A–225N, on the child-links285. In the case of a bus-bridge260having two buses attached via grandchild-links295, bus281and bus282, for example, a single channel could be used to transmit an identifier of either a “0”, or a “1”, to indicate which bus was the source of the transaction. However, where more than two buses280are attached to the bus-bridge260, and a constraint exists which requires the use of only one channel, or for which only two TOQs are available, it is contemplated that the same single channel could still be used to handle the transactions by assigning buses280, or grand-child links295, an identifier of either “1”, or “0,” where the separate TOQs would handle buses of common identities as though they originated from a single source. As the number of buses rises, or the number of available TOQs increase, the need for additional channels arise. For example, where 4 buses and 4 TOQs are present, two channels (i.e., base10's “3”=base2's “11”) would be needed, if however 8 buses and 8 TOQs are present, three channels (i.e., base10's “7”=base2's “111”) would be needed. It should be noted that other means of identifying a transaction may occur through signals sent through dedicated connections between the bus-bridge260and the bridge-bridge232, or means other than an unused channel in child-links285.

It is contemplated that if the disclosed embodiment is implemented with a typical parent-bridge140as found inFIG. 1, i.e., a parent-bridge with only one TOQ per child-links285, rather than a parent-bridge232which has multiple TOQs per child-links285, that this implementation would result in a system with the same throughput as the typical architecture shown inFIG. 1. This is because although a bus identification signal would be sent to the parent-bridge232, there would be no functionality to receive it, nor any additional TOQs to take advantage of the information if it could be received, and thus, the parent-bridge232would simply order all the transactions coming through a particular child-link285as though they were originating from the same bus280, or grand-child link295, i.e., the same result as what is occurring at parent-bridge140inFIG. 1. Further, it is also contemplated that if the disclosed embodiment, having at least one parent-bridge232that in turn has multiple TOQs240per its child-links286, is implemented without a child-bridge260that either originates or transmits bus identification signals to the parent-bridges232, i.e, the child-bridge162ofFIG. 1, that this implementation would also function with the same throughput as the architecture ofFIG. 1. This is because the parent-bridge232would receive each transaction without any bus identification signal and for parent-bridge232to receive a transaction without an identification signal is the same as if it received a transaction with an address of “0.” Thus, all the transactions received by parent-bridge232would be directed to a single TOQ resulting in the same throughput experienced by the system ofFIG. 1.

FIGS. 3A and 3Bis a disclosed embodiment that introduces the application of the disclosed techniques to architectures using three or more hierarchical levels of bridges. In the embodiment shown inFIGS. 3A and 3B, the same type of architecture and functionality that was attributed to the bridge-bridge232in level2inFIG. 2(the parent-bridge inFIG. 2), is now in bridge-bridge200(parent-bridge) in level3, but rather than ordering transactions received directly from a bus-bridge260in level1, (the child-bridge inFIG. 2), the parent-bridge200receives transactions from a child-bridge232in level2. Here, rather than TOQ sets310containing TOQs218that maintain ordering for buses280, such TOQs218maintain ordering for bus-bridges260(grandchild-bridges). However, for embodiments that do not use the multi-TOQ design, the parent-bridge200in level3, as shown inFIGS. 3A and 3B, receives multiple transactions over child-links220from the corresponding child-bridge232, but does not know from which grandchild-bridge260the transaction originated, and therefore must apply standard transaction ordering across all transactions coming across child-links220, thus, unnecessarily allowing the blocking of transactions originating from one grandchild-bridge260by transactions originating from another grandchild-bridge260. Regardless of the number of levels of hierarchical bridge architecture employed, the implementation of the multi-TOQ per grandchild-link design across any parent/child/grandchild combinations would result in improved throughput through such parent. Thus, architectures with three or more levels all have at least one parent/child/grandchild combination that can have their throughput optimized by including the suggested multi-TOQ architecture.

In further detail, level3, inFIG. 3A, represents a disclosed embodiment which utilizes a bridge-bridge200with connections220(child-links) to the multiple bridge-bridges230disclosed in level2. Here, every child-link220to bridge-bridges260has its own set of TOQs310and transaction buffers339. The number of TOQs218in any such set310is equal to the number of bus-bridges260attached via grand-child links285to the bridge-bridge230. This one-to-one ratio of TOQs-to-bus-bridges at a bridge-bridge level (level3), allows separate transaction ordering to occur for the groups of transactions originating from any one bus-bridge, (i.e., one TOQ per bus-bridge), and to occur in a bridge located at least one level deeper than the architecture shown inFIG. 2. As such, FIG.3's level3design represents a more efficient design than that shown in FIG.2's level2design. Specifically, the potential blocking of any particular bus-bridge's transactions by another bus-bridge is no longer present with the design inFIGS. 3A and 3B, i.e., where the disclosed multiple-TOQ concept is introduced at a third level of bridges.

In even greater detail, level3's TOQs are broken into as many sets310as there are child-links to bridge-bridge200. Specifically, four child-links221,222,223and224are shown in parent-bridge200, and each link has an associated TOQ set310:311,312,313and314respectively, as well as their own transaction buffers339. The child link221may include channels219A–219N, which may be any number of channels that are utilized to communicate with the parent-bridge232. It should also be appreciated that each of the other child-links may include various channels, as well. Further, within each TOQ set310there are as many TOQs218as there are grand-child links285for the associated child-link220. For example, TOQ set311, associated with child-link221, and where such child-link221has four grand child links associated thereto:286,287,288and289, is made up of four TOQs:201,202,203and204. It should be noted that TOQ203is drawn in phantom form to show that it could represent multiple TOQs to assure that there were an equal amount of TOQs in set311as grand-child links associated with child-link221. Each of the TOQ sets310contain a phantom TOQ for the same purpose. The remaining TOQ sets disclosed are as follows: TOQ set312contains TOQs205,206,207and208; TOQ set313representing none or more TOQ sets310, contains TOQs209,210,211and212; and TOQ set314contains TOQs213,214,215and216. Each of these TOQs201–216may include a TOQ identifier, such as TOQ identifiers401–416, which are similar to the TOQ identifiers441–456discussed above. Other embodiments may use less than one TOQ per grand-child link285for the associated child-link220, but a minimum of two such TOQs are needed to optimize transaction ordering. Further, other multi-TOQ architectures use more or less number of links to more or less number of child-bridges or grandchild-links.

Other embodiments may incorporate the disclosed multiple TOQ concept, but may do so in a fashion such that there is not a one-to-one correlation between the TOQs in the parent level bridge-bridge to the number of grand-child links. However, such embodiments would use at least two TOQs per child-link in any TOQ set. For example, looking atFIG. 2where the parent level is232, here if the TOQ set321were changed to have only two TOQs241and242, and child-link285remained connected to bus-bridge262that continued to have the four grand-child links296,297,298and299to the four buses281,282,283and284, then each TOQ241and242, for example, could each handle the transactions from two of the buses. In such a design, although there are two buses for each TOQ, i.e., TOQ241for buses281/282and TOQ242for buses283/284, and therefore the transactions from both buses are subject to the blocking of transactions from the other, this design still represents an improvement to a design where no multiple TOQs are used, as each bus, or grandchild-link, can only have its transaction blocked by one other bus (i.e., the other bus sharing the same TOQ), not three (i.e., not the three other grand-child links).

Additionally, rather than a single transaction buffer being used per child-link in a parent bridge, other embodiments may utilize a one-to-one ratio of transaction buffers to TOQs. For example, inFIG. 2, instead of there being one transaction buffer342per TOQ set321, there would instead be four transaction buffers, (i.e., Buff1a, Buff2b, Buff2cand Buff2d), for each TOQ241,242,243and244. As such, there are as many transaction buffers349as TOQs240(this multi-transaction buffer to multi-TOQ is not shown in any figure), and as many TOQs as there are grand-child links. When a transaction is received by the parent-bridge232, the parent-bridge232places the transaction in the proper transaction buffers342(multiple buffers not shown), i.e. the transaction buffer342that corresponds with the grandchild-link295from which the transaction originated. It is contemplated that such an embodiment having a one-to-one ratio of transaction buffers to TOQs, might be easier to implement. However, it is also contemplated that such an embodiment would be more expensive from the standpoint of silicon used.

FIG.4shows the disclosed embodiment ofFIG. 2incorporated into a computer system600. The computer system600includes CPU nodes610, I/O nodes630, and switch matrix620. CPU nodes610include the four nodes611,612,613and614. I/O nodes630include four I/O nodes601,602,603and604. A switch fabric620is connected to CPU nodes610and to I/O nodes630. The embodiment disclose inFIG. 2is shown inFIG. 4as I/O node0. LikeFIG. 2, I/O node0contains a parent-bridge230. Parent-bridge230is attached via child-links285to child-bridges260. The child-bridges260, in turn, are connected via grand-child links295to buses280. Finally, buses280are attached to I/O devices290. It is contemplated, although not required, that some or all of the other I/O nodes would adopt a similar architecture shown in detail in I/O node0.

The foregoing disclosure and description of the various embodiments are illustrative and explanatory thereof, and various changes in the nodes, buses, signals, components, circuit elements, circuit configurations, and signal connections, as well as in the details of the illustrated circuitry and construction and method of operation may be made without departing from the spirit and scope of the invention.