Implementación de algoritmos subóptimos para reordering en síntesis de circuitos integrados para synopsys

Abstract

La industria de los circuitos integrados experimenta un crecimiento desenfrenado y de- sempeña un papel fundamental en el avance tecnológico a nivel mundial. Synopsys, empresa líder en la industria, emplea la técnica de Scan Testing para verificar la funcionalidad de los circuitos integrados después de la fabricación, a través del proceso de Scan Insertion. Este proceso implica la incorporación de circuitos adicionales, incluida la conformación de una ca- dena entre componentes del circuito. En particular, el componente esencial de Scan Insertion, conocido como Reordering, se centra en optimizar la conectividad de esta cadena, buscando minimizar su largo. Este desafío se aborda como una instancia particular del Problema del Vendedor Viajero, reconocido por su complejidad NP-Completo.

Aunque los algoritmos actuales de Synopsys son funcionales, tienen un amplio margen de mejora y distan del estándar por el cual se guían las soluciones propuestas en la literatura académica. Tras revisar heurísticas desarrolladas en la academia para el Problema del Ven- dedor Viajero, se identifica el algoritmo Lin-Kernighan con mejoras de Keld Helsgaun como prometedor para implementar en Synopsys, a pesar de los desafíos en la implementación.

La implementación del algoritmo muestra resultados notables en la mejora de la optimali- dad y tiempos de ejecución prometedores. Se considera que el nuevo algoritmo sea adoptado como el estándar en la herramienta de diseño de Synopsys, allanando además el camino a futuros desarrollos, al mismo tiempo que haciendo hincapié en el uso de estándares acadé- micos y la conversión del problema de Reordering de Synopsys a una versión simétrica más estudiada, lo que resulta en una mayor amplitud de herramientas utilizables para resolver el problema.