Best FPGA for floating point performance

mk wrote:
> On 28 Aug 2005 16:49:15 -0700, "JJ" <johnjakson@yahoo.com> wrote:


> >
> the problem with highly threaded cpus is that they are not very good
> at running wordprocessors, spreadsheets and fpga p&r tools and that's
> where most cpus are used so the two cpu developers put most of their

As long as almost all favorite software languages don't support
concurrency or even worse have a broken early 1960s lock based model
(java,C#) then its a darn good job most apps are not multi threaded,
they would all be broken as Java Swing was shown to be. But with
languages like CSP/occam which can be added to C++,Java its much more
practical to do so but there hasn't been any compelling reason to do
this SO FAR. I hear that C++ may finally  be getting some official
concurrency added in coming round. ADA though has been on solid ground
for 20yrs and coincidently shares some of Occams view of cooperating
processes with its rendezvous.

For office processing, it really doesn't take more than a few Mips to
do the raw grunt work, its the GUIs and bloatware that is killing most
SW performance today as well as the cpus memory systems that don't like
anything but extreme locality of reference. Most applications like
Word, OpenOffice are really databases with complex data structures that
can not fit into any cache. They are not so different in principle from
EDA databases, lots of hash tables, trees, lists, graphs, and all of
these have poor locality of reference. Hash tables are the worst, they
have completely random behaviour and are my favourite data structure
(being associative). On paper a 20 (10ns) instruction hash entry
actually takes 1000 cycles every time (if table is > cache).

I think that folks who use SW but don't write it are living under the
false illusion spread by Intel/AMD marketing that all their opcodes run
at 2 or 3GHz and that with the wonders of Superscaler and Out of Order,
they run several opcodes per cycle. In practice they hit the memory
wall all the time. When locality is present, they are amazing though,
and multimedia codecs are esp good at this.

Programs that manage large databases esp such as those for VLSI and
also FPGA P/R have no locality at all. If the database can't fit into
L2 cache, the cpu is broken. I know of no suitable CS data structures
that are extremely cache friendly that can substitute for those above
and described by Knuth. Most CS data structures were imagined (in the
60s or earlier) when memory cycles were similar to processor cycles.

The memory model I propose (at cpa2005) not only has a fairly flat
access time accross its entire DRAM space, its issues about as fast as
your typical L2 SRAM but has some latency and multi threads as its
price.

Would you rather have 1 thread cpu that lives in a cache prison of 1ns
at 16K plus a 4ns 512K backyard plus >100ns nGB wasteland with always
too few TLBs and missing more often than not. A 1% miss means 1ns +
N*100ns/100 avg accesses. More than 1% misses means several ns avg
L1,L2,DRAM accesses. A 3% miss rate probably means 250Mips of loads and
stores plus a few times more for all the free opcodes inbetween that
don't hit memory.

Or would you rather have 4N threads all of which see something like a
2-4 instruction DRAM access even if threads are each much slower. In an
90nm ASIC process the FPGA design I describe could run each thread at
peak 200-250Mips each. If 1 thread isn't enough to run OpenOffice, then
time to find another package.

The real limit to computing is memory throughput, period. Single
threaded cpus make it worse by mostly serializing these through single
memory management unit. Multithreaded cpus with same memory model make
it even worse because the locality is divided further.

But threaded processing with threaded memory can achieve far higher
sustained memory bandwidth and thats really all that matters. After
that its pretty easy to attach Mips to memory issues (but theres more
to it than that).


> money into developing slightly threaded architectures with full
> multi-cores instead of smt. if you noticed the new multi-core i86
> implementations don't support ht anymore. another reason this idea is
> not very easy to implement is that regardless what's happening with
> power on 90nm and lower processes, speed still counts and embedding
> dram on a high speed logic process is a big problem. if and when a new
> memory structure comes out which can be embedded in logic process and
> as inexpensive as 1t+1c dram, i am sure isa architects will look at
> highly threaded cpus again but probably not before then. also keep in
> mind that developing cpus is a very expensive endevour and anyone who
> is not developing an x86 compatible one seems to be giving up

Well I don't actually suggest any DRAM of any sort should be on die
with cpu. What I do suggest is RLDRAM interface to off the shelf parts.
Further I suggest smaller and larger models of the same threaded memory
architecture, the smaller one in interleaved SRAM inside cpu at full
cpu speed (ie a L1 cache again) and larger one for much slower DDR DRAM
for lower cost. In effect a 3 level memory all threaded to give high
level of associativity at different speed size points. No paging, no
TLBs. Page size is only 32bytes though.

> including intel. i expect sun will drop sparc pretty soon and intel
> will drop itanium too; moving their itanium developers to xeon
> projects doesn't bode too well which is for the better as we won't
> have to deal with a completely proprietary, fully moated with patents
> isa.

I don't think Sun will be dropping Sparc at all exept the older models,
Sparc in its Niagara form will serve their needs better than any x86,
and Opterons for their other customers. Niagara and RMI MIPs are very
similar to what I propose but they don't have the same memory model I
suggest.

Itaniums, I guess 50-50, don't really care. The world of comp arch is
not as sterile as an Intel only desktop world would have us believe.

The embedded space and the much smaller HPC (thank heavens) is entirely
more appreciative of engineering. I for one don't believe x86 is as
important as most believe, when you have been around 30yrs in the
business, everything is old and tired and Windows is looking very
tired. 99% of x86s get used solely for surfing and light office work
and almost all of these are idle 98% of the time. If you take a WinCE
toy and add a bit more RISC grunt and video output to it, what you
still have is the familiar Windows but not on x86. Eventually people
will tire of 100W heaters.

The workstation model died because it tried to hitch a free ride on x86
coat tails. If you want to use a PC to do FPGA P/R that is barely good
to surf the web or run bloatware, thats something we did to ourselves.
I do believe that ASIC & FPGA EDA could benefit enormously by
threading, its been done in ASIC EDA for years in some products.

end of rant

johnjakson at usa ...
transputer2 at yahoo ...

Simon Peacock wrote:

> well its an interesting follow on... the more cores.. the better the
> floating point.. I think that's the aim here... but I'm surprised no one has
> mentioned the cell... it has 9 processors on board.

  IBM has just posted more info on this, as they 'open' it up.
Good info on opcodes, but hard to find real speed specs, or
price / package options....

IIRC an earlier release also mentioned some programmable fabric
linking these cores [so they did not need to get it quite so
'right first time'] but not sure if that info will be avaialble
to end users.

  So, perhaps a FPGA _and_ a Cell :) ?

