NDPage: Efficient Address Translation for Near-Data Processing Architectures via Tailored Page Table

Near-data processing is a promising technique to alleviate the memory wall in data-intensive applications [26, 15]. By placing the computing unit (referred to as an NDP core) near the main memory, NDP cores can access data with low latency and high throughput. Figure 1 shows a typical NDP architecture based on 3D-stacked memories like the Hybrid Memory Cube (HMC) [10] and HBM [19, 20]. In this architecture, NDP cores are placed in the logic layer of the 3D-stacked memory. An NDP core typically has a shallow L1 cache due to two reasons: (1) a strictly limited power and area budget in the logic layer, and (2) the memory access in NDP applications usually exhibits low data locality, which cannot benefit from deep cache hierarchies [29, 6]. Apart from that, to support virtual memory, an NDP core incorporates a memory management unit (MMU), which will be discussed in Section II-B.

Virtual memory is a fundamental concept in computer systems, designed to provide applications with the illusion of having unlimited memory [12, 4]. This abstraction is crucial for enabling several key functionalities in computing systems, such as process isolation, data sharing, and memory protection. To support these functionalities, address translation is essential for mapping virtual addresses to corresponding physical addresses. The page table stores the metadata for these mappings.

A commonly used page table mechanism is the radix page table [13]. In x86-64 systems, when a virtual address needs to be mapped to a physical address, the operating system allocates memory for the page tables at each level only if they do not already exist. This involves allocating a 4KB page frame for each new table required. The flexibility provided by radix page tables results in significant space savings, which is one of their major advantages. Figure 2 depicts the address translation based on a 4-level radix page table in x86-64 systems. The OS divides the higher 36 bits of the virtual address into four parts and executes four sequential memory accesses to page tables from level 4 to level (PL4 - PL1) to obtain the physical frame number (PFN).

To avoid frequent access to the main memory for the page tables, virtual memory systems usually adopt the MMU hardware to accelerate address translation. As shown in Figure 3, an MMU has two main components: (1) TLB, which caches recently used address translations. (2) PTW, which initiates a page table walk upon a TLB miss, searches for PTEs in the memory hierarchies including the cache, and finally obtains the corresponding physical address.

We conduct an analysis of PTE access by examining the cases of address translation on a 4-core NDP system. Firstly, we observe that the TLB miss rate reaches 91.27%, and 65.8% of the memory accesses are caused by PTEs. Thus, a significant amount of PTE accesses overwhelms the memory system, starting with the cache hierarchies. We evaluate the L1C miss rate of metadata in 4-core NDP systems. As Figure 7 shows, the blue bar demonstrates that the average PTE miss rate in the L1 cache reaches 98.28%. We conclude that irregular PTE access cannot effectively utilize the cache in NDP systems. What’s worse is that excessive PTE misses will lead to an increase in normal data misses. As Figure 7 shows, comparing the green bars and orange bars, we observe that the L1C miss rate of the normal data in the NDP 4-core system reaches 35.89%, which is 1.37x higher than the 26.16% in the ideal NDP 4-core system with no address translation. As a result, the main memory access caused by PTE in the NDP system increases by 200.4x compared to the CPU 4-core system. To conclude, our first key observation is that the memory access pattern of PTE metadata in an NDP system is extremely irregular, which results in the following: (1) the memory access of metadata cannot benefit from the cache, and (2) significantly pollutes the cache, negatively impacting the performance of accessing normal data.

The key benefit of the four-level radix page table mechanism in the conventional system is its flexibility, which results in memory space savings, i.e., the next level of the page table is allocated only when needed. However, we conduct a study on the occupancy of four-level page tables in the NDP 4-core system.

As Figure 8 shows, the average occupancy rate of the L2 and L1 page tables reaches 98.24% and 97.97%, respectively, significantly higher than 0.43% and 3.12% of L4 and L3. In other words, the full PL2 and PL1 are always needed in NDP systems. The flexibility of the 4-level radix page table is overkill in the last 2 levels of fully occupied page tables, and the additional levels increase sequential accesses to the page tables. To conclude, our second key observation is that in NDP systems, fully occupied L2 and L1 page tables negate the necessity of maintaining the 4-level radix-tree structure between them.

These two key observations lead us to two ideas for designing efficient address translation mechanisms for NDP systems.

