MASC: 一種通過新穎的時空預測實現壓縮的內存高效伴隨靈敏度分析
中文題目：MASC: 一種通過新穎的時空預測實現壓縮的內存高效伴隨靈敏度分析
論文題目：MASC: A Memory-Efficient Adjoint Sensitivity Analysis through Compression Using Novel Spatiotemporal Prediction
錄用會議：61st ACM/IEEE Design Automation Conference (DAC '24)（CCF A）
錄用時間：2024-2-27
原文DOI：https://doi.org/10.1145/3649329.3657393
作者列表：
1） 李晨曦 中國石油大學（北京）人工智能學院 碩 22
2） 張博源 美國印第安納大學
3） 段永強 中國石油大學（北京）人工智能學院 碩 23
4） 李 陽 中國石油大學（北京）人工智能學院 碩 23
5） 葉佐昌 清華大學
6） 劉偉峰 中國石油大學（北京）人工智能學院 計算機系教師
7） 陶鼎文 美國印第安納大學
8） 金 洲 中國石油大學（北京）人工智能學院 計算機系教師
背景與動機:
在現代集成電路設計和驗證中，伴隨靈敏度分析至關重要，但隨著電路規模、目標函數數量以及時間點的增加，其計算開銷會顯著增長，這會妨礙其更廣泛的應用。由于瞬態分析的前向積分過程和伴隨靈敏度分析的反向積分過程具有密切的聯系，所以我們可以保存瞬態分析中的雅可比矩陣，用于加速伴隨靈敏度分析。然而，跨多個時間步長的雅可比矩陣組成的稀疏張量通常非常龐大，無法在正向積分過程存儲在內存中，假如把這些數據存儲在磁盤中又會帶來顯著的磁盤讀寫開銷。為了解決這個問題，我們設計了一種內存開銷極低的靈敏度分析方法，利用數據壓縮來最小化仿真過程中的內存開銷，并提高伴隨靈敏度分析的效率。我們的壓縮算法可以充分利用數據的電路特性和時空特性，可以高效壓縮由雅可比矩陣組成的稀疏張量，還引入了共享索引技術、先進的時空預測模型和健壯的殘差編碼方案。最后我們在來自真實世界的7個數據集上評估了我們的壓縮算法。與通用壓縮算法相比，所提壓縮算法的壓縮率大約是GZIP的4倍，同時壓縮時間是其25%；與浮點數壓縮算法相比，所提算法壓縮率大約是FPZIP的2.24倍、NDZIP的15.69倍以及SpiceMate的4.95倍，同時壓縮時間大約是NDZIP的50%和SpiceMate的45%，稍慢于FPZIP。
設計與實現:
（1） 高效的稀疏張量壓縮算法
l共享索引以及時空預測技術
圖 1 MASC壓縮算法工作流程
上圖描述了所提壓縮算法中的原理和工作流程。為了有效的壓縮雅可比矩陣構成的稀疏張量，我們首先以CSR等格式來存儲稀疏矩陣，分別討論對矩陣索引和非零元數組的壓縮。
由于在同一次瞬態分析中雅可比矩陣的索引數組都是相同的，所以我們可以將索引數組僅僅保留一份，即在堆中保存一份共享索引，這些索引數組可以用整數壓縮算法進一步的壓縮。
由于非零元數組通常由IEEE 754浮點數組成，所以我們采用浮點數壓縮算法進行高效的壓縮。同時我們利用了時間上相鄰雅可比矩陣之間的時間相關，以及由于器件Matrix Stamping過程所導致的數據空間相關性，構建了時空預測模型，高效的去除數據之間的冗余。
通過對整數索引的壓縮以及浮點數非零元的壓縮，我們有效的降低了仿真過程中的內存開銷。
l預測模型選擇
圖 2 預測模型選擇
為了減少選擇最佳預測模型所帶來的時間開銷以及記錄模型選擇的空間開銷，我們創新性地采用了馬爾可夫模型。首先我們在壓縮任務的開始階段，對每種預測模型的精度進行判斷，并選擇精度最高的作為最終的預測模型，同時對預測模型的選擇頻率進行記錄。在之后的壓縮任務中，我們以頻率估計概率，直接對預測模型進行選擇，從而減少了開銷。
l高效的殘差編碼方案
圖 3 殘差編碼算法
壓縮器從壓縮隊列的前端讀取實際值，從混合預測器讀取預測值，在它們之間執行異或操作以生成殘差，之后編碼器對這些殘差進行編碼。由于實際值和預測值通常非常接近，所以殘差通常包含許多前導零和尾隨零。因此，有效地編碼這些零比特可以對浮點數進行有效的壓縮。如上圖所示，我們根據殘差的數據特征采用了一套高效的殘差編碼方案，由于接近60%的殘差的所有位為‘0’，所以我們采用1bit去編碼這種情況，同時還采用了共享編碼的方法去進一步提高壓縮率。
lMASC工作流程
圖 4 MASC仿真工作流程
完整的仿真工作流程如上圖所示。在瞬態分析中，進行數據的壓縮和存儲。首先我們在計算電路的直流工作點時獲得共享索引。在瞬態仿真中，MASC將tn時間點的雅可比矩陣存儲到tn+1時間點，利用tn+1時間點獲得的雅可比矩陣完成對tn時間點雅可比矩陣的壓縮。同理，在靈敏度仿真過程中，整個過程逆向進行，完成對雅可比矩陣的解壓與內存釋放。
實驗結果及分析:
表 1 壓縮算法性能對比
如上圖所示，我們在多個電路上將所提時空壓縮算法和浮點數壓縮算法FPZIP，NDZIP，和 SpiceMate進行了性能比較，這些壓縮算法分別來自高性能計算和電路仿真等多個領域。實驗結果表明，時空壓縮算法在壓縮率、壓縮時間和解壓時間上都有著很好的表現。它的平均壓縮率大約是FPZIP的2.24倍、NDZIP的15.69倍以及SpiceMate的4.95倍；其壓縮時間大約是NDZIP的50%和SpiceMate的45%，稍慢于FPZIP。 最后，我們將壓縮算法集成至電路仿真器xyce，與原本的xyce靈敏度仿真相比，時間開銷減少了50%左右，這證明了我們所提仿真性能的優越性。
結論:
在本文中，我們將數據壓縮算法集成到仿真過程中，利用前向積分過程中存儲的雅可比矩陣來加速反向伴隨靈敏度求解過程。同時，我們開發了一種新穎的無損壓縮算法，可以大幅度的減少仿真過程中的內存開銷。與通用壓縮算法GZIP和最先進的浮點壓縮算法FPZIP、NDZIP以及SpiceMate相比，所提壓縮算法表現出顯著的優勢，有效地減少了伴隨靈敏度仿真過程中的內存開銷。
通訊作者簡介:
金洲，副教授。中國石油大學（北京）計算機系副教授，入選北京市科協青年人才托舉工程、校青年拔尖人才。主要從事集成電路設計自動化（EDA）領域工作的研究龍其是AI和 GPU加速的電路仿真等方向。主持并參與國家自然科學基金青年項目、重點項目，科技部重點研發微納電子專項、高性能計算專項青年科學家項目，國家重點實驗室開放課題，企業橫向課題等。在DAC、TCAD、SC、PPoPP、ICCAD、DATE、IPDPS、TODAES 、TCAS-II等重要國際會議和期刊上發表60余篇高水平學術論文。獲SC23最佳論文獎、EDA2青年科技獎、ISEDA23榮譽論文獎、IEEJ九州支部長獎等。
聯系方式：jinzhou@cup.edu.cn