本論文作者王治海是中國科學(xué)技術(shù)大學(xué) 2020 級(jí)碩博連讀生，師從王杰教授，主要研究方向?yàn)閺?qiáng)化學(xué)習(xí)與學(xué)習(xí)優(yōu)化理論及方法、人工智能驅(qū)動(dòng)的芯片設(shè)計(jì)等。他曾以第一作者在 TPAMI、ICML、NeurIPS、ICLR、AAAI 等頂級(jí)期刊與會(huì)議上發(fā)表論文七篇，一篇入選 ICML 亮點(diǎn)論文（前3.5%），曾獲華為優(yōu)秀實(shí)習(xí)生（5/400+）、兩次國家獎(jiǎng)學(xué)金（2017和2024）等榮譽(yù)。

近日，中科大王杰教授團(tuán)隊(duì)（MIRA Lab）和華為諾亞方舟實(shí)驗(yàn)室（Huawei Noah's Ark Lab）聯(lián)合提出了可生成具有成千上萬節(jié)點(diǎn)規(guī)模的神經(jīng)電路生成與優(yōu)化框架，具備高擴(kuò)展性和高可解釋性，這為新一代芯片電路邏輯綜合工具奠定了重要基礎(chǔ)。論文發(fā)表在 CCF-A 類人工智能頂級(jí)會(huì)議 Neural Information Processing Systems（NeurIPS 2024）。

• 論文標(biāo)題：Towards Next-Generation Logic Synthesis: A Scalable Neural Circuit Generation Framework
• 論文地址：https://neurips.cc/virtual/2024/poster/94631

論文概覽

邏輯綜合（Logic Synthesis, LS）是芯片設(shè)計(jì)流程中承上啟下的關(guān)鍵環(huán)節(jié)，對芯片設(shè)計(jì)的效率和質(zhì)量都具有重要影響。具體來說，邏輯綜合旨在生成精準(zhǔn)滿足給定功能要求（如由電路輸入輸出對構(gòu)成的功能真值表）的最優(yōu)邏輯電路圖，是 NP 難問題。為了求解該問題，傳統(tǒng)方法主要依賴于硬編碼啟發(fā)式規(guī)則，易陷入次優(yōu)解。

該框架能夠精確生成達(dá)1200節(jié)點(diǎn)規(guī)模的電路，該方案為新一代芯片電路邏輯綜合工具提供了可行思路與奠定了關(guān)鍵基礎(chǔ)。相關(guān)技術(shù)和能力已整合入華為自研EDA工具。

引言

芯片電路生成的目標(biāo)是在給定電路功能描述的條件下，生成精準(zhǔn)滿足電路功能要求且節(jié)點(diǎn)數(shù)少的邏輯電路圖。傳統(tǒng)的電路生成方法將高級(jí)電路描述語言直接轉(zhuǎn)譯為冗余度較高的邏輯電路，這給后續(xù)的電路優(yōu)化帶來了較大壓力。近期，一些研究通過引入機(jī)器學(xué)習(xí)方法，將電路生成與優(yōu)化過程有機(jī)結(jié)合，展現(xiàn)了新一代邏輯綜合技術(shù)的美好前景。

神經(jīng)網(wǎng)絡(luò)架構(gòu)搜索（Differential Neural Network Architecture Search, DNAS）是一種利用梯度下降法搜索離散結(jié)構(gòu)的技術(shù)。已有研究將其應(yīng)用于生成低冗余電路，展現(xiàn)出了顯著的潛力。然而，作者發(fā)現(xiàn)現(xiàn)有方法在生成電路時(shí)，尤其是在處理大規(guī)模電路時(shí)，難以實(shí)現(xiàn)完全準(zhǔn)確的生成，且其性能對超參數(shù)極為敏感。

在深入的實(shí)驗(yàn)分析后，作者進(jìn)一步總結(jié)出將 DNAS 應(yīng)用于電路生成的三個(gè)主要難點(diǎn)：

1. DNAS 傾向于生成大量的跨層連接，導(dǎo)致網(wǎng)絡(luò)表達(dá)能力受限。
2. 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)與電路固有結(jié)構(gòu)存在較大偏差，顯著降低了 DNAS 的搜索效率。
3. 不同輸入輸出示例數(shù)據(jù)的學(xué)習(xí)難度差異顯著，現(xiàn)有方法難以學(xué)習(xí)難例輸入輸出對。

