Ce que j’aurais aimé savoir avant de développer un autorouter

"Leçons essentielles pour créer l’automaticien de routage le plus rapide du monde"

Utiliser l’algorithme A* partout

• A* est l’algorithme le plus puissant et le plus flexible pour les problèmes de recherche
• Il peut être utilisé non seulement sur une simple grille 2D, mais aussi dans des problèmes très variés
• A* est une "recherche informée" qui explore en priorité les nœuds proches de la destination, plus rapidement et plus efficacement que BFS
• Dans le code existant, la plupart des usages de DFS ou BFS peuvent être remplacés par A*
• Pour améliorer les performances, on peut exécuter plusieurs instances de A* et allouer davantage de ressources aux configurations les plus performantes

L’algorithme compte plus que le langage de programmation

• Développer un autorouter en Javascript ne posait absolument aucun problème
• Le cœur de l’optimisation consiste à réduire le nombre d’itérations
• Plus que les performances du langage, l’important est de savoir "à quel point on peut concevoir rapidement un algorithme intelligent"
• Javascript est plus favorable à des algorithmes intelligents qu’à l’obsession de l’optimisation bas niveau

Le Spatial Hash Indexing est plus efficace que les structures en arbre

• Les structures de données arborescentes comme les quadtrees sont en général lentes
• Un Spatial Hash Index regroupe les objets spatialement proches en hachant leur position
• Les structures basées sur le hachage offrent des performances de recherche proches de O(1)
• Pour être efficace, il faut bien choisir la taille des cellules, ce qui n’est pas très difficile

Le partitionnement spatial et le cache sont 1000 fois plus importants que l’algorithme

• Même les cartes électroniques complexes présentent majoritairement des motifs répétitifs
• Comme dans le développement de jeux, mettre en cache des résultats précalculés peut améliorer radicalement les performances
• Les structures cacheables et le partitionnement spatial seront au cœur des futurs autorouters
• Le stockage devient rapidement moins cher, et quelques Go de cache peuvent déjà apporter un gros gain de performances

Sans visualisation, impossible de résoudre les problèmes

• Pour chaque problème, la première étape consistait à créer un outil de visualisation
• La visualisation a permis d’accélérer le débogage d’un facteur supérieur à 10
• Même de simples étapes algorithmiques, une fois visualisées, permettent d’identifier rapidement la cause d’un problème

Les outils de profiling de Javascript sont extrêmement utiles

• L’onglet Performance des outils de développement Chrome permet de voir le temps passé par portion de code
• Même sans framework supplémentaire, on peut facilement analyser Flame Chart, usage mémoire, etc.
• Ce sont des outils très précieux pour le débogage des performances

Éviter les fonctions récursives

• Les fonctions récursives sont généralement synchrones et difficiles à convertir vers A*
• Une implémentation itérative est plus rapide et facilite le suivi des nœuds visités
• Dans une fonction récursive, modifier l’état est difficile et inefficace
• Il vaut mieux écrire avec des boucles autant que possible

Mieux vaut éviter les algorithmes de Monte Carlo

• Les algorithmes fondés sur l’aléatoire sont non déterministes et difficiles à déboguer
• Des heuristiques spécialisées pour le domaine offrent toujours de meilleures performances
• Aucun concepteur de PCB ne trace des pistes au hasard → ce n’est pas une approche réaliste
• Cela peut néanmoins être utile au début pour se faire une intuition

Ancrer chaque étape de l’algorithme dans l’espace réel du problème

• Normaliser les sous-algorithmes par rapport à l’origine rend la compréhension du flux global plus difficile
• Visualiser les entrées et sorties de chaque étape permet d’identifier laquelle introduit une erreur
• Il est important de conserver un repère cohérent tout au long du déroulement de l’algorithme

Visualiser le processus itératif sous forme d’animation

• Cela permet de voir visuellement à quel point l’algorithme explore de manière inefficace
• L’animation est très efficace pour réduire le nombre d’itérations et améliorer l’efficacité
• Les situations problématiques deviennent faciles à repérer, par exemple une recherche coincée dans une boucle infinie

On peut se passer de grille grâce aux mathématiques d’intersection

• Utiliser des mathématiques vectorielles au lieu d’une grille est bien plus rapide
• Dans bien des cas, les opérations mathématiques sont plus rapides que les accès mémoire
• Grâce aux LLM, les mathématiques de détection d’intersection sont devenues faciles à implémenter
• L’usage inutile d’une grille est une source de baisse de performances

Mesurer la probabilité d’échec à chaque étape permet de prioriser les chances de résolution

