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 > 2025 > 62(5): 1151-1163. > 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, 2025, 62(5): 1151-1163. DOI: 10.7544/issn1000-1239.202440065

Citation:

PDF (1729 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. Distinguished member of CCF. His main research interests include design automation for microfluidic biochips and integrated circuits

Yu Yantao: born in 2000. Master candidate. Student member of CCF. His main research interest includes VLSI routing

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

Wei Rongshan: born in 1980. PhD, professor, PhD supervisor. His main research interests include intelligent sensor chip design, and 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

The high frequency characteristics of rapid single-flux-quantum (RSFQ) circuits 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, we propose 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, 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, 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]. Journal of Physics: Conference Series, 2020, 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]	Wu Zehui, Wei Qiang, Wang Xinlei, Wang Yunchao, Yan Chenyu, Chen Jing. Survey of Automatic Software Vulnerability Exploitation[J]. Journal of Computer Research and Development, 2024, 61(9): 2261-2274. DOI: 10.7544/issn1000-1239.202220410
[2]	Li Jinpeng, Zhang Chuang, Chen Xiaojun, Hu Yue, Liao Pengcheng. Survey on Automatic Text Summarization[J]. Journal of Computer Research and Development, 2021, 58(1): 1-21. DOI: 10.7544/issn1000-1239.2021.20190785
[3]	Ma Yanchun, Liu Yongjian, Xie Qing, Xiong Shengwu, Tang Lingli. Review of Automatic Image Annotation Technology[J]. Journal of Computer Research and Development, 2020, 57(11): 2348-2374. DOI: 10.7544/issn1000-1239.2020.20190793
[4]	Xie Juanying, Hou Qi, Shi Yinghuan, Lü Peng, Jing Liping, Zhuang Fuzhen, Zhang Junping, Tan Xiaoyang, Xu Shengquan. The Automatic Identification of Butterfly Species[J]. Journal of Computer Research and Development, 2018, 55(8): 1609-1618. DOI: 10.7544/issn1000-1239.2018.20180181
[5]	Ling Jimin, Zhang Li. An Approach to Automatically Build Customizable Reference Process Models[J]. Journal of Computer Research and Development, 2017, 54(3): 642-653. DOI: 10.7544/issn1000-1239.2017.20151047
[6]	You Feng, Zhao Ruilian, Lü Shanshan. Output Domain Based Automatic Test Case Generation[J]. Journal of Computer Research and Development, 2016, 53(3): 541-549. DOI: 10.7544/issn1000-1239.2016.20148045
[7]	Hao Fanchang, Luan Junfeng, Zhu Daming, Zhang Peng, and Li Ming. A Faster Algorithm for Sorting Genomes by Reciprocal Translocation, Insertion and Deletion[J]. Journal of Computer Research and Development, 2010, 47(11): 2011-2023.
[8]	Ma Peijun, Wang Tiantian, and Su Xiaohong. Automatic Grading of Student Programs Based on Program Understanding[J]. Journal of Computer Research and Development, 2009, 46(7): 1136-1142.
[9]	Shi Yuliang, Huang Guang'an, Ye Wei, Zhang Liang, Shi Baile. Automatic Composition of Web Services Based on Task Dependency Specification[J]. Journal of Computer Research and Development, 2006, 43(12): 2110-2116.
[10]	Wang Zhiming, Cai Lianhong, Ai Haizhou. Automatic Estimation of Visual Speech Parameters[J]. Journal of Computer Research and Development, 2005, 42(7): 1185-1190.