Cosas que me hubiera gustado saber antes de desarrollar un Autorouter

"Lecciones importantes para crear el autorouter más rápido del mundo"

Usar el algoritmo A* en todas partes

• A* es el algoritmo más potente y flexible para problemas de búsqueda
• Puede usarse no solo en una cuadrícula 2D simple, sino en muchos tipos de problemas
• A* es una "búsqueda informada" que, a diferencia de BFS, explora primero los nodos más cercanos al objetivo de forma más rápida y eficiente
• La mayoría de los usos actuales de DFS o BFS en código existente pueden reemplazarse por A*
• Para mejorar el rendimiento, se usa una técnica que ejecuta varias instancias de A* y asigna más recursos a las configuraciones que mejor desempeño muestran

El algoritmo importa más que el lenguaje de programación

• Desarrollar el autorouter en Javascript no fue ningún problema
• La clave de la optimización es reducir la cantidad de iteraciones
• Más importante que el rendimiento del lenguaje es "qué tan inteligente sea el algoritmo que puedes construir y qué tan rápido puedas crearlo"
• Javascript favorece más los algoritmos inteligentes que las iteraciones rápidas

Spatial Hash Indexing es más eficiente que una estructura en árbol

• Las estructuras de datos basadas en árboles, como Quadtree, suelen ser lentas
• Spatial Hash Index agrupa y procesa juntos los objetos cercanos en el espacio al hacer hash de sus posiciones
• Las estructuras basadas en hash ofrecen un rendimiento de búsqueda cercano a O(1)
• Para que funcione bien, hay que elegir correctamente el tamaño de las celdas, aunque no es difícil encontrar un tamaño adecuado

La partición espacial y la caché importan 1000 veces más que el algoritmo

• Incluso las placas de circuito complejas suelen tener patrones repetidos
• Como en el desarrollo de videojuegos, cachear resultados precalculados puede mejorar el rendimiento de forma drástica
• Las estructuras cacheables y la partición espacial serán la clave de los autorouters del futuro
• El almacenamiento se abarata rápidamente, y hasta una caché de varios GB puede dar una gran mejora de rendimiento

Sin visualización no se pueden resolver los problemas

• Para cada problema, primero se construyó una herramienta de visualización
• Con visualización fue posible mejorar la velocidad de depuración en más de 10 veces
• Incluso en pasos simples del algoritmo, visualizar ayuda a identificar rápidamente la causa del problema

Las herramientas de profiling de Javascript son muy útiles

• En la pestaña Performance de las herramientas para desarrolladores de Chrome se puede ver cuánto tiempo consume cada parte del código
• Incluso sin frameworks adicionales, es fácil analizar Flame Charts, uso de memoria y más
• Son herramientas muy útiles para depurar rendimiento

No uses funciones recursivas

• Las funciones recursivas suelen ser síncronas y son difíciles de convertir a A*
• Las implementaciones iterativas son más rápidas y facilitan el seguimiento de los nodos visitados
• En funciones recursivas es difícil cambiar el estado y además resultan ineficientes
• Siempre que sea posible, conviene escribirlo con bucles

Evita los algoritmos Monte Carlo

• Los algoritmos basados en aleatoriedad no son deterministas y son difíciles de depurar
• Las heurísticas especializadas para el dominio siempre ofrecen mejor rendimiento
• Ningún diseñador de PCB traza pistas al azar → no es un enfoque realista
• Aun así, al principio pueden servir para darse una idea

Fija las etapas del algoritmo al espacio real del problema

• Si normalizas los subalgoritmos con respecto al origen, se vuelve difícil entender el flujo completo
• Visualizar las entradas y salidas de cada etapa permite detectar cuál está provocando errores
• Es importante mantener un sistema de coordenadas consistente junto con el flujo del algoritmo

Visualiza el proceso iterativo con animaciones

• Permite ver visualmente qué tan ineficiente está siendo la exploración del algoritmo
• Las animaciones son muy efectivas para reducir iteraciones y aumentar la eficiencia
• Facilitan detectar situaciones problemáticas (por ejemplo, búsquedas atrapadas en un bucle infinito)

La matemática de detección de intersecciones basta sin usar una cuadrícula

• Usar matemáticas vectoriales en lugar de una cuadrícula es mucho más rápido
• En muchos casos, las operaciones matemáticas son más rápidas que acceder a memoria
• Gracias a los LLM, ahora también es fácil implementar la matemática de detección de intersecciones
• Usar una cuadrícula innecesariamente provoca pérdidas de rendimiento

Mide la probabilidad de fallo en cada etapa para priorizar la posibilidad de resolverlo

