Hacker News Reader

Comment by dnautics | Hacker News Reader

Obviously the "given a sufficiently sophisticated compiler" joke applies, but it seems like the out-of-order optimization is computationally challenging. Now that we have more sophisticated programming languages (and more sophisticated versions of old programming languages) shouldn't that be done at compile time as a one-time (power, time) cost instead of a recurrent cost across all computing (which will inevitably duplicate effort)? Can someone explain to me why this should be done on metal? (besides that it's always been done like that since the late 90s)

View on HN

Out-of-order execution isn't only about instruction order, and static scheduling can't give you everything. One execution of a given chunk of code might have something in cache, another execution of that same code might not. One execution might consistently take one branch, another might consistently take another, because it varies based on workload.

Out-of-order execution helps with things like "I don't have the memory fetch done yet, but let's make a reasonable assumption and then speculatively do lots more that doesn't depend on that fetch".

While true in principle, in practice the majority (~88%) of the gains of OoO come not from reactions to dynamic events (e.g. caches misses) but rather from schedules.

This is relatively recent research, and definitely against the common grain. See Daniel McFarlin's work at CMU (https://dl.acm.org/citation.cfm?id=2499368.2451143)

thanks! Cache miss latency! I forgot about that.

It means

   load [rp1] -> r1
   inc  r1
   load [rp2] -> r2
   inc  r2

may execute in a different order for every execution.

Hi dnautics!

Dynamic scheduling isn't as complicated as it seems, especially now that we have so many transistors on a chip and Amdahl performance is still very critical for most applications.

However, the value of OoO isn't just about constructing the "best" schedule, it's about being able to change schedules on a dime.

For example, VLIW compilers must try to statically produce the best "trace scheduling" across basic blocks. But OoO, register-renaming, and branch prediction allows you to build "trace schedules" on the fly. And branches tend to be far easier to predict dynamically than they are statically (or rather, branches tend to be more dynamically predictable than statically biased).

Unless you rely on a JIT to rebuild traces, and you can tolerate that overhead every time you fire up the JIT, I think OoO/dynamic scheduling will be with us forever.

The Mill architecture team is working on a static-scheduled architecture, but only time will tell if compilers can reasonably get good enough at it to make it viable. One major problem with static schedules is that if you want more IPC, you generally have to change the ISA or have machine-specific loaders which mutate the code at load time (this is the approach the Mill folks take).

Standard ISAs let you write a program with a linear model, and let the hardware get better at scheduling the micro ops over time, or just let it be linear (as is generally preferred on low end microcontrollers and low-power mobile cores).

> One major problem with static schedules is that if you want more IPC, you generally have to change the ISA or have machine-specific loaders which mutate the code at load time (this is the approach the Mill folks take).

This isn't a problem with static schedules, it's a problem with VLIWs (well actually any exposed pipeline machine).

(And really not that much of a problem anyways)

The Mill is certainly interesting, and while they still haven't provided a satisfactory answer to the ILP question, I think they may be successful enough anyways due to their other innovations.

> if compilers can reasonably get good enough at it

Do compilers, plural, have to get good at it, or just the Mill team's own LLVM backend?

What about the optimizing compilers in v8? SpiderMonkey (and friends)? JVM/Hotspot? Beam? the CLR/Roslyn? I maybe most of what compiles only on GCC (or MSVC) today could be reasonably ported to compile on Clang or DragonEgg, but there are a lot of compilers in the world these days.

What we're talking about is not the difficulty of making one sufficiently intelligent compiler, but probably something more like six of them, along with every other compiler anyone ever wants to write again.

I don't know about you, but I'm not about to assume that we'll somehow manage to develop and maintain six of something we've never even developed one of. The Mill is no Itanium, but it is very unusual. They haven't even tried to make a normal assembler, their assembler is a C++ template metaprogram which generates the assembler which you then run to get your program.

