Abstract:
An access control system (10) for controlling access to a shared resource among a plurality of service requestors is described. When a service requestor seeks access to the shared resource, it generates a service request signal which includes its assigned unique service request priority number. The outputs of all the service requesters are applied to pipelined first and second OR-trees (75, 78) which produce an OR-ed output signal. The OR-ed output signal is then applied to an access control unit (38) which performs an arbitration protocol to determine the highest priority number. Each service requester includes a state machine which selectively applies the bits of its priority number to the OR-trees (75, 78). The use of pipelined protocol with two OR-trees (75, 78) reduces cycle consumption and permits arbitration within a single clock cycle.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates generally to a system and method for arbitrating access to a shared resource among multiple requesters, and more particularly to a system and method which determines the requestor with the highest priority. 
     2. Description of the Related Art 
     Many systems must manage access of peripheral devices to a shared resource. One common approach to manage the resource conflict is to prioritize the requests and to give the resource to the requestor with the highest priority number. In a computer system, for example, peripherals generally obtain access to the central processor through an interrupt system. 
     There are many ways to determine which requester has the highest priority. A common technique is a round robin scheme in which the arbiter checks the priority number of each requestor sequentially. While straightforward, the round robin technique requires several clock cycles for each bit of the priority number to complete in systems with many requestors. Other algorithms which are faster than the round robin technique have been used. Some require implementation using a dynamic wired-or function. However, new semi-custom techniques, such as logic synthesis, do not easily allow inclusion of dynamic logic, e.g., precharge-discharge logic. 
     There is a need for an arbitration system which can be implemented with static logic or a simple OR-tree. There is also a need for an arbitration system which can determine the requester with the highest priority using a single clock cycle for each bit of the priority number. There is a need for an arbitration system which is flexible enough to enable an expanded protocol. 
     SUMMARY OF THE INVENTION 
     To achieve the foregoing and other advantages, an access control system for controlling access to a shared resource according to the invention includes a plurality of service request nodes (SRNs), first and second OR-trees and an interrupt control unit (ICU). Each SRN is assigned a unique priority number, which is programmed by the user. Essentially, the access control system determines interrupt priority by performing a bit-by-bit comparison between the SRN priority numbers. To accomplish this comparison, outputs from each SRN, which can represent bits of the priority number, are OR-ed in the first and second OR-trees and the result is propagated to the ICU. The ICU performs an arbitration round which determines which of the requesting SRNs has the highest priority. The ICU then generates an interrupt request signal which includes the priority number of the winning SRN and presents it to the shared resource. The ICU maintains the priority number of the current SRN having access to the shared resource to ensure that only an SRN with a higher priority number can bump an SRN currently accessing the shared resource. 
     The access control system utilizes a pipelined protocol, which is made possible by the two OR-tree arrangement. The pipelined protocol significantly reduces arbitration time. 
     The arbitration according to the invention can be used for any kind of arbitration, including interrupt arbitration, direct memory access (DMA) and multi-master management. The system uses OR-trees, but dynamic wired OR-functions or other wired-OR implementations may also be used. 
     Each SRN may include a state machine which selectively applies the bits of the priority number to the first and second OR-trees. The system includes one or more service request node counters (SRNCs) which provide down count signals to the SRNs for synchronizing selection of the priority number bits during an arbitration round. 
     Many advantages are achieved with the invention, which includes a pipelined protocol that reduces interrupt arbitration time. Additionally, space savings are achieved in that the wires used for arbitration are also used for passing additional information after the arbitration. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a pipelined arbitration system according to an embodiment of the present invention. 
     FIG. 2 is a block diagram of a service request node according to an embodiment of the present invention. 
     FIG. 3 is a block diagram of a service request node counter according to an embodiment of the present invention. 
     FIG. 4 is a tree diagram of a state machine for use in the service request node of FIG. 2. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     By way of example, a block diagram of an access control system 10 according to the present invention is shown in FIG. 1. The access control system 10 arbitrates access of any number of peripherals 30, 40 to a shared resource 50, such as a central processing unit (CPU) or direct memory access (DMA) controller, or the like. The peripheral 30 may include three segments which can assert requests for access independently via a plurality of interrupts 33, 34 and 35. Similarly, the peripheral 40 may include four segments which can assert requests for access independently via a plurality of interrupts 41, 42, 43 and 44. 
     Each interrupt request output (INT1, INT2, etc.) of the peripherals 30, 40 may be applied to the inputs of a plurality of service request nodes (SRNs). As shown, the interrupts 33, 34 and 35 from the peripheral 30 may be applied to the inputs of SRNs 15, 16 and 17, respectively. Similarly, the interrupts 41, 42, 43 and 44 of the peripheral 40 may be applied to the inputs of SRNs 18, 19, 20 and 21, respectively. Each SRN has a programmable service request priority number, which uniquely defines its respective interrupt priority. Each priority number can be stored within a corresponding SRN, in a register 110 (FIG. 2). 
     A plurality of service request node counters (SRNCs) 32 and 34 count down so that the bits in the priority number can be accessed and arbitrated on a bit-by-bit basis, with the most significant bit being arbitrated first. For each arbitration round, the arbitration continues for each bit in the priority number. The SRNCs 32 and 34 are shown as driving the groups of SRNs 15-21, but could be configured to drive individual SRNs. However, since each peripheral 30-40 normally has more than one SRN 15-21, it is convenient to have one common counter for each peripheral 30, 40. 
     The outputs of the SRNs 15-21 may be applied to two OR-trees, ITREE 75 and UTREE 76. The dual OR-tree arrangement permits the interrupts to be arbitrated in a pipelined manner, as discussed below in detail. The OR-trees 75-76 perform a wired-OR function of all SRN 15-21 outputs. The delay times through the OR-trees 75,76 can be reduced by building balanced trees with multiple input OR-gates, which may be optimized according to the clustering of the SRNs 15-21. 
     The ITREE 75 includes three inputs from the OR-gates 71,73,77. Similarly, the UTREE 76 receives three inputs from the OR-gates 72,74,78. As shown, the outputs 81-94 from the SRNs 15-21 are applied to the OR-gates 71-74. Depending on the number of SRNs 15-21 included in the access control system, a different number of inputs for the OR-gates 71-74 may be required. The outputs of the two OR-trees 75-76 are provided to the ICU 38 as the signals ITREEOUT and UTREEOUT. 
     Based on the OR-ed results from the OR-trees 75-76, the interrupt control unit (ICU) 38 can monitor and control the arbitration round to determine the SRN with the highest priority number, among those SRNs requesting an interrupt. 
     Referring to FIG. 2, a block diagram of an SRN 15-21 is shown. The SRN 15-21 may include a state machine 101, an ITREE AND-gate 103, an UTREE AND-gate 104, a multiplexer 109 and the register 110 for storing the priority number, and a register 102 for storing an interrupt request flag. When the peripheral 30 (FIG. 1) requests access to the shared resource 50, it sends an interrupt signal (INT1-INT3) 33-35 to an SRN 15-17. The interrupt signal sets the request flag to &#34;1&#34; in the register 102. 
     As shown in FIG. 3, the SRNCs 32, 34, may include a loadable down counter 137 (shown as a 4-bit down counter) and an OR-gate 139. The down counter 137 can be a synchronous counter that decrements its output in response to a clock signal (not shown). The signal lines 69 and 70 from the SRNCs 32, 34 carry an arbitration start signal, ARBSTART 135, and a priority bit index signal, PBITINDEX 133, which are applied to the SRNs 15-21. As shown, the signal PBITINDEX is a 4-bit value applied to the MUX 109 as a select signal to identify the specific bit being arbitrated. The specific bit being arbitrated is selected from one of the eight bits contained in register 110 or the bit stored in the request flag register 102. In the example shown, when the most significant (MSB) bit of PBITINDEX is equal to &#34;1&#34;, the request flag register 102 is selected. Otherwise, the lower three bits of PBITINDEX indicate one of the eight bits stored in register 110. 
     The ARBSTART 135 signal is generated by the OR-gate 139 in response to the command signal 61. Accordingly, the ARBSTART signal 135 is asserted anytime the command signal 61 is greater than zero. The ARBSTART signal 135 indicates that an arbitration round is commencing. 
     The arbitration round, controlled by the ICU 38, is used to determine the highest priority number of all SRNs 15-21 requesting access to the shared resource 50. The ICU 38 begins an arbitration round by sending a command signal (COMMAND) via line 61 to the SRNC counters 32 and 34. The command signal can be a three-bit value, indicating the length of the priority number stored in the register 110 (FIG. 2). The ICU 38 can store information about arbitration length and the length of the priority number. Upon receipt of the command signal on line 61, the SRNC 32, for example, begins its down count cycle by sending a signal 69 to the SRNs 15-17. Similarly, the SRNC 34 begins its down count cycle by sending a signal 70 to the SRNs 18-21. 
     When the command signal 61 is &#34;111&#34; to &#34;001&#34; (7 to 1 decimal), the down counter 137 is loaded with the corresponding value and ARBSTART signal 135 is activated. When the command signal 61 is &#34;000&#34; (0 decimal), the down counter 137 counts down (provides PBITINDEX signal 133) until &#34;1111&#34; (-1 decimal) is reached. The contents of the request flag register 102 can be accessed when output &#34;1111&#34; is provided to the MUX 109. 
     In this example, the minimum arbitration length in the command signal 61 may be &#34;001&#34;, so that the two least significant bits of the register 110 are output during an arbitration round. Since the two least significant bits can represent four possible values, i.e., &#34;00&#34;, &#34;01&#34;, &#34;10&#34;, or &#34;11&#34;. The minimum arbitration length of &#34;001&#34; can select a winning priority number from among a maximum of four SRNs participating in a given arbitration round. 
     During an arbitration round, priority bit selection is controlled by the output PBITINDEX 133 of the SRNCs 32, 34; which, in turn, controls the multiplexer 109 to sequentially provide the value of each bit of the priority number to the inputs of the AND-gates 103-104. During an arbitration round, the state machine 101 receives as inputs the signals ARBSTART 135 and ITREERESULT 64 from the ICU 38. Depending on the output of the state machine 101, the bits of the priority number will be passed to either ITREE 75 or UTREE 76 via the AND-gate 103 and the AND-gate 104, respectively. The ICU 38 sets ITREERESULT 64 once for each priority bit arbitrated. The ITREERESULT 64 is set to equal either the ITREEOUT 62 or the UTREEOUT 63. The ITREERESULT is set to the UTREEOUT when all participating SRNs are in an &#34;uncertain&#34; state, which is described below. 
     At the end of the arbitration round, the ICU 38 compares the priority number of the winning SRN to the priority number of an SRN currently accessing the shared resource 50, should there be one. If the winning priority number is higher than the current priority number (CPN), the ICU 38 assets an interrupt request signal 65 (INTREQ). The shared resource 50 provides the CPN to the ICU 38 via line 68. This prevents an interrupt with a lower priority from disturbing a higher priority service. In addition, the priority number of the winning SRN is provided to the shared resource 50 as a pending priority number (PPN) via line 66. The shared resource 50 can send an acknowledgement of the received interrupt and PPN via line 67, as signal INTACK. 
     During each clock cycle, the SRNCs 32, 34 decrement their outputs, the multiplexers 109 in each SRN 15-21 provide the next priority bit to the AND-gates 103-104, and, depending on the current state of the state machine 101, the priority bits pass through the AND-gates 103, 104 and are combined in the OR-trees 75-76. 
     For purposes of illustration, an arbitration toward using a single OR-tree is described. Interrupt arbitration using a single OR-tree is similar to a successive approximation algorithm. In a synchronous system, where state transitions occur according to a clock signal, the successive approximation algorithm can require two clock cycles for each bit of the priority number. The algorithm works as follows: In the first clock cycle, every SRN which has a pending interrupt request drives the most significant bit of its priority number onto the OR-tree. In the second clock cycle, the OR-ed result is (ITREERESULT) fed back to the SRNs. The SRNs then decide whether they participate in the further arbitration or give up because they have no chance to win highest priority. Each SRN makes this decision based on the following conditions: If the SRN produced a priority bit of &#34;1&#34; during the first cycle and ITREERESULT is also &#34;1&#34;, then the SRN participates in the second cycle. If the SRN produced a priority bit of &#34;0&#34; and ITREERESULT is also &#34;0&#34;, the SRN participates in the second cycle. If the SRN outputs a priority bit of &#34;0&#34; and the OR-ed result is &#34;1&#34;, the SRN gives up and ceases to participate in the arbitration round. 
     To complete the arbitration round, the two cycles are repeated for each next less significant bit until the least significant bit is reached. Because each SRN has a unique priority number, at the end of the arbitration round only one SRN is left to participate in the second cycle; it is the winner of the arbitration round. 
     As applied to a single OR-tree, synchronous arbitration system, the successive approximation technique consumes two clock cycles per priority bit and is an improvement over the round robin technique of the prior art. However, in the dual OR-tree system, arbitration for each bit in the priority number can be completed within one clock cycle. This is possible because SRNs outputting a priority bit of &#34;1&#34; automatically participate in subsequent bit arbitrations, while SRNs outputting a &#34;0&#34; are not certain to participate in the next bit arbitration. 
     The SRNs in the &#34;uncertain&#34; state use a different OR-tree (UTREE 76) than the SRNs outputting a &#34;1&#34; (ITREE 75), as described in more detail below. This permits the bit arbitration period to be reduced to one clock cycle. 
     FIG. 4 is a state diagram which shows the states and actions for the state machine 101. The state machine 101 can be a synchronous machine that transitions between states on the occurrence of a clock edge. The state machine 101 has five states: &#34;I --  am --  in&#34;, &#34;I --  am --  out, &#34;I --  won&#34;, &#34;uncertain&#34; and &#34;acknowledge&#34;. On power-up, the state machine is initialized into the &#34;I --  am --  out&#34; state. The arbitration round begins when ARBSTART 135=&#34;1&#34; and REQFLAG 102=&#34;1&#34;; upon this occurrence, the state machine 101 enters the &#34;I --  am --  in&#34; state. In this state, if the priority bit being arbitrated (PBITVAL) is &#34;1&#34;, the state machine 101 stays in the &#34;I --  am --  in&#34; state. When the state machine 101 is in the &#34;I --  am --  in&#34; state, it sets the ITREE --  ENABLE 105 to &#34;1&#34;; allowing PBITVAL to propagate through AND-gate 103. In this state, the machine 101 also sets UTREE --  ENABLE 106 to &#34;0&#34; to disable AND-gate 104. 
     If an end of count is detected (PBITINDEX=-1), the state machine transitions to the &#34;I --  won&#34; state, indicating that the SNR include the state machine 101 has won the arbitration round. In PBITVAL=&#34;0&#34;; the state machine 101 transitions from the &#34;I --  am --  in&#34; state to the &#34;uncertain&#34; state. In the &#34;uncertain&#34; state, the state machine 101 sets ITREE --  ENABLE 105 to &#34;0&#34; to disable AND-gate 103 and UTREE --  ENABLE 106 to &#34;1&#34; to allow PBITVAL to propagate through AND-gate 104. 
     The OR-ed results from both OR-trees are provided to the ICU 38, which then returns results of the first bit to all the SRNs via ITREERESULT 64, which contains &#34;OR&#34;-ed bits from ITREE or UTREE if all SRNs are in the &#34;luncertain&#34; state. 
     When processing the next priority bit, if PBITVAL=&#34;1&#34;, the state machine 101 stays in the &#34;I --  am --  in&#34; state, regardless of the value of ITREERESULT. If PBITVAL=&#34;0&#34;, the state machine 101 transitions to the &#34;uncertain&#34; state, regardless of the value of ITREERESULT. If the state machine 101 is already in the &#34;uncertain&#34; state and ITREERESULT=&#34;0&#34; and PBITVAL=&#34;1&#34;, then the state machine 101 transitions to the &#34;I --  am --  in&#34; state. If the state machine 101 is in the &#34;uncertain&#34; state and ITREERESULT=&#34;1&#34;, then it transitions to the &#34;I --  am --  out&#34; state and ceases to participate further in the arbitration round. If the end of the countdown occurs (PBITINDEX=-1) and ITREERESULT is &#34;0&#34;, the state machine 101 transitions to the &#34;I --  won&#34; state. 
     Upon returning to the &#34;I --  am --  out&#34; state, the machine 101 sets ITREE --  ENABLE 105 and UTREE --  ENABLE 106 to &#34;0&#34;, so as not to disturb the on-going arbitration round. However, if PBITINDEX=-1, arbitration has finished. If a new interrupt request occurs and the SRN did not take part in the current on-going arbitration round, then the state machine 101 sets UTREE --  ENABLE 106 to &#34;1&#34;, permitting REQFLAG to propagate to UTREE 76; otherwise, it sets UTREE --  ENABLE 106 to &#34;0&#34;. 
     If the state machine 101 is in the &#34;uncertain&#34; state and ITREERESULT=&#34;0&#34; and PBITVAL=&#34;0&#34;, the state machine 101 stays in the &#34;uncertain&#34; state. 
     At the end of the countdown (PBITINDEX=-1), if the state machine 101 is in the &#34;I --  am --  in&#34; state at this time, the state machine 101 transitions to the &#34;I --  won&#34; state. If ITREERESULT is &#34;0&#34;, the state machine 101 stays in the &#34;I --  won&#34; state until the ICU 38 acknowledges the arbitration round. The ICU acknowledges the completion of the arbitration round by asserting &#34;1&#34; on ITREERESULT. When in the &#34;I --  won&#34; state, the state machine 101 sets ITREE --  ENABLE 105 to &#34;0&#34; and UTREE --  ENABLE 106 to &#34;0&#34;. This disables the AND-gates 103, 104 so they do not disturb any new arbitration requests. In the &#34;I --  won&#34; state, when ITREERESULT is &#34;1&#34;, the state machine transitions to the &#34;acknowledge&#34; state and clears the request flag 102 (CLRREQFLAG=&#34;1&#34;). The state machine can remain in the &#34;acknowledge&#34; state for one-clock period before transitioning to the &#34;I --  am --  out&#34; state. 
     After the arbitration round, one SRN will be in the &#34;I --  won&#34; state, but it will generally take some time before the shared resource 50 enters the corresponding interrupt service routine. This event is signalled to the winning SRN by setting ITREERESULT to=&#34;1&#34;, which causes the winning SRN to enter the &#34;acknowledge&#34; state and to clear its interrupt request flag 102. 
     If no SRN has an interrupt request pending, it is not necessary to perform arbitration rounds, so the access control system can be shut down or put in a sleep mode to save power. 
     After completion of an arbitration, it can take time until the interrupt request is acknowledged by the shared resource 50. In the meantime, there could be a new higher priority interrupt request, which was not considered in the last arbitration round. It may be advantageous to signal to the shared resource 50 that a new interrupt occurred, which did not participate in the last arbitration round. Therefore, at the end of an arbitration round, each SRN drives its request flag to the ITREE 75, permitting the ICU 38 to determine whether a new interrupt has arrived.