• Es posible estimar la probabilidad de fallo en cada nodo de partición espacial
• Luego se pueden reconfigurar o volver a explorar primero los nodos con mayor probabilidad de fallar en etapas posteriores
• La probabilidad de fallo puede medirse claramente y tiene más margen de mejora que una heurística
• Aumentar la probabilidad total de resolver el problema puede ser más efectivo que apuntar solo a la optimización

Con Weighted A* se puede mejorar la velocidad hasta 100 veces

• El A* básico garantiza la ruta óptima, pero es lento
• Weighted A* explora de forma más codiciosa y puede mejorar drásticamente la velocidad
• Puede implementarse simplemente ajustando el peso en f(n) = g(n) + w * h(n)
• Aunque se pierda un poco de optimalidad, puede resolver el problema mucho más rápido
• Es una técnica muy usada también en desarrollo de videojuegos y vale la pena tomarla como referencia

[GN⁺]

Comentarios en Hacker News

• Descarta demasiado rápido el método Monte Carlo, y eso es un gran error

  • La característica del método Monte Carlo es que permite intercambiar precisión por velocidad
  • Cuanto más tiempo se ejecuta el algoritmo, más preciso se vuelve
  • A la inversa, también se pueden obtener resultados rápidos pero imprecisos
  • En vez de explorar todas las rutas, explora solo una ruta elegida al azar
  • Es efectivo usar Monte Carlo en el bucle más interno del algoritmo
  • Por ejemplo, al entrenar una red neuronal, el bucle externo actualiza los parámetros de la red y el bucle interno calcula rutas a través del grafo
  • Con Monte Carlo, la precisión del bucle interno puede reducirse a una sola iteración
  • Intuitivamente, esto permite construir una política que siempre tome decisiones correctas
  • En ajedrez o Go, se pueden usar variantes de búsqueda de árboles Monte Carlo para calcular la ruta óptima

• Estoy en la postura de "no confíes en el autorouter"

  • En el campo de eCAD hay una gran oportunidad para acelerar la velocidad del layout
  • Es más probable que se usen herramientas de co-creación que herramientas de automatización total
  • Al inicio del diseño no está definida la colocación, y eso influye mucho en el routing
  • En la página no se puede confirmar si la colocación forma parte del algoritmo
  • Me da curiosidad el plan para un AR escrito en JavaScript

• El artículo menciona puntos importantes sobre visualización y efectos de caché

  • Los algoritmos recursivos son búsqueda en profundidad
  • DFS y BFS pueden escribirse de forma iterativa o recursiva
  • A* es útil para búsqueda de rutas
  • BFS explora todos los nodos adyacentes y A* prioriza los nodos más cercanos al destino
  • A* es un algoritmo dinámico que puede terminar antes con confianza al encontrar la ruta más corta

• Es una gran discusión sobre autorouting

  • El routing en sí es fácil
  • Se vuelve complejo cuando hay que quitar lo ya enrutado para hacer espacio a algo nuevo
  • Se extraña el autorouter de KiCAD

• El 95% del enfoque debería estar en reducir la cantidad de iteraciones

  • Si el rendimiento sigue siendo importante, hay que reescribirlo en un lenguaje de bajo nivel
  • numpy, pandas, OpenCV y TensorFlow están implementados con C++/ensamblador/CUDA de alto rendimiento

• QuadTree y las estructuras de datos de árbol en general son muy lentas

  • Los árboles no son una representación informativa de los datos
  • Los enfoques basados en hashing solo sirven cuando los puntos están distribuidos de manera uniforme
  • Los algoritmos aleatorios son útiles cuando el espacio de búsqueda es muy grande

• Casi todo coincide con las heurísticas del desarrollo de juegos

  • A*, el algoritmo de Lee y otros son todos geniales
  • Es casi un crimen escribir un flood fill sin visualización
  • El hashing espacial en particular coincide mucho con mi experiencia

• "Indexación con hash espacial > estructuras de datos de árbol" funciona bien en este dominio, pero no debería tomarse como una verdad universal

  • Si los puntos no están distribuidos uniformemente, la función hash puede ser mala

• Recuerdo las palabras clave que aprendí en la universidad

  • No he tenido oportunidad de usar algoritmos fancy
  • En cambio, construyo componentes de UI y API REST

• Como alguien que no trabaja directamente con problemas espaciales 2D/3D, la mayor lección es el valor de la visualización

  • Los humanos son muy buenos para entender y analizar imágenes
  • Es importante la idea de usar métodos probabilísticos o de fuerza bruta para entender la forma del problema