Micro2023: Utopia

导言

This blog delves into Onur Mutlu’s Address Translation work on Processing-in-Memory (PIM), titled “Utopia[^0]: Fast and Efficient Address Translation via Hybrid Restrictive & Flexible Virtual-to-Physical Address Mappings.”

[^0]: Additionally, the name “Utopia” translates to 乌托邦 in Chinese.

Excellent Video Resource

xxx

Outstanding Blog or Overview Paper

You can find a Chinese-language blog discussing this topic[^1]

Supplementary Materials

PPT is here

Author and Affiliation

The mastermind behind this work is Onur Mutlu, a prominent figure at ETH Zürich. The primary author^2, a rising star in the realm of Processing-in-Memory (PIM).

background

1. four-level radix-tree PT
2. Two trends to reduce the PTW overhead:
   1. PWC
   2. hash-based address mapping scheme

Motivation

The motivation behind this research is to create a system that combines both flexible and restrictive address mapping schemes to harness the advantages of each. This strategic decision is visualized in the following flow chart:

Strategy Decision Flow Chart

graph LR
  A["Translation
  Structures"] --> B{"Large or
  Compact?"};
  B -->|Large| C["Flexibly Mapping 
  BUT more metadata
  High Latency and Overhead"];
  B -->|Compact| D["Reduce Overhead 
  BUT Individual Partition Limits Data Sharing 
  and Can Lead to Out-Of-Memory (OOM)"];
  C --> E[Utopia];
  D --> E;

Restricting the flexibility of the address mapping increases data accesses to the swap space of the storage device by 122%.

Difficulty

1. identifying the candidates (potential situation)
2. efficiently managing the co-existence of system design(1)
3. extend system to support new way with minimal overhead on existing hardware solution

When to use contential way?

1. support conventional virtual memory features such as data sharing
2. OOM: avoid accesses to the swap space when data does not fit inside a restrictive segment.

Q&A After jump read paper and PPT

1. Q1: The main design is combine the two conventional design, why it’s fast than SOA hash-based design, where is the different?
2. A1: deal with the OOM’s swap overhead???

   2. Q2: how is it deal with traditional hash-based drawback: 1. hash conflict 2. PA component. e.g., cache-like RestReg how to deal when the way is full
    1. A: Utopia allocates a page in a FlexSeg in two cases: (i) when the corresponding page gets evicted from a RestSeg or (ii) when there is not enough free memory space in any RestSeg.
   3. What is `FSM` in diagram
      1. In order to minimize the latency of a page walk, the PMH is implemented as a **Finite-State Machine (FSM)**.[^3]
2. Q3: **identifies** and maps costly-to-translate addresses to RestSegs
    1. A3: 1. All Page-Fault-based Page Allocation in the RestSeg 2. monitor PTE in FlexSeg, if used frequent, move to RestSeg

相对于 NAT，Utopia 重点在于如何结合两者： 1. 物理地址的划分和存储 2. 相互如何转换 3. OS的支持

(iv) how Utopia decides which data should be placed into a RestSeg (Challenge 1), (§5.5).

(v) the OS extensions to enable Utopia (Challenge 2)(§5.6), and 

(vi) the architectural modifications in the MMU to efficiently support Utopia (Challenge 3)(§5.7)..

Main Idea in One Line

Outline: Key Steps

The key idea of Utopia is to manage physical memory using two types of physical memory segments: restrictive segments and the flexible segment.

• A restrictive segment (called RestSeg) enforces a restrictive, hash-based address mapping scheme, thereby enabling fast and efficient address translation through compact and efficient address translation structures.
• A flexible segment (called FlexSeg), employs the conventional address mapping scheme and provides full virtual-to-physical address mapping flexibility.

Article Highlights

1. Following NAT’s idea: Restricting the virtual-to-physical mapping
2. Using hash-based PT

Challenges in Replicating the Research

Discussing the difficulties and obstacles encountered when attempting to reproduce the research findings or results.

参考文献