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