\chapter{The Pipelined Input-Output Bus}

\section{An Overview of the PBus}
    
    The pipelined input-output bus, or PBus connects the I/O interface board
to the CAM-8 space modules.  The PBus is a synchronous 16-bit bus which operates at
the CAM-8 clocking rate.  It has a high degree of fanout in order
to interface to a large number of space modules which may compose a giant CAM-8.
Indeed, the most characteristic feature of the PBus is that it is designed to 
provide for the fanout of 
control and data to an unlimited number of CAM-8 space modules.
Figure~\ref{pbusblk} shows a top level diagram of the tree-like PBus structure
with binary fanout.

    The PBus begins as a root which consists of a single level of its data and
control lines.  Thereafter, the bus divides into several branches which 
themselves further divide into more branches.  Each branch contains a replica
of the control and data lines associated with the root level.  Bus branches
are connected by bus nodes.  The bus fanout is defined as the number of 
output branches associated with a node. The terminal nodes of the PBus are called bus
leaves.  The depth of the bus is the number of nodes encountered by a direct
path from the root to a leaf.  In the CAM-8 input-output system, the interface
board forms the root of the PBus and the CAM-8 space modules occupy the
leaf positions.  The depth of the PBus is the same for all leaves, and
is proportional to the logarithm of the number of leaves supported by the
bus.  The fanout
of the PBus is variable, and depends on the drive capability of the bus nodes.
A larger fanout supports more CAM-8 space modules for a given bus depth. 
However, a larger fanout requires stronger line drivers on each PBus node.
As mentioned above, Figure~\ref{pbusblk} is an example of a PBus with binary fanout per node.

     The PBus branches simply consist of wires over which the control and 
data signals travel.  The bus direction of a branch, defined by the direction
of data transfer over that branch, is controlled by the leftmost node attached
to the branch.  In addition to controlling branch direction, a node contains 
storage elements to hold data in transit over the bus when the pipeline from 
root to leaf is held up.  Although the direction of data flow over the PBus
may change, control information to CAM-8 is always transmitted from the 
root to the leaves.  The PBus has a minimum latency which is proportional to the
bus depth.   The bus can provide a maximum throughput equal to its clocking 
rate. 

\begin{figure*}
\psfig{figure=pbusblkt.ps}
\caption{The Pipelined Input-Output Bus with binary fanout.}
\label{pbusblk}
\end{figure*}

     During a bus write, all PBus branches are configured to transmit data
away from the root.  Nodes broadcast data from their incoming to outgoing
branches.  Data and control information entering the pipeline at the root
eventually makes its way to the space modules where it is absorbed by active
modules.  Should the controller chips be unable to absorb the incoming data
(an unlikely event), the pipeline is held up and data is stored in the bus
nodes.  When pipeline flow is resumed, the stored data is propagated to the
leaves.

\begin{figure*}
\psfig{figure=pbusnodest.ps}
\caption{Operation of a PBus node in write and read modes.}
\label{pbusnodes}
\end{figure*}

     In a read cycle, all bus branches are configured for data flow 
from the leaves to 
the root.  Nodes propagate valid data on any of their input branches towards 
the root.  During a read, only one CAM space module drives valid data
on the PBus.  All other modules in the system transmit the 
default data value of 1 on every PBus data line. At each node, the data
on all incoming branches is logically ANDed, and the result is sent towards
the root.  The result is that the data transmitted from the active CAM module
 at a bus leaf is propagated to the interface board 
where it is absorbed.  If the interface board is unable to absorb data at
the PBus rate, the pipeline is held up until data can be accepted. 
The operation of a typical PBus node in write and read modes is shown in 
Figure~\ref{pbusnodes}.  The branches labelled Data in this figure are
branches which contain valid CAM data.  The No Data branch contains the
default value of all ones on its PBus data lines.

    A major challenge of using a pipelined bus structure as shown in Figure~\ref{pbusblk} is that when the bus direction needs to be changed from read to write,
there is potential for contention since branches closer to the root are
stimulated to change bus direction before those nearer the leaves.  Thus
one can envision a node in the system where both the input and output branches
are configured to transmit data into the node.  In the PBus architecture, 
this contention is avoided by always prefacing a bus direction change with
a propagation wave of ``broken branches'' through the system.  A ``broken
branch'' is a bus branch which is in a high impedance state and transmits
data in neither direction.  Instead of changing branch directions immediately,
a branch is first put into the broken state before assuming the new direction.
By propagating broken branches from the root to the leaves, there is never the
case of all branches pointing into a node.  As a result, contention is avoided.

