芯片設計僅靠 AI 還不夠，可能需要經(jīng)典搜索和機器學(xué)習結合

自1971 年費德里科·法金 （Federico Faggin） 完成第一個(gè)商用微處理器 Intel 4004 的草圖以來(lái)，芯片設計已經(jīng)取得了長(cháng)足的進(jìn)步，當時(shí)他只用了直尺和彩色鉛筆。今天的設計人員可以使用大量的軟件工具來(lái)規劃和測試新的集成電路。但是，隨著(zhù)芯片變得越來(lái)越復雜（有些芯片包含數千億個(gè)晶體管），設計人員必須解決的問(wèn)題也越來(lái)越復雜。而這些工具并不總是能勝任這項任務(wù)。
現代芯片工程是一個(gè)由九個(gè)階段組成的迭代過(guò)程，從系統規范到封裝。每個(gè)階段都有多個(gè)子階段，每個(gè)子階段可能需要數周到數月的時(shí)間，具體取決于問(wèn)題的大小及其約束條件。許多設計問(wèn)題只有 10 個(gè)中只有少數幾個(gè)可行的解決方案100到 101000可能性——如果有的話(huà)，這是一個(gè)大海撈針的場(chǎng)景。當今使用的自動(dòng)化工具通常無(wú)法解決這種規模的現實(shí)問(wèn)題，這意味著(zhù)必須人工介入，這使得該過(guò)程比芯片制造商希望的更費力和耗時(shí)。
毫不奇怪，人們對使用機器學(xué)習來(lái)加速芯片設計的興趣日益濃厚。然而，正如我們在英特爾人工智能實(shí)驗室的團隊所發(fā)現的那樣，機器學(xué)習算法本身往往是不夠的，尤其是在處理必須滿(mǎn)足的多個(gè)約束時(shí)。
事實(shí)上，我們最近嘗試開(kāi)發(fā)一種基于 AI 的解決方案來(lái)處理一項稱(chēng)為布局規劃的棘手設計任務(wù)（稍后會(huì )詳細介紹該任務(wù)），這讓我們找到了一個(gè)基于非 AI 方法（如經(jīng)典搜索）的更成功的工具。這表明該領(lǐng)域不應該太快就否定傳統技術(shù)。我們現在相信，結合兩種方法優(yōu)點(diǎn)的混合方法，雖然目前是一個(gè)未被充分探索的研究領(lǐng)域，但將被證明是最富有成效的前進(jìn)道路。原因如下。

AI 算法的危險
芯片設計中最大的瓶頸之一發(fā)生在物理設計階段，在架構得到解決并且邏輯和電路已經(jīng)解決之后。物理設計涉及對芯片的布局和連接進(jìn)行幾何優(yōu)化。第一步是將芯片劃分為高級功能塊，例如 CPU 內核、內存塊等。然后，這些大分區被細分為較小的分區，稱(chēng)為宏和標準單元。一個(gè)系統級芯片 （SoC） 平均有大約 100 個(gè)高級模塊，由數百到數千個(gè)宏和數千到數十萬(wàn)個(gè)標準單元組成。
接下來(lái)是布局規劃，其中功能塊的排列滿(mǎn)足某些設計目標，包括高性能、低功耗和成本效益。這些目標通常是通過(guò)最小化線(xiàn)長(cháng)（連接電路元件的納米線(xiàn)的總長(cháng)度）和空白（未被電路占用的芯片總面積）來(lái)實(shí)現的。此類(lèi)布局規劃問(wèn)題屬于數學(xué)規劃的一個(gè)分支，稱(chēng)為組合優(yōu)化。如果您曾經(jīng)玩過(guò)俄羅斯方塊，那么您已經(jīng)解決了一個(gè)非常簡(jiǎn)單的組合優(yōu)化難題。
 

布局規劃是芯片設計的許多階段之一，其中 CPU 內核和其他功能塊的排列是滿(mǎn)足特定目標。這尤其具有挑戰性，因為它需要求解具有多個(gè)約束的大型優(yōu)化問(wèn)題?？死锼埂し茽柌ㄌ?/p>

