\chapter{A bit of F-CPU history}
\textbf{(And a reflexion on the evolution of the F-CPU through a description of the different
 proposed architectures)}


\section{M2M}


 The first generation was a "memory to memory" (M2M) architecture that disapeared with the
original F-CPU team members (they have written the previous text). It was believed that
context switch time consumed much time, so they mapped memory regions to the register set,
as to switch the registers by changing the base register. I have not tracked down the reasons
why this has been abandonned, I came later in the group. Anyway, they launched the F-CPU
project, with the goals that we now know, and the dream to create a "Merced Killer".
Actually, i believe that we should compete with the ALPHA directly ;-)


\section{TTA}

 The second generation was a "Transfer Triggered Architecture" (TTA) where the computations
are triggered by transfers between the different execution units. The instructions mainly
consist of the source and destination "register" numbers, which can also be the input or
output ports of the execution units. As soon as the needed input ports are written to,
the operation is performed and the result is readable on the output port. This architecture
has been promoted by the anonymous AlphaRISC, now known as AlphaGhost. He has done a lot of
work on it but he has left the list and the group lost track of the project without him.

~

Brian Fuhs (bkfuhs1@attglobal.net) explained TTA on the mailing list this way :

\begin{verbatim}
TTA stands for Transfer-Triggered Architecture. The basic idea is that you don't tell
the CPU what to do with your data, you tell it where to put it. Then, by putting your
data in the right places, you magically end up with new data in other places that
consists of some operation performed on your old data. Whereas in a traditional OTA
(operation-triggered architecture) machine, you might say "ADD R3, R1, R2", in a TTA
you would say "MOV R1, add; MOV R2, add; MOV add, R3". The focus of the instruction set
(if you can call it that, since a TTA would only have one instruction : MOV) is on the
data itself, as opposed to the operations you are performing on that data. You specify
only addresses, then map addresses to functions like ADD or DIV.

That's the basic idea. I should start by specifying that I'm focusing on general
processing here, and temporarily ignoring things like interrupts. It is possible to
handle real-world cases like that, since people have already done so; for now, I'm
more interested in the theory. Any CPU pipeline can be broken down into three basic
stages : fetch and decode, execute, and store. Garbage in, garbage processing, garbage
out. With OTAs this is all done in hardware. You say "ADD~R3,~R1,~R2", and the hardware
does the rest. It handles internal communication devices to get data from R1 and R2 to
the input of the adder, lets the adder do its thing, then gets the data from the output
of the adder back into the register file, in R3. In most modern architectures, it
checks for hazards, forwards data so the rest of the pipeline can use it earlier, and
might even do more complicated things like reordering instructions. The software only
knows 32 bits ; the hardware does everything else.

The IF/ID stage of a TTA is very different. All of the burden is placed on\\
software. The instruction is not specified as ADD (something), but as a series of\\
SRC, DEST address pairs. All the hardware needs to do is control internal busses\\
to get the data where it is supposed to go. All verification of hazards, optimal\\
instruction order, etc should be done by the compiler. The key here is that a TTA,\\
to achieve IPC measures comparable to an OTA, must be VLIW : you MUST be able to specify\\
multiple moves in a single cycle, so that you can move all of your source data to the\\
appropriate places, and still move the results back to your register file (or wherever\\
you want them to go). In summary, to do an "ADD~R3,~R1,~R2", the hardware will do the\\
following :
\end{verbatim}

\begin{tabular}{ll}
  TTA                            &    OTA                                           \\
\hline
MOV R1, add                      &    ADD R3, R1, R2                                 \\
 ~ \textit{Move R1$ \rightarrow $adder}  &    ~   \textit{Check for hazards}                          \\
MOV R2, add                      &    ~   \textit{Check for available adder}                  \\
 ~ \textit{Move R2$ \rightarrow $adder}  &    ~   \textit{Select internal busses and move data}       \\
 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~   \textit{(adder now does its thing in both cases)}   \\
MOV add, R3                      &    ~   \textit{Check for hazards}                          \\
 ~ \textit{Move adder$ \rightarrow $R3}  &    ~   \textit{Schedule instruction for retire}            \\
                                 &    ~   \textit{Select internal busses and move data}       \\
                                 &    ~   \textit{Retire instruction}                        \\
\end{tabular}

\begin{verbatim}

TTA stands for Transfer-Triggered Architecture. The basic idea is that you don't tell

The compiler, of course, becomes much more complicated, because it has to do all of
the scheduling work, at compile time. But the hardware in a TTA doesn't need to worry
about much of anything... About all it does in the simple cases is fetch instructions
and generate control signals for all of the busses.

Execution is identical between TTA and OTA. Crunch the bits. Period.

Instruction completion is again simplified in a TTA. If you want correct behavior,
make sure your compiler will generate the right sequence of moves. This is compared
to a OTA, where you at least have to figure out what write ports to use, etc.

