6 ms·
Obviously the "given a sufficiently sophisticated compiler" joke applies, but it seems like the out-of-order optimization is computationally challenging. Now t
by dnautics 9y ago
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)
- rjsw 9y agoLet us know when you have written your "sufficiently smart compiler" It is hard, see here [1]. [1] https://en.wikipedia.org/wiki/Itanium https://en.wikipedia.org/wiki/Itanium
- dnautics 9y agoyeah 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.
- rjsw 9y agoOther 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.
- dnautics 9y agoThe 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.
- wbl 9y agoGPUs 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.
- AlphaSite 9y agoAlso, as I understand it, GPUs are now out of order as well, aren’t they?
- TomV1971 9y agoNo, they are not. OoO is much more expensive to implement than simply scheduling a different warp to hide latency.
- deepnotderp 9y agoAbsolutely not. Maybe you're confusing the GPU's threading techniques for OoO?
- deepnotderp 9y agoYeah, 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.
- dnautics 9y agohave you tried programming rex neo?
- benjaminl 9y agoThe 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.
- dnautics 9y agoyou 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.
- philipkglass 9y agoit'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.
- jasonwatkinspdx 9y agoIt 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).
- mhh__ 9y agoDoing 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).
- phs2501 9y agoThe 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.
- crest 9y agoThere have been CPUs with multiple datastacks e.g. https://bernd-paysan.de/4stack.html 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.
- phs2501 9y agoThanks, 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?
- deepnotderp 9y ago> 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.
- microcolonel 9y agoThe 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).
- mwcampbell 9y ago> 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?
- microcolonel 9y agoWhat 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.
- phs2501 9y agoThe 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.
- sliken 9y agoBecause 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.
- JoshTriplett 9y agoOut-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".
- dnautics 9y agothanks! Cache miss latency! I forgot about that.
- ant6n 9y agoIt means load [rp1] -> r1 inc r1 load [rp2] -> r2 inc r2 may execute in a different order for every execution.
- deepnotderp 9y agoWhile 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 https://dl.acm.org/citation.cfm?id=2499368.2451143)
- _chris_ 9y agoHi 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.
- userpass 9y agoUpgrading the CPU with a faster one will make all programs faster. Compiling a program to a specific CPU that supports issuing 3 moves per cycle and then upgrading to a CPU that supports issuing 5 moves per cycle requires updating the compiler and recompiling all software to take advantage of the improvement.