請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/27740
標題: | 質數體上算術數據通路的高階合成 High-Level Synthesis of Finite-Field Arithmetic Circuits Using Abstract Algebra |
作者: | Bing-Yuan Chen 陳炳元 |
指導教授: | 江介宏(Jie-Hong Roland Jiang) |
關鍵字: | 有限體,算術電路,定點數據通路, finite field,arithmetic circuit,fixed-point datapath, |
出版年 : | 2011 |
學位: | 碩士 |
摘要: | 硬體高階合成上,電路數據通路常來表示於多項式定點算術上。有趣的是硬體的資源是有限的,因此電路最佳化是必要的。數據溢出的問題可以使用不同的方式處理,例如,它們使用例外的處理,同餘 (模正整數)等。同餘在於不同的模數利用了不同的代數結構。當我們的模數為2^n,這樣的同餘運算可被視為一個ring。另一方面,若我們的模數為質數時,則這樣的運算可被視為一個field。當前者得到很多的關注和進展時,後者相對沒得到深入的探討。在本論文是有關後者代數結構的數據通路最佳化,並比較兩種不同的代數結構可能的設計空間探索。下列為本論文所完成的結果:
(1)利用團結多項式設計了一個針對單值輸出多項式的簡單化演算。 (2)多值輸出最佳化演算法基於萃取共同表示式。 (3)我們設計了一個降低乘法次數的括號法,使得算術電路所使用的乘法器個數能夠降低。 實驗結果顯示,我們合成過後的面積與Horner Form比平均降低了34.2%,同樣的跟[1]的方法做比較我們的面積平均也小了29.8%。 In high-level hardware synthesis, circuit datapaths are often expressed by polynomials in fixed-point arithmetic. Interestingly the intrinsic boundedness of hardware resources, rather than a limitation, is exploitable for circuit optimization. The data overflow (out-of-bounds) problems can be handled in different ways, for example, treating them using exceptions, congruences (modulo some positive integer), etc. Congruences under di erent moduli impose different algebraic structures. When the modulus is in the form of 2^n for some positive integer n, a polynomial can be seen as a ring. On the other hand, when the modulus is a prime number, a polynomial can be seen as a finite field. While the former received recent attention and progress, the later was relatively not well explored. This thesis is concerned with datapath optimization in the latter algebraic structure, and intends to compare the optimalities under the two di erent algebraic structures for possible design space exploration. The main results include (1) A simplification algorithm for single-output polynomials using unity polynomials. (2) An optimization algorithm for multiple-output polynomials based on common expression extraction. (3) A bracketing method to reduce the number of multiplication operations. Experimental results show that the area generated by our method is averagely 34.2% smaller than the Horner Form. Regarding the comparison with [1], the area is improved by 29.8%. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/27740 |
全文授權: | 有償授權 |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-100-1.pdf 目前未授權公開取用 | 2.24 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。