\documentstyle[11pt,../deriv,fleqn,theorem,fullpage]{article}

%\oddsidemargin -0.5in    %   Note that \oddsidemargin =
                         %   \evensidemargin
%\evensidemargin -0.5in

%\textwidth 7.5in        % Width of text line.

\parindent=10pt
\parskip=0pt
\input psfig
\newtheorem{definition}{Definition}
\newtheorem{theorem}[definition]{Theorem}
\newtheorem{lemma}[definition]{Lemma}
\newtheorem{corollary}[definition]{Corollary}
\newcommand{\pref}{{\bf pref}}
\newcommand{\iif}{{\bf if}\;}
\newcommand{\ffi}{{\bf fi}\;}
\newcommand{\then}{\;{\bf then}\;}
\newcommand{\eelse}{\;{\bf else}\;}
\newcommand{\ddl}{\frac{d}{dl}\:}
\newcommand{\ev}{\mbox{\cal E}}

\newcommand{\dhf}{\delta_{h,f}}
\newcommand{\Dhf}{\Delta_{h,f}}
\newcommand{\dhr}{\delta_{h,r}}
\newcommand{\Dhr}{\Delta_{h,r}}
\newcommand{\Dr}[1]{\Delta_{#1,r}}
\newcommand{\dr}[1]{\delta_{#1,r}}
\newcommand{\Df}[1]{\Delta_{#1,f}}
\newcommand{\df}[1]{\delta_{#1,f}}

\title{Response Time Properties of Asynchronous Linear Pipelines.}
\author{Robert Berks and Jo Ebergen\footnote{Currently on leave at Sun 
Microsystems
Laboratories, Mountain View, USA.}\\
        Department of Computer Science\\
        University of Waterloo\\
        Waterloo, Ontario, Canada N2L 3G1\\
        \{rtberks,jebergen\}@maveric.uwaterloo.ca}
\begin{document}
\maketitle
\begin{abstract}
  Extending previous work~\cite{Ebergen97}, 
  we give bounds on the worst and average-case response times 
  of asynchronous linear pipelines. The delays of
  the cells are bounded by a general variable delay model
  that allows for both forward and reverse latencies.
  Each cell may have a delay distribution different from and independent
  from  other cells. We derive simple closed-form formulae that bound the
  worst 
  and average-case response time. Our results
  are simple, provable, require no simulation, and allow
  high-level reasoning about performance of pipelines.
\end{abstract}

\section{Introduction}
\label{sect:introduction}
We present some properties on the
response time of linear pipelines that are
an extension of ideas presented in~\cite{Ebergen97} to make the results
both simpler and more easily applicable, yet far more general.

We consider linear pipelines where each of the component
cells may have a variable delay, and each component
may have different delay characteristics from
other components. Pipelines of asynchronous cells
can have these features, and it is interesting
to see the timing properties of such an achitecture. Unlike
synchronous pipelines, we cannot derive throughput
information from the clock frequency, so we
require a different kind of analysis.

Consider a linear array of $L+1$ cells
as indicated in Figure~\ref{array} (where $L=3$).
\begin{figure}[htbp]
\begin{center}
\makebox{\psfig{file=/u/rtberks/RESPONSE/GENERALIZED/Fig/pipe.eps,width=9.5cm}}
\end{center} 
\caption{A linear array of cells}
\label{array}
\end{figure}
We are only interested in the communication behaviour
at the interface of each cell as an ordering of events.
Each interface between two cells has the same communication behaviour,
viz., a repetition of a request $r$ followed by an acknowledgment
$a$. A request followed by an acknowledgment is called a
handshake. The end cell handshakes at its only interface,
the other cells perform handshakes at both interfaces  such that in each cycle
one handshake occurs at either side.

The requests and acknowledgments
are considered as instantaneous events, and delays can be incurred in
the cells or the environment of the pipeline.  For each cell
we assume that the delays between the receipt of the {\em last} input
causing an output and the production of that output is always bounded
from above and below. Unlike in~\cite{Ebergen97}, each
cell may have a set of bounds different from other cells, and we also
distinguish between whether a signal is transmitted through a cell in a
``forward'' or ``reverse'' direction.
The lower bounds for the forward and reverse latency of cell $i$ are given by
$\delta_{i,f}$ and $\delta_{i,r}$ respectively.
Similarly, the upper bounds for the forward and reverse
latency for cell $i$ are given by $\Df{i}$ and $\Dr{i}$  respectively.  We also
assume a lower bound ($\delta_e$) and upper bound ($\Delta_e$) for the environment
delay. Surprisingly, despite this great increase in the generality of the delay
model over our previous work, the results are even simpler than before.

The delays of the cells do not have to be fixed, but may vary between
a fixed upper and lower bound.  Delays may depend on the data
received, or they may vary over different instances of the same cell,
or they may vary over time.  

Response time ({\em RT\/}) is defined as the time between a request
from the environment ($r_0$) and the successive acknowledgment
($a_0$). We give a closed-form formula for the upper bound of response-time {\em
RT\/} under any distribution of delays.
We also give both lower bounds and upper bounds
for the average response time of pipelines, denoted by $AR$, under any
distribution of delays.

Although our results give bounds, not specific
values, our approach has the following advantages.
\begin{itemize}
	\item We need not give specific implementations
	of cells or compute specific distributions of delays.
	Different implementations must only satisfy the
	upper bounds and lower bounds for the delays of the basic cells.
	\item The results can be proved analytically,
	without any simulation. 
	\item We can express the results as closed-form formulae. This
	allows us to reason at a higher level about an architecture.
	We can also experiment rapidly with different
	parameters values.
\end{itemize}

As an example of our formulae, we show that
\begin{itemize}
	\item ${\it RT}  \leq  \max (\{ \Dr{k} + \Df{k-1} +
	\sum_{h=0}^{k-1}(\Dhr -\dhr)
	- \delta_e \;|\; 1 \leq k \leq L \} \cup \{ \Dr{0} \})$
	\item $mc - \Delta_e  \leq AR \leq MC - \delta_e$
\end{itemize}
The parameters are defined in Table~\ref{tab:symbols} and
will be further explained in the following sections. The upper bound for the
response time $RT$  is strongly related to the reverse latencies in the
summation term and the pipeline length $L$. Surprisingly, there is only one term
in this formula relating to forward latencies. Furthermore, the bounds for the
average response
$AR$ time depend on certain pipeline bottlenecks, as defined by $mc$ and $MC$,
and is independent of
$L$.

Our architectural model is restricted to pipelines. Nevertheless
this offers a rich area of designs.
There are many pipeline designs for various computations all
where data is flowing in one or both
directions,
see~\cite{Berkel95,Ebergen90b,Furber95,Josephs94,Rem87,Sutherland89}
for example.  If we know what the values are for each of the parameters
for certain implementations, we can quickly determine what the
upper bounds for the worst-case and average response times are.
Our delay model is also appropriate when we use data dependent
completion signals, as in
\cite{Kearney97,Nowick97,Williams91b} for example.
%jliu95 (need special bibtex entry. Get from prop.bib

{\small
\begin{table}[htbp]
  \begin{center}
	\begin{tabular}{|c|c|} \hline
		Symbol & Usage  \\  \hline
		$\dhr$ & Lower bound on ``reverse'' latency of cell $h$\\ \hline
		$\Dhr$ & Upper bound on ``reverse'' latency of cell $h$\\ \hline
		$\dhf$ & Lower bound on ``forward'' latency of cell $h$\\ \hline
		$\Dhf$ & Upper bound on ``forward'' latency of cell $h$\\ \hline
		$\delta_e$ & Lower bound on the environment delay  \\ \hline
		$\Delta_e$ & Upper bound on the environment delay \\ \hline
		$L$ & Number of non-end cells and index of end cell \\ \hline
		${\it RT}$ & Worst-case response time \\ \hline
		${\it AR}$ & Average response time \\ \hline
		${\it mc}$ & Minimum cycle time between adjacent cells \\
		& $mc = \max \{ \Delta_e + \delta_{0,r},
		\delta_{0,f} + \delta_{1,r}, \delta_{1,f} + \delta_{2,r},
		\ldots,
		\delta_{L-1,f} + \delta_{L,r}\}$ \\ \hline
		${\it MC}$ & Maximum cycle time between adjacent cells \\
		&   $MC = \max \{ \delta_e + \Delta_{0,r},
		\Delta_{0,f} + \Delta_{1,r}, \Delta_{1,f} + \Delta_{2,r},
		 \ldots,
		\Delta_{L-1,f} + \Delta_{L,r}\}$ \\ \hline
	\end{tabular}
  \end{center}
\vspace{-0.1in}
\caption{Summary of symbols used.}
\label{tab:symbols}
\end{table}
\small}

\vspace{-0.18in}
\section{Related Work.}
\label{sect:related}

The delay assumptions and dependency graphs (also called process
graphs) in this paper are inspired by the model used
in~\cite{HulBurAmoBor94,Hulgaard94a}.
In~\cite{HulBurAmoBor94,Hulgaard94a} algorithms are described to
obtain exact bounds for the delay between two given occurrences of
events in a given dependency graph under a variable delay model.  A
much larger class of networks and communication behaviours is allowed
than we use here. In contrast, give formulae
for a small set of regular process graphs. Our formulae
have parameters, like the depth of the network and the upper and
lower bounds for certain delays.

More detailed performance
analysis and optimization techniques, all the way down to transistor sizing, 
are given in~\cite{Burns91a}.  Techniques for analyzing the
throughput and latency of micropipelines and rings are proposed
in~\cite{Williams92}, where
formulae are derived for the throughput as a function
of the forward and backward latencies of the stages and the number of
tokens in the ring.  However, a fixed-delay model is used. See also
\cite{Sparso93}, where these techniques have been applied.
A fixed delay model is also used in~\cite{Nielsen94a}, where 
an algorithm is presented to compute the average
cycle time of arbitrary Signal Graphs.
In~\cite{Greenstreet90} formulae for upper bounds of
the utilization of pipelines are presented
under various assumptions for the delay
distributions for the latencies of the cells. 
In~\cite{Rem87} yet another model is
used for analyzing the response time of  implementations. The model is based on
the notion of sequence functions and  is more restrictive than a variable delay
model. 

The algorithms in~\cite{Xie97} compute average time separation
of events using an iterative numerical procedure to find
the steady state. For each set of values for the parameters, the algorithm
can compute the average. The algorithm is applicable to  
a wide range of process graphs.
%The computations
%are said to be efficient though there are neither
%empirical results, nor are there formal proofs
%of the efficiency.
%They also allow
%a wide range of possible distributions of delays
%for any edge in the graph, and these are stepwise functions
%with an arbitrary number of steps. The larger the number
%of steps the slower the algorithm runs.
A simulation approach is also
found in Kearney and Bergmann~\cite{Kearney95}.

\section{Communication Behaviours}
\label{sect:communication}

Consider the cell in Figure~\ref{cell} from a linear array.
\begin{figure}[htbp]
\begin{center}
\makebox{\psfig{file=/u/rtberks/RESPONSE/Fig/cell.eps,width=7.5cm}}
\end{center} 
\vspace{-0.1in}
\caption{One cell}
\label{cell}
\end{figure}
At interface $i$, the communication behaviour for the handshakes can
be given by $ *[ r_i?; a_i! ] $.
That is, we take an input request, $r_i?$, and then we
output an acknowledgement $a_i!$. ($?$ denotes input, while
$!$ denotes output.) This behaviour then repeats (indicated by $*[..]$).
At interface $i+1$ the communication behaviour is given by 
$  *[ r_{i+1}!; a_{i+1}? ] $.

Cell $i$ synchronizes the handshakes at interface $i$ and $i+1$.
We restrict ourselves to behaviours for cells where for every handshake
on interface $i$ there is a handshake on interface $i+1$.
More precisely, the communication behaviours we look at are given by
\[
 (r_i?;\;
 *[\: (a_i!;\,r_i?) \| (r_{i+1}!;\,a_{i+1}?) \:]) 
\]

In other words, every occurrence of the segment
$r_{i+1}!;\,a_{i+1}?$ takes place in parallel with the
handshake $a_{i}!;\,r_{i}?$.

\begin{figure*}[hbtp]
\begin{center}
\makebox{\psfig{file=/u/rtberks/RESPONSE/GENERALIZED/Fig/linear.eps,width=15cm}}
\end{center} 
\vspace{-0.1in}
\caption{Unfolded communication behaviour for a linear array of four
  cells.}
\label{linear}
\end{figure*}

If we consider a complete network of 3 non-end cells, one end cell,
and the environment of the pipeline, then we can depict its behaviour 
in a process graph (Figure~\ref{linear}), where all edges
represent direct precedences brought about by some component in the network.
The dashed arrows represent direct precedences caused by the environment
of the pipeline.
Let us denote the $k$-th occurrence of event $a_i$ by
$(a_i,k)$, where $k \geq 0$.
Such a process graph gives a precedence
relation for occurrences of events. A precedence
between occurrences of events $e_0$ and $e_1$ is denoted by  
$e_0 \rightarrow e_1$.
For example, we have the following precedences
highlighted in Figure~\ref{linear}.
\[ (r_0,1) \rightarrow (a_0,1) ~~~{\rm and}~~~ 
(a_{1},0)  \rightarrow (a_0,1) \]
These precedences indicate that occurrence $1$ of event $a_0$
can only happen after occurrence $1$ of event $r_0$  and
occurrence $0$ of event $a_{1}$ has happened.

\section{The Delay Model}
\label{sect:delay}

We need to add a delay model to our behavioural model.
Let $c$ be a node in a (unfolded) process graph
with $c$ an output of cell $h$.
$T(c)$ is the time assigned to node $c$
and
\[ T_{pred}(c) = \max \{ T(b) \;|\; b {\rm ~is~a~direct~predecessor ~of~c}\}\]

We will stipulate that the delay is always measured from the
time $T_{pred}(c)$, when the {\em last\/} directly preceding event occurs,
to the actual occurrence of the event $c$.
Our delay model prescribes that any timing assignment $T$ of the
process graph must satisfy the 
following constraints. 

\[T_{pred}(c) +\dhf \leq T(c) \leq T_{pred}(c) +\Dhf \]
if node $c$ is a request, and
\[T_{pred}(c) +\dhr \leq T(c) \leq T_{pred}(c) +\Dhr \]
if node $c$ is an acknowledgment.

The constraints prescribe that ``forward'' delays through cell $h$ have lower
bound $\dhf$ and upper bound $\Dhf$, that is
\[ \dhf \leq \mbox{cell~$h$ forward delays} \leq \Dhf \]
Similarly, ``reverse'' delays for cell $h$ are bounded by $\dhr$
and $\Dhr$.

\[\left.
\begin{array}{l}
	r_h \rightarrow r_{h+1}\\
	a_{h+1} \rightarrow r_{h+1}
\end{array}
\right\} \mbox{ forward latencies for cell $h$.}
\]

\[\left.
\begin{array}{l}
	r_{h} \rightarrow a_{h}\\
	a_{h+1} \rightarrow a_{h}
\end{array}
\right\} \mbox{reverse latencies for cell $h$.}
\]

The end cell is associated with a reverse latency only
and the environment is associated with a forward latency.
We label the lower bound and upper bound on the environment delays $\delta_e$
and $\Delta_e$ respectively.

For worst-case response time we will minimize the environment delay
when we maximize the pipeline delay, and vice-versa for
best-case response time. Observe the definitions of Maximum
and Minimum Cycle time given in Table~\ref{tab:symbols}.

%We define the Maximum Cycle time and Minimum Cycle time respectively as.
%\[
%  MC = \max \{ \delta_e + \Delta_{0,r},
%	\Delta_{0,f} + \Delta_{1,r}, \Delta_{1,f} + \Delta_{2,r},
%	 \ldots,
%	\Delta_{L-1,f} + \Delta_{L,r}\}
%\]
%
%\[
%  mc = \max \{ \Delta_e + \delta_{0,r},
%	\delta_{0,f} + \delta_{1,r}, \delta_{1,f} + \delta_{2,r},
%	 \ldots,
%	\delta_{L-1,f} + \delta_{L,r}\}
%\]
%Since $\Delta_e \geq \delta_e$ it is not necessarily true that $mc \leq MC$.

\subsection{A Micropipeline}
\label{sect:micropipeline}

Suppose we have a micropipeline control-circuit
as in Figure~\ref{fig:model4}. Micropipelines were
described in \cite{Sutherland89} and are used
by the asynchronous versions of the ARM processor\cite{Furber95}.
In our model Figure~\ref{fig:model4}
corresponds to a pipeline with three non-end
cells and one end-cell. Hence, we would model it as a linear
pipeline with parameter $L=3$. Micropipeline stages have
one handshake on the right to every handshake on the left.

We assume that the only delays in the circuit are the buffer delays. That is, we
assume that the C-elements and wiring have zero-delay. This causes no loss of
generality, because we can always model the delays of the C-elements with the
delays of the buffers.

\begin{figure*}[hbtp]
\begin{center}
\makebox{\psfig{file=/u/rtberks/RESPONSE/GENERALIZED/Fig/model4.eps,width=15.1cm}}
\end{center}
\vspace{-0.22in}
\caption{A micropipeline with $L=3$. The environment
delay is labelled with an $e$. }
\label{fig:model4}
\end{figure*}

\subsection{Critical Paths}
When a dependency graph and a timing assignment is given, we define
the useful notion
of {\em critical paths}.
We define an edge $b \rightarrow c$ to be a {\em critical edge} if
either
\begin{description}
       \item[(i)]
	$c = r_0$, and
	$\delta_e \leq T(c)-T(b) \leq \Delta_e$ where $b$ must be $a_0$.
       \item[(ii)]
	$c = r_{h+1}$, and
	$\dhf \leq T(c)-T(b) \leq \Dhf$ for some $b$.
       \item[(iii)]
	$c = a_h$, and
	$\dhr \leq T(c)-T(b) \leq \Dhr$ for some $b$.
\end{description}

So we have three cases: environment delays, forward delays
and reverse delays.
The lower bound $\delta_x$ (
$x \in \{e,(h,f),(h,r)\}$ depending on the type of edge)
is automatic by our statement
that edge delays must be at least $\delta_x$. The
upper bound may not always be true, because other
dependencies may make event $c$ occur later.
A directed path is a {\em critical path}, if all its edges are critical 
edges.

We can view the critical edges as pieces of elastic which
can ``stretch'' between lengths $\delta_x$ and $\Delta_x$.
%Note that for each node at least one incoming edge  must
%be a critical edge, because of the delay constraints.
If we stretch an edge beyond $\Delta_x$ it breaks.
On a critical path, we know that no bit of elastic
on that path is broken, since, by the choice of the edges
on the path, none of the bits of elastic is stretched beyond its
upper bound, $\Delta_x$.

\section{Worst-Case Response Time}
\label{sect:worst-case}
%\noindent
%We have the following theorem.
\begin{theorem}
\label{theorem:RT-upper}
The worst-case response time ${\it RT}$ 
for any pipeline (as defined in Section
3 operating under a delay model of Section 4)
is bounded from above as 
\begin{eqnarray*}
{\it RT} & \leq & \max (\{ \Dr{k} + \Df{k-1} +
	\sum_{h=0}^{k-1}(\Dhr -\dhr)
	- \delta_e \;|\; 1 \leq k \leq L \} \cup \{ \Dr{0} \}) \\
\end{eqnarray*}
\end{theorem}
\vspace{-0.07in}
\noindent
$\Box$ {\em (Proof omitted)} \cite{Berks97} \\
\noindent
Notice that the summation term depends only on the reverse latencies.
As the length of the pipeline gets larger the summation
term can  get larger, though ultimately the worst
case depends on the cycle time between cells $k$ and
$k-1$. Consequently, the bound becomes smaller if 
we put the adjacent cells with the slowest cycles
(i.e. $\Dr{k} + \Df{k-1}$) near the entrance of
the pipeline, as this is where the summation term is minimized.

The bound above may not be tight
and cannot be simplified further without
further assumptions about the variables.
In many implementations the variation among cell delays is only
in the forward latencies. The reverse latencies may be fixed,
i.e., $\Dhr = \dhr$ for $0 \leq h \leq L$. With this
assumption the summation term disappears and the result
is independent of the length of the pipeline.
\begin{eqnarray*}
{\it RT} & \leq & \max (\{ \Dr{k} + \Df{k-1} +
	\sum_{h=0}^{k-1}(0)
	- \delta_e \;|\; 1 \leq k \leq L \} \cup \{ \Dr{0} \}) \\
	& = & \max (\{ \Dr{k} + \Df{k-1}
	- \delta_e \;|\; 1 \leq k \leq L \} \cup \{ \Dr{0} \}) \\
	& = & \max (\{ \Dr{k} + \Df{k-1}
	\;|\; 1 \leq k \leq L \} \cup \{ \Delta_{0,r} + \delta_e\}) -\delta_e \\
	& = & MC - \delta_e
\end{eqnarray*}
In other words,  in a linear pipeline with no
variation in reverse latencies per cell, the worst-case response time is at most
the maximum cycle time between adjacent cells.

\vspace{-0.065in}
\section{Average-Case Response Time}
\label{sect:average}
In a previous paper\cite{Ebergen97} we
described amortized response time as an upper bound on the
average response time. That is, over many request/acknowledgment
cycles, we also calculate the worst possible delay caused by the pipeline,
and divide this by the number of cycles. Here we also
find a lower bound on the average response time by a similar technique.
Averaged over many request/acknowledgment cycles
we calculate the {\em minimum\/} possible delay caused by the pipeline.

%We have the following theorem.
\begin{theorem}
\label{theorem:AR-linear}
The average response time ${\it AR}$ 
for any pipeline (as defined in Section
3 operating under a delay model of Section 4), 
is bounded as follows
\begin{eqnarray*}
mc - \Delta_e \leq & {\it AR} & \leq  MC - \delta_e
\end{eqnarray*}
\end{theorem}

\noindent
{\em Proof.} (Upperbound.)
From acknowledgment $(a_0,j_0)$ there
is a critical path to some request $(r_0,i_0)$ with
$i_0 \leq j_0$ and on this critical response path there is no other
event at level 0.
Let this path be of length $2k+1$ with $k\geq 0$.
There may be many paths between $(r_0,i_0)$ and $(a_0,j_0)$
of length $2k+1$.  We label each edge on each path with maximum
delays and then we choose a critical path $P$. This path $P$ is the
longest path (in terms of delay) between $(r_0,i_0)$ and $(a_0,j_0)$
excluding paths through the environment. We call the delay on this
critical path of length $2k+1$, $D_k$.

Between $(r_0,i_0)$ and $(a_0,j_0)$ there are $k$ 
environment edges (i.e, $a_0 \rightarrow r_0$) and $k+1$ 
``response'' edges (i.e, $r_0 \rightarrow a_0$).
Environment delays are at least $\delta_e$. In $k$ handshake
cycles, the total time for the environment delays is at least
$k\delta_e$. To obtain the upper bound on the average response time we subtract
the environment delay over $k$ handshake cycles and divide by the number of
responses.
\begin{eqnarray*}
{\it AR}	& \leq & \max \{ D_k -k \delta_e)/(k+1) \;|\; k \geq 0 \}\\	
	& = & \max \{ D_k + \delta_e)/(k+1) \;|\; k \geq 0 \} - \delta_e
\end{eqnarray*}
We look in more detail at the first term $\max \{ D_k + \delta_e)/(k+1) \;|\; k
\geq 0\}$.

Suppose there is either an edge $r_{i} \rightarrow r_{i+1}$ or
an edge $a_{i+1} \rightarrow r_{i+1}$ in our path, $P$.
$r_{i+1}$ is the output request signal of cell $i$. The path
must pass back through cell $i$ at some point which means
there must be an acknowledgement $a_{i+1}$ forthcoming
from cell $i+1$. So, for each edge on the path that ends
in $r_{i+1}$ there must be a corresponding edge that
ends in $a_{i+1}$. For each pair of edges we
have a maximum delay of $\Delta_{i,f} + \Delta_{i+1,r} \leq MC$.
There are $k$ edges ending in a request in the path and so we have $k$ pairs
with total delay less than or equal to $k \cdot MC$. We also
have one ``loose'' reverse edge at the end of the path. So the total delay on
the path is bounded as $D_k \leq k \cdot MC + \Delta_{0,r}$.
\begin{eqnarray*}
\max \{ D_k + \delta_e)/(k+1) \;|\; k \geq 0 \}  & \leq & 
	\max \{ k \cdot MC + \Dr{0} + \delta_e)/(k+1) \;|\; k \geq 0 \} \\
	& \leq & \max \{ k \cdot MC +  MC)/(k+1) \;|\; k \geq 0 \} \\
	& = & MC
\end{eqnarray*}
But we also note that there exist paths $P$ that almost exclusively consist of
handshake cycles with delay $MC$, except for a begin part and end part. As
$k \rightarrow \infty$, we have for delay $D_k$ on these paths
\begin{eqnarray*}
\lim_{k \rightarrow \infty} (D_k + \delta_e)/(k+1)
	& = & \lim_{k \rightarrow \infty}
		(k \cdot MC + \Dr{0} + \delta_e)/(k+1) = MC
\end{eqnarray*}
From the above two equations we find that
$\max \{ D_k + \delta_e)/(k+1) \;|\; k \geq 0\} = MC$.
Consequently
\begin{eqnarray*}
{\it AR} & \leq & \max \{ D_k + \delta_e)/(k+1) \;|\; k \geq 0 \} - 
\delta_e =  MC - \delta_e
\end{eqnarray*}

