7 ms·

"The R1000 addresses 64 bits of address space instantly in every single memory access. And before you tell me this is impossible: The computer is in the next ro

"The R1000 addresses 64 bits of address space instantly in every single memory access. And before you tell me this is impossible: The computer is in the next room, built with 74xx-TTL (transistor-transistor logic) chips in the late 1980s. It worked back then, and it still works today." That statement has to be coming with some hidden caveats. 64 bits of address space is crazy huge so it's unlikely the entire range was even present. If only a subset of the range was "instantly" available, we have that now. Turn off main memory and run right out of the L1 cache. Done. We need to keep in mind, the DRAM ICs themselves have a hierarchy with latency trade-offs. https://www.cse.iitk.ac.in/users/biswap/CS698Y/lectures/L15.pdf https://www.cse.iitk.ac.in/users/biswap/CS698Y/lectures/L15.... This does seem pretty neat though. "CHERI makes pointers a different data type than integers in hardware and prevents conversion between the two types." I'm definitely curious how the runtime loader works.

cmrdporcupine 4y ago
"We need to keep in mind, the DRAM ICs themselves have a hierarchy with latency trade-offs" Yes this is the thing -- I'm not a hardware engineer or hardware architecture expert, but -- it seems to me that what we have now is a set of abstractions presented by the hardware to the software based on a model of what hardware "used to" look like, mostly what it used to look like in a 1970s minicomputer, when most of the intensive key R&D in operating systems architecture was done. One can reasonably ask, like Mr Kamp is, why we should stick to these architectural idols at this point in time. It's reasonable enough, except that the alternative of heterodox, alternative architectures is also heterogenous -- new concepts that don't necessarily "play well with others." All our compiler technology, all our OS conventions, our tooling, etc. would need to be rethought under new abstractions. And those are fun hobby or thought exercises, but in the real world of industry, they just won't happen. (Though I guess from TFA it could happen in a more specialized domain like aerospace/defence) In the meantime, hardware engineering is doing amazing things building powerfully performing systems that give us some nice convenient consistent (if sometimes insecure and awkward) myths about how our systems work, and they're making them faster every year.
- bentcorner 4y ago
  Makes me wonder if 50 years from now we'll still be stuck with the hardware equivalent of the floppy disk icon, only because retooling the universe over from scratch is too expensive.
- nine_k 4y ago
  As they say, C was designed for the PDP-11 architecture, and modern computers are forced to emulate it, because the tools to describe software (languages and OSes) which we have can't easily describe other architectures. There were modern semi-successful attempts though, see PS3 / Cell architecture. It did not stick though. I'd say that the modern heterodox architecture domain is GPUs, but we have one proprietary and successful interface for them (CUDA), and the open alternatives (openCL) are markedly weaker yet. And it's not even touching the OS abstractions.
  - aap_ 4y ago
    > As they say, C was designed for the PDP-11 architecture Not really though. A linear address space was not particularly specific to the PDP-11. The one point where C really was made to fit the PDP-11 was the addition of a byte datatype (aka char), but the PDP-11 wasn't unique in that regard either.
    - nine_k 4y ago
      PDP-11 wasn't unique. To the contrary, it had many typical features. - Uniform memory, cache memory is small, optional and transparent. - A single linear address space; no pages, stack in the same RAM as data. - A single CPU, with a single scalar ALU, and completely in-order execution; no need for memory barriers. A typical modern machine larger than an MCU has several level of memory hierarchy which affect performance enormously, the physical RAM is mapped all over the address space, several execution units process data in parallel and often out of strict order, there are many variants of vector (SIMD) instructions, and usually a whole vector co-processor ("graphics card"). This breaks many of the assumptions that C initially ha made, and hardware tries hard to conceal the memory hierarchy (well, your OS may allow you to schedule your threads to the same NUMA domain), to conceal the parallel execution, to conceal the memory incoherence between processing nodes, etc. Well, you sort of can make the compiler infer that mean a vectorized operation, or use an intrinsic. In my eyes, the C's assumptions about hardware show their age, and also hold the hardware back.
