考虑长度匹配的快速单通量量子电路布线算法

刘耿耿; 余延涛; 周茹平; 魏榕山; 徐宁

doi:10.7544/issn1000-1239.202440065

考虑长度匹配的快速单通量量子电路布线算法

刘耿耿^{1, 2,},
余延涛^{1, 2},
周茹平^{1, 2},
魏榕山^3, ,,
徐宁⁴

1.
福州大学计算机与大数据学院　福州　350116
2.
福建省网络计算与智能信息处理重点实验室（福州大学）　福州　350116
3.
福州大学物理与信息工程学院　福州　350108
4.
武汉理工大学信息工程学院　武汉　430070

基金项目: 国家自然科学基金项目（62372109）；福建省杰出青年科学基金项目（2023J06017）.

详细信息

作者简介:
刘耿耿: 1988年生. 博士，教授，博士生导师，CCF高级会员. 主要研究方向为微流控生物芯片和集成电路的设计自动化

余延涛: 2000年生. 硕士研究生，CCF学生会员. 主要研究方向为超大规模集成电路布线

周茹平: 1998年生. 博士研究生，CCF学生会员. 主要研究方向为超大规模集成电路布线、时钟树综合

魏榕山: 1980年生. 博士，教授，博士生导师. 主要研究方向为智能传感器芯片设计、面向深度学习等应用的人工智能芯片设计

徐宁: 1968年生. 博士，教授，博士生导师，CCF高级会员. 主要研究方向为电子设计自动化、集成电路设计自动化和人工智能

通讯作者:
魏榕山（wrs08@fzu.edu.cn）

中图分类号: TP391
计量
- 文章访问数: 0
- HTML全文浏览量: 0
- PDF下载量: 0
出版历程
- 收稿日期: 2024-02-01
- 修回日期: 2024-10-15
- 录用日期: 2024-11-12
- 网络出版日期: 2024-11-18

Rapid Single-Flux-Quantum Circuit Routing Algorithm Considering Length Matching

Liu Genggeng^{1, 2,},
Yu Yantao^{1, 2},
Zhou Ruping^{1, 2},
Wei Rongshan^3, ,,
Xu Ning⁴

1.
College of Computer and Data Science, Fuzhou University, Fuzhou 350116
2.
Fujian Key Laboratory of Network Computing and Intelligent Information Processing(Fuzhou University), Fuzhou 350116
3.
College of Physics and Information Engineering, Fuzhou University, Fuzhou 350108
4.
School of Information Engineering, Wuhan University of Technology, Wuhan 430070

Funds: This work was supported by the National Natural Science Foundation of China (62372109) and the Fujian Science Foundation for Distinguished Young Scholars (2023J06017).

More Information

Author Bio:
Liu Genggeng: born in 1988. PhD, professor, PhD supervisor, senior member of CCF. His main research interests include design automation for microfluidic biochips and integrated circuits

Yu Yantao: born in 2000. Master postgraduate, student member of CCF. His main research interests include physical design of rapid single-flux-quantum circuit and VLSI routing

Zhou Ruping: born in 1998. PhD candidate, student member of CCF. Her main research interests include VLSI routing, clock tree synthesis

Wei Rongshan: born in 1980. PhD, professor, PhD supervisor. His main research interests include intelligent sensor chip design, artificial intelligence chip design for deep learning and other applications

Xu Ning: born in 1968. PhD, professor, PhD supervisor, senior member of CCF. His main research interests include electronic design automation, design automation for integrated circuits and artificial intelligence

摘要