為系統(tǒng)性地解決這些挑戰(zhàn)，作者提出了一種新穎的正則化三角形電路網(wǎng)絡(luò)生成框架（T-Net），實(shí)現(xiàn)了完全準(zhǔn)確且可擴(kuò)展的電路生成。此外，他們還提出了一種由強(qiáng)化學(xué)習(xí)輔助的演化算法，以實(shí)現(xiàn)高效且有效的電路優(yōu)化。在四個(gè)電路評(píng)測標(biāo)準(zhǔn)數(shù)據(jù)集中，實(shí)驗(yàn)表明他們的方法能夠精確生成多達(dá) 1200 節(jié)點(diǎn)規(guī)模的電路，且其性能顯著優(yōu)于國際邏輯綜合競賽 IWLS 2022 和 2023 中冠亞軍方案。

背景與問題介紹

邏輯電路生成介紹

邏輯電路圖（And-Inverter Graph, AIG）是邏輯電路的一種表示方式。AIG 為有向無環(huán)圖，圖中的節(jié)點(diǎn)代表與邏輯門，圖中的邊代表邏輯門間的連線，連線上可以添加非門。邏輯電路的大小為 AIG 中的節(jié)點(diǎn)數(shù)，在邏輯功能不變的情況下，節(jié)點(diǎn)數(shù)越少表示電路結(jié)構(gòu)越緊湊，這將有助于后續(xù)的芯片設(shè)計(jì)優(yōu)化。

邏輯電路生成方法將電路的完整輸入輸出對組合，即功能真值表，建模為訓(xùn)練數(shù)據(jù)集，并利用機(jī)器學(xué)習(xí)模型自動(dòng)從數(shù)據(jù)集中學(xué)習(xí)生成邏輯電路圖 [1,2,3]。在電路設(shè)計(jì)的實(shí)際應(yīng)用中，要求設(shè)計(jì)精準(zhǔn)滿足功能要求的電路結(jié)構(gòu)，因此生成的邏輯電路圖必須在訓(xùn)練集上達(dá)到 100% 的準(zhǔn)確率。

基于 DNAS 的電路生成介紹

神經(jīng)網(wǎng)絡(luò)架構(gòu)搜索（Differential Neural Network Architecture Search, DNAS）[4] 近期被用于生成邏輯電路圖 [2,3]。這類方法將一個(gè) L 層，每層 K 個(gè)神經(jīng)元的神經(jīng)網(wǎng)絡(luò)建模為 AIG，其中神經(jīng)元視為邏輯門，神經(jīng)元之間的連接視為邏輯門之間的電路連接，神經(jīng)元可以連接到更淺層的任意神經(jīng)元。對于一個(gè)參數(shù)化的神經(jīng)網(wǎng)絡(luò)，每個(gè)神經(jīng)元都固定執(zhí)行與邏輯運(yùn)算，而神經(jīng)元之間的連接參數(shù)是可學(xué)習(xí)的。

為了能夠使用梯度下降法訓(xùn)練網(wǎng)絡(luò)結(jié)構(gòu)，現(xiàn)有方法會(huì)執(zhí)行 2 種連續(xù)化操作：1. 神經(jīng)元的邏輯運(yùn)算用等價(jià)的可微方式計(jì)算，例如 a 與 b 用 a?b 代替 [5]。2. 將離散的網(wǎng)絡(luò)連接方式參數(shù)化，并在前向傳播時(shí)使用 gumbel-softmax [6] 對連接進(jìn)行連續(xù)化和采樣。

在訓(xùn)練期間，真值表的每一行輸入 - 輸出對都作為訓(xùn)練數(shù)據(jù)輸入網(wǎng)絡(luò)，通過梯度下降法訓(xùn)練連接參數(shù)。在測試期間，每個(gè)節(jié)點(diǎn)的輸入根據(jù)參數(shù)只選擇一條連接，從而將網(wǎng)絡(luò)離散化，模擬實(shí)際的邏輯電路。

動(dòng)機(jī)實(shí)驗(yàn) ——DNAS 難以準(zhǔn)確生成電路

