\chapter{The MOVE Framework}
\label{cha:move}

Due to the decreasing feature size of VLSI technology, the amount of hardware
which can be integrated into a single chip increases. As a result, future
processor chips may execute tens of operations concurrently.
Many applications can profit from these huge amounts of hardware
parallelism by designing an application specific instruction set processors
(ASIP).
Two problems emerge however: (1) the design space of ASIPs is very large; it
is difficult to chose a satisfactory solution, and (2) the design complexity 
increases and therefore design cycle gets too long.

To alleviate these problems a design trajectory based on a
{\em templated, transport triggered architecture} (TTA) has been
developed.  Using a restricted, but still very large, design space
it is possible to automate the design trajectory based on a quantitative
analysis of many design points.
A key aspect of TTAs is the reduction of the on-chip data transport
requirements; this may result in a better cost-performance ratio of the
realized ASIPs.
In this chapter we discuss an automated design process for ASIPs using
the {\em MOVE framework}.

The chapter is structured as follows: Section~\ref{sec:framework} explains
the MOVE framework, and discusses briefly how TTAs operate.
Then, in section~\ref{sec:move-conclusions} several conclusions are drawn.

%---------------------------------------------------------
\section{The MOVE framework}
\label{sec:framework}

Designing ASICs based on templated application-specific instruction
set processors (ASIPs) is an attractive solution that offers
flexibility and a short design time while still retain part of the
advantages of ASICs. The design process consists of finding the right
architecture parameter values for the given application, such as the
operation set, the amount of instruction level parallelism, and the
sizes of the register files. Also, additions of special function units
that can map a complex task into one single optimized instruction are
possible. The quality of a solution depends on the offered performance
and the implementation costs.

The synthesis framework presented in this section uses
an architecture design space based on a {\em transport
triggered architecture}, or TTA. This architecture is of the {\em
instruction level parallel} type; it resembles the well
known VLIW architectures. However, a key difference is that TTAs are
programmed by specifying data transports instead of operations. This
gives an finer level of control to the code generator, and allows for a
more efficient use of hardware resources.
Although we use a TTA template for designing ASIPs, the design
space is still very large. Picking a proper solution (for a
specific application) from this design space requires a quantitative
analysis of many design points.  This search process must largely be 
automated in order to reduce the design time. Therefore tools are
needed, not only for making the quantitative analysis of hardware and software
(generated code), but also for the automated search. 

The MOVE framework consists of a set of tools for
hardware and software synthesis.  
Within the synthesis process we use an {\em architecture template},
i.e. processors are built according to the pattern of a TTA.  A specific
TTA is defined by a set of architecture parameters, like the number and type
of function units, the number of register files and registers, etc.
At first sight this suggests that we restrict
ourselves and therefore obtain inferior solutions.  In practice
however, several advantages emerge.
Firstly, the template building
blocks are pre-designed and can therefore be made very efficient, both
in area and performance.  Secondly, the architecture pipelining is
worked out very carefully, alleviating many timing bottlenecks;
prototype realizations learned where these bottlenecks exactly are.
Finally, usage of a clearly defined design space allows the design of
synthesis and evaluation tools, which not only generate a combined
hardware and software solution, but also allow a quantitative analysis
of the design space.
Also, note that the template still covers a very large design space.

\begin{figure}[htb]
   \centerline{\epsfxsize=8cm \epsfbox{fig/MOVE-overview.eps}}
%   \newfigh{framework.idr}{0.45\textwidth}
   \caption{MOVE framework overview.}
   \label{fig:framework}
\end{figure}

The synthesis of hardware and software for a given application is done using
the MOVE framework; this framework produces both the layout of an ASIP and
the corresponding object code to be executed on this ASIP.
An overview of this framework is shown in
figure~\ref{fig:framework}.
It  consists of three main components:
\begin{enumerate}
\item{\bf Optimizer} which is responsible for searching the design space and the
interaction with the designer. It determines the configuration (i.e., the set
of architecture parameters) to be evaluated next.
\item{\bf Hardware subsystem} generating processor layout, and giving
  information on timing, area, and power consumption.
\item{\bf Software subsystem} generating instruction level parallel code, and 
  giving statistical information on usage of hardware resources.
\end{enumerate}

These components are detailed in following subsections.
Before, we briefly describe how TTAs operate.

%=========================================
\subsection{Transport triggered architectures}
\label{subsec:tta}

TTAs can be compared to VLIW architectures; their instructions are
horizontally encoded; i.e. each instruction has a number of fields.
Whereas fields for VLIWs specify RISC like operations, for TTAs they
specify the required data transports.  These transports may trigger
operations as side effect.  Programming transports adds an extra level
of control to the code generator, and enables new optimizations; in
particular, it allows us to get rid
of many superfluous data transports to and from the register files and
to reduce the on-chip connectivity\cite{Hoogerbrugge94a}.

