臺灣博碩士論文加值系統

Rewiring is a well developed and widely used technique in the synthesis and optimization of traditional Boolean logic designs. The threshold logic is a new alternative logic representation to Boolean logic which poses a compactness characteristic of representation. Nowadays, with the advances in nanomaterials, research on multi-level synthesis, verification, and testing for threshold networks is flourishing. This paper presents an algorithm for rewiring in a threshold network. It works by rst removing a target wire, and then corrects circuit's functionality by adding a corresponding rectication network. It also proposes a simplication procedure for representing a threshold logic gate canonically, an important property of functional verication. The experimental results show that our approach enables the
logic restructuring of threshold logic networks. Additionally, our approach has 7.1 times speedup compared to the-state-of-the-art multi-level synthesis algorithm, in synthesizing a threshold network with a new fanin number constraint.

重接線已高度發展並廣泛地被運用在傳統布林邏輯設計上的合成與最佳化；臨界邏輯，相較於布林邏輯擁有較精簡的特性，是一種新的邏輯表示方式。現今，伴隨著奈米材料技術的演進，臨界邏輯上的研究，包含多層合成、驗證與測試，皆蓬勃發展。這篇論文提出了一個實作在臨界邏輯電路的重接線演算法，藉由移除一個目標線，並加上相對應的改正網路來修正電路的功能性；同時使一個臨界邏輯閘以標準型態表示的簡化程序也被提出，標準表示也是功能性驗證的一重要性質。實驗結果展現了此演算法實作在臨界邏輯電路上的邏輯重建能力；除此之外，在合成一個具有新輸入端數目限制的臨界網路，相較於最先進的臨界邏輯合成演算法，我們提出的方法加快了7.1倍的速度。

書名頁
中文摘要
Abstract
Acknowledgements
Contents
List of Tables
List of Figures
1 Introduction
2 An example for rewiring
3 Preliminaries
3.1 Threshold logic
3.2 Positive-Negative weight transformation
4 Rewiring for the threshold network
4.1 Overview
4.2 Input grouping and gate decomposition
4.3 Target wire removal
4.4 Rectication network construction
5 Simplication
5.1 Simplication flow
5.2 Functional equivalence
5.3 Weight and threshold value decreasing
5.4 An example for the simplication flow
6 Experimental results
7 Conclusion and future work
References
Publications

