# SpArch: Efficient Architecture for Sparse Matrix Multiplication <body> <div style="text-align: right;"> <p>2024.06.27</p> <a href="https://arxiv.org/pdf/2002.08947">Paper link</a> </div> --- [TOC] --- ## Background [Huffman Tree](https://xken831.pixnet.net/blog/post/459581308-%E3%80%90%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E3%80%91%E9%9C%8D%E5%A4%AB%E6%9B%BC%28huffman%29%E6%A8%B9%E6%95%99) 有一串數字，由小到大排列，最小值的節點開始合併 ## Overview ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e85.png) ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e86.png) - Inner product with **poor input reuse** - Outer product with **poor output reuse** - 本篇基於outer product去修改，試圖解決其缺點 - 使用streaming merger去做psum的累加，且其可切pipeline - 使用Matrix Condensing去減少運算，也可以減少psum矩陣 - 使用Huffman Tree Scheduler去最佳化psum矩陣合併的順序，以減少memory access次數 - 使用Row Prefetcher以減少右矩陣的memory access次數 ## Method ### A. Comparator Array based Merger #### (a) Parallel Merge Unit ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e87.png) - 有一矩陣A & B，和一個4 * 4的比較器分別比較矩陣A, B的4個元素 - A在比較器左側，B放在比較器上方 - 如果A≥B，'≥'，否則'<' - 比較器右方padding一列'<'，下方padding一行'≥' - Boundary Definition - (0, 0)一定是，row0如果是'≥' - 一個點是1，上方點是'<' - 一個點是0，左方點是'≥' - 利用斜對角將這個比較器分成8組，同一組有相同的group index標記在每個點的左上角 - 輸出規則 - 沿著邊界的輸出小的值 #### (b) Hierarchical Parallel Merge Unit ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e88.png) - 假設現在要比12 * 12，用Fig.3的方法就會很浪費 - 直覺是，如果Block A 的最大元素仍然小於BlockB的最小元素，則我們可以跳過兩個Block的比較。 - 所以先Block之間比較，利用左側的3 * 3比較器，接著只需要做這個3 * 3裡面的5個邊界 - 這樣就可以以加一個3 * 3的比較器，省下其他的4個4 * 4的比較器 - `註：原本要有9個4 * 4，或1個12 * 12，現在變成1個3 * 3 + 5個4 * 4` #### (c ) Merge Tree ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e89.png) - 這邊是堆疊多個Fig.4的Binary Streaming合併器，形成一個Merge Tree - Merge Tree的每一個節點都是一個FIFO，每兩個一組都是1 * 1的比較器，一路往上傳遞，就能將多個array進行合併 #### (d) Adders and Zero Eliminator ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e8a.png) - Fig.5是index的結果，但相同index的要做加法，所以Merge Tree後面要接加法器 - 舉例來說，相同index的4個值要相加，但這4個值原本是存在4個位置(具有相同的index)，所以將這4個值相加存到第1個位置，剩下的3個位置改成0 - 接著就需要將這些改成0的位置填滿，所以需要shift，並且紀錄究竟有多少個0，Fig.6就是在講這部分 - 首先需要zero_count去計算一個元素前面有多少0，接著以1, 2, 4...，2的冪次去做shift - `註：以需要shift 7為例，就需要做1 + 2 + 4，共3次shift，因為Mux是吃zero_count的bit` ### B. Matrix Condensing ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e8b..png) - 資料以csr形式儲存在DRAM - load的時候，以4個緊密的col唯一組，由右向左由上到下load矩陣 - `註：推測是要一個Round做完可以先進行compute` - 透過減少col數量，便可以減少psum matrix數，也就是減少外積運算數量 ### C. Huffman Tree Scheduler ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e8c.png) - Merge最多可以合併64個矩陣(或矩陣片段，根據比較器大小決定)，但總數有可能超過，那該是誰要先被合併就是一個值得探討的問題 - 理論上來說，越早被合併的矩陣，就需要越多的DRAM讀寫，所以直觀來說，越稀疏的矩陣越應該早點被合併，因為load起來比較快，因此使用Huffman Tree Scheduler來最小化memory access，也就是最小化Fig.8的節點數 - weight代表每一個col有幾個row有值，這樣合併之後就可以大略估算大小 - 一個col一個節點，合併後也會產生節點 - 一個col代表一個condensed col，也就是一個矩陣的資料，因此合併後的節點也就是一個合併後的矩陣意思 ### D. Row Prefetcher ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e8d.png) - 雖然矩陣A確實需要算的列數減少了，但變成是每一個element要對應到不同的矩陣B的行數 - 所以使用Row Prefetcher來處理 - 使用col index，也就是condense之前所在的col index，就可以知道要乘上的對應的矩陣B的row(因為採用csr格式) - Row Prefetcher有兩個功能 - 提前獲取乘法器使用的數據，以隱藏 DRAM 的延遲(多個prefetcher，多個DRAM Bank) - 將獲取的數據緩存在buffer中，以供reuse，減少 DRAM 讀取的數量，buffer就是最久之後才要用到的會被蓋掉 - 以Fig.9來看，step2時要選哪些要蓋掉，先load R2-0之後，由於R0的distance比R1遠，所以先蓋R1，但還是不夠用，所以再蓋R1-0和R1-1。像step8時，因為R3-1和R3-2已經在buffer裡面了，所以只需要load R3-0 ### E. System Architecture ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e8e.png) - SpArch 的系統架構如Fig.10 所示。 - 矩陣 A 以 CSR 格式存儲並通過condensed col提取，矩陣 B 以 CSR 格式存儲於 HBM 中。 - 矩陣 A Col Fetcher接收來自software scheduler的控制指令，計算選定col中數據的地址，並從矩陣A中提取元素。然後，提取的元素將被發送到一個look-ahead FIFO。Distance List Builder將處理look-ahead FIFO 並計算每個row的下一次使用時間。row index和下次使用時間被提供給 矩陣B Row Prefetcher，以prefetch row並決定哪個row buffer要清空 - 為了尋找所需的row是否在buffer中，使用Hash Table將row index映射到buffer中的位置，以便宜且快速的做搜尋 - 並使用下次使用的時間來決定清空哪個row。由於Hash Table的寬度遠低於buffer本身，且下次使用時間變化很少（每個周期最多一條線），所以很便宜。 - 在prefetch row之後，乘法器陣列將進行外積並以 COO 格式生成psum矩陣，然後將它們發送到Merge tree。Merge tree的每個最低級 FIFO 前都有一個MUX，可配置為接受來自乘法器陣列或部分矩陣fetcher的數據。如果每個最低級 FIFO 前的 MUX 被配置為psum矩陣fetcher，scheduler將發送相應部分合併結果的地址。一旦 FIFO 接近空，它將fetch所請求的矩陣。Merge tree的輸出將連接到Psum Mat Writer。它在將psum矩陣寫入 DRAM 之前buffer住，並且如果是最終結果，還會將內部的 COO 格式轉換為 CSR 格式。 ## Evaluation ### A. Methodology ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e8f.png) - 以c++寫cycle accurate的simulator，系統相關參數如上 - array mergers, arithmetic units, FIFOs, row prefetcher, and DRAM 有被寫成verilog，來測量area和power，使用TSMC 40nm - 使用xsim RTL 模擬器，模擬annotated toggle rate，並轉儲到 Switching Activity Interchange Format（SAIF），用 Design Compiler 估算功耗 - 根據reference[30]的area和power資料，和模擬器中的MACs數量(Floating Mul & Add)去估算area和power。 - 從模擬器中轉儲了每個 SRAM/FIFO 的大小、寬度和r/w量，並使用 CACTI 來估算電路中 FIFOs 和Prefetch Buffer的power和area。從模擬器中，還獲得了 DRAM rw的確切量。使用這些數據根據reference[31]、[32]估算 DRAM 功耗。 - 使用多個平台作為baseline，包括desktop CPU、GPU、mobile CPU，以及最先進的 ASIC 加速器 OuterSPACE，僅測量 SpGEMM 函數的核心執行時間，對於所有功耗測量，首先測量系統的空閒功耗，然後重複運行工作負載並測量總功耗。然後dynamic power = total power - idle power。 ### B. Experimental Results ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e90.png) ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e91.png) - 使用與 OuterSPACE 相同的 DRAM BW估算power，即 42.6 GB/s/W ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e92.png) - Merge Tree佔了大部分的power和area消耗，這是 SpArch 的核心部分。在 SuiteSparse 數據集 [27] 和 SNAP 數據集 [28] 上評估了 SpArch 的性能，這些數據集與 [1] 相同。 ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e98.png) ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e99.png) - SpArch 比 OuterSPACE、MKL、cuSPARSE、CUSP 和 ARM Armadillo 快 4倍、19倍、18倍、17倍 和 1285倍。 - 主要是由於減少了psum matrix 過多的memory access - 與 OuterSPACE 相比，DRAM access減少了 2.8 倍。 - 通過row prefetching和streaming merge tree的規則write pattern，所以有比 OuterSPACE 更高的memory bandwidth reuse rate。 - Fig. 12 power表現。 - SpArch 與 OuterSPACE、MKL、cuSPARSE、CUSP 和 ARM Armadillo 相比，有 6倍、164倍、435倍、307倍 和 62倍的power reduction，主要是省在不需要cache, instruction decoder。 ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e9a.png) Fig.14表示不同sparsity 從6×10^−3 到 5×10^−5在合成的 rMAT [29] 數據上與 Intel MKL 的性能比較，SpArch 實現了超過 10 倍的加速。 - 當矩陣變得更稀疏時，性能僅下降了 2.7 倍，而 MKL 則遭受了更大的性能下降。 - 對sparsity的影響較低部分來自於使用outer product。架構設計使用一個大的合併樹而不是許多小的procsee unit。後者更可能遭遇負載平衡問題，特別是當矩陣變得更稀疏時。 ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e9b.png) - Fig.15展示roofline model，因為spGEMM一定是在memory，這張圖展示了相比OuterSPACE更加接近屋頂 ### C. Interpreting the Performance Gain ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e9c.png) - Fig.16主要是想分析各個操作的效能 ### D. Design Space Exploration - SpArch主要有2大優點 - high memory bandwidth reuse rate - low memory access - 要最佳化這2個優勢，就需要搭配好各個module的配置 ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e9d.png) - Fig.17 (a )和(b )分析performance和buffer size，(a )先決定開的大小，決定總size之後，再決定究竟是要切多段，每段較短，還是少段較長 - Fig.17 (c )分析performance和merge tree中的比較陣列size，8 * 8卡在compute bound，16 * 16在memory bound - Fig.17 (d )分析look-ahead FIFO size，size越大，就可以看越遠，prefetcher預測越準 ![](https://casmd.ee.ncku.edu.tw/uploads/16eca2831f15aac8ee1673e9e.png) - Fig.18 分析merge tree size，越長越貴，但可以看的越遠，所以prefetch越準 ## Conclusion 推測乘法器是2組8*8的compute unit，因此一個cycle最多會產生8組需要合併的array。也因為統計過通常64不夠一次合併完成，所以如果算完的，但還來不及被合併的就會先被存到DRAM，之後再根據huffman tree去讀取回來合併。 總而言之，本文主要幾項貢獻 - merge tree去做psum累加 - condensed matrix去減少需要累加的矩陣數 - 使用prefetcher去抓取與buffer所需要運算的row - 透過huffman tree去決定哪些矩陣應該要先被合併