# CoNDA: Efficient Cache Coherence Support for Near-Data Accelerators
###### tags: `PIM` `Onur Mutlu` `ISCA '19`
###### `papers`: [link](http://users.ece.cmu.edu/~saugatag/papers/19isca_conda.pdf)
###### `slides`: [link](https://people.inf.ethz.ch/omutlu/pub/CONDA-coherence-for-near-data-accelerators_isca19-talk.pptx)
## 0. ABSTRACT
* near-data accelerators(NDAs) 有許多好處，但是若要解決 coherence 問題會有以下兩個困難點：
1. NDAs 跟 CPUs 間的溝通 cost 很高
2. NDA application 會產生許多 off-chip data movement
* 經過作者的實際實驗發現兩個特性：
1. 大部分的 off-chip coherence 是不必要的
2. 大部分的 off-chip traffic 可以被避免，如果 coherence mechanism 真的實際了解 NDA 的 memory access
* 作者提出 CoNDA 的 coherence mechanism，首先讓 NDA 以沒有 coherence 情況為前提直接執行，再把真的要執行 coherence 的部份重做，以此來減少不必要的 data movement
## 1. INTRODUCTION
* NDA 要實作 coherence 會有兩點困難
1. NDAs 跟 CPUs 間的溝通 cost 很高，以 HMC 來說，move data 所消耗的能量跟讀取 DRAM data 一樣
2. 因為 NDA application 比較少計算的需求，所以會有 poor locality 並產生大量的 off-chip data movement，因此會產生大量的 coherence miss，所以若套用 MESI，每個 cache miss 都要處理 coherence 會消耗大量使用 NDA 所帶來的好處
* 作者觀察到兩個現象：
1. application 中並不是所有部分都適合在 NDA 上，而部分在 CPU 上執行的部份會同步的存取在 NDA 上執行的部份，所以需要大量的 data sharing
> 真的嗎？ 要思考怎切的[name=david]
2. 雖然有大量 data sharing，真的 access 到同一個 cache line 的機率很小，而且就算真的同步 access，大部分都只有 read，不會去修改到實際的 data
* 比較現行的三種 coherence mechanisms：non-cacheable regions、coarse-grained coherence、fine-grained coherence，發現兩個現象
1. 這三種方法都會消除掉許多 NDA 產生的好處
2. 大部分所做的 cache coherence 都是不必要的，架構上都消極的認為所有 memory access 都需要獲得 coherence permissions or shared data cannot be reached，但實際上是不需要的
* 但可惜有時候要實際執行才能知道這件事，如 pointer or graph traversal
* 作者提出 CoNDA 的架構：
* 一開始先執行 optimistic execution，假設 NDA 完全擁有 coherence permission，不需要任何的 coherence message
* 執行 optimistic execution 的時候，CoNDA 不會真的 commit data update
* 若真的不需要執行 coherence operation，才會 update data
* 若有部分需要執行 coherence operation，執行需要的 coherence operations 並重新執行 NDA kernel portion
* optimistic execution model 適合 NDA coherence 有三個原因：
1. 可以真的了解需要做的 coherence
2. CPU 真的需要跟 NDA update 同樣的 data 的機率非常低
3. NDA 因為使用較為不複雜，且通常不支援 ILP 的 core，所以重新執行 NDA kernel 的 cost 較小
* 此論文的 contributions:
* 探討兩種 applications 發現了三個現象：
1. CPU threads 通常不會 update NDAs 正在使用的 data
* 探討後發現：
1. coherence 問題處理不好會消除 NDA 產生的 performance 跟省下的 energy
2. 大部分的 off-data movement 是不必要的
3. 不必要的 coherence 可以透過實際了解哪些 memory access 真的需要 coherence operation 而得知
* 提出 CoNDA，新的 coherence mechanism 來改善此問題
## 2. BACKGROUND
* 此論文的 NDA 規格：
* in-order cores
* ISA-compatible
* small L1 I/D caches
* do not have any sophisticated ILP techniques
## 3. MOTIVATION
* 允許 coherence 有兩項優點：
* 在有 NDA 情況，programmers 仍可以使用傳統的 shared memory models
* 簡化 accelerators 間的 communication and share data
### 3.1 Application Analysis
* Application 應該要分為某部分給 NDA 做，某部分留在 CPU 做
* NDA 適合 memory-intensive
* CPU 適合 compute-intensive，尤其是需要 cache hierarchy or 複雜 ILP 技巧
* 探討 multithreaded graph processing frameworks, such as Ligra，若是把適合 CPU 跟適合 NDA 的部份分開，可以發現 CPU 約有 60.1% and 71% (graph, intermediate data structure)的 LLC misses 存取 shared memory
* 探討 hybrid transactional/analytical processing (HTAP) database system，主要有 analyical and transactional operations，analyical operations 適合在 NDA 執行，transactional operations 適合在 CPU 執行，因此兩者間的同步 access 是不可避免的
* 分析 Connected Components and Radii algorithms from Ligra，發現只有 5.1% and 7.6%會同時存取同樣的 elements，而其中又只有 11.2% 會由 CPU thread 寫入，其他 CPU threads 都只有 read
* 這類型的 accelerator-centric application collide 機率低的原因是因為 programmers 特意設計，會避免 CPU thread update
### 3.2 Analysis of NDA Coherence Mechanisms
* 探討三種 CPU threads and NDAs 間使用的 cache coherence 機制:
* Non-Cacheable Approach
* Coarse-Grained Coherence
* Fine-Grained Coherence
* Ideal-NDA
* 假設執行 coherence 不會有任何 energy and performance penalty
* Non-Cacheable Approach
* 把所有 NDA 可以 access 的資料區段 (NDA data region) 都設為 non-cacheable，也就是說 CPU 有甚麼 data update 都直接讓 NDA 看到
* 如果 CPU 常常要 access 到 NDA data region，那效能就會非常差，透過實驗可以發現，跑 Ligra application，input 是 arXiv，CPU 有 38.6% 都 access 到 NDA data region
* Coarse-Grained Coherence
* 每當 NDA 獲得 coherence permission，CPU 會 flush 所有 dirty cache lines in NDA data region
* 但事實上 NDA 不會 access 那麼多 data，造成不必要的 data movement
* 即使把 granularity 降低到一個 entry per page，還是可能因為 irregular aceess pattern，造成要 flush 所有改變到的 pages，但其實只有 access 一些 cache lines
* 有些 coarse-grained coherence 會使用 coarse-grained locks 來讓 CPU and NDA 只有其中一個可以 access coarse-grained region，這樣造成 CPU and NDA 要循序的執行，無法同步，讓效能變差很多
* Fine-Grained Coherence
* Fine-Grained Coherence (e.g., MESI)，有兩個性質適合 irregular memory access
* 當在做 pointer chasing 時，只有該 pointer 的部分會得到 coherence permission，不像 coarse-grained coherence 會是整個 region
* 在實作 NDA 時，programmars 不需花費多餘力氣，因為目前 multithreaded programs 都使用這種 programming model
* NDA 跟 CPU 需要每次 cache miss 都要交換 message，而事實上 CPU write 的機率是偏低的，造成不必要的 overhead
* 總結這些 cache coherence 問題，都是因為沒有真正的執行 memory operation，所以不會知道是否真的要執行 coherence，這些 coherence 方法也無法有效發揮 NDA 所產生的好處
* 
* 
## 4. OPTIMISTIC NDA EXECUTION
* 大部分因為 coherence 問題產生的 data movement 都是不必要的，因為那些機制都悲觀的認為：
* 每一個 memory operation 都需要獲得 coherence permission
* CPUs and NDAs 間的 data shared 不能被 cached
### 4.1 Execution Model
* application 在 CPU 上跑的時候可以要求開始在 NDA 上跑，而原先的 CPU thread 可以同步進行，NDA 會在 optimistic mode 下跑，假設擁有所有的 coherence permission，但產生的 data 不會 commit，而是在 optimistic execution stop 的時候決定是否在這期間有 coherence request，若沒有，則直接 commit，若有，則重做該部分，而因為其實 CPU and NDA 幾乎不會同時 access 同一個 cache line，這讓 optimistic execution 很有效率
* programmer 不會知道會執行 optimistic execution，只會認為 NDA 是另一個 thread，而在需要在 NDA 執行的部分會加入 MACRO 來做為辨識
* programmer 對於同步的 CPU thread 應有這些認知
* 在系統的 memory consistency model 下，所有指令在 multi thread 的情況下是可以 interleaved 的
* 如果想要有特定的 ordering，要自己下 synchronization primitives
### 4.2 Identifying Necessary Coherence Requests
* 討論三種 CPU and NDA memory operations to same cache line 的情形
* Case 1: NDA Read and CPU Write (to the Same Cache Line)
* Case 2: NDA Write and CPU Read (to the Same Cache Line)
* Case 3: NDA Write and CPU Write (to the Same Cache Line)
* Case 1: NDA Read and CPU Write (to the Same Cache Line)
* 會需要 re-execution
* CPU 寫入的資料要 flush 回 DRAM，NDA 再重做該部分
* Case 2: NDA Write and CPU Read (to the Same Cache Line)
* 不需要 re-execution
* 因為 update buffer 要等到可以 comfirm 時候才能 update，CPU 可能讀到舊資料(C6/N5)，但若是 prgrammer 想要保證 CPU 讀到 NDA 產生的新資料，那他要下 synchronization primitive 來保證
* Case 3: NDA Write and CPU Write (to the Same Cache Line)
* 不需要 re-execution
* 如果 CPU and NDA 同時寫入 cache line，當 NDA 要 commit 的時候，不能直接覆蓋 CPU 寫入的 cache line，而是透過 per-word dirty bit mask，把 CPU 修改的 cache line 資料留下，只把 NDA 在 update buffer 中的 data 放入
## 5. CoNDA ARCHITECTURE
### 5.1 Program Interface
* programmer 使用兩個 MACRO：NDA_begin and NDA_end 來框出要在 NDA 執行的 code section
* compiler 會將 MACRO 轉成新加入 ISA 的 instruction，並分別 trigger and end NDA kernel execution
* CoNDA 需要知道 NDA data region 使用哪些 pages，可以由 compiler 辨識，也可以由 programmer 標記
* CoNDA 會將這些 page table entry 加上一個 bit，當在執行 optimistic execution 需要 track read/write to page 的時候可以使用
### 5.2 Starting Optimistic NDA Execution
* 當 NDA kernel 開始時，CoNDA 會開始 optimistic execution，CPU 會分配 kernel's starting Program Counter(PC) and 可以使用的 register 到 NDA
* 每次 optimistic execution 開始時，CoNDA 會把現在的 NDA state，也就是 NDA's PC and software-visible registers 記錄起來，若是 commit fail，可以 re-execution
### 5.3 Signatures
* CoNDA 使用 signature 來 track optimistic execution 是否需要 coherence request
* **Implementation**
* 使用 fixed-length parallel Bloon filter
* N-bit signature 切割成 M segment，每個 segment 跑獨自的 hash function，並將 bit 設成 1
* 透過 parallel Bloon filter，CoNDA 可以完成三個 operations:
1. 透過檢查所有的 M segment，確認 filter 是否包含輸入的 address
2. 使用 signature extension technique，找回 filter 中的 address
3. 使用 bitwise 的 AND operation，快速比對兩個 filter 中是否有相同的 address
* 可能產生 false positive，re-execution，但其實不需要
* 每次 optimistic execution 開始的時候會 reset filter
* **Tracking Memory Operation During NDA Execution**
* CoNDA 包含三種 set of signatures
* NDAReadSet
* NDAWriteSet
* CPUWriteSet
* CPUWriteSet 記錄某些 cache line 在 NDA data region 中的 address：
* CPU thread writes during optimistic execution
* NDA kernels 執行前，CPU cache 中的 dirty copies
* 包含 TLB overhead，整個 CPU scan 的時間不超過總共執行時間的 1%，因為 NDA kernel 常常需要大量時間運算
* 如果真的產生 performance bottleneck，也可以使用 Dirty-Block Index 來 track dirty NDA data
* **Signature Size**
* 每個 Bloom Filter 由一個 fixed length register 組成，register size 決定總共有多少 address 可以被加入 filter 並不會超過 false positive rate
* 一旦可以儲存的 address 超過上限，CoNDA 結束 optimistic execution，並處理必要的 coherence request
* NDAReadSet 跟 NDAWriteSet 各自有一個 256B register，並分成四個 Segment
* CPUWriteSet 使用 8 個 256B Bloom filter，並使用 round-robin 決定要放哪個
* false positive rate 設為 20%(worse case) in CoNDA，大概允許每個 256B register 儲存 250 address
> bloom filter 真的不會造成 false positive? 要多了解這塊 [name=david]

