Interconnect switch method and apparatus

[0002] The invention relates to interconnect switches for use in devices and systems.

[0003] A multiprocessor system typically includes a plurality of processors. In some multiprocessor systems, a distributed storage or memory system having plural storage or memory modules is employed. The plural processors are capable of executing in parallel, and thus are able to read and write to the memory modules concurrently. As a result, multiple data streams often have to be communicated between the processor nodes, processors and the memory modules, and the processor nodes and distributed storage at the same time.

[0004] To improve concurrency, an interconnect switch is employed to interconnect the processor nodes, the processors and the memory modules, and the processor nodes and storage. The interconnect switch has a number of input ports (that usually correspond to the number of processors) and a number of output ports (that usually correspond to the number of memory modules). Typically, the interconnect switch is a crossbar-switching network that couples the input ports to the output ports. The interconnect switch can be implemented in an integrated circuit device such as an application specific integrated circuit (ASIC) device.

[0005] In a typical interconnect switch, a first-in-first-out (FIFO) queue is associated with each of the input ports. One of the issues involved in many interconnect switches is blocking of data. When data at the front of an input FIFO queue cannot be forwarded because of contention with another input FIFO queue for the same output port, trailing units of data are blocked from being forwarded to another output port that is available. As a result, a delay is experienced in the communication of data through the interconnect switch. In many high-speed systems, such delays may cause degradation of overall system performance.

[0006] In general, a device comprises a plurality of input ports, a plurality of output ports, and an interconnect switch between the input and output ports. The interconnect switch comprises a buffer in a circular queue containing at least one pointer to indicate an available one of plural storage locations in the buffer.

[0007] Other or alternative features will become apparent from the following description, from the drawings, and from the claims.

[0008] FIG. 1 is a block diagram of an example embodiment of a node having components that are coupled by an interconnect switch.

[0009] FIG. 2 illustrates components of the interconnect switch of FIG. 1, which contains a plurality of input engines corresponding to input ports, a plurality of output engines corresponding to output ports, a central buffer, and a central buffer manager, in accordance with an embodiment.

[0010] FIG. 3 is a block diagram of components of the input engine, output engine, and central buffer manager of FIG. 2.

[0011] FIG. 4 illustrates contents of a “flit” that is stored in each entry of the central buffer.

[0012] FIG. 5 illustrates a central buffer pointer queue containing pointers to the central buffer in the interconnect switch of FIG. 1.

[0013] FIGS. 6A-6C illustrate different states of the central buffer pointer queue of FIG. 5.

[0014] FIG. 7 illustrates an example operation of the interconnect switch of FIG. 1.

[0015] FIG. 8 illustrates an output engine queue that stores pointers to the central buffer.

[0016] In the following description, numerous details are set forth to provide an understanding of the present invention. However, it will be understood by those skilled in the art that the present invention may be practiced without these details and that numerous variations or modifications from the described embodiments may be possible.

[0017] FIG. 1 illustrates an example node or system 10 that includes a number of components that are coupled by an interconnect switch 16. In the example of FIG. 1, the components that are coupled to the interconnect switch 16 include plural processors 12A-12D connected to a first set of ports 18 (“input ports”) of the interconnect switch 16, and memory modules 14A-14D connected to a second set of ports 20 (“output ports”). Data streams that occur as a result of processor execution (e.g., reads and writes of the memory modules 14A-14D) are routed through the interconnect switch 16. In another embodiment, the interconnect switch 16 can be used to interconnect processors with processors or to interconnect processor nodes with storage.

[0018] In accordance with some embodiments of the invention, the interconnect switch 16 enhances throughput through the interconnect switch 16 by employing a central buffer storage and queuing mechanism. Generally, the interconnect switch includes a central buffer that holds data units transferred from the input ports until respective output ports become available. A queuing mechanism allocates entries in the central buffer on an as-needed basis. Once a data unit from a central buffer entry is transmitted to an output port, the entry is indicated as being available for use again to store a data unit for another transfer operation. Indicators in the form of pointers are provided in the queuing mechanism to indicate which entries in the central buffer are available—as a consequence, compute- and time-intensive comparison operations need not be made to find available central buffer entries.

[0019] Another benefit of the central buffer and queuing mechanism is that head-of-the-line blocking at the input side is reduced, since data can be quickly moved from an input port to the central buffer. A further benefit is that allocation of resources in the interconnect switch is made flexible, with the allocation performed “on demand.” The on-demand allocation is possible by use of the central buffer and a circular queue containing pointers to storage locations in the central buffer. Thus, available resources that are not being used by inactive ports can be used for active ports, which increases utilization of interconnect switch resources and thus the efficiency and speed of the interconnect switch.