The impression I get is that their odd assembler is pretty much there for development expedience while they are hand-writing assembly. I can't imagine that their specializer (the thing that runs at install or run time which converts the generic load module to specialized concrete machine code for the processor you have) will produce as an IR form assembly that will then go through a C++ compiler... that would just be crazy. And the weird C++ assembler is definitely for the concrete machine code; the generic form is supposed to be very similar to LLVM IR.

Amongst other things it (a C++ assembler) would be slow as hell and require a huge amount of runtime. Ideally the specializer would be a single binary that would convert a generic load module to a specialized one with no intermediate steps. My guess is that they will generate such a specializer with their current generic specification tools.

You'd be right that the specializer doesn't do the same things as the assembler; and programmable assemblers are the norm, but the crucial difference is that their ISA and ABI make the assembler context-dependent.

Well, their exposed ISA and ABI are probably considered to be genAsm, which is the aforementioned mostly-LLVM-based IR. The concrete machine code will mostly likely only ever be generated by the specializer in the real world. Consider the specializer to be the static software equivalent of the x86-to-uOp decoding core in the hardware of a modern x86. On the one hand it can only make static scheduling decisions, whereas on the other hand it can look at the entire program being translated to make those decisions rather than just the window of instructions the x86 decoder can see during execution.

I really think this is the only path to make a long-term-viable staticly-scheduled architecture. Otherwise you'll wind up with the Itanium problem, which is that you eventually need to rewrite/reorder code internally (in hardware) as your architecture evolves, which kind of removes the advantage of having the static scheduling in the first place.

> I really think this is the only path to make a long-term-viable staticly-scheduled architecture.

You may be right. I think the challenges involved (especially as OOBC is proposing to solve them) defeat the goal. For systems that have no present or future interest in JIT, it might offer somewhat higher peak performance than whatever commodity computers are on the market; for those with JIT (especially with frequent compilation, like in a web browser) I can see it being prohibitive. I don't care how magical their specializer is, it will cost something to run, and cost a lot to integrate (imagine not being able to know the size or entry point of the basic block until you've specialized it, infuriating!). The way they talk about the specializer, it even gives the impression that they don't intend to share the source code, which will be a whole lot of fun when deciding whether or not you trust it to run in the middle of your application.

Yeah, who knows. I mostly think the Mill is a pile of interesting ideas that just might, if they're very lucky, eventually become a product. I'm certainly not holding my breath though.

Regarding their intentions, they've said repeatedly that they want to sell chips. It'd therefore be pretty stupid IMHO to not open up as much as they can the toolchain to get software to run on their chips, including the specializer. For that matter they should definitely also be releasing the chip specification data (insn/op bit patterns, functional unit slot arrangement, latencies, etc) that's used to create the specializer so people can roll their own if they want.

Then again this is the same world where Intel ME is an ultra-suspicious closed blob and you can't get datasheets on tons of chips to save your life, which makes no sense to me either. So I'm probably not a very good judge of what's reasonable.

Because you take a huge hit in IPC. Somewhat less if you make your binaries extremely CPU specific. For instance even something simple like the load instruction. To answer that you have to know the state of ALL levels of cache, their size, associativity, contents, TLB, etc. Otherwise it might take 0.3ns or 100ns. To be able to do nothing (because you are in order) is a huge bottleneck.

Doing OOO optimizations in the compiler (Same applies for VLIW etc.) generally requires the ISA to expose its's pipeline to the compiler: This is a complete paradigm shift from current architecture.

Also, special invariants are sometimes needed/helpful to avoid data hazards/simplify data dependencies: e.g. the Mill cpu effectively has no general purpose registers, but an FILO stack of immutable items (This guarantees SSA on the data the cpu is operating on).

> Doing OOO optimizations in the compiler (Same applies for VLIW etc.) generally requires the ISA to expose its's pipeline to the compiler: This is a complete paradigm shift from current architecture.

Not really, exposed pipeline is pretty common in the VLIW world.

VLIW is uncommon outside of DSPs.

The Mill belt is actually (conceptually) a fixed-size FIFO queue; LIFO stacks have been done reasonably often before (see stack machines) but since there's only one stack head they don't support parallel operations particularly well.

