啟發(fā)式算法與在線式解析

1、 本文由0q8u0yzm1b貢獻 pdf文檔可能在WAP端瀏覽體驗不佳。建議您優(yōu)先選擇TXT，或下載源文件到本機查看。 第 卷 第 期 年 月 信 息 工 程 大 學 學 報 啟 發(fā) 式 算 法 與在 線 式 解 析 羅 穎 ， 肖梓 祥 （ 息 工 程 大學 信息 工 程 學 院 ， 南 鄭 州 ， 信 河 ） 摘 要 ： 對在 線 式芯 片解析 方法 中數(shù)據(jù) 的特 點 ， 針 分析 了經(jīng) 典邏 輯綜 合算 法 的不適 用 性和啟 發(fā) 式 算 法 的可行性 。 同 時， 對邏 輯綜 合軟 件 實現(xiàn)過 程 中要解 決 的問題進 行 了分 析。 關 鍵 詞 ： 線 式解 析 ； 發(fā) 式算 法 ；

2、 輯綜 合軟 件 在 啟 邏 中圖 分類 號 ： 文獻 標識 碼 ： 文 章編 號 ： ） （ ， （ ， ， ） ， ： ： ； ； 和 啟發(fā)式 算 法兩類 。 引 言 在 線 式 解 析法 是 在 脫 機式 解 析 法遇 到 極 大 的 困難 下提 出 的。在脫 機式 解析 法 中 ， 明芯 片需 從 不 設 備上 取下 來插 到一 個專 門的硬件 平 臺上 ， 輸 入 從 經(jīng)典 邏輯 綜合 算法 分析 經(jīng) 典 的邏輯綜 合算 法 是先 求 出質蘊 涵項 ， 再求 最 小覆蓋 。常用 的算 法有 ： 進 的 算 法 、 義 改 廣 相 容算 法和 銳積 法等 。 以下結 合這 種算 法對

3、“ 在 線 式” 集到 的數(shù) 據(jù)進 行邏 輯綜 合處 理時 的適 用性 采 做 簡單 分析 。 改進 的 算 法 端 施加 激勵 ， 輸 出端 收集 數(shù) 據(jù) ， 集 到 的 數(shù) 據(jù) 與 從 采 芯 片輸 入 端 施 加 的激 勵 相 關 ， 有 連 續(xù) 性 和 唯 一 具 性， 而且是 芯片 的工 作全 集 。該方 法采 集 和處理 的 數(shù)據(jù) 量隨著 不 明芯 片 引腳數(shù) 的增 加而 成指 數(shù)增 長 。 該 算 法是 將 數(shù) 值最 小 的最 小 項 和數(shù) 值 最 大 的 最 小項相 合并 ， 到 覆蓋 函數(shù) 最 大 的 多 維體 ， 得 目的 是 將盡 可能 多 的 （ 點 與 或 ） 點 相

4、合 并 ， 從 而得 到最簡 的質 蘊涵 項集 合 。 該算 法 不受 數(shù)據(jù) 離散性 的影 響 ， 但綜 合 過程 中 在 這種 情況 下 ， 大規(guī) 模 引腳數(shù) 的芯 片解 析幾 乎不 可 能 。在“ 線式 ” ， 片 不從 設 備 上 取 下 來 ， 是 在 中 芯 而 采 用邏 輯分 析儀 實 時 采 集 芯 片在 目標 系統(tǒng) 中的 工 作 數(shù)據(jù) ， 且對 其 分 析 處理 ， 據(jù)采 集 過 程 與 目標 并 數(shù) 系統(tǒng) 的工 作狀 態(tài)相關 ， 集到 的數(shù) 據(jù)是 芯 片的 工作 采 集 ， 有 隨機性 、 具 離散 性 和非 全集 等特點 。 必 須得 到全 部 的 點 集合 和 點集 合