mikepavone 4y ago
> That statement has to be coming with some hidden caveats. 64 bits of address space is crazy huge so it's unlikely the entire range was even present. If only a subset of the range was "instantly" available, we have that now. Turn off main memory and run right out of the L1 cache. Done. So I did some digging around for documentation about this machine and it looks like it puts the upper 54-bits of the address through a hash function to select an entry in a set associative tag RAM which is then used to select a physical page. This has the possibility for collisions, but it can get away with that because RAM is just a cache for disk contents. Certain parts of the address technically mean something, but apart from leveraging that in the design of their hash function it has no real relevance to the way the hardware works. This scheme would work with linear 64-bit addresses just fine with an appropriate hash implementation. Basically all that's happening here is that the TLB is large enough to have an entry for reach physical page in the system and a TLB miss means you have to fetch a whole page from disk rather than walking a tree of page tables in memory. I think the other thing going on here is that the R1000 is a microcoded machine from the 80s with no cache (well unless you're counting main RAM as cache, so it probably has a relatively leisurely memory read cycle which makes it more straightforward to have a very large TLB relative to the size of main memory. There's no magic here and no lessons for modern machines when it comes to how virtual address translation is done
- phkamp 4y ago
  You are right that there is no lessons for "modern machines" as we build them now. But that is precisely my point: Maybe there are better ways to build them ?
  - mikepavone 4y ago
    What I mean is that the R1000 memory architecture is not fundamentally different from modern hardware in a way that seems to solve any modern design problems. The tag RAM is functionally equivalent to the TLB on a modern CPU, but it's much larger relative to the size of the RAM it's used with. The 2MB memory boards described in US Patent 4,736,287 (presumably an earlier version of the 32MB boards present in the R1000/s400) have a whopping 2K tag RAM entries. This is the same size as the 2nd level data TLB in Zen 2 which is supporting address lookup for a much larger main memory. If you were to try and make a modern version of the R1000 architecture you're going to run into the same size vs speed tradeoffs that you see in conventional architectures. The server oriented Rome SKus of Zen 2 support 4 TB max RAM. Even if you bump the page size to 4MB, you still would need 1M TLB/tag RAM entries to support that with an R1000-style implementation.
phkamp 4y ago
The entire address space (64 address bits, addressing bits, so "only" 61 bit addresses for bytes, but also 3 "kind" bits, separating code/data/control etc.) were available at all times. The crucial point is that the RAM wasn't laid out as a linear array, but as a page-cache. In a flat memory space, to allocate a single page far away from all others, you will need four additional pages (the fifth level is always present) for the page-tables, and four memory accesses to look them up before you get to the data. In the R1000, you present the address you want on the bus, the memory board (think: DIMM) looks that address up in its tag-ram to see if it is present, completes the transaction or generates a memory fault, all in one single memory cycle, always taking the same time.
- gpderetta 4y ago
  The problem is that there is a limit on how fast you can make the look-up in hardware. Today, given the large amounts of physical memory and the high frequency that CPUs are clocked at, single cycle lookup would be impossible. In fact today CPUs already have such lookup tables in the form of TLBs as hitting the page table every time would have very high latency; still TLBs cannot cover the whole address space and still need multi-level structures even for a subset of it. Single Address Space OSs are an option, but it means that you are restricted to memory safe languages, it is very vulnerable to spectre-like attacks, and any bug in the runtime means game over.
  - trasz 4y ago
    >Single Address Space OSs are an option, but it means that you are restricted to memory safe languages CHERI works just fine for enforcing memory protection within an address space.

cmrdporcupine 4y ago

"We need to keep in mind, the DRAM ICs themselves have a hierarchy with latency trade-offs" Yes this is the thing -- I'm not a hardware engineer or hardware architecture expert, but -- it seems to me that what we have now is a set of abstractions presented by the hardware to the software based on a model of what hardware "used to" look like, mostly what it used to look like in a 1970s minicomputer, when most of the intensive key R&D in operating systems architecture was done. One can reasonably ask, like Mr Kamp is, why we should stick to these architectural idols at this point in time. It's reasonable enough, except that the alternative of heterodox, alternative architectures is also heterogenous -- new concepts that don't necessarily "play well with others." All our compiler technology, all our OS conventions, our tooling, etc. would need to be rethought under new abstractions. And those are fun hobby or thought exercises, but in the real world of industry, they just won't happen. (Though I guess from TFA it could happen in a more specialized domain like aerospace/defence) In the meantime, hardware engineering is doing amazing things building powerfully performing systems that give us some nice convenient consistent (if sometimes insecure and awkward) myths about how our systems work, and they're making them faster every year.

bentcorner 4y ago
Makes me wonder if 50 years from now we'll still be stuck with the hardware equivalent of the floppy disk icon, only because retooling the universe over from scratch is too expensive.
nine_k 4y ago
As they say, C was designed for the PDP-11 architecture, and modern computers are forced to emulate it, because the tools to describe software (languages and OSes) which we have can't easily describe other architectures. There were modern semi-successful attempts though, see PS3 / Cell architecture. It did not stick though. I'd say that the modern heterodox architecture domain is GPUs, but we have one proprietary and successful interface for them (CUDA), and the open alternatives (openCL) are markedly weaker yet. And it's not even touching the OS abstractions.
- aap_ 4y ago
  > As they say, C was designed for the PDP-11 architecture Not really though. A linear address space was not particularly specific to the PDP-11. The one point where C really was made to fit the PDP-11 was the addition of a byte datatype (aka char), but the PDP-11 wasn't unique in that regard either.
  - nine_k 4y ago
    PDP-11 wasn't unique. To the contrary, it had many typical features. - Uniform memory, cache memory is small, optional and transparent. - A single linear address space; no pages, stack in the same RAM as data. - A single CPU, with a single scalar ALU, and completely in-order execution; no need for memory barriers. A typical modern machine larger than an MCU has several level of memory hierarchy which affect performance enormously, the physical RAM is mapped all over the address space, several execution units process data in parallel and often out of strict order, there are many variants of vector (SIMD) instructions, and usually a whole vector co-processor ("graphics card"). This breaks many of the assumptions that C initially ha made, and hardware tries hard to conceal the memory hierarchy (well, your OS may allow you to schedule your threads to the same NUMA domain), to conceal the parallel execution, to conceal the memory incoherence between processing nodes, etc. Well, you sort of can make the compiler infer that mean a vectorized operation, or use an intrinsic. In my eyes, the C's assumptions about hardware show their age, and also hold the hardware back.

mikepavone 4y ago

> That statement has to be coming with some hidden caveats. 64 bits of address space is crazy huge so it's unlikely the entire range was even present. If only a subset of the range was "instantly" available, we have that now. Turn off main memory and run right out of the L1 cache. Done. So I did some digging around for documentation about this machine and it looks like it puts the upper 54-bits of the address through a hash function to select an entry in a set associative tag RAM which is then used to select a physical page. This has the possibility for collisions, but it can get away with that because RAM is just a cache for disk contents. Certain parts of the address technically mean something, but apart from leveraging that in the design of their hash function it has no real relevance to the way the hardware works. This scheme would work with linear 64-bit addresses just fine with an appropriate hash implementation. Basically all that's happening here is that the TLB is large enough to have an entry for reach physical page in the system and a TLB miss means you have to fetch a whole page from disk rather than walking a tree of page tables in memory. I think the other thing going on here is that the R1000 is a microcoded machine from the 80s with no cache (well unless you're counting main RAM as cache, so it probably has a relatively leisurely memory read cycle which makes it more straightforward to have a very large TLB relative to the size of main memory. There's no magic here and no lessons for modern machines when it comes to how virtual address translation is done

phkamp 4y ago
You are right that there is no lessons for "modern machines" as we build them now. But that is precisely my point: Maybe there are better ways to build them ?
- mikepavone 4y ago
  What I mean is that the R1000 memory architecture is not fundamentally different from modern hardware in a way that seems to solve any modern design problems. The tag RAM is functionally equivalent to the TLB on a modern CPU, but it's much larger relative to the size of the RAM it's used with. The 2MB memory boards described in US Patent 4,736,287 (presumably an earlier version of the 32MB boards present in the R1000/s400) have a whopping 2K tag RAM entries. This is the same size as the 2nd level data TLB in Zen 2 which is supporting address lookup for a much larger main memory. If you were to try and make a modern version of the R1000 architecture you're going to run into the same size vs speed tradeoffs that you see in conventional architectures. The server oriented Rome SKus of Zen 2 support 4 TB max RAM. Even if you bump the page size to 4MB, you still would need 1M TLB/tag RAM entries to support that with an R1000-style implementation.

phkamp 4y ago

The entire address space (64 address bits, addressing bits, so "only" 61 bit addresses for bytes, but also 3 "kind" bits, separating code/data/control etc.) were available at all times. The crucial point is that the RAM wasn't laid out as a linear array, but as a page-cache. In a flat memory space, to allocate a single page far away from all others, you will need four additional pages (the fifth level is always present) for the page-tables, and four memory accesses to look them up before you get to the data. In the R1000, you present the address you want on the bus, the memory board (think: DIMM) looks that address up in its tag-ram to see if it is present, completes the transaction or generates a memory fault, all in one single memory cycle, always taking the same time.

gpderetta 4y ago
The problem is that there is a limit on how fast you can make the look-up in hardware. Today, given the large amounts of physical memory and the high frequency that CPUs are clocked at, single cycle lookup would be impossible. In fact today CPUs already have such lookup tables in the form of TLBs as hitting the page table every time would have very high latency; still TLBs cannot cover the whole address space and still need multi-level structures even for a subset of it. Single Address Space OSs are an option, but it means that you are restricted to memory safe languages, it is very vulnerable to spectre-like attacks, and any bug in the runtime means game over.
- trasz 4y ago
  >Single Address Space OSs are an option, but it means that you are restricted to memory safe languages CHERI works just fine for enforcing memory protection within an address space.