Method and apparatus for arbitrating on an acyclic directed graph

[Technical field to which the invention belongs]<u style="single">Background of the invention</u><u style="single">Related application</u>This application has been assigned to the assignee of this application, and the application under the name "Method and MFP for Unique Address Assignment, Node Self-Identification and Topology Mapping for aDirected Acyclic Graph" filed at the same time as this application. It is related to 07 / 994,402 and the application Serial No. 07 / 994,117 under the name "Method and MFP for Transforming an Arbitrary Acyclic Topology Collection of Nodes into an Acyclic Directed Graph".<u style="single">Field of invention</u>The present invention relates to a computer system. More specifically, the present invention relates to methods and devices for establishing and utilizing communication schemes between a plurality of arbitrarily assembled elements of a computer system.

[0002] [Conventional technique]<u style="single">Background</u>The internal components of a given computer system require the ability to carry signals between them themselves. In a very simple system, it is possible to wire each element of the system directly to all other parts of the system. However, in reality, computer designers developed the concept of communication buses long ago to make computers extensible and to accommodate an unknown number of system components.

[0003] A bus is a communication path, such as a wire or wire, that runs through an entire computer system. Each component of the system only needs to be plugged into a bus that should theoretically be connected to each of the other components in the system. It goes without saying that since there can only be a single communication channel between the components, each component cannot communicate with the other components at the same time. When using a communication bus, each component communicates with other components in an efficient manner without leaving important information from one component in a suspended state while waiting for bus access. It is necessary to establish a shared structure in some way so that the bus can be used. The method by which the components on the bus share the bus is generally called the bus arbitration method.

[0004] In addition to the critical requirement of optimizing the bus arbitration scheme to maximize the flow of important information, the physical nature of the bus itself to minimize system latency while retaining as much flexibility as possible. (And logical / electrical) configurations can and should be optimized.

[0005] In order to communicate with other components associated with a bus, each component must be equipped with hardware such as a transmit / receive circuit that is consistent with the communication conventions implemented for that bus. One such communication standard is described in the IEEE standard document P1394 under the title "High Performance Serial Bus" attached as Appendix A to this document. The standard described on P1394 seeks to perform low cost interconnection between cards on the same backplane, cards on other backplanes, and external peripherals.

[0006] Conventional technology buses or networks have required knowing which and where to plug. For example, many computers have designated ports on the back that correspond to specific peripherals. Some computers implement some buses, such as the Macintosh, which uses a bus called ADB for components such as the mouse and keyboard, and a SCSI bus for other peripherals. is there. These types of buses make up daisy chain elements together, but their connection topologies are limited. Other known buses / networks require that the nodes of the network be arranged as a ring, i.e., in a loop that must be closed in order to operate. Finally, the stellate array, or hub-spoke array, required each node to be linked directly to the central master. Each of the systems of the prior art lacks the desired degree of flexibility.

[0007] [Problems to be Solved by the Invention] It is possible to arbitrarily attach computer elements to one bus, and in doing so, a functional system without requiring an arbitrary topology by the system for a predetermined arrangement of components. It would be desirable to be able to change to, and that is therefore the object of the invention.<u style="single">Outline of the invention</u>An object of the present invention is to provide a fair bus access arbitration scheme for a computer system bus or network in which node connections are changed to non-cycle directed graphs. Another object of the present invention is to provide a preferred bus access arbitration scheme for a computer system bus or network whose node connections have been changed to non-cycle directed graphs. Another object of the present invention is to provide a method of token passing bus arbitration for a computer system bus or network in which node connections are changed to non-cycle directed graphs. Yet another object of the present invention is the initial preemptive bus by any node in the network when an error is detected in the network of nodes modified to a non-cycle directed graph or when the number of nodes is increased or decreased during operation. It is to provide a mechanism that can trigger the configuration.

