The integrated fan-out (InFO) wafer-level chip-scale package (WLCSP) is introduced for modern system-in-package designs with larger I/O counts, higher interconnection density, and small form factors. A redistribution layer (RDL) in an InFO package is an extra metal layer for interchip connections, and RDL routing is crucial for achieving desired interchip connections. In a high-density InFO package, multiple RDLs with flexible vias are often adopted. To integrate chips of different technology nodes into one package, irregular pad structures need to be considered; however, no published RDL routing work considers flexible vias or irregular pad structures. This article formulates a new RDL routing problem with unified-assigned pad pairs on a via-based multilayer multichip InFO package with irregular pad structures and presents the first algorithm for this problem. The algorithm consists of a preprocessing stage, three routing stages, and a layout optimization stage. The preprocessing stage analyzes routing resources and potential routing congestion. The first routing stage performs layer assignment based on a weighted maximum planar subset of chords algorithm to route interchip nets concurrently. The second routing stage constructs a 3-D routing graph based on partitioned octagonal tiles to handle the irregular layout structure and applies A*-search to route remaining interchip nets. The third routing stage transforms a routing graph into a network-flow model to perform concurrent routing for chip-to-board nets by applying the minimum-cost maximum-flow algorithm. Finally, we develop an efficient linear-programming-based layout optimization algorithm to find desired solutions. Experimental results show that our router can achieve 100% routablility for all benchmarks under limited RDLs, while the previous state-of-the-art work cannot.

The integrated fan-out (InFO) wafer-level chip-scale package is introduced for modern system-in-package designs with larger I/O counts and higher interconnection density. A redistribution layer (RDL) in an InFO package is an extra metal layer for inter-chip connections. To achieve flexible and compact inter-chip connections, the RDL routing problem for InFO packages has become a crucial problem for modern electronic designs. In advanced high-density InFO packages, multiple RDLs with flexible vias are often adopted. On the other hand, to integrate chips of different technology nodes into one package, irregular pad structures need to be considered. To our best knowledge, however, there is no published work for RDL routing considering flexible vias or irregular pad structures. In this paper, we present the first work to handle the routing problem with pre-assigned pad pairs (i.e., the hardest pre-assignment routing problem) on the via-based multi-chip multi-layer InFO package with irregular pad structures. We first propose a layer assignment method based on a weighted maximum planar subset of chords algorithm to concurrently route as many inter-chip nets as possible. We then propose an octagonal tile model with a layout partitioning method to tackle increasingly popular irregular structures. Finally, we develop an efficient linear-programming-based layout optimization algorithm to find solutions with high-quality wirelength and via arrangements. Experimental results demonstrate the effectiveness and robustness of our algorithm.

A robust redistribution layer (RDL) router is required for advanced package designs, where the length-matching constraint for a group of nets needs to be considered to preserve good timing properties at the package level. For area-I/O flip-chip design with pre-assigned nets on RDLs, we propose the first group-based length-matching routing framework that can simultaneously minimize the wirelengths of an arbitrary group of nets with and without equal-length constraints, based on an equal-length-aware A*-search algorithm and a bounded sliceline grid (BSG) snaking one. For the irregular structure of the area-I/O flip-chip design, we apply Delaunay triangulation and Voronoi diagram to model the routing resources more precisely. To effectively consider the equal-length constraints in the earlier stage, we first profile the routing resource to obtain an approximation of the longest net, and then adopt the equal-length-aware A*-search algorithm to extend shorter nets to match the estimated longest net. A BSG-based snaking method is then applied to meet the equal-length constraint, while preserving the minimized wirelength of unconstrained nets. Experimental results demonstrate that our framework can solve all benchmarks effectively and efficiently.

As Engineering Change Order (ECO) has attracted substantial attention in modern VLSI design, the open net problem, which aims at constructing a shortest obstacle-avoiding path to reconnect the net shapes in an open net, becomes more critical in the ECO stage. This paper addresses a multi-layer obstacle-avoiding region-to-region Steiner minimal tree (SMT) construction problem that connects all net shapes by edges on a layer or vias between layers, and avoids running through any obstacle with a minimal total cost. Existing multi-layer obstacle-avoiding SMT algorithms consider pin-to-pin connections instead of region-to-region ones, which would limit the solution quality due to its lacking region information. In this paper, we present an efficient algorithm based on our new multi-layer obstacle-avoiding region-to-region spanning graph to solve the addressed problem, which guarantees to find an optimal solution for a net connecting two regions on a single layer. Experimental results show that our algorithm outperforms all the participating routers of the 2017 CAD Contest at ICCAD in both solution quality and runtime.