推 tomap41017:原PO好威！！我也有最後一個問題 12/26 16:44
※ 引述《ric2k1 (Ric)》之銘言：
: Strash 這個動作把電路中相同 fanin 的 AIG node,
: 像是 f = AND(a, b) 以及 g = AND(b, a) 找出來，然後 merge 在一起，
: 而這裡的 a, b 是 f, g 的直接 fanin, 而非電路的 PIs。
: 直觀的想，你可能會覺得從每一個 gate 去看它的 outputs，
: 再從它的 outputs 去找到相同 fanins 的 gates,
: 但是你可以想想看這樣的複雜度為何?
: 跟用 hash 來檢查哪個比較快?
: BTW, 這裡的 hash 的 key 應該就是每個 gate 的 pair(fanins)。
strash是把fanin相同的gate給merge起來
但是我發現實際上沒有這麼單純
merge完的電路可能會出現以下情形
可以再進一步以boolean operation來化減(不需進行simulation)
1.and gate的兩個input接到相同fanin
這種情形可再化減成一條line -> y = x && x = x
y y
│ │
◢█◣ ═＞ │
│ │ │
└┬┘ │
x x
2.and gate的兩個input接到相同的fanin 但其中一個是inverted
這種情形可再化減成一個const false -> y = x && (!x) = 0
若and的fanout也 inverted 則可化減成const true -> y = ! (x && (!x) )=1
y y
│ │
◢█◣ │
○ │ ═＞ │
└┬┘ const
x false
而做完以上化減後會產生以下連鎖效應
可繼續化減其fanout的電路
例如 y= 1 && x = x
1.
y y
│ │
◢█◣ ═＞ │
∣ ∣ │
const ∣ │
true x x
2. y = 0 && x = 0
y y
│ │
◢█◣ │
∣ ∣ ═＞ │
const ∣ const
false x false
所以strash是除了要把相同fanin的gate給merge起來以外
還能以boolean operation 來化減電路?
我還有個問題
如果要用Hash來存gate的話
HashKey是要把它定義成一對數字嗎?例如:
class HashKey
{
private:
unsigned _iGateID[2];//input gate id
};
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 58.114.204.36