An efficient graph-based Steiner tree heuristic for the global routing of macro cells

摘要

Le routage global des macro cellules reste un pas important mais consommateur de temps dans le cycle de conception VLSI. Les macro cellules sont des modules de circuit de dimensions larges et irrégulières qui contiennent un nombre très élevé de terminaux qui doivent être interconnectés. Le modèle d'interconnections pour chaque ensemble de terminaux (réseau) qui doit être connecté est un arbre de Steiner, et le sous-problème principal dans le routage global des macro cellules est de trouver un ensemble d'arbres de Steiner distincts, de faible coût, pour chaque réseau qui doit être acheminé. Dans ce papier, on propose un algorithme à deux phases pour construire rapidement un réservoir varié d'arbres de Steiner pour le routage des réseaux à multiples terminaux. Dans la première phase, un algorithme constructif original, nommé Shrubbery, est utilisé pour croit» le nombre d'arbres de Steiner de haute qualité dans le réservoir. Pour assurer une variété parmi les membres du réservoir, on utilise une mémoire de long terme et une stratégie de perturbation arête-poids pour diversifier la recherche des nouvelles solutions. Dans la seconde phase, on utilise une recherche locale pour améliorer encore la qualité des arbres du réservoir. Des tests de calcul qui ont été réalisés sur plus de 800 bancs d'essai usuels montrent que l'algorithme proposé est capable de générer des réservoirs optimaux (ou presque optimaux) d'arbres dans un temps très court. Plus important encore, les arbres produits sont très différents, permettant de nombreux cheminements possibles pour chaque réseau.%Global routing of macro cells remains an important but time-consuming step in the VLSI design cycle. Macro cells are large, irregularly sized parameterized circuit modules that typically contain large numbers of terminals that must be interconnected. The interconnection pattern for each set of terminals (net) that must be connected is a Steiner tree, and the primary subproblem in the global rooting of macro cells is to find a set of dissimilar, low-cost Steiner trees for each net that must be routed. In this paper, a two-phase algorithm is proposed for quickly constructing a diverse pool of Steiner trees for routing of multi-terminal nets. In the first phase, a novel constructive algorithm called Shrubbery is used to grow high-quality Steiner trees for the pool. To ensure variety among pool members, a long-term memory and edge-weight perturbation strategy is employed to diversify the search when seeking for new solutions. Local search is used in the second phase to further improve the quality of trees in the pool. Computational experiments performed on over 800 commonly used benchmarks show that the proposed algorithm is able to generate pools of optimal (or near-optimal) trees in a very small amount of time. Most importantly, the trees produced are highly dissimilar, allowing for numerous routing possibilities for each net