Chip Floorplanning 就像打了類(lèi)固醇的俄羅斯方塊。首先，可能的解決方案的數量可能大得驚人——毫不夸張地說(shuō)。在典型的 SoC 平面圖中，大約有 10 個(gè)250排列 120 個(gè)高級塊的可能方法;相比之下，估計有 10 個(gè)24宇宙中的星星。宏和標準單元格的可能排列數量要大幾個(gè)數量級。
給定一個(gè)目標 — 例如，將功能塊壓縮到盡可能小的硅面積 — 商用布局規劃工具可以在短短幾分鐘內解決如此規模的問(wèn)題。然而，當面臨多個(gè)目標和限制時(shí)，例如關(guān)于某些塊必須去哪里、如何塑造它們或哪些塊必須放在一起的規則，它們就會(huì )陷入困境。因此，人類(lèi)設計師經(jīng)常求助于反復試驗和他們自己的聰明才智，從而將生產(chǎn)計劃增加數小時(shí)甚至數天。而這只是一個(gè)子階段。
盡管機器學(xué)習在過(guò)去十年中取得了勝利，但到目前為止，它對芯片設計的影響相對較小。像 Nvidia 這樣的公司已經(jīng)開(kāi)始訓練大型語(yǔ)言模型 （LLM）（為 Copilot 和 ChatGPT 等服務(wù)提供支持的 AI 形式）來(lái)為硬件設計程序編寫(xiě)腳本并分析錯誤。但這樣的編碼任務(wù)與解決像布局規劃這樣的復雜優(yōu)化問(wèn)題相去甚遠。
乍一看，將 Transformer 模型（LLM 的基礎）也拋向物理設計問(wèn)題可能也很誘人。從理論上講，我們可以通過(guò)訓練變壓器按順序預測芯片上每個(gè)模塊的物理坐標來(lái)創(chuàng )建一個(gè)基于 AI 的樓層規劃器，類(lèi)似于 AI 聊天機器人按順序預測句子中的單詞。但是，如果我們試圖教模型放置塊，使它們不會(huì )重疊，我們很快就會(huì )遇到麻煩。雖然人類(lèi)很容易掌握，但這個(gè)概念對于計算機來(lái)說(shuō)學(xué)習起來(lái)并不簡(jiǎn)單，因此需要大量的訓練數據和時(shí)間。同樣的事情也適用于進(jìn)一步的設計約束，比如要求將塊放在一起或靠近某個(gè)邊緣。
 

一個(gè)簡(jiǎn)單的平面圖 [左] 可以用 B* 樹(shù)數據結構 [右] 來(lái)表示?？死锼埂し茽柌ㄌ?br/>所以，我們采取了不同的方法。我們的第一項任務(wù)是選擇一種有效的數據結構來(lái)傳達平面圖中區塊的位置。我們落在了所謂的 B* 樹(shù)上。在此結構中，每個(gè)塊都表示為二叉樹(shù)上的一個(gè)節點(diǎn)。平面圖左下角的塊成為根。右側的塊變?yōu)橐粋€(gè)分支;頂部的塊將成為 Other Branch。此模式對于每個(gè)新節點(diǎn)都將繼續。因此，隨著(zhù)樹(shù)的生長(cháng)，它會(huì )在向右和向上扇動(dòng)時(shí)封裝平面圖。
B* 樹(shù)結構的一大優(yōu)點(diǎn)是它保證了無(wú)重疊的平面圖，因為塊的位置是相對的而不是絕對的——例如，“在另一個(gè)塊的上方”而不是“在這個(gè)位置”。因此，AI 樓層規劃師不需要預測它放置的每個(gè)塊的確切坐標。相反，它可以根據塊的維度以及其關(guān)系鄰居的坐標和維度輕松計算它們。瞧——沒(méi)有重疊。
有了數據結構，我們在包含數百萬(wàn)個(gè)最佳平面圖的數據集上訓練了幾個(gè)機器學(xué)習模型，特別是圖形神經(jīng)網(wǎng)絡(luò )、擴散模型和基于 transformer 的模型。這些模型學(xué)會(huì )了預測放置在先前放置的塊的上方或右側的最佳塊，以生成針對面積和線(xiàn)長(cháng)優(yōu)化的平面圖。但我們很快意識到，這種循序漸進(jìn)的方法行不通。我們將布局規劃問(wèn)題擴展到大約 100 個(gè)塊，并在無(wú)重疊規則之外添加了硬性約束。這些要求包括要求將一些塊放置在預定位置（如邊緣）或將共享相同電壓源的塊分組。然而，我們的 AI 模型浪費了時(shí)間尋求次優(yōu)解決方案。
我們推測，問(wèn)題在于模型無(wú)法回溯：因為它們按順序放置塊，所以它們無(wú)法追溯修復之前的錯誤放置。我們可以使用強化學(xué)習代理等技術(shù)來(lái)繞過(guò)這個(gè)障礙，但訓練一個(gè)好的模型所需的這種代理需要大量的探索是不切實(shí)際的。走到死胡同后，我們決定放棄逐個(gè)區塊的決策，嘗試新的策略。

