4 ms·
I always wondered if it is feasible to do a pipelined/super scalar stack based CPU.
by pkaye 6y ago
I always wondered if it is feasible to do a pipelined/super scalar stack based CPU.
- FullyFunctional 6y agoContrary to much common misunderstanding, sure, no real problem. The semantics of each instruction is consume the two top stack elements and replace that with the results. You handle this by having an stack rename stack of physical registers (with additional complication for handling under- and overflows), that is assuming the current stack is pr3 pr4 pr5 and the first free register is pr56 Then an "+" instruction is interpreted as "add pr56, pr4, pr5" and pr56 is consumed and pr4 and pr5 marked to be freed when this commits. Because stack machines inherently introduce a lot of tight dependencies you will need to use dynamic scheduling (OoOE) to go super-scalar, but it's not a problem. Upsides are incredible instruction density. Downside: slightly harder to do good code generation, but not really.
- klelatti 6y agoThank you for an interesting answer. This begs the question of course: why have they never caught on?
- deleted 6y ago[deleted]
- FullyFunctional 6y agoI'm assuming partly inertia, partly the code density not being important enough to do this. To be clear, while you _can_ go OoO superscalar with a stack machine, it's more work than with an ISA that exposes the dependencies, like VLIW or EDGE. Don't take my word for it, design, model, simulate, and implement it yourself. It's a small matter of coding. EDIT: Reduceron is an example of a super-scalar stack machine, though not dynamically scheduled. It's very difficult to write code by hand though.
- klelatti 6y agoThanks - the Reduceron looks really interesting.
- crest 6y agoIt's possible to pipeline a stack CPU but the there is an upper limit on the number of pipeline stage that make sense. A forth friendly (data and return) dual stacked CPU can be very simple and small yet achieve a throughput close to one instruction per cycle. Going superscalar on a single datastack is hard. You basically have to rename every stack access and most compute instructions consume two arguments producing a single result. You just trapped yourself in a fate about as bad as having to implement a superscalar x87 FPU. One interesting design to break the 1 instruction per clock barrier is a multistack VLIW design. In this design the dense encoding of a stack based instruction compensates for the low usage code density common in VLIW instruction sets. See https://bernd-paysan.de/4stack.html https://bernd-paysan.de/4stack.html an example of this out of the box approach.