質數體上算術數據通路的高階合成

硬體高階合成上，電路數據通路常來表示於多項式定點算術上。有趣的是硬體的資源是有限的，因此電路最佳化是必要的。數據溢出的問題可以使用不同的方式處理，例如，它們使用例外的處理，同餘 (模正整數)等。同餘在於不同的模數利用了不同的代數結構。當我們的模數為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%.

並列關鍵字

finite field ； arithmetic circuit ； fixed-point datapath

參考文獻

[1] A. Peymandoust and G. De Micheli. Application of Symbolic Computer Algebra in High-Level Sata-Flow Synthesis. IEEE Trans. Computer-Aided Design of

Integrated Circuits and Systems, vol. 22, no. 9, pp. 1154-1165, 2003.

[3] David M. Burton. Elementary Number Theory. McGraw-Hill Companies, Inc, 2010.

[5] Finn Haedicke, Bijan Alizadeh, Grschwin Fey, Masahiro Fujita and Rolf Drech-sler. Polynomial Datapath Optimization Using Constraint Solving and Formal Modelling. In Proc. IEEE/ACM International Conference on Computer-Aided

[6] J. E. Eaton. The Fundamental Theorem of Algebra. American Mathematical Monthly, 1960.

國際替代計量

質數體上算術數據通路的高階合成

全文下載

主題瀏覽