NarrateurDuChaos
Hello there!
It's been a while since somebody asked lots of technical questions on this forum. I thought I would pick it back up, and try to discuss things that haven't been brought up too much, either in the video talks or on the forums.
Since I have a ton of questions, I'll be splitting them roughly by subject in posts below.
NarrateurDuChaos
- 1) Exit prediction with dynamic addresses.
What's the current story for exit prediction with dynamic function pointers, vtables and such? Obviously, if you have a loop iterating over an array of virtual objects, the predicted address for a single call instruction isn't going to be too helpful. But it's probably suboptimal to throw up your arms and say "it can't be predicted", since sometimes these addresses will be available tens of cycles ahead of time.
I think you mentioned potentially using deferred branches, but eventually gave up on the idea. If nothing else, deferred branches wouldn't help you with the "array of objects" cases, since it could presumably only predict the first one.
Ideally, you would want to have predictions available for each vtable in the array, so you can call the next method as soon as you returned from the last one. Maybe you could have a prediction queue of some sort? Or an alternate encoding scheme for when the Exit Table predicts that a given exit will always be a dynamic branch?
- 2) Hardware prefetching
How does the Mill handle data-side hardware prefetching? Traditional CPUs mostly rely on detecting stride patterns, eg "If you asked for addresses 12037, 12047 and 12057, you're probably going to ask for 12067". Do you expect Mill cores to do stride detection?
Deferred load can help hide the latency of an L1 miss, but obviously don't help with an L3 miss. But there are some common patterns (eg tree traversal, arrays of pointers) where stride detection and deferred loads don't help at all, but the hardware would still have enough information to prefetch lots of data ahead of time. For instance, a foreach loop iterating depth-first over a binary tree might want to take the left branch immediately and prefetch the right branch, thus skipping half the L3 misses. Does the Mill provide anything to facilitate this?
- 3) Inner-loop specific optimizations
The "inner" instruction seems like it would open a lot of potential for optimizations. Have you explored loop-specific optimizations?
I'm thinking about things like exact exit prediction (if you're looping from "i = 0" to "i < array.size", you know exactly how many iterations the loop will run), smart prefetching (in a loop with no branches, you know exactly what loads the next iterations will run, so you can prefetch them ahead of time), etc.
I know that a lot of software prefetching is wasted because it prefetches past the end of a loop and things like that, but the hardware would have enough info to be precise.
NarrateurDuChaos
- 4) Tail calls
Does the Mill support tail-call instructions? I'm told they're important for some functional programming languages.
You might be able to save instruction entropy by encoding tail calls as "a return ganged with a function call".
- 5) Exception handling
Do you have first-class C++ style exception handling?
By "first class", I mean "zero-cost if no exception is thrown", so no branch-after-every-function-return or things like that.
Also, can you handle setjmp/longjmp?
- 6) Coroutines
Do you support stackless coroutines in hardware? By coroutines, I mean functions you can jump into, yield from, and then jump back into at the yield point.
By stackless, I mean "unlike a thread, they don't need their dedicated stack and add stack frames directly to the caller's stack". I guess the big difficulty would be spilling directly to userspace.
NarrateurDuChaos
- 7) Benchmarking support
Are there plans to support stable benchmarking in the Mill? Benchmarks often have to go through all sort of contortions to get filter out performance noise: warming up caches, running multiple times to smooth outliers out, maybe even recompiling multiple times to test performance with different code layouts, etc.
The Mill has some natural advantages: the Exit Table can be preloaded, and no runtime reordering means better stability. Do you have plans to include features specifically for stable execution? Things like purging caches, avoiding interrupts, pinning cores, etc?
- 8) Profiling support
Similar to the previous question, do you have plans to support fine-grained profiling? Profilers often give out coarse information like "this function was executed roughly X times", "this function took roughly Y cycles on average", etc.
You can use emulation tools like valgrind to get more fine-grained info like the number of L2 misses from a specific instruction, at a cost of massive performance loss. Could the Mill provide tools to help get fine-grained data without the massive overhead?
- 9) Profile-guided optimization
How does Mill plan to benefit from PGO?
Traditional PGO is mostly centered on layout: the profiling phase gets coarse-grained info about which functions are called most often in which order, and from that the compiler knows both which functions to optimize for size vs performance (in other words, which loops to unroll and vectorize) and which functions should be laid out together in memory.
It feels like, since the Mill is a lot more structured than traditional ISA, it could get a lot more mileage from PGO. It can already get benefits through the Exit Table. Are there plans to facilitate other optimizations, besides general code layout?
- 10) Specializer hints
Because of the whole Specializer workflow, the genASM format is essentially a compiler IR. As such, have you thought about including hints to help the Specializer produce better local code?
Some hints might include (straight from LLVM): aliasing info (saying that a load and a store will never alias), purity info for function calls (saying a function will never load/store/modify FP flags), generally saying that a loop is safe to unroll, etc.
NarrateurDuChaos
- 11) Feature detection
Are there any plans for the general Mill ISA to have instructions of the form "If this feature is available on the target architecture, compile this EBB, otherwise compile this other EBB"? I know something similar is planned for WebAssembly.
- 12) Any plans for over-128-bits SIMD?
In past discussions on the subject you seemed to think it was a future possibility? Now that AVX-512 has been out for a while, have you settled?
Do you think there's benefit in having 256-bits or 512-bits vector instructions, or do you think having a very wide pipeline always provides the same benefits?
- 13) Economy cores
Recently, mobile CPUs and the Apple M1 have started to use designs based on "economy cores". The idea being that the CPU includes a large number of small, low-frequency, less-performant cores that the device could use both as additional threads on heavy workloads, and as the only threads for when the device needs to conserve power.
Could the Mill provide a similar architecture? In the past you've floated the idea of a chip with both Silver and Tin cores (I think), but those would have incompatible binary formats. Have you considered ways a single device (eg smartphone) could run multiple cores with different specs while still executing the same binaries?
NarrateurDuChaos
- 14) Function signature tags
I know you've said in the past that jumping to an attacker-supplied address is very unlikely to be a problem in the Mill, because the bidirectional encoding means arbitrary addresses in executable memory are very unlikely to be valid code; but still, have you considered adding some hardening for dynamic function calls? History has proven that attackers can be a *lot* more imaginative than defenders in building exploits out of seemingly unusable flaws.
Hardening might include checks that the caller function has supplied the right number and shapes of arguments, and that the target of a dynamic function call is indeed a function and not an arbitrary EBB (for instance, it could check that the EBB starts with a stackf instruction).
- 15) Formally proving safety
Have you considered looking into formal proofs of safety?
I don't know about processors, but the idea of formal proofs for compilers has been picking up steam lately, as exploits keep piling up.
In particular, while you've talked a great deal about how the Mill made Spectre-style exploits harder/impossible, do you have an actual model for what information is available to a given user through caches and side-channels, and how you might guarantee that these side-channels can't be used to extract privileged information?
(My background here is from the Rust language, where the compiler provides guarantees that certain types of exploits can't happen except when certain escape hatches are used. While these guarantees do hold strong in practice, there has been a major drive to figure out the formal rules the guarantees implicitly rely on, to have a better model of what code is sound and why.)
NarrateurDuChaos
- 16) What have you learned from the M1?
The Apple M1 has been a bit of a shockwave in the CPU world. Everyone was surprised what a company like Apple could get in terms of single-core performance for a consumer product, once they had control of the entire supply chain.
Are there any lessons you took from them? Anything you've decided to do differently after you saw their results?
- 17) What have you learned from other recent innovations?
The announcement of the Mill was almost 10 years ago, an eternity in computer times. Since then, a lot has happened, both on the hardware side (which I'm not too familiar with) and the software side. I'm thinking of WebAssembly, Fuschia, Rust and other memory-safe languages, eBPF, io_uring, etc.
Did any of these lead you to change plans or think of new features you could add to the Mill? I know you've said that eg the Mill would be particularly well suited to running WebAssembly, but have you considered adding instructions specifically to help WebAssembly support? To help Rust support?
(I'm thinking of the M1 which added instructions to run JS faster, and faster atomic counters since Swift and Objective-C use lots of ref-counted pointers. Mill could probably benefit from a fast bound-checks instruction.)
- 18) Any clever ideas you've had lately that didn't pan out?
I know there are a lot of clever ideas you can't talk about because you want to patent them first, but are there some clever ideas you've had, that you put some research effort into, and that you ultimately discarded because they didn't pan out in practice?
ivan
Wow, what a pile of excellent questions! Thank you.
ivan
– 1) Exit prediction with dynamic addresses.
The cause of the exit transfer doesn't matter for prediction, with the exception of returns. Most ebbs (hyperblocks) have several conditional ways to exit, one of which is taken; the predictor says where the taken one will go, in which cycle, and the kind of transfer (call/return/branch). The prediction itself doesn't care whether it was something dynamic. Calls and returns use a predictor-maintained stack of return positions rather than an actual address in the prediction; the return prediction entry itself just says "return" and pops the entry.
Your question seems to assume that prediction is per transfer site, as in per vtable. It's not; it's per transferred-to location: if you got here somehow, then you will next get there. History prediction can use a chain (actually a hash) of heres. If a region of code contains a bunch of vtable transfers on the same object, the first will predict that the object will be of the same type (and transfer the same way) as the prior object - and miss if wrong. But the history will then kick in and subsequent transfers will predict the transfer sequence of the last time an object of the same type was processed. There's a per-member tradeoff between the size of the predictor and the fanout of types that the predictor can handle.
ivan
– 2) Hardware prefetching
Data prefetch is per-member. The present members at Silver and above have stride prefetching defined; others have none. We haven't poked at anything more complicated, and do not expect to do so pending customer experience with real data and apps.
ivan
– 3) Inner-loop specific optimizations
Anything of this sort would be member-specific, and none of the current members do such things. There has been some thought though; at one point we considered a "do(n)times" branch form. One problem is that the needs and possible optimizations are heavily domain dependent: "inner loop" screams "scientific programming", whereas more conventional code can actually be detuned by keeping extra state for "optimization".
ivan
– 4) Tail calls
There is no special architectural support for tail calling at present. The LLVM-based compiler and tool chain can convert recursion to tail calling loops. This is actually easier in a Mill than in a register architecture, because the belt means you don't have to overwrite register contents, just use the new values, as you do in a loop.
ivan
– 5) Exception handling
Mill has first class C++ exceptions in a way that is NYF (Not Yet Filed, sorry). The mechanism is also used for setjmp/longjmp. A consequence of the design is that exceptions work in the kernel code itself, and do not require trapping to recovery code nor use of the file system.
The facility is not entirely zero cost because there are setup and control instructions needed to define the exception environment and these do cost code space. However there is no latency cost if not thrown. The latency of a caught throw is roughly the same as the equivalent sequence of return instructions and destructor calls if directly executed, mostly due to mispredicts in the control flow of the exception path; there are no table searches or file lookups. The net result is that Mill exceptions are a practical control flow technique that can be used, and thrown, in performance critical and kernel code.
ivan
– 6) Coroutines
This functionality is subsumed under streamers, which are NYF. The semantics is slightly different, but nearly all use of such coroutines is to implement streams and at present we do not expect to separately support stackless coroutines beyond whatever the compiler/language system provides. There has been some talk about what we should do to help microthread systems, but frankly we're too ignorant of the needs to do much without more experience.
ivan
– 7) Benchmarking support
Nearly all of this topic is at the OS and language levels, not the architectural level. There are some admin operations presently defined - bulk purging the cache for example - and there may be more added as needed, but most such things, interrupt control for example, are the property of various system services and most systems don't make them available for use directly by apps. Of course, you could write your benchmark to run on a bare machine and get control at power up...
ivan
– 8) Profiling support
This too is mostly the domain of language and OS. The usual instrumentation methods will work on a Mill of course, but transparent instrumentation has really nasty issues with security that can only be addressed by the OS security model, not the architecture. Do you really want to give this turf the ability to dynamically change (i.e. instrument) the code being run by that turf?
In addition, like all wide machines the Mill presents an execution model that is not the single-program-sequence of a z80. What does it mean to single-step a program when it fires a dozen instructions at once, and retires them at a dozen different points in time? Our tools give us a good view of machine level debugging - but debugging and profiling Mill at the source level is just as hard as doing it for heavily optimized code on any architecture.
The tool chain does have a mode (still buggy) in which the code emulates a one-complete-instruction-at-a-time architecture, z80-ish. That helps with debugging and some profile questions like how many times was something called, but is completely useless for timing questions. These are human-factors questions for which nobody seems to have answers on any architecture.
ivan
– 9) Profile-guided optimization
The tool chain does not yet have PGO support, so this answer is speculative. Many, perhaps nearly all PGO optimizations are counter-productive on a Mill. Thus for example unrolling loops prevents software pipelining and forces spill/fill of transients that otherwise would live only on the belt for their lifetime; shut unrolling off for better performance. It is also unclear how much function and block reordering will actually pay; our best estimate now is "not much" because so much Mill control flow is collapsed in the tool chain into much larger blocks and gets executed speculatively. Exit prediction also sharply cuts the fetch overhead that reorder is intended to help.
Lastly, SIMDization (they are not really vectors in the Cray sense) can be done in the tool chain as well for the Mill as for any architecture. Our major advance is the ability to do SIMD with per-element error control. Whether apps will take advantage of that to improve their RAS is as yet unclear.
ivan
– 10) Specializer hints
The tool chain already responds to some of the hint info that LLVM provides. In addition, our dumper (IR to genAsm shim) extracts some info known to LLVM that is not in the IR from LLVM internal structures and adds to the genAsm. An example is the ordering dependency oracle in the genAsm for each function body, which encompasses what LLLVM knows from the aliasing info and function body analysis. Generally we want to push that sort of info and analysis into the steps before genAsm, and let the specializer use the result of the analysis (such as required ordering) without doing the analysis itself.
For your specific examples:
* aliasing is reflected in the oracle; potentially colliding references have an oracle entry giving the textual order
* flags are local in the architecture; ops that change global flags are ordered in the oracle w/r/t ops that use them
* loops should not be unrolled; SSA form (in the IR and genAsm) eliminates most references and the pipelining preserves order across iterations for the rest
ivan
– 11) Feature detection
Member detection exists now; that's how we handle per-member differences such as whether quad (128-bit) arithmetic is present. The specializer replaces non-existent genAsm operations with synthesized calls on library functions, often inlined. There is not currently any way to do feature (as opposed to member) detection in source that gets passed through; you'd use pre-processor facilities to build targeted genAsm, or select the desired genAsm in the prelinker. This may change as we get further into the OS work.
ivan
– 12) Any plans for over-128-bits SIMD?
The problem with wide SIMD is that the belts position widths must match the widest possible, which is wasteful for the vast majority of code that won't use it, or we would need to have multiple belts of differing element widths with the concomitant hassles of multiple ops/transfer move instructions/etc. that plague the legacy ISAs with multiple register widths. We have pretty much settled that SIMD in a member will only be to the widest scalar width, and further parallelism will be provided by wider pipes.
As an aside: auto-SIMD with the same semantics as scalar has been ten years away for a very long time. It is worst when the code does something unexpected, like overflow. At least on a Mill you will get the same answer SIMD or scalar; good luck on legacy ISAs.