中文題目：用于低功耗設計驗證的高效譜感知電源噪聲分析

論文題目：Efficient Spectral-Aware Power Supply Noise Analysis for Low-Power Design Verification

錄用期刊/會議：2024 Design, Automation and Test in Europe Conference (DATE) (CCF-B類會議)

原文鏈接：https://ieeexplore.ieee.org/document/10546831

原文doi：10.23919/DATE58400.2024.10546831

錄用/見刊時間：2024-10-27

作者列表：

1） 柏一諾 中國石油大學（北京） 人工智能學院 19本

2） 楊曉宇 中國石油大學（北京） 人工智能學院 24碩

3） 魯一澄 中國石油大學（北京） 人工智能學院 

4） 牛   丹 東南大學 自動化學院

5） 卓   成 浙江大學 信息科學與電子工程學院

6） 金   洲 中國石油大學（北京） 人工智能學院 計算機系教師

7） 劉偉峰 中國石油大學（北京） 人工智能學院 計算機系教師

背景與動機:

設計節能電子設備時，低功耗設計驗證方法至關重要，尤其是對電源噪聲的控制。譜方法被證明有效用于電源噪聲分析，它通過生成譜相似的稀疏子矩陣作為預條件子，減少線性系統求解的迭代次數和時間。然而，現有的譜圖稀疏化方法計算復雜度高或依賴近似減少計算時間。為此，本文提出了一種兩階段譜感知算法來解決這些挑戰。通過引入譜感知權重，更好地評估圖中邊的優先級，并以最小的相對條件數構建高質量的生成樹。其次，通過特征值變換策略，快速準確地恢復具有譜關鍵性質的樹外邊。最后，本文提出了一種快速計算方法，以降低有效電阻的計算復雜度。與兩種SOTA方法GRASS和feGRASS相比，我們的方法在預條件子生成方面分別平均加速37.3倍和2.13倍，并且在電源網絡分析的線性求解方面分別平均加速5.16倍和1.70倍。

設計與實現:

（1）構造譜感知權重生成樹

為了構造高質量的預條件子，需要考慮生成樹對于預條件子的影響，因此，我們提出了一種構建更精確生成樹的方法。對于原圖G對應的拉普拉斯矩陣LG和原圖G的生成樹T對應的拉普拉斯矩陣LT之間的廣義特征值：

我們將特征向量u的轉置uT分別與和相乘，并進一步推導，得到廣義特征值的一種表示形式：

 

結合上述推導并引入節點體積（與節點相連邊的權重之和），推導出如下公式：

其中g_i表示單位矩陣的第i列，和分別表示了節點i在原圖G和子圖T中的體積。由于L_G和L_T間相對條件數的大小更多取決于兩者間的最大廣義特征值，通過上述推導，我們找到了L_G和L_T間最大廣義特征值的一個下界為原圖和子圖間最大不匹配的節點體積比例。我們可以通過約束該下界從而降低原圖與子圖間的最大廣義特征值，對L_G和L_T間相對條件數進行約束。因此，最小化最大不匹配的體積比例是減少相對條件數的有效方法。此外根節點通常指定為體積最大的節點，更接近根節點的節點有利于減少其在原圖和子圖間最大不匹配的體積。

由此我們推出了更有效的生成樹權重定義：

其中deg表示節點體積，dist表示節點到根節點r的未加權距離。該權重被稱為譜感知權重，其確保連接更靠近根節點的邊具有更高的權重，因此更有可能保留在生成樹中。

（2）基于特征值變換準確恢復樹外邊

當我們構造生成樹后，準確的恢復少量樹外邊并最大的減小相對條件數是關鍵問題。對于原圖G與其任一子圖P，考慮它們之間的廣義特征值和相對條件數，我們可以得到如下公式：

其中L_P是子圖P對應的拉普拉斯矩陣。我們通過特征值變換，將原圖G與其任一子圖P的相對條件數的上界轉換為了，因此我們可以通過增大來減小相對條件數的上界。為了使恢復的樹外邊最大化的增大，我們進一步推導得到如下公式：

其中g_i,j表示了單位矩陣的第i列減去第j列，P’表示子圖P恢復一條邊后新的子圖。我們通過的上界，并考慮恢復邊e=(i,j)后的上界的前后變化，推出了每條樹外邊對于上界的增加值為，因此我們每次恢復樹外邊時可以選擇最優的樹外邊，使得恢復有限樹外邊的同時最大化的降低相對條件數。我們的方法可以在不損失任何精度的情況下為樹外邊排序。