5、， 即必 須 是 數(shù)據(jù) 全集 ， 則 綜 合 出來 的質 蘊 涵 項 就 會 出錯 。 否 因此 ， 改進 的 算 法 不適 合 “ 線 式 ” 的數(shù) 據(jù) 在 中 處理。 啟 發(fā) 式 算 法 與 在 線 式 解 析 目前 國 內外 采用 的邏 輯綜 合 算 法有 經(jīng)典 算 法 收稿 日期 ： 廣 義相 容算 法 廣 義相 容算 法綜 合數(shù) 據(jù) 的特 點是 ： 從數(shù) 據(jù)集 的 某 一端 元 素不 同的蘊 涵項 開 始合 并 ， 后逐 次 與其 然 作者簡介： 羅穎 （一） 女 ， 南 淮 陽 人 ， 息 工 程 大學 碩 士 研 究 生 ， 究 方 向 為 數(shù) 字 系統(tǒng) 設 計 自動化 。 ，

6、河 信 研 第 期 羅 穎 等 ： 發(fā) 式 算 法 與在 線 式 解 析 啟 它 原始蘊 涵項 進行 比較 ， 同 時將 能合并 的蘊 涵項 并 個 芯片 內的 多輸 出函 數(shù)解耦 成單 輸 出 函數(shù) ， 即綜 合 合并 ， 復處 理 ， 至 不能進 一 步處理 ， 求得 全部 反 直 便 質 蘊涵項 。 出每一 條 輸 出腿 的 質 蘊 涵 項 集 合 ， 求 出 最 小 覆 并 蓋 。 因此 ， 們就 必 須 根 據(jù)采 集 到 的 數(shù)據(jù) ， 行 芯 我 進 廣 義相 容算 法在 對數(shù) 據(jù)的處 理過 程 中 ， 受數(shù) 不 據(jù) 離散性 的影 響 ， 每 次都 要 將 其余 但 點 集合 和 點

7、集 合進 行 比較 ， 而 導 致 時 間復 雜 度 加 大 ， 從 并且 中間過程 的 點 集 合 和 點 集 合 要 一 直 保 留到算 法結 束 ， 又導 致 空 間 復 雜 度 變大 ， 以在 所 進 行大規(guī) 模 芯片 的數(shù) 據(jù)處 理時 ， 用該 算 法會使 解 析 片輸 入輸 出 引腳信 息 的相關 性分 析 ， 出 相關 的輸 找 入輸 出信息 ， 而 確 定 出 我 們最 終 要 綜 合 的數(shù) 據(jù) 。 從 這樣 ， 就有 了兩 類 數(shù) 據(jù) 格 式 ， 們 定 義 了 如下 數(shù) 據(jù) 我 結構 。 解耦 前 的數(shù)據(jù) 結構 在“ 在線式 ” 析 中 ， 解 采用 邏 輯分 析儀來 實

8、時采 集 芯片 的工作 集 ， 是這 些數(shù) 據(jù) 具有很 大 的離散 性 但 和重 復性 ， 了 滿 足 啟 發(fā) 式 算 法 對 數(shù) 據(jù) 處 理 的 要 為 的時空效 率 不堪 忍 受 。 而在 線 式 解 析 法 是 針對 大 規(guī) 模多腿 芯 片而研 制 的 ， 以該 算法 同樣 不適 用 。 所 銳積 法 該算 法 是一個 求 補 的過程 ， 目的是從 數(shù)據(jù) 全集 中逐 一去 掉 或 頂 點 ， 而將 數(shù)據(jù) 全 集 分 （ ） 從 求 ， 們首 先對 數(shù) 據(jù) 進 行 冗余 處 理 ， 我 然后 再 進 行 數(shù) 據(jù)格 式化 的轉 化 ， 即將 數(shù)據(jù) 以狀 態(tài)真值 表 的形式 存 放 到存儲 器

9、 中 。其 中 ， 對芯 片狀 態(tài)真值 表 的存儲 我 采用 字 節(jié)存 儲 ， 個 引腳 的 信息 占一 位 ， 滿 每 不 一 裂 成多個 質蘊 涵 項 。 銳 積運 算 是 通 過 產(chǎn) 生 的 中 間 結 果 與剩 余 的多 維體 集合 繼續(xù) 進行綜 合 化簡 ， 是 但 在線 式解 析 法 中采集 的數(shù)據(jù) 離 散度 大 ， 以中間處 所 理 過程 中產(chǎn) 生 的中間 結果 迅猛 增長 ， 由于銳 積 運 再 個 字 節(jié)的用 填充 。具 體格 式 如圖 。 有效輸入變量 充 位 填 一 狀態(tài)輸入變量 。 輸出變量 算 是最 復雜 的一 種綜 合運算 ， 以采用 銳積 法處理 所 離 散度 大