[Means for Solving the Problems] These and other objectives of the present invention are realized in a system in which any assembly of nodes along the system bus is changed to a non-cycle directed graph. The hierarchical array of nodes specifies one node as the root, while all other nodes establish a parent-child relationship with the nodes they are linked to. Each node may have a plurality of connected child ports that establish a predetermined acknowledgment priority method. Fair bus access arbitration executes bus permissions in a sequence that corresponds to a given port priority, causing all nodes to turn on the bus. The root node may always assert its preferred access state in order to gain bus access, which is useful for responding to the root node requesting isochronous data transfer. Alternatively, a token passing arbitration method may be realized, in which case tokens related to bus access are passed around the nodes according to the predetermined port priority method described above. The preemptive bus initialization may be triggered by either node when an inevitable error is detected or when a connection is added or removed from an existing node.

【0009】<u style="single">Detailed description of the invention</u>A method and an apparatus using a bus having an arbitrary topology will be described. In the following description, a number of specific details such as various computer elements will be described in order to fully understand the present invention. However, it will be obvious to those skilled in the art that the present invention can be practiced without such specific details. In other cases, well-known control structures and coding techniques have not been described in detail in order not to obscure the invention unnecessarily.

[0010] Throughout this detailed description, a number of descriptive terms have been introduced to give the description metaphorical clarity. For example, the expression parent-child relationship between nodes in a given topology is often found. The purpose is to represent the concept of "direction" leading to the graph that is finally derived. As described below, if any topology is transformed into a non-cycle directed graph, one node will be identified as the "root" node. The root node has no parent node, and all nodes that are logically adjacent to the root node are child nodes of that root. The "tree" metaphor is completed by incorporating nodes called "branches" and "leaves".

[0011] Although the bus architecture described herein is described in the context of a single computer-related element, it generally has a broader scope. The present invention is applicable in defining a bus topology to any arbitrarily assembled collection of integrally linked nodes, such as in a network of devices. One thing to keep in mind is that we need to distinguish between nodes and physical computer elements. There is at least one node physical layer controller associated with each element that should reside on the bus. In some situations it may be advantageous to associate a given element with multiple nodes, but usually there is a one-to-one correspondence between the device or element on the bus and the node. ..

[0012] Then, referring to FIG. 1, a block diagram of node 10 is shown. How the node is physically realized is somewhat arbitrary. In a preferred embodiment of the invention, the node is attached as Appendix A, IEEE P1394. <u style="single">High Performance Serial Bus</u>It is designed to comply with communication rules. Node 10 contains arbitration state machine logic 11. This arbitration state logic machine logic incorporates all logic circuits for executing the techniques and algorithms described here. The circuit may consist of a programmable logic array (PLA) or may be uniquely designed to perform the functions described herein. Once the functions to be performed by node logic have been explained, those skilled in the art will be able to realize the present invention without any unnecessary explanation. By its logic, the node implements a minimal arbitration protocol that includes bus initialization, tree identification, self-identification, and bus arbitration features, all of which are described in more detail below.

[0013] The node 10 shown in FIG. 1 further includes transmitter multiplexers 12 and 13, and a data transmitter, receiver, and resynchronizer 14. The node shown in Figure 1 is attached to the local host 15. The local host 15 can be any device that you want to attach to the bus, such as a disk drive, CPU, keyboard or some other component that needs to communicate with other components in the system. Node 10 communicates with other nodes via a communication link. A link is a connection between two ports, which is a cable segment in direct and practical terms, but can usually be realized as some kind of physical communication channel. At a minimum, a link should be able to configure a half-duplex communication channel between the two ports it connects to. A port is an interface between a node and a link. According to the present invention, the port must be capable of sending and receiving data and arbitration signals. A port must also be able to determine if it connects to another port via a link. One way to facilitate this is to apply a bias voltage through the link by the connecting port, which is detectable by the port at the other end of the link. That is, if one port has a link or a bare link that is not connected to the port at the other end, it is determined that the port is not a connection port. In FIG. 1, the illustrated node 10 has three external ports 21, 22 and 23 with connection links 17, 18 and 19, respectively.