摘要:
由于快速单通量量子 (rapid single-flux-quantum, RSFQ)电路的高频特性，对电路的版图设计构成了巨大挑战. 针对RSFQ电路的高频特性带来的电路时延问题，可以在布线阶段通过使用延时元件如无源传输线来解决. 因为无源传输线的时延与它的长度近似成正比，且传输线的功耗不随着线长增加而增大，所以对于快速单通量量子电路而言长度匹配布线是一个非常重要的问题. 为此，提出了一种高效的考虑长度匹配的RSFQ电路布线算法，包括以下关键策略：1) 在生成初始路径时，提出了一种迂回布线的方法，在不改变初始布线空间的情况下，满足无源传输线的部分长度匹配；2) 提出了一种基于区域感知的迭代资源插入策略，减少需要添加的额外资源区域；3) 提出了一种考虑阻塞代价的长度匹配驱动布线策略，提高了对布线空间的资源利用. 实验结果表明所提算法与现有的多端布线算法相比，布线所需的区域面积减少了8%，运行时间减少了36%，从而取得快速且高质量的布线结果.
- 快速单通量量子电路 /
- 物理设计 /
- 时序匹配 /
- 长度匹配 /
- 通道布线
Abstract:
Because of the high frequency characteristics of rapid single-flux quantum circuits (RSFQ), it poses a great challenge to circuit layout design. In order to solve the circuit delay problem caused by the high frequency characteristics of RSFQ, delay elements such as passive transmission line can be used in the routing stage. The delay of a passive transmission line is roughly proportional to its length, and the power consumption of the passive transmission line does not increase with the increase of the wirelength, so length matching routing is a crucial problem for RSFQ circuits. Therefore, this paper proposes an efficient RSFQ circuit routing algorithm considering length matching, including the following key strategies: 1) when generating the initial path, a method of detour routing is presented to meet the partial length matching of passive transmission lines without changing the initial routing space; 2) an iterative resource insertion algorithm based on region-awareness is utilized to reduce the area of additional resources needed to be added; 3) a length-matching driven routing algorithm considering blocking cost is designed, which improves the resource utilization of routing space. Experimental results show that, compared with existing multi-terminal routing algorithms, the proposed algorithm reduces the area required for routing by 8% and the running time by 36%, thus achieving fast and high-quality routing results.
- rapid single-flux-quantum circuit /
- physical design /
- time matching /
- length matching /
- channel routing

HTML全文

图 1 SPL分配的对比

Figure 1. Comparison of SPL allocation

下载: 全尺寸图片幻灯片

图 2 算法流程图

Figure 2. Algorithm flowchart

下载: 全尺寸图片幻灯片

图 3 PTL切割及迂回布线

Figure 3. PTL cutting and detour routing

下载: 全尺寸图片幻灯片

图 4 迂回布线方案

Figure 4. Detour routing result

下载: 全尺寸图片幻灯片

图 6 布线区域扩展结果对比

Figure 6. Comparison of routing area expansion results

下载: 全尺寸图片幻灯片

图 5 资源分配及布线过程

Figure 5. Resource allocation and routing process

下载: 全尺寸图片幻灯片

图 7 插入位置的条件

Figure 7. Conditions for insertion position

下载: 全尺寸图片幻灯片

图 8 潜在可用单元利用情况

Figure 8. Utilization of potentially available units

下载: 全尺寸图片幻灯片

图 9 布线结果的对比

Figure 9. Comparison of routing result

下载: 全尺寸图片幻灯片

图 10 局部布线结果图

Figure 10. Local routing result

下载: 全尺寸图片幻灯片

图 11 运行时间对比

Figure 11. Comparison of run time

下载: 全尺寸图片幻灯片

表 1 多端线网测试用例详细信息

Table 1 Details of Test Cases for Multi-Terminal Nets

基准电路	布线区域高度	连接数量	最大延长长度/ 平均延长长度
RR0	356	83	0.00/0
RR1	356	91	21.91/46
RR2	356	99	28.26/56
RR3	356	103	40.78/130
RR4	356	105	94.02/252
RR5	356	99	128.30/370
RR6	356	50	67.60/346
Newb1	356	99	126.30/370
Newb2	356	106	91.01/252
Newb3	356	91	64.30/260
Newb4	356	50	113.15/554
Newb5	356	105	95.24/288

下载: 导出CSV

表 2 基于PTL切割转移策略对比结果

Table 2 Comparison Results of Strategies Based on PTL Cut and Shift

基准电路	布线区域宽度
基准电路	文献[15]	文献[17]	CAS(本文)
RR0	20	20	20
RR1	40	34	34
RR2	46	40	39
RR3	54	49	48
RR4	108	79	75
RR5	96	75	73
RR6	28	28	28
Newb1	97	78	74
Newb2	103	82	80
Newb3	54	50	47
Newb4	49	39	35
Newb5	102	82	78
比率	1.26	1.04	1.00

下载: 导出CSV

表 3 基于区域感知的迭代资源插入策略对比结果

Table 3 Comparison Results of Strategies Based on Area-Aware Iterative Resource Insertion

