I read-ish the whole set of slides and it sounds pretty good (the devil is always in the details), but I got a little worried about VLIW-ish issues when [in the slides] he said on slide #57:
The compiler controls when ops issue
One of the big issues with VLIW was that the compiler had to be intimately aware of processor architecture. So when you upgraded your '886 to a '986 you needed new binaries because the '986 had more registers or executions units. [I assume Itanium fixed some of this, but it also sunk my interest in VLIW.]
Is this architecture going to face the same issue?
Edit: I watching the video and heard that "nearly all of what the super scalar is doing is [not calculating]". One of the other VLIW issues was that chip area was dominated by cache-area, so all the stuff about [not calculating] shrank and shrank relatively as cache area grew (see: http://techreport.com/review/15818/intel-core-i7-processors). This claim concerns me.
The Mill compiler is a conventional three-phase tool. The first version used the EDG front end and home-grown middle and back ends, but we are converting to a clang front end, LLVM middle, and home-grown back end. All optimization is done in the middle end; the back end (the "specializer" runs at program install (or load) time and does only scheduling and emit.
All Mill family members have a common architecture, that the middle end knows about. ME output (specializer input) is a complete CFG and DFG for the abstract Mill. The specializer first replaces operations that are not present on the target with calls to functions; on a Mill function call is semantically equivalent to an op like an add.
There is no instruction-selection phase. The Mill in general has only one way to implement any given source-level action, and the correct (abstract) code has already been selected by the ME. The BE does instruction scheduling, introducing spill where necessary, using standard schedule algorithms long used for in-order machines and VLIWs. The result may be listed as assembler source or emitted as binary. The schedule algorithms have quadratic worst case but in practice are linear. The generated binaries are cached in the load module, so subsequent runs skip the specializer step.
Current status is that work on the new (LLVM-based) compiler is on hold while we complete the patent filings, and the old one is out of date already. When the filings are in we hope to make the tool chain and sim available on-line for those who want to play. We could do that now with the assembler and sim, except that the asm instruction set exposes some things that the patents aren't in on yet. Grrr - patents!
As someone who worked on operating systems back at Multiflow (late 80's, the first VLIW start-up as a spin-off from Yale research), it struck me recently that something like an LLVM representation of binary code might solve the "compiler problem" (needing to know the exact specifics of the chip's latencies). I.e., you'd run and load LLVM binaries, and have a runtime final optimization pass that took into account the specific latencies of each opcode for a particular implementation. (The LLVM architecture is actually already set up to do optimizations at runtime on LLVM "binaries".)
But perhaps that "final optimization pass" would be nearly as hard as the whole compilation problem in the first place; dunno. I wasn't on the compiler team, so this is perhaps a naive viewpoint.
The LLVM architecture is actually already set up to do optimizations at runtime on LLVM "binaries".
Pragmatically, exactly how fast is that run-time optimization? Could you realistically JIT it, or should the more-optimal, chip-specific asm be cached between loads? Or is this so slow you'd only ever want to do it once?
Right, forgot to say that: you'd cache the results (like Rosetta translation on the PowerPC or the DEC VAX-to-Alpha binary recompilation) so you'd only take the translation hit once.
Transmeta was doing dynamic binary translation from x86 to VLIW. I think the grandparent comment is saying that you could distribute programs in an IR and then compile them before running.
In terms of square millimeters the caches dominate chip area. In terms of fab yield (which is the cost driver) they do not, because caches are regular structures that are built with built-in sparing.
If there's a bad gate in the cache then the fab process simply uses one of the spare cells inside; the user never realizes that a spare has been used. If there's a bad gate in the core proper then that chip is gone, lowering the fab yield.
The same can be done at the level of other regular structures. Your two-core chip is really a four-core chip with a couple of bad cores. That's one of the reasons why the vendors are so eager to convince you that multicore is the Pearly Gates - it increases their effective yield.
Re cache area:
To a first approximation, power cost of a cache is constant independent of size, whereas core power is superlinear. Consequently the limiting factor for increasing cache size is latency, not power. See ootbcomp.com/docs/encoding for how the Mill doubles instruction cache size without increasing latency.
I feel like the issue this faces isn't so much the belt length, since I think you'd probably just end up with a dominant choice (much like x86 managed to stick to a roughly unchanging number of registers for a very long time).
But the lack of latency hiding means you have to generate code to schedule starting operations at the right time. Mul taking 2 cycles means you want to start any dependent, but lower latency instructions after it. But if at some point in the future mul is scaled down to one cycle for whatever reason your timings will all be off and your belt occupancy will be less than ideal.
I kind of wonder if the reality is simply that there is nothing better equipped to schedule instructions than the cpu itself. Maybe we could have better ways to explicitly hint meaningful information to it, but I'm not sure shoving all the decisions to the compiler is a long term solution.
The obstacle would simply be recompiling from IR. That doesn't seem like a big challenge in today's environment for a large swath of devices -- nearly mobile devices, for instance, have nearly-complete top-to-bottom source code for all software running on the chip available. So that approach doesn't seem nearly as crazy as it would have 10-20 years ago.
This assumes that the applications are provided fully compiled to object code. In situations where the applications are provided as bytecode (e.g. Android Dalvik) or are interpreted (e.g. Python) the applications of which you speak will run just fine.
...which (probably) explains why Google seems to be so interested in this new architecture. Besides Dalvik this new CPU architecture could also be used with the new Portable Native Client (PNaCl) which uses LLVM to compile to an intermediary bitcode. From this perspective, the Belt architecture makes a lot of sense.
Comments
First off, I love the post! Super meaty goodness.
I read-ish the whole set of slides and it sounds pretty good (the devil is always in the details), but I got a little worried about VLIW-ish issues when [in the slides] he said on slide #57:
One of the big issues with VLIW was that the compiler had to be intimately aware of processor architecture. So when you upgraded your '886 to a '986 you needed new binaries because the '986 had more registers or executions units. [I assume Itanium fixed some of this, but it also sunk my interest in VLIW.]Is this architecture going to face the same issue?
Edit: I watching the video and heard that "nearly all of what the super scalar is doing is [not calculating]". One of the other VLIW issues was that chip area was dominated by cache-area, so all the stuff about [not calculating] shrank and shrank relatively as cache area grew (see: http://techreport.com/review/15818/intel-core-i7-processors). This claim concerns me.
Edit V2: but damn... Exciting stuff.
The Mill compiler is a conventional three-phase tool. The first version used the EDG front end and home-grown middle and back ends, but we are converting to a clang front end, LLVM middle, and home-grown back end. All optimization is done in the middle end; the back end (the "specializer" runs at program install (or load) time and does only scheduling and emit.
All Mill family members have a common architecture, that the middle end knows about. ME output (specializer input) is a complete CFG and DFG for the abstract Mill. The specializer first replaces operations that are not present on the target with calls to functions; on a Mill function call is semantically equivalent to an op like an add.
There is no instruction-selection phase. The Mill in general has only one way to implement any given source-level action, and the correct (abstract) code has already been selected by the ME. The BE does instruction scheduling, introducing spill where necessary, using standard schedule algorithms long used for in-order machines and VLIWs. The result may be listed as assembler source or emitted as binary. The schedule algorithms have quadratic worst case but in practice are linear. The generated binaries are cached in the load module, so subsequent runs skip the specializer step.
Current status is that work on the new (LLVM-based) compiler is on hold while we complete the patent filings, and the old one is out of date already. When the filings are in we hope to make the tool chain and sim available on-line for those who want to play. We could do that now with the assembler and sim, except that the asm instruction set exposes some things that the patents aren't in on yet. Grrr - patents!
As someone who worked on operating systems back at Multiflow (late 80's, the first VLIW start-up as a spin-off from Yale research), it struck me recently that something like an LLVM representation of binary code might solve the "compiler problem" (needing to know the exact specifics of the chip's latencies). I.e., you'd run and load LLVM binaries, and have a runtime final optimization pass that took into account the specific latencies of each opcode for a particular implementation. (The LLVM architecture is actually already set up to do optimizations at runtime on LLVM "binaries".)
But perhaps that "final optimization pass" would be nearly as hard as the whole compilation problem in the first place; dunno. I wasn't on the compiler team, so this is perhaps a naive viewpoint.
Pragmatically, exactly how fast is that run-time optimization? Could you realistically JIT it, or should the more-optimal, chip-specific asm be cached between loads? Or is this so slow you'd only ever want to do it once?
Right, forgot to say that: you'd cache the results (like Rosetta translation on the PowerPC or the DEC VAX-to-Alpha binary recompilation) so you'd only take the translation hit once.
Transmeta was a little like that, except it was x86 to VLIW.
Transmeta was doing dynamic binary translation from x86 to VLIW. I think the grandparent comment is saying that you could distribute programs in an IR and then compile them before running.
In terms of square millimeters the caches dominate chip area. In terms of fab yield (which is the cost driver) they do not, because caches are regular structures that are built with built-in sparing.
If there's a bad gate in the cache then the fab process simply uses one of the spare cells inside; the user never realizes that a spare has been used. If there's a bad gate in the core proper then that chip is gone, lowering the fab yield.
The same can be done at the level of other regular structures. Your two-core chip is really a four-core chip with a couple of bad cores. That's one of the reasons why the vendors are so eager to convince you that multicore is the Pearly Gates - it increases their effective yield. Re cache area:
To a first approximation, power cost of a cache is constant independent of size, whereas core power is superlinear. Consequently the limiting factor for increasing cache size is latency, not power. See ootbcomp.com/docs/encoding for how the Mill doubles instruction cache size without increasing latency.
I feel like the issue this faces isn't so much the belt length, since I think you'd probably just end up with a dominant choice (much like x86 managed to stick to a roughly unchanging number of registers for a very long time).
But the lack of latency hiding means you have to generate code to schedule starting operations at the right time. Mul taking 2 cycles means you want to start any dependent, but lower latency instructions after it. But if at some point in the future mul is scaled down to one cycle for whatever reason your timings will all be off and your belt occupancy will be less than ideal.
I kind of wonder if the reality is simply that there is nothing better equipped to schedule instructions than the cpu itself. Maybe we could have better ways to explicitly hint meaningful information to it, but I'm not sure shoving all the decisions to the compiler is a long term solution.
The obstacle would simply be recompiling from IR. That doesn't seem like a big challenge in today's environment for a large swath of devices -- nearly mobile devices, for instance, have nearly-complete top-to-bottom source code for all software running on the chip available. So that approach doesn't seem nearly as crazy as it would have 10-20 years ago.
Complete source code, except for the applications you want to run.
This assumes that the applications are provided fully compiled to object code. In situations where the applications are provided as bytecode (e.g. Android Dalvik) or are interpreted (e.g. Python) the applications of which you speak will run just fine.
...which (probably) explains why Google seems to be so interested in this new architecture. Besides Dalvik this new CPU architecture could also be used with the new Portable Native Client (PNaCl) which uses LLVM to compile to an intermediary bitcode. From this perspective, the Belt architecture makes a lot of sense.
This question is actually asked: https://www.youtube.com/watch?v=QGw-cy0ylCc&feature=player_d...
Is this architecture going to face the same issue?
Why don't you just recompile?