[0014] Some implementation rules relating to nodes for implementing the present invention are that a node may have one or more ports. The node should be able to send and receive data on any one of its ports. A node should be able to receive data on only one of the enabled ports at a time and be able to send this data on all remaining enabled ports. A node should be able to send and receive signal messages simultaneously and independently through all of its ports. Separate signal transceivers, encoders and decoders are required for each node port. The minimum implementation node does not require a local host device. For example, such a node may act as a cable extension. From now on, when we ignore the device and the local host and refer to the bus topology, we will always describe it in relation to the bus connection through the node and various ports.

【0015】<u style="single">Graph conversion</u>Figures 2 (a) and 2 (b) show a collection of arbitrarily assembled nodes. Hereinafter, the nodes are simply shown as circles, but each node is considered to include an element equivalent to the element described with reference to FIG. However, note that each node may have more or less than three external ports as shown in the figure. The illustrated line connecting the respective nodes is a way to indicate the link. Ports are not shown, but are implicitly interfaces that connect links and nodes.

The bus arbitration technique described herein requires that any topology be transformed into a non-cycle directed graph. In an arbitrary topology graph, a collection of nodes and links may form one cycle. A cycle is established if you start at a particular node in the graph and return to the same node by going through the link and the node without going through the link twice. Figure 2 (a) shows a non-cycle graph because none of the nodes shown are connected inside the loop. However, FIG. 2 (b) is not a non-cycle graph because the region in the boundary definition box 25 contains an aggregate of nodes 40 to 47 forming a plurality of cycles. Since the bus arbitration technique to be described requires that there are no cycles, this section also describes how to intervene with the user to change the cycles.

[0017] In addition to the requirement that the graph not be non-cycled, the graph must be a directed graph. A directed graph is a graph in which a hierarchical structure is established between adjacent nodes. Initially, a parent-child relationship is not established between the nodes. That is, for example, node 31 may be a "parent node" with respect to node 34, or may be a "child node" with respect to node 34. Therefore, it is necessary to take a given arbitrary topology graph and convert it into a non-cycle directed graph. The method described here is of any given arbitrary topology, regardless of the number of nodes, or how the nodes are physically linked, and regardless of the signal propagation time along the link. Also works to perform this conversion.

【0018】<u style="single">Node communication</u>First, the process of converting a non-cycle arbitrary topology graph into a directed graph will be described. Next, a case where a cycle change is required will be described. FIG. 3 (a) is an arbitrary graph of FIG. 2 (a) such that the node and link have a state label and the signal communicated represents the graph conversion process for directing the graph. Is shown. At this point, it is useful to explain the signal communication between the nodes. FIG. 3 (b) shows two nodes 50 and 51 (hereinafter, node A and node B, respectively) connected by the link 52. As described, the link is a communication channel that connects the transceiver ports of each node as described above in connection with FIG. During the graph transformation process, a node needs to establish a parent-child relationship with an adjacent node. If at least one link is connected between the port of the first node and the port of the second node, those two nodes are said to be adjacent nodes. In FIGS. 3 (b) to 3 (d), it is assumed that the relationship to be changed is that node B is the parent of node A, and that it is appropriate for the node to establish that relationship.

[0019] When it is appropriate for node A to establish node B as its parent prior to setting the direction, node A signals "You Are My Parent" from the port to which link 52 is attached. Send (YAMP). This message may take any form as long as it can be seen that node A is generating the YAMP signal and node B can understand that the received message is YAMP. When the YAMP signal 53 is received by node B, node B responds to node A by sending "You Are My Child" (YAMC) to node A via link 52. Node A's arbitration state machine logic 11 keeps track of the time delay between the transmission of the YAMP signal 53 and the reception of the YAMC signal 54. The time measured specifies twice the propagation delay between node A and node B. Upon receiving the YAMC signal, Node A says "You Are My Child" Respond with "Acknowledged" (YAMCA) signal 55. This also gives node B the ability to determine that the propagation time delay between nodes is equal to the time delay between the transmission of YAMC and the reception of YAMCA. For half-duplex communication links, YAMCA messages also have the effect of properly orienting the communication channel.