We can use a similar explanation to prove the lower bound.
Let the same paths exist as before except the delay on each
non-environment edge is minimized. Let the critical path of length $2k +1$
have delay $d_k$. Since we are trying to find a lower bound,
we have to maximize the environment delay when we subtract it.
We obtain
\begin{eqnarray*}
{\it AR}	& \geq & \max \{ d_k -k \Delta_e)/(k+1) \;|\; k \geq 0 \}\\	
	& = & \max \{ d_k + \Delta_e)/(k+1) \;|\; k \geq 0 \} - \Delta_e
\end{eqnarray*}
The same steps as above show
that $\max \{ d_k + \Delta_e)/(k+1) \;|\; k \geq 0 \} = mc$ and the
result follows.
$\Box$\\

\vspace{-0.01in}
The above theorem states that the average response time
of a pipeline is bounded by two bottlenecks.
One bottleneck is described by the minimum
cycle time $mc$ and the other by the maximum
cycle time $MC$. These bottlenecks need not
occur at the same place in the pipeline.
If one has the freedom
to rearrange stages in the pipeline one might
be tempted to split up stages that have a large cycle
time between them so as to minimize $MC$. Two remarks are in order,
however. Firstly, if the reverse latency of stages are identical,
then there is no benefit in rearranging
stages.  Secondly, our formulae are only dealing
with bounds. As a consequence, these formulae say what happens to the bounds
of the average-case response time under any  rearrangement of stages, but they do
not say what happens with the actual average-case response time.