\section{The PBus Protocol}

     The PBus protocol is almost entirely defined by the operation of the
bus nodes which tie the bus branches together.  Since the root and the leaves of
the bus are
special bus nodes, they also execute the protocol.  Figure~\ref{pbusnode} shows a
block diagram of a PBus node.  There is one
PBus control line, the RD/WR line, which is propagated from the interface 
board to configure the PBus direction.
Adjacent
nodes also communicate status information with each other over two status
lines which
connect them together.  In addition, the RD control signal generated at a
bus node is used to enable the tri-state buffers of that node's right neighbors.  The only other control line is the CAM-8
I/O Select line which is unused by the PBus protocol.  

\begin{figure*}
\psfig{figure=pbusnode.ps}
\caption{Block Diagram of a PBus node.}
\label{pbusnode}
\end{figure*}

    The Node Control Logic is responsible for the execution of the bus 
protocol.  It directs the storage and transmission of PBus data and 
control information at the node.  The storage circuitry is represented
by the Data/Control Register block.  The RD and WR signals generated 
by the Node Control Logic determine the direction of the branch between a
node and the one to its immediate right.  If RD is active, the branch
transfers data into the node.  If WR is active, the branch transmits data out
of the node.  If neither RD nor WR is active, the branch is broken and
assumes the high impedance state.  

    Figure~\ref{pbusnode} shows some of the circuitry
associated with each node. RD and WR are the read and write signals generated
by the node; RD' is the read signal from the node's leftmost neighbor.  Node
fanout is also illustrated in this figure.  For a fanout of n, the 16 PBus
data lines are replicated n times and driven by tri-state drivers controlled
by the WR control line of a node.  The replicated data lines are logically
ANDed as required during a PBus read to generate 16 bits of valid bus data.
The buffering of data at a node occurs in the IN-OUT block of Figure~\ref{pbusnode}.  A 16-bit wide multiplexor selects the source of the input to this 
block --- the incoming branch data for a bus write or the logically ANDed data
for a bus read.  The output of the IN-OUT block is either fanned out during
a write or transmitted to the root during a read.  The I/O Select line is
pipelined so that it remains synchronized with its associated data.

     A bus node contains several D-type flip-flops.  Two
such flip-flops register data coming along each of the I/O data lines.  Another
register is used to determine the direction of the bus branch between a node and
the one immediately to its right.  Finally, every node contains two status bits
which indicate whether the node is full or empty.  A node is defined to be full
if it is unable to buffer more information without loss of data.  Since there
are two storage elements per data line, this will occur if a node is buffering
two bits of data line information.  An empty node is one that does not contain
any valid data.  In a flowing bus pipeline, the nodes will be neither empty nor
full --- each node will be temporarily storing exactly one valid data bit 
per line. 

 A bus node also reads the status bits
of the data flip-flops of the nodes immediately to its left and right.
This information, together with its own status information, allows a node to
execute the required bus protocol.  A portion of the PBus during a read to write
transition is
shown in Figure~\ref{finalbus}. 

\begin{figure*}
\psfig{figure=finalbust.ps,width=5.5in}
\caption{A portion of the PBus path from root to leaf during a RD to WR transition.}
\label{finalbus}
\end{figure*}

\subsection{Data and Status Bit Updating}

     Under the PBus protocol, a data flip-flop is updated whenever
it can accommodate new data and such data is available.\footnote{A data flip-flop update corresponds to a flow of data along the PBus.}  This will occur
by default except under the following conditions when the data 
flip-flops retain their old data:

\begin{enumerate}

\item The node is full and the node to its right in the pipeline is 
      also full.
\item The node to the left is empty.

\end{enumerate}

     These conditions are illustrated in Table~\ref{nodestat}.  The empty
