Symmetric Agent Arbitration—Democracy at Work
A symmetric system is one in which any processor is capable of handling (i.e., executing) any task. The job of the SMP (symmetrical multiprocessing) OS is to attempt to keep all of the processors equally busy at all times (in other words, executing various tasks). At a given instant in time, one or more of the logical processors may require ownership of the Request Phase signal group in order to communicate with an external device. In a well-balanced system, the bus arbitration scheme used to decide which of the processors gets ownership next is based on rotational (symmetric) priority—each of the processors has equal importance.
No External Arbiter Required
Refer to Figure 45-1 on page 1152. The Pentium® 4 processors that make up a cluster (i.e., the group of processors that reside on the FSB) have a built-in rotational priority scheme. No external arbitration logic is necessary to determine which of the logical processors require ownership of the Request Phase signal group and which should acquire ownership next. Each of the physical processors always keeps track of:
whether any of them currently owns the Request Phase signal group,
which of them owned the Request Phase signal group last (or still owns it),
and which of them gets to use it next (assuming any of them are requesting ownership).
Figure 45-1. System Block Diagram
In order for them to track this information, each physical processor must know its own Physical Processor ID as well as the ID of the physical processor that last gained ownership of the Request Phase signal group. If a physical processor knows who had ownership last (or still has it), then it knows the physical processor whose turn it is next (because it's a rotational scheme).
The Arbitration Algorithm
One Arbiter Per Physical Processor
Each physical processor's FSB Interface Unit contains an arbiter that services requests received from each of the logical processors within the physical processor. The arbiter, in turn, then asserts the physical processor's BR0# output pin to request ownership of the Request Phase signal group.
When a physical processor acquires ownership of the FSB, it services requests from the two logical processors in round-robin order.
The Rotating ID
As stated earlier, each physical processor must keep track of which of the physical processors was the last to acquire Request Phase signal group ownership. This is referred to as the Rotating ID. When reset is asserted, the Rotating ID is reset to three in all of the logical processors. This means that all of the physical processors believe that physical processor three owned the Request Phase signal group last and therefore physical processor zero should acquire ownership next (if it does in fact request ownership). The sequence in which the physical processors acquire ownership (if all of the physical processors were asking for ownership when reset was deasserted) is 0, 1, 2, 3, 0, etc.
The example just cited assumed a system with four Xeon MPs with or without Hyper-Threading enabled. Table 45-2 on page 1153 provides a list of some additional configurations.
| Processor Type | Hyper-Threading Enabled? | Number of Physical Processors | Logical Processor ID Assignments | Initial Rotating ID |
|---|---|---|---|---|
| Xeon MP | N | 4 | 0, 1, 2, and 3. | 3 |
| Xeon MP | Y | 4 | 0, 1, 2, 3, 4, 5, 6, and 7. | 3 |
| Xeon DP | N | 2 | 0 and 1. | 1 |
| Xeon DP | Y | 2 | 0, 1, 2 and 3. | 1 |
| Extreme Edition | N | 1 | 0. | 0 |
| Extreme Edition | Y | 1 | 0 and 1. | 0 |
| Desktop Pentium® 4 | N | 1 | 0. | 0 |
| Desktop Pentium® 4 | Y | 1 | 0 and 1. | 0 |
| Celeron | N | 1 | 0. | 0 |
| Celeron | Y | 1 | 0 and 1. | 0 |
The Busy/Idle Indicator
General
Refer to Figure 45-2 on page 1154. In addition to the Rotating ID maintained by each of the physical processors, the arbiter within each of the physical processors must also keep track of whether the last physical processor that acquired ownership of the Request Phase signal group retained ownership or has released it (and therefore none of them currently owns it). When the last to acquire ownership retains ownership, the ownership state is said to be Busy. If the previous owner surrendered ownership and none of them currently owns the Request Phase signal group, the ownership state is said to be Idle. Each of the physical processors maintains an internal Busy/Idle state indicator to indicate whether the Request Phase signal group ownership state is currently Busy or Idle.
It is incorrect to think of Busy as meaning that one of the physical processors currently owns the Request Phase signal group and is using it. Rather, it only means that the physical processor has retained ownership—it may or may not currently be using the Request Phase signal group.
Reset's Effect on the Busy/Idle Indicator
As shown in Figure 45-3 on page 1155, the assertion of reset causes the Busy/Idle indicator to enter the Idle state.
The Idle Loop
In Figure 45-4 on page 1155, the Busy/Idle indicator remains in the Idle state as long as no processor has asserted its BR0# output pin to request ownership of the Request Phase signal group to initiate a new transaction.
Transition from Idle to Busy
When the arbiter within any physical processor asserts its BR0# output pin to request ownership of the Request Phase signal group, the arbiters within each of the other physical processors sample it asserted on the next rising-edge of BCLK0. As a result, one BCLK cycle later symmetric ownership of the Request Phase signal group passes to the physical processor that is asserting its BR0# pin and that is next in the rotation. In the same BCLK cycle, the Busy/Idle indicator within the arbiter of each physical processor transitions from the Idle state to the Busy state (see Figure 45-5 on page 1156).
Bus Parking
When the physical processor that just acquired ownership initiates a transaction (i.e., it asserts ADS# and drives out its transaction request), it has two options:
- If it deasserts its BR0# output pin at the same time it asserts ADS#, it is giving up ownership of the Request Phase signal group after it finishes the transaction's Request Phase (either because it doesn't have a second transaction to issue on the heals of the first transaction, or because it detected a bus ownership request issued by another physical processor).
- See Figure 45-6 on page 1157. If it keeps its BR0# output pin asserted when it asserts ADS#, it is signaling that it intends to retain ownership of the Request Phase signal group after it finishes issuing the current transaction request. It will do this for one of the following reasons:
- It is starting the first transaction of a locked transaction series (see “Pentium® 4 Locked Transaction Series” on page 1177 for more information) and keeps its BR0# pin asserted to temporarily prevent ownership from passing to another physical processor.
- No other physical processor is requesting ownership, the current owner doesn't have another transaction to issue immediately, but the current owner was configured to permit Bus Parking at power-up time (see“Bus Parking Option” on page 868).
If a processor is successful at retaining ownership until such time as it may require the use of the Request Phase signal group again, parking provides faster access to the Request Phase signal group (because you don't have to issue a request for the current symmetric owner to surrender ownership).
When a processor parks ownership on itself, it may retain ownership until another processor requests ownership (i.e., until it detects the assertion of another processor's BREQ signal). In other words, be fair to the other processors—don't hog the bus.
Preemption by Another Physical Processor
Refer to Figure 45-7 on page 1158. Assume that the Busy/Idle indicator is in the Busy state because a physical processor has been using the Request Phase signal group. One or more other physical processors assert their respective BR0# output pins to request ownership. In this case, the Busy/Idle indicator remains in the Busy state as ownership passes from one physical processor to another (from one BCLK cycle to the next).
Transitioning Back to the Idle State
Refer to Figure 45-8 on page 1159. Assume that a physical processor acquires ownership of the Request Phase signal group, initiates a transaction, and deasserts its BR0# output pin when it starts the transaction. All of the physical processors will detect this on the next rising-edge of BCLK0 and all of their Busy/Idle indicators transition from the Busy to the Idle state.
Requesting Ownership
Introduction
Refer to Figure 45-9 on page 1160 (and note that, although not shown, the system board designer has placed pull-up resistors on the BREQ signal line traces). The temptation is great to think that physical processor 0 uses its BR0# output to request ownership, physical processor 1 uses its BR1# output, etc., but it's not true. When any physical processor wants to issue a new transaction request, it uses its Bus Request signal, BR0#, to request ownership. On a Xeon MP, BR[3:1]# are inputs that are sampled to see if any of the other three physical processors are also requesting ownership at the same time. If physical processor 0 is issuing a request, the BREQ0# signal trace on the system board is asserted. If physical processor 1 is issuing a request, the BREQ1# signal trace is asserted, etc. Each of the physical processors knows which of the BREQn# signal traces belongs to it and which belongs to each of the other processors.
Figure 45-9. Bus Request Interconnect
Example of One Symmetric Agent Requesting Ownership
Figure 45-10 on page 1161 illustrates physical processor 0 requesting ownership. The following list describes the figure.
Prior to the rising-edge of BCLK0 in clock one, none of the physical processors were requesting ownership (e.g., immediately after reset removal). The FSB ownership state within each of them is Idle and the last one that had ownership was physical processor 3 (note that this is the condition immediately after reset is removed).
During the clock immediately prior to clock 1, physical processor 0 needs to perform a transaction and asserts its BR0# output (which is attached to the BREQ0# trace) to indicate this.
On the rising-edge of BCLK0 in clock one, physical processors 1, 2, and 3 detect that physical processor 0 is requesting ownership. A change in the state of the BREQn# signals from one clock to the next is an arbitration event.
One clock later, during clock two, all of the physical processors change the state of their Rotating ID indicator to indicate that physical processor 0 is now the owner. They also change their Busy/Idle indicators to indicate that the ownership state is now Busy—in other words, one of them now owns the Request Phase signal group. Note that the Rotating ID and the Busy/Idle indicators are strictly internal to the processors and are not presented on any output pins.
In clock two, physical processor 0 takes ownership of the Request Phase signal group and drives out its request and asserts ADS# (Address Strobe) to indicate that a new transaction is being issued to the FSB. It leaves BREQ0# asserted either because it wants to issue another transaction request immediately after this one, or in case it needs the bus again in the future (see “Bus Parking” on page 1156).
Figure 45-10. Example of One Processor Requesting Ownership
Example of Two Symmetric Agents Requesting Ownership
Figure 45-11 on page 1163 illustrates a case where physical processors 0 and 3 are both requesting ownership. Arbitration events (where the physical processors must decide which of them ownership will pass to) occur on the rising-edge of BCLK0 in clocks 1, 3, and 5. The following list describes the figure.
Prior to clock 1, none of the physical processors were requesting ownership. The previous owner was physical processor 2 and the ownership state is currently Idle (i.e., none of the physical processors has ownership).
On the rising-edge of BCLK0 in clock 1, requests from physical processors 0 and 3 are both seen. This is an arbitration event.
In clock 2, all physical processors change the Rotating ID from 2 to 3 and the ownership state from Idle to Busy. Physical processor 3 takes ownership of the Request Phase signal group, issues a request and asserts ADS# (Address Strobe) to indicate that a new transaction request is being issued. As it's issuing the request, physical processor 3, recognizing that one (or more) other physical processors are also requesting ownership, does the polite thing—it deasserts BREQ3# to relinquish ownership.
On the rising-edge of BCLK0 in clock 3, an arbitration event is detected (physical processor 3 has relinquished ownership). All physical processors see that only physical processor 0 is requesting ownership. Having been polite to physical processor 0, physical processor 3 reasserts BREQ3# to request ownership again (because it has another transaction to issue).
One clock later (in clock 4), all physical processors change their Rotating ID to 0 and the ownership state stays Busy (there was a hand off of ownership from one to the other).
In clock 4, physical processor 0 begins to drive its request onto the Request Phase signal group and asserts ADS#. Having detected BREQ3# asserted, it also deasserts BREQ0# to hand ownership back to physical processor 3.
On the rising-edge of BCLK0 in clock 5, an arbitration event is detected (physical processor 0 has relinquished ownership). All physical processors see that only physical processor 3 is requesting ownership.
In clock 6, all physical processors change their Rotating ID to 3 and the ownership state stays Busy.
In clock 6, physical processor 3 begins to drive its request onto the Request Phase signal group and asserts ADS#. It keeps BREQ3# asserted either because it has another transaction request to issue or to park ownership on itself in case it needs in the future.
Definition of an Arbitration Event
An arbitration event is defined as the passing of ownership (of the Request Phase signal group) from one physical processor to another. This occurs under the following circumstances:
When none of the BREQn# lines are asserted during one clock and then one or more are seen asserted in the next clock. An example of this can be seen in Figure 45-11 on page 1163 during the clock that precedes clock one.
When the current owner of the Request Phase signal group relinquishes ownership by deasserting its BREQn# signal and one or more of the other BREQn# lines have previously been asserted.
In either case, the physical processors must collectively decide (based on who owned it last and therefore who's next in the rotation) which of them will assume ownership of the Request Phase signal group in the next clock.
Once BREQn# Asserted, Keep Asserted Until Ownership Attained
Once a physical processor asserts its BREQn# signal, it must keep it asserted until it attains ownership. Once ownership is attained, the physical processor may or may not generate a transaction request (usually it will). If the physical processor no longer needs to generate the transaction request for which it originally asserted its BREQn#, it can deassert its BREQn# (without generating a transaction request) once it has attained ownership.
Example Case Where Transaction Cancelled Before Started
An example would be the case where the processor has a modified line sitting in one of its writeback buffers waiting to be cast back to memory (to make room for a new line being read into the L2 or L3 Cache). The processor had asserted its BREQn# to request ownership to do the cast out. Before it acquired ownership, however, another agent attained ownership and issued a read for the same line. The processor waiting to writeback the line snoops its writeback buffers, asserts HITM# (hit on modified line) and supplies the modified line directly to the agent that issued the read request. There is no longer a need to perform the writeback transaction, but the processor must keep its BREQn# asserted until it attains ownership. It then deasserts its BREQn# without starting a transaction. The other physical processors will see that it is yielding ownership on the next clock and, if any other physical processors have their BREQs asserted, ownership passes to the next in the rotation.