邏輯綜合中工藝映射的研究.pdf

1、邏輯綜合是數(shù)字電路設(shè)計(jì)中極為重要的環(huán)節(jié),而工藝映射是完成這個(gè)環(huán)節(jié)最為重要的一步.該文對以下幾方面進(jìn)行了研究:1、以往,檢測變量對稱通過判斷兩個(gè)相關(guān)布爾函數(shù)的BDD圖是否同構(gòu).我們提出一種算法,檢測變量對稱與否只需建立一個(gè)BDD.而且同構(gòu)的比較只是局部BDD互相比較,由于BDD圖的大小和變量數(shù)呈指數(shù)關(guān)系,所以算法具有時(shí)間復(fù)雜度和空間復(fù)雜度兩方面的優(yōu)勢.2、另外,過去的匹配算法往往只考慮單個(gè)變量的標(biāo)簽,單個(gè)變量和其他變量的組合標(biāo)簽.但是,變

2、量組之間的關(guān)系并沒有被充分考慮.根據(jù)BDD結(jié)構(gòu)獨(dú)特的性質(zhì),我們發(fā)現(xiàn)特征BDD子圖不僅能充分反映待區(qū)分變量信息,而且能體現(xiàn)出變量組之間的對應(yīng)關(guān)系.通過特征BDD子圖,能方便得到有價(jià)值的變量標(biāo)簽.3、BDD是表示、操作布爾代數(shù)的一種有效方式.變量對稱檢測、布爾函數(shù)匹配和形式驗(yàn)證等算法都需要用到BDD.這樣,BDD的大小和這些算法執(zhí)行時(shí)間呈正比,而BDD的大小和變量序直接相關(guān).該文針對對稱變量的特性,找出另外幾種有利于縮減BDD的變量關(guān)系.在

3、此基礎(chǔ)上,進(jìn)一步對變量組分析、重組,最終得到變量序.該文算法執(zhí)行結(jié)果良好,并且和BDD初始變量序沒有關(guān)系,是一種穩(wěn)定的算法.4、雙態(tài)覆蓋(Binate Covering)被首先用于減少有限狀態(tài)機(jī)(FSM)中狀態(tài)數(shù),由于占用內(nèi)存很大,運(yùn)行時(shí)間長沒有得到充分的重視.該文詳細(xì)論述了雙態(tài)覆蓋的特點(diǎn)及其在工藝映射中的應(yīng)用,并針對電路進(jìn)行初步實(shí)現(xiàn).針對調(diào)整門的大小,論文討論了如何提取關(guān)鍵路徑,使得優(yōu)化更具有準(zhǔn)確性.作者博士論文以布爾匹配為中心,嘗試