中文題目：通過糾纏熵和投影釋放AQFP邏輯電路的布局潛力

論文題目：Unleashing the Potential of AQFP Logic Placement via Entanglement Entropy and Projection

錄用期刊/會議：61st ACM/IEEE Design Automation Conference (DAC '24) (CCF-A類會議)

DOI 鏈 接 ：https://dl.acm.org/doi/10.1145/3649329.3658467

發表時間：2024-6-23

作者列表：

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

2)伊恩鑫 中國石油大學（北京） 人工智能學院 碩 21級

3)邢煒 謝菲爾德大學 教師

4)余備 香港中文大學 教師

5)金洲 中國石油大學（北京）人工智能學院 教師

背景與動機:

隨著超導技術的發展，絕熱量子磁通參數邏輯（AQFP）作為一種高效的超導邏輯技術，因其能耗顯著低于傳統超導邏輯（如RSFQ）和CMOS技術而備受關注。然而，隨著電路規模的增大，AQFP電路的設計面臨諸多挑戰，特別是數據同步和最大線長約束問題，這些問題導致需要插入大量緩沖器來維持電路的正常運行，從而顯著增加了電路的功耗和延遲?，F有EDA工具針對CMOS技術設計，無法直接應用于AQFP電路，因此迫切需要開發專門針對AQFP電路的EDA工具。針對AQFP電路布局中緩沖器插入過多的問題，本文提出了一種創新的布局框架，旨在通過最小化額外緩沖器的需求來提升AQFP電路的性能。該框架利用糾纏熵進行拓撲初始化，并通過投影方法進行布局，有效減少了緩沖器的插入數量，同時顯著加速了布局過程。這一研究不僅有助于推動AQFP電路的設計自動化，也為超導電子學領域的發展提供了新的解決方案。

設計與實現:

1.糾纏熵

拓撲初始化的主要目的是通過優化電路中各行的單元順序，減少線長違規，從而降低后續布局階段對緩沖器的需求，提高電路的整體性能。

圖1.消除布線長度違規

我們定義一個叫做糾纏熵的術語用于初始布局，計算公式如下：

 

其中，Xl表示前一行中l的端點的順序，而Yl表示后續行中端點的順序。

我們展示了定義的糾纏熵可有效的用于電路拓撲的初始化過程。圖1展示了三個不同的電路拓撲示例，可以觀察到隨著拓撲結構中交點個數（N）的減少，電路的布局效果逐漸提高。同時，我們還展示了糾纏熵這一指標與交點的數量緊密相關，且利用糾纏熵（E）的變化來優化初始布局要好于直接使用交點個數（如圖2所示）。

 

 

圖2.糾纏熵不同的示例

2.減少糾纏熵

在拓撲初始化階段，算法通過在同一行內交換單元的位置來逐步優化電路拓撲。每次交換后，都會計算糾纏熵的減少量（ΔE），如果ΔE大于0，說明交換后拓撲的糾纏熵降低，電路布局得到優化，其計算公式如下:

 

將差值取為式中所示，即可得到ΔEi：

在算法開始時，通過對每行中的單元進行初始排序，可以進一步加速收斂過程。排序的依據是單元連接的線數，連接更多線的單元更有可能被放置在行的左端，這樣有助于在初始階段就獲得一個相對較低的糾纏熵。算法通過多次迭代，不斷交換單元位置，每次交換都旨在減少糾纏熵。隨著迭代的進行，電路布局逐漸優化，直至達到收斂條件，即糾纏熵不再顯著減少。

3.坐標初始化

坐標初始化旨在根據拓撲初始化階段得到的電路拓撲結構，為每個單元分配初始的坐標位置，以便在后續的迭代過程中能夠高效地調整單元位置并滿足布線約束。

 

圖3.(a)路徑平衡前的電路，(b)路徑平衡后的電路（通過插入buffer滿足同步和線長約束）

