姓名 |
鄭立程(Li-Cheng Zheng)
查詢紙本館藏 |
畢業系所 |
電機工程學系 |
論文名稱 |
以引導式二階權重提取改進辨認二階臨界函數之 研究 (Improved 2nd-order Threshold Function Identification with Guided 2-weight Extraction)
|
相關論文 | |
檔案 |
[Endnote RIS 格式]
[Bibtex 格式]
[相關文章] [文章引用] [完整記錄] [館藏目錄] [檢視] [下載]- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。
|
摘要(中) |
隨著近年來先進製程的演進,帶來了運算能力更強大且面積更小的電路。由於臨界邏輯 (Threshold Logic) 的運作行為容 易使用先進 的奈米級元件 實現,例如: Resonant Tunneling Diodes (RTD)、Quantum Cellular Automata (QCA)、Single-electron
Tunneling (SET) 和 Tunneling Phase Logic (TPL)。因此有許多研究者對臨界邏輯的潛力感到興趣。如何開發一個能夠在布林邏輯 (Boolean Logic) 與臨界邏輯間快速且有效地轉換方法,變成一個需要被解決的問題。
在本篇論文中,我們開發了一個考慮引導式二階權重提取,進而改進傳統基於整數線性規劃辨認二階臨界函數的方法。我們主要提出了一個有效的啟發,透過三個充分條件辨認出不同型態的二階權重提取方式,用以舉出所有可能被提取出的二階權重。與純粹基於整數線性規劃的方法相比,本論文的方法分別在 TLNK6 的實驗中,減少花費了 6.64% 的時間同時具有 99.31% 的相當質量;在 TLNK15 的實驗中,減少花費
了 32.88% 的時間同時具有 95.51% 相當的質量。此外,與純粹基於整數線性規劃的方法相比,在 k-input-TFs 的實驗中,所提出的方法也減少花費了 24.23% 的時間同時具有94.74% 相當的質量。 |
摘要(英) |
In recent years, the advances of emerging technologies bring more computational power and compact circuits. Since Threshold Logic has the behavior that can be easily implemented with emerging nanoscale devices, such as Resonant Tunneling Diodes (RTD), Quantum Cellular Automata (QCA), Single-electron Tunneling (SET) and Tunneling Phase Logic (TPL), many researchers are attracted by the potential of Threshold Logic. Therefore, how to develop a fast and effective method for the translation between Threshold Logic and Boolean Logic becomes a problem needs to be solved.
In this thesis, we improve the conventional ILP-based method for identifying 2nd-order Threshold Function with guided 2-weight extraction. We propose an effective heuristic, which contains three sufficient conditions that can identify different types of 2-weight extractions, to enumerate possibly extracted 2-weights. In the experiments of TLNK6 and TLNK15, the proposed method saves 6.64% and 32.88% of ILP solving time, and has 99.31% and 95.51% of quality compared to the pure ILP-based method, respectively. Furthermore, in contrast to the pure ILP-based method, the experimental results of k-input-TFs show that our method also saves 24.23% of ILP solving time and has 94.74% of quality. |
關鍵字(中) |
★ 邏輯合成 ★ 邏輯最佳化 ★ 臨界邏輯 ★ 一階臨界函數辨認 ★ 二階臨界函數辨認 |
關鍵字(英) |
★ Logic Synthesis ★ Logic Optimization ★ Threshold Logic ★ 1st-Order Threshold Function Identification ★ 2nd-Order Threshold Function Identification |
論文目次 |
摘要 - i
Abstract - ii
Acknowledgement - iii
Table of Contents - iv
List of Figures - vi
List of Tables - vii
1 Introduction - 1
1.1 Threshold Logic - 1
1.2 1st-order Threhold Logic Gate - 1
1.3 2nd-order Threhold Logic Gate - 2
1.4 Related Works - 3
1.5 Main Contributions - 4
2 Background - 6
2.1 Current-mode-based Hardware Implementation for 2-TLG - 6
2.2 ILP-based 1-TF and 2-TF Identification - 8
3 Motivation - 12
3.1 Difficulty of 2-TLN Synthesis - 12
3.2 Limitation of ILP-based Exact Method for 2-TF Identification - 13
3.3 Intention - 14
4 Proposed Method - 15
4.1 Extraction Process - 15
4.1.1 All Elimination Extraction - 16
4.1.2 Partial Elimination Extraction - 18
4.1.3 No Elimination Extraction - 20
4.2 Guided ILP-based Weight Assignment - 22
5 Experimental Results - 25
5.1 Setup - 25
5.2 k-input-TFs - 26
5.3 TLNK6 - 29
5.4 TLNK15 - 33
6 Conclusions - 37
References - 38
Appendix A - 39 |
參考文獻 |
[1] C. Wang and A. C. Williams. The threshold order of a boolean function. Discrete Applied Mathematics, 31:51–69, 1991.
[2] A. Neutzling et al. A simple and effective heuristic method for threshold logic identification. IEEE Trans. Computer-Aided Design, 37:1023–1036, Jul. 2017.
[3] C.-H. Liu et al. Threshold function identification by redundancy removal and comprehensive weight assignments. IEEE Trans. on Computer-Aided Design, Early Access, 2018.
[4] A. Neutzling et al. Effective logic synthesis for threshold logic circuit design. IEEE Trans. Computer-Aided Design, 38:926–937, May 2019.
[5] N.-Z. Lee et al. Analytic approaches to the collapse operation and equivalence verification of threshold logic circuits. In Proc. Int. Conf. on Computer-Aided Design, pages 1–8, 2016.
[6] S. Bobba and I. N. Hajj. Current-mode threshold logic gates. Proceedings of the International Conference on Computer Design, pages 235–240, 2000.
[7] S. N. Mozaffari et al. A new method to identify threshold logic functions. Design, Automation and Test in Europe (DATE), March 2017.
[8] L.-C. Zheng, Y.-C. Chen, and J.-Y. Jou. An effective heuristic for 1st- to 2nd-order threshold logic gate transformation. VLSI Design/CAD symposium, Taiwan, 2019.
[9] R. Zhang et al. Threshold network synthesis and optimization and its application to nanotechnologies. IEEE Trans. Computer-Aided Design (TCAD), 24:107–118, 2005.
[10] A. Phillips and S. Mitchell. pulp. https://pypi.org/project/PuLP-py3/, 2013. |
指導教授 |
周景揚(Jing-Yang Jou)
|
審核日期 |
2020-8-5 |
推文 |
facebook plurk twitter funp google live udn HD myshare reddit netvibes friend youpush delicious baidu
|
網路書籤 |
Google bookmarks del.icio.us hemidemi myshare
|