JRouter: A Multi-Terminal Hierarchical Length-Matching Router under Planar Manhattan Routing Model for RSFQ Circuits

Abstract

Superconducting rapid single-flux-quantum (RSFQ) logic has shown great potential for high-energy-efficient computing systems. To ensure correct operations at ultra-high frequencies, it is necessary to incorporate length-matching constraints into the routing problem. Existing routing algorithms, however, can only address 2-pin connections or support the conventional horizontal/vertical routing model, which substantially limits the optimization space for routing solutions. This paper presents JRouter, an RSFQ router that considers the two-layer planar Manhattan routing model while simultaneously coping with splitter (SPL) placement and length-matching multi-terminal routing. JRouter contains a track-assignment-based initial routing that minimizes the initial routing width while avoiding conflicts in the horizontal constraint graph. Moreover, JRouter implements an SPL-tree-based hierarchical routing with an iterative maximum-flow-based formulation to insert the detours for multi-terminal routing. A routing region extension algorithm is also developed to insert the detours for unsatisfied connections. According to the experimental results, JRouter achieves an average routing width reduction of 35.71% and 22.46% on a 16-bit RSFQ Sklansky adder compared to Kito’s and Kou’s routing algorithms. For randomly generated benchmarks, JRouter reduces the routing width by an average of 38.77%, 38.20%, 21.65%, and 7.01% compared to Kito’s, Kou’s, and two of Yan’s routing algorithms, respectively, while maintaining reasonable runtime.

Publication
Proceedings of the 2023 on Great Lakes Symposium on VLSI