Asynchronous arbiter using multiple arbiter elements to enhance speed

• US 5,713,025 A
• Filed: 09/08/1994
• Issued: 01/27/1998
• Est. Priority Date: 10/21/1993
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Sutherland, Ivan E., Jones, Ian W., Molnar, Charles E.
• Primary Examiner(s): Ray, Gopal C.
• Application Number:
  US08/303,247
• Time in Patent Office: 1,237 Days
• Field of Search: 395/729, 395/732, 395/293, 395/303, 395/291, 395/299, 395/730, 327/19, 340/825.51, 370/85.2, 370/85.6
• US Class Current: 710/241
• CPC Class Codes: G06F 13/364 using independent requests or grants, e.g. using separated request and grant lines
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3867 using instruction pipelines
• CPC Class Codes: G06F 9/3869 Implementation aspects, e.g. pipeline latches; pipeline synchronisation and clocking
• CPC Class Codes: H04L 25/085 Arrangements for reducing interference in line transmission systems, e.g. by differential transmission

Abstract

An arbiter circuit is described that is capable of granting a first user access to a shared resource while concurrently arbitrating subsequent requests from the first user to other users seeking access to the shared resource. The arbiter of the present invention includes a first arbiter element and a second arbiter element. The first arbiter element is initially used to arbitrate and issue a grant signal in response to one or more request signals from two or more users. The second arbiter element arbitrates and issues the next grant signal in response to subsequent request signal or signals from the one or other users. In one embodiment of the invention, the first and second arbiter elements are used alternately. In other embodiments, third and fourth arbiter elements are used to arbitrate in response to subsequent requests. The arbiter circuits of the present invention all reduce the delays in the access of users to the shared resource.

Claims

1. An arbiter configured to receive request signals from a plurality of users and to perform a first arbitration and a next arbitration, including:

a plurality of arbiter elements coupled to receive the request signals;

a grant circuit configured to issue a first grant and a next grant in response to output signals from a first arbiter element and a next arbiter element of the plurality of arbiter elements respectively; and

a feedback element configured to feed back the first grant signal from the grant circuit to the plurality of arbiter elements to invoke the next arbiter element, such that the first arbitration and the next arbitration are performed by different arbiter elements, and the next arbitration may begin as soon as the first grant is issued as a result of the first arbitration.

2. The arbiter of claim 1, wherein the issuance of the first grant is indicated by a transition of a first grant signal from FALSE to TRUE or by a transition of the first grant signal from TRUE to FALSE.

3. The arbiter of claim 1, further including a coupling circuit, coupled between the plurality of arbiter elements and the grant circuit, the coupling circuit configured to couple selected ones of the plurality of output signals from the plurality of arbiter elements to the grant circuit.

4. The arbiter of claim 3, further including a selection circuit, coupled to receive the grant signals and the request signals from the plurality of users, and configured to select the next arbitration element to perform the next arbitration based on the state of the grant signals and the request signals.

5. The arbiter of claim 4, wherein the selection circuit is coupled to further receive a done signal and is configured to select the next arbiter element based on the state of the grant signals and the done signal.

6. The arbiter of claim 5, wherein the done signal is generated internally within the arbiter at a time following each grant issuance after a predetermined delay.

7. The arbiter of claim 4, wherein the selection circuit further includes a plurality of AND gates, each one of the plurality of AND gates being configured to receive a different combination of the grant signals and the request signals.

8. The arbiter of claim 4, wherein the selection circuit further includes a plurality of XOR gates, each one of the plurality of XOR gates being configured to receive a different combination of true and complement of the grant signals and request signals.

9. The arbiter of claim 4 wherein the selection circuit is configured to reset the first arbiter element to perform a subsequent arbitration after the next arbitration.

10. The arbiter of claim 3, wherein the coupling circuit is configured to receive a done signal corresponding to the first grant issuance.

11. The arbiter of claim 10, wherein the coupling circuit is configured to activate the grant circuit and to enable the arbiter to issue the next grant after the done signal and a next one of the output signals from the next arbiter element are received.

12. The arbiter of claim 10, wherein the first done signal is generated internally within the arbiter at a time following the first grant issuance after a predetermined delay.

13. The arbiter of claim 3, wherein the coupling circuit further includes a plurality of AND gates, each of the plurality of AND gates configured to receive a different one of the output signals from the plurality of arbiter elements and a done signal.

14. The arbiter of claim 13, wherein the coupling circuit further includes a plurality of OR gates coupled between the plurality of AND gates and the grant circuit, the OR gates and the AND gates cooperatively configured to cause the grant circuit to issue the next grant upon receipt of the done signal following issuance of the first grant and the receipt of a next output signal from the next arbiter element.

15. The arbiter of claim 1, wherein each of the plurality of arbiter elements is a mutual exclusion element.

16. The arbiter of claim 1, wherein the grant circuit includes a plurality of latches configured to issue the plurality of grants.

17. The arbiter of claim 16, wherein a first latch among the plurality of latches is configured to provide a first grant signal and a complement of the first grant signal.

18. The arbiter of claim 17, wherein the issuance of the first grant is determined by a transition of a first grant signal and a complement of the first grant signal.

19. The arbiter of claim 1, further including a de-coupling circuit, coupled to the plurality of arbiter elements and the grant circuit, and configured to de-couple the first arbiter element from the grant circuit when a done signal is received that corresponds to the issuance of the first grant.

20. The arbiter of claim 1, further including a shared resource coupled to the arbiter, wherein the arbiter provides access to the shared resource to only one of the plurality of users at a time.

21. A method of providing an arbiter configured to receive request signals from a plurality of users and to perform a first arbitration and a next arbitration, including the steps of:

providing a plurality of arbiter elements coupled to receive the request signals;

providing a grant circuit configured to issue a first grant and a next grant in response to output signals from a first arbiter element and a next arbiter element among the plurality of arbiter elements respectively; and

providing a feedback element configured to feed back the first grant signal from the grant circuit to the plurality of arbiter elements to invoke the next arbiter element, such that the first arbitration and the next arbitration are performed by different arbiter elements, and the next arbitration may begin as soon as the first grant is issued as a result of the first arbitration.

22. The method of claim 21, further including the step of coupling the plurality of arbiter elements and the grant circuit, such that selected ones of the plurality of output signals from the plurality of arbiter elements are coupled to the grant circuit.

23. The method of claim 22, further the step of providing a selection circuit, coupled to receive the grant signals and the request signals from the plurality of users, and configured to select the next arbitration element to perform the next arbitration based on the state of the grant signals and the request signals.

24. The method of claim 22, wherein a coupling circuit is configured to activate the grant circuit and to enable the arbiter to issue the next grant after the done signal and a next one of the output signals from the next arbiter element are received.

25. The method of claim 21, further including a shared resource coupled to the arbiter, wherein the arbiter provides access to the shared resource to only one of the plurality of users at a time.