科研動(dòng)態(tài)
用于低功耗設(shè)計(jì)驗(yàn)證的高效譜感知電源噪聲分析
中文題目：用于低功耗設(shè)計(jì)驗(yàn)證的高效譜感知電源噪聲分析
論文題目：Efficient Spectral-Aware Power Supply Noise Analysis for Low-Power Design Verification
錄用期刊/會(huì)議：2024 Design, Automation and Test in Europe Conference (DATE) (CCF-B類(lèi)會(huì)議)
原文鏈接：https://ieeexplore.ieee.org/document/10546831
原文doi：10.23919/DATE58400.2024.10546831
錄用/見(jiàn)刊時(shí)間：2024-10-27
作者列表：
1） 柏一諾 中國(guó)石油大學(xué)（北京） 人工智能學(xué)院 19本
2） 楊曉宇 中國(guó)石油大學(xué)（北京） 人工智能學(xué)院 24碩
3） 魯一澄 中國(guó)石油大學(xué)（北京） 人工智能學(xué)院
4） 牛 丹 東南大學(xué) 自動(dòng)化學(xué)院
5） 卓 成 浙江大學(xué) 信息科學(xué)與電子工程學(xué)院
6） 金 洲 中國(guó)石油大學(xué)（北京） 人工智能學(xué)院 計(jì)算機(jī)系教師
7） 劉偉峰 中國(guó)石油大學(xué)（北京） 人工智能學(xué)院 計(jì)算機(jī)系教師
背景與動(dòng)機(jī):
設(shè)計(jì)節(jié)能電子設(shè)備時(shí)，低功耗設(shè)計(jì)驗(yàn)證方法至關(guān)重要，尤其是對(duì)電源噪聲的控制。譜方法被證明有效用于電源噪聲分析，它通過(guò)生成譜相似的稀疏子矩陣作為預(yù)條件子，減少線(xiàn)性系統(tǒng)求解的迭代次數(shù)和時(shí)間。然而，現(xiàn)有的譜圖稀疏化方法計(jì)算復(fù)雜度高或依賴(lài)近似減少計(jì)算時(shí)間。為此，本文提出了一種兩階段譜感知算法來(lái)解決這些挑戰(zhàn)。通過(guò)引入譜感知權(quán)重，更好地評(píng)估圖中邊的優(yōu)先級(jí)，并以最小的相對(duì)條件數(shù)構(gòu)建高質(zhì)量的生成樹(shù)。其次，通過(guò)特征值變換策略，快速準(zhǔn)確地恢復(fù)具有譜關(guān)鍵性質(zhì)的樹(shù)外邊。最后，本文提出了一種快速計(jì)算方法，以降低有效電阻的計(jì)算復(fù)雜度。與兩種SOTA方法GRASS和feGRASS相比，我們的方法在預(yù)條件子生成方面分別平均加速37.3倍和2.13倍，并且在電源網(wǎng)絡(luò)分析的線(xiàn)性求解方面分別平均加速5.16倍和1.70倍。
設(shè)計(jì)與實(shí)現(xiàn):
（1）構(gòu)造譜感知權(quán)重生成樹(shù)
為了構(gòu)造高質(zhì)量的預(yù)條件子，需要考慮生成樹(shù)對(duì)于預(yù)條件子的影響，因此，我們提出了一種構(gòu)建更精確生成樹(shù)的方法。對(duì)于原圖G對(duì)應(yīng)的拉普拉斯矩陣LG和原圖G的生成樹(shù)T對(duì)應(yīng)的拉普拉斯矩陣LT之間的廣義特征值：
我們將特征向量u的轉(zhuǎn)置uT分別與
和
相乘，并進(jìn)一步推導(dǎo)，得到廣義特征值
的一種表示形式：
結(jié)合上述推導(dǎo)并引入節(jié)點(diǎn)體積（與節(jié)點(diǎn)相連邊的權(quán)重之和），推導(dǎo)出如下公式：
其中gi表示單位矩陣的第i列，
和
分別表示了節(jié)點(diǎn)i在原圖G和子圖T中的體積。由于LG和LT間相對(duì)條件數(shù)的大小更多取決于兩者間的最大廣義特征值，通過(guò)上述推導(dǎo)，我們找到了LG和LT間最大廣義特征值的一個(gè)下界為原圖和子圖間最大不匹配的節(jié)點(diǎn)體積比例。我們可以通過(guò)約束該下界從而降低原圖與子圖間的最大廣義特征值，對(duì)LG和LT間相對(duì)條件數(shù)進(jìn)行約束。因此，最小化最大不匹配的體積比例是減少相對(duì)條件數(shù)的有效方法。此外根節(jié)點(diǎn)通常指定為體積最大的節(jié)點(diǎn)，更接近根節(jié)點(diǎn)的節(jié)點(diǎn)有利于減少其在原圖和子圖間最大不匹配的體積。
由此我們推出了更有效的生成樹(shù)權(quán)重定義：
其中deg表示節(jié)點(diǎn)體積，dist表示節(jié)點(diǎn)到根節(jié)點(diǎn)r的未加權(quán)距離。該權(quán)重被稱(chēng)為譜感知權(quán)重，其確保連接更靠近根節(jié)點(diǎn)的邊具有更高的權(quán)重，因此更有可能保留在生成樹(shù)中。
（2）基于特征值變換準(zhǔn)確恢復(fù)樹(shù)外邊
當(dāng)我們構(gòu)造生成樹(shù)后，準(zhǔn)確的恢復(fù)少量樹(shù)外邊并最大的減小相對(duì)條件數(shù)是關(guān)鍵問(wèn)題。對(duì)于原圖G與其任一子圖P，考慮它們之間的廣義特征值
和相對(duì)條件數(shù)
，我們可以得到如下公式：
其中LP是子圖P對(duì)應(yīng)的拉普拉斯矩陣。我們通過(guò)特征值變換，將原圖G與其任一子圖P的相對(duì)條件數(shù)的上界轉(zhuǎn)換為了
，因此我們可以通過(guò)增大
來(lái)減小相對(duì)條件數(shù)的上界。為了使恢復(fù)的樹(shù)外邊最大化的增大
，我們進(jìn)一步推導(dǎo)得到如下公式：
其中gi,j表示了單位矩陣的第i列減去第j列，P’表示子圖P恢復(fù)一條邊后新的子圖。我們通過(guò)
的上界
，并考慮恢復(fù)邊e=(i,j)后的上界
的前后變化，推出了每條樹(shù)外邊對(duì)于上界的增加值為
，因此我們每次恢復(fù)樹(shù)外邊時(shí)可以選擇最優(yōu)的樹(shù)外邊，使得恢復(fù)有限樹(shù)外邊的同時(shí)最大化的降低相對(duì)條件數(shù)。我們的方法可以在不損失任何精度的情況下為樹(shù)外邊排序。
（3）進(jìn)一步降低有效電阻計(jì)算復(fù)雜度
上述過(guò)程中還有一個(gè)計(jì)算挑戰(zhàn)在于快速的計(jì)算LG+，即計(jì)算拉普拉斯矩陣LG的偽逆。為了快速的進(jìn)行計(jì)算，我們基于矩陣的二次型進(jìn)行推導(dǎo)，將單條樹(shù)外邊的
降到O(1)的時(shí)間復(fù)雜度。我們的推導(dǎo)如下：
通過(guò)上述推導(dǎo)和拉普拉斯矩陣的性質(zhì)，我們得到如下公式：
通過(guò)以上推導(dǎo)，我們可以在線(xiàn)性的時(shí)間內(nèi)快速計(jì)算出所有樹(shù)外邊的有效電阻，大大降低了有效電阻計(jì)算的時(shí)間復(fù)雜度，使得譜圖稀疏化算法可以快速準(zhǔn)確的恢復(fù)樹(shù)外邊到生成樹(shù)，更高效的構(gòu)建高質(zhì)量超稀疏預(yù)條件子。
實(shí)驗(yàn)結(jié)果及分析:
（1）加速效率與預(yù)條件子質(zhì)量對(duì)比
表1：我們的方法與兩種SOTA方法在稀疏化時(shí)間和迭代求解時(shí)間的對(duì)比
我們統(tǒng)計(jì)了三種譜圖稀疏化算法的時(shí)間開(kāi)銷(xiāo)、迭代求解、以及生成的預(yù)條件子與原始矩陣的相對(duì)條件數(shù)等結(jié)果。我們使用三種譜圖稀疏化算法生成的預(yù)條件子與預(yù)條件共軛梯度法進(jìn)行結(jié)合，對(duì)矩陣進(jìn)行迭代求解。
實(shí)驗(yàn)結(jié)果表明與兩種SOTA方法產(chǎn)生的預(yù)條件子相比，我們所提方法產(chǎn)生的預(yù)條件子在迭代次數(shù)和迭代法求解時(shí)間上表現(xiàn)出更優(yōu)的性能。GRASS的預(yù)條件子質(zhì)量較高（相對(duì)條件數(shù)小），但是預(yù)條件子的生成非常慢，feGRASS的預(yù)條件子生成速度快，但是損失了一定的精度。從表中可以看到，我們所提的方法，在保證精度的同時(shí)大幅提高了效率。在迭代法求解時(shí)間上，所提方法的平均加速比為5.16x和1.70x，迭代次數(shù)也優(yōu)于GRASS和feGRASS。在譜圖稀疏化時(shí)間開(kāi)銷(xiāo)上，所提方法的時(shí)間開(kāi)銷(xiāo)相比GRASS和feGRASS的平均加速比分別為37.30x和2.13x。
（2）預(yù)條件子質(zhì)量與稀疏度分析
圖1：我們的方法與SOTA方法生成預(yù)條件子的相對(duì)條件數(shù)對(duì)比
我們進(jìn)一步展示了在不同稀疏度，即恢復(fù)不同比例樹(shù)外邊到生成樹(shù)時(shí)相對(duì)條件數(shù)的變化。我們統(tǒng)計(jì)了我們的方法、兩種譜圖稀疏化的SOTA方法GRASS、feGRASS在這些條件下的數(shù)據(jù)并進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明我們提出的方法在相對(duì)條件數(shù)上始終優(yōu)于其他算法，且能更快的達(dá)到相對(duì)條件數(shù)的降低，即在更低的稀疏度時(shí)達(dá)到較好的相對(duì)條件數(shù)。
結(jié)論:
本文介紹了一種新的譜圖稀疏化方法，旨在為電源噪聲分析中的迭代求解器生成高質(zhì)量的預(yù)條件子。我們的方法側(cè)重于譜感知權(quán)重、特征值變換和有效電阻的快速計(jì)算方法來(lái)降低時(shí)間復(fù)雜度并提高預(yù)條件子的有效性。實(shí)驗(yàn)結(jié)果證明了我們的方法的優(yōu)越性能，在計(jì)算時(shí)間和相對(duì)條件數(shù)方面都有顯著改善，與兩種SOTA方法GRASS和feGRASS相比，我們的方法在預(yù)條件子生成方面具有更高的精度和效率（分別平均加速37.3x倍和2.13x倍），并且在加速電源網(wǎng)絡(luò)仿真和其他拉普拉斯矩陣的線(xiàn)性求解方面也有顯著改進(jìn)（分別平均加速5.16x倍和1.70x倍）。
通訊作者簡(jiǎn)介:
金洲，中國(guó)石油大學(xué)（北京）計(jì)算機(jī)系副教授，入選北京市科協(xié)青年人才托舉工程、中國(guó)石油大學(xué)（北京）青年拔尖人才。主要從事集成電路設(shè)計(jì)自動(dòng)化（EDA）、面向科學(xué)計(jì)算的DSA軟硬件協(xié)同設(shè)計(jì)等方面的研究工作。主持并參與國(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è)橫向課題等二十余項(xiàng)。在DAC、TCAD、TODAES、SC、PPoPP、IPDPS、TCAS-II、ASP-DAC等重要國(guó)際會(huì)議和期刊上發(fā)表60余篇高水平學(xué)術(shù)論文。是DAC、SC、TCAD、TPDS等頂會(huì)頂刊的程序委員會(huì)委員和審稿人。獲SC23最佳論文獎(jiǎng)、SC24最佳論文獎(jiǎng)提名、EDA2青年科技獎(jiǎng)、ISEDA23榮譽(yù)論文獎(jiǎng)、IEEJ九州支部長(zhǎng)獎(jiǎng)等。
聯(lián)系方式：[email protected]