Basically, a TTA and an OTA are functionally identical. The main differences are that
a TTA pretty much has to be VLIW, and requires more of the compiler. However, if the
"smart compiler and dumb machine" philosophy is really the way to go, TTA should rule.
It exposes more of the pipeline to software, reducing the hardware needed and giving
the compiler more room to optimize. Of course, there are issues, like code bloat and
constant generation, but these can be covered later. The basic ideas have been covered
here (albeit in a somewhat rambling fashion... I had this email all composed in my
head, and had some very clear explanations, right up until I sat down and started
typing). For more information see http://www.cs.uregina.ca/~bayko/design/design.html
and http://cardit.et.tudelft.nl/MOVE. These two have a lot more information on
the details of TTA; I'm still hopeful that we can pull one of these off, and I think
it would be good for performance, generality, cost, and simplicity. Plus, it's
revolutionary enough that it might turn some heads - and that might get us more of a
user (and developer) base, and make the project much more stable.


Send me questions, I know there will be plenty ...



                 Brian



\end{verbatim}

 If you want to understand further the TTA concept, the difference is in the philosophy,
it's as if you had instructions to code a dataflow machine on-the-fly. Notice also the fact
that less registers are needed : registers are required to store the temporary results of
operations between instructions of a code sequence. Here, the results are directly stored
by the units, there are less "temporary storage" needed, less register pressure.

~

  To envision this difference, think about a data dependency graph : in OTA, an instruction
is a node, while in TTA the mov instruction is the branch. Once this is understood, there's
not much work to do on an existing (yet simple) compiler to generate TTA instructions.

~
 
 Let's examine~ :~ $  S = (a+b) * (c-d) $ for example. a, b, c, d are known "ports",
registers or TTA addresses.

\begin{verbatim}
                  a   b c   d
                  1\ /2 3\ /4
                    +     -
                    5\   /6
                      \ /
                       *
                       |7
                       S
\end{verbatim}

 In OTA, with 3-operands instructions, there is in this case one instruction per "node"
(+, -, *). Two temporary registers are needed to store the result of the addition and
the substraction (branches 5 and 6). Let's assume that the tree-flattening must preserve
superscalarism (well, instructions have latencies), so we code :

\begin{verbatim}
               ADD r5, a, b
               SUB r6, c, d
               MUL r7, r5, r6
\end{verbatim}
(for example).

~

            In TTA there is one "port" in each unit for each incoming
branch. This means that ADD, having two operands, has two ports. There is
one result port, which uses the address of one port, but that is used as
read, not write. Another detail is that this read port can be static : it
holds the result until another operation is triggered. We can code

\begin{verbatim}
                mv ADD1,a
                mv SUB1,c
                mv ADD2,b    (this triggers the a+b operation)
                mv SUB2,d    (this triggers the c-d operation)
                mv MUL1,ADD
                mv MUL2,SUB  (this triggers the * operation)
\end{verbatim}

~

  TTA is not "better", it's not "worse", it's just completely different while the problem
will always be the same. If the instructions are 16 bit wide, it takes 96 bits, just as the
OTA example would do. In some cases, it can be better as it was shown long ago on the list.
TTA has some interesting properties, but unfortunately, in the very near future, it's not
probable that a TTA will enter inside a big computer as RISC or CISC do. A TTA core can be
as efficient as the ARM core, for example, it suits well to this scale of die size, but too
few studies have been made, compared to the existing studies on OTA. Because the solution of
its scaling up are not (yet) known, this leads to the discussions that shaked the mailing list
near december 1998 : the problem of where to map the registers, how would the ports be remapped
on the fly, etc. When additional instructions are needed, this jeopardizes the whole balance of
the CPU and evolutivity is more constraining than for RISC or OTA in general.

~

 The physical problem of the busses has also been raised : if we have say 8 buses of 64 bits,
this makes 512 wires, it takes around one millimeter of width with a .5u process. Of course,
we can use a crossbar instead.

~

  As discussed a few times long ago, because of its scalability problems (assignation of the
ports and its flexibility), TTA is not the perfect choice for a very long-lasting CPU family,
while its performance/complexity ratio is good. So, it would be possible that the F-CPU team
makes a RISC $ \rightarrow\ $ TTA translator in front of a TTA core that would not have most
of the scalability problems. This would be called the "FC1" (FC0 is the RISC core). Of course,
time will show how the TTA ghosts of the F-CPU group will change.

~

~

  But TTA's problem is probably that it is too specialized, where OTA can change its core and
still use the same binaries. It's one of the points that "killed" the previous F-CPU attempt.
Each TTA implementation could not be completely compatible with another, because of the
instruction format, of the assignation of the "port" and other similar details : the notion
of "instruction" is bound to the notion of "register".

~

~

  I am not trying to prove the advantage of one technique over another, i am trying to show
the difference of point of view, that finally treats the same problem. The scalability, that
is necessary for such a project, is more important than we thought, and the group finally
showed interest for a more classical technology when AlphaRISC left.


\section{Traditional RISC}


            The third generation rose from the mailing list members who
naturally studied a basic RISC architecture, like the first generation MIPS
processors or the DLX (described by Patterson and Hennessy in their ``QA'' book),
the MMIX (Knuth), the MISC CPUs (such as Chick Moore's Forth engines or Bernd's 4Stack),
and other similar, simple projects.
These designs are explained and described in well-known books and taught in universities.
From a simple RISC project, the design grew in complexity and won independence from other
existing architectures, mainly because of the lessons learnt from their history and
the specific needs of the group, which led to adapted choices and particular
characteristics. This is what we will discuss in the next parts of this
document.