[0020] In the case of a full-duplex communication link, the three logical messages YAMP, YAMC and YAMCA can be relayed by only two signal transmissions instead. Figure 3 (c) shows this situation, where node A continues to add the YAMP signal 56 until it receives the return YAMC signal 57. The YAMCA signal is logically transmitted to node B when it is detected that the YAMP signal no longer arrives. By using this triple asynchronous message exchange described, a mechanism is constructed so that both nodes involved in the message exchange can determine the propagation time delay via the link. This delay value is used when modifying competing events, as described further below, and during regular bus arbitration to optimize bus performance. Dynamic extraction of this parameter is mandatory. Instead, the maximum propagation time delay can be deductively specified even if optimal bus performance is not obtained.

[0021] After nodes A and B exchange messages meaning that node B is the parent of node A, it can be said that the link is directed. Node A, by its logic, labels the port to which link 52 is bound as the parent port (speaks to the parent node), and node B speaks to the child port (speaks to the child node) to which link 52 is bound. ). It is important to maintain the labels that a port obtains, as the methods described below are described by the labels assigned to the nodes and ports at a given point in time. Figure 3 (d) shows a shorthand schematic notation, with the direction arrow 58 in the figure indicating that node B is set as the parent of node A and that the link is directed.

【0022】<u style="single">Confirmation of direction</u>Here, the process of orienting the entire arbitrary topology will be described with reference to the processes of FIGS. 6 (a) to 6 (e) while returning to FIG. 3 (a). To help explain the topology transformation process, it is necessary to introduce a slightly more versatile definition. First, a "leaf" node is defined as a node that connects only one port. As soon as it is initialized after power-up or after other bus initialization, the node recognizes its state as a leaf node. A "branch" node is a node that has at least two connecting ports. Through all but one connection port, the branch node is receiving and responding to the YAMP signal. Through the remaining ports, the branch node is sending a YAMP signal, thereby confirming that the node is the parent node. A node has one parent (a node can only have one parent node) and all other ports reach the branch state until they are determined to be connected to the child node. do not do. A node is a "cycle" node because it is possible that it is part of a cycle that makes it impossible to set the orientation until the node is determined to be a branch prior to reaching the branch state. it is conceivable that.

The graph conversion procedure begins at step 60 during bus initialization (power-up or induction), at which point leaf nodes in any topology are recognized in step 61 and those nodes in decision box 66. Label themselves as leaf nodes in step 68 by determining that they have only one port to connect to. In the graph shown in FIG. 3 (a), nodes 33, 35, 36 and 37 are leaf nodes, each of which sends a YAMP signal to an adjacent node via a single connection port in step 69 after initial setup. .. The node receiving those signals then propagates the YAMC signal back to the leaf node in step 70 to determine one direction for a given link between each parent-child pair when YAMCA communication is complete. To do. In step 71, each Rifuno de is labeled with one connection port as a parent port and each receiving port on the parent node is labeled a child port.

[0024] A node on the graph that is not initially a leaf node is initially considered a "cycle node" for the reasons mentioned above and proceeds according to cycle node procedure 63. Any cycle node that labels all but one of the connecting ports as child ports propagates the YAMP signal from the remaining unlabeled ports in a later step 85. When the direction is set for the link, the cycle node will be labeled as a branch node there. That is, after leaf node 37 establishes its node 34 as a parent, node 34 has only one unlabeled port (labeling the link connection to node 37 as going through a child port). 34 broadcasts the YAMP signal to node 31, and as a result, node 34 becomes a branch node. Similarly, if node 31 identifies nodes 33 and 34 as its child nodes, node 31 broadcasts a YAMP signal to node 30. When a node is receiving a YAMP signal through all its ports in decision box 75, that node becomes the root node. In Figure 3 (a), after node 30 receives the YAMP signal from nodes 31 and 32, its label changes from cycle node to root node. In the graph of Figure 3 (a), node 30 may not necessarily be the root. If some of the links in the tree cause long propagation delays, node 30 may have received the YAMP signal on one port and then on the other port. unknown. Each node can be a root or even a leaf, and the leaf takes proper steps. FIG. 3 (e) shows the resulting directed graph in response to the communication signal shown in FIG. 3 (a), where each node is labeled and the direction is indicated by a black arrow.

