Monarch: A Durable Polymorphic Memory For Data Intensive Applications

Last-level caches with 3D die-stacked memories incur significant write-bandwidth due to write backs from on-chip L3 and cache-line installation on cache-miss. Non-volatile memories like RRAM usually have a limited write endurance, due to which some cells die after a specific number of writes to them (usually $10^{8}-10^{12}$ [13]) This poses a significant challenge for employing RRAM-based caches, even more so because 3D stacked memories have a higher bandwidth than the conventional off-chip memory. This also poses security challenges where-in a malicious application can exploit frequent writes to the same block and render the memory unusable. Monarch employs multiple techniques and solutions to keep lifetime at an acceptable level. (1) Monarch introduces a new timing parameter, $t_{MWW}$, which imposes a timing constraint between successive writes to the same region of memory. This timing parameter cannot be enforced at fine granularity; therefore, Monarch introduces a set technique for viable implementation of the timing parameter.

(2) On top of the proposed timing constraint, Monarch employs a rotary technique at the same granularity to further enhance the lifetime, while maintaining a superior performance compared to an idealistic DRAM cache system. (3) Monarch adopts optional write-through directly to the off-chip main memory, along with access no-allocate, thereby eliminating unnecessary writes to Monarch.

The CMOS unit for SRAM+SCAM has the best read latency, followed by 1R and XAM. SRAM has a $10\times$ and $100\times$ better write latency than DRAM and RRAM. The search latency of SRAM, DRAM, and 1R are much higher than the others due to the fact that they support serial search rather than parallel. Instead, SCAM provides the shortest lookup time, followed by XAM and 2T2R.

SRAM and SRAM+SCAM exhibit the best read energy, followed by 1R and XAM. The search energy of XAM and 2T2R are low due to their efficient in-situ XNOR operations. SCAM requires a low write energy but a significant search energy due to its cell complexity. An RRAM write require magnitudes higher energy than SRAM and DRAM.

The 1R array consumes the least area, which is similar to that of XAM. The area of a XAM array is about $10\times$ smaller than the SRAM+SCAM.

Overall, 1R, SRAM+SCAM, and XAM could give configurations optimized for the specific metrics mentioned above. DRAM is a default baseline considering its widespread use in the existing off-chip and on-chip memories. Therefore, we select three technologies to build the 3D baseline system: 1R RRAM, CMOS SRAM+SCAM, and DRAM. Note that XAM process is CMOS compatible, thereby manufacturable on the processor die. But its capacity would be very less to capture the complete behavior of big data applications. On the other hand, off-chip integration of Monarch would encounter a limited bandwidth making it a poor choice for caching. Therefore, we consider Monarch as an in-package high-bandwidth memory flexibly used for cache, associate search, and scratchpad memory.

Considering a 4GB DRAM stack with 8 layers divided into 8 vaults, a total of 64 segments each sized 64MB are necessary. We consider the same configuration for all the baselines using segments that consume the same area across all the technologies. This provides an iso-area comparison among the systems, with memory capacities of 8GB (1R RRAM), 8GB (Monarch), and 73MB (CMOS).

A flat-RAM vault is supposed to service only two types of requests (i.e., read and write) generated by software. Multiple counters are used to track the required delays between pairs of commands before sending each command to the Monarch layers. Moreover, the controller needs to ensure that the target bank/superset is set to RowIn RAM.

Extra components are necessary to enable the flat-CAM mode. First, the controller needs to recognize four different types of software generated requests: data write, search, key/mask write, and data read. Second, the controller may require transitioning the target Monarch bank/superset to different modes prior to serving a request. A data write may be carried out only if the target bank/superset is in the ColumnIn CAM mode. The software is expected to populate the XAM arrays using data writes prior to a search. Figure 6 shows an illustrative example code for operation of CAM through a simple key-value store. The key and data values are initially written into the CAM and RAM scratchpads (a single set each in this example), which is followed by updating the key/mask registers, searching the set, and accessing data based on the value returned by the match pointer.

