Re: [討論] Low Power?

[gwliao (gwliao)]

※ 引述《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)
推 jeunder:仔細看你的敘述之後, 感覺怪怪的, 怎麼會是找最
→ jeunder:佳路徑? 應該是要考慮整個 graph 的加權和才對吧
寫了這麼多字, 還是少了一些  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)