电子学报 ›› 2023, Vol. 51 ›› Issue (3): 666-674.DOI: 10.12263/DZXB.20211212

• 学术论文 • 上一篇    下一篇

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

李杨帅1, 彭斐1, 韩倩1, 李小帅2, 解光军1   

  1. 1.合肥工业大学微电子学院,安徽 合肥 230009
    2.国防科技大学电子对抗学院,安徽 合肥 230009
  • 收稿日期:2021-09-02 修回日期:2022-07-29 出版日期:2023-03-25
    • 作者简介:
    • 李杨帅 男,1996年出生,安徽合肥人.硕士研究生.主要研究方向为场耦合纳米电路自动布局布线算法. E-mail: 1258173567@qq.com
      彭 斐 男,1985年出生,河北保定人.博士研究生.主要研究方向为电子设计自动化、场耦合纳米计算. E-mail: fpeng1985@126.com
      韩 倩 女,1997年出生,江苏宿迁人.硕士研究生.主要研究方向为QCA电路的研究和高速数据的传输. E-mail: 2210202992@qq.com
      李小帅 女,1989年出生,河南登封人,讲师,博士研究生,主要研究方向为通信对抗,车联网通信. E-mail: :xiaoshuaihit@126.com
      解光军 男,1970年出生,安徽合肥人.教授,博士.主要研究方向为纳米器件与电路、集成电路设计. 中国电子学会会员编号:E190004993S.E-mail: gjxie8005@hfut.edu.cn

One Hybrid Strategy for Automatic Placement and Routing of QCA Circuit

LI Yang-shuai1, PENG Fei1, HAN Qian1, LI Xiao-shuai2, XIE Guang-jun1   

  1. 1.College of Microelectronics,Hefei University of Technology,Hefei,Anhui 230009,China
    2.College of Electronic Engineering,National University of Defense Technology,Hefei,Anhui 230009,China
  • Received:2021-09-02 Revised:2022-07-29 Online:2023-03-25 Published:2023-04-20

摘要:

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

关键词: 元胞自动机, 布局布线, 组合优化, 遗传算法, A*算法

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.

Key words: quantum cellular automata, placement and routing, combinatorial optimization, genetic algorithm, A* algorithm

中图分类号: