(논문) Tiered Memory Management: Access Latency is the Key!, SOSP'24 (3. Colloid)

본 글은 논문 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

3.0. Overview §

NXSECTION

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

• 본 section 에서는 Colloid 의 전체적인 design 을 다룬다.
• 일단 Section 3.1 에서는 Colloid 의 유일한 원칙인 “Balancing latency” 와 Memory Interconnect Contention 에 대해 구체적으로 살펴보고, Section 3.2 에서는 Colloid 의 page placement algorithm 에 대해서 알아본다.

• 고려한 tiered memory system architecture 는 위 그림과 같다.
  • 모든 tier 의 메모리는 CPU 의 physical address space 에 노출되고, LOAD 나 STORE 등의 instruction 으로 cache coherence 한 방식으로 접근이 가능하며, 동일한 memory consistency model 을 사용한다.
  • 가장 unloaded latency 가 작은 tier 를 default tier 라고 부르고, 나머지는 전부 alternate tier 라고 부른다.
  • 각 tier 는 별도의 controller 에 의해 관리된다.
• 이러한 architecture 는 대부분의 tiered memory system 에서 흔하게 사용하는 방식이다:
  • 보통 default tier 는 DDR memory 이고, memory controller 에 의해 관리된다.
  • 그리고 alternate tier 는 CXL 이나 HBM 등으로 구성될 수 있다.
• Colloid 는 fixed time period 인 Quantum 마다 동일한 작업을 하는 것을 기준으로 design 되었다.
  • 하지만 Section 4 에서도 설명하겠지만, 이런 periodical 한 방식으로 운영되지 않는 tiered memory system (가령 TPP 등) 에도 통합할 수 있다고 한다.

3.1. Access Latency is the Key §

3.1.0 Understanding the principle of “Balancing the access latency” §

NXSECTION

• 3.1.0 은 주인장이 편의상 naming 한 것으로, 논문에는 이런 section 은 없다.

• 용어정리를 좀 해보자.
  • Memory Request 는 core 의 memory access 중에서, 모든 cache 에서 miss 가 나서 default 혹은 alternate tier 에서 serving 되는 것을 말한다.
  • Unloaded Latency 는 memory request 가 단 하나 있을때의 memory access latency 를 뜻한다.
  • Loaded Latency 는 여러개의 concurrent 한 memory request 가 있을 때의 access latency 를 뜻한다.
  • Memory Interconnect Contention 은 다음의 두 상황에 의해 Loaded Latency 가 Unloaded Latency 보다 커지는 것을 의미한다.
    • 일단 CPU-memory 간의 BW 가 saturate 되어서 memory request 가 queueing 될때 발생할 수 있다.
      • BW 가 saturate 되었을 때의 utilization 은 사전에 알아내기 힘든데, 이것은 request 가 read 이냐 write 이냐에 따라 달라지고, theoretical max. BW 보다 2.5 배나 더 작은 경우도 있기 때문이라고 한다 ¹.
    • 그리고 BW 가 saturate 되지 않아도, controller 에 contention 이 발생할 수도 있다.
      • 가령 DRAM 은 여러개의 bank 들로 구성되어 있는데, 이 bank 들에 Locality 가 부족하게 무작위적으로 접근하면 controller 내에서의 queue 또한 가득 차서 이런 contention 이 발생할 수도 있다고 한다 ².
  • Access Probability 는 page 에 대한 접근 비율로 Quantun 시간 내에서 전체 memory request 개수 대비 해당 page 에 접근하는 memory request 의 비율을 의미한다.
• 이때,
  • $L_D$ 와 $L_A$ 는 각각 default tier 와 alternate tier 에 대한 latency 를 의미하고
  • $p$ 는 default tier 에 대한 모든 page 의 Access Probability 의 총합이라고 해보자.
• 그럼 “Balancing access latencies” 는 다음과 같이 정의할 수 있다.
  • 만약 $L_D<L_A$ 라면, $p$ 를 증가시키는 방향으로 page placement 가 이루어져야 한다.
    • 당연히 default tier 의 latency 가 작다는 의미이므로 default tier 에 hot page 를 더 많이 배치해 $p$ 를 늘려야 한다.
  • 만약 $L_D>L_A$ 라면, $p$ 를 감소시키는 방향으로 page placement 가 이루어져야 한다.
    • 마찬가지로, 이것은 default tier 의 latency 가 크다는 의미이므로 alternate tier 에 hot page 를 더 많이 배치해 $p$ 를 줄여야 한다.
  • 만약 $L_D=L_A$ 라면, optimal 한 상태이므로 추가적인 page placement 가 필요하지 않다.
