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

Groups > comp.lang.forth > #21451

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:

> On 3/22/2013 4:04 PM, Bernd Paysan wrote:
> I've never heard the term "bypass logic" before.

There is a website called www.google.com, which probably could help you.  
Try putting it into quotes, as you want the combined term, not just sites 
that contain "bypass" and "logic".

> I also don't know what you mean by "dependend" [sic].

"dependent."  I'm German, we pronounce all closing consonants hard ;-).

> I'm sure you mean depended, but I'm
> still not sure what that is intended to represent.

Let's say you have the following instructions, expressed as arithmetic 
assignments:

r3 := r2 + r1
r4 := r3 + r5

Then the second instruction depends on completion of the first one.  If 
you pipeline it in the typical read register | alu | write register 
fashion found in most RISC processors, you have to wait two cycles until 
you can start the second instruction.  That sounds pretty slow.

The solution to this is to use a "bypass logic", which injects the result 
of instruction 1 into instruction 2.

> In general I think your comparison is a bit simplistic.  The register
> file must include multiplexors

These things are called multiplexers.  I'm sure you don't see the 
difference, because English people pronounce "er" more like "or" ;-).

> to select which registers are used at the
> inputs to the ALU.  But the stack machine has to have a mux at the input
> to the TOS as well.  In fact, I found in my design this is where the
> bulk of the LUTs were used, in that mux!  Every item that can be pushed
> to the data stack must have an input to that mux.

Yes, but *that* multiplexer doesn't go away when you change the concept to 
a register architecture.  All those different operations which all write 
their result to one register needs to go through this MUX.

> I think that was some
> 13 items in my design with only two of them having to do with I/O.  Many
> stack designs also include a mux at the input to the NOS to support some
> of the more complex stack ops.
> 
> A register file in an FPGA comes with a very highly optimized mux for
> the RAM itself whether from distributed memory or from block RAMs.  I
> know you are working at the chip level, so your muxes are a bit more
> expensive.  In an FPGA I get some amount of free muxes by using the RAM
> resources.  But regardless, the stack machine uses its share of data and
> return path muxes as well.

Yes, the FPGA has a much faster RAM than real hardware, or let's say it: 
it has much slower logic than real hardware of the same structure size, 
but the RAM is equal.  Therefore, your cycle time doesn't increase much.  
You probably need two dual ported RAM blocks with identical content to get 
two reads and one write in one cycle (write to both at the same location, 
read from both asynchronously at different locations).

FPGA design indeed has other tradeoffs.

-- 
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 (!) Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-03-21 04:42 -0500
  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-21 10:54 +0000
    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-21 16:37 +0100
  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