Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #21519

Re: Algorithm design: computational cost of ordinary stack operations (dup, rot, over, swap, etc.) vs. cost of fetch (@) and store (!)

Show all headers | View raw

rickman wrote:
> Smartass replies aren't useful.  I tried googling it and after four
> pages of hits didn't find anything explanatory.

Must be your filter bubble.  The first hit I get is a PDF with slides, which 
explains it pretty well, including nice drawings:

http://people.ee.duke.edu/~sorin/prior-courses/ece152-spring2009/lectures/5.3-pipelining.pdf

>> The solution to this is to use a "bypass logic", which injects the result
>> of instruction 1 into instruction 2.
> 
> So why wouldn't a stack machine need this?

Because it does not need to access a register file to get TOS and NOS.  
These DFFs don't need any indirection, they are directly sourcing the ALU 
inputs, and the output of the instruction MUX (selecting between ALU and 
fetch) goes directly into TOS.

> Or maybe you don't understand English well enough to know that both
> spellings are used.  You might try using google to see that...  Google
> is your friend!

Yes. Google found "Results for 'multiplexers'.  Search instead for 
'multiplexors'".  That's a strong hint that I was misspelling the word, and 
that this happens rather often.  If I insist, I get results for any 
misspelling I want ;-).  Maybe filter bubble again...  The ratio 
multiplexers:multiplexors is just 2:1, so it's pretty common, and the fact 
that I'm getting redirected means someone at Google is really mad about this 
misspelling ;-).

>> FPGA design indeed has other tradeoffs.
> 
> I'm not sure what "real" hardware is really.  I also can't make a lot of
> sense from this.  The cycle time doesn't increase much... when?

When you have async block RAM.  As you discovered, new FPGAs have sync block 
RAM, which means you get that cycle adder you see in "real hardware", too.

The FPGA is a hardware emulator for hardware design.  By emulating gates and 
wires with SRAM-based logic cells, you increase the gate delay of logic 
cells easily by a factor of 5-10.  You don't increase the delay of RAMs, 
because they are just RAMs, without emulation.

> BTW, most block rams have two ports.  You can do one operation on each
> port on each clock cycle.  2 reads, 2 writes, 1 read/1 write.  In other
> words, the limiting feature is the address bus.  There are two of them.

Yes, I know.  In "real hardware" you don't do this, because it's about twice 
as large as a single-ported memory.  So unless you can't avoid the dual-
ported RAM, you use a single-ported RAM.  I've once spent a few weeks to 
convert some FPGA design with dual ported RAMs to single ported RAMs, and 
that reduced the area of the total chip by 1/4th or so.  From "won't fit" to 
"pad/core-limited" which is the point when you don't need to bother much 
about further squeezing the design.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: Algorithm design:  computational cost of ordinary stack operations (dup, rot, over, swap, etc.) vs. cost of fetch (@) and store (!) Brad Eckert <hwfwguy@gmail.com> - 2013-03-22 08:34 -0700
  Re: Algorithm design:  computational cost of ordinary stack operations (dup, rot, over, swap, etc.) vs. cost of fetch (@) and store (!) Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-03-22 10:44 -0500
  Re: Algorithm design:  computational cost of ordinary stack operations (dup, rot, over, swap, etc.) vs. cost of fetch (@) and store (!) Bernd Paysan <bernd.paysan@gmx.de> - 2013-03-22 21:00 +0100
  Re: Algorithm design:  computational cost of ordinary stack operations (dup, rot, over, swap, etc.) vs. cost of fetch (@) and store (!) Bernd Paysan <bernd.paysan@gmx.de> - 2013-03-22 21:04 +0100
    Re: Algorithm design:  computational cost of ordinary stack operations (dup, rot, over, swap, etc.) vs. cost of fetch (@) and store (!) rickman <gnuarm@gmail.com> - 2013-04-05 16:34 -0400
      Re: Algorithm design:  computational cost of ordinary stack operations (dup, rot, over, swap, etc.) vs. cost of fetch (@) and store (!) Bernd Paysan <bernd.paysan@gmx.de> - 2013-04-06 04:05 +0200
        Re: Algorithm design:  computational cost of ordinary stack operations (dup, rot, over, swap, etc.) vs. cost of fetch (@) and store (!) rickman <gnuarm@gmail.com> - 2013-04-06 17:11 -0400
          Re: Algorithm design:  computational cost of ordinary stack operations (dup, rot, over, swap, etc.) vs. cost of fetch (@) and store (!) Bernd Paysan <bernd.paysan@gmx.de> - 2013-04-08 19:47 +0200
  Re: Algorithm design:  computational cost of ordinary stack operations (dup, rot, over, swap, etc.) vs. cost of fetch (@) and store (!) stephenXXX@mpeforth.com (Stephen Pelc) - 2013-03-22 18:10 +0000

csiph-web