\vspace{-0.065in}
\section{An Example Micropipeline}
\label{sect:example}

We refer back to the example given in
section~\ref{sect:micropipeline} where we have a pipeline
with $L=3$.
We instantiate the delay elements as in Table~\ref{tab:delay_elts}.
%These apply to the micropipeline as in~\ref{fig:micropipeline_appl}.
After some calculations we find that the minimum cycle time $mc =
\Delta_e +
\dr{0} = 4 + 1 = 5$ and the maximum cycle time $MC = \Df{1} + \Dr{2} = 5 + 3 =
8$.

Suppose we are interested in average response time.
Since $mc - \Delta_e \leq {\it AR} \leq  MC - \delta_e $
we have $1 \leq {\it AR} \leq 6$. 
If we are interested in worst-case response time, we need to do (a little) more
effort to instantiate our formulae.
Skipping some steps we have,
\begin{eqnarray*}
{\it RT} & \leq & \max (\{ \Dr{k} + \Df{k-1} +
	\sum_{h=0}^{k-1}(\Dhr -\dhr)
	- \delta_e \;|\; 1 \leq k \leq L \} \cup \{ \Dr{0} \}) \\
	& = & \max( \{ 3,6,7 \} \cup \{ 1 \}) \\
	& = & 7
\end{eqnarray*}
\vspace{-0.40in}
\begin{table}[htbp]
  \begin{center}
	\begin{tabular}{|c|c|c|c|c|} \hline
		$h$ & $\dhf$ & $\Dhf$ & $\dhr$ & $\Dhr$ \\ \hline
		$e$ & $2$ & $4$ & $--$ & $--$ \\ \hline
		$0$ & $2$ & $4$ & $1$ & $1$ \\ \hline
		$1$ & $1$ & $5$ & $1$ & $1$ \\ \hline
		$2$ & $1$ & $3$ & $1$ & $3$ \\ \hline
		$3$ & $--$ & $--$ & $2$ & $4$ \\ \hline
	\end{tabular}
  \end{center}