【0025】<u style="single">Route conflict</u>In some situations, a route race condition can occur. This would happen, for example, if the arbitrary topology had an array symmetric with respect to the arbitrary topology shown in FIG. In the arbitrary graph shown in FIG. 4, nodes 160 and 161 are determined to be parents to the two leaf nodes to which they are joined, respectively. Next, each node propagates the YAMP signal to the other at about the same time. The route race condition is recognized by both related nodes in decision box 86. Each node receives a signal that designates it as its parent, while transmitting the same signal over the same port. Each of the competing nodes responds to the other with a YAMC signal in step 91, allowing each node to establish a "decision time" equal to twice the propagation time between the nodes.

The route race condition is resolved by utilizing the random determination mechanism built into each arbitrary state machine logic device 11 of each node. Each time the "decision time limit" elapses, each node randomly (with a 50% probability) decides in step 92 whether or not to send the YAMP signal to the other again. Almost certainly in a limited number of cycles, one node decides to designate the other as the parent without one going back and forth. The one designated as the parent becomes the root in step 95. Alternatively, a predetermined selection criterion value may be assigned to the node, and the larger or smaller value may be used to determine which is dominant in the competition event. Although the dynamic determination of the "determination time limit" gives the optimum performance, it is not indispensable for realizing the present invention. Alternatively, a deductively defined "decision time limit" may be used as long as it is longer than the worst case link propagation that can occur on any bus that uses this algorithm. The same methods used to resolve route conflicts are also used to resolve other race conditions described further below.

【0027】<u style="single">Route allocation</u>As explained earlier, the result of the graph transformation process is the assignment of root attributes to the only node in the graph. The root node has the final decision in the bus arbitration scheme described below, thus allowing the bus to be accessed with the highest priority without using a special priority time interval. In many cases, it is desirable to be able to assign route characteristics to a given node when it is manufactured or dynamically (during runtime) in order to optimize the given system. A given bus may contain nodes that require isochronous data transfer. Isochronous data is data that must be transmitted so as to have some value at a predetermined time. For example, music emanating from a compact disc must be transferred in pieces and transferred and output in the order in which they should be listened to, without major delay, unlike data files that are not necessarily in order.

[0028] Nodes can be classified into three categories with respect to route designation. These designations are made during manufacturing by using a higher level of software to perform the designation's hard wiring to the equipment, programming or decision of the arbitration state machine logic, and then initiating a reboot while maintaining that decision. It should be applied. The three specifications to which a node can be assigned with respect to being routed are: a node that does not want to be a root, a node that can (should) be a root, and a node that will be a root. Steps 81 and 83 test those designations. The node specified in the first category immediately starts the graph conversion procedure when instructed. This is usually immediately after the completion of the bus initialization procedure. A node in the second category delays the start of the process by a predetermined length of time after being instructed to start the graph transformation procedure in step 84. This delay increases the chances that the node will become the root. (The YAMP signal is more likely to propagate to that node due to its delay.) Despite the addition of delay, it is still possible that a "potentially root" node will not end with being designated as the root. This depends on the given topology and the message propagation delay. The amount of delay can be defined during design to be greater than the worst-case reasonable propagation delay when traversing fairly complex graphs.

Nodes that fall into the third category of routing possibilities only recognize that they have already transformed the graph and that all nodes must become roots after identifying themselves. Let's go. The arbitration state functional logic may perform this determination, or it may be software running on the host system. When this happens, the node that must become the route agrees with all the other nodes along the bus that it is about to become the only route, and the interrupted bus initialization signal described further below. Restarts the graph conversion process by sending. Then, in step 82, the node waits to become the root and does not participate in the graph transformation until it receives the YAMP signal on all its ports, which inevitably designates the node as the root. become. Once the route is fixed, the graph can be said to be directed. There is a defined relationship between all the adjacent nodes on the graph.

