Computer system with distributed bus arbitration scheme for symmetric and priority agents

• US 5,581,782 A
• Filed: 10/03/1995
• Issued: 12/03/1996
• Est. Priority Date: 03/01/1994
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Lai, Konrad K., Singh, Gurbir, Sarangdhar, Nitin V., Rhodehamel, Michael W., Fisch, Matthew A.
• Primary Examiner(s): Pan, Daniel H.
• Application Number:
  US08/538,597
• Time in Patent Office: 427 Days
• Field of Search: 395/550, 395/825, 395/421.08, 395/297, 395/200.01, 395/307, 395/294, 395/285, 395/303, 395/299, 395/288, 395/730, 395/739, 395/185.03, 395/800, 395/775, 395/48 2, 364/DIG. 1, 364/DIG. 2, 340/825.5
• US Class Current: 710/119
• CPC Class Codes: G06F 13/36 for access to common bus or bus system
• CPC Class Codes: G06F 13/364 using independent requests or grants, e.g. using separated request and grant lines
• CPC Class Codes: H04L 12/4015 by scheduling the transmission of messages at the communication node
• CPC Class Codes: H04L 12/403 with centralised control, e.g. polling

Abstract

A system and method for providing a high performance symmetric arbitration protocol that includes support for priority agents. The bus arbitration protocol supports two classes of bus agents: symmetric agents and priority agents. The symmetric agents support fair, distributed arbitration using a round-robin algorithm. Each symmetric agent has a unique Agent ID assigned at reset. The algorithm arranges the symmetric agents in a circular order of priority. Each symmetric agent also maintains a bus ownership state of busy or idle and a Rotating ID that reflects the symmetric agent with the lowest priority in the next arbitration event. On an arbitration event, the symmetric agent with the highest priority becomes the symmetric owner. However, the symmetric owner is not necessarily the overall bus owner (i.e., a priority agent may be the overall bus owner). The symmetric owner is allowed to take ownership of the bus and issue a transaction on the bus provided no other action of higher priority is preventing the use of the bus. A symmetric owner can maintain ownership without re-arbitrating if the transaction is either a bus-locked or a burst access transaction. The priority agent(s) has higher priority than the symmetric owner. Once the priority agent arbitrates for the bus, it prevents the symmetric owner from issuing any new transactions on the bus unless the new transaction is part of an ongoing bus-locked operation.

Claims

1. A computer system with distributed bus arbitration, said computer system comprising:

bus means for providing a communication interface;

a plurality of stand-alone agents coupled to said bus means, said stand-alone agents including at least one priority agent and a plurality of symmetric agents;

memory means coupled to said bus means for storing instructions and data;

at least one of said symmetric agents being a processor means for executing said instructions and processing said data and for performing transactions on said bus means, each of said symmetric agents having symmetric arbitration means for arbitrating ownership of said bus means, wherein each said symmetric arbitration means generates requests for bus ownership and receives requests for bus ownership from other symmetric agents, each said symmetric arbitration means also for arranging said symmetric agents in a circular order of priority and selecting a symmetric owner from the symmetric agents requesting ownership of said bus means during an arbitration event, said symmetric owner performing a bus transaction on said bus means;

each of said symmetric arbitration means including rotating identifier means for indicating a lowest priority symmetric agent upon said arbitration event, ownership state means for indicating first and second ownership states, and priority agent request detecting means for detecting bus ownership requests from said at least one priority agent, wherein said symmetric arbitration means of said symmetric owner releases ownership of said bus means when a priority agent request is detected, unless said bus transaction is a locked transaction.

2. The computer system of claim 1 wherein said first state indicates none of said symmetric agents is a symmetric owner and said second state indicates said symmetric owner is selected.

3. The computer system of claim 2, wherein each symmetric arbitration means further comprises:

an agent identifier means for uniquely identifying each of said symmetric agents.

4. The computer system of claim 3, wherein each symmetric arbitration means further comprises:

symmetric agent request detecting means for detecting bus ownership requests from said other symmetric agents, wherein when one symmetric agent is said symmetric owner its symmetric arbitration means releases ownership of said bus means when its symmetric agent request detecting means detects a request unless said bus transaction is atomic.

5. The computer system of claim 4 wherein when said one symmetric agent is said symmetric owner its symmetric arbitration means releases ownership of said bus means when its symmetric agent request detecting means detects a request unless said bus transaction is a burst access.

6. A method of arbitrating for ownership of a bus among a plurality of stand-alone agents which include one or more symmetric agent(s) and at least one priority agent in a computer system, said symmetric agent(s) having a predetermined circular ordering, the method comprising the steps of:

issuing an arbitration event by said symmetric agent(s);

responsive to said arbitration event, determining in each symmetric agent, a symmetric owner from among said symmetric agent(s), each of said symmetric agent(s) performing the steps of;

reading a rotating ID value stored in each of said symmetric agents to determine a lowest priority symmetric agent in said circular ordering;

detecting which of said symmetric agents are requesting ownership of said bus;

