A High-Performance Ordered Routing Algorithm for Large-Scale WLCSP with Multi-Capacity

The redistribution layer ordered routing is a critical problem in fan-out wafer-level chip-scale packaging (WLCSP) design. Traditional integer linear programming (ILP) method is inefficient in dealing with the ordered routing problem of multiple-capacity. Hence, we propose a high-performance ordered routing algorithm to solve the multiple-capacity ordered routing problem on the redistribution layer (RDL). First, we transform the ordered routing problem into the min-cost multi-commodity flow (MMCF) problem and use the linear programming (LP) method to solve it. Then, we use depth-first search (DFS) to process the LP method flow results and obtain the pre-assignment I/O candidate paths. Finally, the candidate path set obtains legal routing results by setting the crossing weight and a heuristic algorithm to receive the minimum crossing weight. When the pre-assignment I/Os routing is uncompleted, we will set the capacity of tile nodes and edges to 0 and perform iterative routing for better results. Compared with the state-of-the-art work, experimental results show that our algorithm can solve twice the scale of the RDL ordered routing problems and reduce the routing time by 17% when dealing with multi-capacity RDL ordered routing problems.