Redundant Memory Mappings for Fast Access to Large Memories

Redundant Memory Mappings for Fast Access to Large Memories 

위 논문을 읽고 정리한 내용입니다.

Notion에서 보기

---

Abstract

• page based virtual memory
  • memory utilization 향상
  • TLB miss로 인한 page table walks로 성능 저하TLB miss 발생→ Ln page table miss*** n = 1, 2
  • → Ln page table entry 내부의 page 가 Ln TLB로 변환하고 물리주소로 변경됨
  • → Ln page table access
  • ** page table walk : TLB miss를 처리하는 과정
• virtual memory의 오버헤드를 줄이기 위해 **Redundant Memory Mappings (RMM)**을 제안한다.
  • RMM leverage ranges of pages :각 range를 하나의 range table entry로 변환한다.
  • → 프로세스의 주소 공간의 대부분을 변환할 수 있는 적당한 entry 개수 설정 가능
  • page range가 연속적인 프로세스 페이지의 일부가 되도록 한다.
  • standard paging + software range table + hardware range TLB
  • eager page allocation으로 운영체제가 자동으로 range를 감지할 수 있도록 수정
  • RMM은 paging 및 huge page 보다 실질적으로 우수한 성능을 발휘하며 direct 세그먼트 (프로그램 당 하나의 범위)보다 다양한 워크로드를 개선하여 가상 메모리의 오버 헤드를 평균 1 % 미만으로 줄인다.

1. Introduction

• virtual memory→ 프로세스별 독립성을 보장하여 security를 향상시킨다.
• → 운영체제와 하드웨어가 각 프로세스의 virtual-to-physical address mapping을 관리하여 프로그래머의 생산성을 향상시킨다.
• : 각 프로세스에 private하고 더 큰 address space를 제공한다.
• 오늘날 대부분의 하드웨어에서는 virtual memory를 page-based로 구현한다.
  • physical memory를 고정된 크기의 page로 쪼갠다.
  • virtual page - physical page mapping을 위해 page table을 사용한다.
  • TLBs를 사용하여 page mapping을 위한 address lookup 속도를 개선한다.: TLB miss가 발생하면 시스템은 반드시 page table walk를 수행하는데 page table walk에서도 cache miss가 또 발생할 수도 있다.
    • physical memory의 크기가 커짐에 따라 page table walk 실행 오버헤드가 더 커진다.
  • → TLB size 부족으로 인해 paging 성능이 떨어진다. (limited TLB reach problem)
• page-based virtual memory에서 paging의 성능 문제를 해결하기 위한 연구
  • multi-page mapping : 하나의 TLB entry - 여러 개의 page (8~16개 page / entry)
    • TLB reach 증가
    • alignment restrictions , 여전히 부족한 TLB reach
    ** alignment restriction : n byte의 데이터가 저장될 떄 메인 메모리의 주소가 항상 n의 배수여야 하는 규칙
  • Huge page : 메모리를 2MB ~ 1GB 크기로 쪼개어 사용한다.
    • TLB reach 증가
    • size and alignment restriction
  • Direct segment : 하나의 임시적인 큰 segment와 일반적인 page를 제공한다.
    • 대부분의 메모리 접근을 위한 하나의 세그먼트를 할당하고 사용하는 어플리케이션의 경우, direct segment로 paging cost를 줄일 수 있다.
    • 하나의 segment만 지원한다.
    • 어플리케이션 실행시에 명시적으로 segment를 할당해야 한다.
  • libhugetlbhs : pre-load하는 라이브러리로 프로세스의 text, data, malloc(), 공유 메모리 + huge page를 지원한다.
  • → 큰 address space를 사용하게 하여 TLB miss로 인한 성능 저하를 방지한다.
  •  
• 다양한 워크로드 전반에서 address translation 성능을 개선시키고, transparent한 가상 메모리 매커니즘 : Redundant Memory Mappings (RMM)
  • redundant mapping (+page table) : physically, virtually 연속적인 page range의 translation 정보를 효과적으로 표현할 수 있다.
  • address space에 natural contiguity를 사용한다.
  • **natural contiguity : 운영체제에서 page를 할당한 상태의 contiguity
  • 전체 page table을 fall-back 매커니즘으로 유지한다.
  • **fall back mechanism : 루트 파일시스템에서 직접 펌웨어에 대한 시스템 캄색을 못하거나 시스템적인 이유로 직접 펌웨어 서치가 불가능할 때 쓰이는 대체 매커니즘으로 Kobject uevent나 사용자 정의 매커니즘이 있다.
  • range translation : contiguous virtual address range → contiguous physical pages mapping using BASE, LIMIT, OFF-SET 값으로 임의의 사이즈의 range의 변환을 수행한다.
    • base-page aligned , redundant to paging
    • page table은 전체 virtual address space를 mapping 한다.
  • software가 관리하는 range table 추가했다 : virtual ranges → physical ranges mapping
  • 마지막 level의 page TLB와 parallel하게 접근되는 하드웨어 range TLB를 추가했다.
  • range table은 page table에 불필요한 것이기 때문에 RMM은 운영체제가 이것을 필요로 할 때만 사용할 수 있는 유연성을 제공한다.
