(논문) Tiered Memory Management: Access Latency is the Key!, SOSP'24 (4. Colloid with existing memory tiering systems)

본 글은 논문 Tiered Memory Management: Access Latency is the Key! (SOSP 2024) 를 읽고 정리한 글입니다.

별도의 명시가 없는 한, 본 글의 모든 그림은 위 논문에서 가져왔습니다.

목차

• 1. Introduction
• 2. Motivation
• 3. Colloid
• 4. Colloid with Existing Memory Tiering Systems (현재 글)
• 5. Evaluation
• 6-7. Related Work and Conclusion

4.0. Overview §

NXSECTION

• 4.0 은 overview 로, 논문에는 이런 section 은 없다.

• Section 3 의 내용을 정리해 보자면, Colloid 는:
  • Latency measurement: Latency 측정
  • Page placement algorithm: 측정한 latency 에 따라 default 및 alternate tier 에 몇개의 hot page 를 배치할지 결정
• 의 역할을 한다고 할 수 있다. 그러면 tiered memory 를 위해서는 다음의 두개가 더 필요하다는 것을 생각할 수 있다:
  • Access tracking: 어떤 page 가 hot 인가?
  • Page migration strategy: 어떻게 page 를 옮길것인가?
• 위의 두개의 역할은 Colloid 에서는 담당하지 않고, 기존의 tiered memory system 들에서 담당한다.
• 즉, Section 4 에서는 기존의 SOTA tiered memory system 인 HeMem, MEMTIS, TPP 들에 Colloid 를 통합시키는 implementation detail 에 대해 설명한다.
• 구체적으로는, 위의 세 system 에 다음의 것들을 추가적으로 구현하는 과정에 대해 설명한다:
  • 각 system 에 대한 latency measurement 구현
  • 각 system 에 대한 page placement algorithm 구현
  • 어떤 page 를 migration 할 것인가
    • 즉, 각 page 들의 access probability ($p$) 를 구하여 어떤 page 를 migration 할 것인지 결정
• 그리고 다음의 것들은 기존의 것들을 그대로 사용한다.
  • 각 system 들의 access tracking 방식
    • 이 부분에서 Colloid 의 access probability 와 좀 헷갈릴 수 있는데,
    • Page 의 access tracking 하는 것은 기존의 방식을 사용하고, Colloid 에서는 이 access tracking 을 통해 알아낸 정보들로 access probability 를 계산하여 latency balancing 을 하는 것이다.
  • 각 system 들의 page migration strategy 방식 (어떻게 옮길것인가? 언제 옮길것이냐? 등)

4.1. HeMem with Colloid §

• HeMem 의 작동 과정을 간단히 살펴보면
  1. Busy-polling thread 를 이용해 일정 기간마다 (fixed sampling rate) Processor Event Based Sampling, PEBS 를 측정하여 page 별 access frequency 를 측정한다.
  2. 각 tier 에 있는 page 들에 대한 hot list 와 cool list 를 유지하고, PEBS 로 측정한 frequency 가 일정 threshold 를 넘으면 hot list 에 추가되는 방식이다.
     • 즉, 이말은 tier 별로 hot list 와 cool list 가 있는 셈이다.
  3. 그리고 이 측정한 frequency 에 대한 또 다른 threshold (COOLING_THRESHOLD) 가 있는데, 어떤 page 가 이 threshold 에 도달하게 되면 모든 page 의 frequency 가 절반이 되는 식으로 cooling 이 이루어진다.
  4. Page migration 은 별도의 thread 로 10ms 의 fixed quantum 마다 asynchronous 하게 진행된다.
