Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

Node duplication and routing algorithms for quantum-dot cellular automata circuits

Node duplication and routing algorithms for quantum-dot cellular automata circuits

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IEE Proceedings - Circuits, Devices and Systems — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

© The Institution of Engineering and Technology
Published

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.

Inspec keywords: cellular automata; quantum computing; network routing; circuit layout; logic design; graph theory; quantum dots

Other keywords: electron charge configuration; binary information; routing algorithms; wire crossing minimisation; vertical constraint graph; QCA circuit layout; QCA circuit manufacturability; K-layered bipartite graphs; node duplication; spatial distribution; quantum-dot cellular automata circuits; cycle breaker; fan-out tolerance duplication; chemical molecules

Subjects: Automata theory; Logic design methods; Combinatorial mathematics; Digital circuit design, modelling and testing; Combinatorial mathematics; Quantum computing techniques

References

    1. 1)
      • I. Amlani , A. Orlov , G. Snider , C. Lent . Demonstation of a func. quantum-dot cellular automata cell. J. Vac. Sci. Technol. , 3795 - 3799
    2. 2)
      • Deutch, D.: `A dogleg channel router', Proc. ACM Design Automation Conf., 1976.
    3. 3)
      • M. Garey , D. Johnson . Crossing number is NP-complete. SIAM J. Algebr. Discrete Methods
    4. 4)
      • R.G. Michael , S.J. David . (1979) Computers and intractability: a guide to the theory of NP-completeness.
    5. 5)
      • R. Kummamuru , J. Timler , G. Toth , C. Lent , R. Ramasubramaniam , A. Orlov , G. Bernstein . Power gain in a quantum-dot cellular automata latch. Appl. Phys. Lett. , 1332 - 1334
    6. 6)
      • S. Sapatnekar . A timing model incorporating the effect of crosstalk on delay and its application to optimal channel routing. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. , 550 - 559
    7. 7)
      • Hashimoto, A., Stevens, S.: `Wire routing by optimizing channel assignment within large apertures', Proc. ACM Design Automation Conf., 1971, p. 155–169.
    8. 8)
      • S.K. Lim , R. Ravichandran , M. Niemier . Partitioning and placement for buildable QCA circuits. ACM J. Emerging Technol. Comput. Syst. , 50 - 70
    9. 9)
      • Antonelli, D., Chen, D., Dysart, T., Hu, X., Kahng, A., Kogge, P., Murphy, R., Niemier, M.: `Quantum-dot cellular automata partitioning: Problem modeling and solutions', Proc. ACM Design Automation Conf., 2004.
    10. 10)
      • Rkic, M., Lillis, J., Beraudo, G.: `An approach to placement-coupled logic replication', Proc. ACM Design Automation Conf., 2004.
    11. 11)
      • ITC99. The ITC 1999 benchmark suite.
    12. 12)
      • I. Amlani , A. Orlov , G. Toth , G. Bernstein , C. Lent , G. Snider . Digital logic gate using quantum-dot cellular automata. Science , 289 - 291
    13. 13)
      • Beraudo, G., Lillis, J.: `Timing optimization of FPGA placements by logic replication', In Proc. ACM Design Automation Conf., 2003.
    14. 14)
      • K. Walus , T. Dysart , G. Jullien , R. Budiman . QCADesigner: a rapid design and simulation tool for quantum-dot cellular automata. IEEE Trans. Nanotechnol. , 26 - 31
    15. 15)
      • Weiskircher, R., Gutwenger, C., Mutzel, P.: `Inserting an edge into a planar graph', ACM-SIAM Symp. on Discrete algorithms, 2001.
    16. 16)
      • G. Snider , A. Orlov , I. Amlani , G. Bernstein , C. Lent , J. Merz , W. Porod . Quantum-dot cellular automata: Line and majority gate logic. Jpn. J. Appl. Phys. , 7227 - 7229
    17. 17)
      • M. Lieberman , S. Chellamma , B. Varughese , Y. Wang , C. Lent , G. Bernstein , G. Snider , F. Peiris . Quantum-dot cellular automata at a molecular scale. Ann. New York Acad. Sci. , 225 - 239
    18. 18)
      • ISCAS89. The ISCAS 1989 benchmark suite.
    19. 19)
      • M. Enos , S. Hauck , M. Sarrafzadeh . Evaluation and optimisation of replication algorithms for logic bipartitioning. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. , 1237 - 1248
    20. 20)
      • T. Catarci . The assignment heuristic for crossing reduction. IEEE Trans. Syst. Man Cybern. , 515 - 521
    21. 21)
      • T. Yoshimura , E. Kuh . Efficient algorithms for channel routing. IEEE Trans. Comput.-Aided Des. Int. Circuits Syst. , 25 - 35
    22. 22)
      • P.D. Tougaw , C.S. Lent . Logical devices implemented using quantum cellular automata. J. Appl. Phys. , 1818 - 1825
    23. 23)
      • K. Sugiyama , S. Tagawa , M. Toda . Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man. Cybern. , 109 - 125
    24. 24)
      • M. Marek-Sadowska , M. Sarrafzadeh . The crossing distribution problem. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. , 423 - 433
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-cds_20050278
Loading

Related content

content/journals/10.1049/ip-cds_20050278
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address