Apparatus, system, and methods for facilitating one-way ordering of messages

Methods, apparatus and systems for facilitating one-way ordering of otherwise independent message classes. A one-way message ordering mechanism facilitates one-way ordering of messages of different message classes sent between interconnects employing independent pathways for the message classes. In one aspect, messages of a second message class may not pass messages of a first message class. Moreover, when messages of the first and second classes are received in sequence, the ordering mechanism ensures that messages of the first class are forwarded to, and received at, a next hop prior to forwarding messages of the second class.

FIELD OF THE INVENTION

The field of invention relates generally to computer systems and, more specifically but not exclusively relates to facilitating transfer operation of messages, packets, and information for interconnect technology, particularly to facilitating ordering of messages.

BACKGROUND INFORMATION

An interconnection network, such as, a ring, a bus, a point to point, or a mesh fabric, typically has independent message classes for forward progress or performance reasons. For example, one may group a particular type of messages into a message class to facilitate control and maintain different types of independent flow of each message class. Also, message classes may have different priorities and maintain that blockage in one message class does not prevent traffic flowing in another message class. Also, message classes may be executed at a link layer and allow for independent transmission channels to protocol layer agents. Some examples of message classes could be for snoop, data response, non-data response, special control functions, non-coherent, etc.

Additionally, a message in a particular class may be unordered with respect to other messages in the same class, and also with respect to other messages in different classes. Again, this may be for forward progress or for performance reasons. However, in some cases, there is a functional requirement that messages in different message classes maintain some kind of relative order. For example, in a cache coherence protocol, one may need to guarantee that a message corresponding to a particular cache line address cannot pass a previous message for the same cache line address sent in another message class to the same agent.

Presently, solutions do not exist for facilitating ordering of independent message classes sent between interconnects or segments of an interconnect network.

DETAILED DESCRIPTION

In various embodiments, the claimed subject matter describes a method, apparatus, and system to facilitate one-way ordering of otherwise independent message classes. In one example, a snoop message is described in the context of maintaining ordering with respect to a Global Observation (GO) message across an unordered buffered switch ring interconnect. However, the claimed subject matter is not limited to use for snoop and GO messages and will also be extended to any such ordering requirement across several variations of interconnect topologies that have certain properties that will be discussed later.

Embodiments of the invention disclosed herein disclose a method, apparatus, and system to ensure a one-way ordering between two independent message classes. In one embodiment, one example is depicted for ensuring a leader message from a first message class is ordered with respect to follower messages from a second message class.

For clarity, individual components in the Figures herein may also be referred to by their labels in the Figures, rather than by a particular reference number. For example, the labeling of the nodes inFIG. 1provide information identifying the node and/or its function; such information cannot be conveyed alone with a separate reference number. Additionally, reference numbers referring to a particular type of component (as opposed to a particular component) may be shown with a reference number followed by “(typ)” meaning “typical.” It will be understood that the configuration of these components will be typical of similar components that may exist but are not shown in the drawing Figures for simplicity and clarity.

In one embodiment, one-way ordering of messages in independent message classes that are transferred across ring interconnects is provided. A system100inFIG. 1shows an exemplary architecture under which a one-way ordering of independent message classes may be implemented. System100is illustrative of an advanced system architecture supporting multiple processor cores102, each coupled to a respective node104on one of two ring interconnects, labeled and referred to herein as ring0 and ring1. For simplicity, the nodes for each of the ring0 and ring1 interconnects are shown being connected with a single line. As shown in detail106, in one embodiment each of these ring interconnects include four separate sets of “wires” or electronic paths connecting each node, thus forming four rings for each of ring0 and ring1. In actual practice, there are multiple physical electronic paths corresponding to each wire that is illustrated. It will be understood by those skilled in the art that the use of a single line to show connections herein is for simplicity and clarity, as each particular connection may employ one or more electronic paths.

In the context of system100, a cache coherency scheme is implemented by using independent message classes. Under a ring interconnect architecture, independent message classes may be implemented by employing respective wires for each message class. For example, in the aforementioned embodiment, each of ring0 and ring1 include four ringed paths or wires, labeled and referred to herein as AD, AK, IV, and BL. Accordingly, since the messages are sent over separate physical interconnect paths, they are independent of one another from a transmission point of view. In consideration of the possibility of different amounts of buffering delays being applied to the separate interconnect paths, it would thus be possible for messages of a given message class to “pass” messages of another message class when the message classes employ separate independent ring interconnect paths. However, there are instances where this may not be permitted.

In one embodiment, data is passed between nodes in a cyclical manner. For example, for each real or logical clock cycle, data is advanced from one node to an adjacent node in the ring. In one embodiment, various signals and data may travel in both a clockwise and counterclockwise direction around the ring. In one embodiment, at least some of the nodes in ring0 and ring1 are unbuffered.

