A method, computer program product, and data processing system for automatically
designing routing paths in an integrated circuit is disclosed. The present invention
allows for the design of paths that are optimal in terms of the signal delay in
circuits that may require registers for signal to travel over multiple clock cycles
or in circuits that may contain multiple clock domains.
An integrated circuit die is modeled as a weighted grid graph in which the edges
represent wire segments and the weights represent the delays associated with those
wire segments. Designing for optimum delay involves finding a shortest path between
two vertices in the grid graph using a modified single-source shortest path algorithm.
Registers, buffers, and dual-clock domain synchronizers are modeled according to
a labeling function that assigns components to selected vertices in the routing
path for optimal results.
