Memory

Answers:

1) 0-latency deferred load when there’s no work to overlap. Turns out that it’s expensive to stall issue; modern cores don’t stop on a dime. Hence it’s cheaper to assume a D$1 cache hit and insert the requisite no-ops. However, in nearly all cases the no-ops occupy zero bits in the code stream, so they are free; see Encoding.

2) There is an abandon mechanism for pickup loads and other in-flight state. NYF, but will be covered in the Pipelining talk.

3) Locks: the Retire Stations do snoop on the coherency protocol in multicore configurations. Multicore will be a talk, but not soon.

• This reply was modified 10 years, 12 months ago by  staff. Reason: fix link

Well, some answers are not NYF 🙂 Though there wasn’t a clear deductive line that led to SAS; it evolved by fits and starts like everything else.

I’m somewhat mystified when you say “Even when those instructions themselves are very effecient, they require separate loads and the use of precious belt slots.” True label- and function-pointers do exist on a Mill, and they must be loaded and then branched or called through, just like for any other machine, but the code would be no different with private address spaces. The great majority of transfers are direct and don’t use pointers, and those have neither load nor belt positions. You can branch to a label or call a function in a single operation with no belt change. Color me confused.

And yes, the predictor machinery does do prefetching. The phasing mechanism used to embed calls in an EBB is NFY, but will be covered in the Execution talk 2/5 at Stanford.
We assumed from the beginning that any architecture needed 64-bit program spaces; a 32-bit wall is just too constraining. We never really considered supporting both 32- and 64-bit program spaces; apps are written for both on x86 solely because of the massive install base, which we don’t have. We were afraid that either 32- or 64-bit mode would become dominant by accident and the other would die due to network effects, and our double work would be wasted. So pointers had to be 64-bits, less a few we could steal if we wanted to (and it turned out we did).

Given a 64-bit address space, static linking is right out: 64-bit offsets would completely hose the encoding and icache. So what gets statically linked in such systems, and what could replace it? Two answers: code, and bss (static data). Turns out that nobody has 4GB worth of code, and all big data is held in dynamic memory (malloc, with mmap behind it), not in static, so global static is under 4GB too. Sure, you can have a program that statically declares a 100GB array – but look at the code the compiler gives you for that – you’ll see something else going on behind the scenes, if the compiler doesn’t err-out right away.

So both code and static only need 32-bit offsets, off some address base. That takes care of the encoding issues, but also obviates static linking – there’s no advantage to fixing the base, because the instructions are now position-independent because they carry offsets, not addresses. Sure, you need an address-adder, but you needed that anyway to support indexing, unless you are a RISC Puritan and are willing to do individual shift and add operations, and pay for your purity in icache and issue slots. The Mill has quite conventional address modes: base, index and offset, requiring a specialized three-input adder. No big deal.

So now we have position-independent code (PIC), and 32-bit code and static data spaces within 64-bit overall space. Are all those 64-bits going to be used by any application? Within my children’s lifetime? Only on massive multi-processor supercomputers with shared memory. However, it’s increasingly obvious that shared memory at the building scale is a bad idea, and message passing is the way to go when off-chip. At a guess, 48 bits of space is enough for any app that we want to support in the market. And how many apps will there be? Or rather, how many distinct protection environments (called a turf in Mill terminology) will there be. Or rather, how much address space in total will be used by all turfs concurrently (after all, many turfs are small) on one chip? Surely much less than 64 bits.

So a SAS is possible without running out of bits or needing more hardware. What are the advantages? The obvious one is getting the TLB out of 90+ % of memory access. TLBs are horribly expensive on a conventional. They have their own cache hierarchy to hide some of the miss costs (which still run 20% or more cycles), and to be fast are a huge part of the power budget. All that goes away with SAS. Yes, SAS still has protection in front of the cache, but that is vastly cheaper than a full-blown TLB (NYF; there will be a Protection talk). The virtual address translation does not need to happen anyway, and is very far from free 🙂

