\chapter{The FC0 Execution Units}

 For ease of development and scalability, to name a few reasons, the \index{Execution Units}
Execution Units (EUs) are like LEGO bricks that add new computational capabilities to the 
processor. Like the whole core, they are designed with a full-custom process in mind but can 
be implemented with libraries (if they have the corresponding functions) or in FPGA cells or 
whatever \index{alien technology}alien technology falls from the sky ...
           
 Here are described the minimal necessary EUs that have been considered until today. As they
come, several units can provide the same function (like : shifting left by one is like
multiplying by two or adding the number to itself) so the wisest habit is to check which
unit does what and in how many cycles with wich throughput, in order to pick the best opcode
for the desired operation in each context. Transistor count saving has not been a serious
consideration, more care has been taken to reduce the critical datapath to the minimum
possible.

Because of their different latencies and particularities, the EUs have not been packed
into one "one-fits-all ALU". We can also pick one unit and think about it without caring
of the surrounding units. This way, we see that the hardware being designed provides new
unexpected operations that can be used in the instruction set. When the hardware is in
place, only a few additional logic gates provide useful operations that can spare several
instructions in application software, and speedup some critical algorithms with almost
no overhead.

\section{The "logic" unit (\index{ROP2}ROP2)}

 This is the classical "logic unit". Its purpose is to compute bit-to-bit operations. Due to
its simplicity, it has one cycle of latency and is among the fastest units.

Now, what operations will it execute ? With two inputs, there are 2$^{2^{2}}$=16 possible
operations, from which 8 are unique and useful :

~

\begin{center}
\begin{tabular}{|c|c|c|c|c|l|}
 \hline
            A: &  0 &  0 &  1 &  1 &                                              \\
 \hline
            B: &  0 &  1 &  0 &  1 &                                              \\
 \hline
               & 00 & 01 & 10 & 11 &  Function                                    \\
 \hline
               &  0 &  0 &  0 &  0 &  CLEAR (set to 0) : equiv. to mov res, reg0  \\ 
 \hline
               &  0 &  0 &  0 &  1 &  A AND B                                     \\ 
 \hline
               &  0 &  0 &  1 &  0 &  A AND /B                                    \\
 \hline
               &  0 &  0 &  1 &  1 &  A (do nothing)                              \\
 \hline
               &  0 &  1 &  0 &  0 &  /A AND B (similar to A AND /B above)        \\
 \hline
               &  0 &  1 &  0 &  1 &  B (do nothing)                              \\
 \hline
               &  0 &  1 &  1 &  0 &  A XOR B                                     \\
 \hline
               &  0 &  1 &  1 &  1 &  A OR B                                      \\
 \hline
               &  1 &  0 &  0 &  0 &  A NOR B (equiv. to NOT [A OR B])            \\ 
 \hline
               &  1 &  0 &  0 &  1 &  NOT (A XOR B)                               \\
 \hline
               &  1 &  0 &  1 &  0 &  NOT B (do almost nothing)                   \\ 
 \hline
               &  1 &  0 &  1 &  1 &  A OR /B (equiv. to NOT [/A AND B])          \\
 \hline
               &  1 &  1 &  0 &  0 &  NOT A (do almost nothing)                   \\
 \hline
               &  1 &  1 &  0 &  1 &  /A OR B (similar to A OR /B]                \\
 \hline
               &  1 &  1 &  1 &  0 &  A NAND B (equiv. to NOT [A AND B])          \\
 \hline
               &  1 &  1 &  1 &  1 &  SET to 1 (-1)                               \\
 \hline
\end{tabular}
\end{center}

 ~
 
 Some opcodes are duplicated (if we include operands commutativity), others are not "real" 
2-operands operations (there are 1-op and 0-op operations). We could include directly 4
function bits in the opcode, but we need some room for the "combine" instructions, so we can
save one bit with the use of "condensed" codes. We select the 8 2-operands operations
and create a new table. The decoder can thus avoid to read unnecessary source 
registers. For the ROP2 instructions, the 3 function bits are decoded by a tiny hardwired
lookup table in the decoder as follows :