• 그럼 “Balancing access latencies” 이 왜 application 의 성능을 최대로 뽑아내는 것에 중요한지, 그리고 이를 위해서는 왜 각 상황에서 $p$ 를 저렇게 조정해야 하는지를 생각해 보자.
  • Memory 를 많이 사용하는 application 의 경우에는, memory throughput 에 의해 그의 성능이 결정된다.
  • 이때, memory throughput 은 Section 2 의 64byte object 에 접근하는 workload 에 비추어 생각하면 $\frac{N\times 64}{L}$ 이고, 이때 $N$ 은 core 당의 한번에 보낼 수 있는 memory request 의 최대치이므로 이 값은 최대치가 정해져 있다.
  • 따라서 memory throughput 은 average latency 와 반비례하는 방향으로 직접적으로 연결되어 있고, 따라서 application 의 성능도 직접적으로 영향을 받게 된다.
  • Average latency 는 다음처럼 구할 수 있다: $p\times L_D+(1-p)\times L_A$.
  • 이 수식은 정리하면 $p\times (L_D-L_A)+L_A$ 가 되는데, 만약에 $L_D<L_A$ 라면 $L_D-L_A<0$ 이기 때문에 $p$ 를 늘려야 해당 수식의 값이 작아질 것이다.
  • 마찬가지로, $L_D>L_A$ 라면 $L_D-L_A>0$ 이기 때문에 $p$ 를 줄여야 해당 수식의 값이 작아지게 되는 것.
• “Balancing access latencies” 의 원칙은 다음의 metric 들이 자연스레 녹아들어 unified approach 를 가능하게 만들어 준다.
  • 이 원칙에는 Unloaded Latency 가 자연스럽게 반영된다. 왜냐면 default 와 alternate 간의 Unloaded Latency 차이가 크다면 default tier 에 Memory Interconnect Contention 이 발생해도 여전히 default tier 의 latency 가 작을 것이고, 따라서 default tier 에 page 가 배치될 것이기 때문이다.
    • 이렇게 생각하면 된다: Unloaded Latency 는 Loaded Latency 의 초기값이기 때문에, 당연히 Loaded Latency 를 balancing 하는 것에는 Unloaded Latency 에 대한 고려가 들어가게 되는 것.
  • 또한, 각 tier 의 maximum BW 또한 고려된다. 왜냐면 BW 가 높다면 BW saturation 이 잘 발생하지 않아 Loaded Latency 가 작게 나올 것이기 때문이다.
    • 즉, maximum BW 는 Loaded Latency 에 영향을 주는 요소이기 때문에 이것 또한 반영된다는 것.
  • 마지막으로, 위에서 말한 controller contention 도 반영이 된다. Controller contention 이 발생하면 마찬가지로 Loaded Latency 가 증가하기 때문.
    • 즉, 마찬가지로 controller contention 또한 Loaded Latency 에 영향을 주는 요소이기 때문에 자연스에 반영되게 된다.
• 이런 balancing approach 는 두개 이상의 tier 를 가진 system 에도 적용시킬 수 있다.
  • Latency 가 가장 작은 tier 에 page 를 더 배치해서 latency 를 늘리면, 동시에 다른 tier 에서는 (page 를 뺏겼으므로) latency 가 줄어들 것이다.
  • 다음에는 마찬가지로 두번째로 latency 가 작은 tier 에 page 를 배치해 latency 를 늘리면 마찬가지로 다른 tier 에서도 latency 가 줄어들게 된다.
  • 이런 작업을 recursive 하게 하다 보면 모든 tier 들 간의 latency 가 평준화되고, memory throughput 은 최대가 되는 것이다.

3.1.1. Measuring access latency §

• 우선 memory 의 throughput 을 결정하는 request 는 read request 이고, 따라서 Colloid 에서는 read latency 만을 측정한다고 한다.
  • 왜냐면 대부분의 CPU 에서는 Write allocate 이기 때문에 memory 에서 읽어와서 cache 에 올린 다음 write 를 하기 때문.
  • Cache 에 있는 데이터가 memory 에 쓰이는 것은 write back 될때로, asynchronous 하기 때문에 실제로 memory 에 write request 가 오는 경우는 read 에 비해서는 아주 적다고 생각하면 된다.
