标题: 最小交点式的量子点细胞元自动化布局合成
Minimum-Crossing Layout Synthesis for Quantum-Dot Cellular Automata (QCA)
作者: 赖建丞
李毅郎
资讯科学与工程研究所
关键字: 量子点细胞元自动化;Quantum-Dot Cellular Automata
公开日期: 2005
摘要: 量子点细胞元自动化是一种新式奈米层级上的计算机制,它可以利用在分子上电子的表面配置来表示二元资讯。一个量子点细胞元自动化实体设计流程包含了四个步骤:切割、布置、接头分派以及隧道绕路。因为在量子点细胞元自动化布局上的线路交点数目会严重影响整个量子点细胞元自动化布局设计的复杂度,这篇论文的重点将放在减少线路交点的布局合成。在这篇论文里,量子点细胞元自动化布局里的布置问题将会映射到一个有名的问题“多层双向图交点最小化”。而为了解这个问题,我们提出了一个新的启发示教育法。接头分派这个步骤在隧道绕路之前,其用途是为了提供一个合法的接头分派方式以便接下来的隧道绕路可以无碍的完成。最后,在隧道绕路这个步骤里将提出一个名为‘打破循环’的演算法,同样是为了减少布局上的交点。基于我们的实验数据,在布置和隧道绕路这些步骤里,交点都有显着的减少程度。我们利用量子点细胞元自动化设计者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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT009223593
http://hdl.handle.net/11536/76644
显示于类别:Thesis


文件中的档案:

  1. 359301.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.