Abstract
-NVM은 DRAM에 비해 Row activation latency가 대략 10x 정도로 매우 크다.
-따라서 미리 NVM의 Row를 정확하게 Open 한다음 적은 오버헤드로 Open된 Row에서 데이터 블록을 Prefetch할 수 있는 Collective cross-page prefetching을 제안한다.
-Memory Access 패턴을 식별하고 Ladder stream prefetcher(LSP)를 제안한다.
-Collective Prefetch Table는 Memory Queue의 상태에 따라 Prefetch를 추측적으로 스케쥴링하여 Prefetch Request로 인한 Demand Request와의 충돌을 피한다.
Intro
문제점
-Optane DC PMM가 Memory Mode에서 작동될때 DDR4 DIMM은 NVM의 캐시 역할을 한다.
-이 논문에서는 단순화를 위해 하이브리드 메모리 구조를 External DRAM Cache, NVM 두개를 합쳐서 (EDC - NVMM)으로 칭한다.
-NVMM 은 낮은 row buffer locality를 가지고 있다.(Row buffer Hit rate가 50% 미만이다.)
-NVM의 Activation의 Latency(메모리 모듈에서 Row buffer로 데이터를 전송하는 latency)가 DRAM Activation의 약 10배이기 때문에 NVM의 Row buffer miss는 훨씬 더 크다.
NVM의 요구사항
-첫번째, corss-page prefetch는 long-term future pattern가 필요하다.
-DRAM용 기존 Prefetcher는 Page boundary를 가로지르는 패턴을 사용하지 않으므로 NVM에 대한 Prefetch 효과는 제한적이다.
-두번째, coss-page prefetch는 High Coverage와 Fewer row activation을 위해 낭비되는 Prefetch를 Trade 해야한다.
-Page가 Open 되면 향후 Page에서 Access할 수 있는 블록을 가능한 많이 Prefetch해야 한다, 나중에 누락된 Data block에 Access할때 Page를 다시 open하지 않도록 해야한다.
-비순차적이고 높은 병렬 실행으로 불규칙한 패턴이 생성되며 낭비되는 Prefetch를 발생 시킨다. 이러한 낭비를 감소시키위해 종종 Prefetch의 범위를 줄여야 한다.
-세번째, cross-page prefetch는 future physical page를 정확하게 예측해야 한다.
-그러나 메모리 계층 구조의 하위 수준에 위치한 HW Prefetcher는 Physical-Virtual 매핑이 존재하지 않기때문에 쉽지 않다.
-이전 연구 기록에서는 실제 App에서 가상 페이지의 50%이상이 연속되지 않는 물리 페이지에 매핑된다는 것을 말해준다.
제안
-데이터 집약적 App의 Long term access pattern을 분석하고 두가지 측면에서 패턴을 발견했다.
-(1)Inter - Page Access는 종종 일정한 보폭을 보인다.
-(2)Intra-Page Access는 연속적인 데이터 블록에 집중 되어있다.
-논문에서 이 패턴을 Ladder Stream 이라 하며, 연속적인 페이지 내의 블록은 Rung이라고 한다.
-Prefetch Request는 Request Queue에 들어가지 않고 CPT에 임시로 저장된다.
-페이지 간의 예측 정확도를 향상시키기 위해 가상메모리 주소와 물리적 메모리 주소 간의 매핑을 유지하기 위해 Memory Mapping Table(MMT)라는 구조를 제안한다.
효과
1. NVM에 대한 cross-page prefetch의 필요성에 대해 탐구한다.
2. Ladder Stream Pattern이 다양한 APP에 광범위하게 존재한다는 것을 발견했다. 이를 식별하기 위해 구조와 방법을 제안한다.
3. Ladder Stream Pattern을 활용해 inter-page prefetch와 공격적인 intra-page prefetch를 동시에 수행하는 LSP를 구축한다.
inter-page prefetch 경우 Ladder Stream의 Rung들 사이의 규칙을 찾으며, intra-page prefetch경우 future rung을 대략적으로 가져옴으로 높은 커버리지와 fewer row activation을 위해 낭비적인 프리페치를 Trade한다.
4. LSP에 대한 두가지 최적화를 제안한다. CPT는 Memory Queue의 상태에 따라 Prefetch 요청을 예측적으로 스케쥴링하여 간섭을 줄인다. CPT는 단일항목 사용, MMT는 Virtual Space에서도 작동할 수 있도록 사용
Background
EDC-NVMM Architecture
-뱅크의 액세스는 Row buffer에서 Data를 R/W 한다.
-NVM의 Precharge 및 Activation의 경우 DRAM보다 10배정도 느리다. (일반적 구성에서 tRCD가 DRAM의 10배이다.)
Ladder Stream Pattern
-예시로 세 Page의 Access bitmap을 보여주며 각 비트는 해당 블록에 액세스 했는지 여부를 나타낸다.
-Intra page access는 빨간색 영역으로 집중되고 빨간색 영역들끼리는 Stable distance를 가진다.
-Intra Page access와 inter page access를 모두 포함하는 메모리 흐름으로 ladder stream을 정의한다.
많은 응용프로그램에는 알고리즘, 데이터 구조로인해 Ladder stream이 존재한다.
Ladder stream pattern은 Inter page prefetch를 용이하게 한다.
1. future inter page pattern 제공,
2. rung에 대한 intra page prefetch는 일련의 연속 블록을 대략적으로 예측하면 되며, 잘못된 예측의 오버헤드는 새로운 row activation없이 상대적이로 낮다.
Proposed Technic
Ladder Stream Pattern
-SP는 LLC에서 MC로 도착하는 Memory Request를 Track하고 Ladder Stream을 식별하며 Memory Queue에 Prefetch를 실행한다. 구조와 실행은 Fig3에 나와있다.
-1단계, Memory Access가 도착하면 LSP는 기존 Ladder Stream에 속하는지 확인하고 그렇다면 LSP는 이를 Ladder Stream에 병합
-2단계, 그렇지 않으면 LSP는 이를 Rung Table(RT)에 삽입하고 rung을 형성할 수있는 Access를 식별한다.
-3단계, 식별된 Rung을 Ladder Stream Table(LST)에 병합하고 Ladder Stream의 향후 Rung을 예측하여 CPT에 삽입한다.
-4단계, Memory Request Queue의 상태에 따라 CPT는 예측적으로 Prefetch 를 요청하고 Track한다.
A. Rung Identification
LSP는 RT를 사용하여 rung을 식별한다.
각 RT항목들은 physical page 에 대한 기록 access를 추적한다. "Page"는 실제 Page 번호이다.
"Start", "End"는 각각이 물리적 페이지에 액세스되는 최소 및 최대 블록 번호이다.
"Count"는 이 페이지에 대한 Access 수를 기록한다.
LRU 정책을 사용해 Replace한다.
intra page access set는 액세스 count가 rung 길이의 절반이상일때 Ladder stream에서 rung을 형성한다.
access 순서를 무시하므로 Out of order나 interrupted된 access들의 복잡한 pattern을 간단하게 허용한다.
그림 3에 표시된 예에서 페이지 C의 11 번째 블록 (C [11]로 표시)에 대한 액세스 요청이 들어 오면 RT 항목에 도달하고 카운트는 4가됩니다.
길이는 8이고 액세스 횟수는 길이 / 2와 같습니다. 따라서 렁 C [4, 11]이 식별됩니다. 주소 변환 후 {Start : 260, Length : 8, Page : C} 렁이 LST에 병합됩니다.
B. Rung Merging
LST에서 "Strides"는이 래더 스트림에서 rung 사이의 블록 수를 나타낸다.
"페이지"는 렁이있는 물리적 페이지 번호의 배열입니다. "길이"는 최대 렁 길이를 나타냅니다.
그림 3에서 볼 수 있듯이 페이지 크기는 4KB이고 블록 크기는 64B이며 실제와 가상 간의 주소 매핑은 MMT에 기록됩니다.
새로운 렁 C [4, 11]이 도착하면 LST 입력에 도달하고 새로운 보폭 값은 80입니다. 보폭 배열은 가득 차고 안정된 보폭 값은 80이므로 래더 스트림이 식별됩니다.
가상 주소 공간에서 렁의 시작 블록 주소는“100, 180, 260”입니다. 물리적 주소 공간에서 렁은 "A [36, 43], B [52, 59], C [4, 11]"입니다.
이 래더 스트림의 렁 길이는 8입니다. 따라서 i 번째 미래 렁은 260 + i × 80이 될 것으로 예측됩니다. 첫 번째 향후 단계 인 D [20, 27]은 집합 적 프리 페치의 후보입니다.
LSP는 INTER(rung의 시작주소와 ladder stream의 시작주소간의 차이 무시값)를 동적으로 조정하여 정확도와 공격성을 조정
C. Collective Prefetching Table
그림 4는 공격적인 페이지 내 프리 페칭 및 집합 적 프리 페치의 지연 시간 감소로 인한 수요 요청의 추론을 보여줍니다.
두개의 뱅크에 4개의 NVM Memory Row가 있다고 가정, Row a, Row c는 Bank0, Row b, Row d는 Bank1
프리 페치가없는 경우 각 뱅크에는 세 가지 활성화가 있습니다. 집합 적 프리 페치가없는 LSP의 경우 A [i + 1], B [j + 1]이 프리 페치되고 시퀀스는
A [i], A [i + 1], B [j], B [j +1], C [k], D [h]. A [i + 1]은 B [j]가 메모리 큐에 들어가는 것을 방지하고 B [j]는 C [k]가 메모리 큐에 들어가는 것을 방지합니다.
결과적으로 LSP가 두 행 활성화를 제거 할 수 있지만 전체 대기 시간은 프리 페치가없는 경우보다 훨씬 더 길어집니다.
집합 적 LSP에서 프리 페치 요청은 요청 큐에 직접 들어 가지 않고 일시적으로 CPT에 저장됩니다. CPT는 사용 가능한 메모리 대기열 항목의 수가 뱅크 수보다 크거나 같을 때이를 추측 적으로 발행합니다.
프리 페치 요청이 각 은행의 요청을 차단하지 않도록합니다. CPT의 스토리지 오버 헤드를 줄이기 위해 렁에 대한 여러 프리 페치 요청의 상태를 하나의 항목으로 조합합니다.
그림 4와 같이 대기중인 메모리 큐에 대한 지연을 그에 따라 제거 할 수 있습니다.
Experiments
