octilinear redistributive routing in bump arrays
This paper proposes a scheme for automatic re-distribution layer (RDL) routing, which is used in chip-package connections. Traditional RDL routing designs are mostly performed manually because the wire geometries are more flexible and therefore more difficult to handle on RDL than on chip. For example, octilinear routing is manufacturable in RDL and is widely adopted due to its higher efficiency than Manhattan routing. In this paper we devise a polynomial time octilinear RDL routing algorithm based on a grid network embedded in the bump array. The grid network is constructed to fully utilize the routing space as well as avoid any spacing violation. Detailed routing solution can be obtained following the min-cost max-flow in the network. Experimental results show the effectiveness of our router.
network flow 8-geometry interchangeability routing grid