US Patent 7707536 V-shaped multilevel full-chip gridless routing

A router organizes an IC area into an array of global routing cells (GRCs) and generates a congestion map providing a separate congestion factor for each GRC boundary. The router then iteratively partitions the IC area into progressively smaller tiles while selecting a route for each net passing between tiles when possible without altering any previously routed net. The router thereafter iteratively merges the tiles into progressively larger tiles while selecting a route for each previously unrouted net residing wholly within a single tile, altering routes of previously routed nets when necessary to accommodate the selected route. When selecting each route for any connection of a net, the router seeks to minimize a cost function of congestion factors of all GRC boundaries.