回歸芯片設計傳統
解決大量組合優(yōu)化問(wèn)題的一種常見(jiàn)方法是使用一種稱(chēng)為模擬退火 （SA） 的搜索技術(shù)。SA 于 1983 年首次被描述，其靈感來(lái)自冶金學(xué)，其中退火是指將金屬加熱到高溫，然后緩慢冷卻的過(guò)程。受控的能量減少使原子能夠有序排列，使材料比快速冷卻時(shí)更堅固、更柔韌。以類(lèi)似的方式，SA 逐步找到優(yōu)化問(wèn)題的最佳解決方案，而不必繁瑣地檢查每一種可能性。
以下是它的工作原理。該算法從一個(gè)隨機解決方案開(kāi)始 — 就我們的目的而言，一個(gè)表示為 B* 樹(shù)的隨機平面圖。然后，我們允許算法再次隨機執行以下三個(gè)操作之一：它可以交換兩個(gè)塊，將塊從一個(gè)位置移動(dòng)到另一個(gè)位置，或調整塊的寬高比（不改變其面積）。我們通過(guò)取總面積和線(xiàn)長(cháng)的加權平均值來(lái)判斷最終 floorplan 的質(zhì)量。此數字描述操作的 “成本”。
如果新的平面圖更好（也就是說(shuō)，它降低了成本），我們就會(huì )接受它。如果情況更糟，我們最初也會(huì )接受它，因為我們知道一些 “壞 ”的決定可能會(huì )朝著(zhù)好的方向發(fā)展。然而，隨著(zhù)時(shí)間的推移，隨著(zhù)算法不斷隨機調整數據塊，我們接受增加成本的操作的頻率越來(lái)越低。與金屬加工一樣，我們希望逐步進(jìn)行這種轉變。正如過(guò)快冷卻金屬會(huì )使其原子陷入無(wú)序排列一樣，過(guò)早限制算法的探索可能會(huì )將其困在次優(yōu)解中，稱(chēng)為局部最小值。通過(guò)給算法足夠的余地來(lái)盡早避開(kāi)這些陷阱，我們可以哄騙它找到我們真正想要的解決方案：全局最小值（或它的良好近似值）。
我們使用 SA 解決布局規劃問(wèn)題的成功率要比使用我們的任何機器學(xué)習模型都要大得多。由于 SA 算法沒(méi)有放置順序的概念，因此它可以隨時(shí)對任何區塊進(jìn)行更改，基本上允許算法糾正早期的錯誤。在沒(méi)有限制的情況下，我們發(fā)現它可以在幾分鐘內解決具有數百個(gè)塊的高度復雜的平面圖。相比之下，使用商業(yè)工具的芯片設計師需要數小時(shí)才能解決相同的難題。
 

使用一種稱(chēng)為模擬退火的搜索技術(shù)，布局規劃算法從隨機布局 [top] 開(kāi)始。然后，它會(huì )嘗試通過(guò)交換兩個(gè)塊、將塊移動(dòng)到另一個(gè)位置或調整塊的縱橫比來(lái)改進(jìn)布局?？死锼埂し茽柌ㄌ?/p>

