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