最小交點式的量子點細胞元自動化布局合成

Abstract

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