# Transformer: An OS-Supported Reconfigurable Hybrid Memory Architecture
## 3 Design and Implementation
### Page Hotness Monitoring
#### 3.1.2 A Level Array for Storing Page Access Counts  
As mentioned before, the kernel thread needs to scan the page table of the monitored process and count the access counts. The statistical information includes the starting address of the page, page access counts, and a flag to distinguish whether the page is currently in DRAM or NVM. Theoretically, the virtual memory address space of 64-bit operating systems is 264. Although the address space actually used in a 64-bit Linux is only 48 bits, it is still very large. However, a process usually uses only a small portion of virtual memory space, and not all virtual pages are accessed due to the data access locality. We only have to scan existing page table entries. If we store all page access counts in a regular array directly, the page access monitoring module would incur significant memory space overhead. Thus, it is essential to design an efficient data structure to store the access counts of memory pages. The multi-level page table is essentially a data structure reflecting the page mappings. Inspired by the idea of the page table, we design a data structure  
Figure 3: Data structure of modified page table entry. named level array to store the access counts of memory pages. Since the time complexity of accessing and modifying data in the level array is constant, we can quickly obtain and update the access counts of any page with the level array. The level array adopts a hierarchical structure similar to the page table; it allocates memory according to the number of data elements stored in it. As shown in Figure 4, a level array is composed of multiple layers, and each layer consists of several nodes. Each node is the same size as a memory page. A level array uses a chained structure, which means nodes between each layer are connected by pointers. Therefore, it does not need a continuous large memory space. Only leaf nodes in the last layer store the actual data elements. The other branch nodes store pointers that point to the next layer. The level array uses a reference counting mechanism to free the memory of useless data in time. Each branch node records the number of nodes in the next layer it points to. When the number becomes zero, it means that this layer has become the last layer. Therefore, it will release the memory of nodes in the next level to avoid unnecessary memory waste. The level array also stores a bitmap in the leaf node to verify whether the data stored in the leaf nodes are valid or not. The bitmap has as many bits as the quantity of data elements stored. By setting and clearing the values on the corresponding bits in the bitmap, we can determine whether the data elements in the leaf node are valid or not. A level array needs to determine the range of data elements in advance. For instance, when the level array is designed to store the memory pages-access counts, the index range of the level array is the entire virtual address space. The number of layers is dynamically adjusted by the volume of data elements actually stored. A level array with only one layer contains only one leaf node. As mentioned before, the size of each node is the same as the size of a page, which is 4 KB, so the level array of only one layer can store 4096/_datasize_ data elements, where the _datasize_ represents the size of the data element. If the level array of one layer is not enough to store all data elements, it will expand to two layers. The original leaf node in the first layer becomes a branch node, and the nodes in the second layer become leaf nodes. The first layer contains several branch nodes; each branch node contains a pointer to the next layer and a counter that is used for reference counting. In 64-bit systems, each branch node occupies 8\(\times\)2 bytes, so one page can contain 256 branch nodes. Therefore, a two-layer level array can store the actual number of data elements up to 256 \(\times\) 4096/_datasize_. The capacity of the level array increases exponentially by the number of layers.