[0020] Further, by using the central buffer, the interconnect switch can handle packets that vary in size. Also, an efficient mechanism is provided to support multicasting of packets, which involves one input port transmitting packets to more than one output port. Also, “wormhole routing” can also be performed using some embodiments of the interconnect switch 16. Wormhole routing involves sending data as soon as the data is received, as compared to the “store and forward” technique.

[0021] FIG. 2 illustrates the general architecture of the interconnect switch 16. The interconnect switch 16 includes a plurality of input engines 102 that correspond to the input ports 18 and a plurality of output engines 108 that correspond to the output ports 20. A central buffer 106 has a number of entries that are used to store data units, referred to as “flits” (flow control digits). A flit is routed from one input engine 102 to a destination output engine 108. A flit can also be multicast from the input engine 102 to plural destination output engines 108. If a destination output engine 108 is available, then flit(s) from the input engine 102 can bypass the central buffer 106 for routing to the destination output engine 108. However, if the output engine 108 is unavailable (e.g., the output engine is busy receiving data of another input engine 102), then the flit(s) are stored into the central buffer 106 until the destination output engine 108 is ready to receive data. Storage of data from the input engine 102 into the central buffer 106 is managed by the central buffer manager 104.

[0022] As shown in FIG. 3, components of the input engine 102, the output engine 108, and the central buffer manager 104 are shown. Data is carried over an input link 120 from an input port 18 to the input engine 102, which includes an input link interface 122. The input link interface 122 manages the input physical layer protocol, which includes clock synchronization or re-synchronization. Additionally, the input link interface 122 manages link-level protocol messaging such as flow control signaling to the source node (e.g., sending acknowledgment signaling or credit available back to the source node). In the example of FIG. 1, the source node is a processor 12. The input link interface 122 also decodes the encoded incoming data into packet format.

[0023] The input engine 102 further includes an input first-in-first-out (FIFO) storage 124 that accumulates incoming data packets from the input link interface 122 to be forwarded to the central buffer 106 or to an output engine 108. A central buffer interface 126 is coupled to the input FIFO storage 124. The central buffer interface 126 checks for packet errors, segments the packets into flits, and requests the central buffer manager 104 to write flits into the central buffer 106. The input engine 102 does not necessarily have to have an entire packet before portions of the packet can be forwarded to the central buffer 106. As long as the packet header has been decoded and there is enough data for a flit, the flit is ready to be sent to the central buffer 106.

[0024] The central buffer manager 104 includes a central buffer pointer queue 220, a central buffer arbiter 230, and a routing engine 232. The central buffer pointer queue 220 is a circular queue (described further below) that includes addresses (referred to as “flit pointers”) pointing to storage entries in the central buffer 106. In one embodiment, the number of entries in the central buffer pointer queue 220 is equal to the number of storage entries in the central buffer 106. The central buffer pointer queue 220 can be implemented with random access memory, such as a static random access memory (SRAM) or a dynamic random access memory (DRAM). Alternatively, the central buffer pointer queue 220 can be implemented with other types of storage devices. The circular behavior of the central buffer pointer queue 220 is provided by a central buffer pointer queue controller 221, which generates addresses pointing to locations of the central buffer pointer queue 220 that are incremented as flit pointers in the central buffer pointer queue are being used. The addresses pointing to locations of the central buffer pointer queue are wrapped to respective initial values (e.g., zero) when they cross the last location of the central buffer pointer queue 220.

[0025] The central buffer arbiter 230 arbitrates among input engines and output engines for access to the central buffer 106. The input engine 102, as the consumer of the central buffer 106, requests the central buffer arbiter 230 for a flit pointer that points to a storage entry of the central buffer 106 into which a packet flit can be written. The output engine 108, as the recycler of the central buffer 106, returns a flit pointer to the central buffer pointer queue 220 after completing loading the flit data into the output FIFO.

[0026] In response to receiving a flit from the central buffer arbiter 230, the routing engine 232 determines a routing path and moves the first flit pointer (of the central buffer pointer queue 220) of the packet into an output pointer queue 114 of the target output engine 108. The output pointer queue 114 of each output engine 108 stores flit pointers to packet flits in the central buffer 106 that are to be transmitted by that output engine 108.

[0027] The interconnect switch 16 is also capable of performing multicasting of a packet from one input engine 102 to plural output engines 108. According to one embodiment, for a multicast packet, only one designated output port of the interconnect switch 16 is used for receiving the flit pointer. The routing engine 232 can select which one of the output engines 108 is to receive the multicast packet. The designated output engine 108 can then perform data replication to all other output engines 108 involved in the multicast.

