CHIRPS - A GENERAL-AREA PARALLEL MULTILAYER ROUTING SYSTEM

A new highly parallel model for concurrent multilayer routing, called CHiRPS, is presented. The nucleus of CHiRPS is a very flexible pathfin der that can be easily configured, even in the presence of obstacles, to generate various commonly used pattern-based routes, such as Steine r trees with single trunk, comb trees, contour-based routes, etc., tha t 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 al gorithms scale well with increased problem sizes since they require on ly O(log(N)) time when given a grid-graph with up to N-2 nodes. As suc h they are good candidates for massively data-parallel machines.