A generalization of Dijkstra’s shortest path algorithm with applications to VLSI routing.

*(English)*Zbl 1176.90612Summary: We generalize Dijkstra’s algorithm for finding shortest paths in digraphs with non-negative integral edge lengths. Instead of labeling individual vertices we label subgraphs which partition the given graph. We can achieve much better running times if the number of involved subgraphs is small compared to the order of the original graph and the shortest path problems restricted to these subgraphs is computationally easy.

As an application we consider the VLSI routing problem, where we need to find millions of shortest paths in partial grid graphs with billions of vertices. Here, our algorithm can be applied twice, once in a coarse abstraction (where the labeled subgraphs are rectangles), and once in a detailed model (where the labeled subgraphs are intervals). Using the result of the first algorithm to speed up the second one via goal-oriented techniques leads to considerably reduced running time. We illustrate this with a state-of-the-art routing tool on leading-edge industrial chips.

As an application we consider the VLSI routing problem, where we need to find millions of shortest paths in partial grid graphs with billions of vertices. Here, our algorithm can be applied twice, once in a coarse abstraction (where the labeled subgraphs are rectangles), and once in a detailed model (where the labeled subgraphs are intervals). Using the result of the first algorithm to speed up the second one via goal-oriented techniques leads to considerably reduced running time. We illustrate this with a state-of-the-art routing tool on leading-edge industrial chips.

##### MSC:

90C35 | Programming involving graphs or networks |

90B10 | Deterministic network models in operations research |

90B20 | Traffic problems in operations research |

PDF
BibTeX
XML
Cite

\textit{S. Peyer} et al., J. Discrete Algorithms 7, No. 4, 377--390 (2009; Zbl 1176.90612)

Full Text:
DOI

##### References:

[1] | Albrecht, C., Global routing by new approximation algorithms for multicommodity flow, IEEE transactions on computer aided design of integrated circuits and systems, 20, 622-632, (2001) |

[2] | Bast, H.; Funke, S.; Matijevic, D.; Sanders, P.; Schultes, D., In transit to constant time shortest-path queries in road networks, () |

[3] | S. Batterywala, N. Shenoy, W. Nicholls, H. Zhou, Track assignment: A desirable intermediate step between global routing and detailed routing, in: Proc. IEEE International Conference on Computer Aided Design, 2002, pp. 59-66 |

[4] | R. Bauer, D. Delling, SHARC: Fast and robust unidirectional routing, in: Proc. 10th International Workshop on Algorithm Engineering and Experiments (ALENEX’08), pp. 13-26 · Zbl 1284.05264 |

[5] | R. Bauer, D. Delling, D. Wagner, Experimental study on speed-up techniques for timetable information systems, in: Proc. 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2007) |

[6] | Cherkassky, B.V.; Goldberg, A.V.; Radzik, T., Shortest paths algorithms: theory and experimental evaluation, Math. prog., 73, 129-174, (1996) · Zbl 0853.90111 |

[7] | Cong, J.; Fang, J.; Khoo, K., DUNE — A multilayer gridless routing system, IEEE transactions on computer-aided design of integrated circuits and systems, 20, 633-647, (2001) |

[8] | Cong, J.; Fang, J.; Xie, M.; Zhang, Y., MARS — A multilevel full-chip gridless routing system, IEEE transactions on computer-aided design of integrated circuits and systems, 24, 382-394, (2005) |

[9] | Demetrescu, C.; Goldberg, A.V.; Johnson, D.S., Implementation challenge for shortest paths, (), 395-398 |

[10] | Dijkstra, E.W., A note on two problems in connexion with graphs, Numerische Mathematik, 1, 269-271, (1959) · Zbl 0092.16002 |

[11] | Doran, J., An approach to automatic problem-solving, Machine intelligence, 1, 105-127, (1967) |

[12] | Fredman, M.L.; Tarjan, R.E., Fibonacci heaps and their uses in improved network optimization problems, Journal of the ACM, 34, 596-615, (1987) |

[13] | Gallo, G.; Pallottino, S., Shortest paths algorithms, Annals of operations research, 13, 3-79, (1988) |

[14] | Goldberg, A.V., A simple shortest path algorithm with linear average time, (), 230-241 · Zbl 1007.05088 |

[15] | A.V. Goldberg, C. Harrelson, Computing the shortest path: A* search meets graph theory, in: Proc. 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 156-165 · Zbl 1297.05230 |

[16] | Hart, P.E.; Nilsson, N.J.; Raphael, B., A formal basis for the heuristic determination of minimum cost paths in graphs, IEEE transactions on systems science and cybernetics, SSC, 4, 100-107, (1968) |

