point de Steiner

Un point de Steiner est un sommet additionnel introduit dans un problème de routage de réseau pour réduire la longueur totale du câblage en dessous de ce qu'un arbre direct connectant uniquement les bornes requises permettrait. Dans la conception de cartes de circuits imprimés et le routage d'interconnexions, l'objectif est de connecter un ensemble de nœuds fixes (broches de composants, vias ou points de signal) avec la plus courte longueur totale de conducteur possible. Un point de Steiner n'est pas l'une de ces bornes requises ; il s'agit plutôt d'un nouveau point de jonction placé à un emplacement optimal où plusieurs segments de conducteur se rencontrent, permettant au routage de se plier et de se diviser de manière à économiser de la distance globalement.

Le concept trouve son origine dans la géométrie du point de Fermat, mais tire son nom des travaux de Jakob Steiner sur les réseaux minimaux. Dans le plan, un point de Steiner où trois segments de conducteur se rencontrent crée des angles de 120 degrés à l'optimalité, une propriété qui guide les algorithmes de disposition physique. Pour une simple connexion à deux points, aucun point de Steiner n'est utile ; pour trois points ou plus, l'ajout d'un ou plusieurs points de Steiner peut réduire la longueur totale de 10 à 15 pour cent dans les cas typiques. L'économie théorique maximale sur toutes les configurations approche 13,4 pour cent lorsque des arbres de Steiner optimaux remplacent les arbres couvrants minimaux.

Utilisation pratique dans le routage et la conception

En conception électronique, les points de Steiner apparaissent le plus souvent dans la synthèse d'arbres d'horloge, les réseaux de distribution d'énergie et le routage de signaux sur de grandes puces ou des cartes haute vitesse. Un logiciel de routage calcule les emplacements candidats des points de Steiner pour joindre des réseaux de trois bornes ou plus. Chaque point de Steiner ajouté augmente la complexité du routage et nécessite un placement minutieux pour éviter d'introduire de la diaphonie ou un couplage capacitif. Dans certains flux de conception, les points de Steiner sont placés sur une grille rectiligne (géométrie de Manhattan) plutôt que librement dans le plan, ce qui simplifie la fabrication mais réduit le bénéfice en termes de distance.

Le problème de l'arbre de Steiner lui-même est NP-difficile, ce qui signifie qu'aucun algorithme à temps polynomial connu ne le résout exactement pour les grands graphes. Les outils de routage pratiques utilisent des heuristiques et des algorithmes d'approximation, tels que les techniques Iterated 1-Steiner ou Batched Steiner, qui s'exécutent en un temps acceptable sur des netlists réelles avec des milliers ou des millions de nœuds. Le compromis entre la qualité de la solution et le temps de calcul est central pour la performance des outils de conception aux nœuds technologiques avancés.

Les points de Steiner doivent être distingués des segments de routage intermédiaires qui se croisent ou changent de direction sans se ramifier. Un véritable point de Steiner est une jonction où la topologie du réseau change ; le fait de le réduire ou de le supprimer modifierait les bornes directement connectées. Dans les zones encombrées d'une puce ou d'une carte, les points de Steiner peuvent être sacrifiés ou légèrement déplacés pour respecter les contraintes de ressources de routage, acceptant une petite pénalité de longueur pour la faisabilité physique.