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

Liu Genggeng; Yu Yantao; Zhou Ruping; Wei Rongshan; Xu Ning

doi:10.7544/issn1000-1239.202440065

Journal of Computer Research and Development > 2024 > Accepted Manuscript > DOI: 10.7544/issn1000-1239.202440065 CSTR: 32373.14.issn1000-1239.202440065

Liu Genggeng, Yu Yantao, Zhou Ruping, Wei Rongshan, Xu Ning. Rapid Single-Flux-Quantum Circuit Routing Algorithm Considering Length Matching[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440065

Citation:

PDF (1731 KB)

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
Received Date: February 01, 2024
Revised Date: October 15, 2024
Accepted Date: November 12, 2024
Available Online: November 18, 2024

Graphical Abstract

Abstract

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

FullText(HTML)

References (23)

References

[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

[1]	Peng Yingtao, Meng Xiaofeng, Du Zhijuan. Survey on Diversified Recommendation[J]. Journal of Computer Research and Development, 2025, 62(2): 285-313. DOI: 10.7544/issn1000-1239.202330600
[2]	MB-HGCN: A Hierarchical Graph Convolutional Network for Multi-behavior Recommendation“CCIR 2024推荐”[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440770
[3]	Zeng Weixin, Zhao Xiang, Tang Jiuyang, Tan Zhen, Wang Wei. Iterative Entity Alignment via Re-Ranking[J]. Journal of Computer Research and Development, 2020, 57(7): 1460-1471. DOI: 10.7544/issn1000-1239.2020.20190643
[4]	Dai Chenchao, Wang Hongyuan, Ni Tongguang, Chen Shoubing. Person Re-Identification Based on Deep Convolutional Generative Adversarial Network and Expanded Neighbor Reranking[J]. Journal of Computer Research and Development, 2019, 56(8): 1632-1641. DOI: 10.7544/issn1000-1239.2019.20190195
[5]	Gu Liang, Yang Peng, Dong Yongqiang. A Diversified Recommendation Method for UCL in Broadcast-Storage Network[J]. Journal of Computer Research and Development, 2017, 54(8): 1631-1643. DOI: 10.7544/issn1000-1239.2017.20170128
[6]	Meng Xiangfu, Bi Chongchun, Zhang Xiaoyan, Tang Xiaoliang, Tang Yanhuan. Web Database top-k Diverse Keyword Query Suggestion Approach[J]. Journal of Computer Research and Development, 2017, 54(7): 1577-1591. DOI: 10.7544/issn1000-1239.2017.20160005
[7]	Yu Wenzhe, Sha Chaofeng, He Xiaofeng, Zhang Rong. Review Selection Considering Opinion Diversity[J]. Journal of Computer Research and Development, 2015, 52(5): 1050-1060. DOI: 10.7544/issn1000-1239.2015.20131932
[8]	Wang Xianghai, Cong Zhihuan, Fang Lingling, Song Chuanming. HMM Training Model Using Blending Population Diversity Based Aaptive Genetic Algorithm Title[J]. Journal of Computer Research and Development, 2014, 51(8): 1833-1844. DOI: 10.7544/issn1000-1239.2014.20121211
[9]	Zhang Weiguo, Yin Xia, and Wu Jianping. A Computation Method of Path Diversity Based on AS Relationships[J]. Journal of Computer Research and Development, 2012, 49(1): 167-173.
[10]	Han Jianmin, Yu Juan, Yu Huiqun, Jia Jiong. A Multi-Level l-Diversity Model for Numerical Sensitive Attributes[J]. Journal of Computer Research and Development, 2011, 48(1): 147-158.

Cited By

Cited by

Periodical cited type(7)

1.	罗宇哲，李玲，侯朋朋，于佳耕，程丽敏，张常有，武延军，赵琛. 面向AIoT的协同智能综述. 计算机研究与发展. 2025(01): 179-206 . 本站查看
2.	王蕴，林霄，楼芝兰，李军，孙卫强. 面向边缘光算力网络的上行链路资源协同调度算法. 光通信技术. 2024(03): 45-51 .
3.	王铭源，王正国，李济顺，薛玉君. 层级式机械装备健康指数模型及管理系统构建. 金属矿山. 2024(09): 198-206 .
4.	王睿，王岩，尹朴，齐建鹏，孙叶桃，李倩，张易达，张梅奎. 面向边缘智能的协同训练研究进展. 工程科学学报. 2023(08): 1400-1416 .
5.	薛建强，史彦军，李波. 面向无人集群的边缘计算技术综述. 兵工学报. 2023(09): 2546-2555 .
6.	阴彦磊，王立华，廖伟智，张万达. 融合GRU-Attention与鲸鱼算法的流程制造工艺参数云边联动优化. 计算机集成制造系统. 2023(09): 2991-3005 .
7.	许浩，朱晓娟. SDN中基于模型划分的云边协同推理算法. 兰州工业学院学报. 2023(06): 31-37 .