[17] | A. Hetzel, A sequential detailed router for huge grid graphs, in: Proc. Design, Automation and Test in Europe (DATE 1998), pp. 332-339 |

[18] | W. Heyns, W. Sansen, H. Beke, A line-expansion algorithm for the general routing problem with a guaranteed solution, in: Proc. 17th Design Automation Conference, 1980, pp. 243-249 |

[19] | D.W. Hightower, A solution to line-routing problems on the continuous plane, in: Proc. 6th Design Automation Conference, 1969, pp. 1-24 |

[20] | Hoel, J.H., Some variations of Lee’s algorithm, IEEE transactions on computers, 25, 19-24, (1976) · Zbl 0329.68040 |

[21] | Holzer, M.; Schulz, F.; Wagner, D.; Willhalm, T., Combining speed-up techniques for shortest-path computations, Journal of experimental algorithmics (JEA), 10, 1-18, (2005) · Zbl 1140.68552 |

[22] | Hu, J.; Sapatnekar, S.S., A survey on multi-net global routing for integrated circuits, Integration the VLSI journal, 31, 1-49, (2001) · Zbl 0995.68197 |

[23] | J. Humpola, Schneller Algorithmus für kürzeste Wege in irregulären Gittergraphen, Diploma Thesis, University of Bonn, 2009 |

[24] | Klunder, G.A.; Post, H.N., The shortest path problem on large-scale real-road networks, Networks, 48, 182-194, (2006) · Zbl 1148.90346 |

[25] | Köhler, E.; Möhring, R.H.; Schilling, H., Acceleration of shortest path and constrained shortest path computation, (), 126-138 · Zbl 1121.90413 |

[26] | Korte, B.; Rautenbach, D.; Vygen, J., Bonntools: mathematical innovation for layout and timing closure of systems on a chip, Proc. of the IEEE, 95, 555-572, (2007) |

[27] | Lauther, U., An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background, (), 219-230 |

[28] | Lee, C.Y., An algorithm for path connections and its application, IRE transactions on electronic computing, 10, 346-365, (1961) |

[29] | Li, Y.-L.; Chen, H.-Y.; Lin, C.-T., NEMO: A new implicit-connection-graph-based gridless router with multilayer planes and pseudo tile propagation, IEEE transactions on computer-aided design of integrated circuits and systems, 26, 705-718, (2007) |

[30] | Margarino, A.; Romano, A.; De Gloria, A.; Curatelli, Francesco; Antognetti, P., A tile-expansion router, IEEE transactions on CAD of integrated circuits and systems, 6, 507-517, (1987) |

[31] | U. Meyer, Single-source shortest paths on arbitrary directed graphs in linear average time, in: Proc. 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2001, pp. 797-806 · Zbl 0988.05088 |

[32] | Möhring, R.H.; Schilling, H.; Schütz, B.; Wagner, D.; Willhalm, T., Partitioning graphs to speed up Dijkstra’s algorithm, (), 189-202 · Zbl 1121.68356 |

[33] | Pohl, I., Bi-directional search, Machine intelligence, 6, 124-140, (1971) · Zbl 0263.68021 |

[34] | Rubin, F., The Lee path connection algorithm, IEEE transactions on computers, C-23, 907-914, (1974) · Zbl 0291.90071 |

[35] | Sanders, P.; Schultes, D., Highway hierarchies hasten exact shortest path queries, (), 568-579 · Zbl 1162.68505 |

[36] | Schulz, F.; Wagner, D.; Weihe, K., Using multi-level graphs for timetable information, (), 43-59 · Zbl 1014.68902 |

[37] | Sedgewick, R.; Vitter, J., Shortest paths in Euclidean graphs, Algorithmica, 1, 31-48, (1986) · Zbl 0611.68044 |

[38] | Thorup, M., Undirected single-source shortest paths with positive integer weights in linear time, Journal of the ACM, 46, 362-394, (1999) · Zbl 1065.68597 |

[39] | Vygen, J., Near-optimum global routing with coupling, delay bounds, and power consumption, (), 308-324 · Zbl 1092.68002 |

[40] | Wagner, D.; Willhalm, T., Geometric speed-up techniques for finding shortest paths in large sparse graphs, (), 776-787 · Zbl 1266.68234 |

[41] | Wagner, D.; Willhalm, T., Speed-up techniques shortest path computations, (), 23-36 · Zbl 1186.68594 |

[42] | Xing, Z.; Kao, R., Shortest path search using tiles and piecewise linear cost propagation, IEEE transactions on CAD of integrated circuits and systems, 21, 145-158, (2002) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.