[發明專利]一種用于將超大規模網表轉換成DAG圖的方法和系統

有效

• 申請號: 202110320249.0
• 申請日: 2021-03-25
• 公開（公告）號: CN113065298B
• 公開（公告）日: 2022-05-20
• 發明（設計）人: 李肯立;張屹東;陳岑;肖正;劉楚波;唐卓;陽王東;廖清
• 申請（專利權）人: 湖南大學
• 主分類號: G06F30/31
• 分類號: G06F30/31;G06F30/392
• 代理公司: 武漢臻誠專利代理事務所(普通合伙) 42233
• 代理人: 宋業斌

本發明公開了一種用于將超大規模網表轉換成DAG圖的方法，包括：獲取網表，從該網表中提取電路單元及其連線信息，以生成一個圖，其以一個入邊鄰接表和一個出邊鄰接表存儲起來，對圖進行預處理，以得到預處理后的圖，檢測預處理后的圖中的所有強連通分量，并識別根據所有強連通分量識別多個環，提取每個環中的節點序號、以及該環中每個節點所連接的邊在入邊鄰接表和出邊鄰接表中的序號，根據每個環中節點和邊在入邊鄰接表中的序號，對該環中符合預定條件的入邊進行切割，以得到多個單向連通的子圖，使用虛節點將多個單向連通圖關聯起來，從而得到目標DAG圖。本發明能夠克服現有然而現有對電路單元進行設計與分析的方法存在的適用性差的技術問題。

技術領域

本發明屬于超大規模集成電路設計與分析技術領域，更具體地，涉及一種用于將超大規模網表轉換成DAG圖的方法和系統。

背景技術

在對超大規模集成電路進行設計與分析時，通常是針對電路單元進行。現有對電路單元進行設計與分析的方法一般是將電路單元的信息抽象成網表，再將得到的網表轉換成圖，然后對轉換得到的圖進行一系列的設計與分析，最后將結果映射回原集成電路。

然而，現有對電路單元進行設計與分析的方法，通常要求輸入的圖中不能包含環(即節點數大于1的強連通分量)。但在實際中，電路單元信息抽象成的網表中往往存在環，進而使得轉換得到的圖中也包含環，這就會導致現有的方法在很多場景中無法得到應用，進而降低了這些方法的適用性。

發明內容

針對現有技術的以上缺陷或改進需求，本發明提供了一種用于將超大規模網表轉換成DAG圖的方法和系統，其目的在于，可以在短時間內將網表信息轉換成DAG圖的形式，并克服現有然而現有對電路單元進行設計與分析的方法存在的在很多場景中無法得到應用，進而降低了這些方法的適用性的技術問題。

為實現上述目的，按照本發明的一個方面，提供了一種用于將超大規模網表轉換成DAG圖的方法，包括以下步驟：

(1)獲取網表，從該網表中提取電路單元及其連線信息，以生成一個圖，其以一個入邊鄰接表和一個出邊鄰接表存儲起來；

(2)對步驟(1)得到的圖進行預處理，以得到預處理后的圖；

(3)檢測步驟(2)預處理后的圖中的所有強連通分量，并識別根據所有強連通分量識別多個環，提取每個環中的節點序號、以及該環中每個節點所連接的邊在入邊鄰接表和出邊鄰接表中的序號；

(4)根據步驟(3)中獲得的每個環中節點和邊在入邊鄰接表中的序號，對該環中符合預定條件的入邊進行切割，以得到多個單向連通的子圖；

(5)使用虛節點將步驟(4)得到的多個單向連通圖關聯起來，從而得到目標DAG圖。

優選地，步驟(1)具體為，首先獲取網表，將網表中的電路單元及其連線信息轉換成圖的形式，忽略掉外部與電路模塊的輸入輸出連線，記錄網表中的電路單元及其內部相互間的連線信息；

在轉換過程中，將電路單元抽象成節點，并用一個類型標識來表示該節點所映射的電路單元的類型，將電路單元的面積或容量等參數抽象成點權，將電路單元間的通信時間抽象成邊權，然后分別用一個如入邊鄰接表和出邊鄰接表存儲圖的拓撲信息。

優選地，入邊鄰接表中的每個結點的條目包括圖中節點的序號、指向該節點的所有的邊的序號和每條邊的權重(即邊權)、該邊所對應的另一個節點的序號、以及指向該另一個節點所對應的結點的指針；

出邊鄰接表中每個結點的條目包括節點的序號，該節點所指向的所有邊的序號和每條邊的邊權、該邊所對應的另一個節點的序號、以及指向該另一個節點所對應的結點的指針。