an algorithm for routing with capacitance/distance constraints for clock distribution in microprocessors
In modern microprocessors, clocks are usually distributed employing a hybrid network, grid followed by buffered trees, to restrict the skew. This is typically done employing (gated) buffered trees inside the blocks, while the global grid overlay the entire die area. The block-level buffered trees are connected to the grid at specific locations, by routing the wires along the predetermined tracks. The routing of these clock wires, which consume noticeable power, have distance and capacitance constraints to avoid poor slopes at the inputs of the block-level buffers. Moreover, these wires also contribute to significant load on the clock grid. This leads to a problem of capacitance or wirelength minimization during the multi-terminal routing such that wires use pre-specified tracks and routes obey distance and capacitance constraints, i.e. , the length of the route from any receiver to a connection on the grid-wire has less than the specified distance and the overall capacitance due to all receivers on the route is less than the given limit. Since the problem is intractable, we present an efficient algorithm that completes the routing connecting 1000s of terminals over a few $mm^2$ area in seconds, improving the wirelength by 17\% over the commonly used nearest source heuristic. The algorithm is employed to perform post-grid clock distribution in a 45 nm technology microprocessor.
routing clock distribution power