Ideal CPU for FPGA?

In an unrelated thread on FPGA<->CPU clock speeds, an FPGA developer 
stated that FPGAs are ill suited to replicating legacy CPU designs.

I never got around to asking why, but a more relevant question is:

What type of CPU architecture are FPGAs more suited to implement?

On Sun, 19 Jun 2005 01:23:50 +0100, dave <dave@dave.dave> wrote:
>In an unrelated thread on FPGA<->CPU clock speeds, an FPGA developer 
>stated that FPGAs are ill suited to replicating legacy CPU designs.
>
>I never got around to asking why, but a more relevant question is:
>
>What type of CPU architecture are FPGAs more suited to implement?

Actually both questions are relevant, and are best answered together.

When designing a CPU a key ingredient is for the architect to be
totally familiar with the strengths and weaknesses of the underlying
implementation medium. This knowledge then affects the decisions and
tradeoffs that follow. ("Medium" here is the design abstraction
that the CPU designer will be using to implement the CPU. If you work
for Intel in the x86 organization, it is CMOS. If you are using an
FPGA for your canvas, then although they are CMOS chips, your
abstraction is gates/LUTs/flip flops with CE/carry chains  etc.)

Here is my first example: If the goal is a 100 ns instruction cycle
time, and the implementation medium supports wide PROMS at 5 ns, then
a microcoded implementation may be appropriate. If the PROM takes
60 ns, then hardwired decode is the more likely choice.

All things are not equal. The area, speed, power, drive strength,
input load, and other factors do not have the same ratios across all
implementation mediums.

Second example: CMOS, NMOS, PMOS, Bipolar, GaAs, SiGe all have different
"weights" for the above list of characteristics for muxes, flip flops,
memory cells, decoder trees, bus drivers, registers, etc.

What if you have ultra fast logic, but crappy slow I/O, or maybe
your required cycle time is 2 orders of magnitude slower than the
cycle time the hardware can support. Then maybe a serial architecture
is called for.

So when you look at a legacy CPUs, you are looking at a design that
has been crafted to take advantage of the medium it was designed to
be implemented in. Other things affect CPU architecture. It is well
established that to be continually successful in the CPU business, you
need to leverage as best as possible the existing software base, and
development tools. So follow-on products tend to be backward
compatible, and the development tools often seamlessly will take the
source for a program (maybe in C, Fortran, PL/M, ...) and compile to
the newer product. Or maybe not so seamlessly. If it is a major change
the products do not fair well, because once you force the customer to
abandon the existing environment, then they may as well look at
competitors in their product selection process. The Intel 860 and 960
are good examples of a company that lost its way for a while. What this
means is that legacy CPUs often have an amazing amount of baggage that
is there for backward compatibility. Some of it makes no sense for
current applications, but must be there in case some legacy program
comes along. The latest Pentium will still boot DOS 6.1, in 8088 mode,
with silly 1 MB address space, and those inane segment registers.
All this must be replicated for an FPGA equivalent to be called
equivalent.

What all this means is that because legacy CPUs were designed with
some type of silicon implementation medium, the tradeoffs of how the
instruction set is implemented are strongly influenced by this. The
other major influence is the experience of the CPU architect and the
CPUs they have worked on in the past. Oh, and also marketing gets into
the act, and says you have to have decimal adjust instructions, and a
half-carry bit, and handle 1's complement as well as 2's complement
arithmetic. Oh, and the software people say they absolutely need to
have a semaphore instruction and hardware task switching support.
And more ....

Now take the legacy CPU and try to map it onto an FPGA. The medium
is different, and all the careful balancing that was done for the
legacy CPU are totally out of whack for the FPGA implementation. It
is not that it can't be done, it is that it can't be done efficiently.
And you are not allowed to drop the bits that are difficult. If you
do, then you are no longer compatible, and the hoped for leverage of
existing tools or existing code goes out the window.

