GB2326319A - High performance symmetric arbitration protocol support for I/O requirements - Google Patents

Abstract

An apparatus for use in a computer system comprising of: a priority agent having an arbiter unit operable to assert a priority signal to request ownership of a bus from a symmetric arbitration unit coupled to said bus, said arbiter unit obtains ownership of said bus within a pre-determined number of clock cycles after the assertion of the priority signal unless a lock signal has been asserted by said symmetric arbitration unit owning said bus.

Description

2326319 HIGH PERFORMANCE SYMMETRIC ARBITRATION PROTOCOL WFFH SUPPORT FOR

UO REQUIREMENTS

RELATED APPLICATIONS

This patent application is related to co-pending application GB 2287159, endded "Initialization Mechanism for Symmetric Arbitration Agents" which is assigmed. to the assionec: of the present application and Filed concurrently herewith.

BACKGROUND OF THE INVENTION

1. Field of the Invention.

The present invention relates to the field of computer systern buses. More particularly, the picsent invention relates to arbitration protocols for computer systern biisc,-, desioned for ser-,iciilc, multiple processors and L/0 devices.

Rcla(ed,Ail In nindern computer systems, multiple agents arc often coupled to a bus arid arbitrate for the use of the bus. An arbitration protocol determines which agent has a, owriership of the bLIS at any givcn tinic. A computer system miy inclUde multiple processors, or sliniflar devices, that are sornewhat alike in their bus usage requirements. Thc system mayalso include various 1/0 or sirnilir devices. It is advanta2COLIS to niect [fie bus bandwidthand latency requirements of all such agents in a well designed bus arbitration PUMCOL ThC bus bandwith requirement ofan,1(,Crl( is tile pciccillage of tillic, on avcr,12C, thtt the p.lFtiCUlarancrit rcC]Uircs use of the bus. I'll,- lalcricy requirement ofan agent is the maximuni ainount of nine that the a2crit c,,m %vall bc-forc obtaining owncrship of the bus.

In one arbitration scheme a central arbiter receives requests for the use of the bus from the individual agents and selectively grants ownership of the bus. This scheme offers flexibility because computer system designers can individually determine a priority scheme among the agents by customizing the central arbiter. Two drawbacks of this approach are: 1) a costly central arbiter is required, and 2) it has a long latency of bus exchange between multiple agents.

In another arbitration scheme, the agents are daisy-chained. In this scheme arbitration priority between the various agents goes from highest to lowest prion'tv. Two drawbacks of this scheme are inflexibility and long arbitration latency.

It would be advantageous to provide an arbitration protocol that requires no external central arbitration logic and provides low latency of bus exchange between ID ZP multiple agents. The present invention provides such an advantageous result.

It is common in computer systems to couple various types of agents to a computer system bus. For example, multiple processors along with L/O devices such as mass storage devices and memory devices are often coupled to the computer system bus. These agents have varying bus bandwidth and latency requirements. A processor agent may use the bus 20% of the t=im e while an 1/0 agent may use the bus far less than I% of the time. However, compared to a processor an 1/0 device typically has a relatively low bus latency requirement to avoid over-flow or underflow conditions imposed by their lirruted internal buffering Therefore, 1/0 devices should obtain usage of the bus as soon as possible to meet C their low latency requirement thereby avoiding system retries. An overall arbitration protocol should account for the needs of different types of bus agents.

The present invention provides such an advantageous result.

I Many modem computer systems can have a varying number of bus agents.

The number of agents on a particular bUS may vary between systems, or may vary I over time for a given system. Thus, it would be advantageous to provide a versatile C, arbitration protocol wliich supports a varying number of agents with minimal 0 additional logic and expense. The present invention provides such an advantageous t:I result.

In summary, to overcome problems with prior art arbitration protocols it would be advantageous for an arbitration protocol: 1) to provide for varying numbers of agents on the bus without requiring additional external logic (i.e., the

0 =1 protocol should be "glueless"); 2) to be fair in arbitrating between agents with sirrUlar bandwidth and latency requirements, referred to as "symi-netric agents"; 3) to provide a small latency bus exchange between multiple agents; 4) to accommodate burst accesses by agents; 5) to provide flexibdity to meet the requirements of 1/0 or other such devices, referred to as "priority agents"; 6) to meet the worst case arbitration latency for 1/0 devices; and 7) to allow one clock cycle for signal txansrrssion between multiple agents and a separate clock cycle for the agents to respond, referred to as a "latched bus". The present invention provides these and other advantageous results. However, the arbitration protocol of the present invention can also be used in a non "latched bus" environment.

SUMMARY OF THE 1NVENTION