-jg

More likely the programmers have to learn how to think parallel.. then write
a compiler that thinks parallel.. then learn to write games parallel....
stuff hardware guys have done for years.. but not your normal programmers
vision

But the possibilities are good.. and the processor is cheap... :-)  I think
it will catch on.. to a point where PC games will suffer... but it will
start to infect PC's soon enough

Simon

"JJ" <johnjakson@yahoo.com> wrote in message
news:1125315898.748183.133480@o13g2000cwo.googlegroups.com...
>
> Simon Peacock wrote:
> > well its an interesting follow on... the more cores.. the better the
> > floating point.. I think that's the aim here... but I'm surprised no one
has
> > mentioned the cell... it has 9 processors on board.
> >
> > Simon
> >
>
>
> Well I will see the Cell architects at CPA2005. They will describe the
> Cell communications architecture to a group of people most interested
> in parallelism and some might be esp interested in FP performance too.
>
> My own view is the Cell is one way forward but not the way I would
> prefer. Its really one magnificent core surrounded by 8 lesser slaves
> (as much as I know). The gaming world may have a much harder time
> exploiting those slaves than IBM might wish, but then that would be
> true for almost any multi processor, I still remember driving (game)
> cars into and out of walls, their physics isn't all that good.
>
> In the end, I think the memory model comes 1st, the FPU and the rest
> follows on.
>
> John
>

Simon Peacock wrote:
> More likely the programmers have to learn how to think parallel.. then write
> a compiler that thinks parallel.. then learn to write games parallel....
> stuff hardware guys have done for years.. but not your normal programmers
> vision
>
> But the possibilities are good.. and the processor is cheap... :-)  I think
> it will catch on.. to a point where PC games will suffer... but it will
> start to infect PC's soon enough
>
> Simon
>

snipping

Its is very funny that HW guys are so parallel with out even thinking
about it but not in the same way that software guys try it.

Now go into a NG such as comp.arch or any proper SW or par group and
say that and get the cold shoulder, complete waste of time.

The general discussion about parallel in the software world is stuck in
the 1960s model of locks, and semaphores. Message passing is considered
odd in some way, most talk of parallel steers away from it. Message
passing is the natural way to distribute computing even if it means
copying data between processes. In hardware we do this all the time
with wires. Every seasoned ASIC and FPGA EE knows that wires and
communications are half the problem and solution, without them the
modules can't communicate. Somehow the SW folks are trying to avoid
what is percieved to be a redundant copy operation by having processes
share memory directly which is in the end a horrible scheme to
implement after only a few processors. Only small amounts of visiblity
is needed between processes but still they ask for complete memory
sharing across the entire compute space. They often don't understand
that memory operations are hugely expensive and are comparable anyway
with using direct message passing.

