CHiRPS: a general-area parallel multilayer routing system

A new, highly parallel model for concurrent multilayer routing, called CHiRPS (Configurable Highly Routable Parallel System), is presented. The nucleus of CHiRPS is a very flexible pathfinder that can be easily configured, even in the presence of obstacles, to generate various commonly used pattern-based routes, such as Steiner trees with single trunk, comb trees, contour-based routes, etc., that span multiple layers simultaneously. The authors employ the concept of a total grid-graph to capture the state of the routing region. The main steps of the pathfinder are based on new parallel algorithms for cycle detection, cycle elimination and tree reduction. The proposed algorithms scale well with increased problem sizes since they require only O(log N) time when given a grid-graph with up to N² nodes. As such, they are good candidates for massively data-parallel machines