A system a-nd method for providing a high performance sym-meLric arbitration protocol that includes support for priority agerits is described. Each syrrunetric agent in the system maintains dirce items in order to provide distributed arbitration using a round-robin (i.e., circular priority) algorithm: 1) a unique Agent ID initialized during reset, 2) a Rotating M value that reflects the symmetric agent with the lowest priority In [tic next -arbitration event, and 3) a symmetric Ownership State Indicator to indicate either a busy or an idle state. In orie embodiment there a.re four symmetric agents and the circular order of priority is 0, 1, 2, 3, 0, 1, 2, etc. with the Rotating IDS indicating which symmetric agent lim [tic lowest priority for the- next arbaration event. Upon an arbitration event, the syminetnc agent with the highest priority becomes the symmetric owner. A priority agent that requests the bus obtains ownership over the symnictric o%vncr unless tile Sym-metric owner is perfonil-Ing an atomic (i.e., bus-locked) transaction. In one such systern where 0 Intel Arcl-tecture processors are symmetric agents, a priority acycrit (such as an 1/0 signal and obtains ownership of the dcvicc) requests the bus by asserting a BPRlTt I 11us unlcss the current svinnictric Owner IS aSSCrt1111! a LOCKH sTrial.

In addition, a method is described for arbitrating between symmetric agents and a priority agent for ownership of a bus.

Elements of the described computer system include: a system bus; a memory coupled to the system bus; a request bus coupled to the system bus; and a plurality of processors each coupled to the system bus and the request bus for requesting ownership of the system bus and performing transactions on the system bus when selected to be a bus owner. Each processor includes an agent identifier that uniquely identifies the processor's position in a circular ordering of the processors, a rotating identifier that indicates a lowest priority processor such that a circular order of priority of the processors is defined, a request detector that defects bus ownership requests by the processors, arid a symmetric arbitrator that selects a highest priority from among processors requesting the system bus to be the bus owner. The rotating identifier updates itself to indicate the bus owner as the lowest priority agent. Another element that may be included is an ownership state indicator that indicates the ownership state of the system bus. If the ownership state is a first state the symmetric arbitrator of each processor selects the bus owner at least one clock cyle earlier than if the ownership state is a second state. The first and second states can be idle and busy states, respectively.

According to the present invention there is provided a computer system as set forth in claims 1 and 5, appended hereto.

BRIEF DESCRIMON OF THE DRAWINGS The present invention is illustrated by way of example and not limitation in the figures of the accompanying drawings, in which like references indicate siri-Lilar elements and n which:

Figure 1 is a block diagram of a multiprocessor computer system of the present invention; Figure 2 is a block diagram of a bus cluster system of the present invention; Figure 3 is a block diagram of a present Invention system interconnection between symmetric agents and priority agents; Z t Figure 4 is an illustration of the internal state tracking mechanism for distributed arbitration among symmetric agents; Figure 5 is a flowchart describing the steps of the present invention for arbitrating between symmetric agents., Figure 6 is a flowchart describing the steps of the present invention for a priority acrent to arbitrate for the bus; Figure 7 is a flowchart describing the steps of the present invention for a symmetric agent to request ownership of the bus; Figure 8 is waveforms illustraLing bus arbitration initiated af(er a reset sequence in a mode of the invention which includes Intel Architecture CPUs; Figure 9 is waveforms illustrating arbitration between two or more c symmetric agents while LOCK# and B PRI# stay inactive in a mode of the invention p which includes Intel Architecture CPUs; Figure 10 is waveforms illustrating bus exchange between a priority agent 0 _n W 1:1 and two symmetric agents in a mode of the invention which includes Intel 1 Architecture CPUs; and Figure 11 is waveforms illustrating an ownership request made by both a symmetric and a priority agent during an ongoing indivisible sequence by a symmetric owner in a mode of the invention wl-dch includes Intel Architecture Cpus.

- I- 1- 1 i. - "bl-.

AZA- - -..; - 1..

DETAILED DESCRJPTION OF THE PREFERRED EMBOD12vENT A system and method for providing a high performance symmetfic arbitration protocol that includes support for priority agents is described. In the following description, numerous specific details are set forth, such as agent types, bus bandwidths, signal names, etc., in order to provide a thorough understanding of the present invention. It will be understood by one skilled in the art that the present invention may be practiced without these specific details. In other instances, well- known methods, procedures, components, and circuits have not been described in detail in order not to obscure the invention.

FIG. I shows an overview of an example multiprocessor computer system of the present invention. The computer system generally comprises a processormemory bus or other communication means 10 1 for co=unica6ng information between one or more processors 102, 10-33, 104 and 105. Processor-memory bus 10 1 includes address, data and control buses. Processors 102 through 105 may include a small, extremely fast internal cache memory, commonly referred to as a level one (L1) cache memory for temporarily storing data and instructions on-chip. In addition, a bigger, slower level two (L2) cache memory 106 can be coupled to a processor, such as processor 105, for temporarily storing data and instrucdons for use by processor 105. In one mode, the present invention may include Intelg architecture microprocessors as processors 102 through 105; however, the present invention may utilize any type of n-Licroprocessor architecture, or any of a host of digital signal processors.

Processor 102, 103, or 104 may comprise a parallel processor, such as a processor similar to or the same as processor 105. Alternatively, processor 102, 103, or 104 may comprise a co-processor, such as an digital signal processor. In addition, processors 102 throuRh 105 may include processors of different types, -g- Processor 102 is coupled to process or-memory bus 101 over request bus 137 and bus 138. Processor 102 also contains a symmetric arbitration unit 302 which controls both when processor 102 requests access to proce ssor- memory bus 101 and when processor 102 is given ownership of bus 101. Request bus 137 transfers the signals associated with bus arbitration between processor 102 and the remaining agents coupled to processor- memory bus 101. The remaining signals t> 0 transferred between processor 102 and processor-memory bus 101 are transferred over bus 138. These remaining signals include data signals, address signals, and additional control signals. In one embodiment, request bus 137 and bus 138 are part of processor-memory bus 101.

The other processors 103 through 105 also include a symmetric arbitration unit 302 and are coupled to processor-memory bus 10 1 with a request bus 1 3)7 and bus 138 as shown with regard to processor 102. In one embodiment, only the sy=ciric agents coupled to processor-memory bus 101 include a symmetric arbitration unit 302. In an alternate embodiment, all agents coupled to processor- 0 memory bus 101 include a symmetric arbitradon unit 302.

The process or- memory bus 10 1 provides system access to the memory and input/output (1/0) subsystems. A memory controller 122 is coupled with proc essor- memory bus 10 1 for controlling access to a random access memory (RAM) or other dynamic storage device 121 (cornmonly refer-red to as a main memory) for storing information and instructions for processors 102 through 105. A mass data stora2e device 125, such as a maanetic disk and disk drive, for storinc, information and instructions, and a display device 123, such as a cathode ray tube (CRT), liquid crystal display (LCD), etc., for displaying information to the computer user may be coupled to processor-memory bus 101.

An input/output (1/0) bridge 124 may be coupled to processor-memory bus 101 and system 1/0 bus 131 to provide a communication path or gateway for devices on either processor- memory bus 101 or 1/0 bus 131 to access or transfer data between devices on the other bus. Essentially, bridge 124 is an inter-face between the system 1/0 bus 131 and the process or- memory bus 101. Bridge 124 includes a high priority arbiter unit 325 that arbitrates for ownership of the C) I processor-memory bus 101 on behalf of 1/0 devices such as 132-136.

1/0 bus 131 communicates information between peripheral devices in the computer system. Devices that may be coupled to system 1/0 bus 131 include a display device 132, such as a cathode ray tube, liquid crystal display, etc., an alphanumeric input device 133 3 including alphariumeric and other keys, etc., for communicatina information and command selections to other devices in the C, computer system (e.g., processor 102) and a cursor control device 134 for controlling cursor movement. Moreover, a hard copy device 135, such as a plotter Z:) or pi-inter, for providing a visual representation of the computer images and a mass storage device 136, such as a magnetic disk- and disk drive, for storing information and instructions may also bee coupled to system 1/0 bus 13 1.

In some implementations, it may not be required to provide a display device for displaying information. Certain implementations of the present invention may include additional processors or other components. Additionally, certain implementations of the present invention may not require nor include all of the above components. For example, processors 102 through 104, display device 123, 0 or mass stora2e device 125 may not be coupled to processor-memory bus 10 1.

C Furthermore, the peripheral devices shown coupled to system 1/0 bus 131 may be coupled to processor-memory bus 101; in addition, in some implementations only a single bus may exist with the processors 102 through 105, memory controller 122, and peripheral devices 132 through 136 coupled to the single bus, FIG. 2 is a block diagram showing an exemplary bus cluster systern of the present invention. The present invention can apply to multiprocessor computer systems having one or more clusters of processors. FIG. 2 shows two such clusters 201 and 202. Each of these clusters are comprised of a number of agents. For example, cluster 201 is comprised of four agents 203-206 and a cluster t> manager 207, which may include a-nother cache memory (not shown), coupled to bus 212. Agents 203-206 can include microprocessors, co-processors, digital signal processors, etc.; for example, agents 203 through 206 may be the same as W c) processor 102 shown in FIG. 1, being coupled to bus 212 via a request bus 137 and bus 138. Cluster manager 207 and its cache are shared between these four 0 agents 203-206. Each cluster is coupled to a memory system bus 208, which in one embodiment is processor-memory bus 101 of FIG. 1. These clusters 201-202 are coupled to various other components of the computer system through a system 1 interface 209. The system interface 209 includes a high speed I/0 interface 210 for 1 interfacing the computer system to the outside world and a memory inter- face 211 which provides access to a main m-cmory, such as a DRAM memory array (these interfaces are described in greater detail in FIG. 1). In one embodiment, high speed c) 1/0 interface 210 is bridge 124 of FIG. 1, and memory interface 211 is memory controller 122 of FIG. 1.

Certain implementations of the present invention may not require nor include all of the above components. For example, cluster 201 or 202 may comprise fewer than four agents. Additionally, certain implementations of the present invention may include additional processors or other components.