• Latency 를 측정하는 방법으로는, CHA 를 이용한다.
  • 요즘의 CPU 들은 이러한 HW counter 들을 다 가지고 있고, Colloid 는 Intel 의 memory access counter 인 CHA 를 사용하는 것.
  • CHA 에 대해서 간단히 살펴보면:
    • 이놈은 tiered memory 에 대한 abstraction 으로, tiered memory 에 대한 caching 과 cache coherence 등을 제공해준다.
    • CHA 는 각 core 마다 slice 라는 이름으로 partitioning 되어 있고, 이들 각각이 physical address space 의 각기 다른 부분을 담당한다.
    • 작동 과정은 다음과 같다:
      • L1 cache 와 L2 cache 에 miss 가 뜨면, 해당 memory request 는 physical address 에 맞는 CHA slice 에게로 오게 된다.
      • CHA slice 는 자신의 L3 cache 를 확인하고, 거기에 없으면 request queue 에 넣은 뒤 해당 physical address 에 맞는 tier 로 request 를 보낸다.
      • 그리고 해당 request 가 응답되면, 상위계층으로 보내고 request queue 에서 지운다.
  • 이런 CHA 에서는 queue occupancy 와 request arrival rate 를 request type (read, write) 와 tier 별로 알려주는 counter 가 존재하고, Colloid 에서는 이것을 사용하게 된다 ³.
  • 이 CHA counter 를 통해 저러한 정보들을 1ms 정도의 적은 overhead 로 알아낼 수 있다고 한다.
    • 그리고 이정도의 시간은 page placement 를 결정하는 것보다 훨씬 빠른 속도이기 때문에, fine-grained measurement 가 가능하다고 한다.
• 그럼 이제 CHA 가 노출하는 정보들로 latency 를 구하는 방법을 알아보자.
• 일단 $O_D$ 와 $O_A$ 를 CHA 를 통해 알아낸 default tier 와 alternate tier 의 queue occupancy 라고 해보자.
• 그리고 $R_D$ 와 $R_A$ 를 CHA 를 통해 알아낸 arrival rate 라고 해보자.
  • 여기서 Arrival Rate 라는 것은 주어진 quantum 시간 내에서 응답이 온 request 를 quantum 시간으로 나눈 것이다.
  • 즉, 단위 시간 내의 response 의 개수인 것.
• 그럼 $p$ 는 다음과 같다.

$$p=\frac{R_D}{R_D+R_A}$$

• 그리고 Little’s Law 에 의해 $L_D$ 와 $L_A$ 다음과 같다.

$$L_D=\frac{O_D}{R_D},L_A=\frac{O_A}{R_A}$$

• 여기서 Little’s law 에 대해 간단히 알아보자.
  • 만약에 식당에 5시간동안 300명이 다녀갔고, 한 손님당 평균 10분씩 체류했다면, 특정 시점에서의 손님의 수의 평균은 다음과 같이 구할 수 있을 것이다:
    • 식당에 5시간동안 300명이 다녀갔으므로 시간당 손님은 60명이었을 것이다.
    • 만약에 식당에 자리가 1개였다면, 한시간동안 최대로 받을 수 있는 손님의 수는 (한명당 10분이므로) 6명이었을 것이다.
    • 근데 시간당 손님이 60명이 다녀가기 위해서는 식당은 10자리가 있고 한시간 내내 이 자리가 다 차있어야 한다.
    • 따라서 이것을 자리가 10개 이상 있는 대신 항상 자리가 다 채워지지 않는 상황으로 확장해 생각해 보면, 손님 수의 평균은 10명인 것으로 생각할 수 있다.
  • 이것을 Little’s law 수식으로 알아보면 다음과 같다.
    • 일단 손님 수의 평균을 $N$ 이라고 해보자.
      • 원래는 이 값을 나타내는 기호는 $L$ 이다. 근데 latency 랑 헷갈리니까 $N$ 으로 하자.
    • 그리고 시간당 손님수를 $\lambda$ 라고 해보자. 위의 예시에서는 이 값은 60 이다.
    • 마지막으로 손님의 체류 시간을 $W$ 라고 해보자. 위의 예시에서는 이 값은 $1/6$ (시간단위이므로) 이다.
    • 따라서 손님 수의 평균은 $N=\lambda \times W$ 가 된다. 이것이 Little’s law 이다.
  • 그럼 이것을 latency $L_D$, $L_A$ 를 구하는데 적용시켜 보자.
    • 그럼 request queue 가 식당이 되고, queue occupancy ($O$) 는 손님 수의 평균 ($N$), arrival rate ($R$) 는 시간당 손님수 ($\lambda$) 가 되며, latency ($L$) 는 손님의 체류 시간 ($W$) 가 된다.
    • 따라서 Little’s law 인 $N=\lambda \times W$ 는 우리의 경우에는 $O=R\times L$ 가 된다.
    • 결과적으로 $L=\frac{O}{R}$ 라는 수식이 나오게 되는 것.
  • 참고로 Little’s law 는 가게의 자리수가 한정되어있는 경우에 대해서만 적용할 수 있다고 한다. 근데 queue 의 길이는 한정되어 있으므로 Little’s law 가 잘 맞아들어간다고 볼 수 있다.
    • 이렇게 Little’s law 로 latency 를 구하는 것은 저자의 또 다른 논문 Understanding Host Network, SIGCOMM’24 에서 validation 되어 있다고 한다.
