臺灣博碩士論文加值系統

量子點細胞元自動化是一種新式奈米層級上的計算機制，它可以利用在分子上電子的表面配置來表示二元資訊。一個量子點細胞元自動化實體設計流程包含了四個步驟：切割、布置、接頭分派以及隧道繞路。因為在量子點細胞元自動化布局上的線路交點數目會嚴重影響整個量子點細胞元自動化布局設計的複雜度，這篇論文的重點將放在減少線路交點的佈局合成。在這篇論文裡，量子點細胞元自動化布局裡的布置問題將會映射到一個有名的問題「多層雙向圖交點最小化」。而為了解這個問題，我們提出了一個新的啟發示教育法。接頭分派這個步驟在隧道繞路之前，其用途是為了提供一個合法的接頭分派方式以便接下來的隧道繞路可以無礙的完成。最後，在隧道繞路這個步驟裡將提出一個名為『打破循環』的演算法，同樣是為了減少布局上的交點。基於我們的實驗數據，在布置和隧道繞路這些步驟裡，交點都有顯著的減少程度。我們利用量子點細胞元自動化設計者2.0.3來模擬驗證我們合成出來的布局線路。在我們的實驗裡，有一些標準線路已經驗證無誤，但有一些標準線路因為硬體的限制而無法驗證完成。

Quantum-dot cellular automata (QCA) is a novel nano-scale computing mechanism that can represent binary information based on spatial distribution of electron charge configuration in molecules. A QCA physical synthesis flow consists of four stages: partitioning, placement, pin-assignment and channel routing. Because wire crossings in QCA layout increase the complexity of circuit layout design, this work focus on minimizing wire crossings of the circuit under synthesis. In this paper, the problem of QCA placement is mapped to a famous problem “k-layer bigraph crossing problem” and a new heuristic is developed for this problem. Pin assignment stage is prior to channel routing stage, which provides a legal pin assignment for the following channel routing stage. Finally, a new cycle breaking algorithm to reduce wire crossings in channel routing stage is presented. Based on our experimental results, placement and cycle breaking obtain good crossing reduction. We also simulate our circuit by QCA Design 2.0.3 and obtain correct simulation result and other benchmark circuits does not have simulation result since they are too large to complete simulation in time.

Abstract (in Chinese)………………………………………………………….……….I
Abstract(in English)………………………...................................................................II
Acknowledgements…………………………………………………………………..III
List of Figures………………………………………………………………………..VI
List of Tables………………………………………………………………………...VII
1 Introduction ……………………………………………………………………...1
2 Preliminary….........................................................................................................4
2.1 QCA basic……................................................................................................4
2.2 QCA logic devices……………………………………………………………5
2.3 The QCA clocking………………………………………………...………….8
2.4 The timing rule……………………………………………………………...10
3 Problem Formulation……………………………………………………...……11
3.1 Synthesis model……………………………………………………………..11
3.2 Problem formulation of partitioning………………………………………..12
3.3 Problem formulation of placement……………………………….................13
3.4 Problem formulation of pin assignment…... ……………………………….13
3.3 Problem formulation of channel routing…... ………………………………13
4 Algorithm………………………………………………………………………….14
4.1 Partitioning………………………………………………………………….14
4.2 Placement……………...…………………………………………………....18
4.2.1 Guided breadth-first search……………………………………………….18
4.2.2 Multilevel guided breadth-first search……………………………………19
4.2.3 Adaptive insertion method………………………………………………..23
4.3 Pin assignment………………………………………………………………26
4.3.1 Greedy pin assignment……………………………………………………26
4.3.2 Pseudo routing…………………………………………………………….28
4.4 Channel Routing…………………………………………………………….28
4.4.1 Overview………………………………………………………………….28
4.4.2 Doglegging………………………………………………………………..29
4.4.3 Crossing edge insertion…………………………………………………...29
4.4.4 Cycle break………………………………………………………………..30
5 Experimental Result………………………………………………………………34
6 Conclusions………………………………………………………………………42
Bibliography………………………………………………………………………...43