當然，實(shí)際設計問(wèn)題也有限制。因此，我們給 SA 算法提供了一些與機器學(xué)習模型相同的算法，包括對某些區塊的放置位置和分組方式的限制。我們首先嘗試通過(guò)將平面圖違反這些限制的次數添加到我們的成本函數中來(lái)解決這些硬性限制?，F在，當算法進(jìn)行隨機塊更改以增加約束違規時(shí)，我們以越來(lái)越大的概率拒絕這些操作，從而指示模型避免它們。
然而，不幸的是，這種策略適得其反。在 cost 函數中包含約束意味著(zhù)算法將嘗試在滿(mǎn)足約束和優(yōu)化面積和線(xiàn)長(cháng)之間找到平衡。但根據定義，硬性約束不能妥協(xié)。然而，當我們增加 constraints 變量的權重以考慮這種剛性時(shí)，該算法在優(yōu)化方面做得很差。模型沒(méi)有努力修復導致全局最小值（最優(yōu)平面圖）的違規行為，而是反復導致模型無(wú)法逃避的局部最小值（次優(yōu)平面圖）。
推進(jìn)機器學(xué)習
回到繪圖板，我們構思了 SA 的新變化，我們稱(chēng)之為約束感知 SA （CA-SA）。此變體使用兩個(gè)算法模塊。第一個(gè)是 SA 模塊，它側重于 SA 最擅長(cháng)的方面：優(yōu)化面積和線(xiàn)長(cháng)。第二個(gè)模塊選擇隨機約束沖突并修復它。這個(gè)修復模塊很少啟動(dòng)（大約每 10,000 次操作一次），但當它啟動(dòng)時(shí)，無(wú)論對面積和線(xiàn)長(cháng)的影響如何，它的決定總是被接受的。因此，我們可以引導我們的 CA-SA 算法朝著(zhù)滿(mǎn)足硬約束而不阻礙它的解決方案前進(jìn)。
使用這種方法，我們開(kāi)發(fā)了一個(gè)開(kāi)源的布局規劃工具，可以同時(shí)運行 CA-SA 的多個(gè)迭代。我們稱(chēng)其為具有約束感知的并行模擬退火，或簡(jiǎn)稱(chēng) Parsac。人類(lèi)設計師可以從 Parsac 的最佳解決方案中進(jìn)行選擇。當我們在多達 300 個(gè)塊的流行布局規劃基準測試中測試 Parsac 時(shí)，它輕松擊敗了所有其他已發(fā)布的公式，包括其他基于 SA 的算法和機器學(xué)習模型。

 
如果沒(méi)有約束感知，常規的 simulated-annealing 算法會(huì )產(chǎn)生無(wú)法改進(jìn)的次優(yōu) floorplan。在這種情況下，Block X 被困在無(wú)效位置。任何修復此沖突的嘗試都會(huì )導致其他幾個(gè)沖突?？死锼埂し茽柌ㄌ?/p>

然而，這些既定的基準測試已有二十多年的歷史，并不能反映現代 SoC 設計。一個(gè)主要缺點(diǎn)是它們缺乏硬性約束。為了了解 Parsac 在更真實(shí)的設計中的表現，我們在基準測試問(wèn)題中添加了自己的約束，包括關(guān)于塊放置和分組的規定。令我們高興的是，Parsac 在不到 15 分鐘的時(shí)間內成功解決了商業(yè)規模（約 100 個(gè)街區）的高級布局規劃問(wèn)題，使其成為同類(lèi)產(chǎn)品中已知最快的布局規劃器。
我們現在正在開(kāi)發(fā)另一種基于幾何搜索的非 AI 技術(shù)，以處理形狀奇特的塊的布局規劃，從而更深入地研究現實(shí)世界的場(chǎng)景。不規則的布局太復雜了，無(wú)法用 B* 樹(shù)來(lái)表示，所以我們回到了順序塊放置。早期結果表明，這種新方法可能比 Parsac 更快，但由于無(wú)回溯問(wèn)題，解決方案可能不是最佳解決方案。
同時(shí)，我們正在努力使 Parsac 適應宏放置，比塊布局規劃更精細一個(gè)級別，這意味著(zhù)從數百個(gè)元素擴展到數千個(gè)元素，同時(shí)仍然遵守約束。單獨的 CA-SA 可能太慢，無(wú)法有效解決這種規模和復雜性的問(wèn)題，而這正是機器學(xué)習可以提供幫助的地方。
 

Parsac 可在 15 分鐘內解決商業(yè)規模的布局規劃問(wèn)題，使其成為同類(lèi)算法中已知最快的算法。初始布局包含許多違反某些約束的塊 [red]。Parsac 更改了布局規劃以最小化面積和線(xiàn)長(cháng)，同時(shí)消除了任何約束沖突?？死锼埂し茽柌ㄌ?br/>例如，給定一個(gè) SA 生成的平面圖，我們可以訓練一個(gè) AI 模型來(lái)預測哪個(gè)操作會(huì )提高布局的質(zhì)量。然后，我們可以使用此模型來(lái)指導 CA-SA 算法的決策。該算法不會(huì )只采取隨機或“愚蠢”的操作（同時(shí)適應約束），而是以一定的概率接受模型的“智能”操作。我們推斷，通過(guò)與 AI 模型合作，Parsac 可以顯著(zhù)減少尋找最佳解決方案所需的操作數量，從而縮短其運行時(shí)間。但是，允許一些隨機操作仍然至關(guān)重要，因為它使算法能夠充分探索問(wèn)題。否則，很容易陷入次優(yōu)陷阱，就像我們失敗的基于 AI 的地板規劃師一樣。
這種或類(lèi)似的方法可能有助于解決 floorplanning 之外的其他復雜組合優(yōu)化問(wèn)題。在芯片設計中，此類(lèi)問(wèn)題包括優(yōu)化內核內互連的布線(xiàn)和布爾電路最小化，其中挑戰是構建具有最少門(mén)和輸入的電路來(lái)執行功能。

