|
Message
From: Marko Mlinar<markom@o...>
Date: Tue Sep 7 14:00:04 CEST 2004
Subject: [oc] Winning with a reconfigurable computer
On Tuesday 07 September 2004 13:16, Bill Cox wrote:
> Hi, Marko.
>
> Hey, a real expert in the field! I was hoping there would be one or two
> of you out there to keep the discussion honest.
Thanks, but don't expect too much, since I am also in search for most of the
answers ;)
What solution are you trying to make? Is the solution commercial? Is it under
viASIC?
Are you interested in a commercial cooperation?
> > I have spend quite some time on this subject and I am sure it will be one
> > of the hottest research areas in the following decade.
>
> Almost makes me wish I were a grad student, rather than a EDA tool
> developer.
Well, that is not so bad either ;)
> I'll check it out. Do you have a link to it? I missed it when I
> checked the links from the OpenCores site.
It is a part of or1ksim, called CUC (custom unit compiler). I believe it is
currently broke and unmaintained, but there was some versions which worked on
the simulator. The CUC was abandoned due to large circuit sizes and I began
to built second tool, which is more commercial.
> > Although it may seem at the first glance that C->RTL conversion is
> > straightforward and all it requires is a lot of work, but this is not
> > true. I have not been able to prove that solving this problem in finite
> > time would require a machine computationally better than Turing, but that
> > seems very likely, since the problem becomes very similar to code
> > optimization.
>
> Yes, it's obviously an NP hard (or worse) problem to solve optimally. I
> shouldn't have said it's not hard. In particular, doing it well is very
> hard. However, it's doable, as you've proved.
Well, I have proven that conversion is possible -- which is undoubtly true.
But speed is another issue. CUC suffered severely from memory bandwidth,
despite the memory burst it was trying to make by concatenation of memory
accesses.
> I agree that a sub-set of Java or C# would be a better starting point.
> Both languages are less ambiguous, and both deemphasize pointers.
Not fully true -- C# has pointers, but their usage is limited to smaller
areas, which means the arrays used there can be put into smaller RAMs.
> At work, we work in a subset of C, and we already use integers as
> handles to objects. Data already is stored in arrays of properties. We
> don't allow programmers to use pointers, except in very specific cases
> (like returning multiple values).
Moreover you could allow pointers as indexes. All this allows you to
distribute the memories into smaller pieces which is very valuable.
> Even simpler than compiling Java or C# would be to pick a subset that's
> expressive enough to allow good algorithms to be written. We've already
> done this at work. No '.', '->', or '*' operators are allowed.
> Everything is either a variable or an object, and objects are accessed
> through their handles. It should be relatively easy to analyze our
> code, and our data structures are well defined in a text based schema
> file, which is used to generate all our object support code. We do
> allow new property arrays to be allocated to extend the fields of a
> class. We also automate generation of recursive destructors,
> eliminating most of the dangling pointer problems. So, we have little
> use for garbage collection, and our object support code can get dumped
> into the C->Verilog translator just like algorithmic code.
If I understand you correctly you first transform C code to schema and
optimize it further.
> > One of the biggest finding I had is that every loop that can be optimized
> > (containing memory accesses) can be duplicated, where from the first loop
> > you can calculate memory addresses and in the second you collect data. In
> > the worst case your second loop is empty and you have no optimizations,
> > but in most cases you can generate the addresses needed to cope with long
> > RAM access latencies.
>
> This is a cool idea. I'd like to examine how it translates into
> hardware more carefully.
I think this is the right way to go.
> I'm not surprised. I have found that taking advantage of parallel
> processing generally requires changes to the algorithms at a high level.
Yes it is quite obvious, but very constraining.
> I'm not thinking of generating hardware that's many times faster than a
> traditional CPU. I'm just thinking that more than 2x is doable,
> primarily through good memory management across multiple data ports.
I believe that 2x is doable, but more would probably require manual algorithm
change. If you can afford that SW developer would write code optimized for
your architecture, then you are definitely a winner.
> I also think the same tricks could be used to speed up a more
> traditional CPU. The main thing is to hammer down the memory bottleneck
> through several independent memory buses.
Yes, if you look at IA64 architecture, it has a lot of instructions dedicated
for address prediction and for supplying address sooner than needed.
> Thanks for the well informed thoughts on the topic.
I am very interested in this discussion, since apparenly you also have some
experience in the area.
best regards,
Marko
|
 |
Browse