Then there are software advantages: with SAS, processes can cheaply share data at any granularity and in any location; they are not restricted to page-sized shared mmap regions that require expensive OS calls to set up. Getting the OS out of the act permits a micro-thread programming model that is essential for painless parallel programming. The OS is simpler too – it doesn’t have to track whose address space a pointer refers to.

Now all this is an intuitive argument; we certainly don’t have the experience with large programs and real OSs to measure the real costs and benefits. But we were persuaded. 🙂

A “display” is a mechanism to implement lexically nested functions.

Are you thinking about closures created by a JIT, where the code could be anywhere and the code and data may be moved by the GC? Or compiled closures like lambdas in C++?

Sorry, the whole process model is very different, but it’s all NYF. Talk#11 maybe?

But yes, cheap TLS 🙂 And micro-threads.

From following the link you give, I see the general outline of the idea. The challenge of implementing such a device will be to make it deterministic for larger numbers of cores and banks, which is where it would potentially have the greatest benefit. I did not see sufficient detail to make any determination regarding that aspect of the idea’s feasibility.

That said, the problem being attacked is determining which core gets access to which bank. There are several sources of latency here: the arbitration mechanism latency, the “bank is busy” latency, routing latency and RAM access latency. This idea only directly addresses the arbitration mechanism latency. By allowing a larger number of banks, it appears to indirectly help the “bank is busy” or “bank access collision” latency. Unfortunately, a larger number of banks or cores will also increase routing latency. So in the end, routing latency may merely replace arbitration latency as being the performance limiting factor.

• This reply was modified 10 years, 11 months ago by  Art.

There are essentially three layers in the spiller. At the top layer, data is stored in flipflops, effectively registers except not addressable by the program. These are buffers, used as parking places for values that are still live on the belt and are in the result register of a functional unit but the FU has another result coming out and needs its result register back. These live operands are first daisy-chained up the latency line within the containing FU pipeline, but eventually the pipeline runs out and the operand, if still live, gets moved to a spiller buffer. This cost of the move is the same as a register-to-register copy on a conventional machine. A running program that doesn’t do a function call or return will live entirely in these registers, with no spiller traffic below that.

The second layer is a block of SRAM, connected to those spiller registers. When you do a call operation, we save the belt, which means the belt state in pipe and spiller registers is saved. The save is lazy, but gradually live-but-inactive operands are copied from the needed registers into the spiller SRAM. The SRAM is big enough to hold several belts (and scratchpads and other non-memory frame-related state), so you can nest several deep in calls with everything fitting in the spiller SRAM. Most programs spend most of their time withing a frame working set of five or so, calling in a few, returning out a few, calling in a few, over and over. Such behavior fits entirely internal to the spiller.

However, if a program suddenly switches to a deep run of calls, a run of returns, or if there’s a task switch, the state of all those nested calls (or the new thread) will exceed the spiller’s SRAM and the spiller then uses the third level, which is the regular memory hierarchy. The spiller does not go direct to DRAM; it talks to the L2 cache instead, which provides still more buffering.

If you compare the spiller with the explicit state save used by a conventional legacy register machine, you will see that the spiller top level is akin to the register machine’s rename and architected registers; if a function fits in the registers then there’s no traffic, just as if it fits in the belt and scratchpad there’s no traffic.

If there are nested calls on a conventional then the register state gets saved to the hierarchy using normal store operations. These go to the D$1 cache and are buffered there. This is akin to the spiller’s SRAM, but the spiller has three advantages: it uses no program code to do the save, so the power, instruction entropy, and store buffer contention cost of the stores is avoided; it uses a private repository, so saves are not cluttering the D$1 (which is a very scarce resource); and it’s not program visible, removing many possibilities of program bugs and exploits.

Lastly, if you have deeply nested calls on a conventional, the saved state exceeds the capacity of the D$1 and will overflow into the D$2 and eventually DRAM. The spiller does the same when it runs out of private SRAM. Put all this together, and you see that the spiller is in effect a bunch of registers hooked to its own cache, and the overall benefit is to shift state save/restore out of the top level D$ cache and into the spiller SRAM which is in effect a private spiller cache, freeing up space for real data.

