FLUTE: Algoritmo de Árbol Steiner Mínimo Rectilíneo Basado en Tabla de Búsqueda Rápida para Diseño VLSI

En este artículo, presentamos un algoritmo de árbol Steiner mínimo rectilíneo (RSMT) muy rápido y preciso llamado estimación de tabla de búsqueda rápida (FLUTE). FLUTE se basa en una tabla de búsqueda precomputada para hacer que la construcción de RSMT sea muy rápida y precisa para redes de bajo grado. El grado de una red es el número de pines en la red. Para redes de alto grado, se propone una técnica de ruptura de red para reducir el tamaño de la red hasta que se pueda utilizar la tabla. También se presenta un esquema que permite a los usuarios controlar la compensación entre precisión y tiempo de ejecución. FLUTE es óptimo para redes de bajo grado (hasta grado 9 en nuestra implementación actual) y sigue siendo muy preciso para redes de hasta grado 100. Por lo tanto, es especialmente adecuado para aplicaciones de integración a gran escala en las que la mayoría de las redes tienen un grado de 30 o menos. Mostramos experimentalmente que, en 18 circuitos industriales en el conjunto de pruebas ISPD98, FLUTE con precisión predeterminada es más preciso que la heurística de Batched 1-Steiner y es casi tan rápido como una implementación muy eficiente del algoritmo de árbol de expansión mínimo rectilíneo de Prim.