[0028] In the illustrated embodiment, each output engine 108 includes a first output FIFO storage 110 and a second output FIFO storage 112. Packet flits that are to be transmitted are loaded into the FIFO storage 110 or 112, either from the central buffer 106 or directly from an input engine 102. Flits are accumulated in the output FIFO storage 110 or 112 until a packet is formed. The two transmitting data FIFO storage devices 110 and 112 are intended to function as a single FIFO queue. An output link interface 116 (in conjunction with a transmit engine 118) alternately selects the two FIFO storage devices 110 and 112 to transmit data. In another embodiment, instead of multiple FIFO storage devices, a single output FIFO storage is used.

[0029] One reason for using plural output FIFO storage devices is to support multicast. As a multicast flit arrives at the transmit engine 118 of the master output engine 108, there is an empty output FIFO storage in each output engine to store the data to be multicast. Without the second FIFO storage, the logic in the transmit engine 118 may have to wait until the output FIFO storage is empty before multicast data can be stored.

[0030] In addition, the output link interface 116 manages the output link layer protocol, including clock synchronization. The output link interface 116 also retrieves a packet from the output FIFO storage 110 or 112, encodes the data according to the link protocol, and transmits the packet.

[0031] In multicast operations, the transmit engine 118 of one of plural destination output engines 108 is selected as the “master” transmit engine, which is responsible for receiving multicast data and for distributing the data to the other output engines 108.

[0032] The output engine 108 also includes an output pointer queue 114, which is a circular queue similar to the central buffer pointer queue 220 in the central buffer manager 104. The output pointer queue 114 stores flit pointers that point to storage entries in the central buffer 106 that contain flits to be transmitted by the output engine 108. Based on a flit pointer retrieved from the output pointer queue 114, the transmit engine 118 accesses the corresponding location in the central buffer 106 to retrieve a flit for loading into output FIFO storage 110 or 112 and returns the flit pointer to the central buffer queue.

[0033] As shown in FIG. 4, the central buffer 106 includes multiple storage locations or entries 200, with each entry capable of storing a flit 202. A packet or cell contains one or more flits. In the example of FIG. 4, the illustrated packet or cell contains five flits 202A, 202B1, 202B2, 202B3, and 202C. As shown, the flits of one packet can be stored in non-sequential order within the central buffer 106. Each flit 202 contains a data portion that contains the data to be communicated; and a next flit pointer 206, Next_Flit_Ptr, which points to the location of the next flit in the packet. As shown in FIG. 4, the flit 202A is the first flit of the packet, while the flit 202C is the last flit of the packet. By using the Next_Flit_Ptr pointer 206, multiple flits can be linked together to form a packet. In addition, use of the Next_Flit_Ptr pointer 206 provides for a linked list structure that allows a packet to be variable in size. Thus, if a packet contains a greater or smaller number of flits, the number of entries 200 in the central buffer 106 are allocated accordingly.

[0034] Each flit 202 also includes a flit identifier (flit ID) 210, which identifies the position of the flit in a packet (e.g., first, middle, or last). Thus, the flit ID can indicate if a flit is the first flit of the packet, the last flit of the packet, or an intermediate flit between the first and last flits. In the example of FIG. 4, the flit 202A is the first flit, the flits 202B1, 202B2, 202B3 are the middle flits, and the flit 202C is the last flit of the packet. Each flit also includes a multicast bit mask 212 having plural bits, with each bit corresponding to an output port. If a bit in the multicast bit mask 212 is set to an active state, then the corresponding output port is selected for receiving data. To perform a multicast transmission, plural bits in the multicast bit mask 212 are set to the active state. If a unicast is performed instead, then only one of the bits of the multicast bit mask 212 is set active.

[0035] As shown in FIG. 5, the central buffer pointer queue 220, which in some embodiments is a circular queue, contains flit pointers to entries 200 of the central buffer 106. The central buffer pointer queue 220 is also associated with a head pointer 222 and a tail pointer 224. The head and tail pointers 222 and 224 are stored in respective head and tail pointer registers 226 and 228, which are part of the central buffer queue controller 221 (FIG. 3).

[0036] As shown in FIGS. 6A-6C, the central buffer pointer queue has three possible states. In FIG. 6A, the head pointer 222 is one position behind the tail pointer 224 to indicate that the central buffer pointer queue 220 is empty. However, in FIG. 6C, when both the head and tail pointers are pointing to the same location of the central buffer pointer queue 220, the queue 220 is considered to be full. An intermediate state of the central buffer pointer queue 220 is illustrated in FIG. 6B, where the head and tail pointers are apart to indicate that the pointer queue 220 is being processed. The first position after the position pointed to by the head pointer 222 is the first valid entry of the central buffer pointer queue 220. This position is pointed to by a pointer 223 that is equal to the head pointer 222 plus the value one. The valid entry contains a flit pointer to an available storage entry in the central buffer. Thus, generally, the head pointer 222 indicates an available location in the central buffer 106.