（3）進一步降低有效電阻計算復雜度

上述過程中還有一個計算挑戰在于快速的計算L_G⁺，即計算拉普拉斯矩陣L_G的偽逆。為了快速的進行計算，我們基于矩陣的二次型進行推導，將單條樹外邊的降到O(1)的時間復雜度。我們的推導如下：

通過上述推導和拉普拉斯矩陣的性質，我們得到如下公式：

通過以上推導，我們可以在線性的時間內快速計算出所有樹外邊的有效電阻，大大降低了有效電阻計算的時間復雜度，使得譜圖稀疏化算法可以快速準確的恢復樹外邊到生成樹，更高效的構建高質量超稀疏預條件子。

實驗結果及分析:

（1）加速效率與預條件子質量對比

表1：我們的方法與兩種SOTA方法在稀疏化時間和迭代求解時間的對比

我們統計了三種譜圖稀疏化算法的時間開銷、迭代求解、以及生成的預條件子與原始矩陣的相對條件數等結果。我們使用三種譜圖稀疏化算法生成的預條件子與預條件共軛梯度法進行結合，對矩陣進行迭代求解。

實驗結果表明與兩種SOTA方法產生的預條件子相比，我們所提方法產生的預條件子在迭代次數和迭代法求解時間上表現出更優的性能。GRASS的預條件子質量較高（相對條件數?。?，但是預條件子的生成非常慢，feGRASS的預條件子生成速度快，但是損失了一定的精度。從表中可以看到，我們所提的方法，在保證精度的同時大幅提高了效率。在迭代法求解時間上，所提方法的平均加速比為5.16x和1.70x，迭代次數也優于GRASS和feGRASS。在譜圖稀疏化時間開銷上，所提方法的時間開銷相比GRASS和feGRASS的平均加速比分別為37.30x和2.13x。

（2）預條件子質量與稀疏度分析

圖1：我們的方法與SOTA方法生成預條件子的相對條件數對比

我們進一步展示了在不同稀疏度，即恢復不同比例樹外邊到生成樹時相對條件數的變化。我們統計了我們的方法、兩種譜圖稀疏化的SOTA方法GRASS、feGRASS在這些條件下的數據并進行對比，實驗結果表明我們提出的方法在相對條件數上始終優于其他算法，且能更快的達到相對條件數的降低，即在更低的稀疏度時達到較好的相對條件數。

結論:

本文介紹了一種新的譜圖稀疏化方法，旨在為電源噪聲分析中的迭代求解器生成高質量的預條件子。我們的方法側重于譜感知權重、特征值變換和有效電阻的快速計算方法來降低時間復雜度并提高預條件子的有效性。實驗結果證明了我們的方法的優越性能，在計算時間和相對條件數方面都有顯著改善，與兩種SOTA方法GRASS和feGRASS相比，我們的方法在預條件子生成方面具有更高的精度和效率（分別平均加速37.3x倍和2.13x倍），并且在加速電源網絡仿真和其他拉普拉斯矩陣的線性求解方面也有顯著改進（分別平均加速5.16x倍和1.70x倍）。

通訊作者簡介:

金洲，中國石油大學（北京）計算機系副教授，入選北京市科協青年人才托舉工程、中國石油大學（北京）青年拔尖人才。主要從事集成電路設計自動化（EDA）、面向科學計算的DSA軟硬件協同設計等方面的研究工作。主持并參與國家自然科學基金青年項目、重點項目，科技部重點研發微納電子專項、高性能計算專項青年科學家項目，國家重點實驗室開放課題、企業橫向課題等二十余項。在DAC、TCAD、TODAES、SC、PPoPP、IPDPS、TCAS-II、ASP-DAC等重要國際會議和期刊上發表60余篇高水平學術論文。是DAC、SC、TCAD、TPDS等頂會頂刊的程序委員會委員和審稿人。獲SC23最佳論文獎、SC24最佳論文獎提名、EDA2青年科技獎、ISEDA23榮譽論文獎、IEEJ九州支部長獎等。

聯系方式：jinzhou@cup.edu.cn