A Hybrid GPU-CPU Framework for QCA Layout Synthesis via Parallel Simulated Annealing and Register-Level Bitboard Routing

• Leanderson Leles UFV
• Ian Otoni UFV
• Nicolas Silva UFV
• Luis Viana UFV
• Ricardo Ferreira UFV

DOI: https://doi.org/10.5753/sscad.2026.35003

Resumo

Quantum-dot Cellular Automata (QCA) is a promising beyond-CMOS paradigm, but physical design automation remains a bottleneck: existing placement and routing (P&R) approaches rely on sequential, CPU-based search, limiting scalability. This paper presents, to the best of our knowledge, the first GPU-accelerated QCA P&R framework under the USE clocking scheme, combining a parallel Simulated Annealing guided by a novel O(1) USE-aware heuristic with a register-resident bitboard-based BFS and a deterministic CPU-side A* routing pass. Across eleven benchmark circuits, our framework produces valid, fully-routed layouts in the large majority of runs, matching or improving state-of-the-art area results in less time.

Referências

Campos, C. A. T., Marciano, A. L., Neto, O. P. V., and Torres, F. S. (2015). Use: a universal, scalable, and efficient clocking scheme for qca. IEEE Transactions on computer-aided design of integrated circuits and systems, 35(3):513–517.

Canesche, M., Menezes, M., Carvalho, W., Torres, F. S., Jamieson, P., Nacif, J. A., and Ferreira, R. (2020). Traversal: A fast and adaptive graph-based placement and routing for cgras. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 40(8):1600–1612.

Fontes, G., Silva, P. A. R., Nacif, J. A. M., Neto, O. P. V., and Ferreira, R. (2018). Placement and routing by overlapping and merging qca gates. In 2018 IEEE International Symposium on Circuits and Systems (ISCAS), pages 1–5. IEEE.

Formigoni, R. E., Ferreira, R. S., and Nacif, J. A. M. (2021). A survey on placement and routing for field-coupled nanocomputing. Journal of Integrated Circuits and Systems, 16(1):1–9.

Hofmann, S., Walter, M., and Wille, R. (2024a). A* is born: Efficient and scalable physical design for field-coupled nanocomputing. In 2024 IEEE 24th International Conference on Nanotechnology (NANO), pages 80–85. IEEE.

Hofmann, S., Walter, M., and Wille, R. (2024b). MNT Bench: Benchmarking software and layout libraries for field-coupled nanocomputing. In 2024 Design, Automation and Test in Europe (DATE).

Hofmann, S., Walter, M., and Wille, R. (2025). Graph-oriented layout design for field-coupled nanocomputing via parallel multi-objective search space exploration. IEEE Transactions on Circuits and Systems I: Regular Papers.

Kahn, A. B. (1962). Topological sorting of large networks. Communications of the ACM, 5(11):558–562.

Keyes, R. W. (2005). Physical limits of silicon transistors and circuits. Reports on Progress in Physics, 68(12):2701–2746.

Kim, K., Wu, K., and Karri, R. (2005). Towards designing robust qca architectures in the presence of sneak noise paths. In Design, Automation and Test in Europe, pages 1214–1219. IEEE.

Lent, C. S. and Tougaw, P. D. (1997). A device architecture for computing with quantum dots. Proceedings of the IEEE, 85(4):541–557.

Lent, C. S., Tougaw, P. D., Porod, W., and Bernstein, G. H. (1993). Quantum cellular automata. Nanotechnology, 4(1):49–57.

Li, G., Peng, F., Zhang, B., Li, Y., and Xie, G. (2024). A qca placement and routing algorithm based on the sa algorithm. International Journal of Electronics, 111(12):2143–2158.

Moore, G. E. (1998). Cramming more components onto integrated circuits. Proceedings of the IEEE, 86(1):82–85.

Orlov, A. O., Amlani, I., Bernstein, G. H., Lent, C. S., and Snider, G. L. (1997). Realization of a functional cell for quantum-dot cellular automata. Science, 277(5328):928–930.

Torres, F. S., Silva, P. A., Fontes, G., Walter, M., Nacif, J. A. M., Ferreira, R. S., Neto, O. P. V., Chaves, J. F., Wille, R., Niemann, P., et al. (2020). On the impact of the synchronization constraint and interconnections in quantum-dot cellular automata. Microprocessors and Microsystems, 76:103109.

Tougaw, P. D. and Lent, C. S. (1994). Logical devices implemented using quantum cellular automata. Journal of Applied physics, 75(3):1818–1825.

Trindade, A., Ferreira, R., Nacif, J. A. M., Sales, D., and Neto, O. P. V. (2016). A placement and routing algorithm for quantum-dot cellular automata. In 2016 29th symposium on integrated circuits and systems design (SBCCI), pages 1–6. IEEE.

Van Laarhoven, P. J. and Aarts, E. H. (1987). Simulated annealing. In Simulated annealing: Theory and applications, pages 7–15. Springer.

Vankamamidi, V., Ottavi, M., and Lombardi, F. (2008). Two-dimensional schemes for clocking/timing of qca circuits. IEEE Transactions on computer-aided design of integrated circuits and systems, 27(1):34–44.

Walter, M., Wille, R., Große, D., Torres, F. S., and Drechsler, R. (2019). Placement and routing for tile-based field-coupled nanocomputing circuits is np-complete (research note). ACM Journal on Emerging Technologies in Computing Systems (JETC), 15(3):1–10.

Walus, K., Jullien, G., and Dimitrov, V. (2003). Computer arithmetic structures for quantum cellular automata. In The Thrity-Seventh Asilomar Conference on Signals, Systems & Computers, 2003, volume 2, pages 1435–1439. IEEE.