需要新的基準
我們與 Parsac 合作的經(jīng)驗也激發(fā)了我們創(chuàng )建樣本平面圖的開(kāi)放數據集，我們希望它能成為該領(lǐng)域的新基準。隨著(zhù)研究人員尋求驗證新的芯片設計工具，對這種現代基準測試的需求越來(lái)越迫切。例如，最近的研究基于舊基準或專(zhuān)有布局對新型機器學(xué)習算法的性能提出了質(zhì)疑，這引發(fā)了對這些聲明合法性的質(zhì)疑。
我們發(fā)布了兩個(gè)數據集，分別名為 FloorSet-Lite 和 FloorSet-Prime，現已在 GitHub 上提供。每個(gè)數據集包含 100 萬(wàn)個(gè)用于訓練機器學(xué)習模型的布局，以及 100 個(gè)針對面積和線(xiàn)長(cháng)優(yōu)化的測試布局。我們設計的布局充分體現了當代 SoC 平面圖的廣度和復雜性。它們的范圍從 20 到 120 個(gè)塊不等，并包括實(shí)際的設計約束。
 

為了開(kāi)發(fā)用于芯片設計的機器學(xué)習，我們需要許多示例平面圖。我們的 FloorSet 數據集之一的樣本具有約束 [red] 和形狀不規則的塊，這在實(shí)際設計中很常見(jiàn)?？死锼埂し茽柌ㄌ?/p>

這兩個(gè)數據集的復雜程度不同。FloorSet-Lite 使用矩形塊，反映了早期設計階段，當時(shí)塊通常被配置成簡(jiǎn)單的形狀。另一方面，FloorSet-Prime 使用不規則塊，這在設計過(guò)程的后期更為常見(jiàn)。此時(shí)，宏、標準單元格和其他組件在塊中的放置已得到優(yōu)化，從而產(chǎn)生了非矩形塊形狀。
盡管這些數據集是人工的，但我們小心翼翼地整合了商用芯片的特征。為此，我們創(chuàng )建了平面圖屬性的詳細統計分布，例如塊尺寸和約束類(lèi)型。然后，我們從這些發(fā)行版中采樣，以創(chuàng )建模擬真實(shí)芯片布局的綜合布局圖。
這種強大的開(kāi)放存儲庫可以顯著(zhù)推動(dòng)機器學(xué)習在芯片設計中的應用。然而，我們不太可能看到完全基于 AI 的解決方案來(lái)解決棘手的優(yōu)化問(wèn)題，例如布局規劃。深度學(xué)習模型在對象識別和語(yǔ)言生成等任務(wù)中占據主導地位，因為它們非常擅長(cháng)捕獲訓練數據中的統計規律，并將這些模式與所需的輸出相關(guān)聯(lián)。但是這種方法不適用于困難的組合優(yōu)化問(wèn)題，這些問(wèn)題需要模式識別以外的技術(shù)來(lái)解決。
相反，我們預計混合算法將成為最終的贏(yíng)家。通過(guò)學(xué)習識別最有前途的解決方案類(lèi)型進(jìn)行探索，AI 模型可以智能地指導 Parsac 等搜索代理，從而提高它們的效率。芯片設計人員可以更快地解決問(wèn)題，從而創(chuàng )建更復雜、更節能的芯片。他們甚至可以將多個(gè)設計階段組合成一個(gè)優(yōu)化問(wèn)題，或者同時(shí)追求多個(gè)設計。AI 可能無(wú)法完全自行創(chuàng )建芯片，甚至無(wú)法解決單個(gè)設計階段。但是，當與其他創(chuàng )新方法相結合時(shí)，它將改變該領(lǐng)域的游戲規則。