[_CD6_]<dragon7.0>Documentation>ArbiterDoc.tioga!1

DRAGON ARBITER

DRAGON PROJECT — FOR INTERNAL XEROX USE ONLY

The Dragon Arbiter

Ed McCreight

Written December 2, 1986 Revised July 1, 1987

Abstract: The Dragon arbiter is one of a set of identical chips that collectively decide how to grant time-multiplexed control of the Dragon's Dynabus to requesting devices. This document is its interface specification.

Keywords: arbiter, arbitration, scheduling

FileName: /Indigo/Dragon7.0/Documentation/ArbiterDoc.tioga, .interpress

XEROX Xerox Corporation
Palo Alto Research Center
3333 Coyote Hill Road
Palo Alto, California 94304

Dragon Project - For Internal Xerox Use Only

Contents

1. General Description

2. Pin Description

3. Protocols

4. Arbitration Pipeline Stages

5. Unresolved Issues

ChangeLog

1. General Description

The Dragon arbiter chip is part of a Dragon computer system. There is one arbiter chip on each Dragon board, located physically near the board-to-backpanel interface. The main function of this set of identical chips is to control time-multiplexed access to the DynaBus, Dragon's main data bus.

The arbiter implements six discrete priority levels: 0 (most urgent) to 6 (least urgent), except for 2 (reserved to represent Hold). Smaller priority numbers have more urgent priority. Dynabus access is always granted to a requester requesting at most urgent priority. Within each discrete priority level, grants are assigned (approximately) round-robin.

Each arbiter has eight device request ports. Each of these ports can have up to three requests pending, of two types each. Associated with each type is a priority level [0..7) (2 and 7 are illegal) and a packet length (2 or 5 cycles). These sixteen parameter pairs (8 requesters x 2 types) are loaded into the arbiter during system initialization via the DBus scan path.

The two types of request at a single port are called L and H. The priority number assigned to type L must be no smaller than that assigned to type H, because a type H request is preferred over a type L request within the same port, independent of the priority numbers assigned to them.

There can be at most eight arbiters in a Dragon system. These arbiters exchange priority information across the system backpanel. Each arbiter drives one three-bit port and receives the other seven. A fixed pinout for output and input ports is implemented by rotating the inter-arbiter wiring, a nice trick suggested by J. Gastinel.

The arbiter also computes system-wide shared, owner, and stop, and serves as DBus controller.

2. Pin Description

2.1 Request ports

Each of the 8 ports of an arbiter consists of three wires: two input wires and a single output wire. The 2 input wires of port i are named DReq[0] and are encoded as follows:

- Non-FIFO mode:

0: No request

1: Hold

2: Low priority request of length LoLen

3: High priority request of length HiLen

- FIFO mode:

0: No request

1: Hold

2: Low priority request of length 2

3: Low priority request of length LoLen (LoLen should probably be setup as 1 to permit 5 cycle packets).

The single output wire of port i is named DGrant[i], and it is 1 during every grant cycle to port i and 0 otherwise.

This specification allows an arbiter to make back-to-back grants to the same requester, but the first arbiter implementation will not be able to follow a short grant immediately with another grant to the same requester.

2.2 Common grant bus

The following wires are available in common to every requester. Not every requester needs both, or even one.

DHiP - Output - One cycle before the first cycle of a grant, this wire is high if the arbiter is responding to a high-type request from the grantee device, and low otherwise. Its state at other times is undefined.

DLongGrant - Output - One cycle before the first cycle of a grant, this wire is high if the arbiter is responding to a long-packet (5-cycle) request from the grantee device, and low otherwise (2-cycle). Its state at other times is undefined.

2.3 Inter-Arbiter negotiation bus

Requesters don't need to know about this. There are eight three-bit backpanel buses across which arbiters exchange priority information across the system backpanel. These wires are passively pulled high on the backpanel:

ArbReq[j] - Input/Output - A three-bit field that carries the minimum (best) priority level at which arbiter j has any device requesting. If no device is requesting service from arbiter j, the value of this field is 7, NoRequest. If any of the arbiter's requesters is asserting Hold, it is as if that requester is also making a request at priority value 2, Hold.

There is also a single wire to signal the last cycle of a transaction.

LastCyc - Input/Output - Asserted low by the arbiter (if any) that is currently holding the system grant, to indicate that his transaction has not received as many cycles as it needs.

2.4 DBus control

The following signal pairs are buffered and pipeline-delayed from the backpanel to the board's devices:

DBClock -> DDClock

DBDataIn -> DDDataIn

DBExecute -> DDExecute

DBFreeze -> DDFreeze

DBnReset -> DDnReset

One signal goes the other way if the arbiter is "selected":

DBDataOut <- DDDataOut

The arbiter receives but does not pass on one extra backpanel signal:

DBAddr - When this signal is asserted, all arbiters "deselect", and DBDataIn and DBClock are used to shift an address into a 16-bit device address register. When DBAddr is de-asserted, the arbiter compares the high-order 6 bits of this address register against six bits read from the backpanel. If there is an exact match, then a decoder on the next 2 bits is enabled, and three of these four select wires are made available on the board

DDSel1
DDSel2
DDSel3

The remaining eight bits of the address register are also wired to the board

DDAddr[8-15]

The arbiter behaves as DBus devices 0-255 on its board, in that it is enabled only by the invisible DDSel0, and pays no attention to DDAddr[8-15]. As part of its scan path, it reads three arbiter pins

DDMemo[0-2]

each of which can be connected to any of the eight DDAddr[8-15] pins, so simple PC-board interconnection can communicate up to 3*log2(8) = 9 bits of information to the system DBus controller.

2.5 Shared/Owner Merging

The following signals come separately from each requester ( i IN [0..4) ):

DShared[i] - Input - Indicates whether requester i holds a copy of the contents of a memory location.

The following signals are exchanged on the system backpanel ( j IN [0..8) ):

BOwner - Input/Output (Wire-OR) - Indicates whether any requester in the system claims ownership of a memory location.

BShared[j] - Input/Output - Indicates whether any requester attached to arbiter j holds a copy of the contents of a memory location.

The following signals go in common to all requesters:

DOwner - Input - Indicates whether any requester attached to this arbiter claims ownership of a memory location.

SysShared - Output - A signal computer identically by all arbiters, indicating whether any requester attached to any arbiter holds a copy of the contents of a memory location.

SysOwner - Output - Indicates whether any requester in the system claims ownership of a memory location.

2.6 Overhead

ArbIndex (3 bits), from the backpanel, I suppose.

Vdd

Gnd

Clock

3. Protocols

Each arbiter port is parameterized by 9 bits loaded via the DBus. Those 9 bits are:

and are interpreted as follows:

HiP: 3 bit priority of a high-priority request. 0 is highest, 7 is lowest. 2 & 7 are forbidden (2 is for hold, 7 for idle).

HiLen: 1 bit indicating length of high-priority packets (0 means 2 cycles, 1 means 5 cycles).

LoP: 3 bit priority of a high-priority request. 0 is highest, 7 is lowest. 2 & 7 are forbidden (2 is for hold, 7 for idle).

LoLen: 1 bit indicating length of high-priority packets (0 means 2 cycles, 1 means 5 cycles).

nFIFOEna: 1 bit indicating FIFO mode is enabled for this port (0 means enabled, 1 means disabled).

The arbiter is further parametrized with ArbId, a five-bit field

4. Arbitration Pipeline Stages

It is helpful here to consult ArbiterImpl.mesa, the Rosemary RTL simulation of the Arbiter. This can be found in [Indigo]<Dragon>Top>Arbiter24.df. Italics are used to indicate pipeline registers.

0: drqIn[i] in arbiter j is loaded from the DRQ[j][i].Req wire pair, which carries a request from arbiter j's requester i.

1: At this stage, each requester i is handled independently. The request counters, one for each type t, drqCtrs[i][t], are updated with new counts that reflect the contents of drqIn[i] and grants from stage 4. The hold flipflop, drqHold[i], is updated. The best request for a port, together with its type and length, are registered in drqPrior1[i] and drqInfo1[i].

2: At this stage the separate requests i of arbiter j are combined to form a common request, arbReqOut[j].

3: All arbiters exchange priority information over the backpanel using the ArbReq wires, and LastCycle, and these are recorded in arbReqIn and lastCycIn, which are identical in all arbiters.

Each arbiter computes the identity of its own best requester, taking both priority and precedence into account. This requester is coded in unary form in bestDev, and its type and length are recorded in bdInfo3[j].

4: The information in bdInfo3[j] is sent to all requesters attached to arbiter j on DHiPGrant[j] and DLongGrant[j]. Requesters can use this information to set up multiplexers in anticipation of receiving grant in the next cycle.

Each arbiter decides first whether a grant will be made at all, globalGrantStart, and second whether the grant will be made to itself, localGrantStart. The priority of the winning request is computed on all arbiters, and the winning arbiter computes dGrant, a unary encoding of grantees.

The unary-coded representation of the best local device from the previous stage, bestDev is re-coded in binary and stored in bestDevCoded.

The number of cycles remaining in the current local grant, localBusCyclesLeft, is computed, and LastCyc is asserted FALSE if necessary.

5: The winning arbiter communicates dGrant as DRQ[j][i].DGrant to all devices on its board.

The board rover pointer, arbRovers[p], for the winning priority level is recomputed identically in all arbiters.

The device rover pointer, devRovers[p], for the winning priority level is recomputed only in the winning arbiter.

5. Unresolved issues

The DBus isn't right yet.

ChangeLog

McCreight December 2, 1986 4:22:02 pm PST

First version.

McCreight December 22, 1986 10:42:16 am PST

Added owner, shared.

McCreight March 5, 1987 6:43:53 pm PST

Revised to reflect RTL simulation.