One last point: the total Mill state traffic is less than that on a conventional. A conventional callee-save protocol winds up saving registers that are in fact dead, but the callee doesn’t know that and saves them anyway. And the existence of the scratchpad on a Mill means that many function locals that would be kept in memory are in the scratchpad and so do not contribute to cache load and memory bandwidth. Combine these effects, and our sims suggest that the Mill save/restore and locals traffic is about a factor of two less than that of a conventional. This saves not only bandwidth but also power.

We do not have large-scale sims yet so the overall results are guesstimates, but it does appear that actual DRAM traffic on a Mill will be overwhelmingly composed of I/O and very large external data sets, which have the same traffic load as on a conventional; save/restore, locals, and the working set of globals will never see DRAM. That’s why we the Mill has the Virtual Zero that lets it use “memory” that has no backing DRAM.

All this needs pictures, and we will get to the spiller in the talks eventually.

p.s. Forgot to respond to your protection question:

The spiller has its own region of the address space. Spiller space is used for all processes, and the save state of the different processes are not in the process’s address space and so cannot be directly addressed by the program. In effect you can think of the spiller having its own private PLB, although it need not (and so far is not) implemented that way.

Utilities like debuggers and stack unwinders get access to saved state through an API that runs with PLB rights to spiller space; in effect the API is another process. The API is restricted; you cannot arbitrarily change the downstack links for example. As a result, the usual stack-smash exploit is impossible on the Mill.

Because the application cannot address spiller space, there is no synchronization needed between app use of memory and spiller use of memory; they are necessarily disjoint.

Being hardware, the Mill is not language-specific, but must support all common languages, common assembler idioms, and our best guess as to where those will evolve.
The best that we, or any design team, can do is to try to isolate primitive notions from the mass of semantic bundles and provide clean support for those primitives, letting each language compose its own semantic atoms from the primitives we supply.

The “volatile” notion from C is used for two purposes, with contradictory hardware requirements for any machine other than the native PDP-11 that is C. One purpose is to access active memory such as MMIO registers, for which the idempotency of usual memory access is violated and cache must not be used, nor can accesses be elided because of value reuse.

The other common purpose is to ensure that the actions of an asynchronous mutator (such as another core) are visible to the program. Here too it is important that accesses are not elided, but there is no need for an access to go to physical memory; they must only go to the level at which potentially concurrent accesses are visible. Where that level is located depends on whether there are any asynchronous mutators (there may be only one core, so checking for changes would be pointless) and the cache coherency structure (if any) among the mutators.

Currently the Mill distinguishes these two cases using different behavior flags in the load and store operations. One of those is the volatileData flag mentioned in the previous post. This flag ensures that the access is to the top coherent level, and bypasses any caching above that level. On a monocore all caches are coherent by definition, so on a monocore this flag is a no-op. It is also safe for the compiler to optimize out redundant access, because the data cannot change underneath the single core.

On a coherent multicore the flag is also a no-op to the hardware but is not a no-op to the compiler: the compiler must still encode all access operations, and must not elide any under the assumption that the value has not changed, because it might have.

On an incoherent multicore (common in embedded work), a volatileData access must proceed (without caching) to the highest shared level, which may be DRAM or may be a cache that is shared by all cores. Again, the compiler must not elide accesses.

For the other usage of C volatile keyword, namely MMIO, the access is to an active object and must reach whatever level is the residence of such objects. On the Mill that level is the aperture level, below all caches and immediately above the actual memory devices, and the flag noCache ensures that an access will reach that level. Again, the compiler must not elide noCache accesses.

Besides the noCache flag, the Mill also maps all of the physical address space to a fixed position (address zero) within the (much larger) shared virtual space. An access within that address range is still cached (unless it is noCache) but bypasses the TLB and its virtual address translation mechanism. NoCache addresses outside the physAddr region (and volatileData accesses if they get past the caches) are translated normally.

There are other access control flags, but that’s enough for now 🙂

There are no RMW ops. The Mill uses optimistic concurrency using the top level cache for the write set, much like the IBM and Intel optimistic facility. It’s been mentioned somewhere, but I don’t remember if it was in the talks or here, or maybe comp.arch.

