One Hybrid Strategy for Automatic Placement and Routing of QCA Circuit

LI Yang-shuai; PENG Fei; HAN Qian; LI Xiao-shuai; XIE Guang-jun

doi:10.12263/DZXB.20211212

您当前的位置：

首页 >

文章列表页 >

One Hybrid Strategy for Automatic Placement and Routing of QCA Circuit

PAPERS | 更新时间：2025-12-08

- One Hybrid Strategy for Automatic Placement and Routing of QCA Circuit
- ACTA ELECTRONICA SINICA Vol. 51, Issue 3, Pages: 666-674(2023)
- 作者机构：
  
  1.合肥工业大学微电子学院，安徽合肥 230009
  2.国防科技大学电子对抗学院，安徽合肥 230009
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20211212
  CLC： TP391.9
- Received：02 September 2021，
  
  Revised：2022-07-29，
  
  Published：25 March 2023
- 稿件说明：
移动端阅览
李杨帅,彭斐,韩倩等.一种针对QCA电路自动布局布线的混合策略研究[J].电子学报,2023,51(03):666-674.

LI Yang-shuai,PENG Fei,HAN Qian,et al.One Hybrid Strategy for Automatic Placement and Routing of QCA Circuit[J].ACTA ELECTRONICA SINICA,2023,51(03):666-674.
李杨帅,彭斐,韩倩等.一种针对QCA电路自动布局布线的混合策略研究[J].电子学报,2023,51(03):666-674. DOI： 10.12263/DZXB.20211212.

LI Yang-shuai,PENG Fei,HAN Qian,et al.One Hybrid Strategy for Automatic Placement and Routing of QCA Circuit[J].ACTA ELECTRONICA SINICA,2023,51(03):666-674. DOI： 10.12263/DZXB.20211212.

摘要

量子元胞自动机（Quantum Cellular Automata，QCA）电路的自动布局布线是在相关约束条件下自动放置电路单元、自动形成连线，实现门级或元胞级电路的设计过程，是QCA电路设计大型化、复杂化和系统化的必要工具.布局布线算法设计过程中最大的难题是如何解决“时钟同步”，随着二维时钟方案提出，该问题的解决方案变得更加策略化，但仍存在诸多缺陷，如成功率低，布局面积较大等.本文将二维时钟方案的布局布线问题抽象成组合优化模型，提出了一种基于遗传算法GA（Genetic Algorithm）和改进A*算法的混合策略.两种算法相互配合搭建可能的电路布局，并通过精心设计的适应度函数，搜索满足时钟同步的个体，最终实现从硬件电路到二维时钟方案上的门级布局.实验结果表明，本算法在目前被广泛应用的二维时钟方案USE（Universal，Scalable and Efficient）上的布局成功率接近100%.相较当前世界上最先进的两个QCA布局布线工具fiction和Ropper，本算法可适用电路规模更大（逻辑门数量大于10），在成功率和生成布局面积上都有大幅度的优化.

Abstract

The automatic placement and routing (P&R) of quantum cellular automata (QCA) circuits is the design process of placing and connecting circuit units with relevant constraints

and then generating gate-level or cell-level layout of circuits. It is a necessary tool for large-scale

complex and systematic circuit design. The biggest problem in the P&R algorithm design is how to solve “clock synchronization”. With the proposed two-dimensional clocking schemes

the solution has become more strategic

but there are still many shortcomings

such as low success rate and large layout area. This paper abstracts the P&R problem on the two-dimensional clocking scheme into a combinatorial optimization model

and proposes a hybrid strategy based on the genetic algorithm (GA) and the enhanced A* algorithm. Two algorithms cooperate with each other to build a possible circuit layout

and through the carefully designed fitness function

search the individuals that meet the clock synchronization

and finally generate the gate level layout from the hardware circuit. Experimental results show that the placement success rate of this algorithm in the widely used two-dimensional clocking scheme USE (Universal

Scalable

and Efficient) is close to 100%;Compared with the two most advanced QCA P&R tools fiction and Ropper

this algorithm can be applied to a larger circuit scale (the number of logic gates is greater than 10)

and has a significant optimization in success rate and generated layout area.

关键词

Keywords

references

LENT C S , TOUGAW P D . A device architecture for computing with quantum dots [J]. Proceedings of the IEEE , 1997 , 85 ( 4 ): 541 - 557 .

ZHANG Y Q , XIE G J , SUN M B , et al . Design of normalised and simplified FAs in quantum-dot cellular automata [J]. The Journal of Engineering , 2017 , 2017( 10 ): 557 - 565 .

CHO H , SWARTZLANDER E E . Adder and multiplier design in quantum-dot cellular automata [J]. IEEE Transactions on Computers , 2009 , 58 ( 6 ): 721 - 727 .

ABUTALEB M M . A novel configurable flip flop design using inherent capabilities of quantum-dot cellular automata [J]. Microprocessors and Microsystems , 2018 , 56 : 101 - 112 .

SABBAGHI-NADOOSHAN R , KIANPOUR M . A novel QCA implementation of MUX-based universal shift register [J]. Journal of Computational Electronics , 2014 , 13 ( 1 ): 198 - 210 .

