Memory is a costly resource in computing. For example, under many VM instances in AWS (e.g., t2, t3, t3a, t4g), doubling a VM's memory size while keeping the number of vCPUs the same doubles the total hourly cost of the VM (e.g., going from a 0.5GB VM with 1 vCPU to a 1GB VM with 1 vCPU doubles the total hourly cost of the VM). Other large-scale data center operators (e.g., Facebook [1], Microsoft [2], Google [3]) also report that memory makes up a large and rising fraction of total infrastructure cost.
To increase effective memory capacity without increasing actual DRAM cost, many prior works [4], [5], [6], [7], [8], [9], [10] have explored hardware memory compression. Hardware transparently compresses DRAM content on-thefly with the memory controller evicting/writing back memory blocks to DRAM. To increase effective memory capacity (i.e., to store more values in memory), the memory controller also transparently migrates compressed data closer together to free up space in DRAM for future data. To migrate data, the memory controller takes on several OS features; specifically, memory controller maintains a dynamic, pagetable-like, fully-associative, physical address to DRAM address translation table that can map any physical address to any DRAM address; we refer to these new hardwaremanaged translation entries as Compression Translation Entries (CTEs), as they are similar to OS page table entries (PTEs). Prior works cache CTEs in the memory controller via a dedicated CTE cache, similar to the TLBs dedicated to caching PTEs.
This new dynamic physical-to-DRAM address translation increases the end-to-end latency of memory accesses, however. This translation takes place serially after the existing virtual-to-physical translation produces a physical address; if that physical address incurs an LLC miss and the LLC miss suffers from a CTE miss in the CTE cache, memory controller has to wait for the missing CTE to arrive from DRAM before knowing where in DRAM to fetch the missing data block.
This paper explores and addresses the problem of high address translation overheads that large and/or irregular workloads suffer under hardware memory compression. We note that just like how these workloads suffer from high PTE miss rates, they also suffer from high CTE miss rates. To make the matter worse, prior works migrate memory content at memory block granularity; this requires much more fine-grained address translation than existing virtualto-physical translation, which typically operates at 4KB page granularity. In general, the finer the coverage of translations, the less cacheable the translations become, and higher the translation miss rate.
A promising solution to tackle the new address translation overhead is to let hardware take on an OS-inspired approach: only save memory from cold (i.e., less recently accessed) pages without saving memory from hot (i.e., recently accessed) pages (e.g., keep the hot pages uncompressed), like OS memory compression. Saving memory only from cold, but not hot, pages can mitigate the block-level translation overhead due to saving memory from hot pages in hardware. Such an OS-inspired hardware memory compression faces two challenges, however. A) After a compressed cold page becomes hot again, migrating the page to a full 4KB DRAM location still adds another level (albeit page-level, instead of block-level) of translation for future accesses to the newly hot page. B) Only compressing cold pages requires very aggressively compressing cold pages to achieve the same total memory savings as prior works' approach of saving memory from all (both cold and hot) pages; decompressing aggressively compressed pages incurs high latency overhead (e.g., > 800ns in IBM's state-of-the-art ASIC Deflate [11]).
This paper presents Translation-optimized Memory Compression for Capacity (TMCC) to enable high performance hardware memory compression for large and/or irregular workloads. TMCC builds on the OS-inspired approach above, but addresses its two key challenges.
To address Challenge A), we make two observations. First, CTE misses typically occur after PTE misses in TLB because CTEs, especially the page-level CTEs under an OS-inspired approach, have similar translation reach as PTEs. Second, we observe page table blocks (PTBs) are highly compressible because adjacent virtual pages often have identical status bits and the most significant bits in physical page numbers are unused. As such, to hide the latency of CTE misses, TMCC transparently compresses each PTB in hardware to free up space in the PTB to embed the CTEs of the 4KB pages (i.e., either data pages or page table pages) that the PTB points to; this enables each page walk to also prefetch the matching CTE required for fetching from DRAM either the end data or the next PTB.
To address Challenge B), we take IBM's state-of-the-art ASIC Deflate design [11], which was designed for both storage and memory, and specialize it for memory. Specifically, we perform a large design space exploration across many dimensions of hardware configurations available under Deflate and across diverse workloads; the end product is an ASIC Deflate specialized for memory that is 4X as fast as the state-of-the-art Deflate when it comes to memory pages.
The contributions of this paper are as follows:
1) We are the first to tackle the address translation problem faced by large and/or irregular workloads when using hardware memory compression to improve effective memory capacity. 2) We identify CTE cache misses mostly follow TLB misses (e.g., for 89% of the time, on average). As such, we propose embedding CTEs into PTBs to enable accurate prefetch of CTEs during the normal page walks after TLB misses. 3) We are the first to specialize ASIC Deflate for memory. Our ASIC Deflate decompresses 4KB memory pages 4X as fast as the best general-purpose Deflate. We publicly release our HDL at https:// github.com/ HEAP-Lab-VT/ ASIC-DEFLATE-for-memory. 4) We compare against Compresso [6], a state-of-theart prior work on hardware memory compression; our evaluations show that for large and/or irregular workloads, TMCC can either improve performance by 14% without sacrificing effective capacity or provide 2.2x the effective capacity without sacrificing performance.
Conventional Address Translation: OS typically maps virtual addresses to physical addresses at 4 KB page granularity. OS maintains a page table for each program to map virtual pages to physical pages. CPUs incorporate a per-core translation lookaside buffer (TLB) to cache recently used page table entries (PTEs). A TLB has a limited size (e.g., 2048 entries). A TLB miss triggers the page walk. The page walk performs a sequence of memory accesses to traverse the page table. Each step in a page walk fetches a 64B block of eight PTEs; we call this block a page table block (PTB).
Hardware memory compression: Many prior works [4], [5], [6], [7], [8], [9], [10], [12], [13] have explored hardware memory compression; memory controller (MC) transparently compresses content on-the-fly with evicting/writing back memory blocks to DRAM and transparently decompresses DRAM content on-the-fly for every LLC miss.
Broadly, prior works on hardware memory compression falls under two broad categories. One body of works compress memory values to increase effective memory bandwidth [13], [14], [15], [16], [17], [18], [19], [20]. Compressing memory blocks reduces the number of memory bus cycles required to transfer data to and from memory. Another body of works use compression to increase effective memory capacity by migrating compressed blocks closer to free up a large contiguous space in DRAM for future use.
Intuitively, increasing effective capacity requires more aggressive data migration than compressing memory to increase effective bandwidth. The former carries out fullyassociative data migration in DRAM. In comparison, the latter either keeps memory blocks in place after compression [13], [17], [20] or migrates compressed memory blocks to a neighboring location in DRAM [19].
To migrate data transparently in hardware, prior works on increasing effective capacity borrow two OS memory management features and implement them in hardware.
First, prior works borrow from OS' free list; MC maintains a linked-list-based Free List [4], [6] to track free space in DRAM at a coarse (e.g., 256B [4] or 512B [6]) granularity called chunks. When detecting that sufficient slack currently exists within the space taken up by a page, prior works repack the page's content closer together to free up chunk(s) to push to (i.e., track at the top of) the Free List. When a page becomes less compressible and cannot fit in its currently allocated chunks, prior works pop a chunk from (i.e., stop tracking it in) Free List to allocate the chunk to the page.
Second, prior works borrow from OS page tables; MC maintains a dynamic, page-table-like, fully-associative, physical address to DRAM address translation table that can map any physical address to any DRAM address. We refer to these new hardware-managed translation entries as Compression Translation Entries (CTEs), as they are similar to OS page table entries (PTEs). MC stores the CTEs in DRAM as a linear 1-level table. Each CTE (a.k.a, metadata block [6], [4], [8] in prior works) contains individual fields to track the DRAM address of individual 64B blocks within a group of blocks. This is because compression ratio varies across blocks; as such, after saving memory through repacking, different blocks start at irregular-spaced DRAM addresses, instead of regular-spaced DRAM addresses like current systems without hardware compression. Prior works cache these CTEs in a dedicated CTE cache, similar to TLBs dedicated to caching PTEs.
Large workloads (i.e., ones with large memory footprint) are ubiquitous in today's computing landscape [21]; examples include graph analytics, machine learning, and inmemory databases [22]. However, large workloads suffer from high address translation overhead because their PTEs are too numerous to fit in TLBs. Similarly, the PTEs of workloads with irregular access patterns also cache poorly in TLBs. As such, many works [23], [24], [25], [26], [27], [28] have explored how to improve address translation for large and/or irregular workloads in the context of conventional systems without hardware memory compression.
This paper explores the problem of high address translation overheads that large and/or irregular workloads suffer under hardware memory compression for capacity. We note that just like how they suffer from high PTE miss rates in TLBs, they also suffer from high CTE miss rates under hardware memory compression. Making the matter worse, prior works on hardware memory compression translate from physical to DRAM addresses at memory block granularity, instead of page granularity. It is well-known that the finer the translations, the higher the translation miss rate.
Take for example Compresso [6], the state-of-the-art hardware memory compression for capacity. To perform physical-to-DRAM address translation for a 4KB range of physical addresses, Compresso requires a 64B CTE; each CTE records per-block metadata to translate individual blocks within the 4KB range. Overall, each CTE in Compresso costs 8X as much space as a PTE, which is only 8B. Compresso caches CTEs in a 64KB CTE cache in MC; as such, the CTE cache reaches only 64KB/64B = 1K pages. Because TLBs typically have a similar (e.g., 1.5K) number of entries, we expect CTE misses to be similarly frequent as TLB misses.
Figure 1 shows total TLB misses and CTE misses normalized to the number of last-level cache (LLC) misses; we show TLB misses normalized to LLC misses, instead of 1000 instructions, to more closely compare with CTE misses. Figure 1 includes all workloads used by recent prior works [23], [24] on improving address translation that we know how to run in Gem5 [29]. When evaluating IBM's GraphBIG [30], we use a Facebook-like social media graph dataset (see datagen-8 5-fb [31]) and multi-threading. On average across all workloads, CTE miss rate is higher than TLB miss rate (i.e., 34% vs 30%). We were initially surprised by this finding because the CTE misses in Figure 1 only include CTE misses for fulfilling LLC misses. By closer inspection, we find CTEs miss more often because all regular memory requests, including requests for PTBs themselves from the page walker, require accessing CTEs; TLB misses, however, only occur for data (and instruction).
To reduce CTE miss rate, one possible solution is to make the CTE cache bigger. We evaluate CTE hit rate using a 256KB metadata cache. Figure 2 shows an average hit rate of 70.5% for a 256KB metadata cache; this means it still misses 1 -70.5% = 29.5% of the time. As such, making CTE cache bigger does not effectively reduce CTE miss rate.
Another possible solution is to use LLC as a victim cache for CTEs evicted from the CTE cache. Figure 2 shows that even when caching in LLC, a high 21% of
A promising solution to tackle the address translation overhead under hardware memory compression is to let hardware take on yet another OS feature: only save memory from cold (i.e., less recently accessed) pages without saving memory from hot (i.e., recently accessed) pages (e.g., keep the hot pages uncompressed), like OS memory compression. When hardware does not save memory from hot pages, hardware can lay out hot pages' memory blocks regularly either like uncompressed memory or like compressing memory for expanding effective bandwidth (see Section II). For hot pages, which are most critical to performance, doing so helps to avoid the overhead of fine-grained block-level translation.
Specifically, avoiding block-level translation can significantly increase the translation reach of each CTE and, therefore, significantly reduce CTE cache miss rate. Consider for example Compresso; each 64B CTE cacheline only translates for one 4KB physical page due to storing a translation for every block in the page. After switching over to page-level translation like OS, each 64B CTE cacheline can translate for eight pages, like how a PTB translates for eight virtual pages. For the workloads in Figure 1, we find switching from block-level translation to pagelevel translation eliminates 40% of CTE misses, on average, while simply quadrupling the size of the CTE cache only reduces CTE miss rate by 13% (from 34% down to 29.5%, see Section III). Page-level translation is so effective due to increasing effective CTE cache size by 8X and better exploiting spatial locality (i.e., fetching from DRAM a CTE block that translates at page level equates to fetching eight adjacent CTE blocks that translate at block level).
OSes also compress memory [34], [35], [36], [37], [38]. OS does so in many data centers (e.g., Google Cloud [3], IBM Cloud [39], Facebook [1]).
In the eyes of an architect, OS memory compression manages memory as a 2-level exclusive hierarchy: (i) Memory Level 1 (ML1) stores everything uncompressed, (ii) Memory Level 2 (ML2) stores everything compressed. Accesses to ML1 are overhead-free (e.g., incurs no translation overhead). Accesses to a compressed virtual page in ML2 incurs a page fault to wake up OS to pop a free physical page from ML1's free list and migrate the virtual page to the page.
Because ML1 provides no gain in effective capacity, providing significant gain in overall effective capacity requires ML2 to aggressively save memory from the pages ML2 is storing. As such, ML2 uses aggressive page-granularity compression algorithms, such as Deflate [11]. ML2 also keeps many free lists, each tracking sub-physical pages of a different size, to store any compressed virtual page in a practically ideal matching sub-physical page [40], [41].
ML2 gracefully grows and shrinks relative to ML1 with increasing and decreasing memory usage. When everything can fit in memory uncompressed, ML2 shrinks to zero bytes in physical size so ML1 can have every physical page. Specifically, when ML2's free list(s) get large (e.g., due to reducing memory usage), ML2 donates free physical pages from its free list(s) to ML1. OS also grows ML1 free list, when it gets small, by migrating cold virtual pages to ML2. Migrating a virtual page to ML2 shrinks one of ML2's free lists. If a ML2 free list gets empty, ML1 gives cold victim physical pages to ML2 (i.e., track them in ML2 instead of ML1), so that ML2 can compress the virtual pages currently in the victim pages to free space in the victims to grow ML2's free list(s).
Hardware memory compression can also be enhanced to manage DRAM as ML1 and ML2 like OS memory compression, with simple adaptations.
One adaption is to simplify CTEs: instead of finely tracking individual memory blocks, track a single 4KB page worth of content collectively at coarse granularity, just like a PTE. Specifically, each CTE now only records the starting DRAM address of an entire page, without recording any individualized tracking for every block in the page.
Another adaptation is to extend prior works' Free Lists to ML1 and ML2. Figure 3a shows a Free List in prior work [6], [4]. Making it work for ML1 involves increasing chunk size to 4KB (see Figure 3b). ML2 requires multiple Free Lists, each tracking free equally-sized subchunks. The purpose of each sub-chunk is to store an entire compressed page. Equally-sized sub-chunks can be created fragmentation-free by evenly dividing a group of M interlinked chunks, which we call a super-chunk, into N sub- [4]; it stores a pair of pointers in free chunks 'for free' to implement a doubly linked list to track free 256B chunks. (b) ML1 Free List, which tracks free 4KB chunks. (c) An ML2 Free List that tracks 1.5KB free sub-chunks; it tracks all super-chunks containing at least one free 1.5KB sub-chunk. chunks, where N > M and N ,M are chosen to minimize (4KB • M )modN . Figure 3c shows an example ML2 Free List for tracking 1.5KB sub-chunks. When all sub-chunks in a super-chunk becomes free (e.g., the compressed pages they store have all migrated to ML1 over time), the chunks in the super-chunk are returned to ML1's Free List. The superchunks towards the bottom of an ML2 Free list naturally tend to be emptier than super-chunks towards the top. This is because A) ML2 always allocates sub-chunks from the top of ML2 Free List(s) to handle migration to ML2 and B) ML2 tracks at the top of ML2 Free List(s) super-chunks that transition from having no free sub-chunk to having one free sub-chunk (e.g., after a page migrates to ML1).
Beside adapting prior works' CTEs and Free Lists, a new necessary component is a new doubly linked list to track the recency of pages stored in ML1; we call them the Recency List. Besides the list pointers, each Recency List element tracks a page in ML1 by recording the page's PPN (i.e., physical page number). The head and tail of Recency List track the hottest and coldest pages in ML1, respectively. ML1 updates the Recency List for a small (i.e., 1% of) fraction of randomly chosen accesses to ML1; when updating the Recency List for an access to ML1, ML1 moves the accessed page's list element to the hot end of the list. ML1 evicts victims from the cold end of Recency List. In the uncommon case that the victim turns out to be incompressible, ML1 retains the page in ML1; ML1 simply removes the page from the Recency List to avoid uselessly compressing it again. As subsequent writebacks may increase a page's compression ratio, ML1 adds an incompressible page back to the Recency List at 1% probability after a writeback to an incompressible page. ML1 can record whether a page is incompressible via an 'isIncompressible' bit in each CTE.
While ML1 is uncompressed in OS, in hardware, ML1 can also be compressed to increase effective memory bandwidth. One of the many prior memory compression techniques for improving bandwidth (e.g., TMC [19]) can be readily applied to ML1.
Such an OS-inspired hardware compression faces two challenges, however. A) After compressed cold pages are accessed again, migrating them from ML2 to ML1 still adds another level (albeit page-level, instead of block-level) of translation for future accesses to all pages in ML1. B) Only compressing cold pages require very aggressively compressing cold pages to achieve high overall memory saving; decompressing aggressively compressed pages for every access to ML2 is slow. We describe these challenges in detail below.
Performance Challenge under ML1: In OS memory compression, accesses to ML1 incur no overhead. When OS migrates a virtual page from ML2 to a free physical page in ML1, OS directly records the new physical page's PPN in the virtual page's PTE. As such, future accesses to the virtual page in ML1 requires the same amount of translation as a system that turns off memory compression.
However, when hardware memory compression migrates a page from ML2 to ML1 after a program accesses the page, hardware cannot directly update the program's PTE because PTEs are OS-managed. Raising an interrupt to ask OS to update the PTE for hardware would defeat the main purpose of hardware memory compression -avoid the costly page faults under OS memory compression. Instead, hardware tracks the page's new DRAM location through a new layer of translation (i.e., through CTEs). As such, hardware has to use the PPN recorded in the page's PTE to indirectly access a CTE to obtain the data's DRAM address; this requires a new level of serial page-level translation (see Figure 4b), unlike ML1 accesses under OS compression (see Figure 4a). For the workloads in Figure 1, this added page-level translation still causes 20% of LLC misses to suffer from CTE misses.
As such, how to address the latency overhead due to the page-level translation for ML1 in hardware is a challenge. Performance Challenge under ML2: The key latency bottleneck for ML2 is decompressing aggressivelycompressed pages when they are accessed in ML2. OS typically use aggressive page-granularity compression, such as Deflate, to save memory in ML2. For decades, Deflate has been used across many application scenarios (e.g., file systems, network, memory). Due to Deflate's high and robust compression ratio, IBM integrates ASIC Deflate into Power9 and z15 CPUs [11]. This state-of-the-art ASIC Deflate achieves a peak throughput of 15 GB/s for large streams of data [11]. However, it has a setup time (T 0 [11]) of 650-780ns for each new independent input (e.g., a new independent page). This delay can be crippling for small inputs, such as 4KB memory pages. This long delay also limits the bandwidth for reading and writing 4KB compressed pages to only 4 GB/s and 2 GB/s per module, respectively. This amounts to a mere 16% and 8% bandwidth of a DDR4-3200 memory channel. While long latency and low bandwidth is okay for ML2 accesses under OS compression, where overall performance is limited by software overheads, they are inadequate for hardware memory compression.
As such, how to address the high decompression overhead for ML2 accesses in hardware, without significantly sacrificing ML2's compression ratio, is a challenge.
We propose Translation-optimized Memory Compression for Capacity (TMCC) to enable fast hardware memory compression for large and/or irregular workloads. TMCC builds on the OS-inspired approach in Section IV, but effectively addresses the latency overheads for both ML1 and ML2.
To effectively address the problem of long-latency serial translation for accesses to ML1 during CTE misses, TMCC parallelizes the data access with the corresponding CTE access; instead of the conventional approach of waiting for the missing CTE to arrive from DRAM and then use it to calculate the DRAM address to serve the L3 miss, TMCC carries out both DRAM accesses in parallel. This effectively hides the CTE miss latency from the total DRAM access latency for serving an L3 miss request.
To parallelize DRAM accesses for CTE and for the actual L3 miss, we make two enabling observations. 1) Observations: First, we observe CTE misses typically occur immediately after PTE misses. This is also true for the OS-inspired approach to hardware memory compression in Section IV, where each 8B CTE translates for a 4KB page. Similarly, each level N+1 PTE (e.g., L2 PTE) tracks 4KB worth of level N PTEs, while each L1 PTE tracks 4KB of data (or instructions). Due to CTEs and PTEs providing the same translation reach, accesses that cause PTE misses in TLB will likely also cause CTE misses in CTE cache. Figure 5 shows that 89% of all CTE misses for LLC miss requests are due to LLC misses related to a TLB miss (i.e., page walker misses in LLC and/or the subsequent data/instruction miss in LLC).
Second, we observe each page table block or PTB (i.e., a 64B worth of PTEs) is highly compressible because, intuitively, adjacent virtual address ranges often have identical status bits; moreover, many bits in PPN are also identical.
For example, each 8B PTE in x86 consists of 24 status bits that record various permissions and a 40-bit PPN [42]. Figure 6 shows the fraction of L1 page table blocks (i.e., storing L1 PTEs) and L2 page table blocks (i.e., storing L2 PTEs) that have identical status bits across all PTEs within the same PTB; it is 99.94% and 99.3%, on average, for L1 and L2 page table blocks. Meanwhile, many of the most significant bits in the PPN are identical, depending on the actual amount of DRAM currently installed in the system. For example, in a machine with 4TB of OS physical pages, the most significant 10 bits of the PPN are almost always identical (e.g., all zeroes or reused as identical extended permission bits by Intel MKTME [43]).
2) Key Idea: Based on our observations, we propose transparently compressing each PTB in hardware to free up space in the PTB to embed the CTEs of the 4KB pages (i.e., either data pages or page table pages) that the PTB points to; this enables each page walk access to also prefetch the matching CTE required either for the next page walk access (i.e., to the next PTB) or for the actual data (or instruction) access after the walk.
Figure 7c shows a compressed PTB. For each PTE in the PTB, TMCC opportunistically stores in the compressed PTB a CTE responsible for translating the PPN that the PTE contains into a DRAM address. As such, as a page walker fetches a PTB, the CTE for the next access (i.e., either the next page walker access or the end data access) becomes available at the same time as the PPN for the next access. Directly having in the PTB the CTE needed for the next access eliminates the need to serially fetch and wait for CTE to arrive from DRAM before knowing the next DRAM address to access.
A practical challenge is that after migrating a page (e.g., from ML1 to ML2 after the page becomes cold), the corresponding CTE embedded in the page's PTB should be updated. However, hardware has no easy way to use the PPN of the migrating page to find/access the page's PTB(s). TMCC addresses this challenge by lazily updating the CTE in the PTB later around when the PTB is naturally accessed by the page walker, instead of updating it at the time of migrating the page. However, this means that for the first page walker access to the PTB after migrating one of the pages that the PTB points to, the corresponding CTE is out-of-date. To ensure correctness, TMCC also accesses the correct CTE in DRAM (or in CTE cache) in parallel to verify the correctness of the DRAM access. Figure 8 compares and contrasts how TMCC serves an LLC miss that also misses in CTE cache with the baseline approach. Figure 9 provides an architectural overview of TMCC. 3) Detailed Actions Following a TLB Miss: After a TLB miss for instruction X, if the page walker accesses L2, L2 buffers into a temporary buffer every CTE within the accessed PTB. We call this temporary buffer the CTE Buffer. CTE Buffer inserts each CTE as a new key value pair. The key is the PPN that the PTE records; the value consists of the embedded CTE for the PPN and the physical address of the PTB holding the PTE (See Figure 10).
When L2 receives another page walker access or the end data (or instruction) access for instruction X (L2 need not know the access is actually for instruction X), L2 extracts the PPN from the received request to lookup the CTE Buffer to obtain the CTE for MC to translate the PPN. If the request misses in L2, L2 forwards the request to LLC, as usual, and piggybacks the CTE in the request. If LLC also misses, LLC The uncommon case is that the request has no embedded CTE; as such, MC takes the same actions as prior hardware memory compression designs -access CTE in DRAM and then serially access DRAM to service the LLC miss.
The common case is that the request has an embedded CTE; MC uses the CTE to speculatively translate the LLC's request to DRAM address to access DRAM in parallel with accessing the actual CTE in DRAM. Figure 11 shows this common case. When both DRAM accesses complete, MC checks whether the correct CTE from DRAM matches the embedded CTE. In the common case that they match, MC can directly respond to LLC. In the uncommon case that they mismatch, MC uses the correct CTE to translate the LLC request and re-access DRAM (see Figure 8c). Also in both cases, MC piggybacks the correct CTE in the response back to LLC and L2. When receiving a response, L2 extracts the PPN from the response to look up CTE Buffer. On CTE Buffer hit, if the CTE Buffer entry has a mismatching CTE or has no CTE, L2 stores the correct CTE into the entry and uses the PTB physical address that the element records to fetch and update the PTB with the incoming CTE.
Embedding CTEs in PTBs not only reduces the latency to fetch data/instruction from memory at the end of a page walk, but can also reduce the latency to fetch PTB blocks from memory. In other words, embedding CTEs in PTBs can benefit the entire page walk (see (iii) in Figure 12a).
Embedding CTEs in PTBs also benefits 2D page walks for VMs. Each 2D page walk (see Figure 12b) requires multiple regular page walks that only use host PTBs, just like a page walk for a native application. As such, TMCC carries out the same actions during each page walk within a 2D page walk as a regular page walk.
4) Details on Tracking Compressed PTBs: To track which blocks in DRAM are encoded via the compressed PTB encoding (see Figure 7c), each CTE contains a bit vector of 32 bits; each bit tracks whether two adjacent blocks in a page are both currently using the compressed PTB encoding. When one block in a pair of adjacent blocks undergoes an encoding change (i.e., from uncompressed to compressed or vice versa), the MC enacts the same encoding change for the other block when it writes to memory the original block with changed encoding. Figure 13 shows the internal layout of a CTE.
To clarify, compressing memory blocks using our PTB encoding only affects the encoding of individual memory blocks in a page in ML1, without affecting their DRAM location; the 32-bit vector only serves to record the format of the blocks in each page in ML1, and not to migrate the blocks. TMCC does not perform any block-level translation, even for compressed PTBs. After fetching from DRAM a memory block encoded in compressed PTB format, MC replies the block back to LLC in compressed format. Under TMCC, the only compressed content on-chip are PTBs (i.e., cachelines accessed by the page walker). Every L2 and L3 cacheline has a new data bit to record whether the cacheline is compressed. Conversely, when L3 writes back a dirty cacheline to MC, MC checks the new data bit to set the CTE's bit vector accordingly.
Apart from MC, L2 also contains PTB decompressor and compressor. When an L1 cache or a page walker requests a block from L2 and the L2 copy is compressed (i.e., the new data bit -see paragraph above -in the copy is set), L2 replies with a decompressed copy; because all softwareinitiated memory accesses pass through L1 cache, always replying decompressed copy to L1 ensures CTEs embedded in PTBs are invisible to software, such as OS. When L2 receives from L1 a dirty eviction, L2 checks whether the dirty block's value is compressible under the compressed PTB format; if so and if the L2 copy is currently compressed, L2 copies into the incoming dirty block any embedded CTEs held in the stale L2 copy (note that L2 is inclusive of L1) to seek to preserve the embedded CTEs when OS modifies a PTB (e.g., to remap a virtual page elsewhere). Lastly, when receiving an uncompressed block from L3, if the requester is the page walker, L2 compresses the block before caching it; this is how TMCC initially compresses PTBs in a PTB page when OS creates the PTB page or migrates the PTB page to a new address.
5) When TMCC Cannot Embed in PTBs: Compression can only free up limited space in each PTB. As such, TMCC only embeds into PTBs truncated CTEs, with only enough bits to identify a 4KB DRAM address range within an MC's DRAM. Assuming each MC manages up to 1TB of DRAM, each truncated CTE is only log 2 (1T B/4KB) = 28 bits. Assuming the TMCC enables up to 4X physical pages in the OS, TMCC can embed 8 CTEs in the PTB under this configuration (i.e., for all 8 PTEs).
In bigger machines with bigger PPNs, however, each compressed PTB cannot fit eight CTEs. We calculate that for systems with 4TB and 16TB of DRAM, each compressed PTB can only fit seven and six CTEs respectively.
6) Overheads: Decompressing PTBs take ≤ 1 cycle; it only needs wiring to concatenate plaintext (see Figure 7). Each CTE Buffer has 64 entries; it requires a total of ∼1KB.
By always migrating memory content at page granularity, instead of block granularity, TMCC reduces the size of each page's CTE from 64B to 8B. Assuming an OS that boots up with 4X OS physical memory as DRAM size, total size of all CTEs in DRAM reduces from 6.25% to only 0.78%.
By taking on an OS-inspired approach, TMCC requires a Recency List in ML1 (see Section IV-B). Unlike Free Lists, which can store linked list pointers for free in free chunks and sub-chunks, storing ML1's Recency List's pointers takes up memory. Recency List uses 0.4% of DRAM. An OS-inspired approach also requires tracking incompressible pages in ML1 to prevent ML1 from repeatedly trying to evict the same incompressible pages to ML2.
While Deflate is effective and robust, it is slow. The stateof-the-art ASIC Deflate from IBM [11] takes 1100ns to decompress a 4KB page. Deflate is slow because it serially combines two aggressive algorithms -LZ and Huffman.
We note the state-of-the-art ASIC Deflate from IBM is a general-purpose design targeting both storage and memory. Intuitively, there can be much room for improvement when specializing Deflate just for memory. In addition, while a general-purpose ASIC Deflate designed also for storage has to strictly abide by the Deflate standard to provide compatibility across systems, an ASIC Deflate specialized for memory does not; memory values are locally produced and consumed. Unshackling from the constraints of the standard allows more room for specialization and optimization.
To specialize ASIC Deflate for memory, we first implement Deflate in HDL to identify performance bottlenecks. We then perform large design space exploration in HDL to address the bottlenecks. To explore the large design space, we make our HDL highly parameterizable by using the Chisel design language; the tunable parameters include how many characters to encode and decode per cycle, LZ sliding window size (i.e., CAM size), the number of characters in the Huffman tree, the maximum depth of the tree, sample size for frequency counting, etc. We also use a wide range of diverse workloads spanning three C/C++ benchmark suites and three Java benchmark suites to evaluate the impact on compression ratio due to the hardware design choices.
Our ASIC Deflate specialized for memory decompresses each 4KB page in ∼1/4 th the time as the state-of-the-art ASIC Deflate from IBM [11], while providing similar compression ratio. We test our ASIC Deflate via RTL simulations on 50 million 4KB memory pages. We publicly release the HDL for our memory-specialized ASIC Deflate at https: //github.com/HEAP-lab-VT/ASIC-DEFLATE-for-memory.
1) Local Optimizations to Huffman: We implement Huffman in Chisel from the ground up. In the process, we identify the tree construction for compression and tree reconstruction for decompression as the key performance bottleneck for Huffman; this is especially true when using the canonical Huffman tree format, which compresses the tree itself. Making matters worse, the Deflate standard (RFC 1951) specifies building two canonical Huffman trees from LZ output (i.e., one for literals and one for LZ match offsets), performing runlength encoding on the two trees, and compressing the two with a third and final Huffman tree. We also confirm through the IBM authors that the high setup time of IBM's ASIC Deflate is primarily due to building and restoring the Huffman trees.
To avoid this high latency, our solution is two-fold: use a reduced Huffman tree and store it uncompressed.
Our reduced Huffman tree reduces the latency and area required to build and traverse the tree by only compressing the most common input characters and leaving the remaining input characters uncompressed. We find that for non-zero memory pages, the tree can be reduced to just 16
Figure 14: High-level architecture of our Deflate compressor and decompressor. Modules highlighted in green are substantially modified or new compared to IBM's design. Each vertical dashed line separates two stages that are pipelined w.r.t one another; each vertical solid line separates two modules that run serially one after the other (i.e., the earlier module generates and buffers all of its outputs before passing them to the next module). cost of only sacrificing 1% compression ratio, on average. 15 out of the 16 codes are for the 15 hottest characters (i.e., byte-sized values) in each 4KB page going into the Huffman compressor; the one remaining code in the reduced tree is for an escape character to encode the other 200+ characters missing in the tree. Our Huffman encodes each character missing in the tree as the escape code (i.e., the Huffman code for our escape character) plus the missing character.
We further reduce decompression latency by storing the Huffman tree uncompressed. Due to having only 16 codes, our reduced tree is much smaller than the tree under the standard Deflate; this eliminates the need to aggressively compress the tree like the standard Deflate. As such, our compressor outputs the tree in a plain format, instead of the canonical Huffman tree format or any other compressed format, so that when a compressed page is accessed later, the Huffman decompressor can directly use the tree without having to first slowly decompress the tree.
However, prefixing each character not in the reduced tree with an escape code can sometimes make Huffman output bigger than the input (e.g., when most bytes in an input page are characters missing in the tree). This problem can be addressed by dynamically skipping our Huffman for pages that would become bigger after going through our Huffman. Empirically, we find that dynamically skipping our Huffman can improve compression ratio by 5%, on geometric mean. We are implementing this dynamic feature in hardware at the time of this writing.
2) Local Optimizations to LZ: One issue with specializing Deflate ASIC for memory is that the ASIC cannot be used for anything else (e.g., storage, network), unlike a general-purpose Deflate ASIC. As such, the specialized ASIC should use as little area as possible. We find that LZ takes up most of the area in our ASIC Deflate. When we implement IBM's Deflate LZ and reduces LZ's CAM size from 32KB to 4KB to match memory page size, LZ still takes up 0.24 mm 2 for the compressor and 0.09 mm 2 for the decompressor under the 7nm technology node.
We identify that the CAM for performing sliding-window pattern match as the main contributor to this area. As such, we explore the area and compression ratio of the LZ module under different CAM sizes ranging from 256B to 4KB. We find using a 1KB CAM reduces the LZ compressor to 0.060 mm 2 and the LZ decompressor to 0.022 mm 2 , while reducing the compression ratio of non-zero memory pages by only 1.6%. However, smaller (e.g., 512B, 256B) CAMs degrade the compression ratio much more severely.
RFC 1951 specifies a 286-character alphabet for LZ outputs. Since 286 is not a power of two, such an alphabet is not space-efficient; as a result, LZ outputs 9-bit characters for 8-bit character inputs. This poses no problem for standard Deflate because this inefficient alphabet is only used internally; LZ outputs are re-encoded using full Huffman trees and, therefore, do not appear at the final Deflate output and do not compromise the final compression ratio. Due to using a reduced Huffman tree, however, our Deflate can directly output LZ's outputs (e.g., after prefixing them with our escape code). As such, our LZ outputs use a spaceefficient 2 8 = 256-symbol alphabet, like how LZ is used today when it is standalone (i.e., outside of Deflate).
3) Across-Deflate Optimization: Huffman must count the frequencies of the characters in an LZ-compressed page to generate a Huffman tree before using the tree to compress the individual characters in the LZ-compressed page. Precisely counting the frequencies of the characters in an LZ-compressed page requires analyzing the entire page; as such, Huffman compression can only begin after LZ has compressed the entire page, instead of working concurrently with LZ. Having only LZ or Huffman busy, but not both at the same time, can significantly hurt throughput.
To increase throughput, IBM's design resorts to approximate frequency counting (a.k.a 1.1 Pass in [11]) by only analyzing a small portion of LZ output (i.e., a 32KB segment) at the start of a much bigger LZ output (i.e., a 256KB output). This allows Huffman to operate mostly concurrently with LZ, except for just when LZ is outputting the first 32KB out of the 256KB. Meanwhile, the 32KB of LZ output is still big enough to accurately represent the frequency distributions of the overall 256KB of LZ output.
To maximize throughput without reducing compression ratio, our Deflate operates both LZ and Huffman concurrently by using them to process two independent memory pages (see "Page 1" and "Page 2" in Figure 14). This requires adding a buffer (see "Accumulate" in Figure 14) to buffer the entire LZ output; in comparison, IBM's 1.1 Pass only buffers a small fraction of LZ output (e.g., the first 32KB of the 256KB LZ output). However, as memory pages are smaller than files, our buffering overhead is also small. We note that 1.1 Pass is still better along some dimensions (e.g., area); as such, the HDL we release also supports it as a tunable parameter. But we disable it by default as it significantly reduces compression ratio for 4KB pages.
4) Additional Details per Module: This section presents more details for each module in our ASIC Deflate, in the order that they appear in Figure 14.
The first three pipeline stages in the compressor perform LZ compression. The first stage, 1KB CAM, identifies matches between the most recent 1KB of history and the input characters to LZ in the current cycle. This matching relies on a sliding-window CAM based on IBM's nearhistory CAM [11]. The match result passes on to the Select Match stage; to simplify hardware design, our Select Match uses a greedy algorithm to select matches to encode, instead of the "lazy matching" described in RFC 1951. The third stage -LZ 8-bit Encode -encodes the matches and literals using an alphabet with 256 characters.
In our current design, the three stages above can sometimes stall due to pipeline hazards, depending on the length of the matched sequences. As a result, our Deflate only takes in 8 characters/bytes per cycle, just like the IBM design. Taking in more characters per cycle worsens the pipeline hazards and yields diminishing return in performance.
Huffman compression starts with Frequency Count; this pipeline stage reads LZ output to calculate the frequency of each 8-bit character in an LZ-compressed page. The next pipeline stage -Select 15 Characters -identifies the 15 hottest characters across the entire LZ-compressed page.
Accumulate and Replay work together to enable LZ and Huffman to work concurrently on separate pages. Accumulate buffers the output of Select 15 Characters and LZ 8-bit Encode and waits for the Huffman modules after Accumulate to finish processing their current page; then, Accumulate logically transfers its content to the Replay module to replay the buffered values to the later Huffman modules.
Build Reduced Tree then builds a Huffman tree with 16 leaves in the usual way -by repeatedly combining the two nodes with the lowest frequency. To limit the depth of the tree, when a pair of sibling nodes would exceed a tunable depth threshold, Build Reduced Tree discards the less-frequent sibling and promotes the other to keep the tree depth below the threshold. Build Reduced Tree never discards the escape code. Generating the tree takes up to 32 cycles. Write Reduced Tree then takes up to 16 cycles to write the tree to output using an uncompressed format (see Section V-B1). Huffman Encode then compresses the LZ-compressed bytes and outputs the Huffman codes at up to 32-bits per cycle.
Our decompressor begins with Read Reduced Tree, which takes 16 cycles to read in the Huffman tree and sets up the registers in Huffman Decompress; this is a significant improvement over IBM's design, which takes > 500ns to reconstruct the tree. Next, Huffman Decompress decodes up to 8 input codes or 32 input bits per cycle, whichever is smaller, via a multi-stage pipelined decoder based on IBM's design [11] [44]. The last pipeline stage, LZ Decompress, outputs up to 8B of plaintext per cycle.
5) ASIC Deflate Performance: We synthesize our memory-specialized ASIC Deflate on a 7nm ASAP technology node [45] at 0.7V using Synopsys Design Compiler [46]; our Deflate runs at 2.5 GHz with a total area of 0.13 mm 2 (see Table I). We use Verilator [47], an industrystandard high-speed RTL simulator, to measure the full-page latency, half-page latency, and throughput; Table II shows the results. The total throughput of one Deflate module (both compressor and decompressor) is 32.0 GB/s; this exceeds the channel bandwidth of DDR4-3200 (i.e., 25.6 GB/s). To compare against IBM's design, we use the formula in [11] to analytically calculate the performance of IBM's design. For 4KB memory pages, our memory-specialized ASIC Deflate outperforms IBM's Deflate in every performance metric by several times. Notably, our half-page decompression latency -the average time to decompress a needed block in a page to satisfy an L3 miss -is 6X as fast.
To measure the compression ratio of our design, we examine programs with > 200M B memory footprint from three C/C++ benchmark suites [30], [48], [49] and three Java benchmark suites [50], [51], [52]. For each program, we take 10 memory dumps equally spaced across its lifetime and deleted all all-zero pages from each dump; note that all-zero pages in a memory dump are typically untouched or deduplicable virtual pages. We calculate the compression ratio of a workload as the maximum size across its 10 uncompressed dumps divided by the maximum compressed size across its 10 dumps.
Figure 15 shows our measurements. Across all benchmarks, our ASIC Deflate specialized for memory achieves a geomean of 3.4x compression, which is only 12% lower than GZIP. Note IBM's ASIC Deflate also has a 11% lower compression ratio than GZIP [11]. Dynamic skipping of Huffman (see Section V-B1) can increase the compression ratio to 3.6x, which is within 7% of GZIP.
As another reference for comparison, Figure 15 also shows the compression ratio of the memory dumps under block-level compression. We model a 64B-block-level compression that chooses the smallest output between BPC [12], BDI [53], Cpack [54], and Zero Block; across the same benchmark suites, the geomean compression is only 1.51x.
We evaluate TMCC's performance under cycle-accurate simulators. We use Gem5 [29] and Ramulator [55] to simulate CPU and DRAM, respectively. Table III lists the simulated system's parameters. We evaluate workloads used by recent prior works [23], [24] on virtual address translation in conventional systems. We simulate all such workloads that we could run in Gem5. They span IBM's GraphBIG [30], SPEC CPU2017 [56], and PARSEC 3.0 [48]. All workloads are multi-threaded except mcf and omnetpp which are single-threaded. For single-threaded workloads, we evaluate four instances of the same benchmark. Figure 16 shows the memory intensiveness of the benchmarks.
We fast forward each benchmark deep into the region of interest using Gem5's KVM mode in native execution speed; each benchmark reaches at least 95% of its maximum memory footprint. Then, we fetch all of the benchmark's memory values to place, compress, and pack them into available memory. Next, we use at least one second of atomic simulation to warm up ML1, ML2, and embedded CTEs in compressed PTBs. Subsequently, we warm up the branch predictor and prefetchers using 10ms of detailed simulation (without any compression-related performance overheads). Finally, we use 20ms of detailed simulation to evaluate performance. We use store instructions/cycle to evaluate performance.
We simulate one-level TLBs; Gem5 lacks two-level TLB for x86. To keep TLB hit rate consistent with real systems, we increase the number of entries in L1 TLB to 2048, which is similar to the total number of TLB entries AMD's Zen 3 [58]. This ensures a similar TLB hit rate between simulations and the real world; this is essential as TMCC optimizes for memory accesses following TLB misses.
Modeling Details for TMCC's Page-level Accesses: To prevent the faster block-level ML1 accesses from suffering long queuing delays due to the bandwidth-intensive pagelevel accesses to ML2, we simulate the FR-FCFS-Capped command scheduling policy; prior works use capped policies to improve fairness. TMCC also carefully issues the 64B read and/or write requests to carry out page-level accesses so that these requests only consume at most 10 slots in MC's read/write queue at a time. To prevent the many writes due to page migration from blocking reads to the channel, TMCC only targetedly puts into write mode the rank accessed by page write, without putting the entire channel into write mode; prior works (e.g., Nonblocking Writes [59]) also only put individual ranks in a channel into write mode.
When reading from ML2, MC responds to LLC as soon as MC decompresses the requested block. In the background, MC migrates the decompressed page to ML1. This background migration is similar to the background repacking in prior works [6]. We model a 32KB buffer (i.e., eight 4KB entries) in MC to buffer data for the transfer. Accesses to ML2 are stalled when all eight entries are full.
When ML1 Free List has < 4000 chunks, ML1 grows the list by continuously evicting cold pages to ML2. The resultant ML1-to-ML2 page migrations have lower priority than LLC accesses to ML2, which trigger ML2-to-ML1 page migration; ML1 pauses eviction when LLC accesses to ML2 are outstanding or pending. But their priorities are flipped while ML1 Free List has < 3000 chunks.
Figure 17 shows TMCC's performance normalized to Compresso [6], a recent prior work on hardware memory compression for capacity. In this comparison, TMCC saves the same amount of DRAM as Compresso for each workload. On average across all workloads, TMCC improves performance by 14%. The improvement is highest for shortestP ath and canneal; they have high memory access rate (see Figure 16) and high CTE cache miss rate (see Figure 2). The improvement is the lowest for kcore and triangleCount; they have low CTE cache miss rate (see Figure 2). TMCC's performance improvement primarily comes from hiding memory latency overhead due to address translation. Figure 18 shows the average L3 miss latency of a system with: (i) No Compression, (ii) Compresso and (iii) TMCC at iso-compression ratio as Compresso. For a system with no compression, L3 miss latency is 53ns; this includes all sources of L3 miss latency (e.g., NoC latency between MC and LLC tile), not just DRAM latency. Under TMCC, the average miss latency is very close to no compressiononly 56.4ns. For Compresso, the average L3 miss latency is considerably higher -73.9ns; the ∼20ns longer memory access latency comes from accessing data serially after accessing CTEs for each CTE cache miss. TMCC's latency benefit over Compresso are primarily due to fetching from DRAM normal memory blocks and their CTEs in parallel. As described in Section V-A3, TMCC accesses CTE and normal blocks in DRAM in parallel to verify the normal blocks speculatively fetched using CTEs embedded in CTEs. On average, 22% of LLC misses that hit in ML1 are satisfied by fetching normal blocks and CTEs from DRAM in parallel (see Figure 19). However, 22% is only a minority of LLC misses. This is because MC always caches the CTE after it arrives from DRAM. Because TMCC obtains embedded CTEs from compressed PTBs, which are only accessed during page walks, TMCC cannot use embedded CTEs to speed up address translation for LLC misses that are not preceded by page walks. As such, caching a CTE after fetching it from DRAM (e.g., after accessing the CTE in DRAM in parallel with normal data for verification after a TLB miss to a page) speeds up address translation for LLC misses that hit in TLB (e.g., later accesses to the same page).
Some of the latency benefit also comes from reducing how frequently TMCC accesses DRAM to fetch CTEs compared to Compresso. Like prior works, TMCC only fetches CTEs from DRAM when they miss in CTE cache; fetching CTEs from DRAM in parallel with normal blocks for verification Sensitivity Analysis -Saving more Memory: TMCC builds on an OS-inspired approach; as such, TMCC also inherits the following behavior from OS memory compression: as a system's memory usage increases (e.g., due to having more background/context-switched processes in memory), more pages are migrated to ML2 and more DRAM will be saved by ML2's compression (see Section IV-A). As such, having high memory usage in a system can naturally trigger TMCC to save more DRAM than Compresso, especially since TMCC uses page-level Deflate, instead of blocklevel compression as does Compresso; in our evaluation, Compresso uses the block-level compression in Figure 15.
But, of course, saving more DRAM also comes at the cost of performance, as more pages will be stored in ML2 compressed. To fairly evaluate TMCC's memory savings over Compresso, we evaluate the performance of TMCC at various higher memory savings to identify operating points where TMCC can still provide the same (i.e., > 99% of the) performance as Compresso. Table IV shows for each benchmark TMCC's compression ratio normalized to Compresso when operating at the same, instead of higher, performance as Compresso. It is 2.2x on average. Figure 20 shows improvement over the bare-bone OSinspired hardware compression in Section IV. When both designs are saving the same small amount of DRAM (i.e., each workload's DRAM usage matches Column B in Table IV), TMCC improves performance by 12.5%. Figure 20 shows the split of benefit due to TMCC's ML1 and ML2 optimizations; they improve performance by 8.25% and 4.25%, respectively.
When both designs are aggressively saving the same amount of DRAM (i.e., each workload's DRAM usage matches Column C in Table IV), TMCC improves performance by 15.4% over the bare-bone OS-inspired hardware compression. In this scenario, the performance benefit due to TMCC's ML2 optimization surpasses the benefit from ML1 optimization. When aggressively saving DRAM, accesses to ML2 become more frequent (see Figure 21); higher ML2 access rate increases the impact of ML2 optimizations, while diminishing the impact of ML1 optimizations. Sensitivity Analysis -Smaller Workloads: We also evaluate TMCC with smaller workloads -remaining PAR-SEC 3.0 benchmarks and RocksDB using 1GB Twitter dataset. When saving the same amount of DRAM from these workloads as Compresso, TMCC can provide a maximum performance benefit of 5% (for RocksDB) and loses a maximum performance of 0.1% (for f reqmine) compared to Compresso. The average performance is within 1% of Compresso. TMCC provides no meaningful performance benefit for these workloads because they are small and have regular access patterns. However, even for these workloads, TMCC can still provide benefits; our evaluation shows TMCC can provide 1.7X compression ratio on average as Compresso, while still providing the same (i.e., > 99% of the) performance as Compresso for every workload. The maximum is 3.1x, for blackscholes.
Huge Pages: TMCC's ML1 optimization is ineffective for huge pages. Each PTB for huge pages covers eight huge pages or 8•2M B = 16M B. This equates to 16M B/4KB = 4K regular 4KB pages; 4K CTEs is too numerous to fit in a PTB. However, TMCC's ML2 optimization still applies. Compared to prior works on hardware memory compression, TMCC still improves CTE cache hit rate due to using pagelevel, instead of block-level, translation. When repeating our evaluation under huge pages across the workloads in Figure 17, we find that compared to Compresso, TMCC can either improve average performance by 6%, while saving the same amount of memory, or provide 1.8X the effective memory capacity, while providing the same performance.
Memory Interleaving: Some CPUs not only interleave adjacent physical address ranges across the many memory channels in a memory controller, but also interleave adjacent physical address ranges across multiple memory controllers (MCs) to help balance bandwidth utilization. The granularity of this inter-MC memory interleaving can vary across CPUs, BIOS settings, and installed DIMM count/positions.
As TMCC resides in MC, interleaving memory across multiple MCs at sub-page (i.e., <4KB) granularity can interfere with TMCC's page-level compression. Therefore, TMCC requires address mapping to only interleave memory across memory controllers at ≥4KB granularity, instead of sub-page granularity.
We evaluate the performance impact of two TMCCcompatible interleaving policies on bandwidth-intensive benchmarks from a prior work on improving memory bandwidth [60]. We choose these benchmarks because high bandwidth usage magnifies performance differences across different interleaving policies. We simulate a system with 16 cores and two MCs with two channels per MC. The baseline interleaving policy performs sub-page interleaving at 512B granularity across MCs and at 256B granularity across the channels within each MC.
Figure 22 compares sub-page interleaving only for channels within each MC (i.e., MCs are interleaved at 4KB and constituent channels are interleaved at 256B) against the baseline interleaving. The average performance is within 1%. The maximum degradation is < 5%. However, using coarser interleaving improves row buffer locality and hit rate and, therefore, provides a maximum performance improvement of 10%. For sensitivity analysis, Figure 22 also compares always interleaving pages across channels (i.e., no sub-page interleaving across channels) to the baseline interleaving; the 0.8 0.9 performance degradation is more pronounced (e.g., 5%, 10% and 11% for linpack, sp D, and hpcg, respectively). Our results match that of a prior OS work [61]; this work turns off hardware-level sub-page interleaving across MCs and, instead, interleaves pages across MCs by modifying the memory allocator to map adjacent 4KB virtual pages to different MCs. Only 1% real-system performance difference is reported; includes the overheads of the OS changes.
A prior work -LCP [5] -relies on OS support to embed some CTE information into PTEs; OS manages new compressed pages of different sizes (e.g., 2KB, 1KB) and records the compressed page size in PTEs. LCP uses the embedded compressed size of a page to predict the page's data blocks' DRAM locations to speculatively access data in DRAM in parallel with accessing the CTE in DRAM. Beside changing OS, the speculative parallel accesses are often wrong (e.g., as often as ∼50% of the time for many workloads, see Figure 16 in [5]) because using compressed page size alone to accurately predict per-block DRAM location is difficult. When a page changes between different preset sizes due to fluctuation in compression ratio, hardware also raises interrupt to tell OS to update the page size recorded in the PTE. A later work shows these interrupts are costly [6].
Unlike LCP, TMCC embeds CTEs into PTBs softwaretransparently by compressing PTBs in hardware. By migrating memory content only at the page granularity, TMCC keeps CTEs small enough to fit them in PTBs to enable highly accurate speculative parallel accesses to DRAM.
This paper is the first to explore the address translation problem for large and/or irregular workloads under hardware memory compression for capacity. TMCC builds on an OSinspired approach by addressing its latency overheads while accessing both hot pages and cold pages. For hot pages, TMCC hides the latency overhead of physical to DRAM address translation by compressing PTBs to free space in them to embed CTEs. For cold pages, we specialize ASIC Deflate for memory to reduce decompression latency by 4X compared to IBM's state-of-the art ASIC Deflate. Our evaluations show that for large and/or irregular workloads, TMCC can either improve performance by 14% without sacrificing effective capacity or provide 2.2x the effective memory capacity without sacrificing performance, when compared to state-of-the art hardware memory compression.
˜/source_gem5 to process the output. The simulations take 36 hours to finish.
We also provide a README.txt in each experiment folder for quick reference. For Gem5 and page table dump experiments, they provide code overview.
• Gem5 simulations: See Section VI.
• Page table dumps: We pause benchmarks in the region of interest. Then we use the page table dump tool in public artifact of [62]. We also provide the evaluators the resources to take fresh page table dumps. • Compute compression ratio of memory dumps: We use Linux's gcore tool to take memory dump of a program. Subsequently, we process the memory dump to compute the compression ratio. Note that we discard all-zero pages while computing compression ratios. • ASIC Deflate verification: We use Verilator to run RTL simulations of the compressor and decompressor. We verify that each non-zero 4 KB page in the memory dumps are same as original after compression and decompression. Artifact submission, reviewing and badging methodology:
• http://cTuning.org/ae/submission-20201122.html • http://cTuning.org/ae/reviewing-20201122.html • https://www.acm.org/publications/policies/ artifact-review-badging