and full status bits are represented by E and F respectively.  The status
bits of neighboring nodes are labelled EL (Empty Left) and FR (Full Right).
E' and F' are the new values of the node's empty and full bits.  RCRC is
a signal which indicates that data contained in the node is stored for the
clock cycle.
The table assumes
that data in the pipeline flows from left to right. For a PBus write, ``left''
corresponds to the direction of the bus root and ``right'' corresponds to
the direction of the bus leaves.  For a PBus read operation, these directions
are interchanged --- the bus leaves are to the left and the bus root is to the
right.
 A node should
never enter a state where it is both full and empty.  If this state is
ever encountered, the node reverts to the empty state on the following
clock cycle.

\begin{table}

\begin{center}

\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\multicolumn{1}{|c|}{EL}
&\multicolumn{1}{|c|}{E}
&\multicolumn{1}{|c|}{F}
&\multicolumn{1}{|c|}{FR}
&\multicolumn{1}{|c|}{E'}
&\multicolumn{1}{|c|}{F'}
&\multicolumn{1}{|c|}{RCRC}

 \\ \hline

0 & 0 & 0 & 0 & 0 & 0 & 0  \\ \hline
0 & 0 & 0 & 1 & 0 & 1 & 0  \\ \hline
0 & 0 & 1 & 0 & 0 & 1 & 0  \\ \hline
0 & 0 & 1 & 1 & 0 & 1 & 1  \\ \hline
0 & 1 & 0 & 0 & 0 & 0 & 0  \\ \hline
0 & 1 & 0 & 1 & 0 & 0 & 0  \\ \hline
0 & 1 & 1 & 0 & 1 & 0 & X  \\ \hline
0 & 1 & 1 & 1 & 1 & 0 & X  \\ \hline
1 & 0 & 0 & 0 & 1 & 0 & X  \\ \hline
1 & 0 & 0 & 1 & 0 & 0 & 1  \\ \hline
1 & 0 & 1 & 0 & 0 & 0 & 1  \\ \hline
1 & 0 & 1 & 1 & 0 & 1 & 1  \\ \hline
1 & 1 & 0 & 0 & 1 & 0 & X  \\ \hline
1 & 1 & 0 & 1 & 1 & 0 & X  \\ \hline
1 & 1 & 1 & 0 & 1 & 0 & X  \\ \hline
1 & 1 & 1 & 1 & 1 & 0 & X  \\ \hline
\end{tabular}
\end{center}
\caption{Transition Table for a PBus node.}
\label{nodestat}
\end{table}

\subsection{Changing Bus Direction}

     The change of bus direction is always initiated at the bus root.  The
interface board simply transmits the bus direction bit with every clock cycle along
the one-directional, pipelined, RD/WR line.  The bus direction
protocol is as follows.  If the RD/WR bit in one clock cycle agrees
with its value on the previous cycle, then the direction of the branch 
between the node and the one to its immediate right is set to that direction.
If the present and previous RD/WR bits do not agree, then the same
branch assumes the high impedance state.  As described above, this ensures that there is
never any contention caused by adjacent nodes trying to drive the same
line in different directions.
   
     The bus direction should not change from Write to Read until all 
previously transmitted valid data has been accepted by the space modules.
This is ensured by only propagating the RD/WR bit through a node 
if the node was previously in write mode and it is presently empty, or
if the node was previously in read mode.  Otherwise,
the old bus direction  associated with that node
is maintained.

\section{Node Circuitry}

     This section describes some of the circuitry that is used
to implement the PBus protocol described above.

\begin{figure*}
\psfig{figure=buspart.ps,width=6in}
\caption{Circuitry for transfer of PBus node status signals.}
\label{buspar}
\end{figure*}

\subsection{Transfer of Status Information}

     For the proper operation of the PBus protocol, a node must show the
value of its empty and full flip-flops to its neighboring nodes.  It must
also read the empty and full flip-flops of its neighbors. The
transition equations described earlier indicate that a node need
only read the Full bit of the node to its immediate right in the logic
pipeline\footnote{The logic pipeline goes from root to leaf in Write mode
and from leaf to root in Read mode.} and the Empty bit of the node to its
left.

     These restrictions give rise to the circuitry shown in Figure~\ref{buspar}.
 Two wires are used between adjacent nodes.  Each of these wires
carries data in one direction from one node to the other.  In Read mode,
a node passes its empty bit to the node at its left, and its full bit to
the node at its right.  It accepts the empty bit from its right neighbor
and the full bit from its left neighbor.  During Write mode these directions
are reversed.  As illustrated in the diagrams, the circuitry essentially
consists of four 2-to-1 multiplexors correctly wired.  The status input
signal from the right node is actually the logic OR of the Right Status
In signals from all adjacent right nodes.  Since the Empty or Full status
signals are active low, and inactive CAM modules never hold up the bus,
 transfers should proceed only when all fanned out nodes can send or receive
data.  This is achieved by the logic ORing of the right status inputs.

\begin{figure*}
\psfig{figure=busfft.ps}
\caption{Data Register Circuit for a PBus node.}
\label{busff}
\end{figure*}

\subsection{The Data and Status Flip-Flops}

     Figure~\ref{pbusnode} indicated that the data buffering circuitry of a
PBus node is concentrated in the IN-OUT block.  Figure~\ref{busff} shows the
circuitry contained in this block.  The Data register circuit consists of two
D-type flip-flops
and three 2-to-1 multiplexors per data line.  The top flip-flop is used to
pipeline the data bit.  The lower flip-flop normally stores a copy of the
last bit that has been advanced to the right in the logic pipeline.  This 
prevents loss of data in the case when that bit was not accepted by the 
neighboring right nodes because of a pipeline holdup.  In such a case, the
Data register circuit stores two consecutive data bits until the pipeline
resumes normal flow.

     The I/O Select control line to CAM-8 passes through an identical circuit.
The only difference between this line and the data lines is that the I/O
Select line always goes from the root to the leaves of the PBus.  The data
lines, however, are bidirectional. 

The logic equations for the control signals of the Data register circuit
are derived from Table~\ref{nodestat}:

\begin{verbatim}   
               RCRC  = EL + F*FR

               WHICH = F
\end{verbatim}

     The status bits are held in Node Control Logic D-flip-flops which are updated
according to the following equations\footnote{These were derived from the
transition table using Karnaugh maps to simplify the expressions.}:


\begin{verbatim}
               F := (FR*/E*/EL + F*/E*/EL + FR*/E*F)*(RD + WR)

               E := E*EL + EL*/FR*/F + E*F + /RD*/WR
\end{verbatim}


     The equations for E and F also contain terms for the bus
direction.  This is necessary to initialize the bus to the empty state 
on a switch of direction.


\begin{figure*}[p]
\psfig{figure=busdirt.ps,width=6in}
\caption{Bus Direction Circuitry for a PBus node.}
\label{busdir}
\end{figure*}

\subsection{The Bus Direction Registers}

    The bus direction register circuit is shown in Figure~\ref{busdir}.
This circuit contains two serially configured D-flip-flops
which hold the present and previous values of the RD/WR bit that
is propagated from the host.  The logic AND of these signals is used to
configure the bus branch to write mode while the logic NOR of the signals
generates the read mode. 

    The top flip-flop of Figure~\ref{busdir} is a synchronizing flip-flop.
Its purpose is to pipeline the Rd/Wr line of the PBus.  The lower flip-flop
is needed to provide the delayed version of the Rd/Wr signal.  When the 
present and delayed versions of Rd/Wr do not agree, a change in bus direction
is required.  The RD and WR control lines of the node are toggled accordingly.

    A 2-to-1 multiplexor chooses the input of the first of the series
flip-flops.  If the node was previously in write mode but is now empty,
or if the previous mode was read, then the flip-flop is fed with incoming
Read/Write data.  Otherwise,
the old value of the RD/WR bit is recirculated through the
multiplexor.  This procedure ensures that
a Write to Read transition of the bus lags behind any previously
transmitted valid data.

\section{Conclusion}

     The PBus protocol described in this chapter has several advantages.
When the bus is read as fast as data is put into it, none of the 
nodes will be full or empty.  Thus data advances from node to node
with each clock cycle, at the optimum rate.  The buffering effect of
the bus also ensures
that no valid data is lost because of a pileup along the pipeline.
Also, because the bus only responds to valid data\footnote{Data is defined
as valid if a node is not empty.}, any invalid data generated by a slow
bus driver is automatically thrown out of the pipeline to make way for
valid information.  Thus, invalid data bits do not hold up the pipeline.
Because the bus itself indicates that data is valid, a separate Valid
data line to the space modules is not needed.