• 여기서 Colloid 를 위한 추가 구현 사항은 다음과 같다.
  • Latency 를 측정하는 것은 (4) 번에서의 page migration thread 에서 담당한다.
    • 즉, (4) 번 thread 에서 10ms 마다 page migration 을 할 때 CHA 를 읽어들여 queue occupancy 와 request rate 를 측정하는 것.
  • Colloid 의 page placement algorithm 또한 (4) 번 thread 에 구현된다.
    • 즉, Section 3 에서 말한 대로 $\Delta p$ 를 계산하고,
    • (1) 번에서 PEBS 로 측정한 per-page frequency 를 이용해 per-page access probability 를 계산한다.
      • 구체적으로는 HeMem 에서 PEBS 로 per-page frequency 를 측정하였으니,
      • Per-page frequency 를 모든 frequency 의 총합으로 나누어 per-page access probability 를 계산하는 것이다.
    • 그리고 이렇게 구한 per-page access probability 를 이용해 $\Delta p$ 를 맞추기 위한 page 들을 선정한다.
      • 이때 더 효율적으로 page selection 을 하기 위해 HeMem 와 좀 다른 list 들을 관리한다.
      • HeMem 에서는 0 ~ COOLING_THRESHOLD 까지의 frequency 범위를 두개로 나눠 높은 쪽에 들어가는 page 들은 hot list 로 관리하고 낮은 쪽에 들어가는 page 들은 cool list 로 관리했다면,
      • Colloid 에서는 이 frequency 범위를 5등분한 bin 이라는 범위 단위를 이용해 5개의 list 로 관리한다.
      • 그래서 높은 범위에 대한 bin 부터 뒤지며 page 들의 $p$ 합이 $\Delta p$ 보다 작거나 갖게 되도록 하는 식으로 page 들을 고르게 된다.
      • 즉, 이것은 page migration overhead 를 최소화 하기 위해 자연스레 $p$ 를 정렬하는 효과를 가진다: $p$ 가 높은애들부터 확인하여 $p$ 의 총합이 $\Delta p$ 보다는 작거나 같으면서도 최소한의 page 들을 migration 하게 된다.

4.2. MEMTIS with Colloid §

• MEMTIS 는 HeMem 과 유사하지만, 다음의 차이점이 있다고 한다:
  1. HeMem 의 (1) 번에서는 일정기간마다 (fixed sampling rate) PEBS 를 측정했지만, MEMTIS 에서는 가변 기간 (dynamic sampling rate) 을 사용한다.
  2. HeMem 의 (2) 번에서는 고정된 threshold 로 hot, cold 를 구분했지만 MEMTIS 에서는 가변 threshold 를 사용한다.
  3. HeMem 의 (4) 번에서는 하나의 thread 가 page migration 을 진행했지만, MEMTIS 에서는 tier 마다의 thread 인 kmigraterd 들이 page promotion 과 demotion 을 진행한다.
  4. 마지막으로 MEMTIS 에서는 Transparent Hugepages 를 이용한다: 특정한 heuristic 에 따라, background thread 가 page 들을 hugepage 로 합치고 kmigraterd 가 (hugepage 를 사용하는 것이 효과적이지 못할 경우에) hugepage 를 다시 page 로 분리한다.
• 이때, Colloid 는 다음과 같이 구현된다.
  • MEMTIS 의 (1) 번은 Colloid 와는 무관한 변화이기 때문에, HeMem 에서와 동일한 방식으로 per-page access probability 를 구한다.
  • MEMTIS 의 (2) 번의 경우에는 HeMem + Colloid 처럼 bin 을 사용하지 않고, 그냥 MEMTIS 의 hot, cold list 를 그대로 사용해 per-tier hot list 를 scan 하는 것으로 $\Delta p$ 를 채울 page 들을 고른다.
    • 즉, promotion 할 때는 alternate tier 의 hot list 를 scan 하고, demotion 할 때는 default tier 의 hot list 를 scan 한다.
  • Page placement algorithm 은 alternate tier 쪽의 kmigraterd 를 변형하여 구현했다.
    • 즉, default tier 쪽의 kmigraterd 는 수정하지 않았다 ¹.
  • Hugepage 와 관련해서는, Migration limit 을 계산할 때 각 page 의 크기를 같이 고려해 주도록 했다 ².

4.3. TPP with Colloid §

• TPP 의 작동 과정은 간단하게는 다음과 같다:
  1. TPP 에서는 주기적으로 process page table 에 protection bit 를 키는 작업을 해주고 (이때의 시간을 $T_m$ 이라고 하자), 뒤이어 이 page 에 access 될 때는 page fault 가 발생하도록 한다 (이때를 hint fault 라도고 하며, 이때의 시간을 $T_f$ 라고 하자).
  2. 그리고 이 두 시간의 차이 (즉, $T_f-T_m$ 이고 이것은 time-to-fault 라고 부른다) 가 특정 threshold 보다 클 때 page 를 hot 이라고 판단한다.
  3. Alternate tier 의 page 에서 hint fault 가 발생했을 때, 위의 time-to-fault 를 계산하여 이 page 가 hot 일때 default tier 로 promotion 하는 작업을 synchronous 하게 실행한다.
     • 즉, hint fault 는 alternate tier 에서만 발생한다.
  4. Cold page 를 default tier 에서 alternate tier 로 demotion 하는 것은 기존의 kswapd watermark 를 이용하고, demotion page 를 결정하는 것은 저 protection bit 을 이용해 관리되는 kernel 의 inactive list 를 이용한다고 한다.
