United States Patent [191
`Frey, Jr. et a1.
`
`IlllllllllllllllllllllllllllllllIllll||l||Illllllllllllllllllllllllllllllll
`5,181,017
`Jan. 19, 1993
`
`USO05181017A
`[11] Patent Number:
`[45] Date of Patent:
`
`[54] ADAPTIVE ROUTING IN A PARALLEL
`COMPUTING SYSTEM
`[75] Inventors: Alexander H. Frey, Jr., Pasadena,
`Calif.; Joel M. Gould, Norwood,
`Mass; Charles M. Higgins, Jr., Baton
`Rouge, La.
`[73] Assignee: IBM Corporation, Armonk, NY.
`[21] Appl. No.: 386,521
`[22] Filed:
`Jul. 27, 1989
`
`[51] Int. Cl.5 .................... .. H04L 12/00; H04L 12/46
`[52] US. Cl.
`........... .. IMO/825.02; 395/200;
`340/826; 340/827
`364/200 MS File, 900 MS File;
`[58] Field of Search
`370/58; 379/826; 340/825.02, 827; 395/200
`References Cited
`U.S. PATENT DOCUMENTS
`
`[56]
`
`4,399,531 8/1983 Grande et a1. ...................... .. 370/60
`4,825,206 4/1989 Brice, Jr. et al.
`4,872,197 10/1989 Pemmaraju ......................... .. 379/93
`
`OTHER PUBLICATIONS
`“Hyperswitch Network for the Hypercube Computer”,
`
`E. Chow et al., 1988, pp. 90-99, California Institute of
`Technology, Pasadena, Calif. 91109.
`“The Torus Routing Chip", W. Dally et al., 1986, pp.
`187-196, Department of Computer Science, California
`Institute of Techn0l0gy, Pasadena, Calif., USA.
`
`Primary Examiner-Joseph L. Dixon
`Assistant Examiner-Gregory D. Leibold
`Attorney, Agent, or Firm-L. Keith Stephens; Marc
`Block; David Koffsky
`
`ABSTRACT
`[57]
`A multi-dimensional, multi-nodal routing mechanism is
`described for relaying information from node to node
`using a header consisting of route descriptor bits. Each
`node’s receiver/transmitter pair changes states as the
`information is guided to the destination node. The mes
`sage is propagated over several nodes simultaneously to
`traverse the nodes and reach the destination node
`quickly. When the ?nal node is reached, all alternate
`communication routes are freed.
`
`15 Claims, 8 Drawing Sheets
`
`:50
`
`—- XNIT FOR w+ "'---L 320
`301-; RC“! mm w+ -~
`__ OUTGOlNG
`mcoumc
`UNKS _.... Rm FROM w.___ CROSSBAR _.__ mnroa w- ’...22 LINKS
`
`FROM —-— RCVR FOR x+ --
`OTHER
`__.
`MODES 1%- RCVR FOR x- --
`
`-- xun FOR x+ 1212-3
`
`To
`omen
`—--— XMIT FOR x- 14-324mm
`
`311/ 'N‘ECTOR
`
`510
`
`CTOR )/331
`Elm“
`'
`33o
`
`NETWORK SEARCHED
`
`402
`
`3 s
`400 /
`
`HEADER
`0000 0101
`0000 0101
`0000 0001
`0000 0000
`
`/
`/ D (401
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1030, p. 1 of 16
`
`

`
`US. Patent
`
`Jan. 19,1993
`
`Sheet 1 of 8
`
`5,181,017
`
`(-20
`10 F I
`
`l
`
`l
`
`I
`
`l I l I I I I I l I L_JI__IL__IL_I
`
`100
`
`[22
`
`120 '
`
`_
`
`1o \+uom— —— 11 -
`PROCSSR
`ROUTING /
`/MEMORY
`MECHNSM
`
`NODE — ——
`r 220
`PROCSSR
`ROUTING /
`MEMORY
`MECHNSM
`
`' ' —J24
`
`' ‘ —
`
`130
`(23
`110
`21/
`12 +NODE- -—— 13 —;£—NODE— —
`\
`,210 \
`, 230
`PROCSSR
`ROUTING /
`PROCSSR
`RouIINc /
`/MEMORY
`MECHNSM
`/MEMORY
`MECHNSM
`
`FIG. 2
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1030, p. 2 of 16
`
`

`
`US. Patent
`
`Jan. 19, 1993
`
`Sheet 2 of 8
`
`5,181,017
`
`f'350
`
`f. 321 320
`301’
`-- m FOR m I.»
`--— RCVR mm w+ --
`oumomc
`mcoumc
`300 LINKS 30-5- RCVR mom W-->- CRQSSBAR _.._ xun FOR w- ‘"322 LINKS
`:1
`smcH
`rRouwL- RCVR FOR X+ ——-
`0mm __,
`NODES IL RCVR FOR X— ———
`
`32°
`
`—-— xun FOR x+ "-13 T0
`0mm
`—>— XMIT FOR x- /f>'3-24NooEs
`
`311-1 INJECTOR --
`
`310
`
`mam Iii‘ .
`330
`
`NETWORK SEARCHED
`
`402
`
`HEADER
`0000 0101
`0000 0101
`0000 0001
`0000 0000
`
`J s
`‘00
`
`401
`
`FIG. 4
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1030, p. 3 of 16
`
`

`
`US. Patent
`
`Jan. 19, 1993
`
`Sheet 3 of 8
`
`5,181,017
`
`5°‘ \ NETWORK SEARCHED
`
`S
`
`FIG. 5
`
`NETWORK SEARCHED
`
`FIG. 5
`
`500
`
`HEADER
`0000 0001
`0000 0001
`0000 0100
`0000 0010
`0000 0100
`0000 0000
`
`600
`
`HEADER
`0000 0101
`0000 0100
`0000 0001
`0000 0100
`0000 0001
`0000 0000
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1030, p. 4 of 16
`
`

`
`US. Patent
`
`Jan. 19, 1993
`
`Sheet 4 of 8
`
`5,181,017
`
`NETWORK SEARCHED
`
`HEADER
`0000 1101
`0000 0001
`0000 0000
`
`700
`
`FIG. 7
`
`NETWORK SEARCHED
`
`HEADER
`0000 1111
`800 0000 0001
`0000 0000
`
`FIG. 8
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1030, p. 5 of 16
`
`

`
`US. Patent
`
`Jan. 19, 1993
`
`Sheet 5 of 8
`
`5,181,017
`
`IDLE STATE
`
`900
`
`INCOMING .
`BYTE AVAILAB
`?
`
`YES ACTIVE STATE
`
`910
`usE BYTE
`AS A SELECTION /
`
`MASK
`
`.
`
`INCOMING
`BYTE AVAILABL
`"
`
`YES.
`
`50
`SEND BYTE / 9
`THROUGH
`
`FIG. 9
`
`1
`
`/ 960
`SEND our A
`LINK-CLOSE
`COMMAND
`
`IDLE STATE
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1030, p. 6 of 16
`
`

`
`US. Patent
`
`Jan. 19, 1993
`
`Sheet 6 of 8
`
`5,181,017
`
`IDLE STATE
`
`11111011 MODULE ’ 8°10
`ARE WE?
`
`I
`11+ /0020
`BmMsE
`AND BYTE
`WITH
`1110
`
`w
`w- [8030
`B|Tw1sE
`AND BYTE
`WITH
`1101
`
`10050
`I
`x-
`x+ [0040
`BITWISE
`BITWISE
`AND BYTE
`AND BYTE
`WITH
`WITH
`1011
`0111
`
`8055
`l
`EXTRACTOR/
`B1Tw1sE
`AND BYTE
`WITH
`0000
`
`I
`sToRE /8060
`RESULT IN
`WORK REG.
`
`DISCARD
`‘MASK BYTE’
`
`{.0090
`
`DISCARD
`'MASK BYTE’
`
`l AOT1vE sTATE
`
`l SEARCHING sTATE
`
`FIG. 10
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1030, p. 7 of 16
`
`

`
`US. Patent
`
`Jan. 19, 1993
`
`Sheet 7 of 8
`
`5,181,017
`
`SEARCHING STATE
`
`A LINK-CLOSE
`COMMAND‘?
`
`r9190
`CLOSE THE
`PATH THROUGH
`THE CROSSBAR
`
`A
`
`9110
`
`'
`IDLE
`STATE
`
`BITWISE OR THE BYTE RECEIVED FROM THE / 912°
`CROSSBAR AND THE WORK REGISTER
`
`H
`
`N0 / 9140
`SEND THE RESULT OUT THE UNK
`
`ammsE AND THE BYTE wTTH WORK REGISTER / -
`
`1
`STORE THE RESULT IN THE WORK REGISTER
`
`DELAYED STATE
`
`IS WORK
`0000?
`
`FIG. 11
`
`DISCARD THE BYTE ‘
`
`ACTIVE STATE
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1030, p. 8 of 16
`
`

`
`US. Patent
`
`Jan. 19, 1993
`
`Sheet 8 of s
`
`v5,181,017
`
`f T270
`CLOSE THE
`PATH THROUGH
`SMTCH
`
`INCOMING BYTE
`VAILABLE?
`
`1220
`/.
`--- SEND THE BYTE OUT
`
`YES
`
`IDLE STATE
`
`
`
`THE LINK TO THE NEXT NODE DELAYED STATE
`
`II
`
`/-‘I28O
`' CLOSE THE
`PATH THROUGH
`SWITCH
`
`1240
`
`INCOMING BYTE
`AVAILABLE?
`
`'
`
`YES [1250 IDLE STATE
`SEND THE WORK REG. OUT
`THE LINK TO THE NEXT NODE
`I
`f- 1260
`STORE THE BYTE RECEIVED
`IN THE WORK REG.
`
`I
`
`DISCARD THE BYTE
`
`K- 1290
`
`FIG. I3
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1030, p. 9 of 16
`
`

`
`1
`
`ADAPTIVE ROUTING IN A PARALLEL
`COMPUTING SYSTEM
`
`5
`
`30
`
`FIELD OF THE INVENTION
`This invention generally relates to improvements in
`data processing applications in a parallel computing
`system and, more particularly, an effective method for
`routing data between parallel computing elements
`through an interconnected network with multiple inter
`connecting paths (e.g. a multi-dimensional torus net
`work).
`DESCRIPTION 'OF THE RELATED ART
`This invention addresses the problem of low-latency
`message processing found in today’s parallel computers.
`Such a computer system consists of a large number of
`“nodes” interconnected via a high speed communica
`tion network. Each node generally consists of a proces
`sor and memory The nodes operate independently and
`interact with each other by sending messages and
`blocks of data via the communication network.
`The communication network interconnects the
`nodes, but because the number of nodes is potentially
`very large (e.g. thousands), it is impractical for each
`node to have a dedicated link to every other node in the
`system. Therefore, some regular topology of intercon
`necting links is usually employed, with each node hav
`ing direct links to only a few neighbors. In such a net
`work, in order to send information between nodes
`which are not directly connected a path must be found
`using intermediate nodes and the bridging links they
`provide.
`Given such an environment, when one node needs to
`send a message to a non-adjacent node, there must be a
`mechanism for determining the intermediate links and
`nodes to use and for forwarding the message along
`those intermediate links with minimum delay. In a regu
`lar network, there may be many possible routes between
`two given nodes. The message delivery mechanism is
`able to select one route from the many possible, avoid
`ing intermediate links and nodes which are busy or
`broken. Also, the message delivery mechanism is able to
`operate independently of the processor in each interme
`diate node.
`In general, this invention’s network topology is appli
`cable to networking schemes having multiple nodes,
`with each node sharing communication links with its
`neighbors on all sides. An example of this type of a
`topological scheme is the multi-dimensional torus net
`work.
`FIG. 1 illustrates the topology of a two-dimensional
`torus. Each box 10 represents a node and each line 20
`represents a communication link. In FIG. 1, twenty
`nodes are interconnected in a ?ve node by four node
`torus. A three-dimensional torus would have a plurality
`of two-dimensional networks logically stacked in the
`third dimension. Each node has two additional links,
`one to the counterpart in the two-dimensional torus
`above and one to the counterpart in the torus below.
`Larger dimensional torus networks are also possible.
`Descriptions of parallel computing systems are found
`I in US Pat. Nos. 4,636,948, assigned to IBM; 4,514,807
`to Tatsuo; 4,814,980 and 4,730,322 to California Insti
`tute of Technology; 4,811,214 to 4,543,630 to Teradata;
`4,748,660 to Jeumont-Schneider; and 4,598,400 to
`Thinking Machines Corp. These patents describe vari
`ous architectures for parallel processing that represent
`
`5,181,017
`2
`earlier development of routing systems similar to the
`subject invention.
`The subject invention is designed to address the fol
`lowing requirements, heretofore never possible in a
`parallel processing environment. A key requirement is
`the ability to dynamically find the shortest available
`path and send a message over that path from any node
`to any other node in a multi-dimensional network, even
`if they are not directly connected. This capability is
`combined with a total transmission time which is only a
`fraction slower than the raw communication link speed.
`The communication link also requires the ability to
`dynamically adapt to changing network conditions
`including congestion and inoperative links, using alter
`nate routes when required. Routing is accomplished
`without intermediate nodal buffering. This reduces
`costs and eliminates sequential searching when network
`resource blocking is encountered. Finally, any network
`resource must have the ability to be freed if the progress
`of the message is temporarily blocked.
`Examples of prior art systems that failed to meet the
`requirements described above are found in routing
`chip", Distributed Computing, Springer-Verlag, New
`York, 1986; and Chow et al., “Hyperswitch Network
`For the Hypercube Computer”; Computer Architecture
`News, Vol. 16, No. 2 May 1988.
`The Torus article describes a parallel computing
`network routing chip that is speci?cally designed to
`provide low-latency routing in a multi-dimensional
`torus network. The chip pre-establishes an order in
`which the messages are routed through intermediate
`nodes to reach their destination. A technique known as
`“cut through” routing is employed. This technique
`forwards each byte as soon as it is received at an inter
`mediate node. Thus, total transmission time approaches
`raw link speed and no buffering is required at the inter
`mediate nodes. A more detailed description of “cut
`through” routing is contained in “A Framework for
`Adaptive Routing in Multicomputer Networks", ACM
`Symposium on Parallel' Algorithms and Architecture,
`1989.
`The problem with the Torus chip and, more speci?
`cally, ucut through” routing, is that the pre-established
`routes are static, based only on the relative positions of
`the source and destination nodes. If any link in the route
`is broken, the message cannot be routed through the
`network, even if an alternate route could have been
`used. Also, if there is a contention for some of the links
`in the network, the forward progress of one or more
`messages is temporarily blocked. This could, in turn,
`block the forward progress of one or more messages.
`The blockage of these messages in turn impacts other
`messages since blocked messages do not free the paths
`they are using. Thus, there is no ability to free network
`resources if the progress of a message is temporarily
`blocked.
`The Hyperswitch reference is used to route messages
`in a hypercube computer. The hypercube is a special
`case of the multi-dimensional torus wherein the number
`of nodes in each dimension always equals two. The
`hyperswitch network performs adaptive routing. Thus,
`before sending a message, a search of all possible paths
`is performed to identify routes which avoid congestion
`and broken links. This gives the hyperswitch routing
`the ability to dynamically adapt to changing network
`conditions and inoperative links. The routing also re
`quires no buffering and has the added capability of
`
`45
`
`60
`
`65
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1030, p. 10 of 16
`
`

`
`SUMMARY OF THE INVENTION
`According to the invention, these objects are accom
`plished by employing identical routing mechanisms
`located in every node of the system to efficiently route
`information from node to node. Each routing mecha
`nism contains a transmitter/receiver pair coupled via a
`conventional crossbar (space) switch. Incorporated
`within each transmitter/receiver pair are bi-directional
`communication links with other adjacent nodes. Each
`transmitter/receiver pair contains dedicated links to the
`resident node’s processor and memory.
`Information is relayed from node to node using a
`header consisting of route descriptor bits. Each node’s
`receiver/transmitter pair changes states as the informa
`tion is guided to the destination node. The message is
`propagated over several nodes simultaneously to tra
`verse the nodes and reach the destination node quickly.
`When the ?nal nodal connection is accomplished, all
`subsequent communication links are freed via a com
`mand passed back over the network.
`-
`The invention has the capability of sending messages
`from any one node to any other node in a multi-dimen
`sional network, even if they are not directly connected,
`The routing occurs at a total transmission time which
`approaches the point-to-point link speed.
`The routing is architected to dynamically adapt to
`changing network conditions including congestion and
`inoperative links using an alternative route when re
`quired and no buffering of messages is employed. The
`architecture is ?exible enough to detect blocked mes
`sages and dynamically release network resources to
`alleviate constraints in the network.
`
`35
`
`5,181,017
`4
`FIG. 8 is an illustration of another sample network
`search in accordance with the present invention;
`FIG. 9 is a flow chart illustrating the state changes
`for the receiver and injector modules in accordance
`with the present invention;
`FIG. 10 is a ?ow chart illustrating the idle state for
`the transmitter and extractor modules in accordance
`with the present invention;
`FIG. 11 is a ?ow chart illustrating the searching state
`for the transmitter and extractor modules in accordance
`with the present invention;
`FIG. 12 is a flow chart illustrating the ‘active state
`processing for the transmitter and extractor modules in
`accordance with the present invention; and
`FIG. 13 is a ?owchart illustrating the delayed state
`for the transmitter and extractor modules in accordance
`with the present invention.
`DETAILED DESCRIPTION OF THE
`INVENTION
`This invention utilizes multiple, identical routing
`mechanisms which are associated, one for one, with
`every node in the system. Referring to FIG. 2, the com
`munication links between the nodes 10, 11, 12 and 13
`connect directly with the routing mechanisms 200, 210,
`220 and 230.
`The communication links could be local area net
`works or any of a variety of other standard mediums of
`communication commonly employed today for commu
`nicating between nodes. The routing mechanism, pro
`cessor and memory can be selected from any of a vari
`ety of commonly used processors and memory, such as
`the 80386 processor and compatible memory.
`Each routing mechanism provides, in turn, a link to
`the corresponding node’s processor or memory 100,
`110, 120 and 130. Node 10 has each of its communica
`tion links 21, 22, 23 and 24 separately labeled to corre
`late with the detailed description of FIG. 3.
`The number of links supported by the routing mecha
`nism is variable and depends on the dimensionality of
`the network. To simplify the explanation of the inven
`tion, assume a two-dimensional network similar to the
`one shown in FIG. 1. In FIG. 1, each node 10 is con
`nected to its four adjoining nodes via a communication
`link 20. A later discussion explains the additions neces
`sary to support additional dimensions.
`FIG. 3 shows the internal architecture of the routing
`mechanism for a two-dimensional torus. For a two-di
`mensional torus, each routing mechanism supports four
`bi-directional links incoming links 300 and outgoing
`links 320 to other routing mechanisms (in other nodes)
`and one special incoming link 310 and outgoing link 330
`to the processor or memory of its'own node. Since the
`links are bi-directional, ?ve receivers 301, 302, 303, 304,
`310 and ?ve transmitters 321, 322, 323, 324, 330 are
`required. A crossbar switch 350 is shown as an example
`of the hardware used to switch the information between
`the various links. Other embodiments of the invention
`could substitute a space switch for the crossbar switch.
`Each link is appropriately labeled according to the
`direction the link sends data. Thus, the receiver for W+
`301 and the transmitter for W+ 321 correspond to
`communication link 21 in FIG. 2, the receiver for W
`302 and the transmitter for W- 322 correspond to
`communication link 22, the receiver for X+ 303 and the
`transmitter for X+ 323 correspond to communication
`link 23, the receiver for X- 304 and the transmitter for
`X- 324 correspond to communication link 24. The
`
`65
`
`3
`freeing up network resources if blockages are detected
`in the initial investigation of the network.
`As mentioned above, the capability described in the
`hyperswitch article is of use only with a hypercube
`computer. This is extremely limiting given today’s mul
`ti-dimensional network implementations. Further, the
`hyperswitch’s sequential preliminary search is undesir
`able overhead.
`The subject invention has none of the aforementioned
`problems or limitations.
`
`10
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`The foregoing and other objects, aspects and advan
`tages of the invention will be better understood from
`the following detailed description of the preferred em
`bodiment of the invention with reference to the accom
`panying drawings, in which:
`FIG. 1 shows the network topology of a conven
`tional two-dimensional torus network in accordance
`with the present invention;
`FIG. 2 is an illustration of the relationship between
`routing mechanisms and nodes in accordance with the
`present invention;
`FIG. 3 is an illustration of the internal structure of the
`routing mechanism in accordance with the present in
`vcntion;
`FIG. 4 is an illustration of a sample network in accor
`dance with the present invention;
`FIG. 5 is an illustration of a sample network search in
`with the present invention;
`FIG. 6 is an illustration of another sample network
`search in accordance with the present invention;
`FIG. 7 is an illustration of another sample network
`search in accordance with the present invention;
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1030, p. 11 of 16
`
`

`
`5
`“injector" 310 is a special receiver which receives data
`from the node’s processor or memory rather than from
`another node. The “extractor" 330 is a special transmit
`ter which sends data to the node's processor or memory
`rather than to another node.
`The crossbar switch 350 provides one-to-many
`switching from the link receivers 301-310 the link trans
`mitters 321-330. To make connections, each receiver
`301-310 presents a selection mask to the crossbar switch
`350 indicative of the transmitter 321-330 it wants to
`transmit through. Connections are made by the crossbar
`switch 350 only if the particular transmitter is available.
`After a path is opened, a transmitter requests the cross
`bar switch to free the communication link that was
`previously connected.
`
`20
`
`30
`
`5,181,017
`6
`through the crossbar switch 350. The possible values
`and their associated function blocks are shown below.
`1110 for the W+ transmitter (8020)
`1101 for the W— transmitter (8030)
`1011 for the X+ transmitter (8040)
`0111 for the X- transmitter (8050)
`0000 for the extractor (8055)
`Then, in function block 8060, the result is stored in a
`register called WORK. Once stored in the WORK
`register, decision block 8070 determines if the value is
`non-zero. If the value is non-zero, processing continues
`with function block 8090 where the “mask byte” is
`discarded. After discarding the “mask byte”, the trans
`mitter enters the SEARCHING state. If the value is
`zero, the process continues by discarding the “mask
`byte" and entering the ACTIVE state as the extractor.
`In the SEARCHING state, the transmitter modi?es
`each subsequent byte it receives and sends the result out
`its link. A ?ow diagram is shown in FIG. 11 which
`outlines the SEARCHING state logic used by the trans
`mitter and extractor.
`In decision block 9100, a test is made to determine
`whether the received byte is a LINK-CLOSE com
`mand.
`If the received byte is a LINK-CLOSE command the
`processing continues in function block 9190 where the
`path through the crossbar switch is closed and the state
`becomes IDLE.
`If the received byte is not the LINK-CLOSE com
`mand, decision block_9110 determines if an additional
`byte is available from the crossbar switch. If not, the
`processing reverts back to function block 9100, else, a
`bitwise-OR is performed on the WORK register and the
`received byte. This takes place within function block
`9120.
`Then, in decision block 9130, the operation’s results
`are compared to 0000, 0011, 1100, and 1111. If decision
`block 9130’s test fail (i.e. no matches), the process con
`tinues in function block 9140 where the operation’s
`result is sent to the next node. If a match is detected,
`function block 9150 performs a bitwise-AND on the
`received byte and the WORK register. The result be
`comes the WORK register’s new value as shown in
`function block 9160.
`In decision block 9170, the received byte is compared
`to 0000. If the received byte equals 0000, the transmitter
`enters the DELAYED state. If not, the WORK regis
`ter’s new contents are compared with 0000 in decision
`block 9180. If the contents equal 0000 the transmitter
`discards the received byte in function block 9200 and
`enters the ACTIVE state. If not, the process repeats by
`continuing in block 9100.
`In the ACTIVE and DELAYED states, every byte
`received is sent out the transmitter’s link without modi
`?cation. If the information is destined for the extractor,
`this means that the byte is made directly available to the
`node’s processor or memory. The difference between
`these two states is that in the DELAYED state, an extra
`byte needs to be sent out so incoming bytes are delayed
`one cycle in the WORK register.
`The ?owchart in FIG. 12 outlines the ACTIVE state
`for the transmitter and extractor modules. Within the
`ACTIVE state, function block 1200 determines if the
`received byte is a LINK-CLOSE command. If the re
`ceived byte is a LINK-CLOSE command, the process '
`continues in function block 1270 by closing the crossbar
`switch’s path to this module. If the received byte is not
`a LINK CLOSE command, decision block 1210 deter
`
`40
`
`Selection Masks
`The selection mask comprises a four bit command
`word that is presented to the crossbar switch by each
`receiver. If the selection mask is all zeros, the crossbar
`switch initiates a path from that receiver to the extrac
`tor. If the selection mask is non-zero, each bit is used to
`indicate whether a path should be opened to the corre
`sponding transmitter. For example, a selection mask of
`0001 tells the crossbar switch 350 to attempt to open a
`path from the receiver that presented the mask, say
`receiver 301, to the W+ transmitter 321. A selection
`mask of 1010 requests two paths, one from the receiver
`301 to the W- transmitter 322, and one from the re
`ceiver 301 to the X- 324 transmitter. When more than
`one path is opened through the crossbar switch 350,
`every byte generated by the receiver is sent to all con
`nected transmitters.
`Referring to FIG. 9, a flow chart is shown illustrating
`the state changes of the receiver and injector modules.
`Each receiver has two primary states—IDLE and AC
`TIVE. When IDLE, the ?rst byte received over a link
`marks the beginning of a message and causes that re
`ceiver to enter the ACTIVE state. Decision block 900
`tests for a byte from the link or memory. If a byte is
`detected, the receiver enters the ACTIVE state. If not,
`the receiver returns to the IDLE State. In function
`block 910, the receiver uses the least signi?cant nibble
`(four bits) of the “?rst received" byte as a selection
`mask (see above) for the crossbar switch. The selection
`mask, when presented to the crossbar switch, represents
`a set of desired paths to one or more transmitters.
`Decision block 920 tests for busy or inoperable trans
`mitters. If no transmitters are available, processing con
`tinues in function block 960 where a LINK-CLOSE
`50
`command is sent backwards over the link. If at least one
`path through the crossbar switch is available, decision
`block 940 tests for an additional byte of data. If data
`exists, it is sent through the crossbar switch as shown in
`function block 950. If an additional byte does not exist,
`control is transferred to function block 960.
`Referring to FIG. 10, each transmitter has four
`states-JDLE, SEARCHING, ACTIVE, and DE
`LAYED. A transmitter starts in the IDLE state and
`remains in that state as long as it is not connected to any
`receivers via the crossbar switch as depicted in decision
`block 8000. In this state, it neither receives or transmits
`data. When the crossbar switch 350 connects a transmit
`ter to a receiver, the ?rst byte received by the transitter
`is the “selection mask” byte.
`Function block 8010 performs a bitwise-AND with
`the “selection mask" as one operand and an identity
`based bit mask as the other. This operation selects a path
`
`45
`
`55
`
`60
`
`65
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1030, p. 12 of 16
`
`

`
`5,181,017
`8
`KNOWLEDGE command backwards to the source
`node without taking any action. At the source node, the
`ACKNOWLEDGE command is used to indicate that a
`message was received successfully.
`To transmit a message, the source node generates a
`data stream consisting of the following sections (listed
`in order of transmission). The data should be presented
`to the injector of the routing mechanism of the source
`node at the same speed as each link in the network.
`1. A routing header (zero or more bytes)
`2. A zero byte (to end the header)
`3. The message to be sent (zero or more bytes)
`4. The CRC of the message (not including the header)
`5. An END-OF-MESSAGE command
`If the message is received correctly, the source node
`should receive an ACKNOWLEDGE command from
`its injector followed by a LINK-CLOSE command. If
`the LINK-CLOSE command is seen without an AC
`KNOWLEDGE command, the source node knows
`that the message was not received and should be resent.
`When a message arrives at its destination node, the
`bytes sent appears, in the order sent, from the extractor
`of the destination node’s routing mechanism at the same
`speed as the links in the network. The header (including
`the zero byte which marks its end) does not appear at
`the destination, only the message, CRC and END-OF
`MESSAGE command exits the extractor.
`The checking of the CRC and generation of the
`END-OF-MESSAGE, ACKNOWLEDGE and
`LINK-CLOSE commands is handled by hardware be
`tween the routing mechanism and the node’s processor
`or memory. The delay between END-OF-MESSAGE
`and ACKNOWLEDGE or LINK-CLOSE should be
`as short as possible since the routing mechanism holds a
`path back to the source node open until the ?nal LINK
`CLOSE is seen.
`
`20
`
`25
`
`7
`mines if an additional byte exists. If not, the process
`continues in decision block 1200, else, function block
`1220 sends the latest byte to the next node.
`The ?owchart in FIG. 13 illustrates the DELAYED
`state processing. Processing commences with a test in
`decision block 1230 to determine if the received byte is
`a LINK-CLOSE command. If the received byte is a
`LINK-CLOSE command, the process continues in
`function block 1280 by closing the crossbar switch’s
`path to this module. If the received byte is not a LINK
`CLOSE command, decision block 1240 determines if an
`additional byte exists. If not, the process returns to
`function block 1230, else, function block 1250 sends the
`contents of the WORK register to the next node. Func
`tion block 1260 then stores the received byte in the
`WORK register. Finally, as shown in function block
`1290, the received byte is discarded.
`If, while in either the SEARCHING, ACTIVE or
`DELAYED states, the receiver to whom the transmit
`ter is sending data (ie. the one on the other side of the
`link) sends back a LINK-CLOSE command, the trans
`mitter ends its participation in the transfer of that mes
`sage, tells the crossbar switch to disconnect it from the
`receiver currently sending it data, and returns to the
`IDLE state. When all transmitters connected to a re
`ceiver return to the IDLE state, that receiver is in
`formed that it is no longer connected to any transmitters
`and returns to the IDLE state. If a link is inoperative,
`the transmitter driving that link never leaves the IDLE
`state. If a byte is received through the crossbar switch
`for an inoperative link, the transmitter immediately
`instructs the crossbar switch to drop the connection as
`if it had received a LINK-CLOSE command. Finally, if
`a link becomes inoperative in the middle of a transmis
`sion, the transmitter immediately breaks the connection
`in the same manner.
`In addition to data, a few commands can be sent
`backward and forward over each link and through the
`crossbar switch. These commands are implemented as
`separate control wires or as special inband escape char
`acters in the data. The implementation varies with the
`link design.
`The LINK-CLOSE command is sent backwards
`over a link (in the direction opposite data flow) from a
`receiver in one node to a transmitter in another node.
`As described earlier, LINK-CLOSE causes the trans
`mitter to return to the IDLE state and close its connec
`tion through the crossbar switch. If there is only one
`open path through the crossbar switch, it also causes
`another LINK-CLOSE command to be sent, this time
`over a link one hop closer to the source node.
`The END-OF-MESSAGE command is sent forward
`over links and through the crossbar switches from the
`source node to the destination node. The intermediate
`receivers and transmitters send the END-OF-MES
`SAGE command through the system as if it was a data
`byte. When the destination node receives the END-OF
`MESSAGE command, it checks the message’s cyclic
`redundancy check (CRC). If the CRC is correct, it
`sends back an ACKNOWLEDGE command followed
`by a LINK-CLOSE command. If the CRC is wrong,
`only a LINK-CLOSE command is sent.
`The ACKNOWLEDGE command is sent back
`wards over each link from receiver to transmitter and
`backwards through each crossbar switch from transmit
`ter to receiver. It is generated by the destination node
`only after successful reception of the message. Each
`intermediate routing mechanism sends the AC
`
`BASIC HEADER
`The header, which is generated by the source node
`and sent at the beginning of the message, speci?es what
`path or paths the message should take. In a two-dimen
`sional torus, only the least signi?cant nibble of each
`header byte is used. Each byte of the header has the
`following interpretation. (Bit 0 is the least signi?cant.)
`bit 0 Set to 1 to move one link in the W+ direction
`bit 1 Set to 1 to move one link in the W- direction
`bit 2 Set to 1 to move one link in the X+ direction
`bit 3 Set to 1 to move one link in the X- direction
`bits 4-7 Set 0 in a two-dimensional network
`To build the simplest type of header, the source node
`determines the relative distance between it and the des
`tination node in each direction. The length