As to what maps well to FPGAs, the answer is an architecture that is
designed with an FPGA as the target. This tends to be as follows:
Basically RISC style register sets rather than accumulator(s), with
multiple reads and writes per cycle. Pipelined operation (4 or 5
stages). Direct coding of the control bits for the data path in the
instruction encoding (minimal decode trees). Parallel execution of
mutually exclusive functions with the un-needed results thrown away
(Add, barrel shift, priority encode/CLZ, branch calc, TLB search, etc
all occur every cycle, based on the same operands fetched, but only
the needed result is used).

The first CPU in an FPGA (RISC4005/R16) and XSOC/XR16 and NIOS, and
MicroBlaze all look like this. They all easily outperform legacy
CPUs implemented in the same FPGAs, because they are tuned to the
resources that the FPGAs have to offer.


Philip Freidin




Philip Freidin
Fliptronics

Pretty good summary.

>In an unrelated thread on FPGA<->CPU clock speeds, an FPGA developer
>stated that FPGAs are ill suited to replicating legacy CPU designs.

>I never got around to asking why, but a more relevant question is:

>What type of CPU architecture are FPGAs more suited to implement?

I think several of us have said this on occasion or more often, but
there are times when it is justified. I believe one avionics system
does ship with a Z8000 compatible FPGA design at original speed, the
function had to be identical and cycle accurate which only meant
<20MHz. Today <20MHz for general purpose clone of anything isn't
interesting except to history buffs. There is an almost complete
Transputer clone from U Tokyo but still only at original speed about
25MHz and not public. I am sure both of these use vast amounts of FPGA
logic far beyond MB/Nios though. Look also at 68k/x86 cores from some
vendors, they are available but enormous and slow (faster than original
though). Compare Leon/Sparc with MB and OpenCores arch and Leon uses
far more resources and ran at lower actual clock, but in a nice twist
actually was the only complete design and ended on par with MB, MB had
some FPU issues. The open cores design got smoked because it was
designed with ASIC in mind and was very incomplete.


Developing a RISC ground up almost suggests building it bottom up
rather than top down.

Bottom up allows you to find a unit design that works at the desired
speed for each function part, amd then elaborate that into something
that is useful without losing performance along the way. Trouble is, it
is a bit difficult to build cpus this way unless you have a clear
vision all the way back to the top. Eventually all these widgets must
interoperate and some control decisions between them suddenly become
serial, not parallel and the design is broken after much work. I say
that from experience of a design where many parts easily ran separately
close to limits, but could only be integrated with 1 path becoming
brutally awkward, overall perf went down by 3, so I killed that design
approach.

Top down is the way most cpus would naturally be designed when you are
familiar with your materials but as soon as a design is dumped into the
EDA tools one can get nasty surprises very quickly.

What always kills cpu performance is decision making.

For an ASIC, 10 real gate delays can make some pretty complex
structures that can do any of the following. A fast 2 port SRAM, a
64bit adder (Alpha design), a lot of arithmetic mixed control decision
logic. Combine all 3 in parallel and you have a classic RISC in short
order limited to 10gate delay clock cycles which today is 1-4GHz. The
higher end though is all driven by complex transister level circuit
design, not regular std cell.

In an FPGA the BlockRams are as effective if pipelined as in an low end
ASIC. The adder designs are way less effective, we are stuck with
ripple designs because of the general placement of cells. Using complex
designed logic adders doesn't work so well since the free built in
ripple adders are not handicapped by general wiring. In a BlockRam
cycle time you only get 2-3 LUTs depth of logic which is way below
10gates of ASIC decision control.


FPGAs have proved themselves to be pretty good at DSP engines largely
because they don't get up and make decisions on clock cycle boundaries,
they are very good at continuosly streaming data over the same
operators, ie a datapath. Many DSPs that do make some decisions can do
so within a more relaxed timing scheme, say an FFT engine must switch
some controls every 2^Nth clock in predicable block patterns. These
patterns are almost always regular and can be made to go fast enough
too.

CPUs on the other hand demand decisions be made on each and every clock
cycle about any no of things. The more the FPGA cpu looks like a
conventional cpu, the more some of those decisions must be made in a
combined fashion always on each clock. Suppose you branch y/n at
address 0xffff over to 0x10010. That might look like a short +ve branch
but it also may involve the MMU in page faults and or the cache
updateing a new line as well as actually making the bcc decision which
means you don't know where the next op is coming from for sure.