• 그럼 여기서 빠진게 하나 있는데, 바로 CPU-CHA 간의 latency 이다. 근데 이건 너무 작아서 무시해도 된다고 한다.
  • 실험 결과, CPU-CHA 간의 latency 는 CPU-memory 간의 unloaded latency 70ns 중에서 5ns 밖에 안된다고 한다.
  • 또한 loaded latency 로 가면 전체 latency 에서의 5ns 가 미치는 영향은 아주 적을 것이다.
• 참고로 각 occupancy 와 arrival rate 는 Exponentially Weighted Moving Averaging (EWMA) 이라는 것으로 보정하여 noise 를 줄였다고 한다 ⁴.

3.2. Colloid Page Placement Algorithm §

3.2.1. Overview of the Colloid page placement algorithm §

• 위의 그림이 Colloid 에서의 placement algorithm 이다.
• 우선, 이전 quantum 에서의 $O_D$ 와 $O_A$, $R_D$, $R_A$ 를 측정하고 그것으로 $L_D$ 와 $L_A$, $p$ 를 계산한다.
• 그리고 promotion (default to alternate tier) 할지, 아니면 demotion (alternate to default tier) 할지를 결정한다.
  • 이건 “balancing access latency” 의 원칙에 따라 단순하게 $L_D$ 와 $L_A$ 를 비교하기만 하면 된다.
• 다음에는 어떤 page 를 migrate 할지를 정하는데, 이것은 다음의 세 단계로 이루어진다.
  • 우선 $p$ 를 얼마나 조정할지를 결정한다. 이것은 $ComputeShift()$ 를 통해 결정되며, 기호는 $\Delta p$ 이다.
    • 다만 알아야 할 것은 $p$ 는 측정값이기 때문에, 이 $\Delta p$ 값은 원하는 (desirable) $p$ 의 변화량이다.
    • 즉, $p$ 가 이만큼 바뀌었으면 좋겠다 인것이고, 실제로 저만큼 바뀌지 않을 수도 있다는 것.
    • 이에 대해서는 Section 3.2.2 에서 다뤄보자.
  • 다음으로는 migration limit 을 구하는 것이다.
    • Migration limit 이 있는 이유는 page migration 작업 자체에 대해서도 memory traffic 이 발생하기 때문에 너무 많은 양을 옮기지는 못하기 때문이다.
    • 이것은 $min(\Delta p(R_D+R_A))$ 로 결정되는데, 구체적으로 이게 뭔지는 Section 3.2.3 에서 알아보자.
  • 마지막으로는 실제 page migration system (HeMem 등) 으로 page migration 을 수행하게 된다.
    • 여기서는 다음의 두가지 제약조건이 있다.
      • 옮기려는 page 의 access probability 의 총합이 $\Delta p$ 보다 작거나 같아야 한다.
        • 당연히 $\Delta p$ 만큼을 옮기는 것이 목표이므로 $\Delta p$ 와 같으면 좋겠지만, 만약 모든 page 를 전부 옮겨도 해당 수치를 못맞추는 경우에는 어쩔 수 없이 옮길 수 있는 만큼만 옮기게 된다.
      • 옮기려는 page 의 총 크기가 migration limit 을 넘으면 안된다.
    • 이 algorithm 을 HeMem 와 같은 system 에 적용시키는 것은 Section 4 에서 다뤄보자.

3.2.2. Desired shift in per-tier access probability §

NXSECTION

• 3.2.2.x 은 주인장이 편의상 section 을 나눈 것으로, 논문에는 이런 section 은 없다.

3.2.2.1. Algorithm Overview §

