Low performance systems typically cannot afford high pin count packages because of increased package cost and the need for more expensive high density interconnection on board. With the bidirectional option, the DynaBus requires just 82 pins per package, providing an attractive solution for low end systems.

With the DynaBus confined to a single board, it is possible to build a high performance, compact 64-bit bus consisting of just one segment (Figure 5). Each DynaBus chip has an input and an output register connected to the bidirectional data port. These registers make a shorter cycle time possible, eliminating any computation (decoding, gating) during the transmission of data between chips.

Low cost mid range systems can also be built using a non-pipelined bidirectional DynaBus that spans multiple boards. Each board would have bidirectional buffers at its interface, much like VME or FUTUREBUS (see Figure 4 left). Such an implementation of Dynabus would not cycle as fast as a single board version or a pipelined version, but it would nonetheless provide an attractive low cost multi-board alternative.

One of the most interesting features of DynaBus is that it allows pipelining: a single DynaBus can be broken up into multiple bus segments separated by pipeline registers. These registers are placed at the input and output of each chip, module and board connecting to a DynaBus. During one clock cycle a signal starts out in one pipeline register, traverses one bus segment, and ends up in another pipeline register. The principal advantage of such pipelining is that the signal transit times on carefully designed short bus segments are a fraction of those on a single long segment whose length is the sum of the shorter segments. Small signal transit times in turn mean that bus clock frequency and therefore bus bandwidth is increased.

In all these configurations care must be taken in the physical layout of bus segments to minimize reflections and thereby increase the clock rate. Additionally, great care must be taken in distributing the clock to reduce skew. The DynaBus uses balanced transmission lines for bus segments and a special clock distribution scheme that minimizes clock skew.

Each device interacts with the arbiter via a dedicated port consisting of two request wires Request[0..1] and one Grant wire. Two other wires, HiPGrant, and LongGrant, are shared by all devices connected to the arbiter. The arbiter contains two types of ports, normal and memory, that a requesting device can be connected to. A normal port has two request counters, one for high priority requests and the other for low priority requests. In addition, each counter has an associated packet length. A device indicates whether it wants to make a low or high priority request via its Request wires. It may also use these wires to request and release Hold. Recall that while in the Hold state, the arbiter refuses to grant requests for sending request packets but continues to grant requests for sending reply packets. The Request wires for a normal port are encoded as follows:

A memory port consists of a single request FIFO, with a single priority for all incoming requests. A device indicates the length of a packet via its Request wires. It may also use these wires to seize and release the bus. The Request wires for a memory port are encoded as follows:

A device is permitted to have several pending requests within the arbiter, subject to an upper limit imposed by the arbiter implementation. A separate request is registered for each cycle in which the RequestOut wires are in the "add a request" state. For memory ports the FIFO guarantees that grants will be given in the order in which requests arrived.

The type of a port, as well as type-dependent characteristics (the lengths for the high and low priorities for a normal port, and the priority for a memory port) are provided at initialization time using the DBus. For a normal port the priority number of the high priority port (0, 1, 3, 4, 5, or 6) must be no greater than that of the low priority port, since lower priority numbers take precedence.

Grant is used by the arbiter to signal that a device has grant. Grant is asserted for as many cycles as the packet is long. If Grant is asserted in cycle i then the device can drive its outgoing bus segment in cycle i+1. HiPGrant and LongGrant describe a grant that is about to take place. In the cycle before Grant is asserted, HiPGrant tells the device whether the next grant will correspond to a high priority request or not; and LongGrant tells the device whether the next grant will correspond to a 5-cycle packet or not. Figures 10 and 11 show the timing of important signals at the pins of a requester during the arbitration and transmission of a two cycle and a five cycle packet, respectively. It is helpful to refer to the schematic of Figure 12 when reading the timing diagrams.

