Node duplication and routing algorithms for quantum-dot cellular automata circuits
Authors:
- 1 January 2006
- journal article
- Published by Institution of Engineering and Technology (IET) in IEE Proceedings - Circuits, Devices and Systems
- Vol. 153 (5) , 497-505
Abstract
Quantum-dot cellular automata (QCA) is a novel computing mechanism that can represent binary information based on the spatial distribution of electron charge configuration in chemical molecules. QCA circuit layout is currently restricted to a single layer with very limited number of wire crossings permitted. Thus, wire crossing minimisation is crucial in improving the manufacturability of QCA circuits. We present the first QCA node duplication and routing algorithms for wire crossing minimisation. Our duplication algorithm named fan-out tolerance duplication (FTD) explores node duplication in conjunction with node placement using K-layered bipartite graphs (KLBG). FTD successfully removes additional crossings at the cost of increased area and allows flexible tradeoff between area and wire crossing. Our routing algorithm, namely cycle breaker (CB), constructs a modified vertical constraint graph (VCG) to enforce additional vertical relation for wire crossing reduction. We formulate and provide a heuristic solution for the weighted minimum feedback edge set problem to effectively remove cycles from the VCG. As a result, FTD and CB achieve wire crossing results that are very close to theoretical lower bound and outperform the conventional algorithms significantly.Keywords
This publication has 11 references indexed in Scilit:
- QCADesigner: A Rapid Design and Simulation Tool for Quantum-Dot Cellular AutomataIEEE Transactions on Nanotechnology, 2004
- Power gain in a quantum-dot cellular automata latchApplied Physics Letters, 2002
- Quantum-Dot Cellular Automata: Line and Majority Logic GateJapanese Journal of Applied Physics, 1999
- Digital Logic Gate Using Quantum-Dot Cellular AutomataScience, 1999
- Evaluation and optimization of replication algorithms for logic bipartitioningIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1999
- The crossing distribution problem [IC layout]IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1995
- The assignment heuristic for crossing reductionIEEE Transactions on Systems, Man, and Cybernetics, 1995
- Logical devices implemented using quantum cellular automataJournal of Applied Physics, 1994
- Efficient Algorithms for Channel RoutingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1982
- Methods for Visual Understanding of Hierarchical System StructuresIEEE Transactions on Systems, Man, and Cybernetics, 1981