• 기존의 HeMem, MEMTIS, TPP 등과 같은 system 에서는 “얼마나 옮겨야 될까?” 의 문제가 없었다. 그냥 최대한 많이 옮기면 되기 때문.
• 하지만 Colloid 에서는 latency balancing 을 해야 하기 때문에, 이 “얼마나 옮겨야 할까?” 의 문제가 중요하다.
  • 만약에 너무 많이 옮겨버리게 된다면 optimal 한 $p$ (즉, latency 가 평행상태가 되는 $p$ - Equilibrium point) 에 딱 맞지 않고 주변에서 요동치게 될 것이다.
  • 반면에 너무 적게 옮기게 된다면 optimial $p$ 까지 접근하는데 너무 오래 걸려 steady state 가 될 때까지 시간이 오래 걸리게 될 것이다.
• 따라서 Colloid 에서는 per-tier access probability 를 이용해 이 “얼마나 옮겨야 할까 - $\Delta p$” 를 구한다.

• 위의 그림이 바로 이 $\Delta p$ 를 구하기 위한 algorithm 인데, binary search 와 유사한 과정으로 찾아간다.
• 일단 여기서는 두개의 watermark 가 사용된다: $p_{hi}$ 하고 $p_{lo}$.
  • $p_{hi}$ 는 $p$ 에 대한 upper bound 이다. 의미론적으로 보자면, 이 수치는 ”$p$ 가 이 값이라면 default tier 의 latency 는 alternate 의 그것보다 아마도 작을 것이다” 의 의미를 가진다.
    • 즉, 작을수도 있고 아닐 수도 있다는 것.
    • 따라서 이 값은 1로 초기화되는 것이 합리적이다.
  • $p_{lo}$ 는 $p$ 에 대한 lower bound 이다. 의미론적으로 보자면, 이 수치는 ”$p$ 가 이 값이라면 default tier 의 latency 는 alternate 의 그것보다 반드시 작을 것이다” 의 의미를 가진다.
    • 따라서 이 값은 0 으로 초기화되는 것이 합리적이다.
• 만약에 optimal $p$ (equilibrium point) 인 $p^{\ast }$ 가 있다면, 이것은 $p_{lo}$ 와 $p_{hi}$ 사이 ($p_{lo}\le p^{\ast }\le p_{hi}$) 사이에 있을 것이다.
  • 따라서 Colloid 는 $p_{lo}$ 와 $p_{hi}$ 사이의 간격을 좁혀가며 저 $p^{\ast }$ 를 찾는 방식으로 작동한다.
• 구체적으로는 다음과 같다:
  • 만약 default tier 의 latency 가 더 작다면, $p$ 를 키워야 할 것이다. 따라서 $p_{lo}$ 를 $p$ 로 설정하고, $p$ 를 $p_{lo}$ 와 $p_{hi}$ 의 중간값으로 설정된다.
    • 위의 수식에서 $|\frac{p_{lo}+p_{hi}}{2}-p|$ 이 바로 이 의미이다. 마지막에 $p$ 를 빼주는 이유는 이 수식이 구하는 것이 $p$ 의 변화량 ($\Delta p$) 이기 때문.
  • 마찬가지로, 만약 default tier 의 latency 가 더 크다면, $p$ 를 줄여야 할 것이다. 따라서 $p_{hi}$ 를 $p$ 로 설정하고, $p$ 를 $p_{lo}$ 와 $p_{hi}$ 의 중간값으로 설정한다.
• 다만 저 $\delta$ 와 $ϵ$ 는 일단 무시하자. 뒤에 설명이 있다.

3.2.2.2. Static workload §

• 여기까지 와서, static workload 에서 이 방식이 잘 통용될지 보여주는 것이 아래 그림이다.
  • 물론 이것은 이론적인 것일 뿐이고, 실제로 $p$ 가 저렇게 측정되리라는 보장은 없다. 그냥 $p$ 가 측정값이 아니라 계산값이라는 전제 하에 $p$ 가 $p^{\ast }$ 를 잘 쫒아가나를 보자.

