Quantum-Dot Cellular Automata (QCA) circuit partitioning: problem modeling and solutions

ABSTRACT

This paper presents the Quantum-Dot Cellular Automata (QCA) physical design problem, in the context of the VLSI physical design problem. The problem is divided into three subproblems: partitioning, placement, and routing of QCA circuits. This paper presents an ILP formulation and heuristic solution to the partitioning problem, and compares the two sets of results. Additionally, we compare a human-generated circuit to the ILP and Heuristic solutions. The results demonstrate that the heuristic is a practical method of reducing partitioning run time while providing a result that is close to the optimal for a given circuit.

REFERENCES

• 1: A. O. Orlov et al. Expiremental demonstration of clocked single electron switching in quantum-dot cellular automata. Appl. Phys. Lett., 77(2):295--297, July 2000.
• 2: Charles J. Alpert , Andrew B. Kahng, Recent directions in netlist partitioning: a survey, Integration, the VLSI Journal, v.19 n.1-2, p.1-81, Aug. 1995 [doi>10.1016/0167-9260(95)00008-4]
• 3: I. Amlani et al. Digital logic gate using quantum-dot cellular automata.Science 284:289--291, April 1999.
• 4: Q. Hang, Y. Wang, M. Lieberman, and G. H. Bernstein. Molecular patterning through high-resolution polymethylmethacrylate masks. Appl. Phys. Lett., 80(22):4220--4222, June 2002.
• 5: K. Hennessy and C. S. Lent. Clocking of molecular quantum-dot cellular automata. Journal of Vacuum Science and Technology 19(5):1752--1755, September/October 2001.
• 6: X. S. Hu, S. C. Bass, and R. G. Harber. Minimizing the number of delay buffers in the synchronization of pipelined systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 13(12):1441--1449, December 1994.
• 7: J. Jiao, G. J. Long, F. Grandjean, A. M. Beatty, and T. P. Fehlner. Building blocks for the molecular expression of quantum cellular automata. isolation and characterization of a covalently bonded square array of two ferrocenium and two ferrocene complexes. J. Am. Chem. Soc., 125:7522--7523, 2003.
• 8: R. K. Kummamuru et al. Operation of a quantum-dot cellular automata (QCA) shift register and analysis of errors. IEEE Transactions on Electron Devices 50(9):1906--1913, September 2003.
• 9: C. Leiserson and J. Saxe. Retiming synchronous circuitry. Algorithmica 6(1):5--35, 1990.
• 10: C. S. Lent and B. Isaksen. Clocked molecular quantum-dot cellular automata. IEEE Transactions on Electron Devices 50(9).
• 11: C. S. Lent, B. Isaksen, and M. Lieberman. Molecular quantum-dot cellular automata. J. Am. Chem. Soc., 125(4):1056--1063,2003.
• 12: Craig S. Lent, P. Douglas Tougaw, and Wolfgang Porod. Quantum Cellular Automata. Nanotechnology 4, 49 1993.
• 13: Z. Li and T. P. Fehlner. Molecular QCA cells. 2. characterization of an unsymmetrical dinuclear mixed-valence complex bound to a au surface by an organic linker. Inorganic Chemistry 42:5715--5721, 2003.
• 14: M. Lieberman et al.Quantum-dot cellular automata at a molecular scale.Ann. N.Y. Acad. Sci., 960:225--239, 2002.
• 15: M. T. Niemier and P. M. Kogge. Logic-in-wire: Using quantum dots to implement a microprocessor. In International Conference on Electronics, Circuits, and Systems (ICECS '99), Cyprus, September 1999.
• 16: Michael T. Niemier. Designing Digital Systems in Quantum Cellular Automata MS CSE Thesis, University of Notre Dame, April 2000.
• 17: Michael T. Niemier and Peter M. Kogge. Problems in designing with QCAs: Layout = timing. International Journal of Circuit Theory and Applications 29:49--62, April 2001.
• 18: Michael Thaddeus Niemier , Peter M. Kogge, Exploring and exploiting wire-level pipelining in emerging technologies, Proceedings of the 28th annual international symposium on Computer architecture, p.166-177, June 30-July 04, 2001, Göteborg, Sweden
• 19: A. O. Orlov et al. Expiremental demonstration of a binary wire for quantum-dot cellular automata. Appl. Phys. Lett., 74(19):2875--2877, May 1999.
• 20: A.O. Orlov et al. Clocked quantum-dot cellular automata shift register. Surface Science 532--535:1193--1198, June 2003.
• 21: H. Qi et al.Molecular quantum cellular automata cells. electric field driven switching of a silicon surface bound array of vertically oriented two-dot molecular quantum cellular automata. J. Am. Chem. Soc., 125:15250--15259, 2003.
• 22: Naveed A. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Norwell, MA, 1995

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

General Terms:
Algorithms, Design

Keywords:
circuit partitioning, computer aided design, quantum-dot cellular automata (QCA)