\begin{center} 
\begin{tabular}{|c|c|l|l|}
 \hline
              opcode  &  real code  &  Function   & Symbolic name   \\
 \hline
               000    &     0001    &  A AND   B  &  AND            \\
 \hline
               001    &     0010    &  A AND  /B  &  ANDN           \\
 \hline 
               010    &     0110    &  A XOR   B  &  XOR            \\
 \hline
               111    &     0111    &  A OR    B  &  OR             \\
 \hline
               100    &     1000    &  A NOR   B  &  NOR            \\ 
 \hline
               101    &     1001    &  A XNOR  B  &  XNOR           \\
 \hline
               110    &     1011    &  A OR   /B  &  ORN            \\
 \hline
               111    &     1110    &  A NAND  B  &  NAND           \\
 \hline
\end{tabular}
\end{center}

 The necessary hardware for computing this function is rather inexpensive :

\begin{figure}[H]
  \begin{center}
     \includegraphics[width=7cm,draft=false]{rop2.eps}
     \caption{Detail of the ROP2 unit}
  \end{center}
\end{figure}

 There are probably a few other technical details to discuss about, but they are too technology
dependent (signal "tree" of the operation bus, for example). This is the most straight-forward
element of the processor.

Because the critical datapath of this unit is so short, we can add some (simple)
functionality~: let's call it the "combine" function. While ROP2 is bit-to-bit, the
"combination" performs the logical AND or OR of each ROP2 result in every SIMD packet
(variable size) of a word. Combined with the ROP2 function, it is possible to perform
complex masks and bit moves with few instructions and less need of shifts.
Remark : due to the large number of inputs, only 8-bit combines are currently implemented.

\begin{figure}[H]
  \begin{center}
    \includegraphics[width=13cm,draft=false]{combine.eps}
    \caption{Description of the COMBINE function on top of ROP2 for a byte-wide SIMD packet}
  \end{center}
\end{figure}

~

VHDL : see the /vhdl/eu\_rop2 directory in the F-CPU package.


\section{The "\index{bit scrambling unit}bit scrambling" unit (\index{SHL})}

 The goal is to have a one-cycle shifting unit that can do other things as well. As opposed to
the ROP2 unit, the principal function is not change the value of the input data bits but to
changes the position of the bits. Therefore, shifting and rotating are only examples of the
intended purposes of this sometimes called "shuffling" unit : bit field extraction and
insertion, as well as bit and byte reversing and bit testing are examples of what this
hardware is meant to perform.

There is a problem, though : F-CPU will be a 64-bit processor and a classical barrel shifter
is a O (log2 (n)) unit, which is fairly close to the pipeline granularity. A shifting array
(a kind of transistor array) will be necessary to get to O (1), at the price of more
transistors and probably more transistor load, but it is the only solution if we want
to shift 128, 256 or 512 bits in one 10-transistor pipeline cycle. During prototyping,
we can use pre-synthetized hardware but a production-class CPU will require something
looking like an Omega network of small shufflers.

 This unit will also perform SIMD specific operations like SIMD word expansion and mixing. A 
little logic unit at the end of the critical datapath could perform bit operations (test, set, 
clear, change) if enough gates are left in the critical datapath.

\begin{figure}[H]
  \begin{center}
     \includegraphics[width=10cm,draft=false]{shl.eps}
      \caption{Overview of the Scrambling unit}
  \end{center}
\end{figure}

~

VHDL : see the /vhdl/eu\_shl directory in the F-CPU package.

 
\section{The "\index{increment unit}increment" unit }

 This is maybe the most curious unit, because it is not usually found in normal CPUs. The
reason for this dedicated unit is simple : a lot of code adds or substracts one, in loops for
example. This is unnecessary work for an adder, if the second operand is one, so let's hardwire
it and run it faster. That was the first idea.

The method to increment a binary number is not complex to understand : you scan the number 
starting from the LSB, inverting every bit until you find a 0. Then, you turn this 0 into 1.
It is in fact a dedicated carry propagation tree with XOR gates at the output. The tree does
the same thing as "find the first LSB set". So, let's go, let's have it too in the 
instruction set. In some cases, it is very valuable, and there's no hardware overhead. This 
makes two instructions : INC and LSB1.

 So now, we can increment, we can also decrement : we have to invert each bit at the input and