Each of ring0 and ring1 include a plurality of nodes104. Each node labeled Cbo n (where n is a number) is a node corresponding to a processor core sharing the same number n (as identified by the core's engine number n). There are also other type of nodes shown in system100including a QPI 0/1 node, which provides an interface to a QuickPath Interconnect (QPI) fabric108, and an IIO node, which provides an interface to Input/Output interface110. Similarly, Ring2 includes a QPI 2 node providing an interface with a QPI fabric112. Further shown are a number of nodes marked with an “X”; these nodes are used for timing purposes. It is noted that the QPI, IIO, and X nodes are merely exemplary of one implementation architecture, whereas other architectures may have more or less of each type of node or none at all. Moreover, other types of nodes may also be implemented.

Another set of nodes included in system100are buffered switch ring stop nodes, which are labeled Sbo NW (Northwest), Sbo NE (Northeast), Sbo SW (Southwest) and Sbo SE (Southeast), wherein the NW, NE, SW, and SE designations correspond to the relative geographical location of the ring stop nodes relative to the diagram shown inFIG. 100. The ring stop nodes provide ingress and egress points for enabling signals and corresponding messages to cross between ring0 and ring1. For the North buffered switch ring stop nodes Sbo NW and Sbo NE, this is facilitated by a NW Ingress block114, a NE Egress block116, a NE Ingress bock120, and a NW Egress block118. For the South buffered switch ring stop nodes Sbo SW and Sbo SE this is facilitated by a SW Ingress block122, a SE Egress block124, a SE Ingress bock126, and a SW Egress block128. Each of the pathways between ring0 and ring1 employing an Ingress/Egress block pair implement a “half-tunnel” employing a one-way message ordering mechanism that is configured to facilitate transfer of message data between ring0 and ring1 in a manner that ensures a message of a first message class will be delivered before a related message of a second message class.

In the context of maintaining cache coherence in a multi-processor (or multi-core) environment, various mechanisms are employed to assure that data does not get corrupted. For example, in system100, each of processor cores102is provided access to a shared memory store130, which typically will comprise one or more banks of dynamic random access memory (DRAM). For simplicity, the memory interface circuitry for facilitating connection to the shared memory store is not shown; rather, the processor cores in each of ring0 and ring1 are shown respectively connected to the memory store via a home agent node0(HA0) and a home agent node1(HA1).

As each of the processor cores executes its respective code, various memory accesses will be performed. As is well known, modern processors employ one or more levels of memory cache to store cached memory lines closer to the core, thus enabling faster access to such memory. However, this entails copying memory from the shared (i.e., main) memory store to a local cache, meaning multiple copies of the same memory line may be present in the system. To maintain memory integrity, a cache coherency protocol is employed. Under the well-known MESI cache coherency protocol, when a processor (or core) makes a first copy of a memory line from main memory to its local cache, a mechanism is employed to mark the cache line as Exclusive (E), such that another core attempting to access the same memory line knows it does not have exclusive access to the memory line. If two or more cores have copies of the same cache line and the data in the line has not been changed (i.e., the data in the caches is the same as the line in main memory), the cache lines are in a shared (S) state. Once a change is made to the data in a local cache, the line is marked as modified (M) for that cache, and the other copies of the line are marked as Invalid (I), since they no longer reflect the changed state of data for the line. The state returns to Exclusive once the value in the modified cache line is written back to main memory.

Recently, Intel® Corporation introduced a new Forward or “F” state added to a modified MESI cache coherency protocol called the MESIF cache coherency protocol. The F state indicates that a cache should act as a designated responder for any requests for the given line. In a system of caches employing the MESI protocol, a cache line request that is received by multiple caches holding a line in the S state will receive multiple responses. In a system of caches employing the MESIF protocol, a cache line request will be responded to only by the cache holding the line in the F state.

It is noted that the MESI and MESIF protocols are examples of cache coherency protocols, and accordingly these are not to be limiting, but are used herein to explain the use of exemplary message classes.

It is also common to have multiple levels of caches, with caches closest to the processor core having the least latency and smallest size, and the caches further away being larger but having more latency. For example, a typical configuration might employ first and second level caches, commonly referred to as L1 and L2 caches. Another common configuration may further employ a third level or L3 cache.

In the context of system100, the highest level cache is termed the Last Level Cache, or LLC. For example, the LLC for a given core may typically comprise an L3-type cache if L1 and L2 caches are also employed, or an L2-type cache if the only other cache is an L1 cache. Of course, this could be extended to further levels of cache, with the LLC corresponding to the last (i.e., highest) level of cache.

In the illustrated configuration ofFIG. 1, each processor core includes a processing engine132coupled to an L1 or L1/L2 cache134, which are “private” to that core. Meanwhile, each processor core is also co-located with a “slice” of a distributed LLC136, wherein each of the other cores has access to all of the distributed slices. Under one embodiment, the distributed LLC is physically distributed among N cores using N blocks divided by corresponding address ranges. Under this distribution scheme, all N cores communicate with all N LLC slices, using an address hash to find the “home” slice for any given address. Suitable interconnect circuitry is employed for facilitating communication between the cores and the slices; however, such circuitry is not show inFIG. 1for simplicity and clarity.

As further illustrated, each of nodes104in system100is associated with a cache agent138, which are configured to perform messaging relating to signal and data initiation and reception in connection with a coherent cache protocol implemented by the system, wherein each cache agent138handles cache-related operations corresponding to addresses mapped to its collocated LLC136. In addition, in one embodiment each of home agents HA0and HA1employ respective cache filters140and142, and the various caching and home agents access and update cache line usage data stored in a directory144that is implemented in a portion of shared memory130. It will be recognized by those skilled in the art that other techniques may be used for maintaining information pertaining to cache line usage.

As the number of cores increase in a system, the amount of message traffic needing to maintain cache coherence also increases. Different approaches may be used to reduce message traffic collisions and reduce latencies. One of these approaches is to use a ring interconnect, such as employed by system100. Moreover, if separate wires are used for the different message classes, performance is further enhanced.

However, the separation of message classes on independent interconnect paths can lead to problems relating to message class ordering. For example, under one cache coherency protocol, a combination of Global Observation (GO) and Snoop (Snp) messages are employed (in part) for managing the cache line state data. When a GO message and a Snp message pertain to the same cache line, the GO message must precede the Snp message to provide unambiguous transfer of ownership to a core.

In the following description and as used further herein, operations are coarsely divided into two categories—those performed by a processing core and those that are performed by the rest of the system. Accordingly, operations associated with a processor core are referred to as a Core operation, while the rest of the system is termed Uncore. The following is described in the context of usage of GO and Snoop messaging and associated operations to support cache coherency. However, similar principles may be employed to support one-way ordering of other types of message classes.

When the Uncore returns a GO response to a Core, the expectation is that a subsequent Snoop to the address of the request receiving the GO would see the results of that GO. For example, if the Uncore sends GO for an RFO (read for ownership) request followed by a snoop to the same address in the next Uncore clock, then in certain cases one would expect the core to transition the line to M state and reply with a RspIFwdM (core cache is modified and will forward data and invalidate its copy) response back to the Uncore. In order to implement this principle, the protocol links the Request and Response Channels in a single tunnel such that the Core will receive the 2 messages in separate Core clocks in the proper order, allowing the Core to satisfy the guarantee. However, the Uncore must send the snoop message at least 1 clock cycle after the GO message, in order to make the order completely unambiguous.

In accordance with aspects of the invention, a mechanism is provided to enforce a one-way ordering between two message classes (in this example, GO<=Snp i.e., Snp cannot pass GO) across an unordered interconnect composed of various hops (in this example, each hop is a full ring or half ring) with buffering between each hop. Both the interconnect and the buffering are separate for each message class.

For each hop (whether starting from the original sender, or from inter-hop buffering), it is presumed that there is a way for the sender to confirm receipt of the “leader” message (GO) at the receiver. In the example, where each hop is a full ring or half ring with bounce flow control, this is done via a “mini-ring” at the sender which remembers when the message was sent, and knows how many cycles it would take for a bounced message to reappear at the sender's ring stop. The sender will know the message has been received if it does not pass by the sender on the ring at the time indicated by the mini-ring shadowing its path. This pre-requisite could also be achieved by fully crediting the message, explicit acknowledgement by the receiver, or some other means.

The mechanism therefore needs to ensure that within the buffering between each hop, a “follower” (Snp) message that is received cannot be sent before any relevant “leader” (GO) message previously received. An ideal measure of “relevancy” in this example would be to use the cache line address and receiver (sender is always the same for a given cache line address), but the cache line address is not present in the GO message. The next-best measure in the example would be a sender-receiver pair, but the Snp message can have multiple receivers, which would complicate this approach. The example here thus first presumes that all GO messages passing through a given buffer are relevant to all Snp messages passing through the same buffer, and then shows how one can extend the mechanism to order Snp/GO only when they are from the same sender.

FIGS. 2a-eillustrate the use of a mini-ring scheme for ensuring message ordering is maintained for a ring interconnect architecture employing independent message classes, according to one embodiment. Each of the diagrams inFIGS. 2a-erepresent a state in time (i.e., timeframe) showing the progress of GO and Snp messages that are generated by the agent (agent6) for Core2. In this example, processing engine (Eng)2of core2desires to perform a write request to a memory location having an address corresponding to a cache line having a exclusive copy stored in the LLC associated with node Cbo6(collocated with core6) and serviced by the agent6. A GO message must be received to indicate transfer of ownership of a cache line. To make the ownership transfer unambiguous, the GO message must be received prior to any Snp messages corresponding to subsequent transactions for the same address. Meanwhile, the actual data corresponding to the cache line may be transmitted asynchronously to the requestor using data transfer facilities that are separate from the rings used for the GO and Snp messages. For example, as discussed above, each of the cores in the system may be connected to each LLC via a separate (from the ring architecture) interconnect. Alternatively, one or more ring paths in a ring interconnect architecture may be used for transfer of data.

The illustrated timeframe begins at the point in time when agent6has initiated delivery of a copy of the cache line data stored in the LLC of agent6to Core2. At this point, a GO message is placed on the ring (i.e., ring0) at node Cbo6. In order to place a message on the ring, there must be an empty slot corresponding to the message class. In the illustrated embodiment, the applicable ring is AK; accordingly, there must be an empty slot on the AK ring at node Cbo6to place the GO message on ring AK of ring0.

For point of illustration, Agent6is depicted inFIG. 2aas placing a GO message in ring AK of ring0 at node Cbo6at a time cycle “0”. During each successive time cycle, message data on ring AK advance between adjacent nodes in the ring in a counterclockwise manner. Accordingly, the advancement of the GO message is depicted by circles labeled “GO n, where n represents the time cycle. In one embodiment, a time cycle corresponds to a clock cycle employed for the ring interconnect. In general, the clock cycle may be the same as the clock cycle used for a core, may be a multiple of the core clock cycle, or may be separately clocked.

As the GO message traverses the ring it reaches its destination node, which is node Cbo2collocated with Core2. It is possible for a message to be “bounced” at its intended destination node, due to timing mismatch and/or buffer availability. An example of a message that has been bounced is depicted at a time cycle8corresponding to timeframe200inFIG. 2a. As a result, the message will not be received by Core2, and will be forwarded around the ring until it can be received at its intended destination. An example of this is depicted inFIGS. 2b-d.

The mini-ring employed by agent6shadows the progression of the messages it places on the ring such that it can determine if a message has been received by failing to detect the presence of the message at its corresponding node (i.e., node Cbo6) at an appropriate time cycle offset. For example, for ring0 there are16nodes, so the time cycle offset is 16 time cycles. Accordingly, at time cycle16agent6will check AK ring data at Cbo6and see whether it corresponds to a GO message it placed on the ring at time cycle0. If it does not, then the agent knows the GO message was received at its destination, and was not bounced. If the AK ring message is the same GO message, then the message was bounced; as a result, the cycle counter in the min-ring is reset for the GO message, as depicted at timeframe202inFIG. 2b.

The process is continued, with the GO message traversing the ring0 nodes a second time until a time cycle24corresponding to a timeframe204is reached, as shown inFIG. 2c. At this point, there is sufficient buffer space available at the interface to core2to receive the GO message. When a destination core is able to receive a message, the message is termed to be “sunk.” Accordingly, the GO message is sunk at timeframe204corresponding time cycle24.

As shown inFIG. 2d, the slot corresponding to the GO message data at timeframes200and202continues to traverse ring° until it returns to node Cbo6at a time cycle32corresponding to a timeframe206. At this point, agent6checks the corresponding AK ring message data and determines that it does not match the message data sent16time cycles prior. As a result, agent6determines that the GO message has been sunk, and it does not need to track the GO in its mini-ring anymore. Moreover, since the GO message has been sunk, a Snp message corresponding to the address can now be sent on ring IV of ring0. This is depicted inFIG. 2e, wherein at a timeframe208corresponds to 6 time cycles after the Snp message is placed on the IV ring of Ring0. As with the GO message class, Snp messages can only be placed on the ring when a corresponding empty slot is available during a given time cycle. Also, as before, a Snp message can only be sunk (i.e., received at a destination node) if adequate buffer space is available. Thus, the Snp message may traverse at least part of the ring one or more times until it is sunk.

The preceding mini-ring scheme guarantees one-way ordering of messages in independent message classes mapped to different rings of Ring0 relating to the same address. For example, since a Snp message relating to a transaction cannot be placed on the ring until after a corresponding GO message has been sunk, there is no way that the Snp message will ever be sunk before the GO message.

However, the mini-ring scheme doesn't facilitate one-way ordering of messages in independent message classes when the messages must cross between ring interconnects, such as between ring0 and ring1 in system100. As described in detail below, this is facilitated via a one-way message ordering mechanism employed in the buffered switches that cross between the two rings.

FIG. 3is a high level block diagram showing further details of the buffered switches corresponding to the one-way ordering mechanism of system100. InFIG. 3, details of the blocks for the North buffered switches are shown—however, it will be understood that the South buffered switches (e.g., the pathways between the Sbo SW and Sbo SE nodes) are configured in a similar manner.

In one embodiment, NW Ingress block114includes an ingress block for each of the message class rings; in this example these include an AD ingress block300, an AK ingress block302, an IV ingress block304, and a BL ingress block306. In one embodiment, each of the ingress blocks includes a pair of Write (WR) ports, except for IV ingress block306. An arbiter308is employed for managing transfer of signals for the ingress blocks to NE Egress block116. In one embodiment, NE Egress block includes an AD Egress block310, an AK Egress block312, an IV Egress block314, and a BL Egress block316.

FIG. 3also shows NE Ingress block120and NW Egress block118. It will be understood that each of these blocks have a similar configuration to their respective Ingress and Egress blocks shown in the upper portion ofFIG. 3and described above. As further shown, each of the ring interconnect paths of ring0 and ring1 include a pair of signal paths for each independent message class ring, one for sending messages clockwise (CW) around a ring, and the other for sending messages counterclockwise (CCW). Accordingly, there is a pair of input signals corresponding to each message class that is received by an ingress block, buffered and forwarded to an egress block. As discussed above, each signal path is physically implemented using multiple electrical pathways, with reference to a “signal path” or “wire” used for simplicity.

FIG. 4shows a further drill-down of details of an Ingress and Egress block, according to one embodiment. An Ingress block400includes de-multiplexers402,404,406, and408for de-multiplexing the AD and BL signals into an AD bounceable FIFO410, an AD credited FIFO412, a BL bounceable FIFO414and a BL credited FIFO416. Respective arbiters418and420are used to arbitrate the AD and BL outputs to be received by an opposing SBo's Egress block. Meanwhile, the CCW and CW AK and IV signals are buffered in a respective AK bounceable FIFO422and an IV bounceable FIFO424. The outputs of the AK and IV FIFOs are provided as inputs to the opposing SBo's Egress block.

An Egress block426receives the signals output by a corresponding Ingress block. De-multiplexers428and430respectively de-multiplex the AD and BL signals into an AD bounceable FIFO432, an AD credited FIFO434, a BL bounceable FIFO436and a BL credited FIFO438. The outputs of these FIFOs are arbitrated by arbiters440,442,444, and446. Additionally, the AK and IV signals from the Ingress block output are respectively received by an AK Egress block448and an IV Egress block450.

FIG. 4also shows a GO/Snoop Interlock between AK Bounceable FIFO422and IV Bounceable FIFO424, and a GO/Snoop Interlock between AK Egress block448and IV Egress block450. Details of one embodiment of a GO/Snoop Interlock are discussed below with reference toFIG. 5. As shown by the dashed box inFIG. 4and illustrated inFIG. 5, the Go/Snoop Interlock includes components that are part of both an ingress and egress block pair. In brief, the interlock provides a one-way message ordering mechanism that ensures that messages of a first class (e.g., GO messages on AK) received at a given ingress block cannot be passed by messages of a second class (e.g., Snoop messages on IV) received at the same ingress block. Meanwhile, messages of the first class are permitted to pass messages of the second class under applicable circumstances.

FIG. 5shows another illustration of the Ingress and Egress block configurations. In this diagram, data are showed being received from an Ingress Sbo node (Sbo NW) at an Ingress block, being passed between the Ingress block to an Egress block, and forwarded to an Egress Sbo node (Sbo NE).

FIG. 6shows further details of one embodiment of a one-way message order mechanism600. The mechanism employs a GO Egress Queue602, a Snp Egress FIFO604, a GO Ingress FIFO606and a Snp Ingress FIFO608. Go Engress Queue602includes an IFV Ptr (In-flight Vector pointer)610, while Snp Egress FIFO includes an SSN (Snp Serial Number) data block612, and a Snp Epoch block614. Go Ingress FIFO606includes a GO epoch data block616, and Snp Ingress FIFO includes an SSN data block618and an Snp epoch data block620. Toward the top of mechanism600is a mini-ring622, an “epoch delta counter” (EDC) register624, an “Egress Serial Number (ESN) register626and a decision block628. Depicted in the center portion of the diagram is a “GO epoch vector” (GO-EV) register630, a “GO In-flight Vector” (GO-IFV) register632, a Tail Ptr634, a Head Ptr636, and a Sep Ctr (separation counter)638. Toward the bottom of the diagram is a GO epoch register640, a Snp epoch register642, and an Ingress Serial Number (ISN) register644.

The Ingress and Egress FIFOs are typical of buffers used by the buffered switches connecting rings 0 and 1 mentioned above. However, as further detailed inFIG. 2, each buffered switch employs buffering and related circuitry for multiple message classes employing independent paths. It will be understood that similar circuitry may be implemented for each of the buffered switches in system100.

The functionality of the GO/Snoop interlock is provided by the circuit components shown inFIG. 6that are coupled between the ingress and egress buffers (i.e., GO Egress Queue602, Snp Egress FIFO604, GO Ingress FIFO606and Snp Ingress FIFO608). As discussed above, the GO/Snoop interlock comprises a one-way message ordering mechanism that ensures that messages of a first class (e.g., GO messages) received at a given ingress block cannot be passed by messages of a second class (e.g., Snoop messages) received at the same ingress block.

In accordance with one embodiment of the invention and reference to the flowchart ofFIGS. 7A and 7Band the schematic diagram ofFIG. 6, the following operations are performed to facilitate one-way ordering of GO and Snp messages such that GO messages for the same cache line are guaranteed to precede a corresponding Snp message. The operations are described using corresponding operation numbers below and in the flowchart.

1. In a block700ofFIG. 7A, the process begins by incrementing an “ingress serial number” in ISN register644on receipt of each GO message at a buffer ingress (e.g., GO ingress FIFO606). In one embodiment, the ISN has a range of 2× (GO ingress+GO-IFV size (described below in operation 4)) i.e., it has a wrap bit. The current “GO epoch” bit stored in GO epoch register640is stored with the GO message (after any setting by a Snp message received in the same cycle, see operation 2), as shown by GO epoch data block616, and the “GO epoch” bit is reset (this takes precedence over the set in operation 2). The “Snp epoch” bit is then set in Snp epoch register642(this takes precedence over the reset in operation 2). The initial value of the “GO epoch” bit is one, and the initial value of the “Snp epoch” bit is zero.

2. As shown in a block702, on each Snp message received by the buffer ingress, the current ISN (before any increment by a GO message received in the same cycle, see operation 1) is stored in the Snp FIFO entry as the Snp serial number (SSN) (e.g., in SSN data block618in Snp Ingress FIFO608). The current “Snp epoch” bit (before any setting by a GO message received in the same cycle, see operation 1) is stored in Snp epoch data block620with the Snp message, and the “Snp epoch” bit is reset in Snp epoch register642. The “GO epoch” bit is then set in GO epoch register640.

3. On each GO message sent by buffer egress, the buffer mini-ring622is employed to track GO message receipt at the next receiver (details in subsequent operations), as shown in flowchart block704. Mini-ring622works in a similar manner to the mini-ring described above for ensuring one-way message ordering within a ring interconnect. In a manner similar to that described above, it shadows the progress of the GO message as it traverses nodes in the Egress ring (i.e., the ring the messages are being transferred into) and determines when the GO messages are sunk.

4. The “GO in-flight vector” (GO-IFV)632tracks GO messages in-flight within the GO egress queue602or the mini-ring622, as shown in flowchart block706. Functionally, the size of the GO-IFV632could vary from one entry up to many; its use is to tolerate the GO egress queue and mini-ring depth and the out-of-order nature of egress based on direction/polarity and the mini-ring based on bouncing, as detailed below. The recommended size would be somewhere between the mini-ring depth and the size of the GO Egress queue plus the mini-ring depth. Corresponding data associated with the GO in-flight vector include tail pointer634, head pointer636, and separation counter638.

5. On each GO message moving from buffer ingress to buffer egress, set the GO-IFV bit at the tail pointer634and increment the tail pointer and separation counter638. Store the (pre-increment) tail pointer in the IFV-Ptr field of the egress entry in GO Egress Queue602. Store the GO epoch bit from the ingress entry in a separate “GO epoch vector” (GO-EV) register630at the same pointer location. These operations are depicted in flowchart block708.

6. On each GO message sent by buffer egress, store the IFV Ptr610from the egress entry in mini-ring622, as shown in flowchart block710.

7. On each mini-ring deallocation (i.e., GO sink), use the pointer stored in the mini-ring entry to clear the corresponding GO-IFV bit as shown in flowchart block712.

8. As shown in flowchart block714inFIG. 7B, during each cycle, the bit of GO-IFV register632that is at the head pointer (Head Ptr636) is checked. If it is zero, and the separation counter is non-zero, Head Ptr636is incremented, Sep Ctr638is decremented, and the “egress serial number” (ESN) in ESN register626is incremented. If in addition to that the GO-EV bit at the Head Ptr before the Head Ptr was incremented is set, the “epoch delta counter” (EDC) is decremented. In one embodiment, the EDC has a range of +/− (Snp ingress+Snp egress size), and is always negative or zero.

9. If the GO-IFV separation counter is “full” (i.e. equal to GO-IFV size), stop moving GO messages from ingress to egress, as shown in flowchart block716.

10. On each Snp message sent by the buffer egress, the value in SSN data block612from the FIFO entry in Snp Egress FIFO is checked against the value in ESN register626, conditional on the value of the EDC register624. If the EDC value (after a speculative increment by the Snp message, see operation 12) is negative, or it is zero and the SSN is equal to the ESN, then all GO messages in the buffer at the time the Snp message arrived have been received at the destination and the Snp message can be sent. Otherwise (the EDC is non-negative and the SSN is greater than the ESN), the Snp message cannot be sent. These operations are shown in flowchart block718.

11. As shown in flowchart block720, when a Snp message fails this check, its SSN is recorded. Until the ESN becomes equal to the SSN, the buffer does not attempt to send any Snp messages. The EDC does not have to be checked because in this case it cannot become negative until the ESN becomes equal to the SSN. This means that each Snp message will be shot down at most once.

12. When the Snp message check is passed and the Snp message is forwarded to the receiver (i.e., forwarded from the Snp Egress FIFO604), if the corresponding Snp epoch bit is set, EDC register624is incremented, as shown in flowchart block722.

To extend this concept to per-source tunneling, a per-source ISN, ESN, GO and Snp epoch bits, and an EDC are employed. A per-source GO-IFV is not needed. In one embodiment, both GO and Snp messages already carry the source in the message payload, so no additional storage is required. The Snp message check at egress may become more complex, as it needs to choose the proper counters for comparison. To extend this concept to two GO messages received per cycle, the following can be done: (a) on any cycle that two GO messages are received, ISN is incremented by two; (b) at most one of the two GO messages received may have an epoch (whichever appears older in the GO Ingress FIFO). To extend this concept to a Snp Egress Queue (instead of FIFO) which can have Snp messages destined for opposite directions sent out-of-order, the following can be done: (a) arriving Snp messages carry an indication of the direction for which they are destined; (b) GO messages are tagged with two GO epoch bits maintained at Ingress, one corresponding to each Snp message direction; (c) Snp messages are tagged with one of two Snp epoch bits maintained at Ingress, depending on the direction for which they are destined; (d) two EDCs are maintained at Egress and are updated at the time of each GO message sinking as tracked by the mini-ring, according to the corresponding GO epoch bits for each Snp direction; (e) each Snp checks the proper EDC according to the direction for which it is destined, before dispatching from Egress.

The epoch portion of the scheme is employed because there is nothing to prevent the ESN from racing arbitrarily ahead of the SSN's in the Snp FIFO entries. The epoch controls when the ESN/SSN comparison is relevant, and when it can be ignored.

The serial number portion of the scheme is employed because a Snp needs to order with the immediately previous relevant GO. At the time the GO is received (and potentially starts a new epoch) it is not known whether it will become the last GO received before a Snp that is relevant to it. The serial number allows the Snp to identify when the immediately previous GO of the same epoch has been received at the next hop.

A new Snoop epoch is assigned any time a Snp arrives between two GOs. The GO after the Snp is assigned the next GO epoch. At the time the last GO before the Snp arrives, all the GO's still in the buffer (or mini-ring) have an unambiguous serial number, since the serial number size is 2× (GO ingress+GO-IFV size). When the next Snp arrives it will get the same serial number. Even if it gets to the head of egress before any more GOs are sent, it will know it is younger (i.e., received after the GO) based on the serial numbers being unambiguous. The following GO will be assigned the next epoch; so if that GO is sent before the Snp, then the Snp will ignore the serial number comparison based on the negative EDC. The EDC can never become so negative that it wraps to a positive value, since it is sized based on (Snp ingress+Snp egress size) and the epoch changes at most by one for each Snp.

In the foregoing example, the one-way message ordering mechanism is implemented between a pair of ring interconnects. However, the concepts disclosed herein may be implemented in other types of interconnects as well.

For example, consider an interconnect with an arbitrary topology, with any number of nodes interconnected by links. Each node provides the interface between a number of local agents to the rest of the interconnect. Each node also acts as a router in the interconnect. The nodes may have multiple input and output ports—including multiple local ports for sending/accepting messages from/to the local agents. Additionally, input or output ports may have associated buffers. However, the nodes may also be buffer-less (e.g., 2D Mesh nodes are buffered and have 4 input/output ports, and one local port, while ring nodes in one embodiment are buffer-less and have 2 input/output ports, and 1 or 2 local ports).

The messages in this exemplary interconnect are divided into a number of classes (e.g., ring messages are divided into 4 major classes, AD/BL/AK/IV). The point to point links connecting nodes either provide separate physical links for different message classes allowing for messages of different classes to be sent in parallel (e.g., using a ring configuration), or are virtualized, so that all messages classes share the same physical links and need to arbitrate and be sent in interleaved fashion (e.g., some 2D Mesh, or QPI fabric).

Each node passes messages belonging to the same class and between the same input and output ports in the order received, however if the node is buffered it may reorder messages that belong to different classes (this allows forward progress of different message classes by the interconnect). Notice that messages belonging to the same class sent between a source node and a destination node in the interconnect may not (or even need to) arrive in the order sent (this can happen if the messages are allowed to bounce, as explained later on).

Nodes may or may not have input port or output port buffers (in the form of FIFOs) to store messages before forwarding them. Nodes with multiple input or output ports have an internal interconnect (with physical or virtualized links) and associated flow control, arbitration, etc. enabling them to transfer messages from input ports to output ports. The nodes either support virtual channels for different message classes and share common physical links between the input and output ports, or have per message class buffering and internal interconnect between input and output ports.

If the node is buffered, then it uses back-pressure when its (input) buffers are full (and this could be based on the message type or destination port). A message that is back-pressured by the end node of a link stays in the sender node's (output) buffers if the node is buffered; but if the node is buffer-less, then the message is bounced and rerouted on the interconnect on a path of links that will eventually lead it back to the current node so that it gets another opportunity to be accepted by the node that previously bounced it (these are loss-less interconnects where message are never dropped). Note that messages may further be divided to credited and uncredited, where credited messages are always guaranteed to be accepted. And credits can be end-to-end or point-to-point.

Note that an interconnect may have a mixture of buffered and bufferless nodes (e.g., the system100interconnect has two rings composed of bufferless nodes interconnected via two bi-directional buffered switch nodes).

In such a general type of interconnect, there may be two messages belonging to two different message classes C1and C2, with the requirement that if any node A sends a pair of these messages that are related in a certain way (e.g., related to the same address) to any other node B, then the C2message (Snoop in the foregoing example) shall be received by B after the related C1message (GO in the example); i.e., C2messages shall not bypass related C1messages on the path from A to B. Note that this does not prevent C1messages from bypassing C2messages.

To simplify the solution to this problem, we first require the two messages to take on the same nodal route in the interconnect, because if they were to take on different routes on the interconnect controlling their order of arrival may not be possible, or would require extraneous mechanisms. Note that such common routes may include circular paths, in case the messages may bounce; if both messages may bounce, we require their bounce paths to be the same as well. Next, we break the path between the source and destination nodes into sections, such that each section is either composed solely of buffered nodes, or solely of buffer-less nodes (the nodes at the interface between the sections are special nodes that act as buffer-less nodes connecting certain input ports to certain output ports, and act as buffered nodes connecting other input/output ports, such as the buffer switch nodes in system100). Finally, on each of the sections of this path, we enforce rules that guarantee that the C2messages will not bypass related C1messages (to the particular receiver).

In the case of the exemplary ring interconnect of system100, the two messages of interest are Snoop and GO (belonging to two different message classes). On the buffer-less part of the interconnect (i.e., the rings) these messages are sent on separate physical links. The SBos are the (physically stretched) buffered nodes of this interconnect, with input and output FIFOs per message class (more accurately, per AD/BL/AK/IV class) and separate physical links in between input and output FIFOs.

To impose order on the buffer-less paths (e.g., rings in the interconnect) the mini-ring mechanism is employed to ensure Snoops are sent only after GOs are received at the other end of the path. To impose order on the buffered path (e.g., the buffered switch nodes of the interconnect), the half-tunneling scheme is implemented within each buffered node (i.e., between each pair of input and output ports of buffered nodes). Note that the proposed half-tunneling on the buffered path (and the mini-ring mechanism) prevents Snoops from bypassing GOs, irrespective of source and destination of the messages. The scheme can be extended to enforce such ordering requirement per destination (including a property at destination, e.g., cache line address, etc), and theoretically even per source/destination pair, but at increasingly higher cost.

If the C1message cannot bounce on a buffer-less portion of the path, then the mini-ring mechanism would degenerate to a simple mechanism where the senders may send any C2message right after (all earlier/related) C1messages, without having to wait for them to be accepted at the end point of the current path.

If the buffered section of the path between a sender node and a receiver node contains multiple nodes (e.g., in a 2D mesh), then each such node would implement the half-tunneling scheme between each pair of input and output ports. Accordingly, Snoop and GO sequences and epochs between different input and output ports would be tagged and identified separately. Each output port would then order C1and C2messages that it receives in the context of which input port they came from. This of course adds further complexity to the proposed scheme, but the necessary changes/extensions are straight forward.

To summarize: If on the path between a source and a destination node in the interconnect, each node guarantees delivery of any C1message (that it receives) before all related/later C2messages (that it receives) to a next node on the path (e.g., a node at the interface of buffer-less and buffered sections of the path, or an adjacent node in a buffered section of the path, or a node in the buffer-less section of the path), then by induction any C1message sent from the source would be received at the destination before all related/later C2messages sent.