Routing using a pyramid data structure

A general-purpose routing algorithm is proposed. Ideas behind both the maze-running algorithm and the hierarchical routing algorithm are combined into a hybrid routing algorithm. The new algorithm demonstrates a speed compatible to a hierarchical router and produces routings with quality equivalent to that by a maze router. Hybrid routing is based on the maze-running method with a third search dimension added. The extra search space is built by recursively constructing a hierarchy of coarser grid meshes. A user-given parameter can turn this algorithm into a pure maze router, a pure hierarchical router, or a wide spectrum of hybrid routers with different speed/quality characteristics between the extremes. With this approach, it is possible to handle easily a routing of large size, such as those encountered in the sea-of-gate layout.<>