Simultaneous Pre-and Free-assignment Routing for Multiple Redistribution Layers with Irregular Vias

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. ? 2021 IEEE.