The arbiter provides two mechanisms for flow control. The first is arbitration priorities: An arbitration request to send a reply packet is always given precedence over an arbitration request to send a request packet. This mechanism alone would eliminate the congestion problem if devices were always ready to reply before the onset of congestion, but this is a severe requirement to place on all devices. To satisfy this requirement, a device must either be able to service packets at the maximum arrival rate, or it must have an input queue that is long enough so that it does not overflow even during the longest service time for a packet. For certain slow devices like the memory controller, servicing packets at arrival rate is clearly impossible and the queue lengths required to ensure no overflow are prohibitive.

The arbiter therefore provides a second mechanism suitable for slow devices. This mechanism involves the use of a special request called Hold to the arbiter. When the arbiter receives Hold from a device, it refuses to grant any further arbitration requests for sending request packets, but continues to grant requests for sending reply packets. This has the effect of choking off new request packets as long as Hold is being asserted by some device, and allows the device asserting Hold to clear the congestion. Of course, since the effect of Hold can never be instantaneous, especially in piplelined configurations, devices still need to provide headroom within their input queues to tolerate a few request packets while Hold takes effect. Devices must not use Hold with abandon, however, because the use of Hold decreases bus throughput.

In pipelined DynaBus configurations, the bus segments form a tree rooted at the bidirectional backpanel segment (Figure 13). All IC's are connected on the leaf segment, labeled A in Figure 13. The arbiter controls access to this segment independently of any board or module structure. Note that the existence of an input bus Ci, separate from Ai, means that all IC's in the system receive information from the DynaBus at the same time. This is important because it facilitates the computation of shared and owner bits from the values asserted by individual devices. If different devices received information at slightly different times, this computation would become considerably more complex.

The first, or header cycle, of a request packet contains a Command, a Mode bit, a DeviceID, and an Address (Figure 16). The Command identifies the transaction and indicates that the packet is a request rather than a reply packet. The Mode bit is used in protection checking by the receiving devices. The DeviceID identifies the initiator of the transaction, while the Address serves as a selector for a memory location or IO device register.

Most of the information in the header cycle of the request packet is replicated in the header cycle of the reply packet (Figure 17). In fact, only the fourth, fifth and sixth bits may be different. The fourth bit, which is part of the Command field identifies the packet as a reply. The fifth bit indicates if the transaction encountered an error, while the sixth bit tells if the the addressed location is shared or not.

The ReadBlock transaction is used to read a block of data from the memory system. If a cache is owner then that cache replies, otherwise memory replies.

The transaction WriteBlock is used to write a block of data into the memory system. Memory is overwritten, as are any cached copies. This transaction is used by producers of data outside the memory system to inject new data.

The transaction FlushBlock is used by caches to write dirty data being victimized back to memory. Caches do not listen to FlushBlocks, since they are already up to date, only memory does.

The transaction WriteSingle is used to write a 32-bit word of data to the memory system. Only cached copies of the word are updated, main memory is not. This transaction is used by caches to keep multiple copies of cached read/write data consistent.

The transaction ConditionalWriteSingle is used to perform an atomic read-modify-write to a 32-bit location in the memory system. Two 32-bit values old and new define the semantics as follows: if the contents of the target location equal old then new is written into the target. The previous value is always returned as the result (see Section 8.2.3). Only cached copies are affected, main memory is not. This transaction is used to synchronize the actions of multiple processors.

The IORead transaction is used to read a 32-bit word from an IO device.

The IOWrite transaction is used to write a 32-bit word to an IO device.

The BIOWrite transaction is used to broadcast write a 32-bit word to all IO devices of a given type.

The Map transaction is used to translate a 16-bit address space identifier and a 22-bit virtual page number to a 22-bit real page number and associated protection flags.

The DeMap transaction is used to remove all cached virtual to real translations that correspond to a given real page.

Occasionally, a device that has done an arbiter request has nothing to send when it gets grant. In this situation the device is expected to send a NoOp packet of the same length as the packet it had originally intended to send. It does this simply by putting a 0 value for HeaderCycleOut during its allocated header cycle. Thus, there is no special command to indicate NoOp.