10、的 數(shù)據(jù) 會造 成解 析過 程時 間太 長 ， 至使 甚 填 充 位 按 字節(jié)存儲 一 按 字節(jié)存儲 綜 合處理 成 為不 可能 。 啟 發(fā) 式算 法基 本思 想 針 對在線 式解 析 法 中數(shù)據(jù) 的特點 ， 經(jīng)典 的邏輯 圖 引 腳 信 息 存 儲 結 構 解耦 后 的數(shù)據(jù) 結構 綜 合算 法 已不適 用 ， 過實 踐 中的 綜 合 比較 ， 們 經(jīng) 我 采用 啟發(fā) 式算 法 。其 中 最 具 有 代表 性 ， 它 求取 邏輯 函數(shù) 廠覆 蓋 的特 點 是 把 一 個 給 定 的 定 義 在一 個 維 布 爾空 間 的 個輸 出函數(shù) 的邏 輯 函數(shù) 廠的 覆 蓋 ， ， ， 換 成 廠 ，

11、， 轉 的一個 含多 維體 數(shù) 較 少 的質 覆 蓋 我 們 稱 此 過 ， 由 引腳信息 的存 儲結 構 我們 知道 ， 是 由 正 于啟 發(fā)式 算 法是針 對 大規(guī)模 芯 片的解 析 而提 出的 ， 其 中包括 若 干個 輸 出 引腳 ， 此 ， 具 體實 現(xiàn) 過 程 因 在 中 ， 了方 便邏 輯 綜 合 ， 們 將 具 有 多 個 輸 出 函數(shù) 為 我 的不 明芯片解 耦 ， 即將 多輸 出 函數(shù)解 耦為 單輸 出 函 數(shù)， 解耦 后 的數(shù)據(jù) 存儲 格式 如 圖 。 程 為擴 展過 程 。此過 程包 含兩 個運 算 ， 一是 對每 個 用 包 含它 的質 蘊 涵項 （ “ ） 替 換

12、； “ 來 二 是將 中被 所包 含 的 多維 體 刪 去 。這樣 ， 通 過 擴展可 期 望得 到一 個含 較少 多維 體 的覆蓋 。 啟 發(fā) 式算 法是 針 對 某個 選 定 的 多 維體 進 行 擴 一 ： ： ： ！ ： ！ ！ ： ！ ！ ！ ： ！ 。 按字節(jié)存儲 圖 解耦 后 的輸 出 引腳 狀 態(tài) 真 值 表 格 式 展， 其最 終 產(chǎn)生 的近 似最小 覆 蓋 的大小 與分 析系 統(tǒng) 所 選定 的待 擴展 的 多維 體有關 ， 定原 則 由算法 實 選 現(xiàn) 人員 自己確 定 。在 運 算 過 程 中 隨著 多維 體 的 不 斷 擴展 ， 其所 產(chǎn) 生 的 中 間結 果 逐 漸

13、減 少 ， 而 使 算 從 封 鎖 矩 陣 和 覆 蓋 矩 陣 由于多 輸 出 函數(shù) 的 解 耦 ， 于 每 一個 輸 出 ， 對 我 們 都有 一張 狀 態(tài) 真值 表 與 之 對 應 。在 狀 態(tài) 真值 表 法 的空 間復 雜 度進一 步 降低 ， 因而 該算 法適 合處 理 離 散度 大 的數(shù)據(jù) 。 邏輯 綜合 軟件 實現(xiàn) 過程 中需解 決的 問題 多輸 出函數(shù) 的解耦 中 ， 含有 僅 點集 合 和 點集 合 ， 不考 慮 而 集 合 。我們 知道 ， 啟發(fā) 式算 法 實質 上就是 對 （ 或 點集 合 的各項 進 行 逐 位提 升 ， 到 質 蘊 涵項 ， ） 得 并 從 中直接 求得

