Patent Publication Number: US-8984194-B2

Title: Multi-master bus arbitration and resource control

Description:
CROSS-REFERENCE TO A RELATED APPLICATION 
     The present application claims priority to provisional U.S. patent application Ser. No. 61/435,010, filed on Jan. 21, 2011, which is assigned to the assignee of the present application and incorporated herein by reference. 
    
    
     BACKGROUND OF THE INVENTION 
     This invention is related to a new arbitration mechanism for use in system resource management, such as in modern multiprocessor driven computer or computer-controlled systems where one or more resources must be shared. Allowing unrestricted access to a shared system resource may result in system failure, as the result of data corruption, for example. 
     A computer network usually comprises multiple computers or processors that communicate, depending on the number of processors in the network, by various mechanisms such as Ethernet or CAN-bus (CSMA/CD), or any asynchronous serial bus employing master/slave arbitration, or a token passing or similar “round robin” protocol. Ethernet is suitable for a large network, but it is inefficient when applied to a small network. In contrast, the flexibility of a serial bus using master/slave arbitration or token passing technology fit the communication needs of a small, lightweight network. 
     A master/slave system comprises a plurality of processor divided into two groups, one group usually being a single master processor and the other being slave processors. The master processor and slave processors are interconnected by a bus system, typically including a command/data bus and optionally an address/control bus. The slave processors have to constantly wait for permission from the master processor to access their destination; this waiting for the permission slows communication among processors. For the token passing technology, nodes are logically in a ring but are physically connected by a common bus. All tokens are broadcast to every node on the network. Every node on the network has to read the passing tokens to determine if it is a recipient of a message. Only the node having the destination address of a passing token would grab such passing token and act upon the data payload, all other nodes discard the data carried by the token. A node&#39;s handling of data from a passing token that is addressed to other nodes wastes time. Additionally, existing arbitration mechanisms for bus mastership are either overly complex or require an active bus concept to be effective. 
     The present invention proposes a multi-master bus arbitration mechanism that does not need a token passing or similar “round robin” protocol and active bus technology on the network to manage a communication bus to which only limited number of nodes can access. Additionally, the multi-master bus arbitration mechanism can control the number of active nodes, in a multi-node architecture, that can obtain access to the communication bus at any time, and it eliminates all data collisions on the communication bus, while adding minimal complexity to system designs. 
     SUMMARY 
     An apparatus for controlling access of a plurality of nodes external to a shared resource, to which accesses by the number of nodes must be restricted, in a computer or computer-control system, the apparatus comprises an aggregation component capable of generating a biased signal from a request signal sent by a node of the plurality of nodes requesting access to the shared resource, a reference signal, and a comparator in which the reference signal is preset comparing the reference signal with the biased signal and generate a logic output signal interpreted either as “access to the share resource granted” or “access to the share resource denied”. These and other features, aspects, and advantages of the present invention will become better understood with reference to the following description, appended claims, and accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1 . A flowchart showing the arbitration process that a node accesses to a shared resource. 
         FIG. 2 . A flowchart showing a backoff algorithm mechanism. 
         FIG. 3 . A flowchart showing a safety mechanism. 
         FIG. 4 . A circuit for a two-wire implementation of the arbitration mechanism of the present invention. 
         FIG. 5 . A circuit for a single-wire implementation of the arbitration mechanism of the present invention. 
         FIG. 6 . A shared resource is a communication bus. 
     
    
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS 
     The mechanism to be described in the present invention for controlling access of a plurality of nodes external to a shared resource, to which accesses by the number of nodes must be restricted, is applicable to any shared source in a computer or computer-control system. The present design delivers the following advantageous features. It provides localized arbitration to obtain resource access and localized self-management of resource mastery; eliminates resource seizure locally; it allows equal access; encapsulate all four above features with the same circuit/protocol. However, the present invention does not require that all the advantageous features need be incorporated into every embodiment. 
     In an embodiment, an apparatus for controlling access of the plurality of the nodes to the shared resource comprises a comparator, a reference signal preset in the comparator, and an aggregation component. Each of the plurality of nodes that need access to the shared source is capable of adding a request signal, to access to the shared resource, to the aggregation component. The aggregation component adds up the request signals received from those nodes of the plurality of nodes that request access to the shared resource and generates a biased signal. The comparator compares the reference signal and the biased signal and generates a logic output signal. 
     In an embodiment, the comparator comprises a digital signal comparator and an analog to digital converter. The analog to digital converter converts the biased signal from the aggregation component to a digital value and the digital comparator compares the digital value with the digital reference value. In another embodiment, an analog signal comparator is used as the comparator. The analog comparator compares the biased signal with the analog reference value. 
     The apparatus for controlling access of the plurality of the nodes to the shared resource further comprises a decision making logic. A node of the plurality of nodes applies/removes the request signal for access to the shared resource to/from the aggregation component by the decision making logic. After waiting an appropriate length of time for the logic output signal propagation, the decision making logic associated with those nodes of the plurality of nodes that have requested access to the shared resource interprets the logic output signal as either an “access to the shared resource granted” or “access to the shared resource denied” signal. When the biased signal is such that the number of external nodes requesting access to the shared resource exceeds a designed limit, the comparator generates an output signal that the decision making logic received can be interpreted as “access to resource denied” output signal. Otherwise, the comparator generates an output signal that the decision making logic can interpret as “access to resource granted.” Specifically, if the access to the shared resource requested by a node of the plurality of nodes is granted, the node will use the shared resource as desired. If the access to the shared resource by a node of the plurality of nodes is denied, the decision making logic associated with the node would remove its access request signal from the aggregation component, wait a random length of time, then reattempt to obtain access to the shared resource. When the node does not need to access to the shared resource anymore, the node relinquishes its hold of the shared resource by removing its access request signal from the aggregation component through the decision making logic. 
     The plurality of nodes are physical electronic devices such as memory devices, graphic display units, etc., which are tinder control of microcontrollers or microprocessors, or microcontrollers. 
     The total number of nodes connected to the shared resource in a computer system is only limited by the resistive, inductive, and capacitive constraints of the electrical circuit and its affiliated components. In one embodiment, the apparatus for controlling access of the plurality of the nodes to the shared resource is designed such that only one node can access to the restrict resource at a time, which is a mutex configuration. In another embodiment, the apparatus for controlling access of the plurality of the nodes to the shared resource is designed such that several nodes can access to the restricted resource simultaneously, which is a semaphore configuration. 
     The above design is demonstrated in the  FIGS. 1 ,  2 , and  3 . An inquiry is made in Step  102  as to whether a node needs access to the shared resource. If “yes”, the decision making logic associated with the node applies the request signal to the aggregation component in Step  104 . In Step  106 , the aggregation component aggregates the request signals that have been received and generates the biased signal from those request signals. Afterward, the comparator compares the biased signal with the preset reference signal and generates the logic output signal in Step  108 . The decision making logic waits until the comparator propagation delay times elapses; then an inquiry is made in Step  110  as to whether the logic output signal indicates that the shared resource is available. If the answer is “yes” to the inquiry in Step  110 , the node starts to use the shared resource in Step  112 . After the node&#39;s use of the shared resource is completed the decision making logic of the node removes the request signal from the aggregation component in Step  114  and cancels a maximum possession time monitor. 
     Referring to  FIGS. 1 and 2 , if the answer is no to the inquiry in Step  110 , in Step  116  the decision making logic removes the request signal from the aggregation component and to proceed to a backoff algorithm mechanism of Step  128 . The backoff logarithm assigns a random wait time to a node of the plurality of nodes requesting access to the shared resource. In Step  128 , an inquiry as to whether the request is a high priority is made. If “yes”, then the decision making logic goes to Step  138  to generate a random delay value within the high priority range. If “no”, the decision making logic goes to Step  130  asking whether the request is a normal priority request. If “yes” to the inquiry in Step  130 , the decision making logic generates a random delay value within a normal priority range in Step  134 ; otherwise, the decision making logic moves to Step  132  to generate random delay value within a low priority range. In Step  136 , the decision making logic waits until delay time elapses, then go to Step  1104  to reattempt to access the shared resource. 
     In an embodiment, a safety mechanism that ensures that failure of a node does not cripple the entire system is set up. Once the node starts to use the shared resource, the decision making logic commands a maximum possession time monitor to forbid over-long occupation. If the node suffers catastrophic failure, its request signal will be forcibly removed from the aggregation component. The mechanism is demonstrated in the  FIG. 3 . 
     Referring to  FIG. 3 , when a node starts to use the shared resource, the decision making logic commands a maximum possession time monitor start to count time in Step  118 . A determination is made as to whether the maximum possession time monitor is cancelled by Step  114  in Step  120 . If “yes”, the maximum possession time monitor terminates in Step  122 . If “no”, another determination is made as to whether the maximum possession time monitor expires in Step  124 . If “yes” to the inquiry in Step  124 , the decision making logic of the node removes the request signal from the comparator and cancels the maximum possession time monitor in Step  126 . 
     In an embodiment, the reference signal and the request signal are voltage and an voltage comparator is applied. 
       FIG. 4  shows an embodiment of a two-wire system when a voltage comparator is employed; two separate lines built in the computer system conduct each function of “shared resource busy” and “request signal to send/access” by means of an electronic circuit breaker scheme. The apparatus  14  for controlling access of the plurality of the nodes  34  to the shared resource  10  comprises an voltage comparator  16  built in the computer system, a preset voltage, Vref  18  stored in the voltage comparator  16 , and at least one resistor  33  having a known value arranged in series with an aggregation component  20 , connected with the voltage comparator  16 . The aggregation component  20  comprises a plurality of parallel resistors  32  built within the computer system and the plurality of resistor controls  30 , correspondently associated with each of the plurality of parallel resistors  32 , built within each of the plurality of the nodes with which its correspondent resistor  32  communicates. The aggregation component  20  is shown in a thicker gray line. The resistor  33  is a permanently connected to the apparatus  14 . Each of the plurality of parallel resistors  32  communicating with an individual node of the plurality of node is connected to the aggregation component  20  only when such a node need access to the shared resource  10 . 
     The apparatus  14  for controlling access of the plurality of the nodes to the shared resource  10  further comprises a decision making logic  28  built within each of the plurality of nodes, with which the decision making logic  28  communicates. When a node of the plurality of nodes  34  need access to the shared resource  10 , its decision making logic  28  sends the request signal to the aggregation component  20 . In this case, the request signal is realized by closing the resistor control  30  and thereby connecting the resistor  32  to the aggregation component  20 . The aggregation component  20  adds up resistance of the resistors  32  connected to the aggregation component  20  and generates the biased signal, a voltage dropped across the aggregation component  20 , which will be sent to the voltage comparator  16 . The voltage comparator  16  compares the preset reference voltage, Vref  18  with the biased signal, and generates the logic output signal and sends it to the decision making logic  28 . If the logic output signal is interpreted by the decision making logic  28  as “access to the shared resource granted”, the node starts to use the shared resource  10  as desired. Otherwise, it has to wait as indicated by the FIG. 
     In another embodiment, referring to  FIG. 5 , a single-wire system is used, a single wire being built in the computer system implements both the functions of “shared resource busy” and “request to send/access” by means of an electronic circuit breaker scheme. The apparatus  14  for controlling access of the plurality of nodes  34  to the shared resource  10  has a voltage comparator  16  built in each node of the plurality of nodes instead of in the computer system, a preset reference voltage, Vref  18 , and at least one resistor having a known value in series with an aggregation component  20 . The aggregation component  20  comprises a plurality of parallel resistors  32  and a plurality of resistor controls  30  separately associated with each of the plurality of parallel resistors  32 . Each of the plurality of parallel resistors  32  and its correspondent resistor control  30  are built within each of the plurality of nodes with which the resistor  32  communicates. The aggregation component  20  is shown in a thicker gray line. The resistor  33  is a permanently connected to the apparatus  14 . Each of the plurality of parallel resistors  32  communicating with an individual node of the plurality of node is connected to the aggregation component  20  only when such a node need access to the shared resource  10 . 
     The apparatus  14  for controlling access of the plurality of the nodes to the shared resource further comprises a decision making logic  28  implemented by a controlling mechanism—software and/or hardware. The decision making logic  28  is built within each node of the plurality of nodes  34  with which it communicates. When a node of the plurality of nodes  34  need access to the shared resource  10 , its decision making logic  28  sends the request signal to the aggregation component  20  by closing the correspondent resistor control  30  and thereby connecting a resister  32  to the aggregation component  20 . The aggregation component  20  adds up the resistance of the parallel resistors  32  connected to aggregation component  20 , and generates a biased signal, the voltage dropped across the aggregation component  20 , which will be sent to the voltage comparator  16 . The voltage comparator  16  compares a reference voltage, Vref  18  with the biased signal and sends a logic output signal to the decision making logic  28 . If the logic output signal is interpreted by the decision making logic  28  as “access to the shared resource granted”, the node starts to use the shared resource  10  as desired. Otherwise, it has to wait as indicated by the  FIG. 2 . 
     In an embodiment, to complete the task stated in the previous paragraph, the decision making logic  28  is implemented using software that is incorporated into the node&#39;s main application software. The node&#39;s main application software executes a main task of the node with which the decision logic  28  is associated. Also, in an embodiment, the decision making logic  28  is implemented in hardware by coding the algorithm in the silicon of a microprocessor or microcontroller, using silicon die area dedicated to this purpose. This is accomplished by using discrete components such as logic gates, comparators, timers, counters, data storage registers, RAM, ROM and other simple electronic building blocks commonly used to implement “on chip” peripherals. In yet another external hardware implementation of the decision making logic  28 , simple, low cost microcontrollers dedicated entirely to the decision process may be employed; the microcontroller would have the software implementation as their main application code. These aforesaid embodiments for the decision making logic  28  are applicable both for the two-wire system and single-wire system. 
     In an embodiment for the single wire system, the voltage comparator  16  is built into the silicon die area, where the algorithm used for decision making logic  28  is coded. In another embodiment, the comparator is external to the decision making logic  28 . 
     In an embodiment, the resistor controls  30  is a circuit breaker or switch in conjunction with software for controlling the plurality of parallel resistors to connect or disconnect to the aggregation component  20 . This embodiment is suitable for both the single-wire and two-wire system. In another embodiment the switch is an electronic device such as a transistor. 
     In an embodiment, the voltage comparator  16  is a dedicated voltage comparator. In another embodiment, an operational amplifier configured to function as the voltage comparator  16  is implemented. To be compatible with the plurality of nodes, if the plurality of nodes are microprocessors, a dedicated voltage comparator and a transistor-transistor logic (TTL) would be implemented, and in the other situations, an operational amplifier configured to function as the voltage comparator and programmable logic controller (PLC) input voltage is utilized. Both TTL level and PLC level are either logic high or logic low. The TTL or PLC circuit is designed such that when the biased signal is equal to or less than the reference voltage, the TTL or PLC level would swing from logic low to logic high indicating the shared resource  10  unavailable, in other words, indicating access to the shared resource  10  denial. In contrast, if the biased signal is larger than the Vref  18 , both of them would stay logic low indicating the shared resource  10  available, in other word, access to the shared resource granted. The TTL or PLC circuit may also be designed to invert logic levels. 
     In an embodiment, the TTL level is less than or equal to 5V. 
     Referring to the  FIG. 5 , the voltage of Vref.  18  and resistance of resistors  33  and  32  are arbitrarily set to be compatible with intended application, choices of devices, preference of the engineers implementing the design. Here is an example for illustration, assuming the resistance of resistors  32  of the aggregation component  20  has the same values equal to 110Ω and the resistance of resistors  33  is equal to 100 KΩ. Further, assuming the voltage of the aggregation component  20  is 10V, then its preliminary voltage is 10V when none of the plurality of parallel resistors  32  is connected to the aggregation component  20 . When one node is connected to the aggregation component  20 , the biased signal or the voltage dropped across the aggregation component  20  would be equal to 5.24; when two nodes are connected to the aggregation component  20 , the biased signal would be 3.55V; when three nodes, then 2.68V. Assuming Vref  18  is 5V, a half of the preliminary voltage of the aggregation component  20 , the TTL level is designed to stay logic low, when the biased signal is larger than the Vref  18 , 5V indicating the shared resource  10  available. Thus, when one node requests to access to the shared resource  10 , the biased signal is 5.24V, larger than the Vref  18 , 5V, the TTL level staying in logic low and indicating the shared resource  10  available; the node would use the shared resource as desired. When two nodes request to access to the shared resource  10  at the same time, the biased signal would be 3.55V, less than the Vref  18 , 5V, the TTL level switching to logic high and indicating that the shared resource  10  is unavailable; the node&#39;s request to access would be denied. The aforementioned is a representation of a mutex configuration. In contrast, if the Vref  18  is design as 3V. When two nodes request to access to the shared resource  10  at the same time, the biased signal would be 3.55V, the TTL level would still stays in logic low indicating that the shared resource  10  is available. This is a representation of a semaphore configuration. 
     In an embodiment, the shared resource  10  is a communication bus demonstrated in  FIG. 6 . The present invention also can apply to other shared resources. In Step  144 , one byte of data to transmit is retrieved from a message buffer, in Step  146 , an inquiry is made as to whether this message terminator character. If “yes”, go to Step  114 ; if “no”, go to Step  148  loading data into transmitter holding a register. In Step  152 , wait until data is transmitted. In Step  154 , increment data transmitted counter and index to next byte in message buffer. In Step  150 , an inquiry is made as to whether the number of transmitted character equal to the maximum count. If “yes,” go to Step  114 ; if “no,” go to Step  144 . 
     The above examples are illustrative only. Variations obvious to those skilled in the art are a part of the invention.