4 ms·

I wonder how the PLB can be fast. You have a dictionary from byte range to permission. This is harder than TLBs, which map a relatively large granule where you

I wonder how the PLB can be fast. You have a dictionary from byte range to permission. This is harder than TLBs, which map a relatively large granule where you can form a search key by just extracting the top bits from the virtual address. Intel MPX has a similar protection model, and that introduces a lot of overhead (of course it is bolted onto an existing arch and it wasn't a high priority feature).

willvarfar 9y ago
The protection entries have ranges. The bounds are in bytes, but the range can be massive. Imagine you load a 7MP image which takes, say, 21MB of RAM. That would be 5184 4K pages in a classic TLB. In the Mill's PLB, that whole part of the address space can be in a single protection entry. Then, there's a big difference from how things can be organised in software vs hardware. The hardware PLB has some number of entries, and it will check all those entries in parallel.
- neerajsi 9y ago
  Yes, you will have a CAM, but the CAM for a PLB would likely be more expensive than a TLB, right? And today's TLBs are only a few hundred entries for the first level. The PLB would seem to necessitate many cycles for a load, longer cycle times, or a high power CAM. Even if you could make address queries quickly by replicating ranges based on some graularity, invalidating the PLB becomes expensive on a grant revocation. I understand that Itanium was forced into a low frequency, high power L1 cache by being at a similar in order statically scheduled design point, where you need loads to be fast in order for a compiler to be able to come up with a reasonable static schedule. Unless there's some really nice idea out there that's radically different from TLBs as they are today, I bet PLBs will be the major limiter of performance for general purpose code.
  - willvarfar 9y ago
    Each protection entry is has a lower and upper bound. The entry can cover something as small as a single byte, or as big as the whole address space or anything inbetween. It is just a normal bounds compare to see if each entry covers the access, and the PLB has as long as the top-level cache access takes to do the checks. So the PLB misses far far less often than a conventional TLB.
    - hilmipilmi 9y ago
      TLBs index a tag with the higher bits and compare one retrieved value for equality only. A PLB with arbitrary resolution would need to do 2 subtractions for the 2 compares and do that for all active entries in parallel. That is, for every simple load/store in a 16 entry PLB you'd need to do 32 subtractions! Unless you come up with a novel scheme to handle this your chip will get hot. Maybe you can reconstruct the indexing TLB scheme on the fly in hardware or something like that, or have an special purpose embedded Cortex-M3 that recreates an efficient lookup structure for the MILL :-). And no, a 64 bit subtraction is not one clock cycle when you run at 1ghz.
      - willvarfar 9y ago
        The entry contains an upper and lower bound, and requires two comparisons but no subtractions.
  - deepnotderp 9y ago
    Modern L2 TLBs have something like 1024 entries.
  - igodard 9y ago
    There are dededicated Well-Known-Regions for code, stack, globals and TLS that catch the great majority of memory references. The PLB is only consulted when we miss in the WKRs. What's not in the WKRs? MAP_SHARED mmap()s. How many of those are in your program? How often do you access one for the first time or after long enough that the entry has been evicted from the PLB? Like any cache, the optimal PLB size is determined by the working set. In the typical code we are seeing, the program has a couple of open files, half a dozen mmaps where the heap grew itself, and portal blocks for assorted libraries. The working sets are much smaller than a conventional TLB, and with SAS we have several cycles available in parallel with the caches. The upshot is that a PLB can be large, cool, and slow. As for the range compares, the PLB permits the same sore of address sub-setting as is done in mixed size TLBs. Think about how many bits in the typical address range differ between lower and upper bounds.

willvarfar 9y ago

The protection entries have ranges. The bounds are in bytes, but the range can be massive. Imagine you load a 7MP image which takes, say, 21MB of RAM. That would be 5184 4K pages in a classic TLB. In the Mill's PLB, that whole part of the address space can be in a single protection entry. Then, there's a big difference from how things can be organised in software vs hardware. The hardware PLB has some number of entries, and it will check all those entries in parallel.

neerajsi 9y ago
Yes, you will have a CAM, but the CAM for a PLB would likely be more expensive than a TLB, right? And today's TLBs are only a few hundred entries for the first level. The PLB would seem to necessitate many cycles for a load, longer cycle times, or a high power CAM. Even if you could make address queries quickly by replicating ranges based on some graularity, invalidating the PLB becomes expensive on a grant revocation. I understand that Itanium was forced into a low frequency, high power L1 cache by being at a similar in order statically scheduled design point, where you need loads to be fast in order for a compiler to be able to come up with a reasonable static schedule. Unless there's some really nice idea out there that's radically different from TLBs as they are today, I bet PLBs will be the major limiter of performance for general purpose code.
- willvarfar 9y ago
  Each protection entry is has a lower and upper bound. The entry can cover something as small as a single byte, or as big as the whole address space or anything inbetween. It is just a normal bounds compare to see if each entry covers the access, and the PLB has as long as the top-level cache access takes to do the checks. So the PLB misses far far less often than a conventional TLB.
  - hilmipilmi 9y ago
    TLBs index a tag with the higher bits and compare one retrieved value for equality only. A PLB with arbitrary resolution would need to do 2 subtractions for the 2 compares and do that for all active entries in parallel. That is, for every simple load/store in a 16 entry PLB you'd need to do 32 subtractions! Unless you come up with a novel scheme to handle this your chip will get hot. Maybe you can reconstruct the indexing TLB scheme on the fly in hardware or something like that, or have an special purpose embedded Cortex-M3 that recreates an efficient lookup structure for the MILL :-). And no, a 64 bit subtraction is not one clock cycle when you run at 1ghz.
    - willvarfar 9y ago
      The entry contains an upper and lower bound, and requires two comparisons but no subtractions.
- deepnotderp 9y ago
  Modern L2 TLBs have something like 1024 entries.
- igodard 9y ago
  There are dededicated Well-Known-Regions for code, stack, globals and TLS that catch the great majority of memory references. The PLB is only consulted when we miss in the WKRs. What's not in the WKRs? MAP_SHARED mmap()s. How many of those are in your program? How often do you access one for the first time or after long enough that the entry has been evicted from the PLB? Like any cache, the optimal PLB size is determined by the working set. In the typical code we are seeing, the program has a couple of open files, half a dozen mmaps where the heap grew itself, and portal blocks for assorted libraries. The working sets are much smaller than a conventional TLB, and with SAS we have several cycles available in parallel with the caches. The upshot is that a PLB can be large, cool, and slow. As for the range compares, the PLB permits the same sore of address sub-setting as is done in mixed size TLBs. Think about how many bits in the typical address range differ between lower and upper bounds.