\vspace{-0.1in}
\caption{Delays for a pipeline of length $L=3$.}
\label{tab:delay_elts}
\end{table}

%For $n=1$ we
%have the formula.
%\begin{eqnarray*}
%{\it RT} & \leq & \max (\{ \Dr{k} + \Df{k-1} +
%	\sum_{h=0}^{k-1}(\Dhr -\dhr)
%	- \delta_e \;|\; 1 \leq k \leq L \} \cup \{ \Dr{0} \})
%\end{eqnarray*}
%We have to calculate the value for all values of $1 \leq k \leq L$.
%For $k=1$ we have
%\begin{eqnarray*}
%\Dr{1} + \Df{1-1} + \sum_{h=0}^{1-1}(\Dhr -\dhr)- \delta_e
%	& = & 1 + 4 + \sum_{h=0}^{0}(\Dhr - \dhr) - 1\\
%	& = & 1 + 4 + \Dr{0} - \dr{0} - 1\\
%	& = & 1 + 4 + (1 - 1) - 1\\
%	& = & 4
%\end{eqnarray*}
%For $k=2$ we have
%\begin{eqnarray*}
%\Dr{2} + \Df{2-1} + \sum_{h=0}^{2-1}(\Dhr -\dhr)- \delta_e
%	& = & 1 + 4 + \sum_{h=0}^{1}(\Dhr - \dhr) - 1\\
%	& = & 3 + 5 + (\Dr{0} - \dr{0}) + (\Dr{1} - \dr{1}) - 1\\
%	& = & 3 + 5 + (1 - 1) + (1-1) - 1\\
%	& = & 7
%\end{eqnarray*}

