\chapter{Immediates overview}
\label{cha:limm-overview}

A large part of this thesis is devoted to the issue of encoding
immediates in the MOVE processor. In this chapter, an introduction on
immediates in MOVE is given. In section~\ref{sec:whatareimm} and
\ref{sec:immother} and
general overview on immediates and their implementation in other architectures
is given, and in section~\ref{sec:immmove} the current state of
immediates in MOVE is given.
The next two chapters will deal with the implementation of the new
immediate framework and a review on the implemented code.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{What are immediates}
\label{sec:whatareimm}

A processor usually has different ways to supply operands to its
operations. Usual ways include register reference mode ({\small \tt
add~r3,~r1,~r2}) and immediate mode ({\small \tt add~r3,~r1,~\#234}).

An immediate is a way to pass a constant value directly from the
instruction stream to an operation in the processor. To encode an
immediate in the instruction stream, caution has to be taken. An
immediate can take up relatively many bits of the instruction word,
e.g. you only need 5 bits to encode 32 registers, but you need already
10 bits to be able to specify, e.g. constant 911.  If you want to do
an add of two constant 32bit values into a register, you need to
encode, apart from the result register, 64 additional bits. To handle
the encoding of large immediates into the instruction stream,
different architectures have come up with different solutions.

Encoding immediates in the instruction stream poses several problems:
\begin{itemize}
\item As already mentioned, the code size will increase, since
constants take a lot of bits, especially compared to (efficient)
encodings for the address space for registers.
\item If the immediate bits are separated from the operation that uses 
them, scheduling becomes more difficult.
\item We can distinguish between signed and unsigned immediates. Care
has to be taken when sign-extending immediates to fit a certain
immediate field.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Immediates in other architectures}
\label{sec:immother}

Before we discuss the implementation of immediates, we will describe
how other common architectures have solved the problem of immediates.


\subsection{CISC}
As an example on how a typical CISC machine has solved the immediate
problem, we'll take the x86 instruction set as an example.  The actual
name CISC (``Complex Instruction Set Computer'') indicates
that its instruction set can be very specific and large. A common
feature of CISC is that is has many different addressing modes. We'll
take the example of the x86 ``ADD''~\cite{x86intel} instruction here,
and list all possibilities of using this ``ADD'' instruction with an
immediate operand.

\begin{table}[htb]
\begin{center}
\small
\begin{tabular}{|l|l|l|}
\hline
{\bf Opcode}	& {\bf Instruction}	& {\bf Description}\\
\hline
04 ib		& ADD AL, imm8		& Add imm8 to AL\\
05 iw		& ADD AX, imm16		& Add imm16 to AX\\
05 id		& ADD EAX, imm32	& Add imm32 to EAX\\
\hline
\end{tabular}
\end{center}
\caption{Partial X86 ADD instruction reference}
\label{tab:x86add}
\end{table}

As you can see, this typical example of CISC deploys multiple
immediate lengths per instruction, some of them even with their own
opcode. Also noteworthy is the fact that the length of the instruction 
word depends on the size of the immediate used (which is by the way
not uncommon for CISC machines, since they deploy this mechanism
already to be able to encode various addressing modes)


\subsection{RISC}
As an example for immediates used in a typical RISC (``Reduced
Instruction Set Computer'') machine, we take
the PA-RISC2.0 architecture from HP~\cite{hpcomputerorg}.
The following table lists some instruction formats of the PA-RISC2.0:


\begin{figure}[htb]
\centerline{\epsfxsize=10cm \epsfbox{fig/parisc.eps}}
\caption{PA-RISC2.0 instruction format}
\label{tab:parisc}
\end{figure}

Interesting features to point out here are:

\begin{compactenumerate}
\item All PA-RISC2.0 instructions are 32 bits wide. This already constrains
the ways to encode an immediate in an instruction. 
\item All instructions of a certain class have the same structure, with fields
that specify source and destination registers, immediate constants and
opcodes in the same bits of the instruction word.
\item Constants in register-immediate operations are always 16 bits
long. This implies that the PA-RISC2.0 architecture cannot do direct
arithmetic operations on constants larger than 16 bits. If it needs
larger constants, then these have to be either constructed from smaller
values, or stored in memory and loaded in a register, so that
register-register type operations can be used.
\end{compactenumerate}

\subsection{VLIW}
As in introduction to immediates in the MOVE architecture, a look at
how typical VLIW (``Very Large Instruction Word'') machines
handle immediates is very useful, as the actual instruction word
format of the MOVE resembles a VLIW very much.
VLIWs are by design bound to the same principle of RISC: All
instructions in an instruction word have to be the same
size. Actually, a VLIW is nothing more (from an instruction word
encoding point of view) than a series of RISC instructions (sometimes
called 'atoms' or 'slots') concatenated.
Examples of VLIWs are:
\begin{itemize}
\item The Intel IA-64 architecture (3 issue). This is not a genuine VLIW, but
has interesting properties, also in relationship to MOVE.
\item The Philips Trimedia (5 issue). The Trimedia is a DSP chip, MOVE 
is also targeted towards DSP applications.
\item Texas Instruments C6x series (8 issue). The TI C6x series is
also a DSP architecture.
\end {itemize}

We will discuss the IA-64 architecture in greater detail now:

The Intel IA-64 architecture, albeit not a genuine VLIW, is a VLIW
based architecture, called the EPIC~\footnote{Explicit Parallel
Instruction Computing} architecture, and has a special type of operation
called 'Extended', in which two slots together form a 60 bit immediate
suitable for e.g. address displacements in a relative branch. A so
called ``template'' of 5 bits at the beginning of the instruction word
contains, amongst other information, information on what kind of
instructions the various slots contain~\cite{ia64-intel}. Note that
you will see that the solution for immediates in the MOVE framework
resembles the solution that the developers of the IA-64 architecture
came up with.

Figure~\ref{tab:ia64} shows a sample of IA-64 instruction format. The
template ``t'' specifies what kind of instructions each slot
contains. The special ``instruction'' {\tt L+X} indicates that this
slot encodes long immediate bits. The other instructions {\tt A}, {\tt
B} and {\\ M} represent other type of instructions, like ALU
instructions, branch instructions or memory instructions.

\begin{figure}[htb]
\centerline{\epsfxsize=8cm \epsfbox{fig/ia64.eps}}
\caption{Sample IA-64 instruction stream; 128 bits wide}
\label{tab:ia64}
\end{figure}




%Another VLIW architecture which has been recently developed is the
%Crusoe processor. The Crusoe, developed by Transmeta Corporation, is
%special since its native instruction set is the IA-32 instruction set
%by Intel. Crusoe has special software, called the ``Code Morphing''
%software, to convert the x86 code into its own microcode, which runs
%on a VLIW core. This very simple VLIW core, with 4 FUs, and hence 4
%instruction (of 32 bits) in a 128 bits instruction word,



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Immediates in MOVE}
\label{sec:immmove}

