News for hackers. Stuff that matters.
Re:Graviton 3: First Impressions by Hizonner on Sunday May 29, 2022 @10:26AM (#31549379)
It feels like we've gone badly wrong somewhere when processors have to spend so many of their resources guessing about the program. I am not saying I have a solution, just that feeling.
Re:Graviton 3: First Impressions by canarypilot on Sunday May 29, 2022 @11:52AM (#31550095)
Why would you consider prediction based on dynamic conditions to be the sign of a dystopian optimization cycle? Isn’t it mostly intuitive that interesting program executions are not going to be things you can determine statically (otherwise your compiler would have cleaned them up for you with inlining etc.), or could be determined statically but at too great cost to meet execution deadlines (JiTs and so on), or resource constraints (you don’t really want N code clones specialising each branch backtrace to create strictly predictable chains).

Or is the worry on the other side; that processors have gotten so out-of-order that only huge dedication to guesswork can keep the beast sated? I don’t see this as a million miles from software techniques in JiT compilers to optimistically optimize and later de-deoptimize when an assumption proves wrong.

I think you might be right to be nervous if you wrote programs that took fairly regular data and did fairly regular things to it. But, as Itanium learned the hard way, programs have much more dynamic, emergent and interesting behaviour than that!

Re:Graviton 3: First Impressions by amelius on Sunday May 29, 2022 @01:59PM (#31551202)
I guess the fear is that the CPU might start guessing wrong, causing your program to miss deadlines. Also, the heuristics are practically useless for realtime computing, where timings must be guaranteed.
Re:Graviton 3: First Impressions by nine_k on Sunday May 29, 2022 @06:34PM (#31553549)
I suppose that if you assume in-order execution and count the clock cycles, you should get a guaranteed lower bound of performance. It may be, say, 30-40% of the performance you really observe, but having some headroom should feel good.
Re:Graviton 3: First Impressions by bastawhiz on Sunday May 29, 2022 @04:38PM (#31552681)
Isn't that the whole promise of general purpose computing? That you don't need to find specialized hardware for most workloads? Nobody wants to be out shopping for CPUs that have features that align particularly well with their use case, then switching to different CPUs when they need to release an update or some customer comes along with data that runs less efficiently with the algorithms as written.

Since processors are expensive and hard to change, they do tricks to allow themselves to be used more efficiently in common cases. That seems like a reasonable behavior to me.

Re:Graviton 3: First Impressions by cesaref on Sunday May 29, 2022 @11:19AM (#31549809)
I thought this was the reasoning behind Itanium, the idea that scheduling could be worked out in advance by the compiler (probably profile guided from tests or something like that) which would reduce the latency and silicon cost of implementations.

However, it wasn't exactly a raging success, with I think the predicted amazing compiler tech not materialising, but maybe it is the right answer, but the implementation was wrong? I'm no CPU expert...

Re:Graviton 3: First Impressions by Veedrac on Sunday May 29, 2022 @11:50AM (#31550081)
Itanium was a really badly designed architecture, which a lot of people skip over when they try to draw analogies to it. It was a worst of three worlds, in that it was big and hot like an out-of-order, it had the serial dependency issues of an in-order, and it had all the complexity of fancy static scheduling without that fancy scheduling actually working.

There have been a small number of attempts since Itanium, like NVIDIA's Denver, which make for much better baselines. I don't think those are anywhere close to optimal designs, or really that they tried hard enough to solve in-order issues at all, but they at least seem sane.

Re:Graviton 3: First Impressions by speed_spread on Sunday May 29, 2022 @06:36PM (#31553564)
Would Itanium have been better served with bytecode and a modern JIT? Also, doesn't RISC-V kinda get back on that VLIW track with macro-ops fusion, using a very basic instruction set and letting the compiler figure out the best way to order stuff to help target CPU make sense of it?
Re:Graviton 3: First Impressions by Veedrac on Sunday May 29, 2022 @08:30PM (#31554303)
Those are all very different things. It is probably possible to argue that using a JIT would have solved some of Itanium's compilation issues, like it would make it easier to make compilation decisions about where to do software data miss handling, but I don't think it would have made the hardware fundamentally more sensible, or all that performant. RISC-V isn't really anything like VLIW, it is about as close to a traditional RISC as anything gets nowadays, and macro-op fusion is just a simple front end trick that doesn't overly influence whether the back end is in-order or out-of-order (or whatever else).
Re:Graviton 3: First Impressions by nine_k on Sunday May 29, 2022 @06:36PM (#31553570)
I heard that the desire to make x86 emulation performant on Itanium made things really bad, compared to a "clean" VLIW architecture.
Re:Graviton 3: First Impressions by Hizonner on Sunday May 29, 2022 @11:46AM (#31550045)
I'm not sure what happened with Itanium.

I do think a big part of the problem is that people want to distribute binaries that will run on a lot of CPUs that are physically really different inside. But nowadays there's JIT compilation even for JavaScript, so you could distribute something like LLVM, or even (ecch) JavaScript itself, and have the "compiler scheduling" happen at installation time or even at program start.

Re:Graviton 3: First Impressions by imtringued on Sunday May 29, 2022 @06:29PM (#31553511)
You can't distribute LLVM for that purpose without defining a stable format like WebAssembly or SPIR-V.
Re:Graviton 3: First Impressions by inkyoto on Sunday May 29, 2022 @09:37PM (#31554680)
Yes, you can if you use Bitcode which has been a stable format since around 2015. It is possible to distribute an application as a pure Bitcode binary that can be statically translated into the underlying hardware ISA unless the source code uses inline assembly – see https://lowlevelbits.org/bitcode-demystified/ for details.
Re:Graviton 3: First Impressions by booblik on Monday May 30, 2022 @12:52PM (#31560912)
What about linking?
Re:Graviton 3: First Impressions by lmm on Sunday May 29, 2022 @09:55PM (#31554780)
Itanium was designed decades ago when compilers were a lot worse, and had other issues. Maybe it's time for another attempt in that direction.
Re:Graviton 3: First Impressions by tyingq on Sunday May 29, 2022 @10:45AM (#31549530)
There's the Mill CPU, which sounds terrific on paper. Hard to gauge when it might turn into something commercially usable though.
Re:Graviton 3: First Impressions by 0xCMP on Sunday May 29, 2022 @11:24AM (#31549850)
Mill would definitely make things more interesting. They were supposed to have their simulator online a while ago, but sounds like they needed to redo the work on the compiler (from what I understood). Once that comes out it sounds like the next step is getting the simulator online for people to play with.
Re:Graviton 3: First Impressions by mhh__ on Sunday May 29, 2022 @02:26PM (#31551473)
People have tried over and over again to "fix" this and it hasn't worked.

The interesting probabilities are all decided at runtime.

Now we have AI workloads there is a place for a big lump of dumb compute again, but not in general purpose code.

Re:Graviton 3: First Impressions by Cthulhu_ on Sunday May 29, 2022 @11:41AM (#31550003)
It always did feel like a weird hack to me to avoid parts of the CPU to be idle. I mean the performance benefits are there, but it's at the cost of power usage in the end.

Can branch prediction be turned off on a compiler or application level? If you're optimizing for energy use that is. Disclaimer: I don't actually know if disabling branch prediction is more energy efficient.

Re:Graviton 3: First Impressions by Veedrac on Sunday May 29, 2022 @11:57AM (#31550149)
Disabling branch prediction would have such a catastrophic effect on performance, there is no way it would pay for itself. Actually this is true for most parts of a CPU; Apple's little cores are extremely power efficient and yet they are fairly impressive out-of-order designs. It would take a very meaningful redesign of how a CPU works to beat a processor like that, at least at useful speeds.
Re:Graviton 3: First Impressions by thrwyoilarticle on Sunday May 29, 2022 @07:21PM (#31553841)
At the cost of power doesn't necessarily mean at the cost of energy. If it takes a minimum of 1 gazillion electrons to do something useful then it's better to move those electrons quickly and return to idle than it is to eke them out slowly over a longer time despite the latter having a lower power usage.
Re:Graviton 3: First Impressions by ip26 on Sunday May 29, 2022 @09:46PM (#31554728)
Clocks and leakage burn most of the power. So the most power efficient thing to do is to get as much work done per clock as possible, and if a small fraction turns out to be wasted, you still come out ahead.
Re:Graviton 3: First Impressions by imtringued on Sunday May 29, 2022 @06:33PM (#31553541)
Turning off branch prediction sounds like a weird hack that serves no purpose, just underclock and undervolt your CPU if you care about power consumption that much.
Re:Graviton 3: First Impressions by rwmj on Sunday May 29, 2022 @10:53AM (#31549588)
Uli Drepper has this tool which you can use to annotate source code with explanations of which optimisations are applied. In this case it would rely on GCC recognizing branches which are hard to predict (eg. a branch in an inner loop which is data-dependent), and I'm not sure GCC is able to do that.

https://github.com/drepper/optmark

Re:Graviton 3: First Impressions by adrian_b on Sunday May 29, 2022 @01:59PM (#31551198)
A majority of the non-deterministic and speculative hardware mechanisms that exist in a modern CPU are required due to the consequences of one single hardware design decision: to use a data cache memory.

The data cache memory is one of the solutions to avoid the extremely long latency of loading data from a DRAM memory.

The alternative to a data cache memory is to have a hierarchy of memories with different speeds, which are addressed explicitly.

The latter variant is sometimes chosen for embedded computers where determinism is more important than programmer convenience. However, for general-purpose computers this variant could be acceptable only if the hierarchy of memories would be managed automatically by a high-level language compiler.

It appears that writing a compiler that could handle the allocation of data into a heterogeneous set of memories and the transfers between them is a more difficult task than designing a CPU that becomes an order of magnitude more complex due to having a hierarchy a data cache memories and a long list of other hardware mechanisms that must be added due to the existence of the data cache memory.

Once it is decided that the CPU must have a data cache memory, a lot of other hardware design decisions follow from it.

Because there is an inverse relationship between the load latency and the data cache memory size, the cache memory must be split into a multi-level hierarchy of cache memories.

To reduce the number of cache misses, data cache prefetchers must be added, to speculatively fill the cache lines in advance of load requests.

Now, when a data cache exists, most loads have a small latency, but from time to time there still is a cache miss, when the latency is huge, long enough to execute hundreds of instructions.

There are 2 solutions to the problem of finding instructions to be executed during cache misses, instead of stalling the CPU: simultaneous multi-threading and out-of-order execution.

For explicitly addressed heterogeneous memories, neither of these 2 hardware mechanisms is needed, because independent instructions can be scheduled statically to overlap the memory transfers. With a data cache, this is not possible, because it cannot be predicted statically when cache misses will occur (mainly due to the activity of other execution threads, but even an if-then-else can prevent the static prediction of the cache state, unless additional load instructions are inserted by the compiler, to ensure that the cache state does not depend on the selected branch of the conditional statement; this does not work for external library functions or other execution threads).

With a data cache memory, one or both of SMT and OoOE must be implemented. If out-of-order execution is implemented, then the number of registers needed to avoid false dependencies between instructions becomes larger than it is convenient to encode in the instructions. so register renaming must also be implemented.

And so on.

In conclusion, to avoid the huge amount of resources needed by a CPU for guessing about the programs, the solution would be a high-level language compiler able to transparently allocate the data into a hierarchy of heterogeneous memories and schedule transfers between them when needed, like the compilers do now for register allocation, loading and storing.

Unfortunately nobody has succeeded to demonstrate a good compiler of this kind.

Moreover, the existing compilers have frequently difficulties in discovering the optimal allocation and transfer schedule for registers, which is a simpler problem.

Doing efficiently the same for a hierarchy of heterogeneous memories seems out-of-reach for the current compilers.

Re:Graviton 3: First Impressions by neonsunset on Sunday May 29, 2022 @08:16PM (#31554217)
While not addressing explicitly, modern languages do already perform cache-size aware optimizations. Namely, .NET runtime will base its heap sizes and allocation behavior based on CPU's cache size so that data is allocated closer together and further reads, and subsequent garbage collection are friendly to CPU's memory prefetching behavior. On the other hand, register allocation is a much more complex problem to solve because there is no single heuristic that fits all CPUs (and even operating systems!) sharing the same micro-architecture. As a result, "good enough" sometimes is chosen unless the language relies on LLVM/GCC logic.

Alloc/GC: https://github.com/dotnet/runtime/blob/main/docs/design/core...

Reg alloc: https://github.com/dotnet/runtime/blob/main/docs/design/core...

Re:Graviton 3: First Impressions by solarexplorer on Sunday May 29, 2022 @06:00PM (#31553298)
We do have these architectures already in the embedded space and as DSPs. I suppose, they would be interesting for supercomputers as well. But for general purpose CPUs they would be a difficult sell. Since the memory size and latency would be part of the ISA, binaries could not run unchanged on different memory configurations, you would need another software layer to take care of that. Context switching and memory mapping would also need some rethinking. Of course, all of this can be solved, but it would make adoption more difficult.

And last not least, unknown memory latency is not the only source of problems, branch (mis)predictions are another. And they have the same remedies as cache misses: multithreading and speculative execution.

So if you wanted to get rid of branch prediction as well, you could come up with something like the CRAY-1.

Re:Graviton 3: First Impressions by adrian_b on Sunday May 29, 2022 @06:21PM (#31553446)
You are right that a kind of multi-threading can be useful to mitigate the effects of branch mispredictions.

However, for this, fine-grained multi-threading is enough. Simultaneous multi-threading does not bring any advantage, because the thread with the mispredicted branch cannot progress.

Out-of-order execution cannot be used during branch mispredictions, so like I have said, both SMT and OoOE are techniques useful only when a data cache memory exists.

Any CPU with pipelined instruction execution needs a branch predictor and it needs to execute speculatively the instructions on the predicted path, in order to avoid the pipeline stalls caused by control dependencies between instructions. An instruction cache memory is also always needed for a CPU with pipelined instruction execution, to ensure that the instruction fetch rate is high enough.

Unlike simultaneous multi-threading, fine-grained multi-threading is useful in a CPU without a data cache memory, not only because it can hide the latencies of branch mispredictions, but also because it can hide the latencies of any long operations, like it is done in all GPUs.

Fine-grained multi-threading is significantly simpler to implement than simultaneous multi-threading.

Re:Graviton 3: First Impressions by mr_toad on Sunday May 29, 2022 @10:02PM (#31554816)
Seems likely that programmers would game the system and try and hog all the fast memory for their programs.
Re:Graviton 3: First Impressions by staticassertion on Sunday May 29, 2022 @02:55PM (#31551753)
IDK, that seems like how brains work, and brains are pretty cool. They guess all the time in order to save time.
Re:Graviton 3: First Impressions by lmm on Sunday May 29, 2022 @09:57PM (#31554792)
Citation needed. The way I see it brains have a lot of baked in behaviour that isn't tuned at runtime, e.g. the length of time that different types of things are kept in different types of memory is remarkably consistent.
Re:Graviton 3: First Impressions by staticassertion on Sunday May 29, 2022 @11:57PM (#31555333)
It's definitely an extremely well supported fact that brains make predictions about the future in order to optimize various things.
Re:Graviton 3: First Impressions by lmm on Monday May 30, 2022 @12:32AM (#31555507)
If your argument is "anything that attempts to make predictions is a good idea because it's like a brain", that seems enormously fallacious.
Re:Graviton 3: First Impressions by staticassertion on Monday May 30, 2022 @09:25AM (#31558708)
My argument is that brains are cool, brains do this thing, ergo this thing might be cool.
Re:Graviton 3: First Impressions by lmm on Monday May 30, 2022 @06:54PM (#31564495)
If "this thing" is just "making predictions", that's still so broad as to be more or less meaningless.
Re:Graviton 3: First Impressions by yjftsjthsd-h on Sunday May 29, 2022 @10:03PM (#31554822)
In fairness, that's a source of bugs in our brains, too.
Re:Graviton 3: First Impressions by ppg677 on Sunday May 29, 2022 @11:17PM (#31555160)
Your own brain is basically a predictor. That's largely how thinking works.
Re:Graviton 3: First Impressions by ncmncm on Monday May 30, 2022 @03:21AM (#31556314)
Thinking works mostly by hashing. Prediction is an optimization on top of that.