There is only one way that I know to deliver a cpu that runs even
remotely as fast as a DSP and that means no clock to clock decisions,
only decisions made over as many clocks as possible such as 4 or 8.
This leads naturally to threaded designs or barrel engines or in DSP
speak commutators. The datapath-instruction-fetch=decode is made
somewhat longer, not just 5 pipelines but more like 15 with 4 threads
in flight each with a decision to make every 4th clock.

Such an MT design is more complex in several aspects but much simpler
in others. This sort of design looks like a DSP filter with some logic
working effectively at sub clocks. The new complexity lies in the
barrel control keeping 4 or 8 sets of state in flight but in a mostly
regular thread independant manner. The simplicity lies in having 4-8
clocks to actually make a decision for every thread cycle. We will see
more of this sort of design in ASICs too because there the problem is
DRAM cycle latencies, the 4 or 8 way designs can effectively make
memories 4-8 times faster to each thread.

Now when the same MT approach is applied to the DRAM such as Micron
RLDRAM which is also effectively 8way threaded, you get an obvious
match in heaven, 8 instructions can almost be executed with 8 DRAM
cycles but they actually complete every 8 or more clocks ie 20-25ns
window. That allows for some radical simplifications too, no data
cache. Having to use SDRAM fo same task would allow 70ns latency to be
hidden well, but it has very little bank concurrency so the threads
would hardly ever be allowed to do ld/st.


johnjakson at usa dot com
transputer2 at yahoo

Philip Freidin wrote:
> On Sun, 19 Jun 2005 01:23:50 +0100, dave <dave@dave.dave> wrote:
> 
> Actually both questions are relevant...
> ....
> ....
> The first CPU in an FPGA (RISC4005/R16) and XSOC/XR16 and NIOS, and
> MicroBlaze all look like this. They all easily outperform legacy
> CPUs implemented in the same FPGAs, because they are tuned to the
> resources that the FPGAs have to offer.
> 
> Philip Freidin
> 
> Philip Freidin
> Fliptronics

Thanks.

JJ wrote:
> Pretty good summary....
>....
> There is only one way that I know to deliver a cpu that runs even
> remotely as fast as a DSP and that means no clock to clock decisions,
> only decisions made over as many clocks as possible such as 4 or 8.
> This leads naturally to threaded designs or barrel engines or in DSP
> speak commutators. The datapath-instruction-fetch=decode is made
> somewhat longer, not just 5 pipelines but more like 15 with 4 threads
> in flight each with a decision to make every 4th clock.
> 
> Such an MT design is more complex in several aspects but much simpler
> in others. This sort of design looks like a DSP filter with some logic
> working effectively at sub clocks. The new complexity lies in the
> barrel control keeping 4 or 8 sets of state in flight but in a mostly
> regular thread independant manner. The simplicity lies in having 4-8
> clocks to actually make a decision for every thread cycle. We will see
> more of this sort of design in ASICs too because there the problem is
> DRAM cycle latencies, the 4 or 8 way designs can effectively make
> memories 4-8 times faster to each thread.
> 
> Now when the same MT approach is applied to the DRAM such as Micron
> RLDRAM which is also effectively 8way threaded, you get an obvious
> match in heaven, 8 instructions can almost be executed with 8 DRAM
> cycles but they actually complete every 8 or more clocks ie 20-25ns
> window. That allows for some radical simplifications too, no data
> cache. Having to use SDRAM fo same task would allow 70ns latency to be
> hidden well, but it has very little bank concurrency so the threads
> would hardly ever be allowed to do ld/st.
> 
> 
> johnjakson at usa dot com
> transputer2 at yahoo
> 

Thanks JJ.

Are there any open implementations that demonstrate the multi threaded 
approach you've mentioned?

P.S.

How is that Transputer going?