FIG. 3 is a block diagram of a present invention system interconnection between symmetric agents and priority agents. It should be noted that the 1 0 interconnecdon of FIG. 3 is exemplary only; the scope of the present invention is not limited to the interconnection shown. Other numbers of agents and t> interconnection schemes may be udlized which are within the spirit and scope of the present invention. Furthermore, other agents besides processors and 1/0 devices may be arbitrating for access to the bus, such as cluster manager 207 of FIG. 2. For bus arbitration purposes, each symmetric agent includes BR[3:0]#, BPRI#, and LOCK# pins. The BR[3:0]# pins (i.e., bus request pins) are bus request pins whereby a symmetric agent receives bus ownership requests from bus agents and sends bus ownership requests. In one mode, a symmetric agent issues a 4=1 ID bus ownership request by asserting its BRO# pin and receives bus ownership requests on each of the BR[3:01-'rr pins. The BPRI# pin (i.e., priority request pin) is a pnonty request pin whereby a symmetric agent receives bus ownership requests from a high priority bus agent. The LOCK# pin (i.e., bus-locked transaction pin) is a bus-locked transaction pin whereby a symmetric agent signals all other bus agents that bus ownership is currently locked, i.e. bus ownership cannot change while any bus agent is asserting its LOCK# pin. In one mode, a symmetric agent asserts its LOCK7#, pin while per-forrrung an atomic operation (i.e., an indivisible sequence of bus transactions).

The BR[M]# pins of symmetric agents 302-305 are coupled to a set of BREQ[10]#r signals 311-314 (i.e., bus request signals) whereby IndIvIdual symmetric agents send arid receive bus ownership requests to arbitrate for ownership of a system bus, such as processor-memory bus 10 1 of FIG. 1. Additional details of the system bus have not been included so a-S not to clutter the drawings and obscure the present invention. In a computer system where the symm etric agents are processors (or the processors have symmetric arbitration ulUts), the BREQ# " signals are part, of the processor-memory bus 10 1 of FIG. 1 in one mode, or part of the separate request bus 137 in a-nother mode. Altemadvely, in a bus cluster system the BREQ- signals can be part of bus 212 of FIG. 2. Each symmetric agent's BPRI# pin is coupled to a BPRIT'll signal 316 (i.e., a high priority C5 C1 arbitration signal) which can be asseried by I-figh pnority bus agents to a-rbitrate for bus ownership. The LOCK# pins of cacti symmetric agent are coupled to a LOCK# signal 318 (i.e., a bus-lock signal) which can be asseried by the current symmetric owner to maintain bus ownership during a bus-locked transaction.

A high priority arbiter 325 is coupled to drive the BPRI# signal 316 to asbitrate for bus ownership oil behalf of multiple priority agents. In addition, the high priority arbiter 325 receives the LOCK# signal 318 as an input to indicate when it may arbitrate for bus ownership. If none of the symmetric agents 302-305 is asserting (lie LOCKT# signal 3 18 (i.e., the LOCK# signal is deasserted), the high priority arbiter 325 can assert the BPRIr', signal 3 16 to arbitrate for ownership of tile system bus. The high priority arbiter 325 includes a set of 1OR-EQ[ri:O] pins for receiving bus ownership requests frorn various priority agents. In addition, high priority wbiter 325 includes a set of IOACK[n:O] pins for acknowledging to priority agents that bus ownership has been granted. When a high priority request is present on any IOREQ pin, the high priority arbiter 325 prionCzes the current requests, arbitrates for bus o\.ricrstijp, acrio'ledges ownership of the bus to the priority agent having the Inglic.st priority, request.

Note that the high priority arbiter 325 can be thought of as the "priority a-ent" with respect to the wbitradon protocol of die present invendon because the high priority arbiter 325 arbitrates for the bus on belialf of multiple priority agents. In the subsequent discussion of the arbitration protocol, "priority agenC can also mean such a high priority arbiter.

In one niode including the. high priority -arbiter, priority agents cacti include a REQ pin and an ACK pin. A priority -agent asserts its REQ pin (i.e., a priority agent request pin) to request ownership of [lie system bus. A priority agent obser-vcs its ACK pin (i.e., a priority ancrit acknowledge pin) to detcrillific wlicil it lias been grailted ovrierslilp of (lie system bus.

In one embodiment, priority agents 327 and 328 are coupled to the high priority arbiter 325. Each priority agent's REQ output is coupled to one of the high priority arbiter's IOREQ[O..n] inputs. Each priority agent's ACK input is coupled to one of the high priority arbiter's IOACK[O..n] outputs. The priority agents 327328 obtain ownership of the processormemory bus 101 through a request and acknowledge protocol with the high priority arbiter 325. A priority agent sends a request for ownership of the bus by asserting its REQ output. The high priority ZD 0 arbiter 325 prioritizes the current requests received on its IOPEQ[O..n] inputs, asserts the BPRIT# signal 316 to arbitrate for the bus, and notifies the selected priority agent when bus ownership is 0 granted by asserting the appropriate IOACK[O..n] output.

The symmetric agents 0-3 may be processors 0-3 of FIG. I with the BREQ[3:0]# signals being part of the process or-memory bus 101 in one mode or part of the request bus 137 in another mode. Priority agents 0 and I may be 1/0 devices with their REQ and ACK signals being part of systern-I/O bus 13 1. The 0 ID high priority arbiter 325 may be embodied in the bridge 124.

Thus, present invention system interconnection scheme of FIG. 3 provides a means whereby the symmetric agents 302-305 can arbitrate between themselves for ownership of the bus, i.e. a symmetric agent arbitration protocol, and also c provides a means whereby priority agents 327-328 can arbitrate for ownership of C the bus, i.e. a priority agent arbitration protocol.

c I. The Arbitration Protocol of the Present Invention For further clarity, the present invention arbitration protocol embodying both the symmetric agent and priority agent arbiti-a6on protocols Is now dliscussed in more detail. The following, discussion is for an arbitration protocol for up to four symmetric agents and a prionty agent (or Egh priority arbiter that may arbitrate on behalf of any number of other priority agents). The present invention, however, is not limited to the case of four symmetric agents. Other numbers of symmetric agents are within the scope and spirit of the present invention. Note that the O'priority agenC in the following discussion can also be a high priority arbiter as shown in FIG. 3. In the arbitration protocol of the present invention, a single priority agent or a high priority arbiter that arbitrates on behalf of multiple priority agents arbitrate for the bus in essentially the same manner.

Arbitration Phase. A bus agent needs to have bus ownership before it can initiate a bus transaction. If the agent is not the bus owner, it enters the Arbitration Phase to obtain bus ownership. Once bus ownership is obtained, the agent can enter the Request Phase and issue a transaction on the bus.

Arbitration Protocol Overview. The bus arbitration protocol of the present invention supports two classes of bus agents: symmetric agents and priority agents. The symmetric agents support fair, distributed arbitration using a roundrobin (i.e., circular priority) algorithm. Each symmetric agent has a unique Agent ID between zero to three assianed at reset. The al-orithm arranges the four C It symmetric agents in a circular order of priority: 0, 1, 2, 3, 0, 1, 2, etc. Other numerical schemes could be used, however. Each symmetric agent also maintains a common Rotating ID that reflects the symmetric Agent ID with the lowest priority in the next arbitration event. An arbitration event is the process by which a new symmetric bus owner is detern-ined and changed. On every arbitration event, the symmetric agent with the highest priority becomes the symmetric owner. Note that 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 enter the Request Phase provided no other action of higher priority is preventing the use of the bus.

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 entering into a new Request Phase unless the new transaction is part of an ongoing 0 bus locked operation. Bus locked operations are those operations, (for example an atomic operation such as read- mod i fy -write) which cannot be interrupted without disturbing the integrity of the operation. The priority agent is allowed to enter the 0 115 Request Phase provided no other action of higher priority is preventing the use of the bus.

In one embodiment, the symmetric agents are processors and the "priorivy I agent" is a high priority arbiter that arbitrates on behalf of multiple 1/0 devices.

I C) Besides the two classes of arbitration agents, a bus lock- can act as an Z arbitration modifier. A bus agent causes a bus lock action by asserting LOCK:'.

Z= Z:) The bus lock action is available to the current symmetric owner to block other agents, including the priority agent, from acquiring the bus. Typically a bus lock-ed 0 CD 1 C) operation consists of two or more transactions issued on the bus as an indivisible s equence (i.e., an aton-iic operation). Once the symmetric bus owner has successfully initiated the first bus locked transaction it continues to issue remaining, requests that Lre part of the same indivisible operation without releasing the bus, i.e. it asserts its BR, "rr and LOCK# pins low throughout the operation.

