# HPL

## 基本概念
- Linpack: 一種用於解線性代數問題的數值計算軟體庫
- HPL (High Performance Linpack): a software package that solves a (random) dense linear system in double precision (64 bits) arithmetic on **distributed-memory** computers. It can thus be regarded as a portable as well as freely available **implementation** of the High Performance Computing Linpack Benchmark.
- GPU version: NVIDIA HPC-Benchmarks / HPL-NVIDIA 23.10.0

## HPL 運算過程

- 目的：求解 N × N 密集矩陣線性方程組，其值為 `HPL.dat` 中的參數 N （Problem size）。
- 求解方法：
1. 矩陣分解：用 LU 分解，將矩陣拆解成下三角矩陣與上三角矩陣
- 使用到 level-3 BLAS (Basic Linear Algebra Subprograms) 中的 DGEMM 函式，此函式用以進行雙精度的矩陣乘法
2. 使用 Forward substitution 處理下三角矩陣 L，求解方程組 Ly = b 中的向量 y，得到中間結果，下一步驟中會繼續使用。
3. 使用 Backward substitution 處理上三角矩陣 U，求解方程組 Ux = y 中的向量 x。這一步得到了方程組的解。
- 由於 BLAS 能針對不同的 architecture 實現記憶體最佳化的效能，在記憶體快取的部分能夠提升資料的重複使用率，因此能大幅度地提升HPL的運算效率。
- HPL 中，矩陣相乘運算（DGEMM）約佔總運算量的 70%，應作為效能調校的第一個重點。
- 相較於 CPU，GPGPU 更適合用於進行矩陣乘法運算。

