→ ckmarkoh:謝謝老師 老師辛苦了!! 12/26 23:29
原則上，一些 trivial 的 optimization 應該是隨時要處理的，
像是 constant propagation, identical input merging,
redundant wire/gate removal 等等，
所以你在 parse 完電路後可以執行一下以上的動作。
但是我在 spec 上並沒有明確規定，所以這些動作算是 nice to have，
你做了可能可以讓你的電路簡化，以至於讓後來的動作比較有效率，
但沒做應該也不會影響正確性。
此外，你在其他 optimization 動作(strash/fraig)完之後也可以做一下這些操作，
但 again, 這算是你們 implementation 的 flexibility,
我們不會硬性要求一定要做的一模一樣的。
至於我們要怎麼檢查你們的正確性？
我們會準備一些 equivalence checking 的case，如果你們做的正確的話，
整個電路應該會變成 constant 0 (or f xor f)
至於你 hash key 的問題，我想是 OK 的，
不過記得要考慮 phase, permutation, 以及 inversely equivalent 的問題!
這幾天還在忙國科會計畫，已接近尾聲，
明天晚上開始可以 focus 在 ref program 以及 testcases 上了...
※ 引述《ckmarkoh (阿傑)》之銘言：
: ※ 引述《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: 114.36.54.107