[發(fā)明專利]基于局部最小化ROBDD及面積延遲優(yōu)化的工藝映射的方法

有效

• 申請?zhí)枺?/td>: 201410075155.1
• 申請日: 2014-03-04
• 公開（公告）號: CN103885771B
• 公開（公告）日: 2017-05-24
• 發(fā)明（設(shè)計）人: 段振華;李文露;黃伯虎;田聰;張南;王小兵
• 申請（專利權(quán)）人: 西安電子科技大學(xué)
• 主分類號: G06F9/44
• 分類號: G06F9/44
• 代理公司: 北京科億知識產(chǎn)權(quán)代理事務(wù)所(普通合伙)11350
• 代理人: 湯東鳳

1.一種基于局部最小化ROBDD及面積延遲優(yōu)化的工藝映射的方法，其特征在于，該基于局部最小化ROBDD及面積延遲優(yōu)化的工藝映射的方法包括以下步驟：

第一步，刪除電路中的冗余節(jié)點(diǎn)；

第二步，建立BDDpool以隊列的形式存儲將要處理的ROBDD信息，為電路建立局部ROBDD，并且進(jìn)行重排序和化簡后，加入到BDDpool中；利用局部ROBDD表示電路邏輯信息，與傳統(tǒng)的全局ROBDD為電路的原始輸出節(jié)點(diǎn)PO建立ROBDD相比，局部ROBDD為電路中的每一個節(jié)點(diǎn)包括PO和中間節(jié)點(diǎn)建立一個ROBDD，減小了電路分解的時間和內(nèi)存消耗；

第三步，將BDDpool中的所有ROBDD分解到最小化；包括以下步驟：

步驟一，從BDDpool中取出一個ROBDD，如果是最小化ROBDD，也就是ROBDD的節(jié)點(diǎn)數(shù)為2，則執(zhí)行步驟二，否則執(zhí)行步驟三；

步驟二，將該ROBDD加到BDDpool的隊尾，如果所有ROBDD都為最小化，則邏輯優(yōu)化結(jié)束，否則執(zhí)行步驟一；

步驟三，判斷該ROBDD中是否存在代數(shù)域節(jié)點(diǎn)，如果存在則執(zhí)行步驟四，否則執(zhí)行步驟五；

步驟四，如果存在1-dominator則將ROBDD分解為兩個ROBDD的合取；如果存在0-dominator則分解為兩個ROBDD的析取，如果存在x-dominator則分解為兩個ROBDD的同或，將分解后的ROBDD都加入到BDDpool中，執(zhí)行步驟一；

步驟五，對ROBDD進(jìn)行布爾域分解，將分解后的ROBDD加入到BDDpool中，執(zhí)行步驟一；

第四步，用有向無環(huán)圖DAG表示電路結(jié)構(gòu)；

第五步，按照從原始輸入到原始輸出的拓?fù)漤樞蜻M(jìn)行節(jié)點(diǎn)標(biāo)記；節(jié)點(diǎn)標(biāo)記過程，包括以下步驟：

(1)，增加源節(jié)點(diǎn)s連接所有的PI，PI為電路的原始輸入，初始化集合L＝{PI}，所有的PI節(jié)點(diǎn)標(biāo)記值賦為0；

(2)，從L中選取一個節(jié)點(diǎn)t，首先求節(jié)點(diǎn)t的花費(fèi)cost，cost(t)＝weight(t)/node_num_fanout(t)，其中weight(t)為節(jié)點(diǎn)t的權(quán)重，默認(rèn)為1，node_num_fanout(t)為節(jié)點(diǎn)t的扇出節(jié)點(diǎn)個數(shù)；

(3)，將節(jié)點(diǎn)t及其所有前驅(qū)節(jié)點(diǎn)構(gòu)造為網(wǎng)絡(luò)Nt，計算網(wǎng)絡(luò)Nt中所有滿足LUT對輸入個數(shù)K約束要求的劃分中，X中所有節(jié)點(diǎn)的cost的總和，選出其中最小的記為min-cost劃分；

(4)，設(shè)p為Nt中節(jié)點(diǎn)的最大標(biāo)記，將Nt中所有標(biāo)記等于p的節(jié)點(diǎn)都合并到t中得到新的節(jié)點(diǎn)t’，將該網(wǎng)絡(luò)記為Nt’；

(5)，將網(wǎng)絡(luò)Nt’中，除了s和t’外的所有節(jié)點(diǎn)，分裂成兩個節(jié)點(diǎn)，分裂邊的權(quán)值設(shè)為1，原有邊的權(quán)值設(shè)為∞，將該網(wǎng)絡(luò)記為Nt”，根據(jù)最大流最小割定理，判斷Nt”網(wǎng)絡(luò)中的最大流是否小于等于K，如果是，則節(jié)點(diǎn)t的標(biāo)記為p，否則為p+1；

(6)，如果滿足節(jié)點(diǎn)t標(biāo)記的劃分有兩個或兩個以上，則按照(2)的方法計算最小cost的劃分，記為min-height min-cost劃分，如果只有一個這樣的劃分，則直接記為min-height min-cost劃分；

(7)，更新集合L，L＝(L-{t})∪{node_fanout(t)}，node_fanout(t)為節(jié)點(diǎn)t的扇出節(jié)點(diǎn)集合，判斷L是否為空，如果不為空，則跳至(2)，否則，節(jié)點(diǎn)標(biāo)記過程結(jié)束；

第六步，按照從原始輸出到原始輸入的拓?fù)漤樞蛴貌檎冶鞮UT對電路進(jìn)行覆蓋；查找表LUT覆蓋過程，包括以下步驟：

1)，令集合L＝{PO}，PO為電路的原始輸出；

2)，從集合L中取出一個節(jié)點(diǎn)v，判斷節(jié)點(diǎn)v是否在關(guān)鍵路徑上，如果在則進(jìn)行min-height min-cost覆蓋，否則進(jìn)行min-cost覆蓋；生成新的節(jié)點(diǎn)v’來表示覆蓋后的LUT節(jié)點(diǎn)；

3)，更新集合L，令L＝(L-{v})∪input(v’)，判斷L中是否所有節(jié)點(diǎn)都為PI，若是則結(jié)束覆蓋過程，否則跳至1)；

第七步，進(jìn)一步的面積優(yōu)化。

2.如權(quán)利要求1所述的基于局部最小化ROBDD及面積延遲優(yōu)化的工藝映射的方法，其特征在于，第七步，進(jìn)一步面積優(yōu)化過程，包括以下步驟：

步驟一，按拓?fù)漤樞虮闅v網(wǎng)絡(luò)，判斷是否存在下述情況，K-LUT v有且只有一個輸出K-LUT u，并且|{input({u,v})}|≤K，如果存在，將v合并到u中；

步驟二，按拓?fù)漤樞虮闅v網(wǎng)絡(luò)，判斷是否存在下述情況，兩個節(jié)點(diǎn)K-LUT v和K-LUT u都只有一個輸出節(jié)點(diǎn)且輸出節(jié)點(diǎn)都是K-LUT w，并且|{input({u,v})}|≤K,如果存在，將v和u合并為一個只有一個輸出為K-LUT w的K-LUT。