一种针对QCA电路自动布局布线的混合策略研究  

One Hybrid Strategy for Automatic Placement and Routing of QCA Circuit

作　　者：李杨帅 彭斐 韩倩 李小帅 解光军 LI Yang-shuai;PENG Fei;HAN Qian;LI Xiao-shuai;XIE Guang-jun(College of Microelectronics,Hefei University of Technology,Hefei,Anhui 230009,China;College of Electronic Engineering,National University of Defense Technology,Hefei,Anhui 230009,China)

机构地区：[1]合肥工业大学微电子学院,安徽合肥230009 [2]国防科技大学电子对抗学院,安徽合肥230009

出　　处：《电子学报》2023年第3期666-674,共9页Acta Electronica Sinica

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

关 键 词：元胞自动机 布局布线 组合优化 遗传算法 A^(*)算法 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]