作者使用上述 DNAS 方法生成電路，生成準(zhǔn)確率和電路的規(guī)模如圖 1（a）所示。結(jié)果顯示，現(xiàn)有方法難以準(zhǔn)確生成電路，且準(zhǔn)確率隨著電路規(guī)模增大而減小。同時(shí)，他們發(fā)現(xiàn)生成準(zhǔn)確率對網(wǎng)絡(luò)初始化方式及其敏感，方法的魯棒性較差。

圖 1. 觀察實(shí)驗(yàn)。(a) 現(xiàn)有的 DNAS 方法難以準(zhǔn)確生成電路，特別是大規(guī)模電路。(b) 輸出節(jié)點(diǎn)位于網(wǎng)絡(luò)淺層，跳過了大量可用節(jié)點(diǎn)。(c) 實(shí)際只有約四分之一的節(jié)點(diǎn)被使用 (深色)。(d) 電路各層節(jié)點(diǎn)數(shù)統(tǒng)計(jì)，與普遍使用的方形網(wǎng)絡(luò)存在差異。

為了進(jìn)一步分析產(chǎn)生上述挑戰(zhàn)的原因，作者進(jìn)行了詳細(xì)的實(shí)驗(yàn)。 

首先，他們發(fā)現(xiàn)網(wǎng)絡(luò)利用率很低。由于節(jié)點(diǎn)間的連接可以跨層，因此存在被跳過的節(jié)點(diǎn)。圖 1（b）展示了經(jīng)過訓(xùn)練后輸出節(jié)點(diǎn)位于網(wǎng)絡(luò)中的位置，可以看到大部分網(wǎng)絡(luò)層都被跳過，沒有連接進(jìn)最終電路。圖 1（c）展示了網(wǎng)絡(luò)中實(shí)際使用到的節(jié)點(diǎn)（深色），只有約四分之一的底層節(jié)點(diǎn)被使用。過度的跨層連接浪費(fèi)了大量網(wǎng)絡(luò)結(jié)構(gòu)，限制了網(wǎng)絡(luò)的表達(dá)能力。

接著，他們發(fā)現(xiàn)實(shí)際電路結(jié)構(gòu)與網(wǎng)絡(luò)之間存在結(jié)構(gòu)偏差。他們統(tǒng)計(jì)了使用傳統(tǒng)方法生成電路的各層節(jié)點(diǎn)數(shù)，如圖 1（d）所示。圖中展示了實(shí)際電路在底層有著更多節(jié)點(diǎn)，而頂層則節(jié)點(diǎn)更少，這與普遍使用的方形網(wǎng)絡(luò)存在差異。

最后，他們發(fā)現(xiàn)不同輸入 - 輸出示例之間存在學(xué)習(xí)難度差。具體來說，它們在訓(xùn)練時(shí)的 loss 收斂速度存在顯著差異。這與通常認(rèn)為的獨(dú)立同分布（IID）假設(shè)并不相同。更多細(xì)節(jié)可見原論文第 4 章節(jié)。

方法介紹

針對以上三個(gè)挑戰(zhàn)，作者設(shè)計(jì)了新穎的正則化三角形電路生成框架（T-Net），如圖 2 所示。它包含 3 個(gè)部分：多標(biāo)簽數(shù)據(jù)變換、三角形網(wǎng)絡(luò)結(jié)構(gòu)、正則化損失函數(shù)。

圖 2. 作者提出的電路生成框架圖，包含多標(biāo)簽數(shù)據(jù)變換、三角形網(wǎng)絡(luò)結(jié)構(gòu)、正則化損失函數(shù)三部分。

多標(biāo)簽數(shù)據(jù)變換：提高可擴(kuò)展性

隨著輸入位數(shù)的增多，真值表的長度呈指數(shù)型增長。為了解決擴(kuò)展性挑戰(zhàn)，作者設(shè)計(jì)了基于香農(nóng)定理的多標(biāo)簽訓(xùn)練數(shù)據(jù)變換。香濃定理證明了一個(gè)邏輯函數(shù)可以通過一個(gè)分解變量分解成兩個(gè)子函數(shù)：

由于真值表是邏輯函數(shù)的對偶表示，他們通過以下兩步完成數(shù)據(jù)變換：首先選定一個(gè)輸入變量，通過固定它的值為 0 或 1，將真值表分解為 2 個(gè)長度減半的子表。接著將 2 個(gè)子表并列起來，每個(gè)輸入組合的輸出數(shù)量翻倍。