在確定單元的y坐標時，確保每行中單元的頂部左角的最小y坐標等于上一行中單元底部左角的最大y坐標。這樣做是為了減少布線長度，并確保數據能夠同步到達每一層的單元。對于同一行中的單元，根據拓撲初始化階段確定的順序緊密排列，并且使所有單元的中心在y軸方向上對齊。對于第一行，將頂部左角的y坐標設置為0。在迭代過程中，主要調整單元的x坐標。初始時，將每行中最左側單元的頂部左角的x坐標設置為0，其他單元則根據拓撲初始化階段確定的順序緊密排列。

4.單元的理想位置

在邏輯電路布局過程中，為每個單元找到一個理想的位置，以最小化與該單元相連的所有布線的最大長度，這是提高電路性能和效率的關鍵步驟之一。

 

圖4.移動單元到理想位置

初始狀態下，兩個單元通過一條可能超出最大布線長度約束的長布線相連。為簡化問題，我們采用基于投影思想的對稱翻轉方法，將某單元相鄰的兩行單元沿著單元所在的軸線對稱地“翻轉”到同一行上，同時保持布線長度不變。此步驟為理論操作，實際布局中不執行翻轉。在對稱處理的基礎上，通過水平移動將單元移至中間位置。

確定單元理想位置的關鍵在于最小化與其相連的所有布線中的最長布線長度。通過將所有相連的單元投影到一條直線上，并計算最左側和最右側單元x坐標的平均值，得到該單元的理想x坐標位置。將單元放置在此理想位置上，可以確保與其相連的所有布線長度盡可能均衡，從而避免過長布線導致的信號衰減或延遲增加，實現電路布局的優化。

實驗結果及分析: 

表1 測試電路信息

表1展示了用于評估所提出的AQFP邏輯電路布局算法的測試例的詳細信息，包括每個電路的名稱（如c17、c432等）、單元數量（從7個到7552個不等）以及所需緩沖器數量（從7個到3256個不等）。這些數據反映了測試例在電路規模和緩沖器需求上的多樣性，為驗證算法在不同規模和復雜度下的有效性提供了全面的基準。 

表2 測試結果對比

表2展示了三種算法（遺傳算法GA、ASAP算法和本文提出的算法）在多個測試案例上的性能比較。結果顯示，在插入的緩沖器數量和緩沖器行數方面，我們提出的算法表現最優，平均減少了98%和81%的緩沖器需求，顯著優于其他兩種方法。在時間開銷方面，我們的算法也表現出色，平均加速比分別達到GA方法的81.82倍和ASAP方法的1.88倍，體現了其在提高布局效率方面的優勢。

 

圖5.面積功耗延遲對比

通過柱狀圖展示了在c3540測試例上，應用ASAP算法和本文提出的算法后，電路的延時增加百分比、功耗增加百分比和面積增加百分比的比較。結果顯示，與ASAP算法相比，我們提出的算法的電路的延時、功耗和面積的增加百分比均顯著降低，表明算法在優化電路性能方面具有顯著優勢。具體來說，延時增加百分比從34%降低到13%，功耗增加百分比從42%降低到15%，面積增加百分比從38%降低到19%，體現算法在提升電路效率方面的有效性。

結論:

本文提出了一種新穎的算法，旨在高效地布局AQFP超導邏輯電路，減少在AQFP電路中額外插入的緩沖器數量，以提升電路的功率、性能和面積效率。算法分為拓撲初始化和布局插入緩沖器兩個階段，拓撲初始化階段通過引入最小化糾纏熵的概念來優化每行中單元的順序，布局插入緩沖器階段則通過迭代確定每個單元的具體坐標，并在必要時插入緩沖器以消除布線長度違規。實驗結果表明，與現有的GA方法和ASAP算法相比，本文提出的算法在緩沖器需求和運行時間上均表現出顯著優勢，平均減少了98%和81%的緩沖器需求，以及81.82倍和1.88倍的加速比。此外，對c3540電路的測試結果顯示，應用本文算法后的電路在延時、功耗和面積方面均有顯著降低，表明該算法在工業應用中的巨大潛力。 

通訊作者簡介:

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

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