Optimización detallada de colocación y enrutamiento global con restricciones complejas
Autores: Huang, Zhipeng; Huang, Haishan; Shi, Runming; Li, Xu; Zhang, Xuan; Chen, Weijie; Wang, Jiaxiang; Zhu, Ziran
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Optimización detallada de colocación y enrutamiento global con restricciones complejas
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería Eléctrica y Electrónica
Palabras clave
Colocación
Enrutamiento
Algoritmo
Restricciones
Optimización
VLSI
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 33
Citaciones: Sin citaciones
Con varias etapas divididas, la ubicación y el enrutamiento son los pasos más críticos y desafiantes en el diseño físico de VLSI. Para garantizar que los problemas de implementación física sean manejables y converjan en un tiempo razonable, los problemas de ubicación/enrutamiento suelen dividirse aún más en varios subproblemas, lo que puede causar una reserva de margen conservadora y una mala correlación. Por lo tanto, es deseable diseñar un algoritmo que pueda considerar de manera precisa y eficiente la ubicación y el enrutamiento simultáneamente. En este documento, proponemos un algoritmo detallado de co-optimización de ubicación y enrutamiento global al considerar restricciones de enrutamiento complejas para evitar la reserva de margen conservadora y la mala correlación en las etapas de ubicación/enrutamiento. En primer lugar, presentamos una tecnología de preprocesamiento rápido basada en R-tree para mejorar los resultados de enrutamiento iniciales. Después, se diseña un algoritmo de direccionamiento óptimo aproximado basado en BFS en 3D para encontrar un destino adecuado para el movimiento de celdas. Proponemos un algoritmo de selección de región óptima basado en la solución de enrutamiento parcial para salir de la solución óptima local. Además, se utiliza un algoritmo rápido de eliminación parcial de red y reruteo en el proceso de movimiento de celdas. Finalmente, adoptamos una técnica de refinamiento eficiente para reducir aún más la longitud de enrutamiento. En comparación con los 3 mejores según los benchmarks del concurso CAD ICCAD 2020, los resultados experimentales muestran que nuestro algoritmo logra la mejor reducción de longitud de enrutamiento para todos los casos con un tiempo de ejecución más corto. En promedio, nuestro algoritmo puede mejorar un 0,7%, 1,5% y 1,7% para el primero, segundo y tercer lugar, respectivamente. Además, aún podemos obtener los mejores resultados después de relajar la restricción máxima de movimiento de celdas, lo que demuestra aún más la efectividad de nuestro algoritmo.
Descripción
Con varias etapas divididas, la ubicación y el enrutamiento son los pasos más críticos y desafiantes en el diseño físico de VLSI. Para garantizar que los problemas de implementación física sean manejables y converjan en un tiempo razonable, los problemas de ubicación/enrutamiento suelen dividirse aún más en varios subproblemas, lo que puede causar una reserva de margen conservadora y una mala correlación. Por lo tanto, es deseable diseñar un algoritmo que pueda considerar de manera precisa y eficiente la ubicación y el enrutamiento simultáneamente. En este documento, proponemos un algoritmo detallado de co-optimización de ubicación y enrutamiento global al considerar restricciones de enrutamiento complejas para evitar la reserva de margen conservadora y la mala correlación en las etapas de ubicación/enrutamiento. En primer lugar, presentamos una tecnología de preprocesamiento rápido basada en R-tree para mejorar los resultados de enrutamiento iniciales. Después, se diseña un algoritmo de direccionamiento óptimo aproximado basado en BFS en 3D para encontrar un destino adecuado para el movimiento de celdas. Proponemos un algoritmo de selección de región óptima basado en la solución de enrutamiento parcial para salir de la solución óptima local. Además, se utiliza un algoritmo rápido de eliminación parcial de red y reruteo en el proceso de movimiento de celdas. Finalmente, adoptamos una técnica de refinamiento eficiente para reducir aún más la longitud de enrutamiento. En comparación con los 3 mejores según los benchmarks del concurso CAD ICCAD 2020, los resultados experimentales muestran que nuestro algoritmo logra la mejor reducción de longitud de enrutamiento para todos los casos con un tiempo de ejecución más corto. En promedio, nuestro algoritmo puede mejorar un 0,7%, 1,5% y 1,7% para el primero, segundo y tercer lugar, respectivamente. Además, aún podemos obtener los mejores resultados después de relajar la restricción máxima de movimiento de celdas, lo que demuestra aún más la efectividad de nuestro algoritmo.