• range translation의 contiguity를 증가시키기 위한 노력
  • 운영체제의 default lazy demand page allocation 전략을 확장시켜 eager paging을 수행하도록 했다.
  • demand paging : 첫번째로 접근될 때 physical memory의 page를 인스턴스화 한다.
  • eager paging : 할당 요청시에 바로 physical memory의 page를 인스턴스화 한다.
  • 운영체제가 transparent huge page로 paging하는 것보다 훨씬 적은 범위로 프로세스 virtual address space의 대부분을 자동으로 mapping 하게 한다.
• RMM 도입 결과
  • 350 MB ~ 75 GB 메모리 워크로드에서 RMM은 50 이하의 range translation을 하면서 메모리의 99% 이상의 mapping을 하는 가능성을 보였다.
  • 일반적인 paging, clustered TLBs, huge page와 비교했을 때, RMM은 다양한 워크로드에서 세개의 대안보다 훨씬 좋은 성능을 보였다.
  • RMM은 평균 1%이하로 virtual memory의 오버헤드를 줄인다.
  • RMM을 적용한 application들은 프로그래머의 개입 없이 translation 오버헤드를 줄이는 것을 더 선호한다.
• RMM design
  • Linux kernel v3.15.5
  • x86의 performance counter + BadgerTrap의 functional TLB simulation2. Background

2.1 Multi page Mapping

• 여러개의 page table entry들을 하나의 TLB entry로 묶는 기법
  • sub-blocked TLBs and CoLT : default OS memory allocator를 사용하여 contiguous physical page의 작은 블록들을 contiguous virtual page 에 할당한다.
  • Clustered TLB : contiguous virtual page의 작은 set을 physical pages의 clustered set에 할당한다.
  →entry 당 translation을 8~16번 정도로 조금 수행할 수 있다.
• ⇒ 큰 working set에 대한 page walk를 감소시킬 수 있는 가능성을 줄인다.

2.2 Huge pages

• Transparent Huge Pages (THP)
• libhugetlbfs

→ TLB reach를 증가시킨다.

↔ size-alignment requirement 로 인해 huge page의 효과가 제한된다.

(메모리가 size-aligned하거나 contiguous할 때만 운영체제가 huge page를 huge page할당하도록 하기 위해서 huge page는 반드시 size-aligned physical address를 가져야 하기 때문이다.)

↔ 대부분의 CPU들은 huge page를 캐시할 수 있는 TLB entry 개수를 제한하기 때문에 huge page를 TLB에 캐시하여 얻는 이점이 제한된다.

2.3 Direct segments

** segment : 필요한 크기에 맞게 지정된 영역 (고정된 크기 X)

• 하나의 하드웨어 segment를 사용하여 contiguous virtual memory에 크기에 제한이 없는 하나의 range(segment) → contiguous physical memory mapping
• (사용자가 지정한 영역을 하나의 segment로 구성한 뒤 contiguous하게 address mapping을 하는 것)
• 나머지 virtual address space는 일반적인 paging을 수행한다.
• virtual address는 direct segment 나 paging으로 mapping되지만 둘이 함께 mapping되지는 않는다.
• Direct segment 는 BASE, LIMIT, OFFSET 레지스터를 도입하여 segment 내에서 page walk를 제한
  • 필요 조건

3. Redundant Memory Mappings (RMM)

 

• 많은 application들은 virtual address space에서 많은 contiguity를 보여준다. 그러나 이 contiguity를 표현하는데 필요한 range의 수는 적다.
• Abundance of address contiguity
  • x86-64 하드웨어에서 프로세스를 실행시켜 address contiguity를 quantize했다.
  • 같은 권한을 가진 모든 page가 mapping된 virtual address의 사이즈를 측정하기 위해 주기적으로 page table을 스캔했다.
  • 운영체제가 contiguous physical page로 mapping할 수 있는 contiguous virtual range의 최소한의 수 >>→ 워크로드는 전체 virtual address space를 mapping하기 위해 16~112 range의 physical memory를 필요로하지만 application의 memory space의 99%를 차지하는 range의 수가 50 미만이다.
  •  

⇒ 즉 range translation를 조금만 수행해도 virtual memory address translation 성능을 높일 수 있다.

3.1 Overview

 

• range translation을 줄이기 위한 RMM의 접근법
  • 운영체제는 best-effort allocation을 사용하여 range table과 page table상에서 contiguous virtual page를 찾아 contiguous physical pages에 mapping한다.
  • 하드웨워 range TLB는 page translation과 병행하며 여러개의 range translation을 캐시한다.
  • 대부분의 address들이 range TLB에서 hit하지만 miss할 경우, 시스템은 page table을 이용해서 translation 하는 과정으로 되돌아 갈 수있다.