NDPage implements a cache-bypass mechanism only for metadata, i.e., the PTEs, in NDP systems. This mechanism arises from the observation that highly irregular metadata cannot benefit from the cache in NDP systems, as analyzed in Section IV-A. Therefore, NDPage bypasses the PTEs from the NDP cache, directly accessing the main memory. The hardware implementation of the cache-bypass mechanism is based on well-established techniques [25, 9]. We reference these prior works to implement the technology in the hardware design of NDP systems. The key focus is on the careful recognition and selection of data to bypass. We modify the operating system to mark the regions of the PTEs, which is essentially a 4KB memory, i.e., $2^{9}$ entries $\times$ 64 bits/entry, in the 4-level radix-tree page table design. Since 4KB is divisible by 64B, which is the conventional cache line size, making these regions 64B aligned ensures this mechanism does not affect normal data accesses within the cache. In the NDPage design, for each access to the metadata, the OS triggers a special load instruction to look up the PTEs, depending on the architecture. For instance, the x86 ISA provides the PFLD (pipelined floating-point load) [2] instruction to issue the memory request that bypasses the cache system. The cache bypassing violates the assumption of inclusion with inclusive multi-level cache hierarchies [24]. However, since there is only one level of cache in the NDP systems, the violation of the cache bypassing to the inclusive multi-level caches doesn’t exist.

The conventional radix page table is organized as a 4-level structure for high flexibility. However, as shown in Section IV-B, the 4-level structure is excessive for data-intensive NDP applications since the last two levels of the page table are nearly fully occupied. Based on this observation, we propose a flattened L2/L1 page table. Flattening uses the radix nature of the page table to naturally merge levels into single, larger levels, resulting in a shallower tree. We merge the last two levels of the page table to reduce the number of sequential memory accesses for each PTW from 4 to 3. Figure 9 illustrates the address translation in NDPage with the flattened L2/L1 page table. By combining the L2 and L1 levels, a single 2 MB flattened node replaces each L2 node and its 512 L1 child nodes, encompassing all $2^{9}\times 2^{9}=262,144$ entries. Although this increases the size of individual page table entries, the overall impact is minimal due to the small fraction of the page table relative to the actual data size. To support flattened page tables, minor modifications are needed in the system architecture. Specifically, control registers and page table entries require a single bit to indicate flattened nodes. The hardware page walker uses these bits to determine the appropriate index bits from the virtual address for each level. To implement the flattened page tables, we modify the encoding of the virtual address bits for indexing. Each flattened L2/L1 table structure comprises $2^{9}\times 2^{9}=262,144$ entries, fitting into a single 2 MB page. Therefore, as shown in Figure 9, 18 bits are required for indexing each combined L2/L1 table.

The Page Walk Cache (PWC) [3] is a small dedicated cache in modern processors that accelerates address translation by storing recently accessed Page Table Entries (PTEs). In a modern processor, each level of the page table has its own PWC. We also implement the PWC in the NDPage design to further optimize PTE access. We observe that the hit rates of the PWCs in L4 and L3 are nearly 100% and 98.6%, respectively, while the hit rates in L2 and L1 are relatively low, averaging 15.4% in our evaluation. This result is consistent with previous works [22, 3, 21], which also report very high PWC hit rates in L4 and L3 and low hit rates in L2 and L1. We conclude that NDPage flattens the last two levels of the page table while retaining the advantages of PWCs in L3 and L4. By restricting the high PWC miss rate to a flattened PL2/PL1, instead of two separate PL2 and PL1 levels, NDPage significantly reduces memory accesses.

Figure 11 demonstrates the address translation and corresponding data access flow in an NDP system with NDPage. The core initiates a virtual-to-physical address translation via the MMU, which first incurs a TLB lookup. When a TLB miss occurs , the MMU triggers a Page Table Walk (PTW) to look up the page tables in the main memory. Unlike normal data accesses, the metadata accesses caused by the PTW bypass the first-level cache and begin directly at the main memory . The PTW requires three sequential page table accesses: first to the PWCs, and if there is a miss, then to the main memory, progressing from the L4 page table to L3, and finally to the flattened L2/L1 page table . In the end, the page table walker fetches the physical address . Once the address translation is complete, the NDP core initiates the normal data access using the physical address at the L1 cache , and if the L1 cache misses, it proceeds to access the main memory .