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

doi:10.12263/DZXB.20211212

摘要/Abstract

摘要：

量子元胞自动机（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

中图分类号:

TP391.9

李杨帅, 彭斐, 韩倩, 等. 一种针对QCA电路自动布局布线的混合策略研究[J]. 电子学报, 2023, 51(3): 666-674.

Yang-shuai LI, Fei PENG, Qian HAN, et al. One Hybrid Strategy for Automatic Placement and Routing of QCA Circuit[J]. Acta Electronica Sinica, 2023, 51(3): 666-674.

图/表 12

参考文献 23

1	LENT C S, TOUGAW P D. A device architecture for computing with quantum dots[J]. Proceedings of the IEEE, 1997, 85(4): 541-557.
2	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.
3	CHO H, SWARTZLANDER E E. Adder and multiplier design in quantum-dot cellular automata[J]. IEEE Transactions on Computers, 2009, 58(6): 721-727.
4	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.
5	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.
6	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.
7	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.
8	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.
9	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.
10	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.
11	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.
12	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.
13	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]. .
14	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.
15	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.
16	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.
17	RAVICHANDRAN R, LIM S K, NIEMIER M. Automatic cell placement for quantum-dot cellular automata[J]. Integration, 2005, 38(3): 541-548.
18	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.
19	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.
20	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.
21	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.
22	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.
23	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.

Benchmarks				CS	fiction-exact			Ropper			提出的算法
电路名称	节点数量	输入/输出	布线	U/T	面积	关键路径	时间/s	面积	关键路径	时间/s	面积	关键路径	时间/s
XOR	5	2/1	6	U	4×5	9	0.7	5×6	10	2.7	3×3	6	2.8
XOR	5	2/1	6	T	3×6	8	0.2	5×6	10	2.8	3×3	5	2.4
2:1 MUX	6	3/1	6	U	5×3	7	0.2	5×6	10	2.7	3×4	7	3.4
2:1 MUX	6	3/1	6	T	3×4	6	0.1	5×6	10	2.7	3×3	4	2.0
4:1 MUX	13	4/1	19	U	-	-	-	14×14	18	15.3	6×9	20	45.9
4:1 MUX	13	4/1	19	T	7×8	13	34.0	-	-	-	-	-	-
ParGen	6	3/1	9	U	4×10	14	287.0	9×14	18	4.2	5×5	16	8.0
ParGen	6	3/1	9	T	5×7	10	0.8	13×3	18	2.9	5×5	9	5.7
ParCheck	13	4/1	18	U	-	-	-	-	-	-	8×9	29	55.1
ParCheck	13	4/1	18	T	7×8	14	10.6	-	-	-	9×10	16	56.1
1 bitAdder	10	6/1	15	U	-	-	-	11×17	18	2.2	7×5	20	22.0
1 bitAdder	10	6/1	15	T	6×10	14	6.4	14×17	18	5.0	-	-	-
C17	11	5/2	12	U	-	-	-	7×8	14	2.8	5×5	10	5.8
C17	11	5/2	12	T	5×7	10	1.0	6×11	14	2.9	4×6	8	5.3
FA	9	3/2	12	U	-	-	-	-	-	-	5×8	15	52.4
FA	9	3/2	12	T	7×9	15	330.2	9×10	22	21.6	-	-	-
FS	9	3/2	12	U	-	-	-	7×12	20	29.8	6×6	15	156.0
FS	9	3/2	12	T	5×10	14	227.9	-	-	-	-	-	-
HA	6	2/2	8	U	5×6	10	14.2	-	-	-	3×6	10	9.1
HA	6	2/2	8	T	4×5	8	1.2	-	-	-	4×5	6	4.7
HS	6	2/2	8	U	5×6	15	10.7	-	-	-	3×5	8	8.8
HS	6	2/2	8	T	4×6	9	3.1	-	-	-	3×7	8	8.4