• range translation
  • contiguous virtual pages → contiguous physical pages
  • ** range = contiguous pages to be mapped
  • unlimited size
  • base-page aligned
  • BASE ~ LIMIT address로 식별
  • 하드웨어가 virtual address에 주소에 상응하는 range만큼 OFFSET을 준다.
• RMM에서 range를 관리하기 위해 도입한 새로운 component
  • range TLBs , range table:→ L1 TLB 에서 miss가 나면 range TLB와 page TLB (L2 TLB) 에 병렬적으로 접근한다.→ 흔하지 않은 경우지만 range TLB와 page TLB에서 모드 miss가 발생하면 address는 range translation으로 mapping 되고, 하드웨어는 실행을 재개하기 위해 page table entry를 가져오고, 백그라운드에서 range table entry도 가져온다.
  • → range TLB나 page TLB에서 hit하면, 하드웨어는 4 KB TLB entry를 이전 level의 TLB에 만들고, 계속 실행한다.
  • range TLB에 여러개의 unlimited size의 range translation을 저장하고, 마지막 level의 page TLB (L2 TLB) 와 병렬적으로 접근된다.
  • eager paging allocation :각 range의 범위를 최대화하기 위해, RMM은 운영체제의 page allocator가 eager paging allocation을 하게 하여 contiguity를 향상시킨다.
  • → 운영체제는 항상 page table과 range table을 업데이트하여 전체 메모리를 consistency하게 관리한다.
  • RMM의 성능은 적은 수의 entry를 가지고 높은 hit ratio를 가지는 range TLB에 따라 결정된다.

4. Architectural Support

4.1 Range TLB

• 여러개의 range translation을 저장하는 하드웨어 캐시
• TLB entry는 unlimited range of contiguous virtual pages → contiguous physical pages
• range TLB 는 last-level page TLB (L2 TLB) 와 parallel하게 접근된다.
• → TLB access latency 내에 lookup 결과 (miss / hit)을 반드시 반환한다.
• range TLB는 direct segment의 base/limit/offset logic의 N-fully associative copy / 단순화된 range cache와 유사하다.
  • fully-associative vs set-associative** look up: cache에 접근하려고 하는 데이터가 존재하는지 확인하는 것
    • direct mapped cache 방식 :
      • 여러 개의 주소가 캐시 메모리 하나의 주소에 대응되는 N:1 방식
      • 하나의 메모리 주소는 cache의 고정된 위치에만 캐시될 수 있다.
      • 캐시 메모리가 한번에 1 word 데이터만 가져올 수 있다.
      • 캐시된 메모리 주소는 일부를 쪼개서 cache index로 활용한다.
      • index로 접근하기 때문에 specific search에 적합하다.
      Ex ) 00000₂, 01000₂, 10000₂, 11000₂인 곳의 데이터를 캐시 메모리의 주소가 000₂인 곳에만 읽고 쓰는 방식이다.
    • fully-associative :
      • 비어 있는 cache에 무작위로 캐시하는 방식
      • cache look up을 수행할 때 cache에서 관리되는 모든 entry를 탐색한다.
      • cache 활용도가 최대가 된다.
      • content addressable memory (CAM) 이라는 특수한 메모리 구조가 필요하다. (비싸다)
    • set associative :
      • direct mapped + fully-associative
      • cache의 하나의 index에 block의 집합 (set)을 mapping한다.
      • n-way ⇒ n이 커질수록 구현이 어렵고, 속도가 떨어지며, 제조 비용이 높아지지만 miss 발생 빈도가 떨어진다. (1-way = direct mapped / cache block 개수 n-way = fully associative)
  • : CPU가 cache를 관리하는 방법
• → 하나의 equality test가 아니라 entry마다 두번의 비교를 수행한다. (range TLB는 entry를 조금가지고 있고, 빠른 비교 회로를 사용할 수 있기 때문에 성능 이점이 있다.)
• range table entry = virtual range + translation
  • virtual range : virtual address range의 BASE, LIMIT을 저장한다.
  • translation : OFFSET (physical memory의 range 시작 부분 - BASE) 과 protection bit (PB)를 저장한다.
  • lookup 연산을 위한 두개의 comparator
• L1 TLB miss → L2 TLB + range TLB에 접근한 경우→ 하드웨어가 L1 TLB 에서 miss가 발생한 virtual page number를 range TLB의 모든 entry의 range 들과 비교한다.→ range TLB에서 hit 한 경우, range TLB는 해당 range translation의 OFFSET과 protection bits를 반환하고, L1 TLB에 대한 page table entry를 계산한다.→ miss 한 경우, range TLB는 range table walk를 수행하여 range table에서 해당하는 range translation을 가져온다.
• 그리고 요청된 virtual page number에 OFFSET 값을 더하여 physical page number을 만들고, range translation에서 protection bits를 복사하여 page를 반환한다.
• $$BASE ≤ virtual page number ≤ LIMIT$$
•  
• optimization
  • fully-associative lookup 비용을 감소시키기 위해 optimal MRU pointer를 사용한다.→ range TLB는 가장 먼저 MRU pointer를 확인하고→ miss 한 경우 모든 valid entry를 확인한다.
  • ⇒ range TLB의 associative search를 줄여 page TLB보다 빠르게 translation을 할 수 있어 성능을 높인다.
  • → hit 한 경우 다른 엔트리로 skip하고
  • MRU pointer : 가장 최근에 사용된 range translation을 저장한다.

