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

Groups > comp.lang.forth > #21525

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

AKE wrote:

> On Monday, April 8, 2013 5:11:55 PM UTC+1, Anton Ertl wrote:
>> 
>> General-purpose register machines have won (for the bigger CPUs), not
>> because they are a better fit for the languages, but because they
>> execute these languages fast when supported by a compiler with decent
>> register allocation.
>> 
> 
> It would seem this support's Knuth's choice of general-purpose register
> machine for his MMIX 'ideal machine'.  I've wondered why Knuth's
> algorithmic work did not assume a simpler, stack machine.  Perhaps this is
> why?

IMHO, the register machines won, because you can implement Tomasulo's 
instruction scheduling algorithm with registers, but it doesn't make that 
much sense to do it with stack machines (you can, it is just more 
complicated - and more complicated means that you'll lose the race).

Example: The T800 transputer, a simple stack machine with the workspace 
pointer as helper for C-like languages, was pretty impressive back when it 
was introduced.  But trying to improve the instruction level parallelism 
resulted in a monster, the T9000.  In essence, the T9000 was the "ultra-
CISC" processor, combining many simple T800 operations into long and 
powerful instructions, which were hard to decode...

There were other approaches at improving ILP, like SIMD and VLIW, but 
compiler support for them never got out of some particular niches.  It's 
also interesting that AMD dropped SIMD+VLIW on their most recent GPU 
architecture, even though GPUs had algorithms that were easy to compile for 
SIMD+VLIW.  But apparently, it's even better to just split the workload on 
many, many simple cores.  Still a register architecture, though.

-- 
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 (!) rickman <gnuarm@gmail.com> - 2013-04-05 16:45 -0400
  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-04-06 03:00 -0500
  Re: Algorithm design:  computational cost of ordinary stack operations (dup, rot, over, swap, etc.) vs. cost of fetch (@) and store (!) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-04-08 16:11 +0000
    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-04-08 15:43 -0500
      Re: Algorithm design:  computational cost of ordinary stack operations (dup, rot, over, swap, etc.) vs. cost of fetch (@) and store (!) "Rod Pemberton" <do_not_have@notemailnotq.cpm> - 2013-04-08 23:49 -0400
        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-04-09 04:02 -0500
      Re: Algorithm design:  computational cost of ordinary stack operations (dup, rot, over, swap, etc.) vs. cost of fetch (@) and store (!) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-04-09 07:03 +0000
        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-04-09 04:04 -0500
    Re: Algorithm design:  computational cost of ordinary stack operations (dup, rot, over, swap, etc.) vs. cost of fetch (@) and store (!) AKE <assadebrahim2000@gmail.com> - 2013-04-08 14:34 -0700
      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-09 00:02 +0200
      Re: Algorithm design:  computational cost of ordinary stack operations (dup, rot, over, swap, etc.) vs. cost of fetch (@) and store (!) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-04-09 07:06 +0000

csiph-web