In surrimary, the priority for entering the Request Transfer Phase is:

I 1. The current bus owner retains ownership until it completes an oncoin. indivisible bus locked operation.

2. The priority agent gains bus ownershi C -- 1 ip over a symmetric owner.

3. Other-wise, the current s mmetric owner as determined by the rotating y priority is allowed to generate new transactions.

Bus Signals. The bus ai-baration signals are BREQ[10]#r, BPRIr't, and LOCK,#. Referring again to FIG. 3, the BREQ[10],' bus signals are connected to the four syrnmelric agents in a rotating manner. This =angement initializes evcr-,y 1 c) 1 syrrunctric agent with a unique Agent ID during power-on configuration. Details of the Agent LD initializafion mecharsm are described in the above- referenced patent application. Every symmetric agent has one input/output pin, BRO#, to arbitrate for the bus during normal operation. The remaining three pins, BR I#, BR2#, and BR3#, are input only arid are used to observe the arbitration requests of the remaining three syrnmetric agents.

The BPRJ# signal 316 is an output from the priority agent by which the priority agent arbitrates for ownership of the bus. In addition, BPRI# isan input to signal the synunetric agents that a priority agent requests ownership of the bus. LOCK# is a bi-dircctional signal bused among all agents. The current bus owner uses LOCK# to define an indivisible bus locked operation.

Jntemal BLIS State-, of Symnietric Agnts. III order to maintain a "glueless' multi-agent interface aniong the symmetric agents, sorne bus states are distributed and tracked by all syminetric agents on the bus. This is known as a distributed svrnmetric arbitration protocol. "Glueless" means that no external loC1IC IS required to perform symineLric arbitration.

