改良式重覆相配演算法運用在多常數乘法器上之化簡

Improving Modify IMA perform on MCM’s reduction

林瑋翔(Wei-Hsiang Lin)

指導教授 ： 白宏達

國立臺北大學/電機資訊學院/通訊工程研究所/碩士(2007年)

摘要

在積體電路的設計上,有時會使用到大量的多常數乘法器(Multiple Constant Multiplications)。因此,化簡多常數乘法器就變成一個重要的議題。但在實做上因為運算量過大的關係,一直沒有辦法做到最佳化,只能選擇到次佳解。
重覆相配演算法(Iterative Matching Algorithm)一直是多常數乘法器的常見的化簡方式,是一種次佳解的演算法。這是一種運用經驗法則的方法,並不能保證最佳化。本論文提出預測路徑,計算相配位元組合總量,及多位元比較幾個改進方法,以得到在不同情況之下,更好的改進效果。

關鍵字

重覆相配演算法 ； 多常數乘法器

並列摘要

The design of integrated circuits is often involved with usage of many Multiple Constants Multipliers (MCMs).Therefore, it is very important to reduce the complexity of the MCM. However, the optimal reduction has been very difficult because of the large amount of calculations involved. Several sub-optimal algorithms have been proposed. One of the most popular sub-optimal algorithms is the Iterative Matching Algorithm (IMA).It is derived huristically and acceptable results are obtained under reasonable computational complexity. However, further reduction of the MCM is needed for mobile applications. Three approaches, including Predictive Matching, Total Matchings, and Multi-bit Matching, are proposed to improve the IMA. Simulation results show that these approaches are better than the IMA under most conditions.

並列關鍵字

IMA ； MCM

參考文獻

S.T.J.Fenn, M.Benaissa, and D.Taylor, “Gf(2m) multiplication and division over the

dual basis,” IEEE Transacitons on Computers, vol. 45, pp. 319–327, Mar. 1996.

constant multiplications by shifts and additions using iterative pairwise matching,” in

M. Potkonjak, M.B.Srivastava, and A.P.Chandrakasan, “Multiple constant multiplications:

Efficient and versatile framework and algorithms for exploring common subexpression