There have been CPUs with multiple datastacks e.g. https://bernd-paysan.de/4stack.html is a VLIW ISA with a very dense encoding and "just less ports" to the register file than a classic DSP.

Thanks, that's very interesting. Seems like it'd also be "interesting" to write a compiler for though, especially since you have to manage stack hygiene for four stacks simultaneously. And I'm not sure, but doesn't allowing each functional unit to directly read the top four entries of the other FUs' stacks reintroduce some of the kind of potential hazards that the Mill belt (with its SSA-style usage) tries to avoid?

The Very Long Instruction Word (VLIW) architectures used this philosophy. The most famous of which is Intel's Itanium ISA.

It turns out that it is really hard to create a compiler to effectively take advantage of instruction level parallelism at compile time.

you mean.... it's really hard to create a non-x86 compiler that posts good results on {benchmarks designed to make x86 look good} if you're Intel. And/or no one can really be bothered to make their compile particularly well to a proprietary foreign architecture if the chip already costs an arm and a leg.

it's really hard to create a non-x86 compiler that posts good results on {benchmarks designed to make x86 look good} if you're Intel.

When I used Itanium 2 systems for HPC, Intel's compilers produced the fastest binaries from C and Fortran, at least on the software I used (molecular dynamics and quantum chemistry).

What's meant by "benchmarks designed to make x86 look good"? Itanium was introduced against POWER, Alpha, SPARC, and MIPS chips. It was primarily benchmarked for server/workstation applications, where x86 processors weren't the fastest at the time. In 2003 a "Madison" Itanium 2 was significantly faster on numerical simulation code than a contemporary "Gallatin" x86 Xeon.

It was worse than that. The archives of comp.lang.arch have a lot of detailed discussions on the gory details, including participation by senior designers at Intel among others.

Itanium 2 did finally get reasonable performance, but only by adding back in dynamic scheduling to the microarchitecture.

(This is all in terms of fundamental benchmarks that are not x86 specific).

Let us know when you have written your "sufficiently smart compiler" It is hard, see here [1].

[1] https://en.wikipedia.org/wiki/Itanium

yeah I acknowledged that joke, but if you don't think that, for example, say LLVM is light-years ahead of GCC in implementing plugins that let you do various forms of optimization, you're crazy. It stands to reason that further architectural developments will make things even better than what we have now.

Nowithstanding the fact that your answer is totally unhelpful: I thought about it for a second and I think the answer is basically that if you have a multithreading cores and you're pending on the results of another operation, then you can't necessarily know what optimizations you can do ahead of time because you don't know what other threads are resident on your core, which will affect the on-the-fly reorganization.

Other people have pointed out that Itanium is the most recent example of a project that expected to be able to write a really smart compiler for an in-order CPU and failed.

If you can write better LLVM plugins then I'm sure Intel and HP will be happy to throw lots of money in your direction.

The field is littered with the tombstones of people that have tried to make compilers for insert any foreign architecture. Obviously in-order CPUs are a challenge on top of that. I do think there is a real 'go-to-market' problem. If you think about it this is kind of solved by Nvidia (with CUDA). GPUs are in-order computational arrays with custom compiler.

GPUs are vector processors under another name, that hide the latency of memory differently. They don't need to use the sort of compiler tricks you would with CPU code.

Yeah, but GPUs target only a small subset of the workloads and they are very hard to program even then. I prefer processors like the Rex Neo or Adapteva Epiphany in that respect actually.

have you tried programming rex neo?

Nope, I know you have experience with it though, so perhaps you can help there ;)

I've toyed around with the older Epiphanies though, and they were definitely easier than GPUs in many respects.

Also, as I understand it, GPUs are now out of order as well, aren’t they?

No, they are not.

OoO is much more expensive to implement than simply scheduling a different warp to hide latency.

Absolutely not.

Maybe you're confusing the GPU's threading techniques for OoO?

Reply on news.ycombinator.com