A useful definition of data consistency must satisfy three criterea: it must allow interesting programs to be written; it must be simple to understand; and it must be practical to implement. A common way to define consistency is to say that all copies of any given location have the same value during each clock cycle. While this definition is adequate for writing programs and easy to understand, it is hard to implement efficiently when the potential number of cached copies is large. Fortunately, there is a weaker definition that is still sufficient for programming, but is much easier to implement in a large system. It is based on the notion of serializability.

Figure 20 shows an abstract model of a shared memory multiprocessor that will be used to define serializability. Each processor has a private line to shared memory over which it issues the commands Fetch(A) and Store(A, D), where A is an address and D is data. For Fetch(A) the memory returns the value currently stored at A; for Store(A, D) it writes the value D into A and returns an indication that the write has completed. Let the starting time of an operation be the moment a request is sent to shared memory, and the ending time the moment a response is received by the processor.

A computation C on this abstract model consists of N sequences of fetches and stores, one sequence for each of the processors. A computation transforms the initial state I of the shared memory into a final state F, but does not have any other visible effect. The Fetches and Stores of C are said to be serializable if there exists some global serial order of all the N sequences such that if the operations were performed in this order, without overlap, the same final state F would be reached starting from the same initial state I (two operations p and q overlap if the starting time of p is before the ending time of q and the starting point of q is before the ending time of p). The serial order must, of course, also preserve the semantics of Fetch and Store: the value returned by a Fetch(A) in this global sequence must have been the value stored by the most recent Store(A, .), or A's initial value in I if no such Store exists.

Given this definition of serializability, a shared memory multiprocessor is said to maintain data consistency if there is an algorithmic procedure for serializing the Fetches and Stores for any computation C on this machine. This procedure takes the N sequences of Fetches and Stores and produces a single global sequence that has the same effect on shared memory. The procedure, of course, depends on concrete implementation details of the multiprocessor. For example, if the multiprocessor has a single port memory with no caches, the transformation of the N sequences to the global sequence is trivial. For a DynaBus based multiprocessor that has processor caches, the procedure depends on details of the cache consistency algorithm and certain synchronization properties enforced by caches and memory controllers.

This definition also has a simple and intuitive interpretation. If a shared memory multiprocessor maintains data consistency according to the above definition, the memory model the programmer needs to know is the very simple one illustrated in Figure 20, regardless of the actual complexity of the machine's memory system. The real machine behaves for programming purposes as though its processors were directly connected to a simple read write memory with a single port that is able to service exactly one Fetch or Store operation at a time.

The simplest way to understand how the DynaBus consistency protocol works is to look at an example (a more careful specification useful for reference will be given in the following section). Consider the five processor system showed in Figure 22. The example below describes a sequence of events for a particular location (address 73) starting from the state where none of the five caches has the block that contains this location. Numbers in the figure correspond to the numbers in the text below.

For the example, it is sufficient to know that a cache maintains two state bits Shared and Owner for each block of data. When a block has Shared=1 it means that there may be other cached copies of this block; Shared=0 means this is the only cached copy. When Owner=1 it means that this cache's processor was the last one to update this block and any copies it has in other caches. At most one cached copy of a block may have Owner=1. The protocol uses the DynaBus lines shared and owner defined in Section 4.5.

A single level system consists of one or more processors connected to the DynaBus through caches, and a single main memory. The first thing to note about this configuration is that it is sufficient to maintain consistency between cached copies. The main memory copy can be stale with respect to the caches without causing incorrect behavior because processors have no way to access data except through caches.

The protocol requires that for each block of data a cache keep two additional bits, shared and owner. For a given block, the shared bit indicates whether there are multiple copies of that block or not. This indication is not accurate, but conservative: if there is more than one copy then the bit is 1; if there is only one copy then the bit is probably 0, but may be 1. We will see later that this conservative indication is sufficient. The owner bit is set in a given cache if and only if the cache's processor wrote into the block last; thus at most one copy of a datum can have owner set. A cache is also required to maintain some pendingState for a transaction the cache has initiated but that hasn't been replied to as yet; this state allows a cache to correctly compute the value of the shared bit for the block addressed in the pending transaction, and to take special actions for certain "dangerous" packets that arrive while the reply is pending. In addition to this state, the protocol uses two lines on the DynaBus, Shared and Owner that were described earlier in Section 4.5.

Generally, a cache initiates a ReadBlock transaction when its processor does a Fetch or Store to a block and the block is not in the cache; it initiates a FlushBlock when a block needs to get kicked out of the cache to make room for another one (only blocks with owner set are written out); and it initiates a WriteSingle when its processor does a write to a block that has the shared bit set. Caches do a match only if they see one of the following packet types: RBRqst, RBRply, WSRqst, WSRply, CWSRqst, CWSRply, and WBRqst. In particular, note that no match is done either for a FBRqst or a FBRply. This is because FB is used only to flush data from a cache to memory, not to notify other caches that data has changed. No match is done for a WBRply either, because all this packet does is acknowledge that the memory has processed the WBRqst.

When a cache issues a RBRqst or WSRqst, all other caches match the block address to see if they have the block. Each cache that matches, asserts Shared to signal that the block is shared and also sets its own copy of the shared bit for that block. The requesting cache uses pendingState to compute the value of the shared bit. The reason it can't just copy the value of Shared into the shared bit like the other caches is because the status of the block might change from not shared to shared between request and reply due to an intervening packet with the same address. This ensures that the shared bit is TRUE for a block only if there are multiple copies, and that the shared bit is cleared eventually if there is only one copy. The clearing happens when only one copy is left and that copy's processor does a store. The store turns into a WSRqst, no one asserts Shared, and so the value the requestor computes for the shared bit is FALSE.

The manipulation of the owner bit is simpler. This bit is set each time a processor stores into one of the words of the block; it is cleared each time a WSRply arrives on the bus (except for the cache whose processor initiated the WSRqst). There are two cases to consider when a processor does a store. If the shared bit for the block is FALSE, then the cache updates the appropriate word and sets the owner bit right away. If the shared bit is TRUE, the cache puts out a WSRqst. When the memory sees the WSRqst, it turns it around as a WSRply with the same address and data, making sure that the shared bit in the reply is set to the value of the Shared line an appropriate number of cycles after the appearance of the WSRqst's header cycle. When the requestor sees the WSRply, it updates the word and also sets owner. Other caches that match on the WSRply update the word and clear owner. This guarantees that at most one copy of a block can ever have owner set. Owner may not be set at all, of course, if the block has not been written into since it was read from memory.

When an RBRqst appears on the bus, two distinct cases are possible. Either some cache has owner set for the block or none has. In the first case the owner (and possibly other caches) assert Shared. The owner also asserts Owner, which prevents memory from responding, and then proceeds to supply the block via an RBRply. The second case breaks down into two subcases. In the first subcase no other cache has the block, Shared does not get asserted, and the block comes from memory. In the second subcase at least one other cache has the data, Shared does get asserted, but the block still comes from memory because no cache asserted Owner. Because the bus is packet switched, it is possible for ownership of a block to change between the request and its reply. Suppose for instance that a cache does an RBRqst at a time when memory was owner of the block, and before memory could reply, some other cache issues a WSRqst which generates a WSRply which in turn makes the issuing cache the owner. Since Owner wasn't asserted for the RBRqst, memory still believes it is owner, so it responds with the RBRply. To avoid taking this stale data, the cache that did the RBRqst uses pendingState to either compute the correct value of the data or to retry the ReadBlock when the RBRply is received. Dangerous transactions for a pending ReadBlock are the ones that modify data: WSRply, CWSRply, and WBRqst.

It is interesting to note that in the above protocol the Shared and Owner lines are output only for caches and input only for memory. This is because the caches never need the value on the Owner line, and the value on the Shared line is provided in the reply packet so they don't need to look at the Shared line either.