from among said symmetric agent(s) requesting ownership of said bus, selecting a highest priority symmetric agent to be said symmetric owner;

updating said rotating ID value to indicate said symmetric owner; and

granting ownership of said bus to said symmetric owner.

7. The method of claim 6 further comprising the step of:

in each said symmetric agent(s), reading a symmetric ownership state indicator stored therein to determine whether said symmetric bus ownership state is idle or busy, wherein said symmetric bus ownership state is idle if no symmetric owner is assigned to said bus, and wherein said symmetric bus ownership state is busy if said symmetric owner is assigned.

8. The method of claim 7 further comprising the step of:

parking on the bus by said symmetric owner if said symmetric bus ownership state is idle and said symmetric owner has not deasserted its request.

9. The method of claim 8 further comprising the initial step of:

in each said symmetric agent, initializing said symmetric bus ownership state to idle and said rotating ID value to point to a predetermined one of said symmetric agent(s).

10. The method of claim 6 further comprising the additional step of:

relinquishing ownership of said bus by said symmetric owner to said priority agent in response to assertion of a priority request signal from said priority agent.

11. The method of claim 10 further comprising the step, prior to said relinquishing step, of:

performing a bus transaction by said symmetric owner.

12. In a computer system having a plurality of stand-alone agents which include a symmetric processor and a priority agent, said symmetric processor including an arbitration unit controlling access to a bus, a method for transferring ownership of said bus from said symmetric processor to said priority agent comprising the steps of:

asserting a priority request signal to request ownership of the bus by said priority agent;

determining that a lock signal has not been asserted by said arbitration unit of said symmetric processor;

granting ownership of said bus to said priority agent within a determined number of clocks after said priority agent asserts said priority request signal.

13. A multiprocessor (MP) computer system comprising:

a main memory;

a plurality of processors;

a first bus coupled to the plurality of processors and to the main memory providing information transfer therebetween;

a priority agent coupled to the first bus, the priority agent including an arbiter unit that arbitrates for ownership of the first bus;

wherein each processor includes a symmetric arbitration unit controlling processor access to the first bus, each processor asserting an address strobe signal when performing a transaction on the first bus, and asserting a lock signal to block other processors or the priority agent from acquiring the first bus;

the arbiter unit asserting a priority signal to request ownership from a processor having current ownership of the first bus, the processor relinquishing ownership within a determined number of clock cycles after the assertion of the priority signal unless the lock signal has been asserted by the processor, the arbiter unit releasing ownership of the first bus to the processors by deasserting the priority signal.

14. The MP computer system of claim 13 wherein the determined number of clock cycles is equal to four.

15. The MP computer system of claim 13 further comprising:

a second bus;

a plurality of input/output (I/O) devices coupled to the second bus; and

wherein the priority agent comprises a bridge circuit providing an interface between the first and second buses, the bridge circuit including the arbiter unit which arbitrates for ownership of the first bus on behalf of the I/O devices.

16. The MP computer system of claim 15 wherein the determined number of clock cycles equals four.

17. The MP computer system of claim 15 wherein the symmetric arbitration unit of each processor includes:

a unique age identification (ID);

a rotating identification (ID) which reflects an agent ID of a lowest priority processor; and

a bus ownership state bit which indicates whether the first bus is busy or idle.

18. The MP computer system of claim 17 wherein the lowest priority processor is equal to the agent ID of the processor having current ownership if the first bus is busy.

19. The MP computer system of claim 17 wherein the lowest priority processor is equal to the agent ID of a previous owner if the first bus is idle.

20. The MP computer system of claim 17 wherein the agent ID and the rotating ID each comprise two bits.

21. The MP computer system of claim 20 wherein the rotating ID of the processors changes in accordance with a round-robin arbitration scheme.

22. In a multiprocessor (MP) computer system comprising a plurality of symmetric processors each including an arbitration unit for controlling access to a bus, and a priority agent coupled to the bus, a method of arbitrating for ownership of the bus from a symmetric processor having current ownership of the bus, the method comprising the steps of:

(a) asserting by the priority agent a priority request signal during a first clock cycle;

(b) determining that a lock signal has not been asserted by the arbitration unit of the symmetric processor;

(c) determining within a certain time period of the first clock cycle whether a transaction is occurring on the bus;

if so

(d) waiting until the transaction completes;

else,

(e) waiting a predetermined number of clock cycles;

(f) obtaining ownership of the bus by the priority agent.

23. The method of claim 22 further comprising the step of:

deasserting the priority request signal to relinquish ownership of the bus by the priority agent.

24. The method of claim 22 further comprising the steps of:

asserting a bus request signal by another symmetric processor;

waiting until a rotating identification points to the another symmetric processor in accordance with a round-robin arbitration scheme;

performing a new bus transaction by the another symmetric processor.

25. The method of claim 24 further comprising the initial step of:

asserting a lock signal to prevent other symmetric processors from gaining ownership of the bus.

26. The method of claim 24 wherein the bus request signal remains asserted until the new bus transaction completes when the new bus transaction is a burst access.

