Distributed arbitration apparatus and method for shared bus

• US 4,920,486 A
• Filed: 11/23/1987
• Issued: 04/24/1990
• Est. Priority Date: 11/23/1987
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Nielsen, Michael J. K.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Ray, Gopal C.
• Application Number:
  US07/123,382
• Time in Patent Office: 883 Days
• Field of Search: 364/200 MS File, 364/200, 364/900 MS File
• US Class Current: 710/111
• CPC Class Codes: G06F 13/378 using a parallel poll method

Abstract

Each user of an intercommunicastion bus is associated with a distinct channel of an arbitration bus and maintains a priority record indicating its current priority status against each other user. During a contention interval each user then seeking to use the intercommunication bus bids for use of it by transmitting a bus request signal and makes an analysis of the signals to ascertain if it has a dominating priority for initiating a transaction on the bus, and access is granted accordingly. During the use-signal interval a user then using the intercommunication bus transmits an in-use signal used to up-date priority records with the effect of giving the last using user lowest priority. For transactions which require a response from a user other than the one initiating the transaction, a second round of bidding is conducted to determine whether any user is qualified to respond and if so which will be enabled to do so. When the response bidding shows no bidders the system immediately initiates bidding for a new transaction.

Claims

1. In a computer system having a multiplicity of subunits connected to a shared bus, distributed bus arbitration apparatus comprising:

an arbitration bus with means for carrying a multiplicity of substantially simultaneous bus request signals; and

a multiplicity of arbitration means, each coupled to the shared bus, the arbitration bus and a corresponding one of the subunits, for determining the relative priorities by which said subunits shall access said shared bus;

each said arbitration means determining only whether said subunit coupled to said arbitration means is to be granted access to said shared bus;

each said arbitration means including;

status means for storing status signals denoting which ones of said subunits have higher priority and which ones have lower priority than the subunit corresponding to said arbitration means;

bus requesting means coupled to said arbitration bus for asserting a bus request signal on said arbitration bus; and

access control means, coupled to said arbitration bus and said status means, for receiving bus request signals asserted on said arbitration bus and for granting said corresponding subunit access to said shared bus only when said bus requesting means has asserted a bus request signal and none of the received bus request signals were asserted by the arbitration means of subunits denoted by said status means as having higher priority than said corresponding subunit;

wherein said multiplicity of arbitration means simultaneously arbitrate access to the shared bus.

2. The distributed bus arbitration apparatus of claim 1, said arbitration means further including:

use asserting means coupled to said arbitration bus for asserting a use signal on said arbitration bus when said access control means grants access to the corresponding subunit; and

status updating means coupled to said status means for storing a status signal denoting low priority for each subunit granted access to said shared bus;

whereby said multiplicity of arbitration means maintain distinct but consistent status signals in their respective status means.

3. The distributed bus arbitration apparatus of claim 1, said arbitration means further including:

use asserting means coupled to said arbitration bus for asserting a use signal on said arbitration bus when said access control means grants access to the corresponding subunit; and

status updating means coupled to said status means for storing a status signal denoting low priority for each subunit granted access to said shared bus, and for storing high priority status signals for all other subunits when said corresponding subunit is granted access to said shared bus.

4. In a computer system having a multiplicity of subunits connected to a shared bus, distributed arbitration apparatus comprising:

an arbitration bus having a separate channel for each said subunit; and

a multiplicity of arbitration means, each coupled to the shared bus, the arbitration bus and to a corresponding one of the subunits, for determining the priority by which said subunits shall access said shared bus;

each said arbitration means determining only whether said subunit coupled to said arbitration means is to be granted access to said shared bus;

each said arbitration means including;

status means for storing a multiplicity of status signals denoting which of said subunits have priority over the subunit corresponding to said arbitration means;

bus requesting means coupled to said arbitration bus for asserting a bus request signal on the channel of said arbitration bus corresponding to said arbitration means; and

access control means, coupled to said arbitration bus and said status means, for comparing bus request signals asserted on the channels of said arbitration bus with corresponding ones of said status signals stored in said status means, and for granting the corresponding subunit access to said shared bus only if none of said bus request signals correspond to status signals denoting subunits having higher priority than said corresponding subunit.

