Placement plays a crucial role in modern chip design, aiming to determine the positions of circuit blocks (macros and standard cells). Traditional data structure-centric heuristics often yield suboptimal placement prototypes, ineffectively guiding downstream mixed-size analytical placement to find the desired results for modern large-scale designs. Recent works have showcased the potential of reinforcement learning (RL) to enhance chip placement by training a policy to place macros as a board game. However, placing macros and fixing them in the earlier stages without sufficient information often incurs undesired solutions. This paper proposes a novel RL-based mixed-size placer with iteratively moving the blocks to characterize dense rewards and comprehensive layout information in each step. We further introduce a semi-concurrent moving mechanism to learn the collaborative dynamics among actions on a subset of blocks at each step. We integrate continuous action spaces to develop a deep Q network-based model for learning the semi-concurrent moving policy to derive the proposed moving strategy. Compared with the state-of-the-art methods, experimental results show that our RL-based placer achieves the best placement quality based on commonly used mixed-size placement benchmarks.

Global routing is a critical stage in the VLSI design flow, aiming to provide a robust guide for detailed routing and serve as early design feedback for placement. Many approaches have leveraged GPU parallelization to achieve significant acceleration. However, with the fast-growing complexity of modern large-scale designs, recent GPU-accelerated maze routing algorithms, driven by the sweep operation, struggle to find solutions efficiently with limited GPU memory resources. In order to address this issue, this paper proposes a scalable, GPU-friendly sweep-based maze routing that requires significantly less memory and fewer kernel function calls while accelerating overall runtime. We introduce a sweep-sharing technique that allows multiple nets to be routed simultaneously within a single sweeping process, substantially reducing memory consumption and kernel launching overhead. We further propose an edge-level rip-up-andreroute technique that selectively reroutes only overflowed segments, preserving feasible parts of the solution to reduce runtime substantially. Experimental results on the latest ISPD’24 Contest benchmarks demonstrate that our GPUfriendly maze routing with sweep sharing can significantly improve the efficiency of the state-of-the-art GPU-accelerated maze router.

In modern heterogeneous integration technologies, chips with different processes and functionality are integrated into a package with high interconnection density and large I/O counts. Integrating multiple chips into a package may suffer from severe warpage problems caused by the mismatch in coefficients of thermal expansion between different manufacturing materials, leading to deformation and malfunction in the manufactured package. The industry is eager to find a solution for warpage optimization. This paper proposes the first warpage-aware floorplanning algorithm for heterogeneous integration. We first present an efficient qualitative warpage model for a multi-chip package structure based on Suhir's solution, more suitable for optimization than the time-consuming finite element analysis. Based on the transitive closure graph floorplan representation, we then propose three perturbations for simulated annealing to optimize the warpage more directly and can thus speed up the process. Finally, we develop a force-directed detailed floorplanning algorithm to further refine the solutions by utilizing the dead spaces. Experimental results demonstrate the effectiveness of our warpage model and algorithm.

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.

In modern packaging technology, redistribution layers (RDLs) are often used to redistribute interconnections among multiple chips and between I/O pads and bump pads. For high-density RDL routing, irregular vias, where vias can be placed at arbitrary locations, are adopted to better utilize RDL resources to obtain desired routing solutions. As the problem size increases, however, using irregular vias may suffer from high computation overheads. Moreover, most previous works route pre-assignment (PA) and free-assignment (FA) nets in separate stages, incurring routing resource competition. To remedy these disadvantages, we propose a simultaneous PA and FA routing framework with irregular RDL via planning. In this paper, we first propose a novel partitioning method based on the Voronoi diagram to handle irregular via structures and derive a theoretical upper bound on the number of generated regions. We then propose a chord-based tile model and a net-sequence list to generate non-crossing guides for PA and FA nets on the same routing graph. Finally, we develop a novel geometry-based pattern routing to obtain the final solutions. Experimental results show that our work can achieve 100% routability and an average 30X speedup over the-state-of-the-art work.

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.