A Redistribution Layer PA Routing Algorithm for InFO Packages Based on Triangular Grid

The redistribution layer (RDL) routing plays a vital role in InFO packages. Previous work using a tile model could only partially utilize the routing space. This paper proposes an efficient algorithm based on triangular grid to utilize the routing space better and improve the routability. We first determine the connection of all multi-pad nets by minimum spanning tree and split chip clusters by minimum weight vertex coverage for potential congestion mitigation. Then, we transform the routing problem into a network flow problem by constructing a triangular grid-based graph to maximize the use of space and apply an improved Minimum Cost Maximum Flow algorithm to find flow paths in a relatively short time. Finally, we decompose the network flow results to avoid crossing the paths and map them on the average grid to optimize routing results by eliminating acute angles. Experimental results show that our algorithm reduces the runtime by 27.2% compared to Cadence Allegro.