[0037] As shown in FIG. 6B, the entries of the central buffer pointer queue 220 between (in the clockwise direction) the tail pointer 224 and the head pointer 222 (including the entry pointed to by the tail pointer) contains invalid or blank entries. An invalid or blank entry of the central buffer pointer queue 220 does not contain a valid flit pointer.

[0038] The central buffer pointer queue 220 is initialized to the full queue state by setting both the head and tail pointers to the same value, such as a zero value or some other predetermined value. After reset, all flit pointers in the central buffer pointer queue 220 are available to all input ports. At reset, the entries of the central buffer pointer queue 220 store sequential flit pointers that point to a sequential order of entries in the central buffer 106. However, once operation begins, and the flit pointers are moved between the central buffer pointer queue 220 and the output pointer queues 114, the order of the flit pointers in the central buffer pointer queue 220 may become non-sequential.

[0039] An example operation of the interconnect switch 16 is illustrated in FIG. 7. The input engine 102 stores a packet 440 in its input FIFO storage 124. The packet 440 is divided into plural flits, with flit 442 being the first flit of the packet 440 and flits 444A, 444B, and so forth being the remaining flits. The input-engine 102 writes (at 402) the first packet flit 442 into an entry of the central buffer 106 that is pointed to (at 406) by flit pointer X. Flit pointer X is stored in a location 420 of the central buffer pointer queue 220 pointed to by the pointer 223. The flit pointer X in the location 420 is then moved (at 408) from the central buffer pointer queue 220 to the output pointer queue 114. As the flit pointer is moved from the central buffer pointer queue 220 to the output pointer queue 114, the head pointer 222 is incremented by one to point to the location (420) of the central buffer pointer queue 220. The pointer 223 is incremented by one to point to the next location (422).

[0040] The next flit 444A is loaded (at 404) from the input FIFO storage 124 to an entry of the central buffer 106 that is pointed to by a flit pointer at location 422 in the central buffer pointer queue 220, which is now pointed to by the pointer 223. The flit pointer at location 422 is then removed from the central buffer pointer queue 220 and stored in the Next_Flit_Ptr field of the flit 442 in the central buffer pointer queue 220. The head pointer 222 and pointer 223 are then incremented again. The same is repeated for the other flits 444B and so forth in the packet 440, with the flit pointers associated with such other flits stored in the Next_Flit_Ptr field of the previous flit 444. Thus, as described above, the flit pointer (X) pointing to the first flit of the packet 440 is stored in the output pointer queue 114, while the flit pointers of the remaining flits are stored in the Next_Flit_Ptr field of the flits in the central buffer 106. Although shown as being grouped together in the central buffer 106, the flits of the packet 440 can actually be distributed in non-consecutive entries in the central buffer 106, depending on the available flit pointers in the central buffer pointer queue 220.

[0041] In the example of FIG. 7, it is assumed that another packet 450 is already in the central buffer 106. When the output engine 108 is ready to transmit the packet 450, the transmit engine 118 (FIG. 3) accesses the output pointer queue 114 to retrieve the first flit pointer of the first flit of the packet 450. When the flit is retrieved (at 410) from the central buffer 106, the first flit pointer is returned (at 412) to a location of the central buffer pointer queue 220 that is pointed to by the tail pointer 224. The tail pointer 224 is then incremented.

[0042] The transmit engine 118 then uses the Next_Flit_Ptr field contained in the first flit to access the next flit of the packet 450. When the next flit is retrieved, the flit pointer in the Next_Flit_Ptr field is returned by the output engine 108 to the central buffer pointer queue at the location pointed to by the tail pointer 224. The above is repeated until the last flit has been retrieved and loaded (at 410) into the output FIFO storage 110 or 112.

[0043] The output pointer queue 114 is illustrated in FIG. 8. A head pointer 302 stored in a head pointer register 306 and a tail pointer 304 stored in a tail pointer register 308 points to two positions of the output pointer queue 114. Each entry of the output pointer queue 114 contains a flit pointer that points to a storage entry of the central buffer 106. The head and tail pointer registers 306 and 308 are initialized to an empty queue. The queue is empty when the head pointer 302 is one entry behind the tail pointer 304. The queue is full when the head pointer 302 and the tail pointer 304 are equal. At reset, the output pointer queue 114 is reset to empty. As flit pointers are moved from the central buffer pointer queue 220 to the output pointer queue 114, the tail pointer 304 is advanced. When flit pointers are returned to the central buffer pointer queue 220, the head pointer 302 is incremented.

[0044] While the invention has been disclosed with respect to a limited number of embodiments, those skilled in the art will appreciate numerous modifications and variations therefrom. It is intended that the appended claims cover such modifications and variations as fall within the true spirit and scope of the invention.