US5168570A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for a multiple request toggling priority system
Assignee: Silicon Graphics International Corp
•
Filing: 1990-06-11
•
Granted: 1992-12-01
•
Expires: 2010-06-11
Abstract
Abstract A multiple request toggling (MRT) arbitration system for prioritizing requests to a set of shared resources by multiple requestors, especially requests by multiple processors to shared resources in a multiprocessor system. The MRT arbitration system assigns priority to multiple requests on a first-come, first-serve basis with the priority of multiple simultaneous requests being resolved through an arbitration network.
Inventors
- 👤 Roger E. Eckert
- 👤 Andrew E. Phelps
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 09:13
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/43; G06F8/433; G06F13/00; G06F13/14; G06F13/36; G06F13/362; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; G06F15/17381; G06F15/76; G06F15/80; G06F15/8053; G06F15/8076; G06F15/8092; G06F8/45; G06F9/00; G06F9/06; G06F9/30; G06F9/30003; G06F9/30007; G06F9/30021; G06F9/30094; G06F9/30145; G06F9/30149; G06F9/38; G06F9/3802; G06F9/3804; G06F9/3824; G06F9/3834; G06F9/3836; G06F9/3838; G06F9/3854; G06F9/3856
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
322 words
A multiple request arbitration system for determining priority among a number N of requestors to a common shared resource where N is an integer number greater than 2, the arbitration system comprising: state storage means for storing at least (N*(N-1))/2 relative priority state indicators, each priority state indicator dynamically representing the priority for access to the common shared resource between a unique pair of requestors over a plurality of arbitration periods such that the relative priority of every unique combination of pairs of requestors is represented by the relative priority state indicators for each arbitration period; and for each requestor: input means operably connected to the state storage means for presenting a request from the requestor to update all of the relative priority state indicators in the state storage means that are associated with the requestor once during an arbitration period; and output means responsive to all of the relative priority state indicators in the state storage means that are associated with the requestor for signaling the shared resource that the requestor has obtained grant to the shared resource in response to the request for this arbitration period when all of the relative priority state indicators that are associated with the requestor indicate that the requestor has priority for access to the common shared resource, such that the state storage means determines the relative priority on a first-come, first-serve toggling basis by setting the relative priority state indicators for each requestor to a lowest priority state on each arbitration period of the arbitration system unless the requestor has a valid request which was not granted on the previous arbitration period, and, in the event that both requestors associated with a relative priority state indicator are attempting to set that relative priority state indicator to the lowest priority state, toggling the relative priority state indicator between the lowest priority state for each of the requestors on successive arbitration periods of the arbitration system.
Claim 2
Dependent Claim
322 words
A multiple request arbitration system for determining priority among a number N of requestors to a common shared resource where N is an integer number greater than 2, the arbitration system comprising: state storage means for storing at least (N*(N-1))/2 relative priority state indicators, each priority state indicator dynamically representing the priority for access to the common shared resource between a unique pair of requestors over a plurality of arbitration periods such that the relative priority of every unique combination of pairs of requestors is represented by the relative priority state indicators for each arbitration period; and for each requestor: input means operably connected to the state storage means for presenting a request from the requestor to update all of the relative priority state indicators in the state storage means that are associated with the requestor once during an arbitration period; and output means responsive to all of the relative priority state indicators in the state storage means that are associated with the requestor for signaling the shared resource that the requestor has obtained grant to the shared resource in response to the request for this arbitration period when all of the relative priority state indicators that are associated with the requestor indicate that the requestor has priority for access to the common shared resource, such that the state storage means determines the relative priority on a first-come, first-serve toggling basis by setting the relative priority state indicators for each requestor to a lowest priority state on each arbitration period of the arbitration system unless the requestor has a valid request which was not granted on the previous arbitration period, and, in the event that both requestors associated with a relative priority state indicator are attempting to set that relative priority state indicator to the lowest priority state, toggling the relative priority state indicator between the lowest priority state for each of the requestors on successive arbitration periods of the arbitration system.
Claim 3
Dependent Claim
26 words
The multiple request arbitration system of claim 1 wherein the relative priority state indicators are stored as a single bit for each unique pair of requestors.
Claim 4
Dependent Claim
250 words
A multiple request arbitration system for determining priority among a number N of requestors to a number M of shared resources on the basis of requests issued by the N requestors indicating which of the M shared resources is requested, the arbitration system comprising: state storage means for storing a plurality of relative priority state indicators, one for each unique pair of requestors for dynamically representing the relative priority state of the requests for that unique pair of requestors over a plurality of arbitration periods; input means operably connected to the state storage means for receiving the next request to be processed for each of the N requestors and for updating the status of the all of the relative priority indicators associated with each requestor once during an arbitration period; M inhibit matrix means operably connected to the state storage means, each inhibit matrix means operably connected to a unique shared resource for determining in response to the relative priority state indicators which request will be granted access to the shared resource associated with the inhibit matrix means for that arbitration period and for generating a resource grant signal to the shared resource; and N destination resource decoder means, each destination resource decoder means operably connected to an associated requestor and to each of the M inhibit matrix means for enabling the inhibit matrix means associated with the shared resource indicated by the request to grant access to the shared resource in response to the request for that arbitration period.
Claim 5
Dependent Claim
250 words
A multiple request arbitration system for determining priority among a number N of requestors to a number M of shared resources on the basis of requests issued by the N requestors indicating which of the M shared resources is requested, the arbitration system comprising: state storage means for storing a plurality of relative priority state indicators, one for each unique pair of requestors for dynamically representing the relative priority state of the requests for that unique pair of requestors over a plurality of arbitration periods; input means operably connected to the state storage means for receiving the next request to be processed for each of the N requestors and for updating the status of the all of the relative priority indicators associated with each requestor once during an arbitration period; M inhibit matrix means operably connected to the state storage means, each inhibit matrix means operably connected to a unique shared resource for determining in response to the relative priority state indicators which request will be granted access to the shared resource associated with the inhibit matrix means for that arbitration period and for generating a resource grant signal to the shared resource; and N destination resource decoder means, each destination resource decoder means operably connected to an associated requestor and to each of the M inhibit matrix means for enabling the inhibit matrix means associated with the shared resource indicated by the request to grant access to the shared resource in response to the request for that arbitration period.
Claim 6
Dependent Claim
38 words
The multiple request arbitration system of claim 3 wherein the relative priority state indicators are stored as a single bit for each unique pair of requestors and the number of relative priority state indicators is at least (N*(N-1))/2.
Claim 7
Dependent Claim
122 words
The multiple request arbitration system of claim 4 wherein the arbitration period is a clock cycle and the state storage means determines the relative priority on a first-come, first-serve toggling basis by setting the relative priority state indicators for each requestor to a lowest priority state on each clock cycle of the arbitration system unless the requestor has a valid request which was not granted on the previous clock cycle, and, in the event that both requestors associated with a relative priority state indicator are attempting to set that relative priority state indicator to the lowest priority state, toggling the relative priority state indicator between the lowest priority state for each of the requestors on successive clock cycles of the arbitration system.
Claim 8
Dependent Claim
90 words
The multiple request arbitration system of claim 3 wherein each inhibit matrix means comprises: N enable logic means, each enable logic means associated with a unique requestor for logically combining an enable signal produced by the destination resource decoder means for the requestor with each of the relative priority state indicators associated with that requestor; and N grant logic means, each grant logic means associated with a unique requestor for logically combining the results of all N of the enable logic means to produce a grant signal for that requestor.
Claim 9
Dependent Claim
46 words
The multiple request arbitration system of claim 6 wherein each enable logic means is comprised of N-1 AND gates and wherein each grant logic means is comprised of a multiplexor for combining the results of all N of the AND gates associated with a given requestor.
Claim 10
Dependent Claim
51 words
The multiple request arbitration system of claim 6 wherein the N destination resource decoder means further include qualification means for determining whether the request is a valid request based on whether the selected resource is available and for preventing the enable signal from being generated if the resource is not available.
Claim 11
Dependent Claim
63 words
The multiple request arbitration system of claim 3 further including feedback means operably connected to each inhibit matrix means and to the input means for setting the priority of the relative priority state indicators for a requestor to lowest priority after a request for the requestor has been granted by the inhibit matrix means associated with the shared resource indicated by the request.
Claim 12
Dependent Claim
54 words
The multiple request arbitration system of claim 3 further including destination grant means operably connected to each of the inhibit matrix means and to each requestor for distributing a grant signal back to a given requestor when a request has been granted between the given requestor and the shared resource indicated by the request.
Claim 13
Dependent Claim
292 words
A multiple request toggling arbitration system for determining priority among a number N of requestors to a number M of shared resources, the arbitration system comprising: N request queue means, each request queue means for temporarily storing one or more requests from an associated requestor, each request indicating which of the M shared resource is requested; state storage means for storing a plurality of relative priority state indicators, one for each unique pair of requestors for dynamically representing the relative priority state of the requests for that unique pair of requestors over a plurality of arbitration periods; update priority logic means operably connected to each of the request queue means and to the state storage means for receiving the next request to be processed for each requestor and for updating the status of the relative priority indicators associated with each requestor on each arbitration period in accordance with a toggling priority scheme; M inhibit matrix means, each inhibit matrix means operably connected to a unique shared resource for determining in response to the relative priority state indicators which request will be granted access to the shared resource associated with the inhibit matrix means for that arbitration period and for generating a resource grant signal to the shared resource; fanout means operably connected to the state storage means and to each of the inhibit matrix means for distributing the relative priority state indicators to each of the inhibit matrix means; and N destination resource decoder means, each destination resource decoder means operably connected to an associated requestor and to each of the M inhibit matrix means for enabling the inhibit matrix means associated with the shared resource indicated by the request to grant access to the shared resource in response to the request.
Claim 14
Dependent Claim
292 words
A multiple request toggling arbitration system for determining priority among a number N of requestors to a number M of shared resources, the arbitration system comprising: N request queue means, each request queue means for temporarily storing one or more requests from an associated requestor, each request indicating which of the M shared resource is requested; state storage means for storing a plurality of relative priority state indicators, one for each unique pair of requestors for dynamically representing the relative priority state of the requests for that unique pair of requestors over a plurality of arbitration periods; update priority logic means operably connected to each of the request queue means and to the state storage means for receiving the next request to be processed for each requestor and for updating the status of the relative priority indicators associated with each requestor on each arbitration period in accordance with a toggling priority scheme; M inhibit matrix means, each inhibit matrix means operably connected to a unique shared resource for determining in response to the relative priority state indicators which request will be granted access to the shared resource associated with the inhibit matrix means for that arbitration period and for generating a resource grant signal to the shared resource; fanout means operably connected to the state storage means and to each of the inhibit matrix means for distributing the relative priority state indicators to each of the inhibit matrix means; and N destination resource decoder means, each destination resource decoder means operably connected to an associated requestor and to each of the M inhibit matrix means for enabling the inhibit matrix means associated with the shared resource indicated by the request to grant access to the shared resource in response to the request.
Claim 15
Dependent Claim
38 words
The multiple request arbitration system of claim 11 wherein the relative priority state indicators are stored as a single bit for each unique pair of requestors and the number of relative priority state indicators is at least (N*(N-1))/2.
Claim 16
Dependent Claim
122 words
The multiple request arbitration system of claim 11 wherein the arbitration period is a clock cycle and the state storage means determines the relative priority on a first-come, first-serve toggling basis by setting the relative priority state indicators for each requestor to a lowest priority state on each clock cycle of the arbitration system unless the requestor has a valid request which was not granted on the previous clock cycle, and, in the event that both requestors associated with a relative priority state indicator are attempting to set that relative priority state indicator to the lowest priority state, toggling the relative priority state indicator between the lowest priority state for each of the requestors on successive clock cycles of the arbitration system.
Claim 17
Dependent Claim
52 words
The multiple request arbitration system of claim 13 wherein the update priority logic means comprises an update logic circuit for each requestor, the update logic circuit comprising a logical OR of the grant signal for the requestor with a request queue empty signal to produce a request update signal for the requestor.
Claim 18
Dependent Claim
180 words
The multiple request arbitration system of claim 14 wherein the state storage means for storing each relative state priority indicator comprises: a relative priority state cell comprising a flip-flop circuit having a negative state output and a positive state output, a data input, and a clock input connected to the clock cycle for the arbitration system; a first input circuit for receiving the request update signal from a first requestor of the unique pair of requestors represented by the relative state priority indicator and for combining the negative of the request update signal from the first requestor with the positive state output of the flip-flop circuit; a second input circuit for receiving the request update signal from a second requestor of the unique pair of requestors represented by the relative state priority indicator and for combining the request update signal from the second requestor with the negative state output of the flip-flop circuit; and a logical OR circuit operably connected to the output of the first and second input circuits and the data input of the relative priority state cell.
Claim 19
Dependent Claim
34 words
The multiple request arbitration system of claim 14 wherein the request queue empty signal is the negative of a request queue valid signal that is based upon whether the resource being requested is busy.
Claim 20
Dependent Claim
90 words
The multiple request arbitration system of claim 11 wherein each inhibit matrix means comprises: N enable logic means, each enable logic means associated with a unique requestor for logically combining an enable signal produced by the destination resource decoder means for the requestor with each of the relative priority state indicators associated with that requestor; and N grant logic means, each grant logic means associated with a unique requestor for logically combining the results of all N of the enable logic means to produce a grant signal for that requestor.
Claim 21
Dependent Claim
46 words
The multiple request arbitration system of claim 17 wherein each enable logic means is comprised of N-1 AND gates and wherein each grant logic means is comprised of a multiplexor for combining the results of all N of the AND gates associated with a given requestor.
Claim 22
Dependent Claim
51 words
The multiple request arbitration system of claim 17 wherein the N destination resource decoder means further include qualification means for determining whether the request is a valid request based on whether the selected resource is available and for preventing the enable signal from being generated if the resource is not available.
Claim 23
Dependent Claim
56 words
The multiple request arbitration system of claim 11 further comprising: N feedback means, each feedback means operably connected to each inhibit matrix means and to the update priority logic means for setting the priority of a requestor to lowest priority after a request for the requestor has been granted by one of the inhibit matrix means.
Claim 24
Dependent Claim
69 words
The multiple request arbitration system of claim 20 wherein each feedback means further including destination grant means operably connected to an associated request queue means for distributing a grant signal back to the requestor when a request has been granted between the given requestor and the shared resource indicated by the request and for presenting the next request in the request queue means to the update priority logic means.
Claim 25
Dependent Claim
53 words
The multiple request arbitration system of claim 11 further including output encoded means operably connected to each of the inhibit matrix means for receiving the grant signals indicating that a request has been granted between a given requestor and shared resource and for encoding the granted request for distribution to the shared resource.
Claim 26
Independent Claim
225 words
A method for determining priority among a number N of requestors to a shared resource in a logic system where N is the integer number greater than 2, the method comprising the steps of: providing a relative priority memory array for dynamically storing the relative priority of each unique pair of requestors as a single bit in the relative priority memory array having at least (N*(N-1))/2 bits of storage; for each arbitration period in the logic system: updating the relative priority memory array once in response to any valid requests from one or more of the requestors which have not been granted access by performing the following steps for each requestor: setting the singls bits in the relative priority memory array for the requestor to a lowest priority unless the requestor has a valid request which was not granted access on the previous arbitration period; and in the event that both requests associated with a single bit in the relative memory array ar attempting to set that bit to the lowest priority, toggling the bit between lowest priority for each of the requestors on successive arbitration period; determining which of the requests has the highest priority as indicated by the relative priority memory array for that arbitration period; and granting access from the requestor to the shared resource to the request having the highest priority.
Claim 27
Independent Claim
225 words
A method for determining priority among a number N of requestors to a shared resource in a logic system where N is the integer number greater than 2, the method comprising the steps of: providing a relative priority memory array for dynamically storing the relative priority of each unique pair of requestors as a single bit in the relative priority memory array having at least (N*(N-1))/2 bits of storage; for each arbitration period in the logic system: updating the relative priority memory array once in response to any valid requests from one or more of the requestors which have not been granted access by performing the following steps for each requestor: setting the singls bits in the relative priority memory array for the requestor to a lowest priority unless the requestor has a valid request which was not granted access on the previous arbitration period; and in the event that both requests associated with a single bit in the relative memory array ar attempting to set that bit to the lowest priority, toggling the bit between lowest priority for each of the requestors on successive arbitration period; determining which of the requests has the highest priority as indicated by the relative priority memory array for that arbitration period; and granting access from the requestor to the shared resource to the request having the highest priority.
Claim 28
Dependent Claim
56 words
The method of claim 23 wherein each of the requestors is provided with queue to hold multiple requests from the requestor to the shared resource and the step of updating the relative memory array comprises the step of: using the request at the head of each of the queues to update the relative priority memory array.
Claim 29
Independent Claim
170 words
A method for determining priority among a number N of requestors to a number M of shared resource in a logic system on the basis of requests issued by the N requestors indicating which of the M shared resources is requested, the method comprising the steps of: providing a relative priority memory array for dynamically storing the relative priority of each unique pair of requestors as a single bit for each unique pair of requestors and the number of bits is at least (N*N-1)/2; for each arbitration period in the logic system: updating the relative priority memory array in response to any valid requests from one or more of the requestors which have not been granted access; determining for each of the M shared resource which of the requests that are requesting each of that shared resource has the highest priority for that arbitration period as indicated by the relative priority memory array; and granting access from the requestor to the shared resource to the request having the highest priority.
Claim 30
Independent Claim
170 words
A method for determining priority among a number N of requestors to a number M of shared resource in a logic system on the basis of requests issued by the N requestors indicating which of the M shared resources is requested, the method comprising the steps of: providing a relative priority memory array for dynamically storing the relative priority of each unique pair of requestors as a single bit for each unique pair of requestors and the number of bits is at least (N*N-1)/2; for each arbitration period in the logic system: updating the relative priority memory array in response to any valid requests from one or more of the requestors which have not been granted access; determining for each of the M shared resource which of the requests that are requesting each of that shared resource has the highest priority for that arbitration period as indicated by the relative priority memory array; and granting access from the requestor to the shared resource to the request having the highest priority.
Claim 31
Dependent Claim
101 words
The method of claim 25 wherein the arbitration period is a clock cycle and the step of updating the relative memory array includes: for each requestor, setting the single bits in the relative priority memory array for the requestor to a lowest priority unless the requestor has a valid request which was not granted access on the previous clock cycle; in the event that both requestors associated with a single bit in the relative memory array are attempting to set that bit to the lowest priority, toggling the bit between lowest priority for each of the requestors on successive clock cycles.
Claim 32
Dependent Claim
57 words
The method of claim 25 wherein each of the requestors is provided with a queue to hold multiple requests from the requestor to the shared resource and the step of updating the relative memory arry comprises the step of: using the request at the head of each of the queues to update the relative priority memory array.
Claim 33
Dependent Claim
50 words
The method of claim 25 wherein the step of updating the relative memory array further includes the step of: determining whether the request is a valid request based on on whether the selected resource is available and preventing the enable signal from being generated if the resource is not available.
References Cited (Backward Citations)
US3925766A
Cited
US4009470A
Cited
US4257095A
Cited
US4229791A
Cited
US4271467A
Cited
US4449183A
Cited
US4392200A
Cited
US4314335A
Cited
US4370709A
Cited
US4499538A
Cited
US4473880A
Cited
US4454581A
Cited
US4675812A
Cited
US4636942A
Cited
US4754398A
Cited
US4745545A
Cited
US4719569A
Cited
US4920485A
Cited
US4816990A
Cited
US4894769A
Cited
US4937733A
Cited
US4949239A
Cited
US4845722A
Cited
US5016167A
Cited
US5012409A
Cited
US5016162A
Cited
US4972342A
Cited
US4979099A
Cited
US5053942A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-12-01 | 1996-06-01 | 1996-12-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-12-01 | 2000-06-01 | 2000-12-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-12-01 | 2004-06-01 | 2004-12-01 | $7700.00 | Window Closed / Lapsed |