• 이때, Colloid 는 TPP 에 다음과 같이 적용된다:
  • 일단 latency measurement 는 별도의 kernel module 로 구현되어 이놈의 thread 가 주기적으로 CHA counter 를 polling 하여 kernel 에게 노출시키는 방식으로 구현된다.
    • 즉, 이때 HeMem 에서처럼 하나의 core 를 이 용도로 사용하게 된다 ³.
  • Per-page access probability ($p$) 는 (2) 번의 time-to-fault 를 이용해 계산된다.
    • 우선 직관적으로 이해해 본다면, $p$ 가 크다면 더 빈번하게 접근되므로 time-to-fault 는 작아지게 되고, 반대로 $p$ 가 작다면 time-to-fault 는 작아지게 된다.
    • 수식으로 보면,
      • Access probability 가 $p$ 인 page 가 있을 때, 그것은 이 page 가 전체 access 중에 $p$ 의 비율로 access 된다는 것이므로 $\frac{1}{p}$ 번의 access 중에 한번은 이 page 인 것으로 생각할 수 있다.
      • 예를 들어 보면, 만약 $p$ 가 0.25 라면 전체 100 번의 access 중에 25 번의 access 는 이 page 에 대한 것이고, 따라서 이 page 는 4번중에 한번 access 되는 것을 생각할 수 있다는 것.
      • 그리고 $r$ 을 해당 page 가 속한 tier 의 access rate (즉, $R_D$ 혹은 $R_A$) 이라고 했을 때, $r$ 은 해당 tier 의 access 횟수를 단위시간으로 나눈 것이므로 $\frac{1}{r}$ 은 각 access 가 request 되는 시간 간격의 평균이라고 할 수 있다.
      • 정리해 보면 어떤 page 는 평균적으로 $\frac{1}{p}$ 번마다 한번씩 access 되고, 각 access 가 request 되는 시간은 $\frac{1}{r}$ 이기 때문에 이 둘을 곱한 $\frac{1}{p\cdot r}$ 은 어떤 page 가 access 되는 시간간격 $\Delta t$ 이라고 할 수 있다.
      • 그리고 $\Delta t$ 가 바로 TPP 에서의 time-to-fault 가 되기 때문에, 수식을 정리해 보면 $p=\frac{1}{\Delta t\cdot r}$ 이 된다.
  • Page placement algorithm 은 hint fault handler 를 수정하는 것으로 구현된다.
    • Alternate tier 에서 hint fault 가 발생하면 기존의 TPP 에서는 무조건 promotion 을 시키지만, TPP + Colloid 에서는 $L_D<L_A$ 일 때만, 그리고 이 page 의 $p$ 가 계산된 $\Delta p$ 보다 작을 때만 수행한다.
    • 그리고 TPP + Colloid 에서는 default tier 에 대해서도 $p$ 를 계산하기 위해 hint fault 를 발생시키는데 ⁴, alternate tier 에서와 마찬가지로 $L_A<L_D$ 일 때만, 그리고 이 page 의 $p$ 가 계산된 $\Delta p$ 보다 작을 때 hot page demotion 을 수행한다.
  • 그리고 cold page demotion 은 기존의 TPP 에서처럼 kswapd 의 방식을 그대로 사용한다.

Footnotes §

1. Demotion 할때는 default tier 의 hot list 를 scan 해야 하는데, 이것이 default tier 의 kmigraterd 를 수정하지 않고도 가능한지 code 로 확인해 봐야 한다. ↩

2. 이것도 수식이 어떻게 바뀌는지 code 로 확인해 봐야 한다. ↩

3. HeMem 의 (4) 번 thread 를 의미하는 것 같은데, 이것은 MEMTIS 에서도 동일하게 필요할 것으로 보이는데 논문에서는 HeMem 만 언급했다: “This requires dedicating one core similar to vanilla HeMem”. ↩

4. 근데 이러면 성능상의 저하가 있지 않을까 싶다. Hot page 의 경우에는 빈번하게 접근되는데, 이놈의 access probability 를 계산하기 위해 빈번하게 page hint fault 가 발생해서 kernel mode 로 진입하게 된다면 그만큼 overhead 가 발생하는데 이것에 관한 언급은 논문에 없었다. ↩