Investigadores de la EPFL, AMD y la Universidad de Novi Sad han descubierto una ineficiencia de larga data en el algoritmo que programa millones de chips reconfigurables utilizados en todo el mundo, un descubrimiento que podría cambiar el modo en que se diseñan y programan las futuras generaciones de estos chips.
Muchas industrias, como las telecomunicaciones, la automoción, la aeroespacial y la física de partículas, dependen de un tipo especial de chip llamado matriz de puertas programables en campo (FPGA). A diferencia de los chips tradicionales, las FPGA se pueden reconfigurar prácticamente sin límite, lo que las hace invaluables en campos de rápida evolución donde diseñar un chip a medida llevaría años y costaría una fortuna. Pero esta flexibilidad tiene una desventaja: la eficiencia de las FPGA depende en gran medida del software utilizado para programarlas.
Desde finales de la década de 1990, un algoritmo conocido como PathFinder ha sido la columna vertebral del enrutamiento de FPGA. Su función: conectar miles de pequeños componentes de circuitos sin crear solapamientos. Durante décadas, funcionó tan bien que se convirtió en el estándar. Sin embargo, a medida que los circuitos crecían, los ingenieros comenzaron a experimentar ralentizaciones frustrantes y, ocasionalmente, fallos rotundos. Los diseños que deberían haber funcionado a menudo se etiquetaban como «no enrutables».
Ahora, con colegas de la Universidad de Novi Sad y la empresa tecnológica AMD, investigadores del Laboratorio de Arquitectura de Sistemas Paralelos(PARSA) de la Escuela de Ciencias de la Computación y la Comunicación han dado un paso más para desentrañar el funcionamiento interno de este algoritmo clásico.
En su artículo reciente, que recibió el premio al mejor artículo en el 33º Simposio internacional IEEE sobre máquinas informáticas personalizadas programables en campo , revelaron por qué ocurren estas fallas y cómo se pueden superar los límites de PathFinder.
Grietas en el algoritmo
“De hecho, no es sorprendente que PathFinder a veces falle”, explicó Shashwat Shrivastava, estudiante de doctorado de PARSA y primer autor del artículo. “Desde el principio, los investigadores demostraron que el problema del enrutamiento FPGA es extremadamente complejo. Posteriormente, los creadores del algoritmo original, junto con algunos colaboradores, encontraron casos en los que PathFinder nunca tendría éxito, pero observaron que tales casos no se presentarían en la práctica”.
Durante décadas, parecía que tenían razón: PathFinder funcionaba sorprendentemente bien.
“PathFinder funcionó tan bien que, de hecho, cuando fallaba, rara vez se cuestionaba el algoritmo. En lugar de investigarlo para ver qué sucedía, ajustaban sus parámetros, modificaban los circuitos o cambiaban a FPGAs más grandes”, añadió Stefan Nikolić, exalumno de la EPFL y actual profesor de la Universidad de Novi Sad. “En parte, esto se debe a que resulta bastante difícil comprender qué hace realmente PathFinder en ejemplos de importancia práctica. Los circuitos modernos son tan grandes que sus señales forman auténticas junglas en el chip”.
Entra en el bosque
“Así que necesitábamos observar cada árbol en esa jungla”, continuó Shrivastava, “y me refiero a árboles. Cada señal —una conexión que transporta información entre los componentes del circuito— debe llegar a múltiples destinos sin superponerse a otras señales. El enrutamiento FPGA consiste básicamente en construir un árbol para cada señal en el chip”.
Mientras trabajaban en otro proyecto basado en PathFinder, el equipo seguía observando resultados que desafiaban la intuición. Al principio, culparon a factores externos, no al algoritmo en sí. Con el tiempo, se dieron cuenta de que necesitaban ejemplos controlados: casos pequeños y complejos donde definitivamente existía una solución y en los que PathFinder debería tener éxito.
“Necesitábamos muchos ejemplos prácticos y reales para comprender qué estaba sucediendo realmente”, explica Shrivastava. “Así que creamos un marco para extraer automáticamente pequeños problemas complejos de circuitos reales. Observar cómo PathFinder lidiaba con ellos nos ayudó a descubrir problemas que habían permanecido ocultos durante mucho tiempo”.
Poder en asociación
“Este avance habría sido mucho más difícil sin el apoyo de la industria”, afirmó Mirjana Stojilović, directora de doctorado de Shrivastava. “Desde el principio, colaboramos con Chirag Ravishankar y Dinesh Gaitonde de AMD. Nos ayudaron a modelar FPGAs lo más parecido posible a los dispositivos comerciales, garantizando así que nuestros hallazgos tuvieran un impacto real”.
Una vez listo el framework, todo se aceleró. El equipo descubrió que PathFinder solía construir árboles de enrutamiento más grandes de lo necesario, lo que aumentaba el riesgo de solapamientos. El problema residía en el orden en que creaba y añadía nuevas ramas a los árboles.
“En retrospectiva, esto es intuitivo, pero por alguna razón pasó desapercibido durante muchos años”, dijo Shrivastava. “Nuestra primera solución fue simple: probar diferentes órdenes y elegir el que diera como resultado el árbol más pequeño. Experimentalmente, funcionó sorprendentemente bien”.
Mirando hacia el futuro
El equipo ahora está explorando soluciones más escalables. «Estoy especialmente orgulloso de la importante contribución de los becarios de Summer@EPFL. Uno de ellos, Sun Tanaka, también es coautor del artículo», añadió Stojilović. «Nuestro descubrimiento podría redefinir la programación de millones de FPGAs e influir en el diseño de futuras generaciones de estos chips reconfigurables».
Lea el artículo: https://doi.ieeecomputersociety.org/10.1109/FCCM62733.2025.00060
EPFL News. T. P. Traducido al español
