[發明專利]使用相關元啟發法的分區

有效

• 申請號: 201780051206.9
• 申請日: 2017-09-01
• 公開（公告）號: CN109923561B
• 公開（公告）日: 2023-09-26
• 發明（設計）人: R·J·艾瑞克森
• 申請（專利權）人: 新思科技公司
• 主分類號: G06F30/392
• 分類號: G06F30/392;G06F30/323;G06F30/327;G06F30/34
• 代理公司: 北京紀凱知識產權代理有限公司 11245
• 代理人: 張全信;趙蓉民

一種用于將包含多個節點的超圖分區到多個箱中的方法包含將所述超圖的每個節點分配給所述多個箱中的一個以生成候選解，以及對于所述候選解中的每對節點，基于所述候選解中所述節點對的每個節點的所述箱分配，計算加權協方差。重復所述分配和所述計算以為所述節點對生成累加的加權協方差，從所述累加的加權協方差中生成所述超圖的種子分區。

背景技術

超圖是圖的一般化，其中邊緣可以連接任何數量的頂點。形式上，超圖G＝(V,E)被定義為一組頂點(或節點)V和一組超邊緣(或邊緣)E，其中每個超邊緣是頂點集V的子集，并且超邊緣的大小或順序是此子集的基數。

超圖分區是一個重要的問題，廣泛應用于許多領域，包含超大規模集成(VLSI)集成電路設計、磁盤上大型數據庫的高效存儲以及數據挖掘。k路分區問題將超圖的每個節點分配到k個箱中的一個，同時試圖最小化“切割度量”，即連接分配給多個箱的節點的超邊緣的數量。除了邊緣成本之外，真實世界的分區問題通常具有多值成本函數，并且遵守各種約束。

對于分區集成電路設計的應用，超圖可以被認為是代表設計被分區成用于基于FPGA的原型設計的系統的k個FPGA單元的網表。除了切割度量外，應用還需要關注系統的時序以及可用于互連FPGA單元的導線數量和配置。

用于分區的常用方法是由Karypis和Kumar為hMETIS系統開發的多級分區方法。這種方法首先使用基于連接的群集粗化超圖，然后重復應用局部搜索優化啟發法(局部搜索)來對超圖進行分區，然后對圖進行“非粗化”。常見的局部搜索優化啟發法是Fiduccia-Mattheyses算法。

多級分區方法的結果質量(QoR)對超圖的最粗糙級別的初始解的質量敏感。局部搜索可能會卡在局部最小值。用于解決此限制的常用方法是運行多個局部搜索試驗，每個試驗都有不同的種子解，并保持最佳的解。

元啟發法實施了一種策略，用于指導復雜優化問題的搜索過程，目的是有效地探索解空間以找到接近最優的解。分區元啟發法是為局部搜索生成種子解的方法。常見的元啟發式方法包含隨機解生成和遺傳優化。

附圖說明

為了容易地識別對任何特定元素或動作的討論，參考數字中的一個或多個最高有效數字指的是首先引入該元素的圖號。

圖1是EDA系統的示例性高級框圖。

圖2是分區器系統的實施例的框圖。

圖3是候選解生成器的實施例的框圖。

圖4是相關元啟發法的實施例的框圖。

圖5示出了分配矩陣的實施例。

圖6示出了概率矩陣的實施例。

圖7示出了協方差矩陣的實施例。

圖8是解生成過程的實施例的流程圖。

圖9是根據一個實施例的將包含多個節點的超圖分區到多個箱中的流程圖。

圖10示出了相關元啟發法系統的實施例。

圖11示出了計算機系統的一個實施例。

具體實施方式

本文公開了使用相關元啟發法來改進用于設計集成電路或電路塊的電子設計自動化的方法的實施例，所述相關元啟發法通過跟蹤節點到箱的分配以及節點對之間的節點分配的相關來改進初始解生成的結果。在局部搜索算法的每次試驗之后，更新分配和相關信息。相關元啟發法使用累加的信息為后續迭代生成有效的種子解。具有被分配給相同箱的歷史的節點對更可能被分配給所得種子解中的相同箱。這改進了分區的整體結果。即使局部搜索卡在局部最小值，該過程也可以優化節點對，如果將它們分配給相同的箱，則將改進結果。成本較低的解改進相關信息。