# 簡介 NUMA 架構
Contributed by < `JulianATA` >

本篇的重點在於簡介 ` NUMA ` 架構、整理 Linux kernel 對於 ` NUMA ` 的支援、以及學術上 ` NUMA ` 架構下的研究議題。

## 什麼是 NUMA ?

` NUMA ` 全名為 ` Non-uniform memeory acces `，是一種多處理器下的記憶體架構。


在 ` NUMA ` 架構下，本地記憶體存取 ` local memory access ` 的速度會比非本地記憶體存取 ` non-local memory access ` 快上許多。 上圖中的 ` Node1 ` 中的 ` Core ` 要存取 ` Node1 ` 中的記憶體，就要比透過 ` Interconnect ` 存取 ` Node2 ` 的記憶體快上許多。

但也因為這樣的特性，在軟體/作業系統上需要考慮更多的議題，例如：
* Interconnect 的圖論意義與負載問題
* Page placement 的策略
* Scalability
* Shared data 的 routing path

創造一個架構，帶來眾多的議題是不是反而弊大於利？
以下節錄了一段分享的內容，解釋探討 ` NUMA ` 問題的必要性。

> In practice, what `NUMA` means is that the amount of CPU and memory has grown so large that is no longer makes sense for all memory in your system to be accessible for all memory in your system to be accessible with at the same levels.
> [name=Stephen Finucane From OpenStack][color=#ed1844]

實際上， ` NUMA ` 架構的出現更傾向於因為核心跟記憶體的數量越來越大，已經再也沒辦法 ` 宣稱 ` 每個核心對於每個記憶體的存取在同一個等級。
因此，` NUMA ` 其實並不是設計出來的複雜架構，而是，因為電腦架構的日漸龐大，造成 ` NUMA ` 架構的誕生。

### NUMA vs ccNUMA
在 ` NUMA ` 架構之下，` ccNUMA ` 是常常被探討的架構，也是 Linux kernel 目標支援的架構。
` ccNUMA ` 全名是： ` Cache Coherent Non-Uniform Memory Access `。 是在 ` NUMA ` 架構之下，考慮 ` Cache Coherence ` 的設計。

#### Cache Coherence Problem:
Cache 機制透過放置一個快速且較小的記憶體供 Core 暫存資料，以此降低記憶體存取時間與記憶體 bandwidth 需求。

* 其中的 $ (cash符號)代表 cache

Cache 機制有一個重點是要維持 Coherence。當 Shared data 被寫入的時候，要讓其他存有該 Shared data 的 Core/Cache 做出應對，確保他們看到的 Shared data 是最新的。

其中有兩個主流的方法來確保 Coherence，` snooping ` 和 ` directory-based `，這邊就省略這兩個方法細節的介紹。

在較低的核心數，如 8 核心的電腦上，` snooping ` 的效果很好，但有著較差的 scalability。因此在大部分 ` ccNUMA ` 架構下的電腦，多以 ` directory-based ` 為主。但仍然有以探討 ` snooping ` 機制於 ` ccNUMA ` 上的研究。

#### Directory-based Protocol
` Directory-based Protocol ` 會用三種狀態來描述 Shared-data ：
* **U**ncacehed: Data 狀態是閒置的。
* **S**hared: Data 的狀態有被其他 core 使用。
* **E**xclusive: 代表 mutual exclusive。 表示 data 正在被 write ，需要更新手邊的 data 。
* 並且會搭配 Bit vector 來形容狀態。例如： S1010 代表狀態為 Shared 並且， Core0 以及 Core2 正在只用。

這邊透過一個例子，了解 Shared data 在 ` directory-based ` 被 write 的機制。
* **X**[S1010]：起始狀態，有一 data **X** 在記憶體中，並同時存在 Core0 與 Core2 的 Cache 之中。
* Core0 欲寫入 **X**。
* 透過查詢狀態 **X**[S1010]，發現其他 Core 的 Cache 存有 **X** 。
* Core0 發生 ` Write Miss `。
* 透過狀態 **X**[S1010] 清除非寫入 Core ( Core2 ) Cache 的 **X**
* **X**[E1000]：因為 Core0 欲寫入 **X**，清除非寫入 Core 的 Cache，並將狀態改為 **E**xclusive 。如果在 **E**xclusive 狀態下，其他非寫入 Core 欲存取 Shared data **X** 則會發生 Read miss。
* Core0 寫入 **X**。
* 透過查詢狀態 **X**[E1000]，發現可以寫入。
* 寫入後將狀態改為 **X**[S1000]
* **X**[S1000]：寫入後，修改狀態為 **S**hared。可供各個 Core 存取。

透過這個例子可以了解維護 Coherence 的開銷，不論是否基於 ` NUMA ` 都會有很大的開銷。

#### ccNUMA:

` ccNUMA ` 架構是在 ` NUMA ` 下考慮 Cache Coherence 的問題。
` ccNUMA ` 下的 Cache Coherence 仰賴處理器或 Interconnect 的支援。 因為 ` NUMA ` 對於非 Local 的記憶體的開銷較大，維持 Cache coherence 的開銷也跟著上漲。

Linux 主要目標支援的框架
簡述 Cache coherence 對於

## Linux 對於 NUMA 架構的支援
### system call
https://hackmd.io/@hPMCWajOS-ORQdEEAQ04-w/BJbBlhbTH
https://hackmd.io/@hPMCWajOS-ORQdEEAQ04-w/BkeOsHUoH
### numactl

### numastat

## NUMA 架構上的難題
### Interconnect 的圖論意義與 Routing Path of shared data
簡介各種類型的 Interconnect 以及 multi core 之下的 routing path problem

列舉常見的 Interconnect 圖型，並簡述 routing path on the different graph.

### Page Placement
簡介從 naive 到 carrefour 再從 carrefour 討論到 asymmetric，以及最近的 bandwidth 考量導向，改編整理以下筆記。
https://hackmd.io/@hPMCWajOS-ORQdEEAQ04-w/Sy_WxizBU

### Scalability

## Reference:
* kernel.org: [What is NUMA?](https://www.kernel.org/doc/html/latest/vm/numa.html)
* [The Wonders of NUMA, or Why Your High-Performance Application Doesnt Perform](https://www.youtube.com/watch?v=4JleOfUeDvg)
* [Linux 核心設計: 記憶體管理](https://hackmd.io/@sysprog/linux-memory)
* [ASPLOS (2013): Traffic Management: A Holistic Approach to Memory Placement on NUMA Systems](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.369.7885&rep=rep1&type=pdf)
* [USENIX ATC(2014): Large Pages May Be Harmful on NUMA Systems](https://www.usenix.org/system/files/conference/atc14/atc14-paper-gaud.pdf)
* [USENIX ATC(2015): Thread and Memory Placement on NUMA Systems: Asymmetry Matters](https://www.usenix.org/system/files/conference/atc15/atc15-paper-lepers.pdf)
* [Eurosys(2019): Compact NUMA-aware Locks](https://arxiv.org/pdf/1810.05600.pdf)
* [IEEE IPDPS(2020): Bandwidth-Aware Page Placement in NUMA](https://arxiv.org/abs/2003.03304)
* [numactl](https://github.com/numactl/numactl)
* [numatop](https://github.com/intel/numatop)
* [numastat](https://man7.org/linux/man-pages/man8/numastat.8.html)