Four pointers are employed for accessing the elements of data, key, mask, and match. For simplicity, assume that the data is a 2D array of a 64-bit type. Each block of 8 data elements is stored across 8 subarrays. A total of 64 blocks are written in a single set. flat_RAM_malloc and flat_CAM_malloc are the proposed function calls for allocating memory within the RAM and CAM scratchpad regions respectively, explained in detail later in this section. Next, the key/mask values are updated through 8 normal writes in the code. However, any accesses to the key/mask pointers are recognized by the flat-CAM controller for special service. First, the key/mask pointers are mapped onto two global registers in the vault controller, which are used for any upcoming search operations. Second, the contents of these registers are sent to the target supersets prior to every search. To eliminate any unnecessary key/mask updates, the controller tracks the recently updated supersets. Each key/mask write may only be carried out in the RowIn CAM mode; therefore, parepare and activate commands may be necessary to toggle the bank/superset mode. A search may be initiated by the software through a normal read to the match pointer. Similarly, the match pointer is mapped to a special register at the Monarch controller. On every read to this register, the memory address is used to determine the target Monarch superset. On a search, the match register is updated with the matching index of the search, and it gets reset to NULL if there is no match in the specific superset. The value stored in the match register can be accessed by the program (Figure 6). The controller will issue a search to the target superset if the results of previous search is not present in the match register and the key/mask registers have not yet been updated. When the previous search result is not present in the match register, a key/mask update is necessary if the superset does not have the latest key/mask values. Prepare and activate commands may be necessary before a read in the ColumnIn CAM mode to perform a search at the target Monarch set.

As the key/mask registers are shared by multiple sets within each superset, searching consecutive sets per superset do not incur unnecessary key/mask updates. Moreover, partial search and variable key length is supported through masking. For example, setting myMASK to 0x0FF00 results in searching among the second byte of data elements. ¹¹1When we have to read the actual keys stored inside the CAM arrays, the controller issues read commands in row mode.

In the cache mode, the vault requires both CAM and RAM banks simultaneously. For example, a vault with 64 banks may be partitioned into 30 RAM and 2 CAM banks to support 64B cache blocks tagged with 30 address bits, 1 valid bit, and a dirty flag. The RAM and CAM banks are assigned for data and tag storage respectively. Upon receiving a request, the vault controller follows certain steps to access Monarch or forward the request to memory. As the data and tags are physically decoupled across banks, we need a coordinated address mapping that corresponds the tag and data locations within each vault. First, we consider a 512-way set associative cache due to the available search bandwidth across all the set columns for one access. For every 512 tags maintained in a set, 512 data blocks are stored in a superset. Therefore, every CAM set corresponds to a RAM superset. Second, every data block requires a tag. Hence, the number of tag locations must be greater than or equal to the number of stored data blocks. For example, $\frac{1}{16}$ of the CAM partition in a cache vault with 32b tags and 32 banks is left unused. As shown in Figure 7, every memory address is translated to RAM and CAM addresses that have the same vault and superset IDs. The bank ID of the RAM address is partially used for computing the set, key and bank IDs of the CAM address. Notably, each array column stores two 32-bit tags. The key ID is used to determine which tag of a row to access during a search. Every tag lookup requires searching for a key/mask combination. We choose more significant bits of the CAM address for the key ID to reduce the frequency of mask updates.

For every cache lookup (1) the key (and if necessary the mask) values are updated and (2) a search will be issued by the controller. Based on the search outcome, a hit or miss will be detected at the controller. On a hit, the corresponding data block will be accessed in the RAM part; otherwise, the request will be forwarded to the main memory. To install a cache block in Monarch, a data read in RAM mode to the CAM part is necessary to check the valid bits of all the 512 tags in a set. Upon finding an invalid tag, the location will be selected for installing the new data and tag. Otherwise, another row read to the dirty bit position of the tags, determines if a clean block is available for eviction.

Intel’s KNL employs the memkind library extension [21] that, which allows the applications to call custom memory allocation (malloc) functions. HBM_malloc is such an example where the memory is allocated in the in-package HBM rather than main memory. Monarch extends the principle of custom memory allocation from the memkind library to add two new function calls (flat_RAM_malloc and flat_CAM_malloc) forthat allow us to independently allocatinge memory for requests in the RAM and CAM vaults respectively. Also, the extended library returns pointers to the match and key/mask registers defined inside the vault controllers.

Tracking block writes with $t_{MWW}$ may be costly and impractical. Consider 4-byte storage per block to track the last writes, a total of 256MB memory would be necessary to track the blocks. Instead, we exploit the specific properties of Monarch to reduce this cost significantly. First, the counters are maintained at the superset granularity, while the writes within each superset are evenly distributed across blocks (will be explained later). Second, the counters are stored in the main memory while a TLB-like approach is employed for on-chip buffering. Due to the high locality of memory accesses, we observe a negligible performance impact by this mechanism.