4.2 Range table

• range table은 프로세스별 architecturally visible한 자료구조로 메모리에 프로세스의 range translation을 저장한다. (프로세스마다 가지고 있다.)
• TLB miss가 발생하면 하드웨어 walker가 range table로부터 range translation을 로드한다. (TLB miss → table walk)
• 운영체제가 프로세스의 메모리 관리 오퍼레이션을 기반으로 range table entry들을 관리한다.
• range table은 B-Tree 자료 구조로 구현한다.
  • (BASEi, LIMITi) 를 key로 사용한다.
  • OFFSETi과 protection bits를 value로 사용한다.
  • B-tree는 캐시 친화적이고, O(log n) 시간으로 search 와 update를 하여 정렬된 데이터를 유지한다.
  • ** cache-friendly : cache 알고리즘을 활용하여 locality가 높은 것을 의미한다.
  • B-tree에 하나의 노드는 여러개의 자식노드로 range를 가질 수 있기 때문에 dense한 range를 표현할 수 있다.
  • range table 노드 당 range 개수는 tree의 depth와 노드 lookup의 평균 개수를 결정한다.
• range table에 저장된 range translation, range table의 각 노드의 design :
  • 각 노드는 4개의 range translation을 가지고 있으며 5개의 children을 가진다.
  • 각 children은 또 다른 range translation을 저장하고 있는 노드를 가리킨다.
  • 하나의 노드가 최대 3-level로 구성하여 최대 124 range translation을 수용할 수 있다.
  • 각 range translation = BASE + LIMIT + OFFSET + protection bits
  • range table은 page table보다 훨씬 작다. (하나의 4KB page에 128개의 translation을 저장한다)
  • 모든 children에 대한 pointer는 physical address이다.
  ⇒ range table의 순회를 cache-friendly하게 보장하고 (오퍼레이션 당 cache line 몇 개만 접근하면 되는 것) range translation의 dense representation 을 유지한다.
  • RMM은 CR-RT 레지스터가 필요하다.** CR-RT 레지스터 : range table관리를 위한 레지스터
  • → address translation을 수행하기 위해 range table root의 physical address를 가리킨다.
•  

4.3 Handling misses in the range TLB

range TLB와 page TLB miss가 발생하면 하드웨어는 메모리에서 translation을 가져와야 한다.

• RMM에서 발생하는 design issue
  • address translation hardware가 missing page table entry만 갖오기 위해 page table을 가용하는지 또는 range translation을 가져오기 위해 range table을 가져와야 하는지 여부
  • 하드웨어가 어떻게 missing translation이 range translation의 일부인지 판단하는지
  • 하드웨어가 range table에서 불필요한 lookup을 피하는 방법

Miss-handling order

1. RMM은 일단 page table에서 missing translation 을 가져온다.
2. CPU가 pending operation을 재개할 수 있도록 가져온 translation을 previous-level TLB에 install한다.

⇒ 불필요한 mapping을 하지 않아 page를 위한 range table접근으로 인한 latency를 발생시키지 않는다.

• background에서 range table walker 하드웨어가 해당 주소가 range에 있는지 알아내고, range table entry를 업데이트한다.

Identifying valid range translations

• range TLB에서 miss 발생 여부를 확인하기 위해 RMM은 page table entry에 range bit를 추가한다.page table walker는 page table entry를 가져오고, range bit = 1이면 백그라운드에서 range table에 접근한다.
• ⇒ range bit = 0 이면 해당 page table entry는 range table에 없다는 뜻이 때문에 miss가 발생해도 range table walk를 하지 않아도 된다.
• page table entry의 range bit : 해당 page가 range table entry의 일부인지 표시한다.
• alternative: 하드웨어가 range table 접근 여부를 결정하기 위해 prediction을 사용할 수 있다. (본 논문에서 실험 X)

Walking the range table

• RMM의 range table walker = comparator * 2 + 하드웨어 state machine
• range table walker는 백그라운드에서 CR-RT 레지스터부터 range table walk를 시작한다.(miss가 발생한 page address를 range table에 있는 range translation의 BASE와 LIMIT 정보를 이용하여 존재 여부를 파악한다.)→ range translation을 발견하면 그것을 range TLB에 install한다.
• (다음에 해당 range에 속하는 page miss가 발생하면 range TLB에서 hit 할 수 있도록 캐시)
• → 해당하는 range translation 을 찾을 때까지 child pointer를 따라 이동한다.
• → walker는 missing address 와 각 range table node의 range translation들을 비교한다.
• 이것을 단순화하기 위해 운영체제 handler가 range table lookup을 수행할 수 있다.

Shootdown