[1] M. J. Avedillo and J. M. Quintanaa, "A Threshold Logic Synthesis Tool for RTD Circuits," in Proc. European Symp. on Digital System Design, Sep. 2004, pp. 624-627.
[2] M. J. Avedillo, J. M. Quintana, H. Pettenghi, P. M. Kelly, and C. J. Thompson, "Multi-Threshold Threshold Logic Circuit Design Using Resonant Tunnelling Devices," Electron. Lett., vol. 39, no. 21, Oct. 2003, pp 1502-1504.
[3] M. J. Avedillo, J. M. Quintana, A. Rueda, and E. JimCnez, "Low-Power CMOS Threshold-Logic Gate," Electron. Lett., vol. 31, no. 35, Dec. 1995, pp. 2157-2159.
[4] V. Beiu, J. M. Quintana, and M. J. Avedillo, "VLSI Implementations of Threshold Logic-a Comprehensive Survey," in Tutorial at Int. Joint Conf. Neural Networks, 2003.
[5] Berkeley Logic Synthesis and Verication Group, "SIS: Synthesis of both synchronous and asynchronous sequential circuits," http://embedded.eecs.berkeley.edu/pubs/downloads/sis
[6] P. Celinski, J. F. Lopez, S. Al-Sarawi, and D. Abbott, "Low Power, High Speed, Charge Recycling CMOS Threshold Logic Gate," Electron. Lett., vol. 37, Aug. 2001, pp. 1067-1069.
[7] S.-C. Chang, K.-T. Cheng, N.-S Woo, and M. Marek-Sadowska, "Postlayout Logic Restructuring Using Alternative Wires," IEEE Trans. Computer-Aided Design, vol. 16, pp. 587-596, June 1997.
[8] S.-C. Chang, M. Marek-Sadowska, and K.-T. Cheng, "Perturb and Simplify: Multi-level Boolean Network Optimizer," IEEE Trans. Computer-Aided Design, vol. 15, pp. 1494-1504, Dec. 1996.
[9] S.-C. Chang, L. P. P. P. Van Ginneken, and M. Marek-Sadowska, "Fast Boolean Optimization by Rewiring," in Proc. Int. Conf. Computer-Aided Design, 1996, pp. 262-269.
[10] C.-W. Jim Chang, M.-F. Hsiao, and M. Marek-Sadowska, "A New Reasoning Scheme for Ecient Redundancy Addition and Removal," IEEE Trans. Computer-Aided Design, vol. 22, pp. 945-952, July 2003.
[11] K. J. Chen, K. Maezawa, and M. Yamamoto, "InP-Based High-Performance Monostable-Bistable Transition Logic Elements (MOBILE's) Using Integrated Multiple-Input Resonant-Tunneling Devices," IEEE Eletron Device Letters, vol.17, pp.127-129, Mar. 1996.
[12] Y.-C. Chen and C.-Y. Wang, "An Improved Approach for Alternative Wires Identication," in Proc. Int. Conf. Computer Design, 2005, pp. 711-716.
[13] Y.-C. Chen and C.-Y. Wang, "Fast Detection of Node Mergers Using Logic Implications," in Proc. Int. Conf. on Computer-Aided Design, 2009, pp. 785-788.
[14] Y.-C. Chen and C.-Y. Wang, "Node Addition and Removal in the Presence of Don't Cares," in Proc. Design Automation Conf., 2010, pp. 505-510.
[15] Y.-C. Chen and C.-Y. Wang, "Fast Node Merging With Don't Cares Using Logic Implications," IEEE Trans. Computer-Aided Design, vol. 29, pp. 1827-1832, Nov. 2010.
[16] M. L. Dertouzos, "Threshold Logic: A Synthesis Approach". Cambridge, MA: M.I.T. Press, 1965.
[17] S.-C. Fu, T.-K. Lam, and Y.-L. Wu, "Improved Scheme for Digital Circuit Rewiring and Application on Further Improving FPGA Technology Mapping," in Proc. Asia and South Pacic Design Automation Conf., 2009, pp. 197-202.
[18] D. Goldharber-Gordon, M. S. Montemerlo, J. C. Love, G. J. Opiteck, and J. C. Ellenbogen. "Overview of Nanoelectronic Devices," in Proc IEEE, vol. 85, no.4, pp. 521-540, Jan. 1997.
[19] T. Gowda and S. Vrudhula, "Decomposition Based Approach for Synthesis of Multi-Level Threshold Logic Circuits," in Proc. Asia and South Pacic Design Automation Conf., 2008, pp. 125-130.
[20] T. Gowda, S. Vrudhula, and G. Konjevod, "A Non-ILP Based Threshold Logic Synthesis Methodology," in Proc. International Workshop on Logic and Synthesis, 2007, pp. 222-229.
[21] T. Gowda, S. Vrudhula, and G. Konjevod, "Combinational Equivalence Checking for Threshold Logic Circuits," in Proc. Great Lake Symp. VLSI, March 2007, pp. 102-107.
[22] P. Gupta, R. Zhang, and N. K. Jha, "Automatic Test Generation for Combinational Threshold Logic Networks," IEEE Trans. Computer-Aided Design, vol.16, pp.1035-1045, Aug. 2008.
[23] Z. Kohavi, "Switching and Finite Automata Theory". New York, NY: McGraw-Hill, 1978.
[24] C. Lageweg, S. Cotofana, and S. Vassiliadis, "A Linear Threshold Gate Implementation in Single Electron Technology," in Proc. IEEE Coput. Soc. Workshop VLSI, 2001, pp. 93-98.
[25] C.-C. Lin and C.-Y. Wang, "Rewiring Using IRredundancy Removal and Addition," in Proc. Design, Automation and Test in Europe, 2009, pp. 324-327.
[26] W.-H. Lo and Y.-L. Wu, "Improving Single-Pass Redundancy Addition and Removal with Inconsistent Assignments," in Proc. Int. Symp. on VLSI Design, Automation and Test, 2006, pp. 175-178.
[27] S. Muroga, "Threshold Logic and its Applications". New York, NY: John Wiley, 1971.
[28] A. Mishchenko, S. Chatterjee, and R. Brayton, "DAG-Aware AIG Rewriting: A Fresh Look at Combinational Logic Synthesis," in Proc. Design Automation Conf., 2006, pp. 532-536.
[29] K. Maezawa, H. Matsuzaki, M. Yamamoto, and T. Otsuji, "High-Speed and Low-Power Operation of A Resonant Tunneling Logic Gate MOBILE," IEEE Eletron Device Letters, vol. 19, pp.80-82, March 1998.
[30] C. Pacha, P. Glosekotter, K. Goser, W. Prost, U. Auer, and F. Tegude, "Resonant Tunneling Device Logic Circuit," Dortmund/Gerhard-Mercator University of Duisburg, Germany, Tech. Rep., July 1999.
[31] M. Perkowski and A. Mishchenko, "Logic Synthesis for Regular Fabric Realized in Quantum Dot Cellular Automata," in Proc. Int. J. Multiple-Valued Logic and Soft Comput., 2004, pp. 768-773.
[32] S. Plaza, K. H. Chang, I. Markov, and V. Bertacco, "Node Mergers in the Presence of Don't Cares," in Proc. Asia and South Pacic Design Automation Conf., 2007, pp. 414-419.
[33] G. E. Sobelman and K.Fant, "CMOS Circuit Design of Threshold Gates with Hysteresis," in Proc. Int. Conf. on Circuits and Systems, vol. 2, 1998, pp. 61-64.
[34] W.-C. Tang, W.-H. Lo, T.-K. Lam, K.-K. Mok, C.-K. Ho, S.-H. Yeung, H.-B. Fan, and Y.-L. Wu, "A Quantitative Comparison and Analysis on Rewiring Techniques," in Proc. Int. Conf. on ASIC, 2003, pp. 242-245.
[35] A. Veneris and M. S. Abadir, "Design Rewiring Using ATPG," IEEE Trans. Computer-Aided Design, vol. 21, pp. 1469-1479, Dec. 2002.
[36] R. O. Winder, "Threshold Logic." Ph.D. dissertation, Princeton University, Princeton, NJ, 1962.
[37] Y.-L.Wu, W.-N. Long, and H.-B. Fan, "A Fast Graph-based Alternative Wiring Scheme for Boolean Networks," in Proc. Int. VLSI Design Conf., 2000, pp. 268-273.
[38] X.-Q. Yang, T.-K. Lam, and Y.-L. Wu, "ECR:A Low Complexity Generalized Error Cancellation Rewiring Scheme," in Proc. Design Automation Conf., 2010, pp. 511-516.
[39] R. Zhang, P. Gupta, L. Zhong, and N. K. Jha, "Synthesis and Optimization of Threshold Logic Networks with Application to Nanotechnologies," in Proc. Design Automation Test in Europe Conf., 2004, pp. 904-909.
[40] Y. Zheng, M. S. Hsiao, and C. Huang, "SAT-based Equivalence Checking of Threshold Logic Designs for Nanotechnologies," in Proc. Great Lake Symp.
VLSI, May 2008, pp. 225-230.
[41] Q. Zhu, N. Kitchen, A. Kuehlmann, and A. Sangiovanni-Vincentelli, "SAT Sweeping with Local Observability Don't Cares," in Proc. Design Automation Conf., 2006, pp. 229-234.
[42] http://iwls.org/iwls2005/benchmarks.html