By enforcing $t_{MWW}$ at the 512-block supersets, a new write will not be allowed for $t_{MWW}$ if the superset writes exceed $512M$. Monarch follows a strict blocking policy for such write to ensure the target lifetime. Hence, the programmer’s responsibility is to map read-mostly data to Monarch in the flat mode. None of our evaluated applications in the flat mode exceeds this timing requirement. In the cache mode, however, the superset will be locked for $t_{MWW}$ and all its accesses are forwarded to the main memory. Instead, we employ write mitigation techniques to alleviate the diverse impact of superset blocking.

Monarch incurs two kinds of writes into XAM arrays: writebacks from L3 due to eviction and block installation. Most these writes have been proven unnecessary and counterproductive for in-package caches, where skipping them results in a better system performance [9, 10]. Similarly, Monarch eliminates a significant portion of these unnecessary writes to enhance the system lifetime. When fetching a missing block from memory, Monarch follows a no-allocate policy, wherein no XAM memory will be allocated for the new block. Hence, no writes is performed for a missing block. Instead, the block is sent for installation in L3. This, however, may result in zero block installation in Monarch. To address this issue, we allow a selective block installation in Monarch for the evicted blocks (dirty and clean) from L3. Along these lines, we add a new bit-flag per L3 blocks that indicates if the block is read after installation in L3. On a block eviction from L3, the dirty (D) and read (R) flags help the Monarch controller to install or update a block in the XAM arrays, for which four different cases are possible. $D\&R$: If both bits are high, the block has been read from and written into by the program, which is likely evicted from L3 due to a capacity miss. We observed that it would help to write these blocks in Monarch. $D\&\overline{R}$: This case indicates that the block has been written into, but not read from before eviction. Monarch forward these blocks to the main memory. $\overline{D}\&R$: In this case, the block has been read from, but not written into before eviction. We observe most such blocks are read-frequently; therefore, Monarch identifies them as read-only and install them in XAM arrays. $\overline{D}\&\overline{R}$: If both bits are low, the block has not been accessed ever during its lifetime in L3. These blocks are skipped from Monarch. Overall, we observed an average of 31% reduction in the write traffic to the in-package memory due to these rules.

A cache placement/replacement policy may often end up choosing a few physical locations of a superset for eviction and installation. To ensure an even distribution of writes within supersets and a fair use of the Monarch address space, we propose a rotary offset address mapping combined with a hierarchical mechanism. We adopt a random replacement policy based on a free running 9-bit counter shared by all the sets within each vault. On every block replacement, the vault controller increments the counter to indicate the next physical location of all sets for a possible eviction. As a result, every two block evictions/installations at a physical location are spaced in time by at least 512 evictions per vault.

Moreover, Monarch employs a wear leveling mechanism at every vault controller (Figure 8). Similar to DRAM controllers, an address mapper and a command scheduler are used to (1) extract the bank, superset, row, and column IDs for each access, (2) track the required interfacing commands for each request while performing the necessary cache operations, and (3) enforce the required timing parameters among all the issued commands. The proposed mechanism actively monitors all the tag updates, block installs, and data writes to each superset. Upon detecting an uneven write distribution within each vault, a rotate signal is generated to redistribute writes in Monarch through an offset address mapping.

We consider the average number of writes per superset (WR) as a metric to identify an uneven write distribution. A large WR indicates that the accessed supersets are likely hot and candidates for remapping. We employ a write counter and a superset counter for approximating WR. Upon issuing every XAM write by the command scheduler, the write counter is incremented and a superset write table (SWT) is looked up for the W and D flags, which indicate if the superset has been written and dirty, respectively. If this is the first write to the superset (i.e., W=0), the superset counter is incremented by 1 and W is set to 1. If D is 0 and the write creates a dirty block in the superset, the dirty counter is incremented by 1 and D is set to 1. To eliminate the need for a full-fledged divider, we employ a simple logic for approximating the ratio between the write and superset counts. WR is set to 1 when the most significant non-zero bit of the write counter is 9 binary orders ($512\times$) larger than the superset counter. The rotate signal is generated by ORing WR, WC, and DC; where, WC and DC indicate that the write and dirty limits have reached in the counters. On a rotate signal, the dirty supersets from SWT are looked up and their dirty blocks are moved from Monarch to main memory, SWT and all counters are reset, and four address offsets are updated. The offset registers are used for offsetting the vault, bank, superset, and set IDs of Monarch accesses during address mapping. Upon a rotation, the offset registers are incremented by unique prime numbers–i.e., bank (1), set (3), vault (5), and superset (7)–to make the write distribution more even and less predictable. (The vault offset is only updated every 8 vault rotates.)