In the discussion above, we did not say how the transactions CWS and WB work. We will do this now. CWS is identical in its manipulation of the Shared and Owner bits and the Shared and Owner lines to WS, so as far as consistency is concerned these transactions can be treated the same. WB, on the other hand, is identical to FB as far as memory is concerned. Caches ignore FB, but overwrite their data for a matching WBRqst and clear the owner bit for this block.

Figure 23 illustrates a 2-level DynaBus-based system A two-level system consists of a number of one-level systems called clusters connected by a main DynaBus that also has the system's main memory. Each cluster contains a single large cache, that connects the cluster to the main DynaBus, and a private DynaBus, that connects the large cache to the small caches in the cluster. This private DynaBus is electrically and logically distinct from the DynaBuses of other clusters and from the main DynaBus. From the standpoint of a private DynaBus, its large cache looks identical to the main memory in a single-level system. From the standpoint of the main DynaBus, a large cache looks and behaves very much like a small cache in a single-level system. Further, the design of the protocol and the consistency protocol is such that a small cache cannot even discover whether it is in a one-level or a two-level system. The response from its environment is the same in either case. Thus, the behavior of a small cache in a two level system is identical to what was described in the previous section.

The protocol requires the large cache to keep all of the state bits a small cache maintains, plus some additional ones. These additional bits are the existsBelow bits, kept one bit per block of the large cache. The existsBelow bit for a block is set only if some small cache in that cluster also has a copy of the block. This bit allows a large cache to filter packets that appear on the main bus and put only those packets on the private bus for which the existsBelow bit is set. Without such filtration, all of the traffic on the main bus would appear on every private bus, defeating the purpose of a two-level organization.

We have already stated that the behavior of a small cache in a two-level system is identical to its behavior in a one-level system. We have also said that a large cache behaves like main memory at its private bus interface and a small cache at its main bus interface. What remains to be described is what the large cache does internally, and how packets on a private bus relate to those on the main bus and vice-versa.

When a large cache gets an RBRqst from its private bus, two cases are possible: either the block is there or it's not. If it's there, the cache simply returns the data via an RBRply, making sure that it sets the shared bit in the reply packet to the OR of the value on the bus and its current state in the cache (recall that in the single-level system main memory returned the value on the Shared line for this bit). If the block is not in the cache, the cache puts out an RBRqst on the main bus. When the RBRply comes back the cache updates itself with the new data and its shared bit and puts the RBRply on the private bus. When a large cache gets a WSRqst on its private bus, it checks to see if the shared bit for the block is set. If it is not set, then it updates the data, sets owner, and puts a WSRply (with shared set to the value of the Shared line at the appropriate time) on the private bus. If shared is set, then it puts out a WSRqst on the main bus. The memory responds some time later with a WSRply. At this time the large cache updates the word, sets the owner bit, and puts a WSRply on the private bus with shared set to one. When a large cache gets a FBRqst, it simply updates the block and sends back an FBRply.

When a large cache gets an RBRqst on its main bus, it matches the address to see if has the block. If there is a match and owner is set, then it responds with the data. However, there are two cases. If existsBelow is set, then the data must be retrieved from the private bus by placing a RBRqst. Else the copy of the block it has is current, and it can return it directly. When a large cache gets a WSRqst on the main bus, it matches the address to see if the block is there and asserts shared as usual, but takes no other action. When the WSRply comes by, however, and there is a match, it updates the data it has. In addition, if the existsBelow bit for that block happens to be set, it also puts WSRply on the private bus. Note that this WSRply appears out of the blue on the private bus; that is, it has no corresponding request packet. This is another reason why the number of reply packets on a bus may exceed the number of request packets.

All control interactions are carried out through the use of IORead, IOWrite and BIOWrite transactions directed to a common, unmapped 32-bit IO address space. This address space is common in the sense that all processors see the same space, and it is unmapped in the sense that addresses issued by processors are the ones seen by the IO devices. Generally, each type of IO device is allocated a unique, contiguous chunk of IO space at system design time, and the device responds only if an IORead, IOWrite, or BIOWrite is directed to its chunk. The term IO device is being used here not just for real IO devices, but any device (such as a cache) that responds to a portion of the IO address space.