\vspace{-0.3in}
\section{Conclusions}
\label{sect:conclusions}

For linear pipelines with a simple handshake behaviour,
we have given formulae for bounds on the average and worst-case
response time. Although the formulae are  simple, one must always be
aware that we are dealing with bounds and that the formulae do not express what
happens with the actual worst and average-case response times under a specific
delay distribution.   

The bounds on the average-case response
time are dependent only on two bottlenecks in the pipeline
and not on the pipeline length. 
One  bottleneck constrains the maximal average throughput, and the other
bottleneck constrains the minimal average throughput. Both bottlenecks
depend on a cycle of forward and reverse latencies between
two stages.  This observation led to the conclusion that we can minimize the
bounds by minimizing the cycle times $mc$ and ${\it MC}$ between
cells. 

%Studies have shown~\cite{Kearney95}
%that as the variance of the stage delays goes
%up, and as the length of the pipeline goes up,
%the stage delays tend towards their upper bounds due
%to blocking phenomena. Hence the average delays
%would tend towards the upper bounds also.

The upper bound for the worst-case response time
depends mainly on the reverse latencies and the length of the pipeline. The
formula contained only one term with a forward latency. This formula led to
the conclusion that we can minimize the bound for the worst-case response
by putting a stage with a big delay closer to the front of the
pipeline.

%For pipelines with handshake multiplicity $n>1$ we
%can show that all measures are independent of the
%length of the pipeline provided that the delays
%of cells are bounded. The cells are bounded
%by an exponential term relating to their depth in
%the pipeline. This means that we can choose cells with
%exponential bigger delays than than their predecessors
%and still have delays bounded by the delay of cell $0$.
%As long as we make cell $0$, we can design the other
%cells optimizing for area or energy usage without affecting
%worst-case performance.

\vspace{-0.065in}
%\twocolumn
\small{
\bibliographystyle{abbrv}  
\bibliography{/u/rtberks/backup,/u/jebergen/notes/response-time/mybib,http}
}
\end{document} 