14、 近似 最小 覆 蓋 。所 以 ， 在具 體程 序 實 現(xiàn)過 程 中 ， 必須 定 義封 鎖矩 陣 和覆 蓋 矩 陣 ， 經(jīng) 過 比較 ， 我們 決定 采用 適合 大規(guī) 模芯 片解 析 的啟 發(fā)式算 法 。依據(jù) 邏輯 綜合 的理論 ， 邏輯 綜合 算 使 得擴 展過 程變 得簡 單 ， 同時 降低算 法 的時空 復 雜 度 ， 能滿足 大規(guī) 模引 腳芯 片的 解析 需求 。 更 法 的任務 是對 采集 到 的數(shù) 據(jù)進 行綜 合 ， 將設 計在 一 信 息 工 程 大 學 學 報 正 封鎖矩陣 我 們 知道 ， 任何 一多維 體 的擴展 都 不能是 任 意 后不 需要 再考 慮 ； 中刪 去 此

15、 行 集 是 因 為 中 在 對應 的多 維體 一 定 不 能 被 所 蘊 涵 ， 因此 可 刪 除 不作 考慮 。 正是 由于定 義 了封鎖 矩 陣和覆 蓋矩 陣 ， 的， 它受 到 一定 的約束 ， 即 與給 定 函數(shù) 廠的 點集合 之交 必 須 為 空 （ ） 否 則 ， 將 含有 廠的 集合 中的最 小 項 而 不成 為 廠的 蘊 涵 使得 啟發(fā) 式算 法更 加 系統(tǒng) 和有效 。 項 。因此 ， 進 行 擴 展 時 ， 們 除 了需 用 給 定 在 我 結語 啟 發(fā) 式 算 法 占用 空 間 小 ， 初 始 點 集 合 為 、 點集合 足 以及封鎖 矩 陣 和覆蓋 矩陣 占 用 的空

16、間之 和 ， 而且 隨著 多維 體 的擴展 不 斷消 去矩 陣 中的行 和列 ， 而 使 算 法 的 空 間 復雜 度 逐 漸 減 從 小 。 由于在線 式采 集 到的數(shù) 據(jù)都 是零 維體 ， 法不 算 點集合 外 ， 需 要 用 到 點 集 合 。而 封 鎖 還 矩 陣 是 由 及 中 的所 有 多維 體 定 的 決 矩陣 ， 其每 一列 與 的一元 素對 應 ， 每一 行 與 中 一 多維 體對 應 ， 其元 素 由下 式 決定 ： ， 或 而 一 而 ， 【， 它 。 其 由封 鎖矩 陣定 義可 以看 出 ， 義它 的最 大 目的 定 就是 當 擴 展 為 時避 免 了擴展 過 渡 。

17、覆 蓋矩 陣 要求 對 多維體 進 行排 序 ， 是擴 展 的順 序 不 同， 只 綜 合 出來 的結果 也就 有所 不 同 ， 在 函數(shù) 功 能上 是完 但 全等 效 的。啟 發(fā)式 算法 只與 器件 工作 集有關 ， 考 不 慮無關 項 集合 ， 不受 在線 式采 集 的數(shù) 據(jù)離散 性 的影 響， 能夠滿 足大規(guī)模 引 腳芯 片解析 的需 要 。 參考文獻 ： ， 定 義 ： 為 中 待擴 展 的多 維 體 ， 設 以后 的 多維 體組 成集 合 ， 蓋矩 陣 是 一個 由 及 決 覆 定的 陣， 矩 每一 列 與 的元 素 對應 ， 一行 每 與 中的 多維體 對應 。覆蓋 矩 陣 的作 用 是 為 了 使 涵 中盡 可 能 多 的 其 它 多 維 體 。定 義 如 蘊 下： ， 而 或 而 ， ， 其它 。 借 助 于這 兩個矩 陣 ， 在擴 展 過 程 中， 們 將 我 和 中各 列 的元 素分別 歸 人提 升 集 和非 提 升集 。一旦 將某 一 列組 合 歸人 非 提 升 集