QCA channel routing with wire crossing minimization

ABSTRACT

Quantum-dot Cellular Automata (QCA) is a novel computing mechanism that can represent binary information based on spatial distribution of electron charge configuration in chemical molecules. QCA layout is currently restricted to a single layer with very limited number of wire crossing permitted. Thus, wire crossing minimization is crucial in improving the manufacturability of QCA circuits. In this article, we present the first QCA channel routing algorithm for wire crossing minimization. Our channel routing algorithm is able to reduce crossings, where Left-Edge First, Yoshimura and Kuh, and topologically-based algorithms fail to do so.

REFERENCES

• 1: I. Amlani, A. Orlov, G. Toth, G. Bernstein, C. Lent, and G. Snider. Digital logic gate using quantum-dot cellular automata. Science, pages 289--291, 1999.
• 2: Dominic A. Antonelli , Danny Z. Chen , Timothy J. Dysart , Xiaobo S. Hu , Andrew B. Kahng , Peter M. Kogge , Richard C. Murphy , Michael T. Niemier, Quantum-Dot Cellular Automata (QCA) circuit partitioning: problem modeling and solutions, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996671]
• 3: David N. Deutsch, A “Dogleg” channel router, Proceedings of the 13th conference on Design automation, p.425-433, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804843]
• 4: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 5: Nadine Gergel , Shana Craft , John Lach, Modeling QCA for area minimization in logic synthesis, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., USA [doi>10.1145/764808.764824]
• 6: Akihiro Hashimoto , James Stevens, Wire routing by optimizing channel assignment within large apertures, Proceedings of the 8th workshop on Design automation, p.155-169, June 28-30, 1971, Atlantic City, New Jersey, United States [doi>10.1145/800158.805069]
• 7: ISCAS89. The ISCAS 1989 benchmark suite.
• 8: Jing Huang , Mariam Momenzadeh , Mehdi B. Tahoori , Fabrizio Lombardi, Design and characterization of an and-or-inverter (AOI) gate for QCA implementation, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA [doi>10.1145/988952.989054]
• 9: Ramprasad Ravichandran , Sung Kyu Lim , Mike Niemier, Automatic cell placement for quantum-dot cellular automata, Integration, the VLSI Journal, v.38 n.3, p.541-548, January 2005 [doi>10.1016/j.vlsi.2004.07.002]
• 10: K. Walus, T. Dysart, G. Jullien, and R. Budiman. QCADesigner: a rapid design and simulation tool for quantum-dot cellular automata. IEEE Transactions on Nanotechnology, 2004.
• 11: T. Yoshimura and E. Kuh. Efficient algorithms for channel routing. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pages 25--35, 1982.
• 12: D. H. Younger. Minimum feedback arc sets for a directed graph. IEEE Trans. on Circuit Theory, pages 238--245, 1963.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design, Theory

Keywords:
QCA channel routing, weighted minimum feedback edge set, wire crossing minimization