A compiler views a TTA as a collection of function units (FUs), register files
(RFs), {\em move buses}, and
{\em sockets}; see figure~\ref{fig-tta}. FUs perform operations, RFs
provide temporary fast accessible storage, the network of move buses performs
data transports between the FUs and RFs, and sockets interface FUs and RFs to
move buses. Normally, each socket is connected to a different FU input/output
or RF port.

\begin{figure}[htb]
%\newfigh{tta.idr}{0.55\textwidth}
   \centerline{\epsfxsize=10cm \epsfbox{fig/TTA-template.eps}}
\caption{General structure of a TTA.}
\label{fig-tta}
\end{figure}

To illustrate TTA programming, consider the following three operations
of an operation triggered machine, or OTA:

\vspace{-0.5ex}
\begin{small} \samepage
\begin{verbatim}
      add  r1, r2, r3  /* r1 = r2 + r3 */
      sub  r4, r2, r6  /* r4 = r2 - r6 */
      st   r4, r1      /* store r4 at address r1 */
\end{verbatim}
\end{small}
%
These operations can be translated into the following two TTA instructions:
%
\vspace{-0.5ex}
\begin{small} \samepage
\begin{verbatim}
      r2->add_o,   r3->add_t,    r2->sub_o; r6->sub_t;
      add_r->st_t, sub_r->st_o;

\end{verbatim}
\end{small}

In the first instruction the four operands of the add and subtract operations
are moved from the RF(s) to the FU inputs of the FUs that perform the two
operations. In the second instruction the results of the add and subtract
operations are moved from the FUs that performed them to the FU that 
performs the store operation. From this small example we already observe a
few advantages of TTAs. The results of the add and subtract operations are
not written back to the RF and the operands of the store operation are not
read from the RF. The former saves RF write accesses and data transports, the
latter saves RF read accesses. Since TTAs do not couple move buses and RF ports
directly to FUs, as is the case for many VLIW and super-scalar architectures,
the freed resources can be used for
other operations. This makes that TTAs have a better hardware utilization,
which implies less hardware for the same performance or more performance with
the same hardware~\cite{Hoogerbrugge94a}.

The interconnection network may be fully connected, as shown in
figure~\ref{fig-tta}, in which case every socket is connected to all
move buses, or partially connected. A fully connected interconnection
network simplifies the code generation task, but it likely results in
a high bus load on the move buses which affects the achievable cycle
time.  Therefore, in practice the interconnection network will be
partially connected and the compiler is responsible to use the
available connections as well as possible.

Besides executing operations on data, TTAs need to provide immediate operands,
conditional execution, and control flow changing operations.
Details on these issues can be found in~\cite{Corporaal95b,Corporaal91}.

%==============================
\subsection{Optimizer}
\label{sec:optimizer}
\begin{figure}[htb]
   \centerline{\epsfxsize=11cm \epsfbox{fig/solution-space.ps}}
\caption{Possible solutions and Pareto points.}
\label{fig:solution-space}
\end{figure}

Two main design evaluation criteria are cost and performance, where
performance is defined as the inverse of execution time. Costs may include
the amount of chip area, number of pins, power dissipation, and code
size\footnote{
  Currently are included area and pins only.
}. Execution time is dependent on the number of executed operations, latencies,
cache misses, and the clock cycle time.
The {\em solution space} is given by all possible design points in the
2-dimensional cost-performance space. Figure~\ref{fig:solution-space} shows
many generated solutions for a test application (described in 
\cite{Corporaal96}). 
As shown, the solution space is bounded by a curve connecting so called
{\em Pareto points}.  

%These points are local optimal solutions; they
%are defined by~\cite{Brayton80}:

%\medskip
%{\bf Definition:}
%{\em A point $(t_p,c_p)$ is a Pareto point if

%$\forall(t,c)\in \mbox{Solution-Space}, (t\geq t_p \vee c\geq t_c)$.
%} 

The optimizer finds its way through this search space by iteratively trying
different architecture solutions, and letting the software and
the hardware subsystems
produce relevant information about these solutions, like cycle time, costs and
number of cycles needed to run the application. Based on this information
a next design point is chosen by updating the parameters.
The initial architecture parameter values can be chosen freely by the user. 
He can also specify an evaluation function (e.g. minimize the product of costs
and execution time), and the stop criteria.

%==============================
\subsection{Hardware subsystem}
\label{subsec:hardware-subsystem}
The hardware subsystem of the MOVE framework is responsible for
the realization of an application specific TTA in silicon.
It accepts architecture
parameter values, technology information and a cell library as input,
and produces a VLSI layout (e.g. in CIF format) of the generated
processor as output. Figure~\ref{fig:hf} shows its organization.

\begin{figure*}[htb]
%\newfigh{hf.idr}{0.7\textwidth}
   \centerline{\epsfxsize=11cm \epsfbox{fig/h-subsystem.eps}}
\caption{The hardware subsystem.}
\label{fig:hf}
\end{figure*}