• 운영체제가 INVLPG 명령어를 사용한다.
• → TLB shootdown 프로세스 중에 오래된 translation을 무효화한다.
• RMM은 INVLPG를 수정하였다.⇒ 모든 TLB와 range TLB를 TLB shootdown 프로세스 중에도 coherent하게 유지할 수 있다.
• 각 range TLB entry를 address space identifier와 연관지어 range TLB를 flush하지 않고 context switching을 할 수 있다.
• → 모든 TLB entry와 해당하는 virtual page를 포함하는 range TLB entry를 무효화한다.

5. Operating System support

• RMM은 운영체제 수정이 필요하다.⇒ 논문에서는 운영체제가 eager paging allocation을 사용하면서 range의 크기를 늘릴 수 있도록 수정했다.
• → 운영체제에서 range table entry를 만들고 관리하고, page table과 조정해야 한다.

5.1 Managing range translations

• RMM의 PCB는 range table의 root node의 physical address와 함께 range table pointer (RT pointer)에 저장된다.
  • 운영체제가 프로세스를 생성할때, 운영체제는 range table을 위한 공간을 할당하고, range table pointer가 해당 프로세스의 PCB를 가리키도록 설정한다.
  • 매 context switching마다 운영체제는 range table pointer를 CR-RT 레지스터에 복사하고 range table walker가 RT pointer를 사용하여 range table walk를 한다.
• 운영체제는 프로세스가 메모리를 할당하거나 해제할때 또는 page를 요청할 때 range table을 업데이트한다.
  • 운영체제는 접근되는 page의 contiguity를 분석한다.
  • contiguity threshold (8 pages)를 기반으로 운영체제는 range table에서 range translation을 추가/갱신/제거 한다.
  • 이때 작은 range translation은 range TLB에 스레싱을 발생시킬 수 있기 때문에 운영체제는 작은 range translation 을 생성하는 것을 피한다.
  • 운영체제는 contiguity threshold를 현재 range translation의 수와 크기, range TLB의 성능에 따라 수정할 수 있다.
  • 운영체제는 range의 일관성을 유지하기 위해 page 접근시 해당하는 모든 page table entry들의 range bit를 업데이트 한다.

5.2 Contiguous memory allocation

• 대부분의 virtual address translation 요청을 포괄하는 넒은 range translation이 적게 발생해야 range TLB의 높은 hit ratio를 유지하게 하고 virtual memory의 오버헤드를 줄일 수 있다.**eager paging: 가능한 가장 큰 contiguous virtual page를 contiguous physical page에 할당하는 기법
• → RMM은 운영체제 메모리 할당 매커니즘으로 eager paging을 사용하게 한다.