基准电路	布线区域宽度
基准电路	文献[15]	文献[17]	AIRI(本文)
RR0	20	20	20
RR1	40	34	37
RR2	46	40	37
RR3	54	49	49
RR4	108	79	75
RR5	96	75	73
RR6	28	28	29
Newb1	97	78	76
Newb2	103	82	80
Newb3	54	50	48
Newb4	49	39	36
Newb5	102	82	76
比率	1.25	1.03	1.00

下载: 导出CSV

表 4 阻塞感知的蜿蜒布线策略对比结果

Table 4 Comparison Results of Strategies Based on Blocking Aware Snaking Routing

基准电路	布线区域宽度
基准电路	文献[15]	文献[17]	BASR(本文)
RR0	20	20	20
RR1	40	34	34
RR2	46	40	40
RR3	54	49	46
RR4	108	79	75
RR5	96	75	75
RR6	28	28	27
Newb1	97	78	76
Newb2	103	82	78
Newb3	54	50	47
Newb4	49	39	35
Newb5	102	82	75
比率	1.27	1.04	1.00

下载: 导出CSV

表 5 多端线网布线结果对比

Table 5 Comparison of Routing Results for Multi-Terminal Nets

基准电路	布线区域宽度
基准电路	文献[15]	文献[17]	LMRouter(本文)
RR0	20	20	20
RR1	40	34	35
RR2	46	40	39
RR3	54	49	45
RR4	108	79	72
RR5	96	75	69
RR6	28	28	26
Newb1	97	78	72
Newb2	103	82	77
Newb3	54	50	45
Newb4	49	39	33
Newb5	102	82	73
比率	1.31	1.08	1.00

下载: 导出CSV

表 6 单端线网布线结果对比

Table 6 Comparison of Routing Results for Single-Terminal Nets

连接数量/ 布线区域高度	最大延长长度/ 平均延长长度	布线区域宽度
连接数量/ 布线区域高度	最大延长长度/ 平均延长长度	文献[15]	文献[17]	LMRouter(本文)
15/200	43/105	14	14	14
15/200	44/122	14	16	14
15/30	8/26	16	16	14
15/30	18/79	22	22	20
25/50	12/46	22	23	21
25/50	16/51	24	23	21
40/80	16/49	28	28	26
40/80	19/56	30	32	28
40/200	40/168	28	29	27
40/200	42/182	30	29	27
50/100	23/99	42	39	35
50/100	25/111	43	39	37
比率		1.10	1.08	1.00

下载: 导出CSV

参考文献(23)