Benchmarks				CS	fiction-exact			Ropper			提出的算法
电路名称	节点数量	输入/输出	布线	U/T	面积	关键路径	时间/s	面积	关键路径	时间/s	面积	关键路径	时间/s
XOR	5	2/1	6	U	4×5	9	0.7	5×6	10	2.7	3×3	6	2.8
XOR	5	2/1	6	T	3×6	8	0.2	5×6	10	2.8	3×3	5	2.4
2:1 MUX	6	3/1	6	U	5×3	7	0.2	5×6	10	2.7	3×4	7	3.4
2:1 MUX	6	3/1	6	T	3×4	6	0.1	5×6	10	2.7	3×3	4	2.0
4:1 MUX	13	4/1	19	U	-	-	-	14×14	18	15.3	6×9	20	45.9
4:1 MUX	13	4/1	19	T	7×8	13	34.0	-	-	-	-	-	-
ParGen	6	3/1	9	U	4×10	14	287.0	9×14	18	4.2	5×5	16	8.0
ParGen	6	3/1	9	T	5×7	10	0.8	13×3	18	2.9	5×5	9	5.7
ParCheck	13	4/1	18	U	-	-	-	-	-	-	8×9	29	55.1
ParCheck	13	4/1	18	T	7×8	14	10.6	-	-	-	9×10	16	56.1
1 bitAdder	10	6/1	15	U	-	-	-	11×17	18	2.2	7×5	20	22.0
1 bitAdder	10	6/1	15	T	6×10	14	6.4	14×17	18	5.0	-	-	-
C17	11	5/2	12	U	-	-	-	7×8	14	2.8	5×5	10	5.8
C17	11	5/2	12	T	5×7	10	1.0	6×11	14	2.9	4×6	8	5.3
FA	9	3/2	12	U	-	-	-	-	-	-	5×8	15	52.4
FA	9	3/2	12	T	7×9	15	330.2	9×10	22	21.6	-	-	-
FS	9	3/2	12	U	-	-	-	7×12	20	29.8	6×6	15	156.0
FS	9	3/2	12	T	5×10	14	227.9	-	-	-	-	-	-
HA	6	2/2	8	U	5×6	10	14.2	-	-	-	3×6	10	9.1
HA	6	2/2	8	T	4×5	8	1.2	-	-	-	4×5	6	4.7
HS	6	2/2	8	U	5×6	15	10.7	-	-	-	3×5	8	8.8
HS	6	2/2	8	T	4×6	9	3.1	-	-	-	3×7	8	8.4

[1]	赵耿, 马英杰, 陈磊, 董有恒, 侯艳丽. 基于扰动时空混沌系统的动态S盒设计[J]. 电子学报, 2022, 50(8): 2037-2042.
[2]	宣志玮, 毛剑琳, 张凯翔. CBS框架下面向复杂地图的低拓展度A*算法[J]. 电子学报, 2022, 50(8): 1943-1950.
[3]	蒋林, 方东君, 周和文, 黄惠保. 基于射线模型的改进全局路径规划算法[J]. 电子学报, 2022, 50(3): 548-556.
[4]	李彦苍, 巩翔宇. 基于信息熵的改进狮群算法及其在组合优化中的应用[J]. 电子学报, 2021, 49(8): 1577-1585.
[5]	钱忠胜, 俞情媛, 宋涛, 朱懿敏, 祝洁, 赵畅. 基于支持向量机回归模型的测试用例生成与重用[J]. 电子学报, 2021, 49(7): 1386-1391.
[6]	王亚良, 倪晨迪, 金寿松. 基于多邻居结构的自适应元胞差分算法[J]. 电子学报, 2021, 49(3): 578-585.
[7]	刘焕淋, 黄美娜, 陈勇, 杨健, 黄冰川, 张彤. 基于NOMA技术的PLC-VLC用户配对和子载波分配方法[J]. 电子学报, 2021, 49(10): 1952-1959.
[8]	金泽芬芬, 侯志强, 余旺盛, 王鑫, 寇人可. 基于量子遗传算法的视觉目标跟踪[J]. 电子学报, 2020, 48(8): 1493-1501.
[9]	郭广颂, 陈良骥, 文振华, 张勇. 求解高维混合指标优化问题的交互式进化计算[J]. 电子学报, 2020, 48(7): 1361-1368.
[10]	薛河, 苟思育, 倪陈强. 紧凑拉伸试样参比电位差接线点布局的优化方法[J]. 电子学报, 2020, 48(7): 1396-1402.
[11]	范书平, 张岩, 马宝英, 万里, 姚念民, 宋妍. 基于均衡优化理论的路径覆盖测试数据进化生成[J]. 电子学报, 2020, 48(7): 1303-1310.
[12]	徐超群, 易忠, 孟立飞, 刘超波, 黄魁. 基于遗传算法的卫星磁模型研究[J]. 电子学报, 2020, 48(6): 1108-1112.
[13]	唐香琼, 黄春跃, 梁颖, 匡兵, 赵胜军. 基于再流焊冷却过程应力分析的板极组件BGA焊点参数优化[J]. 电子学报, 2020, 48(6): 1117-1123.
[14]	邓飞飞, 解光军, 王晓旸, 程心, 张永强. 量子元胞自动机共面五输入择多门结构的分析与设计[J]. 电子学报, 2020, 48(5): 861-869.
[15]	黄俊君, 关杰. 基于元胞自动机的S盒的性质与神经网络实现研究[J]. 电子学报, 2020, 48(12): 2462-2468.