Length-Matching-Constrained Chip Routing for via Minimization in RSFQ Circuits

It is known that the row-based placement in a rapid single-flux-quantum (RSFQ) circuit can be constructed for a given set of logic cells. In this paper, given a set of 2-pin nets with their extension lengths in a PTL routing plane, based on the introduction of a minimal set of used vias for SFQ pulse integrity, an efficient length-matching-constrained routing algorithm can be proposed for via minimization in a PTL routing plane. Firstly, based on the routability consideration of the routing nets on two available layers and the construction of a routability graph, the detouring-points and vias can be assigned onto some nets on X-type or Z-type intersections under non-detouring constraints. Furthermore, based on the result of the net grouping inside some extracted regions, the full or partial nets inside the extracted regions on two available layers can be routed by using one river-routing or maze-routing process. Finally, based on the extension lengths of the unsatisfied nets, the zigzag detouring-paths can be inserted into the available areas on two available layers to satisfy the length-matching constraints on the unsatisfied nets. Compared with the open-source routing tool, Qrouter, and Lin's routing algorithm, qGDR, in chip routing for via minimization, our proposed routing algorithm can improve 2.7% and 2.0% of routability ratio, decrease 61.0% and 43.5% of the number of the used vias, and decrease 2.7% and 1.7% of the average length of the routed nets with no length-matching constraint in less CPU time for 8 tested circuits on the average, respectively. In addition, our proposed routing algorithm only increases 2.0% of the total length of the routed nets with length-matching constraints for 8 tested circuits on the average.