【0030】<u style="single">Cycle change</u>The graph directing procedure described above works only for non-cycle graphs. If there is a cycle in any topology, the cycle must be broken by the procedure starting in step 80. At step 79, the presence of a cycle is detected when the node is still labeled as a cycle node rather than a leaf, branch or root after a predetermined time-out cycle has elapsed. The "cycle detection" timing starts immediately after the bus initialization function ends. The time-out cycle must not be longer than the worst-case duration of the graph transformation process (additional delays for "potential" nodes and possible route contention events).

Since every message exchange is an asynchronous event, the "cycle detection" time-out event does not have to occur for all nodes in the graph at the same time. Therefore, it is possible for a node that has not yet reached the "cycle detection" time-out event to receive a message instructing that cycle resolution is in progress. Such a node ends its cycle detection time-out interval and initiates the appropriate cycle resolution process.

[0032] The method of cycle resolution according to the present invention requires the intervention of a user of a collection of nodes after assembly. When a node undergoes a "cycle detection" time out, the user of the system will be notified in step 100 of Figure 6 (e) via an output device where the cycle exists and the node is not next associated. .. The user is then instructed to break the link to eliminate the existence of any cycle. The user then returns control to the graph conversion procedure. If each of the loops is broken and there are no cycles left, then the procedure for transforming the graph as described in the previous section may proceed until the entire graph is non-cycled and directed. ..

【0033】<u style="single">Assignment of unique physical address</u>Once the non-cycle directed graph is determined from the original arbitrary topology, it is possible to assign a unique physical address to each node of the graph. The process begins with all leaf nodes requesting a bus by sending a bus request (BR) signal over its single connection port. The parent node that receives the signal waits until it finishes receiving the BR signal from all of its child ports, and then propagates the BR signal to its parent. The BR signal propagates through the graph until the route has received the BR signal from all of its children. If the route receives a bus request through all of its child ports, the route makes a decision to allow the bus through one port and propagate the bus deny (BD) signal through the remaining child ports. Run. The method of selecting which bus request should be allowed may be a deductive decision as described above, for example, when selecting ports from left to right or based on port numbering. A bus permit (BG) signal is sent from the route to the child it is requesting. If the requesting child is itself the parent node that propagated the bus request from one of its children, that child node was described earlier through all but one of its child ports. The bus rejection signal is transmitted by the same predetermined method as. Eventually, one leaf node receives the bus permission signal, that node responds with a bus permission confirmation (BGA) signal, and the BGA signal is propagated back to the root node. Propagation of BD and BGA signals serves to direct the communication links that would be required for half-duplex communication channels. Therefore, all the rejected nodes wait for the activity by the node that finally receives the BG signal.

[0034] The node finally permitted to access the bus transmits an address allocation packet. The node sends this packet over the bus, the packet is received by all other nodes, and each of those nodes counts the number of address packets it receives. The transmitted address packet may have some arbitrary information. The node's unique physical address is based on the number of address packets that the node counted before sending the address packet. That is, the two nodes do not acquire the same physical address even though the address information has not been assigned in advance. The actual composition of the address packet is arbitrary and may be any bitstream that is more efficiently available to the system. After sending the physical address assignment packet, the node sends a "child ID complete" signal (CIC) signal. The parent node that receives this on the child port then sends a "Child Identification Completion Confirmation" (CICA) signal to label the port as an identified child port. In response to the propagation of the next BR signal, the parent of the node that has just identified itself selects the next child to send the physical address packet. If all of the child nodes of a parent node identify themselves, the parent node requests the bus, and when it allows the bus, it propagates its physical address allocation packet. This procedure continues until all the nodes have confirmed the unique physical address assignment by the counting operation according to the predetermined selection criteria. FIG. 5 shows the graph of FIG. 3 (e) in which the left-to-right predefined selection criteria are realized. The node is assigned a unique address, node 33 receives the first address, and as mentioned above, root node 30 receives the eighth and last address. Upon completion of this procedure, each node in the graph will have a unique physical address, which need not be pre-established and may be used for system administration or other purposes.

