針對縮減乘積項之二元決策圖變數定序法及其於單電子電晶體陣列面積最小化之應用

Variable ordering of binary decision diagram for product term reduction and its application to area minimization on single electron transistor arrays

陳揚(Chen, Yang)

指導教授 ： 黃俊達

國立交通大學/電機學院/電子工程系所/碩士(2014年)

https://doi.org/10.6842/NCTU.2014.00921

摘要

當製程演進至深次微米技術時，對於現今的電子電路與系統設計而言，功率損耗已經成為一個重要的問題，特別是漏洩功率已經逐漸成為功率消耗的主要來源。近幾年，由於可重構單電子電晶體陣列的超低功率消耗，已經被視為有希望延伸摩爾定律的元件。目前已有很多針對可重構單電子電晶體陣列的自動化映射方法被發展出來。然而，這些方法只專注於乘積項的排序，當他們被應用於實際實作時，這種方式得到的結果可能較無效率。本篇論文將一個在合成階段降低乘積項總數的方法導入單電子電晶體陣列映射中，同時提出兩種可嘗試較多歸約有序二元決策圖變數排列的有效方法，大幅改善各種自動化映射方法的輸出結果。實驗結果顯示，單電子電晶體陣列總面積變為原本的40%，程式總執行時間省去原本的60%。

關鍵字

Single electron transistor ； Single electron transistor array ； Area minimization ； Product term reduction ； Binary decision diagram ； Variable ordering

並列摘要

As fabrication process exploits even deeper submicron technology, power dissipation has become a crucial issue for electronic circuit and system design nowadays. In particular, leakage power is becoming a dominant source of power consumption. In recent years, the reconfigurable single-electron transistor (SET) array has been considered as the promising device for continuing Moore’s Law due to its ultra-low power consumption. Several automated mapping approaches have been developed for the reconfigurable SET array. However, all of these approaches only consider reordering product terms in last stages. When they are applied to real implementation the results could be inefficient. In this thesis, we introduce the approach for reducing the number of product terms into the synthesis phase of SET array mapping and propose two efficient approaches which try more permutations of variable order in the reduced ordered binary decision diagram to improve all kinds of automated mapping approaches. Experimental results show that our proposed approaches can improve the width and runtime up to 40% and 60% respectively as compared to the state-of-the-art approach.

並列關鍵字

單電子電晶體 ； 單電子電晶體陣列 ； 面積最小化 ； 乘積項縮減 ； 二元決策圖 ； 變數定序

參考文獻

[1] International Technology Roadmap for Semiconductor, Semiconductor Industry Association, 2006.

[3] C. Piguet, Low-power CMOS Circuit: Technology, Logic Design and CAD Tools, CRC Press, Nov. 2005.

[4] R. Bryant, “Graph-based Algorithms for Boolean Function Manipulation,” IEEE Trans. Computers, vol.35, pp. 677-691, Aug. 1986.

[5] S. Kasai, M. Yumoto, and H. Hasegawa, “Fabrication of GaAs-based Integrated 2-bit Half and Full Adders by Novel Hexagonal BDD Quantum Circuit Approach,” Proc. Int’l Symp. on Semiconductor Device Research Symposium, pp. 622-625, Dec. 2001.

[6] H. Hasegawa and S. Kasai, “Hexagonal binary decision diagram quantum logic circuits using Schottky in-plane and wrap-gate control of GaAs and InGaAs nanowires,” Physica E: Low-dimensional Systems and Nanostructures, vol. 11, issue 2-3, pp. 149-154, Oct. 2001.