dave wrote:
> Philip Freidin wrote:
> 
>> On Sun, 19 Jun 2005 01:23:50 +0100, dave <dave@dave.dave> wrote:
>>
>> Actually both questions are relevant...
>> ....
>> ....
>> The first CPU in an FPGA (RISC4005/R16) and XSOC/XR16 and NIOS, and
>> MicroBlaze all look like this. They all easily outperform legacy
>> CPUs implemented in the same FPGAs, because they are tuned to the
>> resources that the FPGAs have to offer.
>>
>> Philip Freidin
>>
>> Philip Freidin
>> Fliptronics
> 
> 
> Thanks.

BTW: I didn't mean to imply the first paragraphs were not relevant!!!

Read up on Suns Niagara and also Raza, he was the architect of the
Athlon and later as a VC helped get Niagara of the ground then did the
same again for the Raza MT Mips arch. These and my MT share quite a few
ideas but I go off in a differnet direction esp with the inverted  MMU
and Transputer stuff.

I don't know of any open source MT designs, perhaps mine will be or
won't. I am sure that if the opensource fans really want to do it, they
could figure it out, but they should target to FPGA and not ASIC, ASIC
perf comes for free after that, not like many open cores ever go to
ASIC. I suspect though that since most comp arch students use the H & P
textbooks that is entirely single threaded, thats all we will see from
students.

At the moment I am spending most of my time on the C compiler just
trying to get the function stuff wrapped up and join up with code
packing. ASAP I go back to getting the ISA simulator to validate what
the compiler will give it then update the RTL code and then the Verilog
and then the memory interface for RLDRAM or atleast a 8 way threaded
BlockRam/SRAM model of it (with artificial 20ns latency). Even my
starter S3 board will be able to model the idea of threaded cpu &
memory even with its meager SRAM.

Since V4 and Webpack 7 have been out, I only today tried to redo the
P/R of the V2P on that, so far results not too good, 320MHz is now
barely 200MHz, more timewasting there. Even V4 doesn't give me anything
yet in perf, will have to redo the flow again but the SW comes 1st.

by for now

JJ

dave wrote:

> What type of CPU architecture are FPGAs more suited to implement?

Primitive CPU architectures are easier to implement on an FPGA chip. ;-)
FPGAs generally have problems with multiport memories -- it's easy to
implement a 1-write N-read port memory bank, but if the number of write
ports is higher, you will have a big problem. And since such blocks are
commonly used by DSPs (and remaining architectures that exploit
massive parallelism, but not VLIW-like, i.e. with complex inter-stage
datapath dependencies), its hard do implement them using on FPGA.

    Best regards
    Piotr Wyderski

Hi Philip,

> So when you look at a legacy CPUs, you are looking at a design that
> has been crafted to take advantage of the medium it was designed to
> be implemented in.

Hum.  Some, perhaps...but "crafted" and 8088/8086 in the same paragraph,
much less sentence one doesn't see much.  There is such a thing as simply a
bad and/or poorly implemented architecture.

> ...8088 mode,
> with silly 1 MB address space, and those inane segment registers.

May be not so "crafted" after all, eh?  Parlez-vous 68k? ;-)

Regards,

Austin

Well I would say for their time the 8086, Z8000, 68k were all
reasonably well crafted as VLSIs go, but all in different ways, I know
this for a fact since I got to reverse engineer them transister by
transister at least for the more repeated or interesting blocks and all
very different styles of circuit and logic design too. At the time
Intel had a budget of around 17K devices, Motorola on the other hand
budgeted around 60k or so though alot of that was microcode rom. That
also meant the 68k was bound to cost several times what the 8086 did
which didn't matter much to workstation vendors at the time.

As for architecture Intel was only upgrading the 8080 to a 16bit arch,
it was not intended to be the entire future of the world computing as
it presently is, blame IBM for that, but then no one sees much further
than 2-3 years do they. Intel was aiming the 432 for that purpose. The
68K had the luxury of not being backwards compatible with anything and
had a fair bit of clean design.

Remarkably all these design teams had very little CAD available to them
for most of the general designs except for spice for absolutely
critical cells, and layout digitizing. Today a novice designing an FPGA
cpu could do billions of times more logic & arch simulations. Thats why
those designs had 200 man years in them.

johnjakson at usa dot com