【0035】<u style="single">Node self-identification</u>The node self-identification process essentially follows the same routine as the physical address allocation procedure described above. When each node sends its physical address assignment packet, the packet supports the ID of the local host associated with the node, how much power it requires, and, for example, the "soft power on" attribute. It may contain other information such as whether or not to do so. In fact, the node self-identification information acts as a physical address allocation packet because it is the basis of the count for acquiring a unique physical address no matter what information is transmitted. For node self-identifying packets, certain information about the node need only be "listened" by the node affected by the nature of the node it is announcing. As in the previous case, this procedure proceeds until all nodes have sent their node self-identification information.

【0036】<u style="single">Topology mapping</u>The method of topology mapping flows along the same line as physical address assignment and node self-identification. That is, in this procedure, when each node has undergone the process of address allocation or node self-identification, whether or not the node has the number of child ports that the node has and whether or not it has disabled ports. Further send information about all ports such as ka. For disabled ports, it would be desirable to implement communication conventions between the ports being disabled so that they can be identified from where they are disabled. Therefore, when a port identifies a disabled port, the port is given an identifier that points to its own ID as well as the port ID from which it was disabled.

By assembling any topology information relating to all ports received during the topology mapping procedure, the host or some software-level application will be able to logically reconstruct the resolved bus topology. This is for a number of purposes, including providing redundancy in which a previously disabled link can work against any node to prevent loss of communication channels in the event of an unexpected link failure. It is useful.

【0038】<u style="single">Fair Bus Access Arbitration</u>Once the topology mapping, node self-identification, or physical address assignment routines are complete, the bus can be considered up and running. One arbitration method realized in accordance with the present invention is a legitimate bus access arbitration method. When a node wants access to a bus, it sends a bus request (BR) signal over its parent port (unless it is the root). When a parent receives a BR signal from one child, it sends a bus rejection signal (BD) through all other child ports. The parent then propagates the BR signal through the parent and upwards until the signal reaches the route. The route issues a bus permit signal (BG) in response to the first BR signal it receives and sends a BD signal through all other child ports, which propagates downwards. Determines the direction of the link. The BG signal propagates downward through the graph until it reaches the requesting node, which in turn sends a bus confirmation (BA) signal, followed by the node sending to the bus. It is a packet of information that needs to be done. When the packet completes, all nodes either return to idle or enter idle.

[0039] If the route receives requests for the bus at about the same time, certain selection criteria involving the root node can be used to allow bus access to one of the nodes. This may be the same predetermined priority selection criterion as described above.

[0040] Another aspect of fair bus access arbitration is that the parent node has priority over its children. That is, when the parent node requests a bus, it transmits a BD signal through all of its child ports and then propagates the BR signal upwards towards the route. One possible problem with this mechanism may be that child nodes can fail to gain proper bus access if the parent has a large amount of information to send over the bus. That's what it means. Therefore, a widely used and well-known gap system has been introduced in the art. After using the bus, the node must wait for one gap period before it can request the bus again. This gives every node along the bus an equal opportunity to allow the bus, regardless of the topology arrangement of the nodes on the bus. To guarantee a fair arbitration protocol, the length of the gap must be greater than the worst-case signal propagation delay as it passes through the bus. Gap values can be pre-determined and hard-wired to node logic, but such a scheme results in near-optimal use of the bus in all but the most extreme cases. Topology mapping capabilities, combined with measurements of propagation delay between adjacent nodes performed during the graph transformation phase, allow the calculation of optimal fairness gaps that optimize bus performance for any particular implementation. ..

【0041】<u style="single">Priority bus arbitration</u>In the bus arbitration scheme implemented according to the fair bus access arbitration described above, it would be desirable for the route to always have bus priority. When this is achieved, the root node may allow itself a bus at any time. This is done by first transmitting the BD signal downward through all the nodes in the graph. Route-related priority bus access is very useful when a root node is required to perform isochronous data transfer.