%The hardware subsystem makes use of the ASA silicon compiler\footnote{
%  ASA is a trademark of SAGANTEC Europe b.v., Eindhoven.
%}, or, alternative relies on Synopsys and Cadence tools.
%Details of this system and realized processors 
%are described in~\cite{Lamberts93}.

The design space explorer makes use of a {\em hardware model} to
estimate the cost of design points.  The costs of FUs are based on a
32-bit data path width\footnote{Although the hardware subsystem can
generate processors for any data width, the software subsystem
currently requires 32 bit integers.}, and relative to an integer FU.
The minimum clock cycle time for a TTA realization is largely
determined by the time needed to perform (and control) data transport.

%==============================
\begin{figure}[htb]
%\newfigh{sf.idr}{0.5\textwidth}
   \centerline{\epsfxsize=10cm \epsfbox{fig/s-subsystem.eps}}
\caption{The software subsystem.}
\label{fig:sf}
\end{figure}

\subsection{Software subsystem}
\label{sssec:sf}

The software subsystem is detailed in figure~\ref{fig:sf}.
It provides the user with three main tools to develop code for
TTAs.  These tools are:
\begin{compactenumerate}
 \item A compiler (referred to also as MOVE front-end) to translate
   HLL (high level language) code to sequential move code
 \item A scheduler (or MOVE back-end) to schedule the sequential code
   and produce parallel code for a target TTA
 \item A simulator and analyzer to verify and evaluate both the
   sequential and parallel code. 
\end{compactenumerate}

The software subsystem accepts any application coded in C or C++
and translates it into text representation of MOVE parallel code
for a specific TTA.
The components of the software subsystem are described in detail
below.

\subsubsection*{Compiler}
The MOVE front-end is a combination of three tools: proper
compiler, assembler and linker. Their relationship is depicted in
figure \ref{fig:front-end}.
\begin{figure}
   \centerline{\epsfxsize=6cm \epsfbox{fig/front-end.eps}}
\caption{Relations between the ported GNU compiler, the assembler and the linker.}
\label{fig:front-end}
\end{figure}
In order to be assured of good code quality, good HLL compatibility, support
for new HLLs and an extensively debugged compiler, a port of GNU C compiler
({\em gcc}), assembler, and linker was made.
These software packages are ported to produce binary sequential MOVE
code for a {\em MOVE generic machine}.
This code is sequentially ordered by instructions; each move referring to
the same operation is grouped in a single instruction, resembling OTA
instructions. Sequential code is used as intermediate representation of
the program and is read by the scheduler.

\subsubsection*{Scheduler}
The scheduler is the most important part of the software subsystem.
Its main function is to schedule moves of sequential code, i.e. to
assign FUs to operations and to assign cycles, sockets and buses to
moves.
The scheduler has to generate instruction level parallel code,
while exploiting all the available hardware resources.
To this purpose, the scheduler uses profiling data
(like execution frequencies) from the simulator.
Several preliminary optimizations on sequential code are
also applied.
The scheduler uses advanced techniques like extended basic block
scheduling, software pipelining, and speculative execution, in order
to enhance code motions and consequently inter basic block
parallelism~\cite{jan:phd}.
All specific optimizations of TTAs (result bypassing, dead moves
elimination, operand sharing) are performed during the scheduling process.
The parallel code is fully parameterized on the template
configuration, which is specified in a machine description file.
In this file processor resources, like supported FUs, amount of registers
and interconnection network are described.
Profiling information is not strictly necessary, but helps the scheduler
to work more efficiently.

\subsubsection*{Simulator}
The simulator accepts either sequential MOVE code or parallel MOVE code.
Its output consists of profiling information, application output and
execution statistics.
The simulator has three purposes in the MOVE framework:
\begin{enumerate}
 \item To verify the compiler and the scheduler. It is virtually impossible
   to port a compiler and write a scheduler without simulating the produced
   code.
 \item To evaluate architecture parameters. The results of the evaluation
   are cycle counts and various statistics about resource utilization and
   compilation events (e.g. the number of operand swaps and the number of
   loop scheduled using software pipelining).
 \item To provide profiling data to the scheduler. Profiling data consist
   of execution counts for each basic block and each control flow edge
   between basic blocks in the program. With this information the scheduler
   can decide which code motion between basic blocks is most profitable.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Conclusions}
\label{sec:move-conclusions}
In this chapter we showed an automated design trajectory for ASIPs based on 
transport triggered architectures. This trajectory has two fundamental
capabilities:
\begin{enumerate}
\item It maps arbitrary applications, written in C/C++, into a combination of
  hardware and software.
\item It offers the possibility to do a quantitative analysis of large parts 
  of the design space.
\end{enumerate}

The search process to find a proper solution consists of resource and
connectivity optimization. Resource optimization attempts to find the
cost effective set of resources. Connectivity optimization reduces the
connectivity in order to reduce bus load and cycle time.  As side
effect it has been demonstrated that the synthesized TTAs require far
less connectivity and fewer register ports than more traditional
instruction level parallel architectures.