This section explains what the existing state of the implementation of
immediates in the MOVE architecture was until now. Also, some key
problems of the current state are highlighted, so a good motivation
for a new implementation can be formed, before a new way of handling
immediates is presented in chapter~\ref{cha:limm-impl}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Existing implementation}

The MOVE architecture is from a instruction  encoding point of
view a VLIW. That means several fixed-width operations are
concatenated to form a wide instruction word, with one slot per data
transport (as opposed to one slot per functional unit in regular
VLIWs). So we have the same problems as current RISCs and VLIWs have,
as they were presented in the previous section. To highlight a few:

\begin{compactenumerate}
\item Fixed width slots. If an immediate is larger than the
instruction slot width, one cannot encode the whole immediate in one
slot. And this is without taking into account the space needed for the 
opcode, a destination register, et cetera.
\item Fixed instruction formats. Since MOVE has a standard instruction 
format to make the job of the Instruction Decode unit as simple as
possible, it's not possible to assign arbitrary fields of a slot to
immediate bits.
\end{compactenumerate}

Some other considerations that make MOVE instructions different from
other architectures:

\begin{compactenumerate}
\item Since a move consists of only one data transport, the only part
of the instruction that can contain an immediate is the source of the
move. This is different from an OTA based RISC architecture, where we
usually have three operands: Two source operands, which both can
contain an immediate, and a result operand, which cannot contain an
immediate. Some instructions don't even have a result operand
(e.g. the jump instruction).
\item There is no opcode field for the whole operation in a move. This
makes it harder to actually let the processor know we have an
immediate in a move instead of a reference to a functional unit
socket.

\end{compactenumerate}


The current solution offered for immediates in MOVE is the following:

\begin{compactenumerate}
\item Immediates shorter than the space reserved for the source socket 
can be encoded in the source field of the move
itself. This is done by reserving part of the opcode space of the
source field for constants.
We call this type of immediate the ``short immediate''.

\item Immediates larger than the short immediate are placed in one or
more 
reserved fields that are concatenated at the end of the instruction
word. This is encoded by added sockets to the instruction set, one for 
each immediate field you add to the instruction word. Each cycle the
immediate fields are read (even if the actual information in that
field is void in that cycle) and placed in an ``immediate register'',
which resides in the Instruction Fetch Unit. A source field of a move
then can address the socket connected to that immediate register to
use the immediate value. 
\end{compactenumerate}

This solution is visualized in figure~\ref{fig:dedicated}.

\begin{figure}[htb]
\centerline{\psfig{figure=fig/dedicated.eps}}
\caption{Dedicated immediate slot in instruction word}
\label{fig:dedicated}
\end{figure}

Algorithm~\ref{alg:findimmmovebus} is a pseudo algorithm of the
current long immediate scheduling, as performed in the function 
{\tt FindImmMoveBus}. First, it is checked whether an immediate is
able to fit in the source field of a move. If so, the standard
movebus-allocation code is called. This allocation code includes
adding a candidate mask for this move to the cycle and check via the
Bipartite Matching Algorithm if a correct schedule is possible. If
the immediate fits and the move can be scheduled correctly, a success
is returned. If the move doesn't fit in the source fields, we have a
long immediate. All immediate registers are then iterated. For each
immediate register, a check is done if the immediate register can hold 
the immediate under schedule. If this is also true, all that remains
is check the movebus allocation with the candidate mask that relates
to the chosen immediate register. By claiming the move and the
immediate register, the dedicated field that contains the actual
immediate bits is claimed implicitly.




\begin{algorithm}[htb]
\caption{FindImmMoveBus}
\begin{algorithmic}
\STATE // check to see if the immediate fits in the source field
\FORALL{destination sockets}
	\FORALL{movebus}
		\IF{{\bf not} immediate fits in source field}
			\STATE continue
		\ENDIF
		\STATE check other resources
		\IF{all resource demands met}
			\STATE add movebus to candidate mask
		\ENDIF
	\ENDFOR
	\STATE try movebus allocation
	\IF{movebuses are allocatable}
		\STATE add possible scheduling
	\ENDIF
\ENDFOR
\IF{possible scheduling was found}
	\STATE choose best possible scheduling
	\STATE assign resources
	\STATE {\bf return} SUCCESS
\ELSE
	\STATE // immediate didn't fit in src field
	\FORALL{immediate registers}
		\IF{{\bf not} immediate fits in immediate register}
			\STATE continue
		\ENDIF
		\FORALL{destination sockets}
			\FORALL{movebus}
				\STATE check other resources
				\IF{all resource demands met}
					\STATE add movebus to candidate mask
				\ENDIF
			\ENDFOR
			\STATE try movebus allocation
			\IF{movebuses are allocatable}
				\STATE add possible scheduling
			\ENDIF
		\ENDFOR
	\ENDFOR
\ENDIF
\IF{possible scheduling was found}
	\STATE choose best possible scheduling
	\STATE assign resources
	\STATE // by claiming the ireg, the dedicated move slot is
		automatically claimed too
	\STATE {\bf return} SUCCESS
\ELSE
	\STATE {\bf return} FAILED
\ENDIF

\end{algorithmic}
\label{alg:findimmmovebus}
\end{algorithm}


The approach that is currently used for implementing immediates in
MOVE suffers from various drawbacks that limit the optimal use of
resources offered by the MOVE architecture. These drawbacks are:

\begin{compactenumerate}
\item Since every move instruction word contains a fixed immediate
field, in cases where there are no immediates used, this field stays
empty and bits in the instruction stream are wasted. Especially in  
embedded processors, program memory space is costly.
\item Since one move instruction word can contain only a limited
number of (long) immediates (usually one), moves might have to be
scheduled in another cycle, only because the long immediate value can
not be put in that cycle, while all other resource requirements are
met.
\end{compactenumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Possible solutions}

Because of above mentioned problems, a new scheme to implement
immediates in MOVE had to be devised, one which would address above
mentioned limitations of the current implementation.

Initial thought on a new implementation can be read
in~\cite{limmoptions}. This document describes basic options for
implementing long immediates, without caring too much about practical
implementation. 

The following basic options for encoding long immediates were
considered:

\begin{compactenumerate}
\item {\bf Larger source.} Extend  the size of the
whole move slot to accommodate for the whole immediate to fit in the
source field of the move.
\item Add a {\bf dedicated immediate field} to the move instruction
format. This is actually the implementation used historically, but has 
many problems, as seen in the previous section.
\item Use {\bf multiple instruction formats}. This could be either replacing 
some move slots in the instruction word with immediate bits, or
replacing a whole instruction word with immediates bits. The latter is 
the solution chosen by the ``MicroMove'' implementation of the MOVE
architecture.
\item {\bf Immediate construction.} Various move source fields 
(which can contain only a limited number of bits) can together make up
one large immediate. This can be done either {\bf sequential} or in
{\bf parallel}.
\end{compactenumerate}

For a more in-depth discussion on these solutions, please
see\~cite{limmoptions}. 
This document also contains a preliminary overview of properties of
above mentioned solutions, which will be repeated for clarity in
table~\ref{tab:limmprop}.


\begin{table}[htb]
{\footnotesize
\centerline{
\begin{tabular}{|l|c|c|c|c|c|} \hline
property & Source & Dedicated & Multiple & Sequential & Parallel \\
 & fields & imm. fields & instr. formats & imm. construction
& imm. construction \\ \hline
area                        & + & + & + & --& + \\
instr. bandwidth            & --& --& $\pm$ & + & $\pm$ \\
move bus utilization        & + & + & --& --& --\\
latency                     & + & + & + & --& + \\ \hline
\end{tabular}
}
}
\caption{Properties of long immediate encoding options, qualitative
indication}
\label{tab:limmprop}
\end{table}

As concluded by the document, a practical solution would probably be
a combination of the basic ideas of this table.
So far, two implementations have been made. The first, dubbed the
``resource variant'', which is the one that this report is about, had
a set of additional requirements, see section~\ref{ssec:requirements}.
The other implementation, dubbed the ``pseudo-move variant'', has been 
implemented by TNO-FEL. This implementation, and its performance in
relation to the ``resource variant'', can be found in
section~\ref{cha:pseudo}.  Both variants use a combination of the
``multiple instruction format'' and the ``parallel immediate
construction'' ideas.
The rest of this chapter will discuss the road to the ``resource
variant'', and the next chapter will discuss its implementation.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Requirements of a new implementation}
\label{ssec:requirements}

A list of requirements of the new immediate implementation was made:

\subsubsection*{The instruction stream}
\begin{compactenumerate}
\item An immediate that does not need more bits than the source field 
of the move should not take any space outside that move. This is what
we call a ``short immediate''. The other requirements listed deal with 
the concept of a ``long immediate'', i.e. an immediate that does not
fit in the move itself.
\item If an immediate does not fit in the source field of a move
itself, extra bits of the instruction stream are needed. Preferably,
these extra bits should be drawn from unused bits in the instruction
stream.
\item A reserved slot just for immediates is optional, as these
would be wasted in case there is no immediate to be scheduled.
\item A decoupling between immediate value and its move introduces
extra state, which needs to address two things: A dependency between the 
immediate value and its move, and a bookkeeping mechanism that keeps
track where the immediate value is placed in the instruction word and
the instruction stream.
\end{compactenumerate}

\subsubsection*{The scheduling algorithms}
%\begin{compactenumerate}
%\item 
The newly implemented algorithms should interfere as less as
possible with the also existing scheduling algorithms. The current
source has a lot of implicit assumptions that could cause unwanted
effects if the new algorithms aren't made as stand-alone as possible.
%\end{compactenumerate}

\subsubsection*{The background of the assignment}
%\begin{compactenumerate}
%\item 
Although the MOVE project needed a recode of the long immediate
implementation because of reasons mentioned in the previous
paragraphs, the problem became more urgent when an actual hardware
implementation of the MOVE framework was to be deployed at NEC
CCRL. The machine description of the
NEC variant of the MOVE processor was already finalized. Although the
implementation would be incorporated in the standard MOVE scheduler,
rudimentary performance decisions were primarily made based upon a
machine description of the NEC processor core.
%\end{compactenumerate}


After careful review of all options, a combination of the ``multiple
instruction format'' and the ``parallel immediate construction'', as
explained in \cite{limmoptions} has
been chosen. The proposal for this new implementation, called the
``resource variant'' can be found in section~\ref{sec:proposal}.
