作者ric2k1 (Ric)
看板EE_DSnP
标题Re: [情报] ref program (temp)
时间Thu Jan 13 16:29:46 2011
: 推 puerpuella:刚刚测试sim08,不过为什麽fraig完strash会删掉gate? 01/12 23:48
: → puerpuella:可以strash掉的不是会出现在FEC pairs里面? 01/12 23:48
:
: 推 puerpuella:抱歉可能没有说清楚..我的意思是跑了让fraig跑完之後, 01/13 09:09
: → puerpuella:我下strash指令,又有gates被merge掉,可是这些被merge 01/13 09:09
: → puerpuella:的gate不是应该会出现在FEC pair中而被SAT证明? 01/13 09:10
这问题其实有点 tricky... 我观察到的情况是:
某个 FEC group, for example,
[38] 100, 200, 300, 400, 500, 600, 700, 800...
比较特别的是这个 group simulatoin 之後的值是 all 0's,
这种情况很有可能会发生在像是大 AND gates, 它们 output = 1 的机率极低,
而且 simulation 其实对它们没有甚麽监别力。
所以我 ref prog 的作法并不是去检查 N^2 个 FEC pairs,
而是去检查每一个 gate 是否等於 constant 0 (i.e. 去解 SAT(g = 1)).
如果是的话, 我就用 const 0 去 replace 它,
反之如果不是的话,产生出来的 counter example 就足以证明 g != 0,
Either way g 都会被从这个 FEC group 拿掉。
但是被拿掉的 gates 并不保证他们原来不会相等,
因此会有 fraig 做完之後再 strash, 甚至是再 fraig,
仍然会有新的可以 merge 的 pairs.
BTW, fraig 的 runtime 以及 optimization result 是个 trade off,
大家行有余力可以试试看如何 balance, 或是试试看做几次很快的 fraig,
看可不可以达到 runtime 以及 optimization 都比单次比较昂贵的演算法好?
(目前版本的 ref prog 还很阳春...)
欢迎分享心得!!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.21.241