作者gwliao (gwliao)
看板CSSE
标题Re: [讨论] Low Power?
时间Tue Aug 16 04:10:03 2005
※ 引述《jeunder (omega~ oh my god)》之铭言：
: 另外, 在非同步电路也常用到 gray code, 不过考量的重点倒不是在 low power.
不过gray code在Low power的方面真的用的很多,
尤其是Bus encoding方面.
像我之前研究如何re-assign ARM7TDMI的instruction的Conditional Code.
ARM7TDMI的每个instruction前4个bit用於Conditional execution,
4个bit就有16种变化, 那ARM的ISA的assign应该不好 (不然我也没得玩 XD )
我是写了ARM的模拟器, 然後用自己写的简陋C compiler, ARM-cc和gcc compile程式,
再大量跑程式得到这16种code之间的transition probability,
然後建16个node的complete graph(Directed),
graph的edge weight就是他们的probability.
然後找一个path,这个path上的total weight最大(类似解Traveling Salesman Problem)
最後在想办法将gray code放在那些node上,
使得 Σ(weight*两个node之间的switching)为最小.
但所找出来的解不是最佳解!
(找path的时候出问题, 不只是path上的weight要算cost,
连其他degree的weight都有份, 这样单纯的解法不能保证是最佳解)
最後我用ILP(Integer Linear Programming)去找出最佳解!
为何不用branch-and-bound method or 其他的方式?
因为还要再多写一些程式(还要debug) XD
用ILP的话, 只要print一下东西, 再用ILP solver去解就OK了.
(这是做architecture的研究, 重点在re-assign的结果, 不是这部份的演算法 XD )
但结果真的不好, 因为结果是...compiler depend, 真是OOXX Orz
所以我的大学专题就换题目了 :~~~~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.230.224
※ 编辑: gwliao 来自: 140.112.48.60 (08/16 18:34)
1F：推 jeunder:仔细看你的叙述之後, 感觉怪怪的, 怎麽会是找最 61.64.86.25 08/17
2F：→ jeunder:佳路径? 应该是要考虑整个 graph 的加权和才对吧 61.64.86.25 08/17
写了这麽多字, 还是少了一些 Orz
其实你说的方向就是找最佳解的方向,
而我ㄧ开始觉得可以用gray code来一次设定16个node,
那path上的edge的probability必须要很大, 这样才能有好效果,
但事与愿违 :( probability很大的edge有, 但不是呈现bus状, 而是star,
所以想用找path方式就...... Orz 了
当然这是偷吃步的方法, 不能保证是最佳解!
用 0-1-ILP 就可以保证是最佳解.
※ 编辑: gwliao 来自: 140.112.230.224 (08/18 01:39)