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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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