5. The distributed bus arbitration apparatus of claim 4, said arbitration means further including:

use asserting means coupled to said arbitration bus for asserting a use signal on the channel of said arbitration bus corresponding to said arbitration means when said access control means grants access to the corresponding subunit; and

status updating means, coupled to said status means and said arbitration bus, for storing a low priority status signal for each subunit granted access to said shared bus, and for storing high priority status signals for all other subunits when said corresponding subunit is granted access to said shared bus.

6. In a computer system having a multiplicity of subunits connected to a shared bus, arbitration apparatus comprising:

an arbitration bus having a separate channel for each other said subunit; and

a multiplicity of arbitration means, each coupled to the shared bus, the abitration bus and to a corresponding one of the subunits, for determining the priority by which said subunits shall access said shared bus;

each said arbitration means determining only whether said subunit coupled to said arbitration means is to be granted access to said shared bus;

each said arbitration means including;

status means for storing status signals denoting which ones of said subunits have higher priority and which ones have lower priority than the subunit corresponding to said arbitration means;

bus requesting means coupled to said arbitration bus for asserting a bus request signal on the channel of said arbitration bus corresponding to said arbitration means; and

access control means, coupled to said arbitration bus and said status means, for receiving bus request signals asserted on said arbitration bus and for granting the corresponding subunit access to said shared bus only when said bus requesting means has asserted a bus request signal and none of said received bus request signals correspond to subunits denoted by said status means as having higher priority than said corresponding subunit.

7. In a computer system having a multiplicity of subunits interconnected by an arbitration bus with means for carrying a multiplicity of substantially simultaneous bus request signals, a method of arbitrating access by said subunits to a shared bus, the steps of the method comprising performing, substantially simultaneously, the following steps at each subunit:

storing a distinct set of status signals denoting which ones of said subunits have higher priority and which ones have lower priority than said subunit;

asserting a bus request signal on said arbitration bus when said subunit needs access to said shared bus;

comparing said bus request signals asserted on said arbitration bus with said status signals for said subunit; and

granting said subunit access to said shared bus only when said subunit has asserted a bus request signal and none of said bus request signals correspond to subunits denoted by said status signals as having higher priority than said subunit;

whereby each subunit simultaneously arbitrates access to the shared bus.

8. The bus arbitration method of claim 7,

said granting step further including the step of asserting a use signal on said arbitration bus when said subunit is granted access to said shared bus;

and

said storing step further including the steps of storing a status signal denoting low priority for each subunit granted access to said shared bus, and resetting said status signals to a predefined state when said subunit is granted access to said shared bus;

whereby said multiplicity of subunits maintain distinct but consistent sets of status signals.

9. The bus arbitration method of claim 7,

said granting step further including the step of asserting a use signal on said arbitration bus when said subunit is granted access to said shared bus;

and

said storing step further including the steps of storing a status signal denoting low priority for each subunit granted access to said shared bus, and storing high priority status signals for all other subunits when said corresponding subunit is granted access to said shared bus.

10. In a computer system having a multiplicity of subunits interconnected by an arbitration bus with means for carrying a multiplicity of substantially simultaneous bus request signals, a method of arbitrating access by said subunits to a shared bus, the steps of the method comprising:

storing, for each subunit, a distinct set of status signals denoting which ones of said subunits have higher priority and which ones have lower priority than said subunit;

asserting on said arbitration bus a separate bus request signal for each of those subunits which need access to said shared bus; and

substantially simultaneously, at each one of said subunits which asserted a bus request signal, comparing said bus request signals asserted on said arbitration bus with said stored status signals for said subunit and granting said subunit access to said shared bus only if none of said bus request signals correspond to subunits denoted by said stored status signals as having higher priority than said subunit;

whereby each subunit simultaneously arbitrates access to the shared bus.

11. The bus arbitration method of claim 10,

said granting step further including the step of asserting a use signal on said arbitration bus when said subunit is granted access to said shared bus;

and

said storing step further including the steps of storing a status signal denoting low priority for each subunit granted access to said shared bus, and storing high priority status signals for all other subunits when said corresponding subunit is granted access to said shared bus.