# Accelerating Pointer Chasing in 3D-Stacked Memory: Challenges, Mechanisms, Evaluation
###### tags: `PIM` `Onur Mutlu` `ICCD '16`
###### papers: [link](https://people.inf.ethz.ch/omutlu/pub/in-memory-pointer-chasing-accelerator_iccd16.pdf)
###### slides: [link](https://people.inf.ethz.ch/omutlu/pub/in-memory-pointer-chasing-accelerator_hsieh_iccd16-talk.pptx)
## 0. Abstract
* 將 pointer chasing 的部份移到 memory 做，因為原先由 CPU 做會有兩個缺點：
* irregular access 造成頻繁的 CPU miss & TLB miss
* 每次 data 都要從 memory 端 send back，CPU 才能決定下一個 access 的 pointer
* 提出 IMPICA，在 memory 做 pointer chasing，有以下困難：
* 如何達到高平行執行
* 如何不透過 CPU's MMU，在 memory side 完成 virtual-to-physical address translation
## 1. Introduction
* The Parallelism Challenge
* 因為 dependent sequential access，即使在 memory 也很難做到 parallelism
* 當前一個 pointer chasing 在等待 memory access 的時間時，會先做下一個 address generation，稱為 address-access decoupling，以此來減少等待時間
* The Address Translation Challenge
* 因為 linked list 指向的位置也是 virtual address，若是 in-memory 來做，每次做完都要由 CPU 傳 physical address，那就有很大的 overhead
* 單純跟 CPU 維持同一份 TLB 也是有很大的 overhead，要解決 coherence、duplication 等問題
* 直接將 IMPICA 會使用到的 data structure map 到 virtual memory space 中連續的空間，並設計新的 translation mechanism，region-based page table
## 2. Motivation
## 3. Design Challenges
### 3.1. Challenge 1: Parallelism in the Accelerator
* simple accelerator 會比 multi-cores 來得慢，因為他要 serial 執行
* IMPICA 將 address generation 跟 memory access 使用兩個引擎分開，因此可以達到接近同步執行的效果
### 3.2. Challenge 2: Virtual Address Translation
* IMPICA 所使用的 page table 完全分離於 CPUs
* 只會在連續的 virtual address map IMPICA 需要 access 的空間，稱為 IMPICA region
* 若只要 map IMPICA region，那可以修改目前傳統的 page table，改為較少 overhead 的 IMPICA page table
## 4. IMPICA Architecture
## 4.1 IMPICA Core Architecture
* 將 core 分為兩部分：
* address engine，產生 pointer 的 address，包含所有 IMPICA's functional units
* access engine，使用 address engine 產生的 address 來 access memory，會透過 IMPICA page table 把 virtual address 轉成 physical
* 步驟：
1. host CPU 將 pointer chasing operation 放入 main memory，並 enqueue request
2. address engine load pointer chasing code into instruction RAM
3. 執行 instruction RAM 的 code，並使用 data RAM 為 stack，所有不需要 memory access 的部份都由 address engine 來做，如 ALU operations、control flow，data RAM 中的 stack 決定了有幾個 pointer chasing operations 能夠同時執行
4. 當 address engine 遇到 memory instruction，他 enqueue address 跟 data RAM stack pointer into access queue，access engine 將 virtual address 透過 IMPICA page table 轉成 physical 後送入 memory controller
5. 當 address engine 從 memory controller 得到 data 後，將它存到 IMPICA cache
6. 跟 return data 對應的 access queue entry 會從 access queue 移到 response queue
7. address engine 會監視 response queue，當 response queue entry 好了， address engine 會去讀 return data
## 4.2 IMPICA Page Table
* region-based page table (RPT) 分為三個層級：
1. first-level region table，7-bits，在 region 中找到對應的 flat table
2. second-level flat table，每個 region 中較大的 page (2MB)，20-bits，在 flat page table 中找到對應的 small page table
3. third-level small page table
* 轉換成 physical address 步驟：
1. [47:41]，7-bits 用來 index region table，並以此找到對應的 flat page table
2. [40:21]，20-bits 用來 index flat page table，並提供 small page table 的位置
3. [20:12]，9-bits 用來 index small page table
4. [11:0]，11-bits 用來確定 physical page 中的 offset
* 不同大小的 pages 提供了放置上的彈性，OS 可以選擇要用 2MB 還是 4KB 作為 last level
* 此方法只會有兩個 misses，flat page table 跟 last-level page table
## 5. Interface and Design Considerations
### 5.1. CPU Interface and Programming Model
* 執行步驟：
1. CPU 將包含 function call and parameters 的 packet 送入 memory
2. packet 寫入特定的位置(data RAM 中的 predefined location)，並以此 trigger execution
3. IMPICA 讀取 predefined location，並 load 到 inst RAM
4. IMPICA 完成 execution 後，將 Value 寫入 data RAM，CPU 會 periodically polls 這些 location
### 5.2. Page Table Management
* 使用特殊 API 來 allocate pointer-based data structures
* OS 會為了 IMPICA 保留一塊連續的空間
* OS 會保持 IMPICA RPT 跟 CPU page table 間的一致性，若有更新到 IMPICA region，會 shoot down IMPICA RPT
### 5.3. Cache Coherence
* 所有牽涉到 IMPICA region 的指令都在 IMPICA 做，因此 IMPICA 一定會看到最新 update 的資料
## 6. Methodology
## 7. Evaluation
## 8. Related Work
## 9. Conclusion