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

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

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

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

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

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

使用一種稱為模擬退火的搜索技術(shù)，布局規(guī)劃算法從隨機布局 [top] 開始。然后，它會嘗試通過交換兩個塊、將塊移動到另一個位置或調(diào)整塊的縱橫比來改進布局?？死锼埂し茽柌ㄌ?/p>

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

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

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

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

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

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

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