【0042】<u style="single">Token passing bus arbitration</u>Instead of the fair bus access arbitration method and the priority bus access arbitration method described above, the present invention may be used in realizing the token passing bus arbitration method. Figuratively speaking, token passing bus access represents the concept that a node may communicate over the bus when the bus owns a token that is being passed between the nodes. Tokens are cycled from node to node so that each node receives a bus at a given point in the cycle. In the present invention, token passing is realized according to the same method as the physical address allocation routine described above. Select the order in which the tokens are passed from node to node using a given selection mechanism that is implemented. This order is similar to the order shown in Figure 5, which indicates the order of unique address allocation. When each node is assigned a token, it propagates its information packet along the bus while the remaining nodes are listening. The node then passes the tokens to the next logical node based on a predetermined ordering method as described above.

【0043】<u style="single">Preemptive bus initial setting</u>An important feature that can be achieved in accordance with the present invention is the concept of preemptive bus initialization. The state machine logic built into each node can trigger a bus initialization (BI) signal that should be propagated from the node through all its ports for some condition. When a node determines that it needs to signal the bus initialization conditions, the node guarantees that all neighboring nodes receive the BI signal through all its ports and then change it. Propagate for a sufficient amount of time to do so. Therefore, the node then enters the start procedure leading to the graph conversion process in the procedure described above.

[0044] There are some situations in which it may be necessary or desirable to trigger a preemptive bus initialization. First, this may be a node response to an unexpected error. In addition, at the host level, it may be determined that different nodes should acquire root attributes, eg isochronous data transfer nodes. This allocation is maintained throughout the bus initialization routine, so the desired node will wait during the conversion procedure until it receives the route designation. Another condition leading to preemptive bus initialization would be link breakage, in which case it would be necessary to calculate a new non-cycle directed graph for the attached node. The last important situation in which preemptive bus initialization should occur is when a device is added to the network, such as what is called a "hot addition" of peripherals. The port to which the new device is connected detects the presence or absence of a new node and is transparent to the users of the system, but for example, a bus initialization that allows the peripherals to be increased or decreased without the need for interruption and repowering. Trigger. Compute a new non-cycle directed graph containing the presence of the added node. It is possible that removing some nodes does not need to trigger bus initialization, for example, removing leaf nodes does not harm the network. However, if a branch node is specified from a running bus, it may be necessary to reconstruct the graph.

Although the present invention has been described by preferred embodiments, it will be appreciated by those skilled in the art that various modifications and modifications can be made without departing from the spirit of the invention. Therefore, the present invention should be judged by the claims that follow.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 shows a block diagram of hardware layer realization utilized in accordance with the present invention.

FIG. 2a shows any assembled collection of nodes, showing non-cycled ones.

FIG. 2b shows any assembled collection of nodes, including cycles.

FIG. 3a is an arbitrarily assembled collection of nodes of FIG. 2A undergoing a graph transformation process according to the present invention.

[Fig. 3b] Fig. 3 (b) shows an example of alternative communication exchange between nodes in realizing the present invention.

FIG. 3c shows an example of alternative communication exchange between nodes in realizing the present invention.

[Fig. 3d] Fig. 3 (d) shows an example of alternative communication exchange between nodes in realizing the present invention.

FIG. 3e graphically illustrates a directed graph obtained from an arbitrarily assembled network of nodes in FIG. 2A.

FIG. 4 shows a symmetric graph array that requires changing route contention.

FIG. 5 shows a non-cycle directed graph with a unique address allocation sequence that can be indicated.

FIG. 6a shows the overall flow of a process according to a preferred embodiment of the present invention.

FIG. 6b shows the flow of leaf node procedures in a process according to a preferred embodiment of the present invention.

FIG. 6c shows the first part of the cycle node procedure of a process according to a preferred embodiment of the present invention.

FIG. 6 (d) shows the second part of the cycle node procedure of the process according to the preferred embodiment of the present invention.

FIG. 6e shows the flow of route contention processing for a process according to a preferred embodiment of the present invention.

FIG. 6f shows a process cycle change process according to a preferred embodiment of the present invention.