通過將真值表合并生成，網(wǎng)絡(luò)可以學(xué)習(xí)到更多可復(fù)用的結(jié)構(gòu)，從而減少最終的電路節(jié)點(diǎn)數(shù)。多標(biāo)簽數(shù)據(jù)變換可以不斷減少真值表的輸入位數(shù)，從而降低學(xué)習(xí)難度，加速電路生成。

三角形網(wǎng)絡(luò)結(jié)構(gòu)：減小搜索空間

為了使網(wǎng)絡(luò)結(jié)構(gòu)更好地適配電路特性，作者設(shè)計(jì)了三角形的網(wǎng)絡(luò)結(jié)構(gòu)。具體來說，更寬的底層結(jié)構(gòu)增強(qiáng)了網(wǎng)絡(luò)的表達(dá)能力，而細(xì)長的頂層結(jié)構(gòu)減少了利用率低的冗余節(jié)點(diǎn)，減小了搜索空間，加速了收斂。同時(shí)，實(shí)驗(yàn)證明了這種窄頂結(jié)構(gòu)也能有效加速具有大量輸出的電路生成。

正則化損失函數(shù)：精確生成電路

本論文的方法包含跨層連接正則化和布爾難度識(shí)別損失函數(shù)兩部分。對于跨層連接，作者對可學(xué)習(xí)的連接分布參數(shù)施加權(quán)重正則化，鼓勵(lì)網(wǎng)絡(luò)連接更臨近層的節(jié)點(diǎn)。對于較難學(xué)習(xí)的輸入 - 輸出示例，他們在損失函數(shù)中為這些示例施加更大的權(quán)重，以在訓(xùn)練后期加速收斂。

同時(shí)，本論文的框架還包含電路優(yōu)化部分。作者在強(qiáng)化學(xué)習(xí)優(yōu)化算子序列調(diào)優(yōu)的基礎(chǔ)上，結(jié)合了演化算法和 agent 重啟技術(shù)，避免陷入局部最優(yōu)解，實(shí)現(xiàn)快速有效的電路優(yōu)化。更多細(xì)節(jié)可見原文第 5 章節(jié)。

實(shí)驗(yàn)介紹

本論文實(shí)驗(yàn)的數(shù)據(jù)集包括 4 類開源電路數(shù)據(jù)集，節(jié)點(diǎn)數(shù)規(guī)模高達(dá) 1200，輸入、輸出數(shù)量最高為 16、63 位。

實(shí)驗(yàn)包含 4 個(gè)部分：1. 在多個(gè)電路上評(píng)估本論文電路生成和優(yōu)化方法的準(zhǔn)確性和電路性能。2. 評(píng)估本論文生成方法針對電路大小的可擴(kuò)展性。3. 通過消融實(shí)驗(yàn)展示本論文方法各部分的效用。4. 驗(yàn)證本論文方法對超參數(shù)的魯棒性。

作者在以下內(nèi)容中詳細(xì)介紹實(shí)驗(yàn) 1，其余實(shí)驗(yàn)請參見原論文的第 6 章節(jié)。

電路生成準(zhǔn)確率

部分實(shí)驗(yàn)結(jié)果見圖 3，作者在開源電路上對比了他們的方法與其他基于 DNAS 生成方法的準(zhǔn)確率。實(shí)驗(yàn)結(jié)果顯示，他們的方法準(zhǔn)確率大幅提升，并可準(zhǔn)確生成 1200 節(jié)點(diǎn)規(guī)模的電路。

圖 3. 作者提出的 T-Net 相比其他 DNAS 電路生成方法準(zhǔn)確率大幅提升。

電路綜合效果

部分實(shí)驗(yàn)結(jié)果見圖 4，作者在開源比賽電路上對比了他們的方法與開源邏輯綜合工具 ABC 和 IWLS 比賽冠亞軍的電路大小。實(shí)驗(yàn)結(jié)果顯示，他們的方法顯著優(yōu)于開源邏輯綜合工具 ABC 中的電路生成算子，且超過了 2022 和 2023 年比賽冠亞軍的方案。

圖 4. 作者提出的電路生成及優(yōu)化框架效果顯著優(yōu)于開源邏輯綜合工具 ABC 中的電路生成算子。