The linked article mentions the Mill CPU architecture just once, in a sentence so vague that I cannot honestly tell what the author believes to be true about the Mill:

BTW, this is a major reason I’m skeptical of the Mill architecture. Putting aside arguments about whether or not they’ll live up to their performance claims and that every chip startup I can think of failed to hit their power/performance targets, being technically excellent isn’t, in and of itself, a business model.

The first word of the above quote is such a vague reference (the previous paragraphs were about memory barriers and what is/isn’t guaranteed on multiprocessor systems), that I cannot tell what the author is trying to say about the Mill. Has anyone else read the linked article, and better understood what the author was trying to convey?

Its possibly ambiguous, but I don’t think he was being skeptical of the Mill memory model. I think he was being skeptical of there being any business for non-x86 chips even if they are better? That was my reading of that part, anyway.

When I read the article the other day (proggit discussion), I cherry picked some of the technical problems he raised and summarised what the Mill was doing in each area:

• TLBs and TLB misses: translation of addresses is after the cache hierarchy; the cache is in virtual addresses and the memory is shared so there’s no translation needed in IPC and context switches.
• locks: we’re 100% hardware transactional memory (HTM) on which you can build conventional locks; but you can jump ahead and write your code to use HTM directly for a big performance gain
• Syscalls and context-switches: there aren’t any context-switches; we’re Single Address Space (SAS). Syscalls are much much faster, and you aren’t restricted to a ring architecture (hello efficient microkernels and sandboxing!)
• SIMD: the Mill is MIMD. Much more of your code is auto-vectorizable and auto-pipelinable on the Mill, and your compiler will be able to find this parallelism
• Branches: we can do much more load hoisting and speculation. We’re not Out-of-Order (OoO), so its swings and roundabouts and we often come out ahead

Free forward with any technical questions related to the article 🙂

Sound questions.

1) Frame exit invalidation is done in the Well Known Region for the stack. It is not necessary to clear the valid bits, because the exited frame is no longer in the user’s address space; return automatically cuts back the stack permission WKR. However, there is an issue with inter-core references to foreign stacks. Core B has no WKR for core A’s stack, so in normal mode threads cannot reference each others stacks and threads cannot reference their own exited frames. However, there is a legacy mode in which inter-stack references are permitted. In legacy mode the entire stack, both used and unused, has a PLB entry for the turf. So if there are two legacy threads running in the same turf then they can browse each others stack, and can browse the rubble in their own stack. We have never found a way to restrict interstack references to only the live portion; all practical implementations seem to require exposing rubble too.

2) The implementation of the TLB is per-member; it is transparent to the programmer. As currently in the sim, a miss in the TLB requires a search of the PTE tables. However, unallocated regions of the 60-bit address space do not need PTEs and do not occupy physical memory. If the search leads to an address where a PTE might be but is not, then the Implicit Zero logic will return a synthetic line of zeroes. The PTE format is carefully arranged to that a zero PTE means that the region is unallocated in DRAM – and the load in turn returns implicit zero. Thus the page table is in virtual memory, not physical, and there are only entries for mapped space.

Thus the miss will trigger a search, which may miss, which triggers a search… The Tiny Alice algorithm we use bounds the recursion to the number of distinct range sizes (current 5), but in practice the intermediate entries are in the LLC and search depth is nearly always <= 2.

Short functions with loads tend to have extra noops or stalls for the reason you give. A sufficiently smart compiler could issue prefetches in the caller, just as can be done for any architecture. But the general Mill approach is inlining.

Most ISAs inline to avoid call overhead, but calls are cheap on a Mill. We inline to get more for the machine width to work on. On a wider Mill you can inline surprisingly large functions with zero latency cost in the expanded caller, because the called ops fit in the schedule holes of the caller. Of course there is usually some increase in the code space used, but removing the call and return means less thrashing in the cache lines, so net it’s a win unless profiling shows the call is never taken.

We’re still tuning the inlining heuristics in the tool chain. As a rule of thumb, any function shorter than a cache line is worth inlining on icache grounds alone.