27. The method claim 24 further comprising the step of:

parking on the bus by the symmetric processor to perform an additional bus transaction.

28. A computer system comprising:

a main memory;

a plurality of stand-alone agents which includes symmetric agents and a priority agent, at least one of the symmetric agents being a processor;

a first bus coupled to the symmetric agents and to the main memory providing information transfer therebetween;

a priority agent coupled to the first bus, the priority agent including an arbiter unit that arbitrates for ownership of the first bus;

wherein each of the symmetric agents includes an arbitration unit controlling agent access to the first bus, a symmetric agent asserting an address strobe signal when performing a transaction on the first bus, and asserting a lock signal to block other symmetric agents or the priority agent from acquiring the first bus;

the arbiter unit asserting a priority signal to request ownership of the first bus from a symmetric agent having current ownership of the first bus, the symmetric agent relinquishing ownership within a determined number of clock cycles after the assertion of the priority signal unless the lock signal has been asserted by the symmetric agent, the arbiter unit releasing ownership of the first bus back to the symmetric agents by deasserting the priority signal.

29. The computer system of claim 28 wherein the determined number of clock cycles is equal to four.

30. The computer system of claim 28 further comprising:

a second bus;

a plurality of input/output (I/O) devices coupled to the second bus; and

wherein the priority agent comprises a bridge circuit providing an interface between the first and second buses, the bridge circuit including the arbiter unit which arbitrates for ownership of the first bus on behalf of the I/O devices.

31. The computer system of claim 30 wherein the determined number of clock cycles equals four.

32. The computer system of claim 28 wherein the arbitration unit of each of the symmetric agents includes:

a unique age identification (ID);

a rotating identification (ID) which reflects an agent ID of a lowest priority symmetric agent; and

a bus ownership state bit which indicates whether the first bus is busy or idle.

33. The computer system of claim 32 wherein the lowest priority symmetric agent is equal to the agent ID of the symmetric agent having current ownership if the first bus is busy.

34. The computer system of claim 32 wherein the lowest priority processor is equal to the agent ID of a previous owner if the first bus is idle.

35. The computer system of claim 32 wherein the agent ID and the rotating ID each comprise two bits.

36. The computer system of claim 35 wherein the rotating ID of the symmetric agents changes in accordance with a round-robin arbitration scheme.

37. In a computer system comprising a plurality of stand-alone agents coupled to a bus, the stand-alone agents including symmetric agents and a priority agent, each of the symmetric agents including an arbitration unit for controlling access to the bus, wherein at least one of the symmetric agents is a processor, a method for arbitrating ownership of the bus from a symmetric agent having current ownership of the bus comprising the steps of:

(a) asserting by the priority agent a priority request signal during a first clock cycle;

(b) determining that the arbitration unit of the symmetric agent has not asserted a lock signal;

(c) determining within a certain time period of the first clock cycle whether a transaction is occurring on the bus;

if so

(d) waiting until the transaction completes;

else,

(e) waiting a predetermined number of clock cycles;

(f) obtaining ownership of the bus by the priority agent.

38. The method of claim 37 further comprising the step of:

deasserting the priority request signal to relinquish ownership of the bus by the priority agent.

39. The method of claim 37 further comprising the steps of:

asserting a bus request signal by another symmetric agent;

waiting until a rotating identification points to the another symmetric agent in accordance with a round-robin arbitration scheme;

performing a new bus transaction by the another symmetric agent.

40. The method of claim 39 further comprising the initial step of:

asserting a lock signal to prevent other symmetric agents from gaining ownership of the bus.

41. The method of claim 39 wherein the bus request signal remains asserted until the new bus transaction completes when the new bus transaction is a burst access.

42. The method claim 39 further comprising the step of:

parking on the bus by the another symmetric agent to perform an additional bus transaction.

43. A computer system with distributed bus arbitration comprising:

a bus;

a plurality of stand-alone agents coupled to said bus, said stand-alone agents including symmetric agents and a priority agent;

each of said symmetric agents having logic circuitry that sends a symmetric request signal on said bus to request ownership of said bus and which receives symmetric request signals from other symmetric agents and which also receives a priority request signal from said priority agent, said symmetric owner of said bus being determined by said logic circuitry as among said symmetric agents according to an algorithm;

wherein said logic circuitry of said symmetric owner releases ownership of said bus when said priority request signal is received.

44. The computer system of claim 43 wherein said logic circuitry of said symmetric owner asserts a lock signal during an atomic bus transaction.

45. The computer system of claim 44 wherein said logic circuitry of said symmetric owner releases ownership of said bus when said priority request signal only after said atomic transaction has completed.

46. The computer system of claim 43 wherein said algorithm comprises a round-robin algorithm that arranges said symmetric agents in a circular priority order.

47. The computer system of claim 43 wherein at least one of said symmetric agents comprises a microprocessor.

48. The computer system of claim 47 wherein said priority agent comprises a bus arbiter that arbitrates for ownership of said bus on behalf of a plurality of input/output (I/O) devices.