the output of the unit. This added hardware lets us also find the "LSB cleared".
Four instructions (add DEC and LSB0). We can also add a bit reverser at the input,
as to find the MSB too. Six instructions (add MSB1 and MSB0 to the I7, and a bit reverser on
the Xbar).

Let's go further : let's put a multiplexer at the end of the incrementer, wich is controlled by
the sign bit of the input value. If the bit sign is set, we set the output to - (n+1) (there is
a bit of juggling to do with inverters but it's just a "technical detail"). With this unit, we
can compute the absolute value of a 2s-complement binary number. Seven instructions (add ABS).
Now that we have these multiplexers at the input and the output of the 'incrementer', we can do
yet more things. Since the incrementer is a "find first bit" binary tree, we can use it to
compare two numbers. The idea is simple, a (positive) number is greater than another if at least
one of its MSBs is set while the corresponding bits of the other number is cleared :
0 $ > $ 1, 11 $ > $ 10 ...

~

So, just XOR the two input numbers, find the first MSB set, and AND the result with one input 
number. If the result is cleared, then this number is lower then the other, and vice versa. 
This makes eight instructions. Still better, we can use the ending multiplexer to select one of
the input values : we can have the min and max instructions, as well as the derivated like 
\textit{``if~reg1~$ > $~reg2~then~reg1=reg2''} (for graphics, in coordinates clipping, or saturated
arithmetics...). We can have more than ten useful instructions with this simple
single-cycle unit~! Some are very useful because they usually involve conditional branches
(and pipeline stalls or branch mispredictions...).

~

 From a purely abstract point of view, finding the first set bit is done with a "binary tree",
so the depth of the unit is O (log2 (n)) with rather simple "nodes". This is almost a schoolbook
case to design. Anyway, like for the shifter array, there are be some problems to 
fit it in the pipeline's stage depth, mainly for the compare and clip instructions...
At least, the INC, DEC, ABS, NEG (and their SIMD variants) are possible in practice
with a strong timing constraint.

~

 In this unit, I have not yet addressed the problem of the SIMD data. Comparing signed numbers 
is straight-forward though : we just have to XOR the sign bit of each SIMD chunk.

~

The current implementation of the INC unit, doing \textit{inc, dec, neg and abs}, fits 
in the 6 gates depth of critical datapath. It is composed of a first line of XORs, a 3-gates
deep AND tree, a line of multiplexors and a last stage of Xors.

~

\begin{figure}[H]
  \begin{center}
     \includegraphics[width=5cm,draft=false]{inc_block.eps}
      \caption{Description of one block of the AND tree}
  \end{center}
\end{figure}
 
~

\begin{figure}[H]
  \begin{center}
     \includegraphics[width=17cm,draft=false]{inc.eps}
      \caption{Overview of the Incrementer Unit (preliminary version)}
  \end{center}
\end{figure}

The output of the last XOR stage can be fed to another pipeline stage that
will perform the remaining operations (LSBx, MSBx, min, max ...).

You can remark that the Xbar cycle can be used to amplify a single signal
to a large number of inputs. The Xbar gives enough time/gates to compensate
such a large fanout.

~

VHDL : see the /vhdl/eu\_inc directory in the F-CPU package.


\section{The \index{add/sub unit}add/sub unit}

 Using a carry-lookahead adder, it needs around two cycles to complete a 64-bit addition or 
substraction~: it is a O (log2 (n)) process with some more heavy mechanisms than the
incrementer, but it computes a 8-bit add/sub in one cycle. Therefore, SIMD with 8-bit data
is fast (1 cycle instead of 2). For these reasons, it would is difficult to use standard
pre-synthetized elements because of the variable-depth and SIMD nature of this unit.
Saturation (signed and unsigned) is desired, with a possible additional latency of one cycle.

~

VHDL : see the /vhdl/eu\_asu directory in the F-CPU package.


\section{The \index{integer multiply unit}integer multiply unit}

 Here, same remarks as for the adder. There are SIMD constraints and a variable-depth, 
fine-grained pipeline (depending on the width of the input data). It will be difficult to find
this kind of unit in pre-synthetized libraries. Today's unit does a 64-bit MAC in 6 cycles.

~

VHDL : see the /vhdl/eu\_imu directory in the F-CPU package.
 
\section{The \index{integer divide unit}integer divide unit}

 Same as the multiplier. Notice, though, that a divide by zero can be caught at decode time 
with the "zero" property flags. We can trigger a trap without issuing the instruction.
An old substract-shift unit can be enough because it is not used often. If faster divisions
are required, the Newton-Raphson method can be used.

~

VHDL : see the /vhdl/eu\_idu directory in the F-CPU package.


\section{The \index{Load/Store unit}Load/Store unit}

 This is a very special case because no actual computation is performed. The latency is
completely unknown at compile time, and there is the problem of the memory protection.
If the memory protection is ensured by other mechanisms, the L/SU is simply a big cache
buffer with a crossbar to perform the word/endian selection. Notice that its structure
is similar to the instruction fetcher unit : it is mirored with a different granularity.

~

When there is no cache miss or buffer to flush, the data can be directly sent or read
from the buffer through the L/S crossbar then sent to the main Xbar. In the ideal case,
there is no latency for memory writes and 1 cycle for memory reads. The memory fetch
logic tries to keep the buffers full when contiguous accesses are performed. A
double-buffer (with a pair of line buffers) can hide the memory latency to a certain
extent.

~

The memory buffer can "cache" eight cache lines (the number of lines may vary with
implementations). It communicates with the external memory data bus, the data cache
memory and the main Xbar. This reduces the latency when recovering from cache misses,
and simplifies the cache memory organisation because the L1 cache does not communicate
directly with the external memory : the memory buffer (L/SU) is used to split the large
cache line into smaller
chuncks that can be sent to the memory interface. Not only the LSU stores data but it
plays a major role in the memory hierarchy, in the cache replacement cycles and the
cache coherency in a multi-bus interface with a limited set of buffers that are used
for several functions.


~

VHDL : see the /vhdl/eu\_lsu directory in the F-CPU package.


\section{\index{population count unit}Population count / \index{Single Error Correction Unit}Single Error Correction (\index{POPC}POPC)}

This is an optional special multicycle unit wich performs \index{SEC}SEC and POPC functions.

The POPC instruction also performs saturated substraction with the 6-bit result (see the
popc instruction description in part 6).

The SIMD chuncks are basicly 64-bit wide, but nothing keeps the designer to support other
granularities.

~

VHDL : see the /vhdl/eu\_popc directory in the F-CPU package.


\section{Other units}

 The floating point numbers have not been discussed, because we better have something that
works correctly in the integer domain first, we'll add FP hardware and instructions later.
The case of the math exceptions will be probably managed with the same kind of mechanism as
the "zero" property flag, so no error will break the execution pipeline flow.

 One "cheap" way to avoid the use of floating point numbers is by using the logarithmic
number base (LNS). Recent works succeeded in making a 32-bit logarithmic adder with descent
speed and die space use. Any other operation (SQRT, SQR, multiply, divide...) can be
performed by existing hardware (maybe slightly modified for the MSB). The conversion
between integers and log numbers will be a rather heavy software task, as long as no
hardware exists. A cooperation with other research teams is encouraged.

 When FP hardware will become available, only add/sub and multiply units will be
implemented at first. Any other mathematical operation (including division) will
be computed with a Newton-Raphson approximation algorithm in software. A third
unit will provide the "seed" from hardwired ROM tables.

\section{Extensions and scalability}

 If you want to add your own custom Execution Unit to the F-CPU, it is rather simple~:
you first have to prepare the Instruction Set map and the decoder, so the necesary
instructions are easy to decode and they don't conflict with other instructions. Then,
you have to ensure that the scheduling and the exceptions don't jeopardize the decoder
unit's structure (see the discussions in the following parts). Finally, you ``plug''
your unit on a newly created port of the Xbar.

 Depending on your target technology, you can add an undetermined number of new units :
the FC0 architecture does not limit the number of physical execution units. The physical
limits are however important and the Xbar can't be extended endlessly : the design goal
(6-gate critical datapath with 4 input max. per gate) must also be respected.

~

The widths of the data are also the parameters that play in favor of the FC0 and the
F-CPU in general : the extension of the register width or the chunk width allow the
engineer to scale the design up easily. Again, the design goals must be respected but
this is another simple way to extend the architecture without redesigning everything
from scratch. For example, the register width and the chunk width are decoupled,
so they can be changed independently.
