原則上，一些 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