News for hackers. Stuff that matters.
Re:Ask HN: Why did stack-based CPUs lose out? by CHY872 on Saturday December 31, 2022 @02:13PM (#34199662)
Building a solid computer stack (hardware through software) is an exercise in mechanical sympathy, understanding the traits of the underlying components which enable the practitioner to get as much out of it as possible. The software should do the thing that the software is good at, and the hardware should do the things that the hardware is good at, and neither exists in a vacuum, both should be aware of the constraints of the other.

For one example, about 25 years ago Intel made a processor called Itanium which used 'VLIW' (very long instruction word) instructions as opposed to x86. In this case, a lot of the complexity of operating a processor is shifted into the compiler, since individual CPU instructions may perform complex operations. In a modern processor, instructions are 'simple', and the processor is responsible for finding the data dependencies that allow multiple instructions to be executed in parallel (this is called 'superscalar' processing). With Itanium, the compiler author can encode such individual operations into more complex instructions which can be executed in parallel, all at once. So, where in x86 I might have in 3 different instructions (add r1, r2, sub r3, r4, mul r5, r6), with Itanium I might be able to combine all of those into a single instruction at compile time. By doing this, in theory we can remove a lot of the complex superscalar logic from the processor, devote more of the chip to execution units and achieve more overall performance.

One problem here is that the compiler may not actually know what parallelism is possible. For example, the latency of a given instruction may vary from chip to chip. The number of execution units for a single operation may vary. Our code is now very highly optimised for a particular CPU, we may not see natural speedups as newer processors are made, newer processors might not even support the code we've written without a translation layer. Taken to extremes, we lose the universality of software (the ability to change the hardware without rebuilding the software). VLIW chips are viable, but they're typically used in more isolated use cases (like DSPs) where it's reasonable to recompile the software for every chip (and where perhaps there is lots of parallelism in the problem space).

State machines essentially have similar issues. High performance processors tease out the data dependencies between instructions in order to perform superscalar processing, which is key to good performance in a modern processor. Stack machines make it very difficult to understand data dependencies because in principle all data depends on all other data, a post-processing step is required (which is considerably more expensive than the processor equivalent of converting to SSA form). Modern register machines rely heavily on register renaming to ensure that both superscalar processing and pipelining work well with each other - maintaining similar performance with a stack machine would lead to similar solutions, and so very likely switching from a register machine to a stack machine would likely look like having a translation layer on the chip, from the stack machine back into a register-like language.

Stacks do exist in a few places these days. The JVM clearly does it - Java is 'register oriented' for the programmer, the JVM instruction set is stack oriented, and the runtime converts it back into a register oriented machine code. Another example is the ARM Jazelle extensions which allow some ARM processors to directly execute Java bytecode. Here, the bytecode is converted into the machine code as an extra stage in the processor pipeline, adding overhead.

BLAB: - There isn't much advantage to stack machines. It's relatively straightforward to translate between the two. - Modern processors are architecturally closer to register machines, and a lot of the techniques used to make them fast would have to be replicated on a stack machine. - Because any decisions at this level of the stack are effectively invisible to the user in modern tech, it's beneficial to go for the simplest solutions to any given problem, which here is to use a register machine at the hardware level.

Re:Ask HN: Why did stack-based CPUs lose out? by bcrl on Saturday December 31, 2022 @09:58PM (#34203130)
It would have been interesting to see a superscalar ia64.

The biggest problem with ia64 is that virtually every generation shipped late. Very late. We had working first generation CPUs years before anything shipped publically. The first ia64 had a huge amount of die space wasted by a worthless Pentium III core (if my memory is correct), which would have been far better used on cache.

For some workloads ia64 was fast. Networking benchmarks on my development machine were impressive because of having gobs of memory bandwidth and fast interrupts. The asynchronous register window engine really helped some things. Sadly, once em64t took off, it was a dead architecture. x86 is the only platform that gets the real resources at Intel.

Re:Ask HN: Why did stack-based CPUs lose out? by gpderetta on Sunday January 01, 2023 @03:30AM (#34204681)
Ia64 was already superscalar. That's the whole point of the Explicitly Parallel part of EPIC.

Maybe you meant out of order?

Re:Ask HN: Why did stack-based CPUs lose out? by CHY872 on Sunday January 01, 2023 @06:11AM (#34205413)
I might be wrong but it seems a little suspect to call Ia64 superscalar because of that. When I hear superscalar, I generally expect to see a processor dynamically checking data dependencies at runtime, and perhaps executing multiple instructions depending on those data dependencies. With out of order execution added on top, I'd additionally expect to see a structure like a reorder buffer to allow results to be written to RAM in the same order as the logical execution.

I think that encoding the parallelism into the instructions would generally not be considered as superscalar, it's an entirely different technique. Most texts I've read would explicitly separate out VLIW and EPIC from superscalar processors. There are plenty of ways of getting parallelism - for example one could probably view SIMD or even some CISC instructions as a form of this - as far as I know, VLIW and superscalar processors are just considered different from this perspective.

Re:Ask HN: Why did stack-based CPUs lose out? by sharpneli on Sunday January 01, 2023 @07:37AM (#34205826)
https://en.m.wikipedia.org/wiki/Superscalar_processor

It very much is superscalar. OoO Superscalar is what you described.

Re:Ask HN: Why did stack-based CPUs lose out? by CHY872 on Sunday January 01, 2023 @07:46AM (#34205878)
I’m not sure it is. For comparison, Arm A8 is superscalar (can issue two non-conflicting instructions per cycle) whereas the A9 is out of order superscalar. I think the linked Wikipedia article supports me, no? My understanding is that a structure like a reorder buffer is what makes the processor OoO.

> The superscalar technique is traditionally associated with several identifying characteristics (within a given CPU): > Instructions are issued from a sequential instruction stream > The CPU dynamically checks for data dependencies between instructions at run time (versus software checking at compile time) > The CPU can execute multiple instructions per clock cycle

Re:Ask HN: Why did stack-based CPUs lose out? by sharpneli on Sunday January 01, 2023 @08:19AM (#34206060)
That part is bit weird because checking data dependencies is precisely what the OoO does. If that was strict part of what superscalar is then OoO moniker would be redundant. If one doesn't execute things out of order then checking for dependencies is useless.

However above that is the simple definition, which is that as long as it executes more than a single instruction per clock it's superscalar. Even SIMD is taken as an example of a superscalar CPU.

As for the original claim the ia64 is very much a superscalar CPU. All VLIW designs are superscalar. VLIW can be also thought as OoO superscalar CPU with the reorder buffer and dependency analyzer ripped off and exposing the execution units explicitly in their gory details. Or alternatively we can also say that VLIW already won, we just added a big honking chip on top to JIT compile machine code into VLIW micro-ops.

Re:Ask HN: Why did stack-based CPUs lose out? by gpderetta on Sunday January 01, 2023 @10:32AM (#34207079)
As everything, it is complicated.

Even in order non-superscalar cpus need some kind of dynamic checking if they allow out of order completion by allowing succesive low latency instructions to execute under the shadow of a preceding high latency instruction [1]. I'm not an cpu architect but this tracking is much simpler than the register renaming of OoO and only relies on hardware interlocks.

I think the grandparent is right in distinguishing VLIW, especially exposed pipeline ones, from superscalar as they have no tracking at all and just naively issue bundles; I think it is an useful distinction.

EPIC is more complicated as while it allows expressing intrabundle parallelism, it also allow dependencies and so it does need hardware interlocks. You could argue either way.

I think SIMD by itself should not be considered superscalar as it is still executing a single instruction is a single execution unit (compare the term superscalar itself to vector computation). Of course a superscalar CPU could have the capability to issue distinct SIMD instructions in parallel (for example larrabee).

CPU microarchitecture details are fun!

[1] there are many examples, starting with the CDC 6600; quake was also famous for implementing texture perspective correction by scheduling a division every 16 pixels and using fast approximation for the remaining pixels.

Re:Ask HN: Why did stack-based CPUs lose out? by simne on Monday January 02, 2023 @09:03AM (#34217898)
> ia64 is very much a superscalar CPU

Yes, but ia64 was not pure VLIW design, it was EPIC - VLIW with additions. So compiler could suggest optimal path of execution, but if suggestion was not created, it using OoO (in reality things sophisticated, but on first look, something like this).

Other wide known VLIWs are nearly all ultraspecialized pure designs, without any OoO, because EPIC is very expensive in means of transistor number and cost of large die.

Example, AMD TeraScale GPU architecture, Radeon HD 2000 series, Radeon HD 3000 series, Radeon HD 4000 series, Radeon HD 5000 Series, Radeon HD 6900 series. https://en.wikipedia.org/wiki/TeraScale_(microarchitecture).

Re:Ask HN: Why did stack-based CPUs lose out? by bcrl on Monday January 02, 2023 @06:12PM (#34225048)
I forgot to type the OoO -- that was indeed what I meant. That's what I get for being tired and overworked doing storm repairs for the past 2 and a half weeks.
Re:Ask HN: Why did stack-based CPUs lose out? by simne on Monday January 02, 2023 @08:45AM (#34217744)
> When I hear superscalar, I generally expect to see a processor dynamically checking data dependencies at runtime

No. They use brute force, they have as many state machines as their superscalarness, and these SMs working simultaneous, saving results in OoO buffer, and periodically synchronize via special algorithm.

Each SM have full set of shadow registers and state of CPU.

To be precise, exists examples of non-orthogonal or "partially" OoO machines - Pentium MMX and IBM POWER. In them, CPU core divided to few parts, MMX parts dividing registers file, POWER have separate pipeline for memory operations, and these parts could do only in their limited space, but other mechanics is same as ideal orthogonal OoO design.

For example, when happen branch and unknown which side will run and have spare resources, SS running each sides (in separate OoO pipeline), and when will know finally effective side, results of other side just discarding, and results of effective side merging with other calculated data.

If happen branch, but resources limited, works predictor, which learn on previous runs and usually could predict with >80% accuracy, which side will run, so most probable side chosen.

When just happen spare resources on run, got last updated PC+1 and run other SM in parallel from there, than on some place (mostly on buffers fill), all data from OoO exec merging with main flow.

All this mean, carefully crafted program could see difference of OoO vs non-OoO execution (not exactly in memory, but by measure jitter, as merge OoO pipeline takes some time), but if not care, mostly have excellent compatibility and if fortunate, OoO will run as many times faster as number of OoO pipelines, which could be significantly large, ie in Pentium-3/4 was 4 or more pipelines.

And as side effects, this all gives high pressure on cache subsystem, and sometimes optimized in unsafe way (but cheap), so happen vulnerabilities, like Meltdown and Spectre.

Re:Ask HN: Why did stack-based CPUs lose out? by anotherhue on Sunday January 01, 2023 @03:05AM (#34204572)
The (disconcertingly silent) Mill CPU company have a design talk that covers these concepts wonderfully in the general form, while explaining their various innovations.

e.g. this video describes how their VLIW compiler does partial compilation/'specialisation' to allow the same input to be consumed on machines with different variations of hardware features.

https://youtu.be/D7GDTZ45TRw?t=259

Re:Ask HN: Why did stack-based CPUs lose out? by silisili on Sunday January 01, 2023 @04:32AM (#34204959)
The sun will have burnt out before the Mill CPU actually ships, sadly. But at least that takes care of some radiation concerns...
Re:Ask HN: Why did stack-based CPUs lose out? by ilyt on Sunday January 01, 2023 @11:37AM (#34207773)
I'd expected them to at least produce FPGA prototype or something
Re:Ask HN: Why did stack-based CPUs lose out? by jawilson on Sunday January 01, 2023 @07:08PM (#34212644)
Full software scheduling breaks down on the first data cache miss. Combined with typically much larger icache foot-prints, VLIW just never lives up to the promise.

I agree they could be useful for DSPs because the icache problem isn't as severe as general purpose software like a compiler or word-processor.