Referring no%,,, to FIG. 4, in illustration of the internal state tracking mechanism for distributed arbitration aniong syriunetric agents is sho%vn. For the internal state tracking, each svr=etrlc agent 500 maintains a two-bit Agent ID 505 and a two-bit Rotating ID 5 10 to perform distributed round-robin arbitration. In addition, each symmetric agent 500 also niaintains a symmetric ownership state bit that describes whether the bus ov.,nership is being retained by the current symmetric ov, ,ner ("busy" state) or is in a state where no syrnmetric agent currently owns the bus ("idic" statc). The no(ion of idle state enables a smaller, two-clock arbitration latency from bus reqUCSt to bus ownership in sonie cases as will be described below. The 1-10110n Of bUSY State enables "bus parking" but increases arbitration latency to a 111111'1111UNI Of f0Ur clocks due to a handshake with the current symmetric owner. "Bus parking" means that the current bus owner maintains bus ownership even if it currently does not have a pending transaction. U a transaction becomes pending before that bus owner relinquishes bus ownership, the current symmetric owner can drive the transaction without having to first arbitrate for the bus. The state tracking mechanism can be implemented as a state machine using combinational logic.

ARent ID. A symmetric agent's Agent ID is determined at reset, as described in the above-referenced application. The Agent ID is unique for every symmetric agent.

Rotating ID. The Rotating ID points to the symmetric agent that will be the C W lowest priority agent in the next arbitration event with active requests, i.e. the Agent 0 W ID of the current symmetric bus owner if the bus is busy or the Agent ID of the previous symmetric bus owner in the case of an idle bus. In one mode all symmetric a. ents maintain the same Rotating ID and the Rotating DD is initialized to 1 CD 0 0 3 at reset. In another mode, each symmetric agent has a different value for its Rotating ID at any given time. However each symmetric agent's Rotating ID points to the same symmetric owner. After an arbitration event, the Rotating ID is C) assigned the Agent ID of the new symmetric owner so that the new owner becomes 0 C the lowest priority agent on the next arbitration event.

0 Symmetric Ownershi12 State. The symmetric ownership state is reset to idle on an arbitration reset. The state becomes busy when any symmetfic agent completes the Arbitration Phase and becomes symmetric owner. The state remains busy while the current symmetric owner retains bus ownership or transfers it to a different symmetric agent on the next arbitration event. When the state is busy, the Rotating ID is the same as the curTent symmetric owner Agent ID. When the state is idle, the Rotating ID is the same as the previous symmetric owner Acent ID.

1 0 1 Note that the symmetric ownership state refers only to the symmetric bus owner. The priority agent can have actual physical ownership of the request bus, even when the state is busy and there is a current symmetric owner.

IT. Present Invention Arbitration Protocol Rules The arbitration protocol of the present invention can be expressed in the following sets of arbitration protocol rules. In the following discussion BINIT# is a signal that indicates a catastrophic bus protocol error. AERR# is a signal that indicates a parity error in the address of an issued bus transaction. AER.R# triggers OC a retry of the transaction having the error.

0 Svmmetric Ap-ent Arbitration Protocol Rules Reset Conditions. On observation of active RESETT# or BLNIT#, all BREQ[10]# signals should be deasserted in one or two clocks. On observation of active AERR# (with AERR# observation enabled), all BREQ[10]# signals should be deasserted in the next clock. All agents also re-initialize their Rotating ID to three and their ownership state to idle. Based on this situation, the new arbitration priority is 0, 1,2,3 and there is no current symmetric owner.

When a reset condition is generated by the activation of BINITr't, BREQn# should remain deasserted until 4 clocks after BINIT# is driven inactive. The first BREQ# sample point is 4 clocks after BE'IT,', is sampled inactive.

When the reset condition is generated by the activation of RESET#r, BREQn# as driven by symmetric agents should remain deasserted until 2 clocks after RESET# is driven inactive. The first BREQ# sample point is 2 clocks after RESET# is sampled inactive. For power-on configuration, the system interface logic should assert BREQO# for at least two clocks before the clock in wljch RESET# is deasserted BREQ0# should be deasserted by the system interface logic in'the clock after RESET# is sampled deasserted. Agent 0 should delay BREQG# assertion for a minimum of three clocks after the clock in which RESET# is deasserted to guarantee wired-or glitch free operation.

When a reset condition is generated by AERR,#, all agents except for a symmetric owner that has issued the second or subsequent transaction of a buslocked operation should keep BREQn# inactive for a minimum of four clocks. The bus owner n that has issued the second or subsequent transaction of bus locked operation should activate its BREQn# two clocks from inactive BREQn#. This approach ensures that the locked operation remains indivisible.

Bus Request Assertion. A symmetric agent n can activate BREQn# to arbitrate for the bus provided the reset conditions are satisfied. Once activated, BREQn# should remain acdve until the agent becomes the symmetric owner. Becorning the symmetric owner is a precondition to entering the Request Phase.

0 ID Ownership from Idle State. When the ownership state is idle, a new arbitration event begins with activation of at least one BREQ[3:0]1'r. During the next clock, all symmetric agents assign ownership to the highest priority symmetric 0 0 1-7 agent with active bus request. In the following clock, all symmetric agents update C) 0 their Rotating ID to the new symmetric owner Agent ID and their ownership state to busy. The new symmetric owner may enter the Request Phase as early as the clock the Rotating ED is updated.

Ownership from Busy State. When the ownership state is busy, the next arbitration event begins with the deassertion of BREQn#r by the current sy=eLric owner. During the next clock, all symmetric agents assign ownership to the highest 0 I'D 1:1 priority symmetric agent with active bus request. In the following clock, all 0 symmetric agents update their Rotating 10D to the new symmetric owner Agent DD and their ownership state to busy. The new symmetric owner may enter the Request Phase as early as the clock the Rotating DD is updated.

0M Parking and Release with a Singgle-Bus Request. When the ownership state is busy, bus parking is an accepted mode of operation. The symmetric owner can retain ownership even if it has no pending requests, provided no other symmetric agent has an active arbitration request. The symmetric owner n may eventually deassert BREQn# to release symmetric ownership even when other requests are not active. When the symmetric owner deasserts BREQn#, all symmetric agents update their ownership state to idle, but maintain the same Rotating 1D.

Bus Exchange With-Multil2le Bus Requests. When the ownership state is busy, on observing at least one other BREQn41 active, the current symmetric owner n can hold the bus for back-to-back transactions by simply keeping BREQn# active. This mechanism should be used for bus- locked operations and can be used for unlocked operations to prevent other symmetric agents from gaining ownership.

A new arbitration event begins with deactivation of BREQn#. On observing release of ownership by the current symmetric owner, all agents assign bus ownership to the highest priority symmetric agent arbitrating for the bus. In the following clock, all agents update their Rotating ID to the Agent ID of the new symmetric owner and maintain their bus ownership state as busy. The prior symmetric owner n deasserts BREQn# for a minimum of one clock after ownership is granted to another symmetric agent.

t> PTiority Agent Arbitration Protocol Rules Reset Conditions. On observation of active RESET# or BINIT#. BPRI# should be deasserted in one or two clocks. On observation of active AERR#, BPRI# should be deasserted in the next clock.

When the reset condition is generated by the activation of BINITIrr, 13PRI# should remain deasserted until 4 clocks after BLNIT# is dri'ven inactive. The first BPRI# sample point is 4 clocks after BINIT# is sampled inactive.

When the reset condition is generated by AERR#, the priority agent should keep BPRI# inactive for a minimum of four clocks unless it has issued the second or subsequent transaction of a locked operation. The priority owner that has issued the second or subsequent transaction of a locked operation should activate its BPRI# two clocks from inactive BPRI#. This ensures that the locked operation remains indivisible.

Bus Request Assertion. The priority agent can activate BPRI# to seek bus ownership provided the reset conditions are satisfied. BPR.1# can be deactivated at any time. On observing active BPRI'M, a.11 symmetric agents guarantee no new non- 0 0 locked requests are generated.

Bus Exchange from an Unlocked Bus. If LOCK# is observed inactive in two clocks after BPRIT'll is driven asserted, the priority agent can take ownership of the bus four clocks after BPRI'm assertion. The priority agent can further reduce its 0 arbitration latency by observing the bus protocol and detem-iining that no other 0 0 aaent could drive a request. For example, arbitration latency can be reduced by to two clocks by observing ADS,-rr active and LOCK.# inactive on the same clock 0 BPR-1# assciied or it can be reduced to three clocks by observing ADS1# active and LOCK#r inactive in the clock a-fter BPR-I# is driven asserted. ADST# is a signal that, when asserted, indicates a transaction on the bus by the current bus owner.

Bus Release. The prionty agent can deassert BPR.11# and release bus ownership in the same cycle that it generates its last request. It can keep BPPU# active even after the last request generation provided it can cuarantee for-ward C> progress of the symmetric agents. When deasserted, BPRI,#r stays inactive for a c) 1:1 rrnimum of two clocks.

Bus Lock Protocol Rules Bus Ownership Exchange from a Locked Bus. The current symmetric owner n can retain ownership of the bus by keeping the LOCK# signal active (even if BPRI# is asserted). This mechanism is used during bus lock operations. After the lock operation is complete, the symmetric owner deasserts LOCK# and guarantees no new request generation until BPRI# is obser-ved inactive.

On asserting BPRI#, the priority agent observes LOCK# for the next two clocks to monitor request bus activity. If the current syrrimetric owner is perform.ing locked requests (LOCK,'t active), the priority agent should wait until LOCK# is observed inactive.

171. Operation of the Present Invention Arbitration Protocol FIG. 5 illustrates a portion of the method of the present invention; specifically it shows how symmetric agents arbitrate for bus ownership. The process begins with a reset condition in step 405. During the reset condition, in step 4 10 for each symmetric agent: 1) the Agent ID is initialized to a unique value of 0, 1, 2, or 3, 2) the Rotating ID is set to point to agent 3, and 3) the Ownership state is set to idle. From this point on, the process proceeds after the syniriletric acents have come out of reset. The following processing steps illustrate the distributed, round-robin arbitration protocol of the present invention. Each symmetric agent's internal state tracking mechanism performs the following steps to 0 maintain the distributed, round-robin symmetric agent arbitration protocol of the present invention.

In step 415 each symmetric agent deten-nines whether the ownership state is busy or idle. If the ownership state is busy the process jumps to step 440; otherwise the process proceeds to step 420.