• 일단 저 초록색 선이 equilibrium point 인 $p^{\ast }$ 일때, 그 위로는 default tier latency 가 더 높고, 아래로는 alternate tier latency 가 더 높다고 해보자.
  • $t=0$ 일 때는 $p_{hi}=1$, $p_{lo}=0$ 로 init 되고 $p=0$ 라고 해보자. 그럼 $\Delta p=0.5$ 로 계산된다.
  • $t=1$ 일 때는 이전의 $\Delta p=0.5$ 가 반영되어 $p=0.5$ 가 된다.
    • 따라서 $L_D>L_A$ 이므로 $p_{hi}=p=0.5$ 가 되고, $p_{lo}=0$ 으로 유지된다.
    • 결과적으로 $\Delta p=0.25$ ($|\frac{0+0.5}{2}-0.5|$) 로 계산된다.
  • $t=2$ 일 때는 이전의 $\Delta p=0.25$ 가 반영되어 $p=0.25$ 가 된다.
    • 이번에는 $L_D<L_A$ 이므로 $p_{lo}=p=0.25$ 가 되고, $p_{hi}=0.5$ 으로 유지된다.
    • 결과적으로 $\Delta p=0.125$ ($|\frac{0.25+0.5}{2}-0.25|$) 로 계산된다.
  • $t=3$ 일 때는 이전의 $\Delta p=0.125$ 가 반영되어 $p=0.375$ 가 된다.
    • 이번에는 $L_D>L_A$ 이므로 $p_{hi}=p=0.375$ 가 되고, $p_{lo}=0.25$ 으로 유지된다.
    • 결과적으로 $\Delta p=0.0625$ ($|\frac{0.25+0.375}{2}-0.375|$) 로 계산된다.
  • $t=4$ 일때는 이전의 $\Delta p=0.0625$ 가 반영되어 $p=0.3125$ 가 된다.
• 이런식으로 가다 보면 $p$ 가 점점 $p^{\ast }$ 에 근접해 간다는 것을 알 수 있을 것이다.
  • 이것은 $p_{lo}\le p\le p_{hi}$, $p_{lo}\le p^{\ast }\le p_{hi}$ 가 항상 만족하며 $p_{lo}$ 와 $p_{hi}$ 의 간격이 점점 좁아지기 때문에 $p$ 가 $p^{\ast }$ 으로 수렴하는 것이라고 생각할 수 있다.

3.2.2.3. Dynamic workload - Changing access pattern §

• 다음으로는 dynamic workload 에서의 변화 과정에 대해 알아보자. 즉, 상황이 바뀌었을때 어떻게 반응할 것인가?
• 상황이 바뀌는 경우의 수는 크게 두 가지이다.
  1. Access pattern 이 달라지는 경우.
     • 즉, memory request 의 양은 동일하지만 hot, cold 영역이 달라지는 것이므로 순간적으로 $p$ 가 튀어 $p_{lo}\le p\le p_{hi}$ 가 위반되게 된다.
  2. Memory interconnect contention 이 발생하는 경우.
     • 이때는 workload 의 memory request 의 양이 달라지거나, 아니면 Section 2 에서처럼 antagonist 가 나타나 workload 와 무관하게 추가적인 memory request 가 발생하는 경우이다.
     • 즉, 이때는 $p^{\ast }$ 가 바뀌어 $p_{lo}\le p^{\ast }\le p_{hi}$ 가 위반된다.
     • 이것에 관해서는 Section 3.2.2.4 에서 알아보자.
• 우선 첫번째 경우에 어떻게 변화하나 살펴보자.

• 위 그림이 $t=3$ 에서 갑자기 access pattern 이 바뀌어 $p=0.725$ 로 튀었을 때의 변화 과정이다.
  • $t=2$ 까지는 $p_{lo}=0.375$, $p_{hi}=0.375$, $p=0.375$ 였다고 해보자.
  • 그리고 $t=3$ 에서 갑자기 access pattern 이 바뀌어 $p=0.725$ 로 튄다.
    • 그럼 이때는 $L_D>L_A$ 가 되므로 $p_{hi}=p=0.725$ 로 바뀌어 $\Delta p=0.175$ ($|\frac{0.725+0.375}{2}-0.725|$) 로 계산된다.
  • 따라서 $t=4$ 에서는 이전의 $\Delta p$ 가 반영되어 $p=0.55$ 가 되고, 하지만 여전히 $L_D>L_A$ 이므로 $p_{hi}=p=0.55$ 로 바뀌어 $\Delta p=0.0875$ ($|\frac{0.375+0.55}{2}-0.55|$) 로 계산된다.
  • 마찬가지로 $t=5$ 에서는 이전의 $\Delta p$ 가 반영되어 $p=0.4625$ 가 되며 점점 원래의 $p^{\ast }=0.375$ 에 근접하게 복귀한다.
• 따라서 access pattern 이 바뀌어 $p_{lo}\le p\le p_{hi}$ 이 위반되는 경우에도 정상적으로 원래의 $p^{\ast }$ 에 수렴하는 것을 알 수 있다.
  • 이것은 quantum 이 시작될 때 $\Delta p$ 를 계산하기에 앞서 $p_{hi}=p$ 로 보정되기 때문에, $p_{lo}\le p\le p_{hi}$ 을 위반한 상태가 곧바로 위반하지 않은 상태로 복구되고, 따라서 이후의 과정은 static workload 에서와 동일한 방법으로 $p^{\ast }$ 으로 수렴되는 것이라고 이해할 수 있다.

