Ulllted States Patent [19]
`Garmire et al.
`
`US006122277A
`[11] Patent Number:
`[45] Date of Patent:
`
`6,122,277
`Sep. 19, 2000
`
`[54] PARALLEL COMPUTER NETWORK
`BROADCASTING AND
`ACKNOWLEDGEMENT
`
`5,245,609
`5,379,295
`5,404,565
`5,410,300
`
`9/1993 Ofek et al. ............................ .. 370/235
`1/1995 Yonehara
`.. 370/400
`4/1995 Gould et al. .
`709/237
`4/1995 Gould et al. ..................... .. 340/82579
`
`
`
`Inventors: Derrick Garmire; Donald GI Grice, both of Kingston NY_ Tim Zhang
`
`
`
`McAuley .............................. .. 5,478,662 12/1995 Strasser ..... ..
`
`429/13
`
`,
`SPnng> TeX-
`
`’
`
`' "
`
`’
`
`5,673,252
`5,764,895
`
`9/1997 Johnson et al
`6/1998 Chung ....... ..
`
`370/449
`709/250
`
`_
`_
`_
`_
`[73] Asslgneei Internatlollal Busllless Machllles
`Corporation, Armonk, NY.
`
`[21] Appl. No.: 08/920,348
`.
`_
`Filed.
`
`Aug. 19, 1997
`
`[22]
`
`.
`
`7
`
`Int. Cl. ........................... .. H04L 12/28, H04L 12/56
`[51]
`[52] US. Cl. ........................................... .. 370/390; 709/223
`[58] Field of Search ................................... .. 370/235, 389,
`370/223, 390, 400, 401, 402, 403, 404,
`474, 406, 328, 449; 709/223, 250; 345/502;
`714/748
`
`[56]
`
`References Cited
`
`US‘ PATENT DOCUMENTS
`4,707,827 11/1987 Bione et al. .......................... .. 370/405
`4,908,828
`3/1990 Tikalsky
`714/822
`370/400
`5,056,085 10/1991 V11 --------------- -
`5JOSSJO91
`2/1992 Schroeder et a1
`370/406
`571097384
`4/1992 Tsf’eng """" "
`714/748
`5,117,420
`5/1992 HllllS et al.
`370/400
`5,181,017
`1/1993 Frey, Jr. et al. .... ..
`709/239
`5,216,675
`6/1993 Melliar-Smith et al.
`714/748
`5,241,625
`8/1993 Epard et al. .......................... .. 345/502
`
`5,857,075
`6,049,533
`
`1/1999 Chung
`.. 709/223
`4/2000 Norman et al. ....................... .. 370/328
`
`Primary Examiner—Hassan KiZou
`Assistant Examiner—John PeZZlo
`Attorney, Agent, or Firm—Floyd A. Gonzalez, Esq.; Heslin
`& Rothenberg, RC‘
`
`[57]
`
`ABSTRACT
`
`Received portion of message is stored persistently and
`transmitted without awaiting receipt of another portion of
`the message and without generating a new message. The
`storing and transmitting can occur substantially simulta
`neously and be performed by one or more hardware ele
`ments. Originator of the message can choose whether to
`indicate indication of broadcasting of the message. First
`hardware element can determine local acknowledgement for
`message and second hardware element can determine deter
`minative signal of the local acknowledgement and at least
`one of: one or more collected intended recipient acknowl
`edgements for the message; and one or more collected
`determinative signals of intended recipient acknowledge
`ments for the messa 6
`g '
`
`13 Claims, 5 Drawing Sheets
`
`100
`
`101A'-\~
`
`NUDE
`
`12OA'-\_
`
`114A
`
`102A'_-— ROUTING MECHANISM
`
`116A\
`
`116B\_-
`
`1
`l
`l
`102B—~ 1201mm; MECHANISM
`
`114B——>
`
`120B
`
`101B~~
`
`NUDE
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1029, p. 1 of 14
`
`

