Package design has become increasingly complex with the evolution of technology nodes and heterogeneous integration. To optimize timing performance and signal integrity, it is essential to separate different pairs of geometrically adjacent nets with distinct spacing values, which is referred to as the paired-spacing constraint. This paper presents the first free-assignment package routing algorithm flow considering the paired-spacing constraint. To minimize the routing resource demand and overall wirelength, we propose a dynamic programming-based net ordering method to maximize the number of nets with the same/similar spacing rules positioned next to each other. In addition, the free-assignment routing problem is elegantly solved with a minimum-cost maximum-flow problem on a delicately designed graph model. Experimental results show that the proposed flow can achieve 100% routability for the adopted industrial-modified benchmarks. In contrast, even with modifications to superficially consider paired spacings, a classic model experiences significant routability degradation.

Lamellar directed self-assembly (DSA) technology in combination with the self-aligned via (SAV) process has emerged as a novel and promising choice for via/contact layer fabrication, where a via between Metal-$x$and Metal-$(x+1)$is generated at the intersection of a wire segment on Metal-$(x+1)$and a rectangular and perpendicular guiding template. Compared to the highly investigated cylindrical DSA, lamellar DSA does not suffer from the overlay error of generated holes and thus can have better yield, and it also benefits from the better flexibility of various via pitches a single template can produce. A state-of-the-art work has addressed the guiding template design problem for the new process, and an integer linear programming (ILP) formulation that can optimally solve the problem as well as a simple heuristic approach are proposed. However, solving the ILP formulation is time consuming, and the heuristic method suffers from unignorable degradation in solution quality due to several algorithm deficiencies. In this article, we propose an enhanced and efficient template design algorithm flow for the lamellar DSA and SAV process by using graph monomorphism for pattern conflict check in multiple patterning lithography. Experimental results show that the proposed flow can greatly reduce the numbers of conflicts and short templates and is almost as efficient as the existing heuristic approach.