• 이에 대한 작동 과정을 나타낸 것이 위의 그림이다.
• 만약 $t=3$ 에서 $p^{\ast }$ 가 바뀐다면, latency 간의 차이는 커질 것이고, 근데 $p_{hi}$ 와 $p_{lo}$ 간의 차이는 작을 것이기에 초기화 logic 에 걸려 $p_{hi}=1$ 로 초기화된다.
• 이후에는 기존과 동일한 logic 으로 바뀐 $p^{\ast }$ 를 찾아가게 된다.

3.2.2.4. Dynamic workload - Changing equilibrium point §

• 그 다음에는 두번째 경우인 memory interconnect contention 이 발생하는 경우에 대해 알아보자.
• 이번에는 좀 문제가 있다: 위의 알고리즘으로는 $p_{lo}\le p\le p_{hi}$ 가 유지되기 때문에, 만일 $p^{\ast }$ 가 $p_{hi}$ 보다 커지거나 $p_{lo}$ 보다 작아지게 된다면 $p$ 가 $p^{\ast }$ 를 쫒아갈 수 없게 된다 ⁵.
• 따라서 이런 상황을 위해 추가적인 처리가 필요한데, 그게 바로 이 부분이다:

• 여기서 보면 일단 2번째 줄에서 $L_D$ 와 $L_A$ 의 차이가 $\delta \cdot L_D$ 보다 작으면 $\Delta p$ 를 0으로 지정하는 것을 확인할 수 있다.
• 그 다음에 5와 6번째 줄에서 $p_{hi}-p_{lo}<ϵ$ 일 때는 $L_D$ 와 $L_A$ 에 따라서 $p_{hi}=1$ 이나 $p_{lo}=0$ 로 초기화해준다는 내용이 있다.
• 이 말뜻은 $L_D$ 와 $L_A$ 의 차이가 $\delta$ 로 결정되는 어떤 값보다 작으면 차이가 없는 것을 간주되는데, 만약 이 기준 하에서 차이가 있는 것으로 간주되지만 $p_{hi}$ 와 $p_{lo}$ 간의 차이는 $ϵ$ 보다 작다면 $p_{hi}$ 혹은 $p_{lo}$ 를 초기화한다는 것이다.
• 이 말은 즉, latency 간의 차이가 있지만 두 watermark 간의 차이는 아주 작다는 의미이므로 $p^{\ast }$ 가 두 watermark 사이에 존재하지 않는다는 것을 걸러내는 것이다.
  • 즉, 반대로 생각하면 $p^{\ast }$ 가 $p_{hi}$ 와 $p_{lo}$ 사이에 있지 않다면 이들간의 차이가 아주 작아져도 latency 는 여전히 같지 않기 때문에 이때는 이 조건에 걸려 $p_{hi}$ 혹은 $p_{lo}$ 를 초기화해 $p_{hi}$ 와 $p_{lo}$ 간의 간격을 벌려 다시 $p^{\ast }$ 를 찾아갈 수 있게 하는 것이다.
• 그럼 이런생각을 할 수 있다: 그럼 $p_{hi}$ 와 $p_{lo}$ 이 좀 가까워지려고 하면 매번 초기화돼서 불안정하게 작동하는 것 아닌가?
  • 이를 위해 latency 가 같다고 판정하는 logic 을 먼저 둔 것이다 (즉, 2번째 줄).
  • $p_{hi}$ 와 $p_{lo}$ 가 가까워져서 latency 또한 차이가 줄어든다면 제대로 $p$ 가 $p^{\ast }$ 를 찾아가고 있는 과정이기 때문에 적당히 latency 간의 차이가 없어진다면 초기화 logic 까지 도달하지 않고 끝나게 해둔 것.
  • 근데 latency 가 줄어들지 않는데도 $p_{hi}$ 와 $p_{lo}$ 가 가까워지고 있다면 $p$ 가 잘못된 곳으로 가고 있다는 것이기 때문에 초기화를 해주는 것이다.
