Abstract Body

Routing of wires is an essential step in the layout design of an RSFQ logic circuit. There are many wires in RSFQ circuits because each logic gate has clock inputs. Wires consume a large amount of a chip area. A wire between logic cells is implemented with two types of interconnects, i.e., Josephson transmission lines (JTLs) and passive transmission lines (PTLs) in RSFQ logic circuits. PTLs are finer than JTLs using active devices. Developing fine PTLs has been actively pursued to realize dense RSFQ chips. However, JTLs are essential for timing tuning to obtain a layout satisfying timing constraints and are effective for implementing short-distance wires, especially for a signal wire with multiple fanouts using splitters.

JTLs are implemented by tiling, in other words, placing while avoiding overlapping, various pre-designed JTL cells whose width and height are multiples of unit length in cell-based design flows such as the flow with the CONNECT cell library [1]. The tiling of cells is mainly performed by hand currently. There are several combinations of cells for implementing JTLs. Selecting appropriate JTL cells for implementing a wire on a path between logic cells is a complicated task. Examining various implementations of cell placements is hard, and choosing the optimal one from various implementations is costly. Design automation is crucial to ease the layout design and obtain a high-quality design. However, the method has yet to be discussed.

We propose a method for tiling appropriate JTL cells automatically for a set of paths. The problem is formulated as an instance of integer linear programming (ILP), which is a problem to find assignments of integer variables for minimizing or maximizing the value of the target linear function under constraint linear formulas. With the help of a solver program, instances can be solved. There are various open-source and commercial solver programs for solving instances of ILP. The method lists all possible and consistent JTL cells for each grid on given paths as the method’s input. Then, it generates constraint formulas for determining a JTL cell for each grid while avoiding overlapping cells. It also generates the objective linear function. The number of Josephson junctions for JTLs, delay of paths, or weighted sum of such parameters is represented as a linear function and can be used for the objective function.

We implemented the method and evaluated it. We employed an open-source program, lp_solve, as the ILP solver for the evaluation. The proposed method had performed JTL cell-tiling for several circuits, including a full adder. The runtime of the solver was short.

References

[1] S. Yorozu, Y. Kameda, H. Terai, A. Fujimaki, T. Yamada, S. Tahara, “A single flux quantum standard logic cell library,” Physica C: Superconductivity, vol. 378-381, Part 2, pp. 1471-1474, 2002.

Acknowledgment

This work was supported by JSPS KAKENHI Grant Number: JP22K11961.