[1]	何小威,乐大珩,郭维,等. 高性能自研处理器物理设计频率提升方法[J],计算机研究与发展2024,61(6):1429−1435 He Xiaowei, Yue Daheng, Guo Wei, et al. Promoting frequency method for our own high performance processor physical design[J]. Journal of Computer Research and Development, 2024, 61(6): 1429−1435(in Chinese)
[2]	Sato R, Hatanaka Y, Ando Y, et al. High-speed operation of random access-memory embedded microprocessor with minimal instruction set architecture based on rapid single-flux-quantum logic[J]. IEEE Transactions on Applied Superconductivity, 2017, 27(4): 1−5 doi: 10.1109/TASC.2017.2684059
[3]	Castellanos-Beltran M A, Olaya D I, Sirois A J, et al. Single-flux-quantum multiplier circuits for synthesizing gigahertz waveforms with quantum-based accuracy[J]. IEEE Transactions on Applied Superconductivity, 2021, 31(3): 1−9
[4]	Ando Y, Sato R, Tanaka M, et al. Design and demonstration of an 8-bit bit-serial RSFQ microprocessor: CORE e4[J]. IEEE Transactions on Applied Superconductivity, 2016, 26(5): 1−5
[5]	Fu Rongliang, Huang Junying, Wu Haibin, et al. JBNN: A hardware design for binarized neural networks using single-flux-quantum circuits[J], IEEE Transactions on Computers, 2022, 71(12): 3203−3214
[6]	Obata K, Takagi K, Takagi N. A clock scheduling algorithm for high-throughput RSFQ digital circuits[J]. IEICE Transactions on Fundamentals, 2008, 91(12): 3772−3782
[7]	Chen W, Rylyakov A V, Patel V, et al. Rapid single-flux-quantum T-flip flop operating up to 770 GHz[J]. IEEE Transactions on Applied Superconductivity, 1999, 9(2): 3212−3215 doi: 10.1109/77.783712
[8]	Katam N, Shafaei A, and Pedram M. Design of complex rapid single-flux-quantum cells with application to logic synthesis[C/OL]// Proc of the 16th Int Superconductive Electronics Conf. Piscataway, NJ: IEEE, 2017[2024-08-17]. https://ieeexplore.ieee.org/abstract/document/8314236
[9]	Kameda Y, Yorozu S, Hashimoto Y, A new design methodology for single-flux-quantum (SFQ) logic circuits using passive-transmission-line (PTL) wiring[J]. IEEE Transactions on Applied Superconductivity, 2017, 17(2): 508−511
[10]	Schindler L, Roux P l, Fourie C J. Impedance matching of passive transmission line receivers to improve reflections between RSFQ logic cells[J]. IEEE Transactions on Applied Superconductivity, 2020, 30(2): 1−7
[11]	Hashimoto Y, Yorozu S, Kameda Y, et al. Development of passive interconnection technology for SFQ circuits[J]. IEICE Transactions on Electronics[J], 2005, 88(2): 198−207
[12]	Ortlepp T, Uhlmann F H. Impedance matching of microstrip inductors in digital superconductive electronics[J]. IEEE Transactions on Applied Superconductivity, 2009, 19(3): 644−648 doi: 10.1109/TASC.2009.2019284
[13]	Jabbari T, Krylov G, Whiteley S, et al. Repeater insertion in SFQ interconnect[J]. IEEE Transactions on Applied Superconductivity, 2020, 30(8): 1−8
[14]	Tanaka M, OBATA K, lto Y, et al. Automated passive-transmission-line routing tool for single-flux-quantum circuits based on A* algorithm[J]. IEICE Transactions on Electronics, 2010, 93(4): 435−439
[15]	Kito N, Takagi K, Takagi N. Automatic wire-routing of SFQ digital circuits considering wire-length matching[J]. IEEE Transactions on Applied Superconductivity, 2016, 26(3): 1−5
[16]	Kito N, Takagi K, Takagi N. A fast wire-routing method and an automatic layout tool for RSFQ digital circuits considering wirelength matching[J]. IEEE Transactions on Applied Superconductivity, 2018, 28(4): 1−5
[17]	Kou Mingyang, Cheng Peiyi, Zeng Jun, et al, Splitter-aware multiterminal routing with length-matching constraint for RSFQ circuits[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2021, 40(11): 2251−2264
[18]	Kitamura K, Takagi K, Takagi N. A two-step routing method with wire length budgeting for PTL routing of SFQ logic circuits[J/OL]. Journal of Physics: Conference Series, 2020, 1590 [2024-08-17]. https://dx. doi.org/10.1088/1742-6596/1590/1/012043
[19]	Yan Jintai. Length-matching-constrained region routing in rapid single-flux-quantum circuits[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 40(5): 945−956
[20]	Yan Jintai. Via-minimization-oriented region routing under length-matching constraints in rapid single-flux-quantum circuits[J]. IEEE Transactions on Very Large Scale Integration Systems, 2021, 29(6): 1257−1270 doi: 10.1109/TVLSI.2021.3059786
[21]	Lin Tingru, Edwards T, Pedram M. qGDR: A via-minimization-oriented routing tool for large-scale superconductive single-flux-quantum circuits[J]. IEEE Transactions on Applied Superconductivity, 2019, 29(7): 1−12
[22]	Lin Tingru, Pedram M. Reducing the maximum length of connections in single-flux-quantum circuits during routing[C/OL]// Proc of IEEE Int Superconductive Electronics Conf. Piscataway, NJ: IEEE, 2019[2024-08-16]. https://ieeexplore.ieee.org/abstract/document/8990897
[23]	Oshimura T Y, Kuh E S. Efficient algorithms for channel routing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1982, 1(1): 25−35 doi: 10.1109/TCAD.1982.1269993

施引文献(2)

期刊类型引用(2)

1.	聂萌瑶，刘鑫. 考虑最大通信量的物联网群体访问路由算法. 计算机仿真. 2024(02): 415-419 . 百度学术
2.	陈淑平，李祎，何王全，漆锋滨. 胖树拓扑中高效实用的定制多播路由算法. 计算机研究与发展. 2022(12): 2689-2707 . 本站查看