`
`U.S. Patent
`
`Sep. 19,2000
`
`Sheet 1 015
`
`6,122,277
`
`NODE
`
`108
`)
`
`106
`
`H,”
`FIG. 1A
`F _________________________ __/____
`H
`a
`|
`|
`:
`l
`l
`:
`I
`f
`:
`:
`MEMORY
`i
`|
`:
`g
`EUNTRULLER
`
`i i
`
`‘ l
`4-114 I
`
`179
`
`104
`
`PROCESSOR
`
`120»
`
`L ____________________ __ ____ _____ __|
`
`/
`
`100
`
`TING
`1528M
`\
`
`i
`
`nnossm swncu
`
`110
`/ / _/112
`
`commune
`‘
`f
`?
`Q
`i
`
`i
`
`1
`
`<-——116
`
`1
`
`+
`
`MESSAGE
`
`12\2\
`
`124
`
`‘
`HEADER
`
`1126
`
`ENDI-DF-
`R TE
`AL
`
`128
`
`‘
`um
`
`130
`
`132
`
`‘
`cum
`VALUE
`
`END'-0F
`ES AGE
`AL
`
`FIG. 2
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1029, p. 2 of 14
`
`

`
`6,122,277
`100
`
`/
`
`114A
`
`U.S. Patent
`
`Sep. 19, 2000
`
`Sheet 2 0f 5
`
`101A-\ _
`
`NUDE
`
`102A—_ —
`
`ROUTING MECHANISM
`
`116A‘
`
`N
`
`l
`116B\__.
`
`k
`
`I
`
`l
`
`k
`
`102B—~ noumm MECHANISM
`
`114B—-»
`
`120B
`
`1 01B‘ —-
`
`NUDE
`
`FIG. 1B
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1029, p. 3 of 14
`
`

`
`U.S. Patent
`
`Sep. 19, 2000
`
`Sheet 3 0f 5
`
`6,122,277
`
`@
`I
`
`300‘
`
`CONTROLLER I12 RECEIVES HEADER 124 AND ALLOCATES ONE
`OR MORE COMMUNICATION LINKS I16
`
`I
`
`301
`
`IS END-OF-ROUTE
`SICNAL T26 AN END OF BROADCAST CHARACTER
`
`II
`
`302
`
`CONTROLLER IIZ ALLOCATES
`~ ONEMEMORY LINKTI4
`
`I
`PORTION OF DATA 128 IS TRANSMITTED OVER
`ANY AND ALL OF THE LINKS T14, T16 THAT _
`HAVE BEEN ALLOCATED ABOVE
`
`END-OF-MESSAOE SIGNAL I32
`
`306
`
`Y!
`EMPLOY CHECK VALUE 130 TO EVALUATE
`CORRECTNESS OF RECEIVED DATA I28
`
`--- 308
`
`@
`
`FIG. 3
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1029, p. 4 of 14
`
`

`
`U.S. Patent
`
`Sep. 19, 2000
`
`Sheet 4 0f5
`
`6,122,277
`
`@
`
`400—--
`
`CONTROLLER IOO KNOWS MESSAGE I22 HAS BEEN
`OORRECTLY RECEIVED INTO MEMORY 106
`
`I V
`IS
`END 0r ROUTE
`30000122 AN END-OF-BROADBASI
`
`_
`
`_
`
`402
`
`406
`
`N
`
`)
`CUNTROLLER ‘"8 RETURNS
`000K0P 00000000
`
`\
`
`Y i
`Y
`000020050 100 RETURNS
`404*“ 050000-0000 00000000
`
`"
`
`FIG. 4
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1029, p. 5 of 14
`
`

