Memory

Tagged: , ,

This topic contains 34 replies, has 11 voices, and was last updated by  Ivan Godard 2 months ago.

  • Author
    Posts
  • #251

    staff
    Keymaster

    Talk by Ivan Godard – 2013-10-16 at Stanford


    Slides: PowerPoint (.pptx)
    This talk at Stanford EE380 Computer Systems Colloquium

    Mostly missless memory in the Mill CPU

    Avoiding the pain of cache misses in a statically-scheduled architecture

    The Mill is a new CPU architecture designed for very high single-thread performance within a very small power envelope. It achieves DSP-like power/performance on general purpose codes, without reprogramming. The Mill is a wide-issue, statically scheduled design with exposed pipeline. High-end Mills can decode, issue, and execute over thirty MIMD operations per cycle, sustained. The pipeline is very short, with a mispredict penalty of only four cycles.

    It is well known that exposed-pipe static scheduling yields near-perfect code with minimal power – except when there is a miss in the cache. In a conventional VLIW, a miss stalls the whole machine, whereas an out-of-order architecture can sometimes find other useful operations to execute while waiting on the memory hierarchy. The Mill uses a novel load instruction that tolerates load misses as well as hardware out-of-order approaches can do, while avoiding the need for expensive load buffers and completely avoiding false aliasing. In addition, store misses are impossible on a Mill, and a large fraction of the memory traffic of a conventional processor can be omitted entirely.

    The talk covers these and other technical aspects of the memory hierarchy in the Mill design.

    • This topic was modified 6 months, 3 weeks ago by  staff.
  • #324

    cypherpunks
    Participant

    (Moved from incorrect thread.)

    I would like to mention that I think the Mill’s load semantics are *brilliant*. Absolutely genius work. People have been trying to make software prefetch work for years, and never getting something that works right.

    By making it an actual load, just deferring the alias resolution, avoid the whole problem of haiving a second address computation, translation, cache lookup, etc.

    Three questions about loads:

    1. Your example seemed to have a minimum latency; on page 22 of your slides, couldn’t I ask for 0 delay and avoid the nops? Does it actually simplify things to leave out this feature?

    2. Have you played with a “load abandon” instruction for pickup loads? That would let me start a likely-to-miss load speculatively, and if it turns out to be unnecessary, reclaim the retire station without having to wait for the load to complete.

    3. I know it resolves same-processor aliasing, but what about multiprocessor? Does the technique let me hoist a load above a lock (e.g load-acquire)? That would definitely be a neat feature.

    • #328

      Ivan Godard
      Keymaster

      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 6 months, 2 weeks ago by  staff. Reason: fix link
      • #329

        Will Edwards
        Moderator

        It sounds to me like the snooping by retire stations is the same mechanism that ensures that aliasing is properly resolved on the single core, right?

        And if I recall correctly, this was on an arbitrary range of memory, rather than being on a cache-line level? Does this mean that in a multicore situation, there is no “false sharing” risk?

        So, at a stroke, another problem the Mill sidesteps and dances around? :)

        • #331

          Ivan Godard
          Keymaster

          Yes, no false sharing; the valid bits on each byte in cache are used by the coherence protocol so that several cores can own disjoint parts of the same line without having to swap the line back and forth. Invalidation is fire-and-forget; the writing core doesn’t have to get the line to write to it, and the sequential consistency memory model removes write-ordering issues so long as invalidations cannot cross in the mail, which is pretty easy to ensure in hardware.

  • #334

    imbecile
    Participant

    I suspect the answer is “Not Yet Filed”, but what was the main reason behind deciding to have one global address space for all processes apart from “Because we can” in 64bit.

    I don’t really like this for various reasons and it’s about the only thing I don’t like so far. The reasons mentioned in the videos for it seem to be minor and more incidental and not the real motivating factors.

    The overarching theme behind me not liking it is that it forces all code to be relocatable, i.e. all calls and jumps are indirect. Even when those instructions themselves are very effcient, they require separate loads and the use of precious belt slots.

    I used to think the main reason was because there is no real prefetching, even for code, and all latency issues are covered by the load instruction. But the prediction talk says differently.

    Another reason could be the mentioned but not yet explained mechanism that enables function calls without really leaving an EBB.

    But, when all processes think they are alone and have the full address space for themselves and all code and data sharing is done via shared virtual memory pages, all code can be statically linked (as far as the process/program itself is concerned), with all the advantages and optimization opportunities that gives, while still having all the advantages of relocatable code without any of the disadvantages. The specializer enables the creation of perfectly laid out memory images for each program in that specific system it is run on, and the virtual address translations, that always happen anyway, do the indirections for free.

    • #336

      Ivan Godard
      Keymaster

      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. :-)

      • #337

        imbecile
        Participant

        >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.

        That’s because I was confused due to lack of information and misinterpreting.

        >Given a 64-bit address space, static linking is right out

        True. Static linking should always be an offset to some implicit base too, especially in 64bit. Whether that base is NULL or some other fixed address or the current program counter for relative addressing doesn’t matter. The important part for static linking is that you can compute the final destinations at compile time and hardcode them into the instruction stream relative to that implicit base.

        Now having read your reply I get the impression that there is an implicit base for each module a process uses that is handled somewhere else that is not a belt slot, and that those implicit bases likely are initialized at module load time in some separate mapping structure in parallel to the virtual addresses.

        > there’s no advantage to fixing the base

        I can actually think of a few advantages to fixing the base (which of course is only possible when you don’t have a SAS). But:

        >The obvious one is getting the TLB out of 90+ % of memory access.

        When this indeed means that in 90% of the memory accesses the virtual address is the physical address and a translation is unnecessary and not done, I fully agree that this would obliterate any advantage I have in mind. I just can’t imagine how this would be feasibly implemented, you would need to know whether an address needs translating before you actually bother to look it up. I guess this can done with the protection zones.

        If that is not the case, and you still have to do address translation on every memory access, then I guess I could start listing and explaining all those advantages I figure fixed bases and offsets have to offer, especially on an architecture like the Mill.

        • This reply was modified 6 months, 2 weeks ago by  imbecile.
        • #339

          Will Edwards
          Moderator

          > you would need to know whether an address needs translating before you actually bother to look it up

          Do you need to?

          In the mainstream, the TLB does both mapping and protection; whereas in the Mill, translation is just mapping. Protection (turf reminds me of ‘get off my lawn’) is fast and between load/store FU and the top of the cache, whereas TLB is much slower but between the bottom of the cache and main memory (which is even slower anyway).

          • #340

            imbecile
            Participant

            > Do you need to?

            Yes, but I guess i can be done cheaply with the separate protection mechanisms.

        • #345

          Ivan Godard
          Keymaster

          This is all filed, but was at most alluded to in the talks so far. so here’s a more complete explanation.

          Code:
          All transfers use one of two modes: indirect through a pointer on the belt (no offset), or (up to 32-bit manifest) signed offset from the entry address of the current function. There is also a LEA form that returns the offset-from-function-entry result as a pointer dropped to the belt.

          Data:
          All address modes (load, store, and LEA) comprise a base, an up-to-32-bit manifest signed offset, and optionally an index from the belt with a manifest scale factor that left-shifts the index by 0-4 bits. The base may be either a pointer from the belt or one of a small set of specRegs that contain addresses. Currently these are:
          cpReg base of code region for load module
          cppReg base of constant pool in load module
          dpReg base of static data region
          fpReg base of stack frame, or NaR if no frame
          inpReg base of inbound memory-passed function arguments, or NaR if none
          tpReg base of thread-local storage, or NaR if none

          This list is expected to change as we discover issues when porting the OSs. In particular, cpReg and cppReg are likely to go away; there may be an outpReg added; and there may be a few levels of display added (for support of languages with closures). With these, all addresses in the code itself are static and no load-time relocation is necessary.

          cpReg, cppReg, and dpReg are initialized by the loader when the process is created. fpReg and inpReg are managed directly by the hardware via the call, retn, and stackf operations. The values of all these registers are currently readable by the rd operation, but that too may go away. They are reachable by MMIO, as used by the init ROM in the power-up sequence to set the initial execution environment.

          • #479

            imbecile
            Participant

            The TLB issues didn’t quite sit right with me, which usually is a sign I’m wrong or misunderstood something.

            What I obviously was wrong about, and which became clear upon rewatching this memory talk, is that the caches are all virtual addresses, and the overhead of going through the TLB is only done when that overhead is hidden by real DRAM access on a cache miss.

            That means you could still have per process address spaces and fix all the bases for direct memory access offsets and still get almost all address indirections for free through the virtual memory in the image created by the specializer. And even better than I thought before, since it only happens on cache loads and writebacks, not on every memory access.

            And there are more advantages:

            You could get rid of most of those per frame special base registers and replace them with one address space selector/process ID register (or integrate this into the frame ID). You would still need to encode the needed base in the load instructions though as if there were registers, so on the encoding side there is no real difference.

            Those hard coded bases/memory regions at the same time serve as the permissions, integrating them into the virtual addresses, making the separate protection tables redundant. Except that when those base selectors serve also as the permission, the encoding for stores and loads becomes smaller. For that to work you would have to make some cache invalidation on context switches though or have the processIDs as part of the key for cache lookup in some way.

            Having the permissions in the virtual address itself also enables the specialization of caches and cache behavior. You know certain data is constant or write only, because of its virtual address, allowing you to adjust cache strategies or even to have separate (and smaller and faster) caches for those.

            Having fixed virtual bases per process could make NUMA memory architectures (which very likely will only become more wide spread in 64 computing) visible to the processes and compilers themselves, adjusting their algorithms and load strategies and memory layouts and even process and thread scheduling accordingly.

            Very big gains from fixed offset bases are to be had in code, too. In this area this would mean a pretty big change in the architecture though. On the other hand, in a way it is bringing some of the core ideas of the Mill to their full potential:

            Having several fixed code pointer bases enables you to have even more instruction streams trivially. In the encoding white paper more than two instruction streams are said to be possible via interleaving cache lines, which has some problems. Well, a fixed base address for each instruction stream doesn’t have those problems and it gives you all those advantages of more streams mentioned like more smaller and faster dedicated instruction caches, smaller instruction encoding, specialized decoders an order of magnitude more efficient with each addtional one etc. Although you probably will get diminishing returns when you go beyond 4 streams (likely subdivisions of functionality would be control flow, compare/data route, load/store, arithmetic).

            There are some caveats with per process address spaces with fixed memory regions. The first process that sets up the virtual memory must be treated specially with a carefully laid out physical memory image. But considering how carefully laid out and crufted the lower memory regions on a pc are with IO addresses, bios code and tables etc. that isn’t anything that isn’t done routinely.
            Also sharing addresses between processes is harder and needs to be arbitrated in some way. And again this is something that is done in most current virtual memory systems. And it is a relatively rare operation, especially in comparison to normal intra-process cross-module function calls that would be much cheaper now.
            Another issue could be that actual executable code size is limited per process. But that is just a question of configuring the chip. Even in the biggest applications today the combined text segments of all modules don’t go beyond a few hundred MB. Actually I have never seen one one where actual code size goes beyond a few dozen MB. In essence a lower per process code segment of a few GB is far less limiting than the actual maximum installed memory usable by all processes. Especially in an architecture that is geared towards many cores, few context switches and compact code size.
            It could also be beneficial to encode the streams that are actually used after a jump into the control instructions. That spares unncesessary memory accesses. Although in practice at least the control flow stream and the compare/data route stream will always be used.

            This post is going quite off topic I guess.
            I also admit that I have another rather self centered and whimsical reason for wanting an own full address space for each process to use: I’m playing around with some language design, and letting each process design their own memory layout allows it to make a lot of safe assumptions about addresses, which in turn enable or make cheaper/free a lot of language features I’m interested in.

          • #490

            Ivan Godard
            Keymaster

            You are well on the way to inventing capabilities :-) https://en.wikipedia.org/wiki/Capability-based_addressing

            I truly wish that the Mill were a cap(ability) architecture. One of the Mill team is Norm Hardy, who did the KeyKos cap operating system, of which Eros and others are descendants. The first compiler I ever did was for the Burroughs B6500, which was a cap machine before caps were invented. One of the things that Andy Glew and I are in passionate agreement about is that computing needs caps.

            That said: I know how to build a cap machine, but I don’t know how to sell one. Caps are fundamentally incompatible with C, because caps are secure and C is not. Caps machines like the AS-400 let you use C by giving you a sandbox that is one whole cap in which you can be as insecure as you want within your play-PDP11. Oh well.

            And fair warning: language design is an insidious vice – you have a slippery slope ahead. Hear the words of someone whose name is in the Algol68 Revised Report :-)

          • #498

            imbecile
            Participant

            I read papers and documentation on KeyKos and Coyotos. Although that was a few years ago.
            And separate address spaces offer most of the advantages of capabilites without being C-incompatible. The traditional problem for separate address spaces is expensive context switches. But on multicore 64 bit processors context switches can be vastly reduced, and the Mill goes into that direction anyway. And with the cache architecture of the Mill and below cache TLBs context switches can become a lot cheaper too even with separate address spaces.
            And as you said yourself, it’s better to leave the OS out of as much things as possible and let the hardware take care of things, and capabilities must be OS constructs and cannot be hardware data types like virtual addresses can. Or am I wrong here?

            And yes, language design is a terrible vice. Ever since I started programming I was unhappy and annoyed and frustrated with whatever I was using. And whenever you try to find or to think of ways to do things better, what you find and learn usually only reveals new annoyances that make you quickly forget about the old ones you have solved.

          • #528

            harrison partch
            Participant

            Is a cap machine compatible with Oberon?

          • #529

            Ivan Godard
            Keymaster

            Yes, as far as I know. However, there are lots of Oberons, and the checking details are messy and not well documented, so it’s not certain.

          • #483

            PeterH
            Participant

            If I’m figuring this right, specReg based addresses can be made fork() safe. Data addresses getting their base from the belt, on the other hand, are not so easily rebased. I’m seeing heap memory using the latter in many cases.

          • #489

            Ivan Godard
            Keymaster

            Sorry, the protection model is NYF. Yes, we do fork(). Yes, it’s a kludge. About as much a kludge as fork() itself is :-(

  • #360

    imbecile
    Participant

    Thank you very much for that detailed information.

    Those are indeed quite a few base pointer special registers. I would be a bit sad to see the cpReg and cppReg go though. I can think of at least one use case where they would allow for elegant implementation of Haskell thunks/closures, where the closure memory layout/parameter description meta-data and the code thunk should be accessible via the same offset/pointer but must of course reside in different access permissions and thus need different bases.
    No idea if those “levels of display” would cover this, because I have no idea what that means in this context here.

    • #362

      Ivan Godard
      Keymaster

      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++?

      • #372

        imbecile
        Participant

        > 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++?

        I mean compiled closures.

        But since we’re getting more specific now I went and looked up this old Peyton Jones paper again, which you are most likely familiar with.

        In chapter 7 he describes how haskell core language closures could/should be implemented in stock hardware of the time. It’s very possible that most of that information very much obsolete today, but as you have said so nicely yourself, the architectures of stock hardware haven’t changed/improved much since then.

        In particular the optimization in 7.6 cannot really be done when constant data and code are in different memory protection turfs. In that case it would be beneficial to have implicit bases handy for both cases, so that one offset works for both, although the info table itself is far less referenced than the actual code.

        • This reply was modified 6 months, 2 weeks ago by  imbecile.
        • #386

          Ivan Godard
          Keymaster

          I read through the Peyton Jones paper; not sure how long ago I looked at if ever, though the Miranda paper I did read.

          Some general comments:
          1) The Mill design has generally been concerned with commercially important languages, and we haven’t put much thought into support for esoterica, which Haskell still is :-) However, we want to provide such support, but don’t really know enough about the issues and details at this point.

          2) The scheme of using global state over function calls as a way to do tail calls doesn’t work on a Mill; call has much more complex semantics than just changing the code pointer. However, the Mill supports label variables and indirect branches, which should provide a satisfactory substitute.

          3) The data structure in which there is a pointer to a closure which contains a pointer to an info record which contains a pointer to the code would be very painful on any modern machine, Mill included. This implies that a closure should contain both the code and the arguments so that it can simply be entered with a single indirection, which is free if the closure pointer is already on the belt. However, there are issues with mixed code and data, because the Mill uses a Harvard architecture with separate i$ and d$. There are also issues with protection; the PLB has byte granularity, but you *really* don’t want a PLB entry for every closure! As a naive alternative, the closure could contain the bindings and an info pointer and also a code pointer, eliminating one but not both indirections. I have to think about what the predictor consequences of that would be.

          4) One possibility is to use the function pointer representation of lexically nested functions as the representation of a closure pointer. That is, a closure pointer is the pair {code pointer, binding pointer}, as is used e.g. for Pascal and other languages with lexical nesting. We expect this form to be used for lambdas in C++. The drawback is that function pointers become 128 bits, which is OK on members with quad but not so good on smaller members.

          5) An alternative is to generate a thunk for each lambda or statically nested function, where the thunk loads a static pointer to the binding (or outer frame) and then jumps to the actual code. This approach is used by gcc for lambdas I think.

          6) both of the above have issues with where to put the data when there’s no GC; not relevant for Haskell and friends, but very relevant for C++.

          7) The natural place for the Node register is inpReg. There are interesting issues when the closure is in a different protection domain (“turf”) than the caller, which inpReg helps with (sorry, NYF). In particular, the caller must not be able to muck with the closure data before or during the call. This again suggests a thunk-like approach, but again the PLB can’t tolerate one thunk per closure-instance and even one per bind-clause may have performance issues.

          I’m probably showing my ignorance here :-( We will want to revisit this when the full machine is public.

          • #387

            imbecile
            Participant

            > The Mill design has generally been concerned with commercially important languages, and we haven’t put much thought into support for esoterica, which Haskell still is

            Fully understandable. But I also suspect that the frame contexts of which there isn’t too much revealed yet, provide everything you need.

            > However, the Mill supports label variables and indirect branches, which should provide a satisfactory substitute.

            I also expect the pick instruction to be very helpful there.

            > The data structure in which there is a pointer to a closure which contains a pointer to an info record which contains a pointer to the code would be very painful on any modern machine

            Yes, a lot has changed there. Most common uses of the info structure have been optimized away, in particular via tagging the pointers. And that is something the Mill supports better than any current hardware.

            > That is, a closure pointer is the pair

            You most likely wouldn’t even need two full 64bit pointers, just two smaller offsets and use the vector instructions to split them. At least in languages with a runtime.

            And I’m no expert by far either, so it should be given a rest here.

  • #484

    Will Edwards
    Moderator

    Can an EBB see the stack of its caller?

    Can you explain more how inpReg is used?

    And, finally, cheap thread-local-storage? Excellent news! Although I imagine many languages may repurpose it, if you let them use it as just another data segment.

    • #488

      Ivan Godard
      Keymaster

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

      But yes, cheap TLS :-) And micro-threads.

  • #516

    jabowery
    Participant

    Using real estate for more cores in preference to threading, resulting from the the Mill’s other architectural features, brings to mind a question about on-chip memory architecture that, while of no immediate consequence to the Mill chip, might affect future trade offs in real estate use.

    With 14nm and higher density technologies coming on line, there is a point where it makes sense prefer on-chip shared memory to some other uses of real estate. This raises the problem of increasing latency to on-chip memory, not only with size of the memory but with the number of cores sharing it. In particular, it seems that with an increasing number of cores, a critical problem is reducing arbitration time among cores for shared, interleaved, on-chip memory banks. In this case, interleaving isn’t to allow a given core to issue a large number of memory accesses in rapid succession despite high latency; it is to service a large number of cores — all with low latency.

    Toward that end I came up with a circuit that does the arbitration in analog which, if it works when scaled down to 14nm and GHz frequencies, might result in a architectural preference for a on-chip cross-bar switch between interleaved low-latency memory banks and a relatively large numbers of cores.

    This spans disciplines — a problem well known to folks involved with the Mill architecture which spans disciplines between software and computer architecture (rather than between computer architecture and analog electronics).

    I’d appreciate any feedback from folks who understand the difficulty of cross-disciplinary technology and have a better grasp the issues than do I.

    • #517

      Art
      Moderator

      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 6 months, 1 week ago by  Art.
      • #519

        jabowery
        Participant

        Thank you for pointing out the challenge of routing latency. Rather than further digression from the Mill memory architecture here, can you suggest a proper forum for discussing this?

        • #521

          Ivan Godard
          Keymaster

          Have you tried the comp.arch newsgroup?

  • #520

    Art
    Moderator

    Unfortunately, all of the places I have seen on line papers about multi-core interconnect have been on various university sites. I don’t see any of them with a proper forum for discussion.

  • #621

    Symmetry
    Participant

    So, the Mill has memory acccess that are the direct result of the execution of instructions but also implicit loads and stores that happen as a result of function calls as the belt and and outstanding memory accesses overspill their buffers and are stored in the general memory heirarchy. I think this would be infeasible on an architecture where any load or store might generate a fault immediately, but on the Mill it’ll just make it’s way through the memory heirarchy the same way anything else would and most interesting things will happen at the TLB stage in the same manner and with the same level of decoupling as any other write or read.

    How do you handle memory protection and synchonization with implicit operations? Just the same as with normal operaitons, possibly with a duplicated PLB and with the addresses broadcast to the retire stations?

    • #623

      Ivan Godard
      Keymaster

      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.

    • #624

      Ivan Godard
      Keymaster

      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.

  • #1060

    LarryP
    Participant

    I’m curious:
    How does/will the Mill implement the semantics of C’s volatile qualifier?
    From what I’ve gathered from watching the talks, the Mill always loads data from the cache hierarchy, not directly from main memory. However, the data in volatile variables (for example memory-mapped peripheral registers), can change independently of CPU activity, so cached values of volatile variables may well not be correct.

    Is there a mechanism, such as designating certain memory regions as non-cacheable, to ensure that the Mill implements the semantics of volatile variables? A forum search turned up a single forum entry that contains the word volatile. In Mr. Godard’s reply #733 in topic “Side channel timing attacks” he writes:

    One of those flags is “volatileData”, which forces the request to bypass private caches and go to the top shared cache.

    However, going to the top shared cache (instead of to main memory itself) doesn’t appear to implement the semantics of C-language volatile variables. Since the Mill is targeted at existing code bases, which include C and C++, I assume that there is (or will be) a way to preserve the semantics of volatile. If it can be revealed at this point, I’d very much like a confirmation that the Mill will preserve the semantics of the volatile qualifier — and, if possible, how the Mill handles volatile.

    Thanks in advance for any reply.

    • #1061

      Ivan Godard
      Keymaster

      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 :-)

You must be logged in to reply to this topic.