科研動(dòng)態(tài)
通過(guò)糾纏熵和投影釋放AQFP邏輯電路的布局潛力
中文題目：通過(guò)糾纏熵和投影釋放AQFP邏輯電路的布局潛力
論文題目：Unleashing the Potential of AQFP Logic Placement via Entanglement Entropy and Projection
錄用期刊/會(huì)議：61st ACM/IEEE Design Automation Conference (DAC '24) (CCF-A類(lèi)會(huì)議)
DOI 鏈 接 ：https://dl.acm.org/doi/10.1145/3649329.3658467
發(fā)表時(shí)間：2024-6-23
作者列表：
1)柏一諾 中國(guó)石油大學(xué)（北京） 人工智能學(xué)院 本 19級(jí)
2)伊恩鑫 中國(guó)石油大學(xué)（北京） 人工智能學(xué)院 碩 21級(jí)
3)邢煒 謝菲爾德大學(xué) 教師
4)余備 香港中文大學(xué) 教師
5)金洲 中國(guó)石油大學(xué)（北京）人工智能學(xué)院 教師
背景與動(dòng)機(jī):
隨著超導(dǎo)技術(shù)的發(fā)展，絕熱量子磁通參數(shù)邏輯（AQFP）作為一種高效的超導(dǎo)邏輯技術(shù)，因其能耗顯著低于傳統(tǒng)超導(dǎo)邏輯（如RSFQ）和CMOS技術(shù)而備受關(guān)注。然而，隨著電路規(guī)模的增大，AQFP電路的設(shè)計(jì)面臨諸多挑戰(zhàn)，特別是數(shù)據(jù)同步和最大線(xiàn)長(zhǎng)約束問(wèn)題，這些問(wèn)題導(dǎo)致需要插入大量緩沖器來(lái)維持電路的正常運(yùn)行，從而顯著增加了電路的功耗和延遲?，F(xiàn)有EDA工具針對(duì)CMOS技術(shù)設(shè)計(jì)，無(wú)法直接應(yīng)用于A(yíng)QFP電路，因此迫切需要開(kāi)發(fā)專(zhuān)門(mén)針對(duì)AQFP電路的EDA工具。針對(duì)AQFP電路布局中緩沖器插入過(guò)多的問(wèn)題，本文提出了一種創(chuàng)新的布局框架，旨在通過(guò)最小化額外緩沖器的需求來(lái)提升AQFP電路的性能。該框架利用糾纏熵進(jìn)行拓?fù)涑跏蓟⑼ㄟ^(guò)投影方法進(jìn)行布局，有效減少了緩沖器的插入數(shù)量，同時(shí)顯著加速了布局過(guò)程。這一研究不僅有助于推動(dòng)AQFP電路的設(shè)計(jì)自動(dòng)化，也為超導(dǎo)電子學(xué)領(lǐng)域的發(fā)展提供了新的解決方案。
設(shè)計(jì)與實(shí)現(xiàn):
1.糾纏熵
拓?fù)涑跏蓟闹饕康氖峭ㄟ^(guò)優(yōu)化電路中各行的單元順序，減少線(xiàn)長(zhǎng)違規(guī)，從而降低后續(xù)布局階段對(duì)緩沖器的需求，提高電路的整體性能。
圖1.消除布線(xiàn)長(zhǎng)度違規(guī)
我們定義一個(gè)叫做糾纏熵的術(shù)語(yǔ)用于初始布局，計(jì)算公式如下：
其中，Xl表示前一行中l(wèi)的端點(diǎn)的順序，而Yl表示后續(xù)行中端點(diǎn)的順序。
我們展示了定義的糾纏熵可有效的用于電路拓?fù)涞某跏蓟^(guò)程。圖1展示了三個(gè)不同的電路拓?fù)涫纠梢杂^(guān)察到隨著拓?fù)浣Y(jié)構(gòu)中交點(diǎn)個(gè)數(shù)（N）的減少，電路的布局效果逐漸提高。同時(shí)，我們還展示了糾纏熵這一指標(biāo)與交點(diǎn)的數(shù)量緊密相關(guān)，且利用糾纏熵（E）的變化來(lái)優(yōu)化初始布局要好于直接使用交點(diǎn)個(gè)數(shù)（如圖2所示）。
圖2.糾纏熵不同的示例
2.減少糾纏熵
在拓?fù)涑跏蓟A段，算法通過(guò)在同一行內(nèi)交換單元的位置來(lái)逐步優(yōu)化電路拓?fù)?。每次交換后，都會(huì)計(jì)算糾纏熵的減少量（ΔE），如果ΔE大于0，說(shuō)明交換后拓?fù)涞募m纏熵降低，電路布局得到優(yōu)化，其計(jì)算公式如下:
將差值取為式中所示，即可得到ΔEi：
在算法開(kāi)始時(shí)，通過(guò)對(duì)每行中的單元進(jìn)行初始排序，可以進(jìn)一步加速收斂過(guò)程。排序的依據(jù)是單元連接的線(xiàn)數(shù)，連接更多線(xiàn)的單元更有可能被放置在行的左端，這樣有助于在初始階段就獲得一個(gè)相對(duì)較低的糾纏熵。算法通過(guò)多次迭代，不斷交換單元位置，每次交換都旨在減少糾纏熵。隨著迭代的進(jìn)行，電路布局逐漸優(yōu)化，直至達(dá)到收斂條件，即糾纏熵不再顯著減少。
3.坐標(biāo)初始化
坐標(biāo)初始化旨在根據(jù)拓?fù)涑跏蓟A段得到的電路拓?fù)浣Y(jié)構(gòu)，為每個(gè)單元分配初始的坐標(biāo)位置，以便在后續(xù)的迭代過(guò)程中能夠高效地調(diào)整單元位置并滿(mǎn)足布線(xiàn)約束。
圖3.(a)路徑平衡前的電路，(b)路徑平衡后的電路（通過(guò)插入buffer滿(mǎn)足同步和線(xiàn)長(zhǎng)約束）
在確定單元的y坐標(biāo)時(shí)，確保每行中單元的頂部左角的最小y坐標(biāo)等于上一行中單元底部左角的最大y坐標(biāo)。這樣做是為了減少布線(xiàn)長(zhǎng)度，并確保數(shù)據(jù)能夠同步到達(dá)每一層的單元。對(duì)于同一行中的單元，根據(jù)拓?fù)涑跏蓟A段確定的順序緊密排列，并且使所有單元的中心在y軸方向上對(duì)齊。對(duì)于第一行，將頂部左角的y坐標(biāo)設(shè)置為0。在迭代過(guò)程中，主要調(diào)整單元的x坐標(biāo)。初始時(shí)，將每行中最左側(cè)單元的頂部左角的x坐標(biāo)設(shè)置為0，其他單元?jiǎng)t根據(jù)拓?fù)涑跏蓟A段確定的順序緊密排列。
4.單元的理想位置
在邏輯電路布局過(guò)程中，為每個(gè)單元找到一個(gè)理想的位置，以最小化與該單元相連的所有布線(xiàn)的最大長(zhǎng)度，這是提高電路性能和效率的關(guān)鍵步驟之一。
圖4.移動(dòng)單元到理想位置
初始狀態(tài)下，兩個(gè)單元通過(guò)一條可能超出最大布線(xiàn)長(zhǎng)度約束的長(zhǎng)布線(xiàn)相連。為簡(jiǎn)化問(wèn)題，我們采用基于投影思想的對(duì)稱(chēng)翻轉(zhuǎn)方法，將某單元相鄰的兩行單元沿著單元所在的軸線(xiàn)對(duì)稱(chēng)地“翻轉(zhuǎn)”到同一行上，同時(shí)保持布線(xiàn)長(zhǎng)度不變。此步驟為理論操作，實(shí)際布局中不執(zhí)行翻轉(zhuǎn)。在對(duì)稱(chēng)處理的基礎(chǔ)上，通過(guò)水平移動(dòng)將單元移至中間位置。
確定單元理想位置的關(guān)鍵在于最小化與其相連的所有布線(xiàn)中的最長(zhǎng)布線(xiàn)長(zhǎng)度。通過(guò)將所有相連的單元投影到一條直線(xiàn)上，并計(jì)算最左側(cè)和最右側(cè)單元x坐標(biāo)的平均值，得到該單元的理想x坐標(biāo)位置。將單元放置在此理想位置上，可以確保與其相連的所有布線(xiàn)長(zhǎng)度盡可能均衡，從而避免過(guò)長(zhǎng)布線(xiàn)導(dǎo)致的信號(hào)衰減或延遲增加，實(shí)現(xiàn)電路布局的優(yōu)化。
實(shí)驗(yàn)結(jié)果及分析:
表1 測(cè)試電路信息
表1展示了用于評(píng)估所提出的AQFP邏輯電路布局算法的測(cè)試?yán)脑敿?xì)信息，包括每個(gè)電路的名稱(chēng)（如c17、c432等）、單元數(shù)量（從7個(gè)到7552個(gè)不等）以及所需緩沖器數(shù)量（從7個(gè)到3256個(gè)不等）。這些數(shù)據(jù)反映了測(cè)試?yán)陔娐芬?guī)模和緩沖器需求上的多樣性，為驗(yàn)證算法在不同規(guī)模和復(fù)雜度下的有效性提供了全面的基準(zhǔn)。
表2 測(cè)試結(jié)果對(duì)比
表2展示了三種算法（遺傳算法GA、ASAP算法和本文提出的算法）在多個(gè)測(cè)試案例上的性能比較。結(jié)果顯示，在插入的緩沖器數(shù)量和緩沖器行數(shù)方面，我們提出的算法表現(xiàn)最優(yōu)，平均減少了98%和81%的緩沖器需求，顯著優(yōu)于其他兩種方法。在時(shí)間開(kāi)銷(xiāo)方面，我們的算法也表現(xiàn)出色，平均加速比分別達(dá)到GA方法的81.82倍和ASAP方法的1.88倍，體現(xiàn)了其在提高布局效率方面的優(yōu)勢(shì)。
圖5.面積功耗延遲對(duì)比
通過(guò)柱狀圖展示了在c3540測(cè)試?yán)?，?yīng)用ASAP算法和本文提出的算法后，電路的延時(shí)增加百分比、功耗增加百分比和面積增加百分比的比較。結(jié)果顯示，與ASAP算法相比，我們提出的算法的電路的延時(shí)、功耗和面積的增加百分比均顯著降低，表明算法在優(yōu)化電路性能方面具有顯著優(yōu)勢(shì)。具體來(lái)說(shuō)，延時(shí)增加百分比從34%降低到13%，功耗增加百分比從42%降低到15%，面積增加百分比從38%降低到19%，體現(xiàn)算法在提升電路效率方面的有效性。
結(jié)論:
本文提出了一種新穎的算法，旨在高效地布局AQFP超導(dǎo)邏輯電路，減少在A(yíng)QFP電路中額外插入的緩沖器數(shù)量，以提升電路的功率、性能和面積效率。算法分為拓?fù)涑跏蓟筒季植迦刖彌_器兩個(gè)階段，拓?fù)涑跏蓟A段通過(guò)引入最小化糾纏熵的概念來(lái)優(yōu)化每行中單元的順序，布局插入緩沖器階段則通過(guò)迭代確定每個(gè)單元的具體坐標(biāo)，并在必要時(shí)插入緩沖器以消除布線(xiàn)長(zhǎng)度違規(guī)。實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有的GA方法和ASAP算法相比，本文提出的算法在緩沖器需求和運(yùn)行時(shí)間上均表現(xiàn)出顯著優(yōu)勢(shì)，平均減少了98%和81%的緩沖器需求，以及81.82倍和1.88倍的加速比。此外，對(duì)c3540電路的測(cè)試結(jié)果顯示，應(yīng)用本文算法后的電路在延時(shí)、功耗和面積方面均有顯著降低，表明該算法在工業(yè)應(yīng)用中的巨大潛力。
通訊作者簡(jiǎn)介:
金洲，副教授，中國(guó)石油大學(xué)（北京）計(jì)算機(jī)系副教授，入選北京市科協(xié)青年人才托舉工程、中國(guó)石油大學(xué)（北京）青年拔尖人才。主要從事集成電路設(shè)計(jì)自動(dòng)化（EDA）方面的研究工作。主持并參與國(guó)家自然科學(xué)基金青年項(xiàng)目、培育項(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、TODAES等多個(gè)頂刊頂會(huì)程序委員會(huì)委員和審稿人。獲SC23最佳論文獎(jiǎng)、SC24最佳論文提名、EDA2青年科技獎(jiǎng)、ISEDA23榮譽(yù)論文獎(jiǎng)、IEEJ九州支部長(zhǎng)獎(jiǎng)等。
聯(lián)系方式：jinzhou@cup.edu.cn