HBM [19] is in-package 3D stacked DRAM that has 8 DRAM dies stacked on top of each other. Through silicon vias (TSVs) connect the DRAM layers through the cross section, and the memory follows a hierarchy of vaults, banks, sub-banks, and sub-arrays. Each HBM typically has 4-8 vaults, with each vault having 8-16 banks. The HBM interface allows for different DRAM commands such as refresh, precharge, activate, read, and write. An in-package multi-channel DRAM (MCDRAM) is employed by Intel’s Xeon Phi processors (code-named as Knights Landing) [35]. MCDRAM supports 3 operational modes for flat, cache, and hybrid address spaces. The addressing mode configuration is performed at boot time.

Software defined memories have been examined by the prior work. Jenga [5] is a software defined cache that builds virtual cache hierarchies depending on the OS needs. Banshee [36] exploits software hardware interplay by combining page-table based page mapping management and bandwidth efficient cache replacement. Li-Si Monona [37] proposes a reconfigurable computing fabric coupled with RRAM based memory to alleviate FPGA performance and energy efficiency of diverse cloud workloads. Monarch provides configuration at a higher level, where the OS can dictate which part of the application needs to run with Monarch as cache, while it can configure a part of Monarch as software defined scratchpad and control data placement with the full address space of the scratchpad being visible.

Research on stream processing with HBM has largely focused on comparing sort merge versus hash join performance. StreamBox-HBM [38] proposes a stream analytics engine optimized for HBM, wherein sequential sort algorithms for grouping are better than hash based join algorithms. Monarch optimizes stream processing applications and operates at the same maximum bandwidth of HBM. Recent work on optimizing HBMs for hash tables have focused on alleviating the overhead of pointer chasing [39], which uses the logic layer of the HBM to perform some in memory commutations for pointer chasing, thereby alleviating the data transfer cost from CPU to memory. This provides optimization for hash tables with separate chaining based conflict resolution. While Monarch implicitly reduces data transfers from memory to CPU for hash table lookups, it focuses on hash tables with open addressing based conflict resolution, which requires no pointer chasing. R-Cache [11] proposes a highly set-associative, in-package cache made by 3D die stacking of memristive memory arrays. However, R-Cache is purely hardware managed and has no reconfigurability, and the transaction flow differs between Monarch and R-Cache. Moreover, R-Cache does not provide any lower bound for the lifetime; whereas, Monarch ensures a minimum lifetime regardless of the user applications. Also, Monarch benefits from skipping unnecessary writes to improve performance.

Prior work on NVM for hash tables [40] has been in building novel single-node hash table structures to benefit from the non-volatility and low latency of NVM. This work proposes a new memristive memory architecture, which can be exploited to optimize open addressing based single-node hash tables. HiKV [41] focuses on designing a hash table that performs a hybrid indexing that exploits the fast index searching capability of NVM and low read latency of DRAM. NVMcached [42] designs an NVM based key-value cache using byte-addressable NVM for key-value store. A maximum throughput of $4.8\times$ on YCSB workloads is gained while Monarch achieves a maximum speedup of around $13\times$ for key-value search. RC-NVM [43] proposes a 1R crosspoint based memory architecture that supports row and column accesses to memory allowing for optimizations of iMDB based applications like SQL. RC-NVM also proposes new instructions to enable row/column storage of data. Monarch proposes a row/column storage similiar to RC-NVM, but unlike RC-NVM, provides the capability of large scale associative search, while also providing a 2R-cell based crosspoint which is more robust against possible sneak currents due to half selected cells [4].

Intel Optane 3D XPoint features a crosspoint structure made of fast switching material. Optane DC [44] supports memory (cached) and app direct (uncached) modes. In memory mode it is used as cache for DDRx, which helps hide the drawbacks of the low bandwidth of DDRx, while in App Direct mode, it is used as a persistent storage device, similiar to Monarch. Optane has been shown to be almost $2\times$ faster than their counterparts for file-system storages. However, Monarch is different due to its multidimensional access and search capability.

Wear levelling for different technologies have been proposed previously which applies across the range of non-volatile memory technologies. Qureshi  [45] et al. proposes start-gap wear leveling, which uses only a start register and a gap register coupled with simple address-space randomization with minimal overhead. To the best of our knowledge, Monarch is the first memory system providing a use-defined lower bound for resistive caches.