[1] Craig S.Lent, P. Douglas Tougaw, and Wolfgang Porod. “Quantum Cellular Automata.” Nanotechnology 4, 49 , 1993.
[2] Michael T. Niemier. “Designing Digital Systems in Quantum Cellular Automata.” MS CSE Thesis, University of Notre Dame, 2000.
[3] Michael T. Niemier and Peter M. Kogge. “Exploring and Exploiting Wire-Level Pipelining in Emerging Technologies.” ISCA, 2001.
[4] Islamshah Amlani, Alexei O.Orlov, Geza Toth, Gary H. Bernstein, Craig S. Lent, Gregory L. Snider. “Digital Logic Gate Using Quantum-Dot Cellular Automata”. Science Vol 284 pp. 289 – 29, 1999.
[5] Gary H. Bernstein, “Quantum-dot cellular automata: computing by field polarization”, Proceedings of the 40th conference on Design automation, 2003.
[6] A.O.Orlov I. Amlani, G.H. Bernstein, C.S. Lent, and G.L. Snider, “Realization of a Functional Cell for Quantum-Dot Cellular Automata”, Science Vol. 277, pp. 928, 1997.
[7] G. L. Snider , A.O. Orlov, I. Amlani, X. Zuo, G. H. Bernstein, C. S. Lent, J. L. Merz, W. Porod, “Quantum-dot cellular automata: Review and recent experiments” , Journal of Applied Physics , Vol. 85, No. 8, pp. 4283-4285 , 1999.
[8] Tougaw, P. Douglas; Lent, Craig S.” Logical devices implemented using quantum cellular automata”. Journal: Journal of Applied Physics, Volume75, Issue 3, pp.1818-1825, 1994.
[9] D. Berzon, T.Fountain , “Computer Memory Structures using QCAs”, Report No.98/1.
[10] Dominic A. Antonelli, Danny Z. Chen, Timothy J. Dysart, Xiaobo S. Hu, Andrew B. Kahng, Peter M. Kogge, Richard C. Murphy, Michael T. Niemier “New ideas in placement: Quantum-Dot Cellular Automata (QCA) circuit partitioning: problem modeling and solutions” Proceedings of the 41st annual conference on Design automation , 2004.
[11] Yih Lang Li and Cheng Wen Wu, “Cellular Automata for Efficient Parallel Logic and Fault Simulation ," IEEE Trans. Computer-Aided Design, Vol. 14, no. 6, pp. 740-749, 1995.
[12] J. Nguyen, R. Ravichandran, S.K. Lim, M. Niemier , “Global placement for quantum-dot cellular automata based circuits” Technical Report GIT-CERCS-03-20, Georgia Institute of Technology ,2003.
[13] Ramprasad Ravichandran, Sung Kyu Lim, Mike Niemier , “Automatic cell placement for quantum-dot cellular automata” INTEGRATION , the VLSI journal , pp. 541-548, 2005.
[14] Brian Stephen Smith, Sung Kyu Lim “QCA channel routing with wire crossing
minimization.” ACM Great Lakes Symposium on VLSI, pp. 217-220 , 2005.
[15] Ramprasad Ravichandran, Mike Niemier, “Eliminating Wire Crossings for Molecular Quantum-dot Cellular Automata Implementation.” ICCAD 2005
[16] Eade, P. and Whiteside S. “Drawing graphs in two layers.” Theoretical Computer Science 131, pp.361-374, 1994
[17] Matusewski, C. Schonfeld , R., and Molitor, P. “Using sifting for k-layer straightline crossing minimization” Proc. 7th Graph Drawing Conference , Number 1731 in LNCS , pp.217-224, 1999.
[18] Schonfeld, R., Gunter, W., Becker, B., and Molitor, P. “K-layer straightline crossing minimization by soeeding up shifting.” Proc. 8th Graph Drawing Conference, Number 1984 in LNCS, pp.253-258, 2000.
[19] Matthias Stallmann, Franc Brglez, Debabrata Ghosh, “Heuristics, Experimental Subjects, and Treatment Evaluation in Bigraph Crossing Minimization”, Journal of Experimental Algorithmics , 2001.
[20] Kernighan, B. W. and Lin, S. “An efficient heuristic procedure for partitioning graphs.” Bell System Technical Journal, pp. 291-307, 1970.
[21] Walus, K.; Dysart, T.J.; Jullien, G.A.; Budiman, R.A. “QCADesigner: a rapid design and Simulation tool for quantum-dot cellular automata”, Nanotechnology, IEEE Transactions on Volume 3, Issue 1, pp.26 – 31 , 2004.
[22] G. Toth, "Correlation and coherence in quantum-dot cellular automata", Ph.D. Thesis, University of Notre Dame, pp. 56-63, 2000.
[23] A. Gin, P. D. Tougaw, and S. Williams. “An alternative geometry for quantum-dot cellular automata”. J. Appl. Phys., 85(12):8281–8286, 1999.