Partitioning and placement for buildable QCA circuits

ABSTRACT

Quantum-dot Cellular Automata (QCA) is a novel computing mechanism that can represent binary information based on spatial distribution of an electron charge configuration in chemical molecules. In this article, we present the first partitioning and placement algorithm for automatic QCA layout. We identify several objectives and constraints that will enhance the buildability of QCA circuits. The results are intended to: (1) define what is computationally interesting and could actually be built within a set of predefined constraints, (2) project what designs will be possible as additional constructs become realizable, and (3) provide a vehicle that we can use to compare QCA systems to silicon-based systems.

REFERENCES

• 1: Amlani, I., Orlov, A., Snider, G., and Lent, C. 1998. Demonstation of a func. quantum-dot cellular automata cell. J. Vac. Sci. Tech. 3795--3799.
• 2: Amlani, I., Orlov, A., Toth, G., Bernstein, G., Lent, C., and Snider, G. 1999. Digital logic gate using quantum-dot cellular automata. Science. 289--291.
• 3: 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]
• 4: Gary H. Bernstein, Quantum-dot cellular automata: computing by field polarization, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775900]
• 5: Jason Cong , Sung Kyu Lim, Performance driven multiway partitioning, Proceedings of the 2000 conference on Asia South Pacific design automation, p.441-446, January 2000, Yokohama, Japan [doi>10.1145/368434.368736]
• 6: Dunlop, A. and Kernighan, B. 1985. A procedure for placement of standard-cell VLSI circuits. IEEE Trans. Comput.-Aid. Des. Integr. Circuits Syst. 92--98.
• 7: Enos, M., Hauck, S., and Sarrafzadeh, M. 1999. Evaluation and optimization of replication algorithms for logic bipartitioning. IEEE Trans. Comput.-Aid. Des. Integr. Circuits Syst. 1237--1248.
• 8: 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
• 9: 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]
• 10: Scott Hamilton, Semiconductor Research Corporation: Taking Moore's Law Into the Next Century, Computer, v.32 n.1, p.43-48, January 1999 [doi>10.1109/2.738303 ]
• 11: Hennessy, K. and Lent, C. 2001. Clocking of molecular quantum-dot cellular automata. J. Vacuum Science Tech. 1752--1755.
• 12: Ho, R., Mai, K., and Horowitz, M. 2001. The future of wires. Proceedings of the IEEE. 490--504.
• 13: 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]
• 14: Kleinhans, J. M., Sigl, G., Johannes, F. M., and Antreich, K. J. 1991. GORDIAN: VLSI placement by quadratic programming and slicing optimization. IEEE Trans. on Comput-Aided Des. Integr. Circuits Syst. 10, 3, 356--365.
• 15: Kummamuru, R., Timler, J., Toth, G., Lent, C., Ramasubramaniam, R., Orlov, A., and Bernstein, G. 2002. Power gain in a quantum-dot cellular automata latch. Applied Physics Letters. 1332--1334.
• 16: Leni, C. S. 2002. Molecular electronics: Bypassing the transistor paradigm. Science, 1597--1599.
• 17: Lieberman, M., Chellamma, S., Varughese, B., Wang, Y., Lent, C., Bernstein, G., Snider, G., and Peiris, F. 2002. Quantum-dot cellular automata at a molecular scale. Annals of the New York Academy of Science. 225--239.
• 18: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 19: Hiroshi Murata , Kunihiro Fujiyoshi , Shigetoshi Nakatake , Yoji Kajitani, Rectangle-packing-based module placement, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.472-479, November 05-09, 1995, San Jose, California, United States
• 20: Nguyen, J., Ravichandran, R., Lim, S. K., and Niemier, M. 2003. Global placement for quantum-dot cellular automata based circuits. Tech. Rep. GIT-CERCS-03-20, Georgia Institute of Technology.
• 21: Michael Thaddeus Niemier , Peter M. Kogge, The effects of a new technology on the design, organization, and architectures of computing systems, 2003
• 22: Niemier, M. and Kogge, P. 2001. Exploring and exploiting wire-level pipelining in emerging technologies. In Proceedings of the Great Lakes Symposum on VLSI.
• 23: Niemier, M. and Kogge, P. 2004. The 4-diamond circuit: A minimally complex nano-scale computational building block in QCA. In IEEE Symposium on VLSI. 3--10.
• 24: Packan, P. 1999. Pushing the limits. Science, 2079--2081.
• 25: Jan M. Rabaey, Digital integrated circuits: a design perspective, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 26: Ramprasad Ravichandran , Nihal Ladiwala , Jean Nguyen , Mike Niemier , Sung Kyu Lim, Automatic cell placement for quantum-dot cellular automata, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA [doi>10.1145/988952.989033]
• 27: Rutten, P. 2001. Is moore's law infinite? The economics of Moore's law. Kellog Tech Venture. 1--28.
• 28: Snider, G., Orlov, A., Amlani, I., Bernstein, G., Lent, C., Merz, J., and Porod, W. 1999. Quantum-dot cellular automata: Line and majority gate logic. Jpn. J. Appl. Phys., 7227--7229.
• 29: Sugiyama, K., Tagawa, S., and Toda, M. 1981. Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man., Cybern. 109--125.
• 30: Sun, W. J. and Sechen, C. 1995. Efficient and effective placement for very large circuits. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 14, 3, 349--359.
• 31: Tougaw, P. and Lent, C. 1994. Logical devices implemented using quantum cellular automata. J. Appl. Phys. 1818.
• 32: Tsay, R. S. 1993. An exact zero-skew clock routing algorithm. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst.
• 33: Walus, K., Dysart, T., Jullien, G., and Budiman, R. 2004. QCADesigner: A rapid design and simulation tool for quantum-dot cellular automata. IEEE Trans. Nanotech.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design

Keywords:
Nanotechnology, partitioning, placement, quantum-dot cellular automata