Default buddy allocator (Linux's)

• buddy allocator는 physical memory를 2 ^ order pages 의 block들로 쪼개고, block size마다 구분된 free-lists를 사용하여 block을 관리한다.
• kernel compile - time parameter는 memory block의 최대 크기와 free-list의 총 개수를 정의한다.
• buddy allocator는 free-list를 2의 제곱수 block으로 구성하고 가장 작은 크기의 free-list로부터 요청을 만족시킬 block을 찾는다.
  • 2 ^ i 크기의 block을 사용할 수 없는 경우 운영체제는 그 다음으로 큰 2 ^ i+k 크기의 free block을 찾는다. (k = 1, 2, ...) 이 과정을 요청을 만족시킬 수 있는 free block을 찾을 때까지 수행한다.→ 하나의 free block을 할당하고, free-list에 나머지 free block을 추가한다.→ buddy block 이 free 상태이면 운영체제는 두 block을 다시 합쳐 2 ^ i+k block으로 만든다.
  • → application이 2 ^ i block을 해제하면 운영체제는 해당 block의 주소를 이용해서 buddy block을 찾는다.
  • → 운영체제는 원하는 사이즈의 free block이 생성될 때까지 반복적으로 block을 둘로 쪼갠다.
• buddy heap에 contiguous page가 있음에도 불구하고 demand-paging으로 인해 실제로 대부분의 할당은 하나의 page 단위로 이루어진다.
  • operating system은 할당 latency를 줄이기위해 demand paging을 사용하여 application이 실제 page를 참조할 때까지 page를 physical page에 할당하는 것을 지연시킨다.
  • 즉, 프로세스의 할다이 운영체제의 할당을 일으키지 않고, 프로세스가 page를 read하거나 write하면 운영체제가 하나의 free-list로부터 하나의 page를 할당한다.
  ⇒ 이러한 demand allocation은 contiguity를 저하시킨다.

Eager paging

• allocation시에 contiguous physical page를 contiguous virtual page에 할당한다.→ large range translation가 많아진다.
• (allocating memory at request-time)
• request가 range threshold보다 큰 경우 운영체제는 여러 개의 range translation을 생성하고, 해당하는 range table entry와 page table entry를 업데이트 한다.
• eager paging은 allocation latency를 증가시키고, fragmentation을 유발할 수 있다.

운영체제는 range translation에서 memory 사용을 모니터링 하고, 일반적인 paging 매커니즘으로 range 와 page를 재요청할 수 있기 때문에 사용되지 않는 메모리가 영구적으로 낭비되는 것은 아니다.

• eager paging은 demand-paging에 비해 더 큰 range translation을 만들어 낼 수 있다.

따라서 RMM 하드웨어에 적합하다.

Algorithm

• eager paging pseudo code** memory fragmentation이 threshold를 넘지 않은 경우 eager paging을 수행한다.
•  
• 프로세스가 Nx page 할당을 요청하면 eager paging은 2 ^ i를 할당한다.
• → contiguity를 maximum managed block size까지 증가시킬 수 있다.
• 프로세스가 가능한 contiguity크기보다 큰 메모리를 요청하면 운영체제는 여러 개의 블록을 할당한다.
• contiguity를 향상시킬 수 있는 optimization
  1. eager paging은 free-list에 있는 block들을 합쳐서 maximum managed block보다 큰 range translation을 할 수 있도록 정렬할 수 있다.
  2. eager paging은 maximum block보다 작은 할당으로부터 large range translation을 만들기 위해서 더 큰 크기의 free-list에서 block을 요청할 수 있다.
  (RMM 프로토타입엔 구현되지 않은 기능)
• eager paging 알고리즘은 여러 개의 block을 합쳐 large range translation을 만들어낼 수 있고, buddy allocator의 clustering을 활용할 수 있다.
• eager paging은 메모리 단편화가 적고, 공간이 충분할 경우에 효과적이다.
• → 운영체제는 그렇지 않은 경우에 다시 eager paging 말고 default paging allocation을 수행할 수 있다.

6. Discussion

구현을 위해 고려해야 하는 하드웨어와 운영체제 issue

TLB friendly workloads

• 어플리케이션이 작은 memory footprint를 가지고 있고(프로세스의 메모리 사용량이 작고), 낮은 page TLB miss rate를 가지고 있다면 range TLB 접근 오버헤드로 인해 range TLB 로 인한 성능 이점이 감소한다.
• **memory footprint : 메모리 사용량
• 운영체제는 application의 사용량에 따라 range TLB 사용 여부를 결정한다.

Accessed & Dirty bits

• x86 CPU의 TLB는 해당하는 page table entry의 page에 접근되면 accessed bit을 set하고, write되면 dirty bit을 set한다.
• range TLB는 page당 accessed/dirty bit을 저장하지 않는다.→ range를 해체하지 않고도 개별 page를 reclaim하거나 swap할 수 있다.
• → range TLB hit하면 운영체제가 range translation에 해당하는 모든 page의 bit들을 할당시에 설정한다. (운영체제가 페이지 단위로 physical 메모리 관리)

Copy-on-write

** copy-on-write : 서로 다른 프로세스가 메모리를 공유하고 있는 경우 한 프로세스가 해당 메모리에 수정을 할 경우 이전의 메모리 복사본에 수정을 하게 하는 방식이다. 그 후 각각의 프로세스별 포인터를 변경시켜주면 된다.

• virtual memory optimization
• 프로세스들이 초기에 page를 공유하고, 프로세스들 중 하나가 page를 수정하면 운영체제가 해당하는 page를 분리하여 개별 생성한다.
• → 수정이 있는 프로세스만 page를 복사한 뒤 그 위에 수정을 반영한다.
• copy-on-write는 page마다 protection bit을 사용한다.→운영체제가 page를 복사하고 page table의 protection bit을 다시 수정한다.
• **protection bit : page가 수정되면 trigger fault
• RMM에서 range translation은 protection bit을 range 단위로 가지고 있다.
• range translation을 read-only shared range로 사용하다가 프로세스가 range에 포함된 page를 write한 경우에 protection bit을 set하면 운영체제가 copy-on-write를 수행하여 range를 분해할 수 있다.
• or 운영체제가 fault된 range translation 전체를 복사할 수도 있다.

Fragmentation

• 복잡한 워크로드로 인한 frequent memory management는 fragmentation을 유발하여 RMM의 성능 이점을 제한한다.
• 운영체제가 메모리에서 충분한 free range를 발견하지 못하면 paging-only를 사용하고 range TLB를 사용하지 않아야 한다.
• fragmentation이 너무 심한 경우 운영체제는 full compaction이나 partial compaction을 수행한다.
  • ** compaction

7. Methodology

RMM operating system prototype

• Linux x86-64, kernel v3.15.5
• 커널의 모든 메모리 관리 오퍼레이션을 대신해서 range table 관리를 구현한다.
• → mmap, brk, mremap 시스템 콜을 수정하여 range 생성과 eager paging을 구현한다.
• 논문의 프로토타입에서 range table은 B-tree 대신 간단한 연결리스트로 구현하였다.
• contiguity threshold를 32 KB (=8 pages)로 설정하였다.
• → range translation의 최소 크기 결정
• buddy allocator의max-order 파라미터를 수정하여 최대 할당 크기를 2 GB → 4 MB까지 증가시켜 range의 최대 크기를 증사시켰다.

RMM hardware emulation

• Intel Sandy Bridge core
• 논문에서는 L2 page TLB와 parallel하게 32-entry fully associative range TLB를 사용했다.

Performance model

• RMM의 성능을 측정하기 위해 사용한 방법
  • 실제 시스템에서 실제 입력값을 사용하여 어플리케이션 실행
  • performance counter를 읽기 위해 Linux perf utility 사용하여 L2 TLB miss와 page walk에 소요되는 실행 cycle을 수집하였다.** Linux perf : 커널 성능 측정 도구 /tools/perf/*
  • → 수집된 값으로 계산한 것: 오버헤드가 없는 이상적인 실행시간, page walk 오버헤드, 감소된 page walk를 적용한 예상 오버헤드

Benchmarks

• RMM은 다양한 어플리케이션에서 large memory 워크로드에서 사용하기 위해 설계되었다.
• RMM의 효과를 측정하기 위해 SPEC 2006, BioBench, Parsec을 사용하였다.
• 사용된 벤치마크별 특징
  • SPEC 2006 :
    • SPEC : 다양한 벤치마크 suite를 만들고 공유하는 협력기구
    • 계산 작업 집중적인 워크로드 성능 측정에 적합하다.
  • BioBench :
  • Parsec :
    • 멀티 스레드 프로그램으로 구성된 벤치마크 suite
    • multi core scalability 측정에 적합하다.

8. Results

• x86-64에서 virtual memory 오버헤드를 측정했다.
• 4 KB pages, 2 MB pages with transparent huge pages, 1 GB pages with libhugetlbfs
• BadgerTrap에서 multi-page mapping emulation
• Clustered TLB 사용 - 각 entry는 최대 8 page cluster을 인덱싱한다.
• eager paging
• 이상적인 direct segment 성능을 가정한다.
• 프로그램 실행 80% 이상 live하는 page들은 하나의 contiguous range로 합쳐질 수 있다고 가정한다.

8.1 Performance analysis

• RMM은 모든 워크로드에서 잘 수행되며 direct segment를 제외한 방식보다 훨씬 더 많은 개선을 보인다.→ 평균적으로 virtual memory의 오버헤드를 1% 미만으로 줄인다
• → RMM은 page walk를 크게 감소시킨다.
• 대부분의 워크로드에서 base page 크기는 높은 오버헤드를 보인다.
• Clustered TLB (CTLB)는 오직 small-memory 워크로드에서 제한된 오버헤드 감소를 보인다.
• Huge pages는 모든 워크로드에서 virtual memory 오버헤드를 감소하지만 여전히 개선될 여지가 많다.
• Direct segment는 large-memory 워크로드에서 엄청난 오버헤드 감소를 보이지만 여러개의 range가 필요한 경우 저조한 성능을 보인다.

8.2 Range TLB sensitivity analysis

• 성능을 높이기 위해서 range TLB는 대부분의 L1 TLB miss를 만족시킬 수 있을만큼 충분히 커야 한다.
• 32-entry range TLB는 대부분의 워크로드에서 발생하는 miss의 평균 97% 제거한다.
• (전력 소모 ↔ 성능)
• virtual memory 오버헤드 감소를 위해서 multi-entry range TLB가 필요하다.

8.3 Impact of eager paging

• eager paging은 range 크기를 증가시킨다.
• demand-paging과 비교했을 때, eager paging의 효과ii) big-memory 워크로드에서 range size를 증가시킨다.⇒ eager paging은 모든 어플리케이션에서 메모리의 많은 부분을 몇 개의 range만으로 사용하기 때문에 적은 entry로 구성된 range TLB의 hit ratio를 높인다.
•  
• iii) 모든 워크로드에서 range size의 평균과 최대 range size를 증가시킨다.
• i) small-memory 워크로드에서 range size를 줄인다.
• eager paging은 대부분의 어플리케이션의 실행 시간이 거의 변화시키지 않았고, 일부만 조금 빨라졌다. (orthogonal 매커니즘)
• eager paging은 어플리케이션이 요청한 메모리 영역을 사용할 것이라고 예상한다. 따라서 memory footprint를 증가시킨다.

⇒ eager paging 의 trade off : memory saving ↔ performance

8.4 Energy

• energy에 미치는 RMM의 주된 효과는 어플리케이션 실행을 빠르게 만들어 시스템의 static energy를 향상시키는 것이다.
• → 본 논문에서 사용한 RMM 모델은 2~84% 까지 성능을 향상시켜 static energy를 절약하였다.
• 시스템이 L1 TLB miss에서 dynamic energy를 소모하고 L2 TLB와 range TLB에 parallel하게 접근한다. 그리고 range TLB는 상대로적으로 L1 TLB에 비해 dynamic energy를 덜 소모하고, L2 TLB에서 miss가 발생했을 떄, range TLB에서 page walk를 하지 않게 하여 dynamic energy를 줄일 수 있다.
• address translation path에 미치는 range TLB의 영향을 고려해 보았을 때, area와 power보다 timing이 더 우선시 되어야 한다. range TLB는 L2 TLB의 절반에도 미치지 못하는 power를 추가하고, L2 TLB의 13% area를 확보하기 때문이다.

9. Related work

• TLB miss cost를 줄이기 위한 방법
  • accelerating the page-walks
    • commodity CPU는 page table entry를 캐시하여 page walk의 속도를 향상시킨다.
    • software-defined TLB 구조 (TSBs in SPARC, TLB in Intel Itanium) 는 TLB의 entry를 pin 해둔다.
    • MMU caches는 page table의 중간 level을 캐시해두어 page walk 중간에 발생하는 메모리 참조를 건너뛸 수 있게 한다.
    • RMM은 page walk의 발생 횟수 자체를 줄인다.
  • TLB miss 발생 횟수를 줄여 virtual memory 오버헤드 줄이기
    • 하드웨어가 page 사용하기 전에 미리 TLB에서 page table entry를 가져오는 방법 이 있다. (prefetching)
    • → prefetching은 메모리 접근 패턴의 예측이 실패할 경우 그 효과가 제한된다.
    • huge page 기반 speculative translation
    • → 이 매커니즘 역시 TLB에 영향을 받으며 메모리 사용이 연속적일 경우에만 효과적이다.
    • Last-level shared TLBs & cooperative TLBs 는 TLB reach를 증가시키고, page walk의 발생 횟수를 감소시킨다.
      • ** shared last-level TLBs :→ lase-level cache + SLL TLB는 L1 TLB miss 발생시 접근된다.
      • → SLL TLB는 공유되기 때문에 한번 접근되면 다른 프로세스들도 사용할 수 있다.
      • 대부분의 multi 스레드들이 동일한 address translation entry에서 TLB miss가 발생한다
      • ** cooperative TLBs :→ leader (가장 먼저 해당 page에 접근하는 프로세서) 가 미리 translation 정보를 캐시해두고 follower (다음 해당 page에 접근하는 프로세서) 들이 함께 translation를 사용할 수 있게 한다.
      • 특정 page entry에서 TLB miss가 발생하면 다른 프로세서들도 해당 page entry에 대한 TLB miss가 발생할 확률이 높다.
    • 모든 page 크기가 하나의 set-associative TLB를 공유할 수 있는 prediction 매커니즘이 제안되었다.↔ RMM은 이와 대조적으로 임의의 large range를 사용할 수 있는 translation 을 생성하고 캐시한다. 따라서 어플리케이션의 접근 패턴을 모르더라도 수용 가능한 매커니즘이고, large memory를 위한 address translation 을 개선시킨다.
    • → TLB entry들이 range를 사용하지 않으면 하나의 page만 mapping하는 것은 그대로이기 때문에 총 TLB reach는 여전히 memory intensive한 어플리케이션에서 부족하다.
  • virtual memory를 구현하기 위해 segmentation을 사용해왔다.
    • 지금까지 page 대신 segmentation을 적용한 CPU들이 있었지만 그로 인한 translation 이점은 존재하지 않았다.
    • RMM은 segmentation으로 translation 성능을 향상시키면서 paging의 유연성과 견고함을 함께 사용했다.
  • virtual cache
    • poor locality로 인해 TLB miss를 증가시킨다.
    • 시스템을 복잡하게 만든다.
    • 단순히 하위 계층의 cache에서 translation을 하는 것이기 때문에 별 효과가 없다.
  • fine-grained memory protection

10. Summary

• Redundant Memory Mapping : novel and robust translation mechanism
• → 다양한 워크로드에서 virtual memory의 오버헤드를 감소시킨다.
• virtually, physically 연속적인 임의의 많은 page들을 range로 효과적으로 표현한다.
• RMM은 기존의 하드웨어와 운영체제를 수정하여 구현할 수 있다.
• RMM을 적용한 시스템은 virtual memory의 성능이 높아지고 어플리케이션에 완전히 transparent하다.

11. RMM의 장점과 단점

1) 장점

• contiguity를 잘 활용하여 메모리 활용도가 높아진다.
• 각 프로세스의 메모리 사용량을 고려하여 range TLB를 사용 여부를 결정할 수 있다.
• big-memory / small-memory 등 다양한 워크로드에서 성능 개선을 보인다.
• range table에 많은 range translation을 표현할 수 있다.
• RMM은 기존의 하드웨어와 운영체제를 수정하여 비교적 쉽게 구현할 수 있다.

2) 단점

• page에 접근할 때마다 page table entry의 range bit을 업데이트 해야 한다.
• eager paging allocation으로 인해 allocation latency가 증가하고 메모리에 fragmentation이 더 발생할 수도 있다.
• page TLB miss handling 이전에 page TLB miss를 발생시키지 않는 것이 더 효과적일 수 있다.
• fragmentation이 심한 경우에는 compaction이 많이 필요해서 오히려 성능이 저하될 수 있다.