US5265257A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fast arbiter having easy scaling for large numbers of requesters, large numbers of resource types with multiple instances of each type, and selectable queuing disciplines
Assignee: Enterasys Networks Inc
•
Filing: 1990-06-22
•
Granted: 1993-11-23
•
Expires: 2010-06-22
Abstract
Abstract A fast arbiter for handling a large number of types of resources with multiple instances of each type of resource is provided. During a first cycle a request logic circuit broadcasts a request for a preselected type of resource onto a broadcast medium. During a second cycle a grant logic circuit broadcasts a queue position onto the broadcast medium for the preselected type of resource. Also, during the second cycle the request logic circuit stores the queue position. After an asynchronous wait for an instance of the requested type of resource to become free, a third cycle begins wherein the first grant logic circuit broadcasts an indication that a free instance of the preselected type of resource is available. During a fourth cycle the requester is granted access to the free instance of the preselected type of resource.
Inventors
- 👤 Robert J. Simcoe
- 👤 Robert E. Thomas
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 08:31
CPC Classifications
G; G06; G06F; G06F13/00; G06F13/14; G06F13/36; G06F13/362
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
336 words
Apparatus for arbitrating access among a plurality of requesters and a plurality of types of resources, each said type of resource having at least one instance, comprising: a request logic circuit coupled to each said requester, thereby forming a plurality of said request logic circuits; a grant logic circuit coupled to each said instance of said plurality of types of resources, thereby forming a plurality of said grant logic circuits; a broadcast medium for transferring information among said plurality of request logic circuits and said plurality of grant logic circuits; means, responsive to a selected one of said requesters desiring to use a preselected type of resource, for said request logic circuit coupled to said selected requester to broadcast a request onto said broadcast medium for said preselected type of resource; means, responsive to said broadcast of said request, for a first grant logic circuit to broadcast queue position information on said broadcast medium for said preselected type of resource, said queue position information for said preselected type of resource is hereinafter referred to as a first queue position information; means, responsive to said broadcast of said first queue position information, for said request logic circuit coupled to said selected requester to store said first queue position information, said stored queue position information hereinafter referred to as a second queue position information; means, responsive to an instance of said preselected type of resource becoming free and prepared to serve a requester, for a second grant logic circuit to broadcast on said broadcast medium an indication that a free instance of said preselected type of resource is prepared to serve a requester, said indication that a free instance of said preselected type of resource is prepared to serve a requester is hereinafter referred to as a third queue position information; means, responsive to said second queue position information and responsive to said third queue position information, for granting access to said selected one of said requesters to use said free instance of said preselected type of resource.
Claim 2
Dependent Claim
336 words
Apparatus for arbitrating access among a plurality of requesters and a plurality of types of resources, each said type of resource having at least one instance, comprising: a request logic circuit coupled to each said requester, thereby forming a plurality of said request logic circuits; a grant logic circuit coupled to each said instance of said plurality of types of resources, thereby forming a plurality of said grant logic circuits; a broadcast medium for transferring information among said plurality of request logic circuits and said plurality of grant logic circuits; means, responsive to a selected one of said requesters desiring to use a preselected type of resource, for said request logic circuit coupled to said selected requester to broadcast a request onto said broadcast medium for said preselected type of resource; means, responsive to said broadcast of said request, for a first grant logic circuit to broadcast queue position information on said broadcast medium for said preselected type of resource, said queue position information for said preselected type of resource is hereinafter referred to as a first queue position information; means, responsive to said broadcast of said first queue position information, for said request logic circuit coupled to said selected requester to store said first queue position information, said stored queue position information hereinafter referred to as a second queue position information; means, responsive to an instance of said preselected type of resource becoming free and prepared to serve a requester, for a second grant logic circuit to broadcast on said broadcast medium an indication that a free instance of said preselected type of resource is prepared to serve a requester, said indication that a free instance of said preselected type of resource is prepared to serve a requester is hereinafter referred to as a third queue position information; means, responsive to said second queue position information and responsive to said third queue position information, for granting access to said selected one of said requesters to use said free instance of said preselected type of resource.
Claim 3
Dependent Claim
62 words
The apparatus as in claim 1 further comprising: said queue position information further comprises a ticket number for said preselected resource; said means for granting access to said selected one of said requesters to use said free instance of said preselected type of resource grants said access in response to said second queue position information corresponding to said third queue position information.
Claim 4
Dependent Claim
44 words
The apparatus as in claim 2 wherein said corresponding is that said second queue position information equals said third queue position information, whereby a stored ticket number of said second queue position information equals a broadcast ticket number of said third queue position information.
Claim 5
Dependent Claim
110 words
T apparatus as in claim 1 further comprising: said first queue position information is a queue position for a next customer and said third queue position information is an indication of the type of resource having a free instance; said means for granting access to said selected one of said requesters to use said preselected type of resource grants said access in response to said request logic circuit coupled to said selected one of said requesters counting said third queue position information indicating that an instance of said preselected type of resource has become free, and in response to a result of said counting corresponding to said second queue position.
Claim 6
Dependent Claim
43 words
The apparatus as in claim 4 further comprising: said counting by said means for granting access is done by decrementing said second queue position information; said access is granted when a decremented value of said second queue position information equals a predetermined number.
Claim 7
Dependent Claim
12 words
The apparatus as in claim 5 wherein said predetermined number is zero.
Claim 8
Dependent Claim
39 words
The apparatus as in claim 1 wherein said queue position information is a number, and said numbers are issued substantially in serial ascending order, whereby access is granted to said requesters in a first in first out queuing discipline.
Claim 9
Dependent Claim
55 words
The apparatus as in claim 1 wherein said second queue position information is incremented by said request logic circuit in response to a broadcast on said broadcast medium of a new queue position information for said preselected type of resource, whereby access is granted to said requesters in a last in first out queuing discipline.
Claim 10
Dependent Claim
22 words
The apparatus in claim 1 further comprising: means for selecting said queue position information in order to make a desired queuing discipline.
Claim 11
Dependent Claim
42 words
The apparatus as in claim 1 further comprising: said request broadcast by said selected one of said requesters desiring to use a preselected type of resource has a priority information component, whereby said requesters are serviced on a priority basis queuing discipline.
Claim 12
Dependent Claim
60 words
The apparatus as in claim 1 further comprising: means for designating one grant logic circuit, of those grant logic circuits coupled to instances of said preselected type of resource, as said first grant logic circuit to respond to said request for said preselected type of resource, said first grant logic circuit hereinafter referred to as said designated grant logic circuit.
Claim 13
Dependent Claim
59 words
The apparatus as in claim 11 further comprising: means for at least one grant logic circuit, of those grant logic circuits coupled to instances of said preselected type of resource and not selected as said designated grant logic circuit, to monitor operation of said apparatus and to inform said apparatus in the event that said monitoring detects an error.
Claim 14
Dependent Claim
39 words
The apparatus as in claim 1 further comprising: a subarbiter to arbitrate access to said broadcast medium by said plurality of request logic circuits and said plurality of grant logic circuits, whereby broadcasting on said broadcast medium is facilitated.
Claim 15
Dependent Claim
41 words
The apparatus as in claim 13 wherein said subarbiter selects a free instance of said type of resource in the event that more that one instance of said type of resource is available to serve said selected one of said requesters.
Claim 16
Dependent Claim
24 words
The apparatus as in claim 1 wherein said second grant logic circuit is associated with said free instance of said preselected type of resource.
Claim 17
Dependent Claim
46 words
The apparatus as in claim 1 fur comprising: means for preventing said broadcast of said third queue position information indicating that an instance of a particular type of resource is free in the event that there is no pending request for said particular type of resource.
Claim 18
Dependent Claim
39 words
The apparatus as in claim 1 further comprising: means for maintaining more than one queue for access to a particular said type of resource and for servicing different of said more than one queue on a priority queuing discipline.
Claim 19
Dependent Claim
35 words
The apparatus as in claim 1 wherein said means for granting access to said selected one of said requesters to use said free instance of said preselected type of resource further comprises an access path.
Claim 20
Dependent Claim
15 words
The apparatus as in claim 18 wherein said access path further comprises a crossbar switch.
Claim 21
Dependent Claim
17 words
The apparatus as in claim 18 wherein said access path further comprises at least one shared bus.
Claim 22
Dependent Claim
20 words
The apparatus as in claim 20 wherein said at least one shared bus further comprises a plurality of shared buses.
Claim 23
Dependent Claim
18 words
The apparatus as in claim 18 wherein said access path further comprises a multiplexer and a common bus.
Claim 24
Dependent Claim
17 words
The apparatus as in claim 22 wherein said common bus further comprises an ethernet local area network.
Claim 25
Dependent Claim
39 words
The apparatus as in claim 1 further comprising: said resources further comprises a plurality of central processor units in a multiprocessor computer system and said access path further comprises a backplane bus for said plurality of central processor units.
Claim 26
Dependent Claim
30 words
The apparatus as in claim 1 further comprising: both said requesters and said resources further comprise communications circuits, and said access path further comprises means for interconnecting said communications circuits.
Claim 27
Dependent Claim
19 words
The apparatus as in claim 25 wherein said means for interconnecting said communications circuits further comprises a crossbar switch.
Claim 28
Dependent Claim
14 words
The apparatus as in claim 25 wherein said communications circuits further comprise telephone circuits.
Claim 29
Dependent Claim
36 words
The apparatus as in claim 25 wherein said types of resources further comprise hunt groups of said communications circuits, and said instances of a type of resource further comprise individual communications circuits of said hunt groups.
Claim 30
Dependent Claim
16 words
The apparatus as in claim 1 wherein said broadcast medium further comprises at least one bus.
Claim 31
Dependent Claim
19 words
The apparatus as in claim 29 further comprising a subarbiter to arbitrate access to said at least one bus.
Claim 32
Dependent Claim
48 words
The apparatus as in claim 29 further comprising: said at least one bus further comprises two buses, said two buses being a request bus and a grant bus; a first subarbiter for granting access to said request bus; a second subarbiter for granting access to said grant bus.
Claim 33
Dependent Claim
18 words
The apparatus as in claim 29 wherein said at least one bus further comprises an ethernet shared bus.
Claim 34
Dependent Claim
288 words
Apparatus for arbitrating access among a plurality of requesters and a plurality of resources, comprising: a request logic circuit coupled to each said requester, thereby forming a plurality of said request logic circuits; a grant logic circuit coupled to each said resource, thereby forming a plurality of said grant logic circuits; a broadcast medium for transferring information among said plurality of request logic circuits and said plurality of grant logic circuits; means, responsive to a selected one of said requesters desiring to use a preselected resource, for said request logic circuit coupled to said selected requester to broadcast a request onto said broadcast medium for said preselected type of resource; means, responsive to said broadcast of said request, for a first grant logic circuit to broadcast queue position information on said broadcast medium for said preselected resource, said queue position information for said preselected resource is hereinafter referred to as a first queue position information; means, responsive to said broadcast of said first queue position information, for said request logic circuit coupled to said selected requester to store said first queue position information, said stored queue position information hereinafter referred to as a second queue position information; means, responsive to said preselected resource becoming free and prepared to serve a requester, for a second grant logic circuit to broadcast on said broadcast medium an indication that said preselected resource is prepared to serve a requester, said indication that said preselected resource is prepared to serve a requester is hereinafter refered to as a third queue position information; means, responsive to said second queue position information and responsive to said third queue position information, for granting access to said selected one of said requesters to use said preselected resource.
Claim 35
Dependent Claim
288 words
Apparatus for arbitrating access among a plurality of requesters and a plurality of resources, comprising: a request logic circuit coupled to each said requester, thereby forming a plurality of said request logic circuits; a grant logic circuit coupled to each said resource, thereby forming a plurality of said grant logic circuits; a broadcast medium for transferring information among said plurality of request logic circuits and said plurality of grant logic circuits; means, responsive to a selected one of said requesters desiring to use a preselected resource, for said request logic circuit coupled to said selected requester to broadcast a request onto said broadcast medium for said preselected type of resource; means, responsive to said broadcast of said request, for a first grant logic circuit to broadcast queue position information on said broadcast medium for said preselected resource, said queue position information for said preselected resource is hereinafter referred to as a first queue position information; means, responsive to said broadcast of said first queue position information, for said request logic circuit coupled to said selected requester to store said first queue position information, said stored queue position information hereinafter referred to as a second queue position information; means, responsive to said preselected resource becoming free and prepared to serve a requester, for a second grant logic circuit to broadcast on said broadcast medium an indication that said preselected resource is prepared to serve a requester, said indication that said preselected resource is prepared to serve a requester is hereinafter refered to as a third queue position information; means, responsive to said second queue position information and responsive to said third queue position information, for granting access to said selected one of said requesters to use said preselected resource.
References Cited (Backward Citations)
US4648029A
Cited
US5142682A
Cited
US4947368A
Cited
US4924380A
Cited
US4979099A
Cited
US4953081A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-11-22 | 1997-05-24 | 1997-11-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-11-22 | 2001-05-24 | 2001-11-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-11-22 | 2005-05-24 | 2005-11-23 | $7700.00 | Window Closed / Lapsed |