In step 420 cach syninictric aggent determines whether ihere is a current request for o.iicrsiiip of [tic bus (i.c., svlictlier one of the BREQn# input signals is asserted). A request for ownership of the bus is an arbitration event when the ownership state is idle. If there are no BREQn# requests the process stays in step 420 to continue checking for a request. If there is a BREQnr# request the process proceeds to step 425.

In step 425 each symmetric agent assigns ownership to the highest priority symmetric agent that has an active request. The priority is determined from the Rotating ED values maintained by each symmetric agent's internal state tracking mechanism. For example, if the Rotating IDs indicate symmetric agent 3 then the highest priority symmetric agent is agent 0. If the Rotating IDs indicate symmetric :D C1 0 agent I then the highest priority agent is agent 2. In the first example the current Z) 0 0 priority order is 0,1,2,3. If symmetric agents I and 3 have active requests then each symmetric agent assigns ownership to agent 1. In the second example the C It) current priority order is 2,3,0, 1. If synunetric agents 2 and I have active requests then each symmetric agent assigns ownership to agent 2. Thus the round- robin 0 C> 0 nature of the symmetric arbitration scheme. The process proceeds to step 430.

In step 430 Each synunetric agent's Rotating ID is updated to indicate the C 0 new symmetric owner. In one embodiment each symmetric agent has the same 1:1 Rotating IID value. In another embodiment, each symmetric agent has a different D 0 value for its Rotating ID at any given time. However each symmetric agent's 1-7 CID Rotating IID points to the same symmetric owner. This embodiment is described in C detail in the above-referenced patent application which is hereby incorporated by reference. The process proceeds to step 435.

In step 435 the current symmetric owner performs a bus transaction if no priority agent has ownership of the bus (i.e., BPR.I# is not asserted). The process then jumps to step 415 to prepare for the next syrrunetric arbitration event.

Returning, to step 415 to describe a second path the process can take, if step 415 determines that the ownership state is busy then the process jumps to step 440 where each symmetric agent determines whether the current symmetric owner has deasserted its request (i.e., each symmetric agent samples its BR' input signals to 0 n determine if the BREQ# signal corresponding to the current symmetric owner is deasserted). When the ownership state is busy, an arbitration event is when the current symmetric owner deasserts its ownership request. If the current symmetric owner has not deasserted its request the process proceeds to step 445; otherwise the process jumps to step 450.

In step 445 the current symmetric owner has not deasserted its request and the current symmetric owner is parked on the bus. A symmetric owner parks on the bus either to perform a bus locked operation or when no other symmetric agent is requesting the bus. Step 445 jumps to step 435 where the current symmetric owner can initiate a transaction on the bus if BPRI1# and BNRI# are not asserted.

In step 450 each symmetric agent deteri---nines whether any symmetric agent is requesting ownerslp of the bus (i.e., whether any of the BREQn# signals are asserted). If a symmetric agent(s) is requesting ownership, the process jumps to step 425 to begin servicing the request; otherwise the process proceeds to step 455.

In step 455 the current symmetric owner releases the bus. The Rotating IDs are not change but each symmetric agents set its ownership state to idle. The 0 0 process then jumps to step 415 to prepare for the next symmetric arbitration event.

FIG. 6 illustrates a portion of the method of the present invention; 1 fil n spec ically it shows how a prio ity agent arbitrates for bus ownership. When a priority agent arbitrates for the bus (by asserting BPRI,','), ownership will be granted unless the current bus owner is performing a bus-locked operation (i.e., LOCK# is asserted). To minimize any impact on system performance, the priority agent should be given ownership as early as possible. However, the priority agent should not begin a transaction on the bus before any current bus transactions are completed. The ADS# signal (which is driven by the current bus owner) indicates 0 M' T when a transaction occurs on the bus. Thus, when ADS# is asserted some agent is currently performing a bus transaction. When requesting ownership of the bus, a priority agent samples the ADS# signal to determine how many clocks the priority agent must wait before it can safely take ownership of the bus. The process 600 details the timing of when the priority agent can safely take ownership of the bus. The process starts in step 605, which may occur at any time during the operation of the arbitration protocol of the present invention (except during the reset sequence).

Step 6 10 deterrrnes whether a priority agent is requesting ownership of the bus (i.e., whether BPRI# is asserted). If no priority agent is requesting ownership, the process stays in step 6 10 to wait for a request by a priority agent. If c> a priority agent is requesting ownership of the bus, the process proceeds to step 615.

Step 615 determines whether the bus is locked (i.e., whether LOCK# is asserted). The bus can be locked by an agent that is performing a locked operation (atorric operation) or for other reasons. If the bus is locked (LOCK# asserted) the process retums to step 610. If the bus is not locked (LOCK# dcasseried) the process proceeds to step 620.

Step 620 determines whether a transaction is observed on the bus (i.e., whether ADS# is sampled asserted) during the clock cycle in which the priority acrent asserts Its request (i.e., durin 1 1 C_ _g the cycle in which 13PRI# is asserted). If U ADS,l is sampled asserted, the process jumps to step 640 to walt two clock cycles before taking ownership of the bus in step 645. If ADS# 'Is sampled deasserted, the process proceeds to step 625 to wait one clock before proceeding to step 630.

Step 630 determines whether ADS# is sampled asserted during the clock cycle following the assertion of BPRI#. If ADS# is sampled asserted, the process jumps to step 640 to wait two clock cycles before taking ownership of the bus in step 645.

If ADS# is sampled deasserted, the process proceeds to step 635 to wait one clock before proceeding to step 640.

In step 640 the process waits two clocks before proceeding to step 645. In step 645 the priority agent takes ownership of the bus and initiates a bus transaction. The process then returns to step 610 to service the next bus ownership request by a priority agent.

FIG. 7 illustrates a portion of the method of the present invention; specifically it shows how a symmetric agent requests bus ownership. The is the process (or rules) followed by a symmetiic agent in generating bus requests. The process starts in step 700. In step 705 the symmetric agent determines whether it needs ownership of the bus. If the symmetric agent needs ownership of the bus, 0 the process proceeds to step 715; otherwise the process stays in step 7 10.

In step 715 the symmetric agent asserts its BRO# output pin to request ownership of the bus (i.e., the syrrunetric agent asserts the BREQn# signal that it 0 0 drives to signal a request for bus ownership).

In step 720 the symmetric agent determines whether it has been granted ownership of the bus under the arbitration protocol. The symmetric agent knows that it has been granted ownership of the bus when the Rotating ID in its internal state tracking mechanism points to the symmetric agent. If the arbitration protocol has granted ownership of the bus to the requesting symmetric agent, the process jumps to step 725; otherwise the process jumps to step 7 10.

In step 725 the symmetric agent determines whether.it will be performing a bus-locked transaction. If so, the process proceeds to step 730 where the symmetric agent asserts the LOCK# signal to prevent all other agents from gaining ownership of the bus until the bus-locked transaction is completed. If the transaction is not bus-locked, the process jumps to step 735.

In step 735 the symmetric agent determines whether the transaction is a burst access (bursty transaction). A burst access transaction is a number of hich- 0 speed memory accesses to sequential memory locations. If the transaction is a burst access, the process proceeds to step 740 where the symmetric agent asserts the BRO# output pin (thereby asserting its BREQn# signal) until the burst transaction is completed. Continued assertion of the BR# pin prevents another syrrunetric agent Z:- from aainina, ownership of the bus until the burst access transaction is completed.

0 0 If the transaction is not bursty, the process jumps to step 745.

In step 745 the symmetric owner performs the transaction on the bus and proceeds to step 750 when the bus transaction is completed.

In step 750 the symmetric agent determines whether another syrnmetric agent is requesting ownership of the bus. If another symmetric agent is requesting ownership of the bus then in step 760 the symmetric owner deasserts the BRO# output pin (thereby deasserting its BREQn# signal) to release the bus to the next symmetric owner. The process jumps from step 760 to step 7 10 to repeat the process.

In step 750 if another symmetric agent is not requesting ownership of the 0 0 bus then in step 755 the symmetric owner continues asserting the BR# pin to park 0 on the bus. While parked on the bus the symmetric owner can per-form transactions without having to first arbitrate for the bus. The process jumps from step 755 to r> step 725 to service any pending transaction requests.

It is appreciated that the present invention arbitration protocol may be carried out by state machines in the bus agents. For example, each symmetric agent may 0 0 have an internal state machine including the state tracking mechanism that implements the protocol. The priority agent may also include a state machine that implements the protocol. The details of the state machines are not described in order not to obscure the present invention. One of ordinary skill in the art can 01olmmsymKlc..-OW M 111-.--, 1 0.

easily provide suitable state machines to implement the present invention arbitration protocol given the above description and examples below.

IV. Examples

To further illustrate the present invention arbitration protocol, a number of examples are given. In the following examples, a square on a waveform indicates that either a request or a response is being driven on that signal by one of the agents. A circle on a signal indicates that the signal is being observed by the 0 aaents.

0 Symmetric Arbitration of a Single Agent After RESET#. Referring now to FIG. 8, waveforms illustrating bus arbitration initiated after a reset sequence are shown. BREQ[10]i'll, BPR.I#, LOCKI't, and BNRi# should be deasserted during RESETT#. (BREQ0# is asseried 2 clocks before RESET# is deasserted for initiaLization reasons.) Symmetric agents can begin arbitration in the clock after U ' signals. Once R.ESET,, is sampled deasserted by driving the BREQ[10]TT ownership is obtained, the symmetric owner can park on the bus as long as no other symmetric agent is requesting it. The symmetric owner can voluntarily release the bus to idle.

RESET# is asserted in TI, which is observed b all acents inT2. This y cl signal forces all agents to initialize their internal states and bus signals. In T3 or T4, 1 all agents deassert their arbitration request signals BREQ[10]r'r, BPR11# and 1 0 arbitration modifier signals BNRi'Tand LOCK4. The symmetric acents reset their 0 1 ownership state to idle and their Rotating ID to point to symmetric agent 3 (so that 0 bus agent 0 has the highest symmetric priority after RESET# is deasserted).

In T-7, the clock after RESET# is sampled inactive, symmetric agent 1 asserts BREQ1# to arbitrate for the bus. In T8, all symmetric agents observe active ZY BREQi# and inactive BREQ[0,2,3]#. During T8, all symmetric agents determine C ---1 ZM that symmetric agent 1 is the only symmetric agent arbitrating for the bus and therefore has the highest priority.. As a result, in T9, all symmetric agents update their Rotating ID to point to symmetric agent 1, the Agent DD of the new sy=eldc owner and its ownership state to busy, indicating that the bus is busy.

Starting from T8, symmetric agent 1 continually monitors BREQ[0,2,3]rrl to determine if it can park on the bus. Since BREQ[0,2,3]# are observed inactive, symmetric agent 1 continues to maintain bus ownership by keeping BREQ1# asserted (i.e., symmetric agent 1 parks on the bus).

1n T15, symmetric agent 1 voluntarily deasserts BREQ1# to release bus ownership, which is observed by all agents in T16. InTI7 all symmetric agents update their ownership state from busy to idle. This action reduces the arbitration latency of a new symmetric agent to two clocks on the next arbitration event.

Svmsnetric Arbitration with no LOCK#. Referrina now to FIG. 9, waveforms Ulustrating arbitration between two or more symmetric agents while LOCK# and BPRIT# stay inactive are shown. Because LOCKT# and BPRI# remain inactive, bus ownership is determined based on a Rotating ID and bus ownership state. The syrnrnetric agent that wins the bus releases it to the other agent as soon as possible. In one embodiment, symmetric agents are lirrted to one bus I transaction, unless either the outstanding operation is locked or no other agent C7 0 wants the bus). The syriunetric agent may re-arbitrate one clock after releasing the bus. Also note that when a symmetric agent n issues a transaction to the bus, 0 BREQn# should stay asserted until the clock in which ADS# is asserted.

In TI, all arbitration requests BREQ[3:0]7'r and BPRIT"? are inactive. The bus is not stalled by BNR#. The Rotating IDs point to syn-Lmetric agent 3 and the bus ownership state is idle. Hence, the round-robin arbitration priority is 0, 1,2,3.

In 72, symmetric agent 0 and symmetric agent I activate BREQO# and BREQ 1# respectively to arbitrate for the bus. In T3, all symmetric agents observe inactive BREQ[12]# and active BREQ[L0]#. Since the Rotating ID is 3, during 0 C1 n, all symmetric agents deterrriine that symmetric agent 0 has the highest priority 0 and is the next symmetric owner. In T4, all symmetric agents update the Rotating ID to zero and the bus ownership state to busy.

Since BPRI# is observed inactive in T3 and the bus is not stalled, in T4, symmetric agent 0 can begin a new Request Phase. (If BPRI'm has been asserted in T3, the arbitration event, the updating of the Rotating ID, and ownership states would not have been affected. However, symmetric agent 0 would not be able to drive a transaction in T4). In T4, syrrunetric agent 0 initiates request phase Oa.

In response to active BREQ1# observed in T3, symmetric agent 0 deasserts BREQ0# in T4 to release bus ownership. Since symmetric agent 0 has another internal request, it immediately reasserts BREQO# after one clock in T5.

In T5, all symmetric agents observe BREQG# deassertion, the release of bus ownership by the current symmetric owner. During TS, all symmetric agents 0 0 recognize that symmetric agent 1 now remains the only symmetric agent arbitrating 0 0 C, for the bus. In T6, all symmetric agents update theirRotating ID to point to symmetric agent 1. The ownership state remains busy.

1 Symmetric agent 1 assumes bus ownership in T6 and generates request phase 1 a in T7 (three cycles from request Oa). In response to active BREQO# observed in T5, symmetric agent 1 deasserts BREQ I# in T7 along with the first c) clock of the Request Phase and releases symmetric ownership. Meanwhile, symmetric agent 2 asserts BREQ2# to arbitrate for the bus. In T8, all symmetric agents observe inactive BREQ1#, the release of ownership by the current syrnmetric owner. Since the Rotating ID is one, and BREQO#, BREQ2# are active, all symmetric agents determine that symmetric agent 2 is the next symmetnc owner. In T9, all symmetric agents update their Rotating ID to point to symmetric agent 2. 71e ownership state remains busy.

In TIO, (three cycles from request la) symmetric agent 2 drives request 2a.

0 In response to active BREQO# observed in T9, symmetric agent 2 deasserts BREQ2# in TIO. In T1 1 all symmetric agents observe inactive BREQ2# and active BREQO#. During T 11, they recognize that syr=etric agent 0 is the only symmetric t> 0 agent arbitrating for the bus. In T12, all syrnrnetric agents update their Rotating ID 0 0 to point to symmetric agent 0. The ownership state remains busy.

In T12, symmetric agent 0 assumes bus ownership. In T13 symmetric 0 agent 0 initiates request Ob (three cycles from request 2a). Because no other agent has requested the bus, symmetric agent 0 parks on the bus by keeping its BREQG# signal active.

Bus Exchange Symmetric and Priority Agents with no LOCK#. Referring 0 now to FIG. 10, waveforms illustrating bus exchange between a priority agent and 0 W two symmetric agents are shown. A symmetric agent relinquishes physical bus 0 ownership to a priority agent as soon as possible. A maximum of one unlocked ADS# can be aenerated by the current s mmetric bus owner in the clock after C y BPR.Wrt is asserted because BPRI# has not yet been observed. Note that the symmetric bus owner (Rotating ID) does not change due to the assertion of BPRI#.

1 1 BPRI# does not affect symmetric agent arbitration, or the symmetric bus owner.

c) Finally, note that in this example BREQO# should remain asserted until T12 bezause transaction Ob has not yet been driven. An agent can not drive a transaction 0 unless it owns the bus in the clock in which ADS# is to be driven for that transaction.

In FIG. 10, before T I agent 0 owns the bus. The Rotating ID points to C symmet.fic agent 0. The ownership state is busy. In T3, the priority agent asserts C W BPRI# to request bus ownership. In T4, symmetric agent 0, the current owner, issues its last request Oa. In T4, all symmetric agents observe BPRI# active, and guarantee no new unlocked request generation starting in T5.

In T3, the priority agent observes inactive ADS# and inactive LOCK# and determines that it may not gain request bus ownership in T5 because the current request bus owner might issue one last request in T4. In T5, the priority agent 0 observes inactive LOCK# and determines that it owns the bus and may begin issuing requests starting in T7, four clocks from BPRI# assertion.

0 The priority agent issues two requests, I/0a. and I/0b, and continues to assert BPRI# through TIO. In TIO, the priority agent deasserts BPRI# to release bus ownership back to the symmetric agents. In T 10, symmetric agent 1 asserts BREQ 1 # to arbitrate for the bus.

In T1 1, symmetric agent 0, the current symmetric owner observes inactive BPRI# and initiates request Ob in T13 (three clocks from the previous request.) In response to active BREQl#r, symmetric agent 0 deasserts BREQG# in T13 to release symmetric ownership. In T14 all symmetric agents observe inactive BREQO#, the release of ownership by the current symmetric owner. Since BREQ11# is the only active bus request they assign symmetric agent 1 as the next symmetric owner. In Z T15 all symmetric agents update their Rotating 1D to point to symmetric agent 1.

C Symmetric Priority Bus Exchange During LOCK#. Referring now to FIG. 11, waveforms fflustrating an ownership request made by both a symmetric and a priority agent during an ongoing indivisible sequence by a symmetric owner are 0 0 shown. When this is the case, LOCK# takes priority over BPRI11r. That is, the symmetric bus owner does not give up the bus to the priority agent while it is 0 driving an indivisible locked operation. Note that symmetric agent 1 can hold bus J 0 ownership even though BPRI# is asserted. Like the BREQ[10]# signals, if the priority agent is going to issue a transaction, BPRI# should not be driven inactive 0 until the clock in which ADS# is driven asserted.

Before TI, symmetric agent 0 owns the bus. In TI, symmetric agent 0 initiates the first transaction in a bus locked operation by asserting LOCK# along i with request Oa. Also in T I, the priority agent and symmetric agent 1 assert BPRI# and BREQ1#, respectively, to arbitrate for the bus. Symmetric agent 0 does deassert BREQ0# or LOCK# since it is in the rniddle of a bus locked operation.

In T7, symmetric agent 0 initiates the last transaction in the bus locked operation. At the request's successful completion the indivisible sequence is complete and symmetric agent 0 deasserts LOCK4# in T1 1. Since BREQ1# is observed active in T 10, symmetric agent 0 also deasserts BREQO# in T 11 to release symmetric ownership.

The deassertion of LOCK# is observed by the priority agent in T12 and it begins new-request generation from T13. The deassertion of BREQ0# is observed by all symmetric agents and they assign the symmetric ownership to symmetric agent 1, the symmetric agent with active bus request. In T13, all symmetric agents update their Rotating ED to point to symmetric agent 1, the Agent ID of the new 0 symmetric owner.

Since symmetric agent 1 observed active BPRI# in T12, it guarantees no new request generation beginning T13. In T13, the priority agent deasserts BPRI#. In T15, three clocks from the previous request and at least two clocks from BPRI-rr deassertion symmetric agent 1, the current symmetric owner, issues request I a.

The arbitration protocol of the present invention solves the problems of prior arbitration protocols detailed in the background of the invention.

First, the present invention provides for varying numbers of agents on the I bus without additional logic or changes to existing external logic. This is possible I 4n due to the distributed nature of the symmetric agent arbitration protocol. For 0 example, a uniprocessor computer system initially has one processor (symmetric agent). Under the arbitration protocol of the present invention, the single symmetric processor will park on the bus because no other requests from symmetric agents will occur. Addii-.g additional processors is done by simply MR 0 int ' i 180,0 1 inserting the added processors into empty processor sockets on the computer system board. Since each processor tracks the bus states with their own internal state tracking state machine, no additional logic is required to be added to the motherboard.

Second, the present invention arbitration protocol is fair in arbitrating between symmetric agents. The round-robin nature of the protocol provides essentially an equal sharing of the bus between multiple symmetric agents.

Thi.rd, the latency of bus exchange between symmetric agents is small. In a "latched bus" environment, a symmetric agent can obtain ownership of the bus in two clocks when arbitrating from idle ownership state. From the busy ownership state, a symmetric agent obtains ownership of the bus in three or four clocks depending on whether the symmetric owner is or is not parked on the bus.

Fourth, the present invention arbitration protocol allows a symmetric agent to retain ownership of the bus for burst accesses. This maintains, in a multiprocessor environment, the performance advantage of burst accesses by individual aaenEs.

Fifth, the present invention arbitration protocol is flexible to support the needs of 1/0 devices. The priority agent protocol gives a priority agent ownership C) 0 of the bus within 2-4 clocks unless the current bus owner is performing bus-locked transaction. In one embodiment, the longest bus locked transaction performed by a symmetric agent is a sequence of: lock memory read, lock memory read, lock resolution, lock memory write, lock memory write. Even in this worst case, the worst case arbitration latency for 1/0 devices is met.

Finally, the present invention arbitration protocol supports a "latched bus" whereby signals between multiple agents are transmitted in one clock cycle and aRents respond to the transmitted signals in the following clock cycle. The latched 0 Z;I 0 buc is advantageous in computer system because inter-processor (transmissioil, --- - - 36 delays are separated from intra-processor delays (processor delays in responding to input signals). This makes processor design more independent from board level design.

Certain advantages of the present invention have been particularly described. other benefits and advantages of the present invention, though not particularly pointed out, are evident from the above description.

In our copending Patent Application No. 9500836.3 (2287621) from which the present case has been divided, there is described and claimed a computer with distributed bus arbitration comprising:

bus means for providing a communication interface; a plurality of agents coupled to said bus means, said 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 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 f irst 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.

In our copending Application No. 9800827.9 (2318487) there is described and claimed a computer system comprising:

main memory; plurality of symmetric agents which includes 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 - 38 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 seal.

In our copending UK patent application No.

9812943.0 there is described and claimed multiprocessor computer system comprising:

main memory; plurality of processors coupled to said memory via a first bus, each processor including an arbitration unit; a plurality of digital signal processors coupled to a second bus; a digital signal processor arbitration unit coupled between said first bus and said second bus; each arbitration unit is capable of arbitrating for ownership of said first bus by asserting a request signal over said first bus, said arbitration units further receiving said request signals from another arbitration units, said arbitration units capable of asserting a lock signal during ownership of said first bus during a locked transaction; and said arbitration units further including a priority agent detection logic for detecting a first bus ownership request from a priority agent, wherein an arbitration unit releases ownership of said first bus when a priority agent request is detected, unless said bus transaction is a locked transaction.

1 W M wWP - OW9M1 110- P 1..

Claims (8)

1. An apparatus for use comprising of: a priority agent having an arbiter unit operable to assert a priority signal to request ownership of a bus from a symmetric arbitration unit coupled to said bus, said arbiter unit obtains ownership of said bus within a pre-determined number of clock cycles after the assertion of the priority signal unless a lock signal has been asserted by said symmetric arbitration unit owning said bus.

in a computer system

2. The apparatus of claim 1, wherein said priority agent is operable to be coupled to a plurality of input/output (1/0) devices.

3. The apparatus of claim 2, wherein said priority agent comprises a bridge circuit providing an interface between the 1/0 devices and said bus, and said arbiter unit of said priority agent is operable to arbitrate for ownership of said bus on behalf of said 1/0 devices.

4. The apparatus of claim 3, wherein the predetermined number of clock cycles is equal to four.

5. A method for accessing a bus by a priority agent in a computer system, said method comprising the steps of:

an arbiter unit of said priority agent asserting a request signal to request ownership of the bus from a symmetric arbitration unit coupled to said bus; - 40 determining that a lock signal has not been asserted by said symmetric arbitration unit owning said bus; and obtaining ownership of said bus within a predetermined number of clock cycles after said arbiter unit of said priority agent asserts said priority request signal.

6. The method of claim 5, wherein said priority agent is operable to be coupled to a pluralityof input/output (1/0) devices.

7. The method of claim 6, wherein said priority agent comprises a bridge circuit providing an interface between the 1/0 devices and said bus, and said arbiter unit of said priority agent is operable to arbitrate for ownership of said bus on behalf of said 1/0 devices.

8. The method of claim 7, wherein the pr determined number of clock cycles is equal to four.