TOUGAW D , JOHNSON E W , EGLEY D . Programmable logic implemented using quantum-dot cellular automata [J]. IEEE Transactions on Nanotechnology , 2012 , 11 ( 4 ): 739 - 745 .

SANDHU A , GUPTA S . A majority gate based RAM cell design with least feature size in QCA [J]. Gazi University Journal of Science , 2019 , 32 ( 4 ): 1150 - 1165 .

NIEMIER M T , KOGGE P M . Problems in designing with QCAs: Layout = timing [J]. International Journal of Circuit Theory and Applications , 2001 , 29 ( 1 ): 49 - 62 .

VANKAMAMIDI V , OTTAVI M , LOMBARDI F . Two-dimensional schemes for clocking/timing of QCA circuits [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2008 , 27 ( 1 ): 34 - 44 .

CAMPOS C A T , MARCIANO A L , VILELA NETO O P , et al . USE: A universal, scalable, and efficient clocking scheme for QCA [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2016 , 35 ( 3 ): 513 - 517 .

GOSWAMI M , MONDAL A , MAHALAT M H , et al . An efficient clocking scheme for quantum-dot cellular automata [J]. International Journal of Electronics Letters , 2020 , 8 ( 1 ): 83 - 96 .

DENG F F , XIE G J , CHENG X , et al . CFE: A convenient, flexible, and efficient clocking scheme for quantum-dot cellular automata [J]. IET Circuits , Devices & Systems, 2020 , 14 ( 1 ): 88 - 92 .

WALTER M , WILLE R , TORRES F S , et al . Fiction: An open source framework for the design of field-coupled nanocomputing circuits [EB/OL]. [ 2021-09-01 ]. https://arxiv.org/abs/1905.02477 https://arxiv.org/abs/1905.02477 .

FORMIGONI R E , FERREIRA R S , NACIF J A M . Ropper: A placement and routing framework for field-coupled nanotechnologies [C]// 2019 32nd Symposium on Integrated Circuits and Systems Design (SBCCI) . Piscataway : IEEE , 2019 : 1 - 6 .

NGUYEN J , RAVICHANDRAN R , LIM S K , et al . Global placement for quantum-dot cellular automata based circuits [J]. Georgia Institute of Technology , 2003 : 1 - 17 .

ANTONELLI D A , CHEN D Z , DYSART T J , et al . Quantum-Dot Cellular Automata (QCA) circuit partitioning: Problem modeling and solutions [C]// Proceedings of the 41st Annual Design Automation Conference . San Diego : IEEE , 2004 : 363 - 368 .

RAVICHANDRAN R , LIM S K , NIEMIER M . Automatic cell placement for quantum-dot cellular automata [J]. Integration , 2005 , 38 ( 3 ): 541 - 548 .

WALTER M , WILLE R , GROßE D , et al . An exact method for design exploration of quantum-dot cellular automata [C]// 2018 Design , Automation & Test in Europe Conference & Exhibition (DATE) . Piscataway : IEEE , 2018 : 503 - 508 .

WALTER M , WILLE R , TORRES F S , et al . Scalable design for field-coupled nanocomputing circuits [C]// Proceedings of the 24th Asia and South Pacific Design Automation Conference . Tokyo : ACM , 2019 : 197 - 202 .

WALTER M , HAASWIJK W , WILLE R , et al . One-pass synthesis for field-coupled nanocomputing technologies [C]// Proceedings of the 26th Asia and South Pacific Design Automation Conference . Tokyo : ACM , 2021 : 574 - 580 .

TRINDADE A , FERREIRA R , NACIF J A M , et al . A placement and routing algorithm for quantum-dot cellular automata [C]// Proceedings of the 2016 29th Symposium on Integrated Circuits and Systems Design . Belo Horizonte : IEEE , 2016 : 1 - 6 .

FONTES G , SILVA P A R L , NACIF J A M , et al . Placement and routing by overlapping and merging QCA gates [C]// 2018 IEEE International Symposium on Circuits and Systems . Piscataway : IEEE , 2018 : 1 - 5 .

AMARU L , GAILLARDON P E , MICHELI G D . The EPFL combinational benchmark suite [C]// Proceedings of the 24th International Workshop on Logic & Synthesis , Mountain View : EPFL , 2015 : 1 - 5 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Genetic Algorithm of Solving Job-Shop Scheduling Problem

Genetic Algorithm Method Based on Knowledge for Minimizing the Number of Tardy Jobs in Identical Parallel Machine Scheduling Problem

Genetic Algorithm Based MIMO Equalization Parameter Optimization Technology for Mode-Division Multiplexed System

An Absorbing Structure Covering the Whole UHF Band

Related Author

张长水

沈刚

阎平凡

Liu Min

Wu Cheng

Dai Yuanshun

ZHAO Tian-feng

WEN Feng

Related Institution

Tsinghua Univ.Beijing l00084)Shen Gang

北京航空航天大学制造工程系

清华大学自动化系北京航空航天大学制造工程系

Department of Automation,Tsinghua University

Key Laboratory of Optical Fiber Sensing and Communication Networks, Ministry of Education, University of Electronics Science and Technology of China

⁰