Now in the Transputer and occam, we have message passing only, no
shared memory, messages pass through channels or software wires or even
real links and real wires. Processes model hardware. A collection or
hierarchy of occam processes looks exactly like a hardware hierarchy.
This is the only natural model of concurrency that works and is
scaleable across a vast sea of processors. Even the brain appears to
work a bit like this (no shared memory, cache coherence etc).

When you have 100s or more processors running 1000s of persistant
processes, you get a new problem for software types, we call it floor
planning place & route, they call it process mapping and don't know
anything about hardware "process" mapping. Now almost all the best
Transputer programming was done by hardware types who saw the pattern,
and grokked it with no trouble (except for the horrible syntax). Most
Transputer apps became DSP and FPGA apps. I like to say that FPGAs and
Transputers are 2 sides of the same coin, 1 runs processes as hardware
and the other as software, put 1 in the other (or vice versa) and
processes can be run as either as the designer sees fit.

johnjakson at usa ..
transputer2 at yahoo ...

austin wrote:
(snip)

> Thanks for all who posted.

> I still claim that by instantiating more than one core in an FPGA, they 
> still win oven even the best uP, however.

> Massive parallelism is of course nearly impossible to use effectively, 
> as there is no language that preserves if operations could be done in 
> parallel.

> We are stuck with a "paper tape" programming mentality in a 
 > flash memory age.

I like systolic arrays, though as you say there is no good
language to write them in.

-- glen

Marc Battyani wrote:

(snip)

> In fact I'm not sure that full IEEE floating point accuracy is needed. For
> sure single precision is not enough but probably double precision is not
> really needed. The problem is that people who write the algorithms do it in
> C(++) using double precision floats and they use double precision libraries,
> etc. So it's not obvious to see what precision is really needed. After all
> in an FPGA we can use the exact number of bit needed. (In fact it is even
> possible that a fixed point format could work)

If fixed point will do it, even significantly wider than floating
point, it is likely the best way.  Floating point add is a lot more 
expensive than fixed point.  The difference is much smaller for
multiply and divide, not counting any overhead specific to full IEEE 
implementations.

-- glen

glen herrmannsfeldt wrote:

> Marc Battyani wrote:
>
> (snip)
>
>> In fact I'm not sure that full IEEE floating point accuracy is 
>> needed. For
>> sure single precision is not enough but probably double precision is not
>> really needed. The problem is that people who write the algorithms do 
>> it in
>> C(++) using double precision floats and they use double precision 
>> libraries,
>> etc. So it's not obvious to see what precision is really needed. 
>> After all
>> in an FPGA we can use the exact number of bit needed. (In fact it is 
>> even
>> possible that a fixed point format could work)
>
>
> If fixed point will do it, even significantly wider than floating
> point, it is likely the best way.  Floating point add is a lot more 
> expensive than fixed point.  The difference is much smaller for
> multiply and divide, not counting any overhead specific to full IEEE 
> implementations.
>
> -- glen
>
Glen, for this application, I'd argue that the floating point might be 
cheaper if he needs the dynamic range, especially if fixed point pushes 
him to wider than 35x35 multipliers.  a floating point multiplier has 
very little extra compared to fixed point, and you can get away with a 
considerably smaller multiply.  He may find that he can get away with a 
17 bit significand with floating point (in which case a single 
multiplier per node in the array is needed), or at worst 4 multipliers 
for single precision.  On the other hand, if his dynamic range demands 
more than 35 bit multiplication if converted to fixed point, then he's 
got 9 embedded multipliers per multiply, plus adders to combine the 
partials.    Generally speaking, using floating point for multiplication 
and division is cheaper than using fixed point.  The opposite is true of 
addition and subtraction.  In this case however, his addition has to 
essentially be done in fixed point, so he can do the conversion to fixed 
using denorms, do the row add and then renormalize the sum.  In any 
event, I don't see any problems getting this matrix multiply into a 
spartan3 as a floating point implementation.

-- 
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950
email ray@andraka.com  
http://www.andraka.com  

 "They that give up essential liberty to obtain a little 
  temporary safety deserve neither liberty nor safety."
                                          -Benjamin Franklin, 1759