### 5.4 Buffering Uncommitted Values
* 因為 NDA 要等到 optimistic execution 結束才能 commit data，在那之前會先將 updated data 存在 自身的 L1 data cache
* 在每個 cache line 加入 per-word dirty bit mask
### 5.5 Ending Optimistic NDA Execution
* CoNDA 以三種事件發生來動態決定什麼時候要結束 optimistic execution：
1. NDA reaches the end of NDA kernel
2. NDA L1 cache 需要釋出某個特定的 cache line
3. 其中一個 signature 無法儲存更多 address
* NDA 會使用 counter 記錄幾個 address 存入 signature 中
### 5.6 Identifying Necessary Coherence Requests
* NDAReadSet 跟 NDAWriteSet 會傳入 CPU 中的 coherence resolution logic，並計算 NDAReadSet 跟 CPUWriteSet 間的交集
* 根據交集結果，有兩種情況
1. Case 1 (Conflict)
* 不能 commit update date
* CPU 將 NDAReadSet 儲存的 address 對應的 dirty cache line flush 到 DRAM，並複製到 NDA L1 cache 中
* roll back to checkpoint，NDA 重新執行
* 設定一個 N 值(論文中是 '3')，若超過 N 次都 fail，那將 NDAReadSet 對應的設為 read-only，以此避免不斷的失敗
2. Case 2 (No Conflict)
* 計算 NDAWriteSet and CPUWriteSet 的 intersection，如果有 overlap，使用 signature expansion 來判斷哪個 cache line 要 merge 對方，保證了 write-after-write coherence
* CPU cache 中對應到 NDAWriteSet 的都設為 invalid
* 將 uncommited flag 清除，並允許 cache line 放入 DRAM
* 繼續執行 optimistic execution
* 在做 coherence resolution 時，CPU thread 繼續執行，但把 NDA data region 使用到的 cache line 設為 locked，並保證 atomic，若碰到那些 cache line，CPU thread stall 直到完成 coherence resolution
### 5.7 Support for Synchronization Primitives
* CoNDA 允許 programmer 使用 synchronization primitives 來手動控制 memory operations 的 order and atomic
* 當 NDA 碰到 synchronization primitives(Acquire, Release)，會有三個步驟：
1. CoNDA 結束 optimistic execution，並且 commit 所有 update data
2. NDA 執行 primitive non-speculatively，執行所有必要的 coherence operations，以此保證 primitive 不會被 rolled back，如同傳統 CPU multithreading
3. primitive 結束後，繼續執行 optimistic execution
### 5.8 Support for Weaker Consistency Models
* 講述 CoNDA 如何支援別的 consistency 架構
### 5.9 Hardware Overhead
* NDA 使用 512B to store signature
* CPU 使用 2kB to store signature
* CoNDA 整體硬體 overhead:
* 1 bit per page in the page table (0.003% of DRAM capacity)
* 1 bit per TLB entry for the page table flag bits (Section 5.1)
* a 1.6% increase in NDA L1 data cache size for the per-word uncommitted data bit mask (Section 5.4)
* two 8-bit counters per NDA to track the number of addresses stored in each signature.
## 6. METHODOLOGY
* CoNDA 使用 gem5 模擬器，在 full-system mode using the x86 ISA
* 修改 DRAMSim2，假設出 NDA 可以使用的 3D-stacked HMC DRAM
* 修改 gem5 的 Ruby memory model 來準確的設計 coherence model
* NDAs 自己有 local coherence directory，使用 MESI
* CPU coherence directory 是 整個系統的 main point of coheremce，使用 MESI
* 在做 coherence resolution 時，有以下 overhead：
* NDA 傳送 signature 到 CPU 要花 20 cycles
* compare CPU/NDA signature 花 2 cycles
* invalidate CPU cache line 花 8 cycles
* 從 CPU 轉移 cache line 到 NDA 並 merge 要花 12 cycles
* 以上皆是保守估計，可能不用那麼多 cycles
* NDA kernel re-execution 的 overhead 如下：
* invalidating uncommitted cache lines and erasing signatures
* rolling back the NDA to a checkpoint
* resolving coherence
* re-running the kernel.
* 假設 NDA rollback takes 8 cycles
* **Applications**
* 使用兩種 datasets:
* 中型 dataset，實驗大部分使用
* 大型 dataset，測試當 input size 變大的影響
* 從 Ligra 中測試三種 graph application
* Connected Components (CC)
* Radii
* PageRank (PR)
* 中型 dataset 的 graph application 的 input 從真實世界數據獲得，共有三種：
* Enron email communication network (73384 nodes, 367662 edges)
* arXiv General Relativity (10484 nodes, 28984 edges)
* peer-to-peer Gnutella25 (45374 nodes, 109410 edges)
* 大型 dataset 的 graph application 的 input 從真實世界數據獲得，共有兩種，平均比中型 dataset 大了 14.8 倍：
* the Amazon product network (334863 nodes, 925872 edges)
* the DBLP collaboration network (317080 nodes, 1049866 edges)
* **Identifying NDA kernels in Applications**
* 使用 hardware performance counter data 來判斷 application 的哪些 funciton 適合由 NDA kernel 來做，滿足以下條件：
1. memory-intensive(last-level cache misses per kilo instruction, or MPKI 超過 20)
2. data movement 是 function 中最大的能量耗損來源
3. function 屬於 application 中前三耗執行時間
* 透過把 malloc 改成 nda_malloc，告知 gem5 這段 data 屬於 NDA region
* 在 Ligra application，選擇 edgeMap()為 NDA kernel
* 在 HTAP workload，選擇 analytical queries(select and join operations) 為 NDA kernels
## 7. EVALUTION
### 7.1 Off-Chip Data Movement
* 16 CPU cores and 16 NDAs 下做實驗
* 比起第二好的 coarse-grained coherence，CoNDA 還要好30.9%
* NC 需要很多 Data movement，因為只要 CPU 修改到 NDA region 都需要寫回 DRAM
* 比起 CPU-only 減少了 86.3%，因為 memory-intensive 部分在 NDA 做
### 7.2 Performance
* 看 Ideal-NC 可以知道使用 NDA 是有很大可能可以加強效能(比平均高約 1.84x)
* CG and NC 都比 CPU-only 效能下降了些，因為要管理 coherence
* FG 雖然有效能進步，但比起 Ideal-NC 仍有一段差距
* CoNDA 只略輸 Ideal-NC 10.4%，贏 CPU-only 66.0% ; 贏 FG 19.6%
* NDA-only 只略贏 CPU-only 8.7%，因為沒有複雜的 logic 跟大的 Cache
* CoNDA 執行時間主要在三個因素上
1. NDA kernel execution
2. coherence resolution overhead (3.3%)
3. re-execution overhead (8.4%)
* coherence resolution overhead 低的原因:
* CPU thread 在做 resolution 的時候不會 stall，除非 access 到 NDA data region
* NDAWriteSet 能夠存的 address 不多(平均 6)，所以 CPU-side invalidations and NDA writebacks 不會很多
* 包含 sending resolution and checking 必要的 coherence operations，總共頂多 50 cycles
* re-execution overhead 低的原因:
* collision rate 很低(平均 13.4%)，真的要重做機率低
* 重作的時候有很大一部分的 instruction and data 都已經從在 NDA L1 cache，當從 CPU cache line flush 進 NDA cache 時，NDA 會先留一份 copy
### 7.3 Memory System Energy
* CoNDA 幾乎跟 Ideal-NDA 耗費的能量一樣的(多 4.4%)，比 CPU-only 好了 43.7%，並比第二好的 CG 好了18.0%
* FG 因為每個 cache miss 都要做 off-chip coherence traffic，所以比 CG 來的耗能
### 7.4 Multiple Memory Stacks
* 將 4 CPU cores and 4 NDAs 合成一個 stack，並做實驗分析
* stack 間連結在一起，使用 processor-centric topology
* 使用每個 NDA stack 中的 local NDA directory 來維持 coherence，使用 MESI
* Off-Chip Traffic
* FG scale 差，因為 stack 增多代表 coherence miss 機會增加
* CG scale 差，因為 stack 增多會線性的增加 writeback
* NC scale 差，因為 stack 增多會產生更多 traffic
* CoNDA 比起 CPU-only 減少 82% 的 traffic
* Performance
* CG 表現差的原因
* flush 的次數增加
* 當在同步執行的時候，CPU 可能會停住，此佔了整個 execution time 的 73.1%
* FG 比 CPU-only 好，但執行 coherence 也影響效能
### 7.5 Effect of Larger Data Sets
* 跑三個 application with larger dataset
* Connected Components
* Radii
* HTAP-1024
### 7.6 Effect of Optimistic Execution Duration
* 測試可以儲存的 address 數量，從 150 到 350
* 以兩個 workload: Connected Components with the Enron input graph, and HTAP-128 測試 execution time and off-chip traffic (normalized to CPU-only)
* 當 address 數量從 150 到 350
* total execution time 分別增加 5.7% and 10.5% for Connected Components and HTAP-128
* conflict rate 分別增加 18.3% and 41.2%
* off-chip traffic decreases, by 25.7% and 15.5%
* 結論:最適合的 address 數量為 250
### 7.7 Effect of Signature Size
* 結論:signature 固定在 256B 最好
### 7.8 Effect of Data Sharing Characteristics
* 三種 application 狀況
1. limited sharing
2. high amount of sharing, infrequent collisions
3. high amount of sharing, frequent collisions
* 針對第一種，CoNDA 表現的跟 CG, NC 差不多，而 FG 則較差
* 針對第三種，FG, CG, NC 表現得比 CPU-only 差了約 33.4%，CoNDA 越差了 2.1%
## 8. RELATED WORK
## 9. CONCLUSION