`
`U.S. Patent
`
`Sep. 19,2000
`
`Sheet 5 0f5
`
`6,122,277
`
`@ T
`
`CONTROLLER H2 KNUWS MESSAGE T22 HAS BEEN
`CCRRECTLY RECEIVED INTO MEMORY TUB
`
`T
`
`502
`
`IS
`END-UF-RCUTE
`SIGNAL T22 AN END-UF-BRUADCAST
`CHARACTER
`
`506
`i
`CDNTRULLER‘TTZ RETURNS
`LUCKUP CHARACTER
`
`N
`
`commune 112 RETURNS
`504*‘ BCLOSEO CHARACTER —"
`
`FIG. 5
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1029, p. 6 of 14
`
`

`
`1
`PARALLEL COMPUTER NETWORK
`BROADCASTING AND
`ACKNOWLEDGEMENT
`
`TECHNICAL FIELD
`This invention relates, in general, to parallel computer
`network communication and, in particular, to broadcasting
`and acknowledgement of a message in a parallel computer
`netWork.
`
`BACKGROUND ART
`
`Aparallel computer netWork often encompasses commu
`nication among a number of nodes. One eXample of a
`parallel computer netWork is a multiple instruction streams,
`multiple data streams (“MIMD”) computer. Each node usu
`ally has a processor coupled to a memory. Typically, the
`nodes operate independently and interact With each other by
`sending and receiving messages or blocks of data.
`Practicability dictates every node cannot have a dedicated
`link to the thousands of other nodes in a large parallel
`computer netWork or system. Rather, the system usually
`interconnects the nodes in a regular topology or structure,
`such as a ring, tree, or multi-dimensional mesh or torus.
`Generally, each node has a direct link to only a feW of its
`neighboring nodes. Data communication betWeen nodes
`Without direct links utiliZes intermediate nodes.
`Anode that originates a message can address the message
`to a single recipient or to multiple recipients. Namely, an
`individual-addressee message has a single intended recipi
`ent. Further, When the originating node intends to send
`particular data to a number of other nodes, the originator can
`send a broadcast message, rather than send separate
`individual-addressee messages to each of the nodes.
`Moreover, a broadcast message can be selective (so it has
`speci?c, multiple intended recipients) or be netWork-Wide.
`In one knoWn individual-addressee communication
`design, a routing mechanism associated With each node
`interfaces that node With the computer netWork.
`Furthermore, a routing mechanism (associated With an inter
`mediate node) both receives data from a preceding routing
`mechanism and also transmits the data to another routing
`mechanism in a byte-by-byte fashion. Moreover, an inter
`mediate routing mechanism relays an acknoWledgement
`from a subsequent routing mechanism to a preceding routing
`mechanism Without taking any action. Such a design is
`disclosed in US. Pat. No. 5,181,017 to Frey, Jr. et al.
`(entitled “Adaptive Routing in a Parallel Computing
`System,” issued Jan. 19, 1993, and assigned to International
`Business Machines Corporation), Which is hereby incorpo
`rated herein by reference in its entirety. A shortcoming of
`this design, hoWever, is the inability of any routing mecha
`nism to transmit a portion of, for instance, a broadcast
`message to another node before storing the entire message in
`memory of a local node. A further shortcoming is the
`inability of an intermediate routing mechanism to take any
`action concerning acknoWledgement of a message, for
`instance, during broadcasting.
`During one common type of broadcasting, the originator
`serially sends its broadcast message to its linked set of
`nodes. NeXt, after receiving the entire message, each node of
`the set runs softWare to process and store the broadcast data.
`Then, each of these nodes serially sends out to its linked
`nodes in the netWork a neW message containing the broad
`cast data. Eventually, all the nodes contain a copy of the
`serially processed-stored-forWarded data. A shortcoming of
`this arrangement is the inability of an intermediate node to
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`6,122,277
`
`2
`transmit any of the data to another node before receipt of the
`entire message. A further shortcoming is the inability of the
`intermediate node to communicate received data Without
`generating a neW message. Another shortcoming is the
`inability of the intermediate node to store any portion of the
`data in its local node memory and transmit the portion to
`another node on a portion-by-portion basis.
`In another knoWn con?guration, a routing mechanism (in
`a netWork in Which nodes and routing mechanisms are
`associated one-for-one) collects subsequent intended recipi
`ent acknoWledgement information for an individual
`addressee node message and returns the status to a preceding
`routing mechanism (toWard the originator). Such a design is
`disclosed in US. Pat. No. 5,404,565 to Gould et al. (entitled
`“Message Tracking in a Parallel NetWork Employing a
`Status Word at Each Node Which Re?ects a Message’s
`Progress,” issued Apr. 4, 1995, and assigned to International
`Business Machines Corporation), Which is hereby incorpo
`rated herein by reference in its entirety. A shortcoming of
`this con?guration is the inability of the routing mechanism
`to return to a preceding routing mechanism a status of
`Whether a broadcast message has been received by its local
`associated node in addition to a number of other nodes.
`Another shortcoming is the inability of an intermediate
`routing mechanism to transmit any of the data to another
`routing mechanism before receipt of the entire message. An
`additional shortcoming is the inability of any routing mecha
`nism to substantially simultaneously store in its local node
`and transmit to another routing mechanism a received por
`tion of a broadcast message.
`Thus, a need exists for a capability that provides storing
`of data of a message in memory of a local node and
`transmitting of the data toWard another node before receipt
`of the entire message. An additional need eXists for a
`technique that alloWs transmission of received broadcast
`data toWard another node Without generating a neW mes
`sage. A further need eXists for a capability that provides
`transmission of a portion of a broadcast message to another
`node before storing the entire message in memory of a local
`node. Another need exists for a technique that alloWs inter
`mediate routing mechanism action concerning acknoWl
`edgement of a broadcast message. A still further need eXists
`for a capability that provides return by one routing mecha
`nism to its preceding routing mechanism of a status Whether
`a broadcast message has been received by its local associ
`ated node in addition to a number of other nodes.
`
`SUMMARY OF THE INVENTION
`The shortcomings of the prior art are overcome and
`additional advantages provided through the provision of a
`messaging capability in Which a received portion of a
`message is stored persistently and transmitted Without aWait
`ing receipt of another portion of the message. The storing
`and transmitting of the received portion of the message can
`occur substantially simultaneously. Also, one or more hard
`Ware elements can perform the storing and transmitting.
`Additionally, the storing of the received portion can occur
`in response to an indication of broadcasting of the message.
`An originator of the message can choose Whether to indicate
`the indication of broadcasting. For eXample, the originator
`can insert the indication into the message.
`The persistent storing of the received portion of the
`message can occur in local memory. Further, a routing
`mechanism can perform the transmitting of the received
`portion.
`The transmitting of the received portion can occur on one
`or more paths toWard one or more intended recipients. Also,
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1029, p. 7 of 14
`
`

`
`3
`the transmitting can occur in response to routing information
`for the message.
`In another embodiment of the present invention, a
`received portion of the message is stored and transmitted
`without generating a new message.
`In another aspect of the invention, a ?rst hardware ele
`ment determines a local acknowledgement for a message.
`Also, a second hardware element determines a determinative
`signal of the local acknowledgement and at least one of: one
`or more collected intended recipient acknowledgements for
`the message; and one or more collected determinative sig
`nals of intended recipient acknowledgements for the mes
`sage.
`The determining of the local acknowledgement can occur
`according to whether an indication of broadcasting appears
`for the message. Further, the determining of the determina
`tive signal can occur according to whether the indication
`appears for the message.
`The second hardware element can transmit the determined
`determinative signal on a path toward an originator of the
`message. Moreover, the ?rst hardware element can be a
`controller of local memory. Further, the second hardware
`element can be a controller of a routing mechanism.
`Alternatively, the ?rst hardware element and the second
`hardware element can be the same hardware element.
`In yet another aspect of the present invention, a hardware
`element determines a determinative acknowledgement sig
`nal for a subset of a plurality of intended recipients for a
`message broadcast from an originator. Further, the hardware
`element transmits the determinative acknowledgement sig
`nal on a path toward the originator.
`The present invention advantageously provides a message
`broadcast capability where data of a message can be stored
`in memory of a local node and transmitted toward another
`node before receipt of the entire message. Additionally, the
`technique of the present invention allows transmission of a
`portion of a broadcast message toward another node before
`storage of the entire message in memory of a local node.
`Furthermore, the present invention provides storage in local
`node memory of a portion of a broadcast message and
`transmission of the same toward another node without
`generating a new message. Also, the technique of the present
`invention allows a received portion of a broadcast message
`to be substantially simultaneously stored in the memory of
`the local node and transmitted toward another node.
`Moreover, the present invention provides an acknowledge
`ment determination capability where an intermediate routing
`mechanism can act concerning acknowledgement for a
`broadcast message. Moreover, the technique of the present
`invention allows a given routing mechanism to return a
`status to a preceding routing mechanism whether a broadcast
`message has been received by its local associated node in
`addition to a number of other nodes.
`Additional features and advantages are realiZed through
`the techniques of the present invention. Other embodiments
`and aspects of the invention are described in detail herein
`and are considered a part of the claimed invention.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`The subject matter which is regarded as the invention is
`particularly pointed out and distinctly claimed in the claims
`at the conclusion of the speci?cation. The foregoing and
`other objects, features, and advantages of the invention will
`be apparent from the following detailed description taken in
`conjunction with the accompanying drawings in which:
`FIG. 1A depicts one eXample of a node and its associated
`routing mechanism suited for use in numerous embodiments
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`6,122,277
`
`4
`of, for instance, four-dimensional mesh or torus topologies
`for various computer systems or networks incorporating and
`using the broadcast and acknowledgement capabilities of the
`present invention;
`FIG. 1B depicts one eXample of multiple occurrences of
`the node and its associated routing mechanism of FIG. 1A
`and interconnections between the same, in accordance with
`the principles of the present invention;
`FIG. 2 represents one eXample of a message arranged in
`accordance with an exemplary protocol used by the node
`and its associated routing mechanism of FIG. 1A;
`FIG. 3 depicts one embodiment of the logic used by a
`controller of the routing mechanism of FIG. 1A to achieve
`progression and appropriate propagation of a message, in
`accordance with the principles of the present invention;
`FIG. 4 depicts one embodiment of the logic used by a
`memory controller of a local node to accomplish acknowl
`edgement for a broadcast message to the routing mechanism
`of FIG. 1A, in accordance with the principles of the present
`invention; and
`FIG. 5 depicts one embodiment of the logic used by the
`controller of the routing mechanism of FIG. 1A to accom
`plish acknowledgement for a broadcast message along a
`path toward an originator, in accordance with the principles
`of the present invention.
`
`BEST MODE FOR CARRYING OUT THE
`INVENTION
`In accordance with the principles of the present invention,
`a message broadcast capability is provided in which data of
`a message can be stored in memory of a local node and
`transmitted toward another node before receipt of the entire
`message. Also, a portion of a broadcast message can be
`transmitted toward another node before storing the entire
`message in memory of a local node. Additionally, a portion
`of a broadcast message can be stored in local node memory
`and transmitted toward another node without generating a
`new message. Furthermore, a received portion of a broadcast
`message can be substantially simultaneously stored in the
`memory of the local node and transmitted toward another
`node. Also, an acknowledgement determination capability
`provides action by an intermediate routing mechanism con
`cerning acknowledgement for a broadcast message.
`Moreover, a given routing mechanism can return a status to
`a preceding routing mechanism whether a broadcast mes
`sage has been received by its local associated node in
`addition to a number of other nodes, as described herein.
`One eXample of a node and its associated routing mecha
`nism suited for use in numerous embodiments of a computer
`system or network incorporating and using the broadcast and
`acknowledgement capabilities of the present invention is
`depicted in FIG. 1A and described in detail herein.
`In one embodiment, a computer system 100 includes a
`node 101 coupled to a routing mechanism 102. The node has
`a processor 104 coupled to a memory 106. The memory
`interfaces with the processor and the routing mechanism
`through its memory controller 108. The routing mechanism
`has a crossbar switch 110 coupled to a routing mechanism
`controller 112, which individually interfaces the routing
`mechanism with both the processor and also the memory
`controller.
`In one eXample, each of controllers 108 and 112 is
`implemented using ?nite-state machines, by techniques
`which are well-known in the art. Preferably the controllers
`108 and 112 are hardware elements. For instance, controllers
`108 and 112 could be embodied as the same hardware
`element.
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1029, p. 8 of 14
`
`

`
`6,122,277
`
`5
`Further, routing mechanism 102 can be, for instance, a
`switch chip hardware element. In one preferred
`embodiment, crossbar sWitch 110 of the routing mechanism
`includes a distributed crossbar sWitching array, as disclosed
`in US. Pat. No. 5,410,300 to Gould et al. (entitled “Dis
`tributed Crossbar SWitch Architecture,” issued Apr. 25,
`1995, and assigned to International Business Machines
`Corporation), Which is hereby incorporated herein by refer
`ence in its entirety.
`As depicted in FIG. 1A, one or more bidirectional
`memory links 114 interconnect memory controller 108 and
`routing mechanism 102. In particular, each memory link
`could service a separate message communication request to
`an individual node 101. Further, one or more bidirectional
`communication links 116 interface the routing mechanism
`With the remainder of the computer netWork. These concepts
`are further described in the above-referenced and incorpo
`rated U.S. Pat. No. 5,181,017.
`A bus 118 (e.g., any selected number of Wires) can
`interconnect processor 104 and memory controller 108.
`Additionally, a bus 120 can interconnect the node processor
`and its associated controller 112 of routing mechanism 102.
`Buses 118, 120 are each siZed appropriately for communi
`cation of electrical signal information. As is Well-knoWn in
`the art, an implementation of a given computer system can
`use multiple parts of a given bus as though the parts
`constituted separate buses.
`For multi-dimensional torus topologies, a given netWork
`node 101 is associated With tWo communication links 116
`for each dimension of the torus, as is Well-knoWn in the art
`and further described in the above-referenced and incorpo
`rated U.S. Pat. No. 5,181,017. For exemplary purposes, FIG.
`1A illustrates eight communication links 116 associated With
`the node for use in one preferred embodiment of a four
`dimensional torus topology. of course, one could easily
`employ the node in the interior of a four-dimensional mesh
`topology (Which has just as many connections as any
`arbitrary node in the four-dimensional torus topology).
`Those skilled in the art commonly distinguish mesh and
`torus topologies on the basis of the torus topology having,
`and the mesh topology lacking, Wraparound connections
`betWeen the nodes at its “ends.” Naturally, one could easily
`employ in any position in the netWork a node having an
`overabundance of communication links for that position
`simply by leaving the excess communication links uncon
`nected in the netWork. Furthermore, one can practice the
`present invention With netWork topologies exhibiting sym
`metry or appropriate degrees of asymmetry, as desired.
`FIG. 1B depicts one example of multiple nodes 101A,
`101B coupled to one another by their respective routing
`mechanisms 102A, 102B. In particular, each communication
`link 116A of a given routing mechanism 102A can be
`connected to another communication link 116B of different
`routing mechanism 102B. As Will be comprehended by
`those skilled in the art, the remaining seven links 116A and
`remaining seven links 116B (depicted in FIG. 1B for exem
`plary connectability in four-dimensional mesh or torus
`topologies) are each individually connected to one commu
`nication link on a unique routing mechanism associated With
`a distinct node, in one preferred embodiment.
`Preferably, each communication link (e.g., 116A or 116B)
`includes a “receiver-transmitter” pair. Also, each memory
`link (e.g., 114A or 114B) includes an “injector-extractor”
`pair. The “injector” is a special receiver that receives a
`portion of message 122 from local node 101. In contrast, the
`“receiver” receives a portion of the message from another
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`6
`routing mechanism 102. Furthermore, the “extractor” is a
`special transmitter that sends a portion of the message to the
`local node. Moreover, the “transmitter” sends a portion of
`the message to another routing mechanism.
`Returning to FIG. 1A, crossbar sWitch 110 alloWs one
`to-many connections, in accordance With their availability.
`For instance, the crossbar sWitch permits connections from
`a “receiver” or “injector” to a number of the “transmitters”
`and/or the “extractor.” These concepts are further described
`in the above-referenced and incorporated US. Pat. No.
`5,181,017 and US. Pat. No. 5,410,300.
`FIG. 2 represents an exemplary illustration of a commu
`nication vehicle for one example of a netWork protocol for
`information transfer. The nodes 101 (FIG. 1A) communicate
`among each other in the netWork by sending and receiving
`packets or messages 122. In one embodiment, the message
`includes a header 124, an end-of-route signal 126, data 128,
`a check value 130, and an end-of-message signal 132, each
`of Which is described herein. Typically, header 124 contains
`routing information, as described herein. In one broadcast
`example of the present invention, end-of-route signal 126 is
`a broadcast signal, descriptively named an “end-of
`broadcast” signal because it assumes the position of the
`end-of-route signal at the end of the header. Data 128
`constitute information the originator Wishes to communicate
`to one or more other nodes. Check value 130 can represent,
`for example, a cyclic redundancy check or any other error
`detection and/or correction scheme Well-knoWn to those
`skilled in the art. End-of-message signal 132 indicates the
`conclusion of the message. Further details of many of the
`components of the message (plus implementation of the
`end-of-message signal as a separate control Wire command)
`are described in the above-referenced and incorporated US.
`Pat. No. 5,181,017.
`In one preferred embodiment, components 124, 126, 128,
`130, and 132 of each message 122 are siZed to have easily
`manageable lengths, such as integral numbers of eight bit
`bytes. Furthermore, transmission of the message preferably
`proceeds in byte-siZe portions from the left-hand side to the
`right-hand side of FIG. 2. In one alternative embodiment, the
`transmitted portions could easily be of any desired siZe.
`In one example, each of links 114, 116 (FIG. 1A) include
`an eight Wire bus for parallel communication of succeeding
`eight bit bytes of message 122. Alternatively, the links could
`easily include a bus of integer times eight Width, or multiple
`eight bit byte buses, for parallel transmission of succeeding
`blocks of multiple bytes (e.g., Words) of the message.
`As represented in FIGS. 1A—2, nodes 101 With associated
`routing mechanisms 102 of the present invention can advan
`tageously choose to send a ?ooding broadcast message, a
`selective broadcast message, or an individual-addressee
`message, as described herein. For instance, When processor
`104 of a given originator node 101 Wishes to send message
`122 to multiple connected nodes, it inserts an end-of
`broadcast character in the position of end-of-route signal
`126, in accordance With the present invention. In particular,
`the end-of-broadcast character inserted in the position of
`end-of-route signal 126 directs each routing mechanism 102
`to allocate one memory link 114, as described in the dis
`cussion of FIG. 3 herein.
`In one preferred embodiment of a ?ooding broadcast,
`processor 104 of originator 101 further inserts in header 124
`of message 122 routing information that causes controller
`112 of routing mechanism 102 to attempt allocating all of its
`communication links 116. The details of insertion and use of
`routing information in the header are described in the
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1029, p. 9 of 14
`
`

`
`6,122,277
`
`7
`above-referenced and incorporated US. Pat. No. 5,181,017.
`Thereafter, each received portion of the message can be
`stored in local memory 106 and transmitted toWard the
`routing mechanisms of the other intended recipient nodes, as
`described herein.
`In accordance With the present invention, each routing
`mechanism 102 can persistently store a portion of broadcast
`message 122 in its local node 101 and transmit the same
`toWard other nodes Without aWaiting receipt of another
`portion of the message, as described herein. In one eXample,
`each of multiple desired portions of the message is Written
`to its oWn assigned address space upon receipt. So, a
`previously received portion is not overWritten by a subse
`quently received portion (even though broadcasting of the
`message occurs on a portion-by-portion basis). Upon
`completion of a successful broadcast netWork-Wide, a copy
`of all of the desired portions of the message advantageously
`eXists in memory 106 of each local node. In accordance With
`the present invention, all desired portions of the message
`remain in local memory for use by its local node. In
`particular, the local node has use of a “persistent” copy (e.g.,
`in its local memory) of each and every portion of, for
`instance, data 128 (e.g., after memory controller 108 has
`checked and discarded check value 130). Of course, the
`local node can thereafter do With the stored portions as it
`sees ?t, including delete all those portions from its local
`memory. The key is the local node has at its disposal all of
`the desired portions. “Persistent” storing indicates no
`desired portion of the message is overWritten or otherWise
`deleted from the local memory in order to receive any other
`such portion. That is, no deletion takes place independent
`from the Wishes of the local node.
`Further in accordance With the present invention, each
`routing mechanism 102 can advantageously store informa
`tion from broadcast message 122 in its local node 101 and
`transmit the same toWard other nodes before receiving the
`entire message and Without generating a neW message. For
`eXample, once the broadcast paths are opened, no interme
`diate node assembles a neW header 124 for continued
`storage and propagation of each received portion of the
`broadcast message. Further, no intermediate node accumu
`lates portions of the original broadcast message in order to
`assemble a neW message for continuation of the broadcast.
`Therefore, each node processor 104 need only concern itself
`With its oWn delivered portions of the broadcast message.
`After the originator presents the broadcast message to the
`netWork, the routing mechanisms desirably handle progres
`sion and propagation of the broadcast information Without
`requiring attention from other node processors, as described
`herein. This advantageously yields decreased processor
`resource use cost and increased broadcast message netWork
`transmission speed.
`In another aspect of the present invention, originator 101
`achieves selective broadcasting of message 122 by including
`routing information in header 124 that corresponds to only
`selected destination nodes. The end-of-broadcast character
`inserted in the position of end-of-route signal 126 still
`directs each routing mechanism 102 to allocate one memory
`link 114 in addition to communication links 116 allocated
`according to the routing information in the header.
`In one alternative embodiment of the present invention,
`the end-of-broadcast character easily could direct controller
`112 of routing mechanism 102 to allocate not only the one
`memory link 114 (as above), but also each and every one of
`communication links 116. Namely, the end-of-broadcast
`character in the position of end-of-route signal 126 easily
`could further direct allocation of any and all communication
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`links that had not yet been allocated by any routing infor
`mation that may appear in header 124. In fact, this ?ooding
`broadcast could then omit the header. So, originator 101
`Would not need to insert routing information in the form of
`the header in order to send a ?ooding broadcast message
`because the interpretation of the end-of-broadcast character
`in this implementation Would effect a request for allocation
`of all links 114, 116 on each routing mechanism it encoun
`ters. Then, the end-of-broadcast character could appear at
`the leading edge of message 122, or at least further
`theretoWard, in order to achieve incrementally faster broad
`casting netWork-Wide.
`FIGS. 3—5 represent reaction by each of controllers 108,
`112 to the end-of-broadcast character having been inserted
`for end-of-route signal 126 in order to accomplish a broad
`cast.
`As represented in FIG. 3 for progression of message 122
`along a forWard path (a path in the netWork from originator
`node 101 toWard one or more intended recipient nodes), at
`STEP 300 controller 112 of routing mechanism 102 receives
`message header 124 and consequently attempts to allocate
`one or more communication links 116, as described herein.
`In accordance With