Message routing in a torus interconnect

#Data communication between components of a computer system can be provided in a number of ways. In many large storage systems, for example, the interconnection solutions may be based on bus architectures such as the small computer system interconnect (SCSI) or fibre channel (FC) standards. In these architectures, multiple storage devices such as hard disk drives may share a single set of wires or a loop of wires for data transfers.

#Such architectures may be limited in terms of performance and fault tolerance. Since all of the devices share a common set of wires, only one data transfer may take place at any given time, regardless of whether the devices have data ready for transfer. Also, if a storage device fails, it may be possible for that device to render the remaining devices inaccessible by corrupting the bus. Additionally, in systems that use a single controller on each bus, a controller failure may leave all of the devices on its bus inaccessible. In a large storage array, component failures can occur with significant frequency. As the number of components in a system is increased, the probability that any one component will fail at any given time increases, and, accordingly, the mean time between failures (MTBF) for the system is decreased.

#It may be desirable to minimize the effect of errors on data transmission between components and to improve performance by routing messages over an interconnection fabric. Multi-path interconnection fabrics can provide failover capabilities to networks. In an interconnection fabric including a network of nodes, multiple independent paths between any two nodes in the network can be possible. After a message is initiated by a source node, the message may pass through multiple intermediate nodes before ultimately reaching the destination node.

#FIG. 1 shows a functional block diagram of a computer system including a 5×5 torus interconnection fabric in accordance with embodiments of the present invention.

#FIG. 2 shows a functional block diagram of a node in accordance with embodiments of the present invention.

#FIG. 3 shows multiple target regions in a torus interconnect fabric in accordance with embodiments of the present invention.

#In the following description, reference is made to the accompanying drawings which form a part thereof, and which illustrate several embodiments of the present invention. It is understood that other embodiments may be utilized and structural and operational changes may be made without departing from the scope of the present invention. The use of the same reference symbols in different drawings indicates similar or identical items.

#Some portions of the detailed description which follows are presented in terms of procedures, steps, logic blocks, processing, and other symbolic representations of operations on data bits that can be performed on computer memory. A procedure, computer-executed step, logic block, process, etc., are here conceived to be a self-consistent sequence of steps or instructions leading to a desired result. The steps are those utilizing physical manipulations of physical quantities. These quantities can take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated in a computer system. These signals may be referred to at times as bits, values, elements, symbols, characters, terms, numbers, or the like. Each step may be performed by hardware, software, or combinations of the two.

#In accordance with some embodiments of the present invention, systems and methods for routing messages in a torus interconnection fabric are provided. The fabric includes a plurality of nodes, each node having, for example, four ports coupled to adjacent nodes in the fabric. A source node initiating a message in the fabric can transmit the message out of one of its four ports. Between a source node and a destination node, there are at least four independent paths which may be taken, depending on the output port from the source node. However, the precise path is not expressly delineated in the message. Instead, the message contains the address of the destination node, the address of the originating node, and a target region for the message. Each intermediate node is configured to receive a message via one of its four ports, and then select an appropriate output port based on the location of the port which received the message combined with the address and target information contained in the message. By providing a system by which four independent paths can be taken by a message, at least three intermediate nodes can fail in the fabric before the message is prevented from reaching the destination node.