Devices connected DynaBus via a cache automatically participate in the data consistency algorithm. If performance were not a problem, all devices could be connected to the DynaBus this way freeing designers of IO devices from having to build special chips to interface to the DynaBus. Unfortunately, this approach is insufficient for high speed input devices, which would cause a cache to needlessly transfer blocks from memory to cache each time the cache got a miss. The protocol provides the transaction WritesBlock to write directly to memory without going through a cache. Of course, a high speed output device could use ReadBlock's to directly transfer data out of consistent memory without going through a cache.

Figure 27 illustrates the MapRequest/MapReply transactions. The MapRequest is used to perform virtual to real page translation when the data requested by the Processor is not contained in the Processor Cache. The Processor Cache sends an address space identifier (aid) and virtual page number to the Map Cache. The Map Cache uses the MapReply transaction to return information to the Processor Cache. If the Map Cache contains the requested entry, it returns the corresponding real page and 4 flags: Dirty, KWtEnable (kernel write enable), UWtEnable (user write enable), and URdEnable (user read enable). The Processor Cache then issues a ReadBlockRequest using the real address which it constructs from the real page. Main Memory returns the data. (See transactions 1a and 1b of Figure 27.) If the Map Cache does not contain the requested entry, it uses the MapReply to return the MapFault FaultCode. This fault initiates a software trap to load the requested entry from the complete Map Table. (See transactions 2a and 2b of Figure 27.)

The DeMap transaction is used to invalidate virtual to real page translations. Whenever the mapping information for a page must be modified, the DeMap transaction is performed to invalidate all cached copies of the mapping entry in the processor caches. Before the DeMap is initiated system software must:

The DynaBus provides a single parity wire to check transport on the 64 Data wires. A device that sends a packet is expected to generate the parity bit, and all receiving devices are expected to check the parity bit. Whether a device considers a DynaBus parity error to be recoverable or catastrophic is not specified.

The DynaBus requires each device to implement a timeout facility to detect devices that do not respond, or devices that aren't there in the first place. Each device must maintain a counter that starts counting bus cycles when the device issues a request to the arbiter to send a request packet. If the system-wide constant maxWaitCycles cycles have elapsed before the corresponding reply packet is received, the device must assume that an error has occurred. Whether a device considers a DynaBus timeout to be recoverable or catastrophic is not specified.

The determination of a system-wide value for maxWaitCycles is tricky because of the wide variance in expected service times. For example, a low priority device might take a long time to just get bus grant, while a higher priority device would get grant relatively quickly. A low priority device might in fact be forced to wait arbitrarily long if a higher priority device decides to hog the bus. The question of whether this ought to be considered an error is debatable.

To avoid getting entangled in these issues, the bus specification simply specifies a system-wide lower bound on the limit maxWaitCycles and leaves it up to the device implementor to decide the exact value. Such a lower limit is needed to avoid generating frequent false alarms. A conservative lower limit can be arrived at by computing the worst-case service time for a cache request and increasing it by an order of magnitude for safety (caches are taken since they are the lowest priority devices that do not change their request priority). Assuming there are 8 caches and only one memory bank, the worst case service time is at most

Increasing this by an order of magnitude gives 2048 cycles, so each device is required to have maxWaitCycles e 2048.

When a device encounters a recoverable error while servicing a request packet, it uses the DynaBus Mode/Fault bit in the reply packet to report the error. The least significant 32 bits of the first data word of the reply packet are set aside for the FaultCode (the format of FaultCode was described earlier, and appears again in Appendix III).

When a device encounters a catastrophic error it uses the DynaBus SStopOut signal to halt all DynaBus activity and signal the service processor. The service processor then uses the DBus to locate the failing device and take appropriate action.