> reference
[線性代數問題：數學問題剖析、高斯－佐丹消去法](http://boson4.phys.tku.edu.tw/numerical_methods/nm_units/linear_algebra_intro_n_Gauss-Jordan.htm)
[(LA-08, 2013/10/29-13) 列運算與LU分解](https://youtu.be/KYPiqtitEl8?si=Z9bYUxphJuO1ByUI)
>

## 資料分布

> reference
[Distribution Techniques](https://www.ibm.com/docs/en/pessl/5.3.0?topic=distributions-distribution-techniques)
[The Two-dimensional Block-Cyclic Distribution](https://netlib.org/scalapack/slug/node75.html)
>
- HPL 使用二維循環式塊狀資料分布（two-dimensional block-cyclic data distribution），將資料平均分配於叢集的各個節點中，提升叢集運算速度的效率。
- **Block Distribution:** 資料被分為固定大小的 blocks 或 subset，然後將這些 data block 分配給不同的計算節點。每個節點負責處理一個或多個完整的區塊。
- **Cyclic Distribution**（循環分佈）：將資料按照順序依次分配給不同的節點，直到所有節點都分配了資料，然後重新開始分配。可確保資料均勻分佈，並減少節點之間的資料通信和負載不平衡的問題。但在某些情況下，它可能會增加一些分配和索引的計算成本。
- **Block-Cyclic Distribution**：結合前述二者。資料被劃分為固定大小的區塊，並按照循環方式分配到不同的節點上。既確保了資料塊的大小固定，又能保持節點間的均勻分佈。這種方式常用於高性能計算和並行計算環境，能夠有效地利用計算資源，同時減少通信開銷和負載不平衡。

## HPL.dat 參數設定

- **Problem Size (N)**
- 這個數值表示 HPL 將生成、計算的線性系統之大小。
- 這個數字應接近填滿總節點的記憶體（以盡可能使用 primary storage 資源），又不至於超過記憶體大小（以避免過多的 swap）。
- 例如使用 4 個節點，每個皆有 256 Mb 的記憶體，共 1 Gb。已知每個矩陣元素是 8 bytes（雙精度），因此，記憶體共可容納 125M 個矩陣元素。對應的矩陣的尺寸 N，為該數開平方根，約為 11585。然而，我們需要留一些記憶體給 OS 或其他 process，因此可取 10000 作為 N。
- 根據經驗法則，可使用記憶體的 80-85% 來計算
- 使用 Nvidia 或其他 GPU 版本的 HPL 時，應參考 GPU VRAM 大小（GPU 專用的 memory）
- **Block Size (NB)**
- 由於 N*N 矩陣會被切分為不同的 block，分配到不同的 node 之中進行運算，因此需要決定每個 block 的大小，該值及為 block size NB。
- 以資料分配的角度來看，較小的 NB 會有較好的 load balance。
- 以計算的角度來看，過小的 NB 會限制計算效能，因為 highest level of memory hierarchy （存取速度最快）的 data 幾乎不會 reuse。
- 一般來說，NB 在 [32 .. 256] 可以得到不錯的效果。
- 應該選擇多少，主要取決於系統的 computation / communication performance ratio，並也受 N 的影響。
- Performance 可用 HPL 之輸出或 profiling 來了解，若計算效能提升，而溝通效能降低，則 NB 過大，導致通信增加。反之亦然。
- **Process Grid (P x Q)**
- 該值應為處理器的總數，以確保所有處理器皆在運算。
- Process grid 是一種將計算任務分配到不同處理器或節點的方式。
- 在 HPL 中，網格是由 P×Q 個處理器組成的，其中 P 表示網格的列數，Q 表示網格的行數
- 每個網格中的處理器可以是一個物理節點上的處理器或者是集群系統中的一個虛擬處理器。
- 通常選擇讓 P、Q 接近相等，使處理器網格為方形，以減少溝通成本與提高 load balance。
- 通常選擇 P≤Q，且 P 為 2 的冪次。
- 參考資料
- [HPL Tuning](https://www.netlib.org/benchmark/hpl/tuning.html)
- [HPL FAQ](https://www.netlib.org/benchmark/hpl/faqs.html)

## 優化矩陣乘法的方式

### 底層程式庫的效能：BLAS, math libraries

- BLAS implementation:
- 使用 architecture optimized BLAS library
- Intel Math Kernel Library (MKL) for Intel
- OpenBLAS, ATLAS 支援多種 architecture
- 優化編譯選項
- 如：gcc `-march=native` 或 `-O3` 等

### 優化 memory access pattern

- 優化矩陣儲存方式，對於不同 operation，或者不同 library，使用適合的儲存方式。
- 可調整矩陣乘法的大小和 blocking 的方式，使其適應 hardware、 memory allocation 的情況，以提高資料被 reuse 的機會，以及減少 cache miss。
- 編譯參數：[GCC编译器高效利用cache的原理和参数](https://zhuanlan.zhihu.com/p/496435946)

### 編譯優化

[編譯 HPL](https://www.mgaillard.fr/2022/08/27/benchmark-with-hpl.html)
- 設定 makefile 時可以加入不同的優化參數

## OS 設定

以下列舉可能影響效能的操作，仍待補充、研究及驗證

### 專屬的處理器：Thread Affinity

- 目標：讓特定 thread (Linux: task) 使用專屬的 CPU core，以減少 context switch 帶來的效能影響。此技術稱為 Thread Affinity，屬於 CPU Isolation。
註：清大團隊不建議改動 CPU affinity 或 GPU affinity 除非知道自己在做什麼。
- 方法：
- 使用 `lscpu` 確認系統 CPU 資訊，含：核心數、thread 數等
- 使用 `taskset` 將特定 thread 綁定至指定 CPU
- `taskset -c [CPU列表] [要執行的指令]`，如：`taskset -c 0,1 ./my_program`
- 或使用 cgroups 等較進階的工具
- 參考資料：
- [Thread Affinity](https://www.sciencedirect.com/topics/computer-science/thread-affinity)
- [3.13. Isolating CPUs Using tuned-profiles-realtime](https://access.redhat.com/documentation/zh-tw/red_hat_enterprise_linux_for_real_time/7/html/tuning_guide/isolating_cpus_using_tuned-profiles-realtime)
- [Linux -- 进程或线程独占CPU](https://www.cnblogs.com/tuowang/p/9398837.html)

### 節點間的通訊：TCP/IP 設定

- 目標：希望透過調整 TCP/IP 或 socket 等網路設定，以提升節點間的**通訊**效能
- 方法：
- 調整（提升） TCP/IP buffer size 或 socket buffer size

        # 查看當前 socket receive buffer size
        sysctl net.core.rmem_default
        sysctl net.core.rmem_max
        
        # 修改 socket receive buffer size
        sudo sysctl -w net.core.rmem_default=XXXXX
        sudo sysctl -w net.core.rmem_max=XXXXX
        
        # 查看當前 socket send buffer size
        sysctl net.core.wmem_default
        sysctl net.core.wmem_max
        
        # 修改 socket send buffer size
        sudo sysctl -w net.core.wmem_default=XXXXX
        sudo sysctl -w net.core.wmem_max=XXXXX

- reference:
- [Socket缓存究竟如何影响TCP的性能？](https://zorrozou.github.io/docs/Socket%E7%BC%93%E5%AD%98%E7%A9%B6%E7%AB%9F%E5%A6%82%E4%BD%95%E5%BD%B1%E5%93%8DTCP%E7%9A%84%E6%80%A7%E8%83%BD.html)
- [10.2. Changing Network Kernel Settings](https://access.redhat.com/documentation/zh-tw/red_hat_enterprise_linux/5/html/tuning_and_optimizing_red_hat_enterprise_linux_for_oracle_9i_and_10g_databases/sect-oracle_9i_and_10g_tuning_guide-adjusting_network_settings-changing_network_kernel_settings)
- [sysctl.conf的設定](https://asplord.com/index.php?sysctl.conf%E7%9A%84%E8%A8%AD%E5%AE%9A)
- 調整 TCP keepalive 設定，避免無效連線佔據資源

        # 查看當前 TCP Keepalive 設定
        sysctl net.ipv4.tcp_keepalive_time
        sysctl net.ipv4.tcp_keepalive_intvl
        sysctl net.ipv4.tcp_keepalive_probes
        
        # 修改 TCP Keepalive 設定
        sudo sysctl -w net.ipv4.tcp_keepalive_time=XXXXX
        sudo sysctl -w net.ipv4.tcp_keepalive_intvl=XXXXX
        sudo sysctl -w net.ipv4.tcp_keepalive_probes=XXXXX

### 記憶體管理效能：使用 Huge Page

- 目標：在作業系統記憶體管理方面，希望透過使用 Huge page 來達到
1. 減少 Kernel paging overhead
2. 減少 memory fragmentation
3. 減少 memory access time
- 方法
- 在 `/etc/sysctl.conf` 中，新增 `vm.nr_hugepages=[NUM]` ，`[NUM]` 為所需的 HugePage 數量
- 假設 HPL 需要 16 GB 的記憶體，且 HugePage size 為 2MB，則需要 16GB / 2MB = 8192 個 HugePage
- HPL 所需的記憶體，可透過 N, NB, P, Q 等參數來評估，並以執行來測試。
- `sysctl -p` 以開始使用該設定
- 參考資料
- Prerequisite knowledge: Operating System: paging, swapping
- [What are the huge pages in Linux?](https://kerneltalks.com/services/what-is-huge-pages-in-linux/)；[Linux 中的“大内存页”（hugepage）是个什么？](https://zhuanlan.zhihu.com/p/34659353)
- [为什么 HugePages 可以提升数据库性能](https://draveness.me/whys-the-design-linux-hugepages/)

## 參考資料

TOP 500 FAQ: https://www.top500.org/resources/frequently-asked-questions/

BLAS: https://www.netlib.org/blas/

## 需補充：GPU Tuning
## 作業
試著自己在工作站執行 HPL
事前作業：安裝 SLURM 及 MPI，或使用行事曆，並溝通須使用機器的時間。