• 따라서 저 $\delta$ 와 $ϵ$ 값을 잘 조정할 필요가 있다는 것을 알 수 있다.
  • 이 두 값은 모두 configurable 한 static threshold 인데,
  • 만약 $\delta$ 가 너무 크다면 latency 를 같다고 판단하는 범위가 너무 넓어져 실제로는 latency 간의 차이가 꽤 나는데도 같다고 판단하게 된다.
    • 하지만 반대로 $\delta$ 가 너무 작다면 아직 latency 가 같다고 판단되기 이전에 초기화 logic 에 걸려버려서 다시 latency 차이가 커질 수 있다.
  • 또한 $ϵ$ 도 trade-off 가 있다: 만약에 이 값이 너무 크다면 마찬가지로 latency 가 같다고 판단되기 이전에 초기화 logic 에 걸려버리고,
    • 만약에 이 값이 너무 작다면 이 logic 에 걸리는데까지 시간이 너무 오래 걸려 $p^{\ast }$ 가 바뀌었을 때 반응시간이 커지게 된다.

3.2.3. Dynamic migration limit §

• Page migration 할 때는, 이놈이 발생시키는 memory traffic 도 고려를 해야 한다.
  • 만약 $\Delta p$ 가 0.01 일때 access probability 가 0.00001 인 page 1000 개를 migrate 한다면 저 $\Delta p$ 를 맞출 수는 있지만 ($0.00001\times 1000=0.01$) 4KB Page 1000 를 migrate 시키면 4MB 의 memory copy 가 발생하므로 memory interconnect contention 이 발생해 불안정해진다.
• 따라서 Dynamic migration limit 이 필요해진다.

• 이 부분이 Dynamic migration limit 을 계산하는 부분이다.
• Page migration 에 소요되는 memory request rate 를 $\Delta p(R_D+R_A)$ 로 지정해 놓는데, 이것이 무슨 의미인지 느낌만 잡아보자.
• 우선 $\Delta p$ 라는 것은 $p$ 의 변화량이므로 대략 이렇게 생각할 수 있다:

$$\Delta p=p_{want}-p_{now}$$

• 근데 $p$ 는 $\frac{R_D}{R_D+R_A}$ 이므로, 대략 이렇다고 생각할 수 있다.

$$\Delta p=\frac{R_D^{want}-R_D^{now}}{R_D+R_A}$$

• 따라서 $\Delta p(R_D+R_A)$ 는 다음과 같다.

$$\Delta p(R_D+R_A)=R_D^{want}-R_D^{now}$$

• 즉, default tier 에 대한 단위시간에서의 access rate 의 차이이다.
• 따라서 해당 limit 은 “앞으로 변화할 default tier 의 access rate” 정도 까지만 migrate 를 허용하겠다는 의미이다.
  • 즉, migration 이후에도 rate 가 이렇게 변할 테니 지금 그 정도의 rate 를 소모해서 migrate 를 하는 것은 인정해 주겠다 정도의 의미라고 생각하면 된다.
• 그리고 이 값또한 너무 커지는 경우에 대비하기 위해 추가적으로 $M$ 을 static configurable parameter 로 받아서 이 둘간의 최소값으로 migration limit 을 정하게 된다.

3.2.4. Selecting pages to migrate §

• Migration page 를 선택하는 것은 전적으로 기반하는 tiered memory system (가령 HeMem, MEMTIS, TPP 등) 에 맡기고, Colloid 는 “Balancing the access latencies” 의 원칙에 따라 단순히 promotion 할지 demotion 할지 ($mode$), 그리고 얼마나 옮길지 ($\Delta p$) 등을 결정하기만 한다.
• 따라서 어떤 page 를 선택하는가와 해당 page 를 실제로 migrate 하는 것은 해당 tiered memory system 을 사용한다.
• 다음 Section 에서 어떻게 이런 tiered memory system 들과 Colloid 를 통합하는지에 대해서 다뤄보자.

Footnotes §

1. 사실 잘 이해 안된다: “Memory bandwidth utilization at the saturation point is hard to characterize in advance since it can vary by as much as 1.75× depending on whether the workload is read-heavy or write-heavy, and be as much as 2.5× lower than the theoretical maximum bandwidth.” ↩

2. 이부분도 잘 이해는 되지 않는다: “For example, each DRAM module consists of multiple banks; load imbalance across these banks and lack of locality in access patterns within each bank can result in queueing of requests at the memory controller, leading to latency inflation.” ↩

3. 이부분 좀 더 찾아봐야할듯 ↩

4. 이게 뭔지는 모르겠는데 별로 중요한 내용은 아닌거 같으니 넘어가자. ↩

5. 근데 $p^{\ast }$ 가 변하면 $p$ 에도 영향이 미쳐서 Section 3.2.2.3 에서와 동일한 매커니즘으로 처리할 수 있지 않나 생각이 든다. 이부분은 좀 더 알아봐야 할듯 ↩