• On peut estimer la probabilité d’échec pour chaque nœud de partitionnement spatial
• Les nœuds les plus susceptibles d’échouer à l’étape suivante peuvent alors être restructurés ou réexplorés en priorité
• La probabilité d’échec se mesure clairement et offre plus de potentiel d’amélioration que de simples heuristiques
• Augmenter la probabilité globale de résolution peut être plus efficace que viser uniquement l’optimisation

Weighted A* peut multiplier la vitesse par 100

• A* classique garantit le chemin optimal, mais il est lent
• Weighted A* explore de manière plus gloutonne et peut accélérer fortement l’exécution
• Il suffit de définir la pondération avec f(n) = g(n) + w * h(n)
• Même si l’optimalité en souffre légèrement, le problème peut être résolu bien plus vite
• C’est une technique souvent utilisée dans le développement de jeux et qui mérite d’être étudiée

[GN⁺]

Commentaires sur Hacker News

• Écarter trop vite la méthode de Monte-Carlo est une grosse erreur

  • La méthode de Monte-Carlo a pour particularité de permettre un compromis entre précision et vitesse
  • Plus on exécute l’algorithme longtemps, plus il devient précis
  • À l’inverse, on peut aussi obtenir rapidement des résultats imprécis
  • Au lieu d’explorer tous les chemins, on n’en explore qu’un seul, choisi aléatoirement
  • Utiliser Monte-Carlo dans la boucle la plus interne de l’algorithme est efficace
  • Par exemple, lors de l’entraînement d’un réseau de neurones, la boucle externe met à jour les paramètres du réseau et la boucle interne calcule des chemins à travers le graphe
  • Avec Monte-Carlo, on peut ramener la précision de la boucle interne à une seule itération
  • Cela permet intuitivement de construire une politique qui prend toujours la bonne décision
  • Aux échecs ou au go, on peut calculer le meilleur chemin en utilisant des variantes de la recherche arborescente Monte-Carlo

• Je suis plutôt dans le camp du « ne faites pas confiance aux auto-routeurs »

  • Il existe une grande opportunité dans le domaine de l’eCAD pour accélérer la vitesse de layout
  • Il est plus probable qu’on utilise des outils de co-création que des outils d’automatisation complète
  • Au début de la conception, le placement n’est pas défini, ce qui influence fortement le routage
  • Je n’ai pas pu vérifier sur la page si le placement fait partie de l’algorithme
  • Je suis curieux du plan autour d’un AR écrit en JavaScript

• L’article mentionne un point important sur la visualisation et les effets de cache

  • Un algorithme récursif correspond à une recherche en profondeur
  • DFS et BFS peuvent être écrits de manière itérative ou récursive
  • A* est utile pour la recherche de chemin
  • BFS explore tous les nœuds adjacents, tandis que A* donne la priorité aux nœuds les plus proches de la destination
  • A* est un algorithme dynamique qui permet d’arrêter tôt avec confiance sur le plus court chemin

• Excellente discussion sur l’auto-routage

  • Le routage en lui-même est facile
  • Cela devient complexe quand il faut retirer ce qui est déjà routé pour faire de la place à quelque chose de nouveau
  • L’auto-routeur de KiCAD me manque

• 95 % de l’attention devrait porter sur la réduction du nombre d’itérations

  • Si les performances restent importantes, il faut ensuite réécrire dans un langage de bas niveau
  • numpy, pandas, OpenCV et TensorFlow sont implémentés en C++/assembleur/CUDA haute performance

• Les QuadTree et les structures de données arborescentes en général sont très lents

  • Un arbre n’est pas une représentation de l’information des données
  • Les approches par hachage ne conviennent que lorsque les points sont répartis uniformément
  • Les algorithmes aléatoires sont utiles lorsque l’espace de recherche est très grand

• Presque tout correspond aux heuristiques du développement de jeux

  • A*, l’algorithme de Lee, etc., sont tous excellents
  • Écrire un flood fill sans visualisation relève du crime
  • Le hachage spatial correspond particulièrement à mon expérience

• « indexation par hachage spatial > structures de données arborescentes » est pertinent dans ce domaine, mais ne doit pas être accepté comme une vérité universelle

  • Si les points ne sont pas répartis uniformément, la fonction de hachage peut être mauvaise

• Je me souviens des mots-clés appris à l’université

  • Je n’ai jamais l’occasion d’utiliser des algorithmes sophistiqués
  • À la place, je construis des composants UI et des API REST

• Pour quelqu’un qui n’est pas directement impliqué dans les problèmes spatiaux 2D/3D, la plus grande leçon est la valeur de la visualisation

  • Les humains excellent à comprendre et analyser des images
  • L’idée d’utiliser des méthodes probabilistes ou brutales pour comprendre la forme d’un problème est importante