NEMO: A new implicit connection graph-based gridless router with multi-layer planes and pseudo-tile propagation

This study presents a new multilayer implicit connection graph-based gridless router called NEMO. Unlike the first implicit connection graph-based router that embeds all routing layers onto a routing plane, NEMO constructs a routing plane for each routing layer. Furthermore, each routing plane is composed of tiles, not an array of grid points as well as their connecting edges, and, consequently, the complexity of routing problem decreases. Each grid then exactly represents one tile (its left bottom corner), and grid maze becomes tile propagation; moreover, to further speedup in path searching, continuous space tiles are combined as a pseudo maximum horizontally or vertically stripped tile. Experimental results indicate that NEMO conducts point-to-point path searching on about 10 times faster than the implicit connection graph-based router. Full-chip routing by NEMO also outperforms all multi-level gridless routers with about 1.45X to 2.42X runtime speedups.