US5519837A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pseudo-round-robin arbitration for a shared resource system providing fairness and high throughput
Assignee: International Business Machines Corp
•
Filing: 1994-07-29
•
Granted: 1996-05-21
•
Expires: 2014-07-29
Abstract
Abstract Systems and methods for arbitrating access to shared resources in a computer system, the systems and methods providing fairness, high throughput, timely response and area efficient implementation. In one form, the pseudo-round-robin arbitration system is composed of a binary tree architecture of round-robin cells. The requests are combined in various groupings and simultaneously provided to all the cells in the multiple levels of the hierarchy. The grant signals are generated from the lowest level of cells. The hierarchy defines that the outputs of the higher level cells serve as enablements to successively related lower level cells in progression by level. A preferred cell for the binary version of the pseudo-round-robin tree architecture is composed of two OR type gates and two AND type gates, the latter gates receiving the enablement signal from the cell in the next higher level of the tree.
Inventors
- 👤 Chinh N. Tran
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 12:10
CPC Classifications
G; G06; G06F; G06F13/00; G06F13/14; G06F13/36; G06F13/362; G06F13/364
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
80 words
In a computer system having multiple access requesters and shared resources, an arbiter apparatus, comprising: a multiplicity of arbiter cells having inputs and outputs connected in a hierarchy of multiple levels; means for directly receiving and arbitrating the same access request signals in arbiter cells at multiple levels in the hierarchy; and means for outputs from arbiter cells at a higher level in the hierarchy to directly control outputs from arbiter cells at a successively lower level in the hierarchy.
Claim 2
Dependent Claim
80 words
In a computer system having multiple access requesters and shared resources, an arbiter apparatus, comprising: a multiplicity of arbiter cells having inputs and outputs connected in a hierarchy of multiple levels; means for directly receiving and arbitrating the same access request signals in arbiter cells at multiple levels in the hierarchy; and means for outputs from arbiter cells at a higher level in the hierarchy to directly control outputs from arbiter cells at a successively lower level in the hierarchy.
Claim 3
Dependent Claim
21 words
The apparatus recited in claim 1, wherein the access request signals are distributed concurrently to receiving arbiter cells for concurrent evaluation.
Claim 4
Dependent Claim
24 words
The apparatus recited in claim 2, wherein the arbiter cells are round-robin arbiters responsive to a token when multiple access requests are received concurrently.
Claim 5
Dependent Claim
22 words
The apparatus recited in claim 3, wherein the direct control of arbiter cell outputs involves a disablement of an arbiter cell output.
Claim 6
Dependent Claim
24 words
The apparatus recited in claim 1, where the arbiter cells are round-robin arbiters responsive to a token when multiple access requests are received concurrently.
Claim 7
Dependent Claim
21 words
The apparatus recited in claim 3, wherein the hierarchy of arbiter cells is in the form of a binary tree architecture.
Claim 8
Dependent Claim
21 words
The apparatus recited in claim 5, wherein the hierarchy of arbiter cells is in the form of a binary tree architecture.
Claim 9
Dependent Claim
79 words
An arbiter cell, comprising: cell inputs for receiving first and second access request signals, a token status signal and enable state signal; first circuitry generating a first output in response to the second access request signal, the token status signal, the first access request signal, and the enable state signal; and second circuitry generating a second output in response to the first access request signal, the token status signal, the second access request signal, and the enable state signal.
Claim 10
Dependent Claim
79 words
An arbiter cell, comprising: cell inputs for receiving first and second access request signals, a token status signal and enable state signal; first circuitry generating a first output in response to the second access request signal, the token status signal, the first access request signal, and the enable state signal; and second circuitry generating a second output in response to the first access request signal, the token status signal, the second access request signal, and the enable state signal.
Claim 11
Dependent Claim
15 words
The cell recited in claim 8, wherein the first and second circuitry includes AND logic.
Claim 12
Dependent Claim
24 words
The cell recited in claim 9, wherein the combination of access request signals with token status signals is accomplished in circuitry having OR logic.
Claim 13
Dependent Claim
97 words
A computer system, comprising: at least one processor; at least one memory; at least one I/O unit; a crossbar switch interconnecting at least one processor, at least one memory and at least one I/O unit; a pseudo-round-robin arbitration means controlling the crossbar switch, the arbitration means comprising multiple levels of hierarchically connected arbiter cells, directly receiving and arbitrating the same access request signals in arbiter cells at multiple levels in the hierarchy, and having arbiter cells at a higher level in the hierarchy directly control outputs from arbiter cells at a successively lower level in the hierarchy.
Claim 14
Dependent Claim
97 words
A computer system, comprising: at least one processor; at least one memory; at least one I/O unit; a crossbar switch interconnecting at least one processor, at least one memory and at least one I/O unit; a pseudo-round-robin arbitration means controlling the crossbar switch, the arbitration means comprising multiple levels of hierarchically connected arbiter cells, directly receiving and arbitrating the same access request signals in arbiter cells at multiple levels in the hierarchy, and having arbiter cells at a higher level in the hierarchy directly control outputs from arbiter cells at a successively lower level in the hierarchy.
Claim 15
Dependent Claim
21 words
The system recited in claim 11, wherein the direct control of arbiter cells involves a disablement of an arbiter cell output.
Claim 16
Independent Claim
83 words
A method of arbitrating multiple access requests involving shared resources using multiple arbiter cells configured in a multiple level hierarchy, comprising the steps of: arbitrating among the multiple access request signals in arbiter cells at a first level in the hierarchy; concurrently arbitrating among the multiple access request signals in arbiter cells at a second level, lower than the first level, of the hierarchy; and directly controlling the outputs of second level arbiter cells in response to outputs of first level arbiter cells.
Claim 17
Independent Claim
83 words
A method of arbitrating multiple access requests involving shared resources using multiple arbiter cells configured in a multiple level hierarchy, comprising the steps of: arbitrating among the multiple access request signals in arbiter cells at a first level in the hierarchy; concurrently arbitrating among the multiple access request signals in arbiter cells at a second level, lower than the first level, of the hierarchy; and directly controlling the outputs of second level arbiter cells in response to outputs of first level arbiter cells.
Claim 18
Dependent Claim
24 words
The method recited in claim 13, wherein the arbiter cells are round-robin arbiters responsive to a token when multiple access requests are received concurrently.
Claim 19
Dependent Claim
19 words
The method recited in claim 14, wherein the multiple level hierarchy of arbiter cell is a binary tree architecture.
References Cited (Backward Citations)
US4470114A
Cited
US4560985A
Cited
US4560985B1
Cited
US5396491A
Cited
US4969120A
Cited
US5072363A
Cited
US5265215A
Cited
US5280591A
Cited
US5175743A
Cited
US5175744A
Cited
US5274785A
Cited
US5241632A
Cited
US5357512A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-05-21 | 1999-11-20 | 2000-05-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-05-21 | 2003-11-20 | 2004-05-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-05-21 | 2007-11-20 | 2008-05-21 | $7700.00 | Window Closed / Lapsed |