[VLSI CAD] Por qué la solución óptima es difícil: NP-difícil, heurística, AI EDA

TL;DR

• Muchos de los problemas centrales de optimización en el diseño de semiconductores son NP-duros / NP-completos / PSPACE-complete, por lo que los algoritmos que garantizan una "solución óptima" son prácticamente poco rentables a escala (por ejemplo, aunque sólo haya 40 casos de 2, hay 1 billón de casos)
• Es por esto que las herramientas EDA están diseñadas desde cero para ser heurísticas + aproximación + mejora iterativa. Esto no se debe a que "las herramientas apesten" sino a la naturaleza del problema.
• AI/ML no encuentra eficientemente soluciones "óptimas" a problemas NP-hard. En su lugar, se benefician de forma realista de modelos para guiar, automatizar y acotar el problema.

1) Diseño Físico: ¿Por qué es NP-duro

El problema "duro" más clásico en Síntesis Lógica, el primer paso del Diseño Físico, es la minimización booleana de dos niveles. Por ejemplo, el problema de encontrar el mínimo SOP(DNF) que satisface una tabla de verdad.

• Se sabe que el problema de minimización booleana de dos niveles es NP-completo.

Caso Quine-McCluskey (QM):

QM es un método de simplificación de funciones booleanas que se enseña en ingeniería digital.

• Objetivo: Cubrir una función booleana con un implícito primo mínimo,
• Procedimiento:
  1. Generar todos los implicantes primos
  2. Listar todos los mintérminos
  3. Crear tabla de cobertura (filas=mintérmino, columnas=primo)
  4. Seleccionar columna mínima → problema de cobertura mínima

👉 Problema 4.

• En circuitos reales, el "conjunto de posibles combinaciones de términos candidatos" es enorme, y QM tiene una complejidad exponencial.
• El proceso de encontrar combinaciones primo-implicantes en la tabla de cobertura de QM cae dentro de la estructura conjunto cobertura / cobertura exacta, que es clásicamente NP-completa.

El punto clave es este.

La razón por la que el CAD VLSI (Herramienta EDA) es lento y difícil no es porque la implementación sea mala, sino porque el problema en sí tiene un número enorme de casos posibles

Es por eso que oyes "¿No puedes resolverlo con SATisfacción/Programación Lineal Entera?", y es así.

• SAT es NP-completo e ILP es NP-difícil.
• Es decir, aunque cambies el formato, sigue siendo NP-completo y NP-duro.

2) ¿Hay tantos NP-duros y NP-completos en los pasos EDA?

El flujo EDA es similar en naturaleza aunque las fases cambien.

"Optimización de costes mediante la colocación/selección/conexión de componentes"
Esta estructura es mayoritariamente NP-difícil.

Lo siguiente es una versión condensada con sólo "objetivo de optimización → por qué es difícil".

2.1 Lógica multinivel (AIG, reescritura DAG)

• Objetivo: Reducir el número de puertas, la profundidad, el proxy de potencia, etc.
• ¿Por qué es difícil? "reestructuración global", que cambia la propia estructura del circuito, se convierte en búsqueda combinatoria. También se sabe que las clases de salida múltiple/minimización son NP-difíciles.

• Solución alternativa: transformación local (reescritura algebraica, reescritura AIG)

2.-Mapeo tecnológico.2 Technology Mapping

• Objetivo: Minimizar el área/retraso mientras se mapean DAGs a celdas estándar o LUTs
• Por qué difícil: Se sabe que el mapeo óptimo es NP-difícil para DAGs generales.
• Excepción: A veces se resuelve mediante DP si la estructura es de árbol, pero se rompe porque es un DAG.

https://hjemmesider.diku.dk/~jegeblad/thesis.pdf

2.3 Colocación

• Objetivo: minimizar la longitud/congestión del cable colocando las celdas en coordenadas
• La simplificación se reduce a particionar/empaquetar y se sabe que es NP-difícil.
• Entonces la realidad: colocación analítica + partición + refinamiento heurístico.

Además, Enrutamiento, CTS, ... muchas cosas son problemas NP.

3) decisión vs optimización vs multiobjetivo

La razón por la que EDA es difícil es que lo que quieren los diseñadores de circuitos no es decisión, sino optimización, y además es multiobjetivo.

• Problema de decisión: "¿Es posible/imposible?" (por ejemplo, ¿es satisfactorio el tiempo de 1ns?)
• Problema de optimización: "¿Cuál es el mínimo/máximo?" (por ejemplo, despliegue de longitud de cable mínima)
• Multiobjetivo: Hay múltiples objetivos, como Rendimiento Potencia Área.

En la práctica, se parece a esto.

• "La sincronización debe ser perfecta" (restricción dura)
• "El área/potencia debe reducirse con una penalización" (restricción suave)
• Y luego se itera y se ajustan las compensaciones.

En otras palabras, EDA no es un juego de "una respuesta correcta" desde el principio, sino más bien un juego de
diseño de restricciones y compromisos.

4) Así que la heurística no es 'opcional' sino 'obligatoria'

Hay cuatro razones por las que la heurística es obligatoria en EDA.

1. El óptimo global no existe → acumular mejora local:
   1. El óptimo global es la solución óptima que enumera todos los casos y demuestra que no hay ningún caso mejor.
2. Diferentes niveles de abstracción → Lo que es bueno en síntesis lógica puede ser malo en Colocación.
3. La función de coste es desordenada → No lineal/no convexa/escalonada, por lo que la "optimización canónica" no funciona bien.
4. El bucle incremental es el predeterminado → "modificar→analizar→modificar" es la esencia, no "hacerlo todo de una vez"

Resumen:

Las herramientas deEDA son inherentemente "sistemas heurísticos".

5) ¿Dónde funciona realmente el EDA impulsado por IA/ML?

Es peligroso decir que la IA "resuelve" problemas NP-difíciles, pero los comunicadores de TI tienden a exagerarlo por el bien de las opiniones.

Si lo desglosas así, tiene más sentido. Aunque este se siente un poco escaso.

A) AI가 잘하는 영역: "predecir/puntuar", no "resolver"

• modelo sustituto: un predictor que sustituye a la costosa simulación/análisis
• predice rápidamente la congestión, los puntos calientes de tiempo en la colocación/ruta para guiar la navegación.

La IA es estable cuando entra en la función de puntuación, no en el solucionador.

B) AI가 실제로 돈 되는 영역: "La IA hace el trabajo de múltiples iteraciones de una herramienta EDA, minimizando el esfuerzo del diseñador."

Este es uno de los enfoques similares a la IA-EDA de muchas empresas de EDA.

• En lugar de cambiar el propio motor EDA, la IA explora "opciones/flujo/parámetros" para reducir el trabajo humano de ajuste.
• Esto tiene un ROI realista.
• La clave aquí es automatización de la búsqueda, no "IA reinventando la colocación".

C) Áreas en las que la IA es débil actualmente: "Donde necesitamos un 0% de error"

• La aprobación o verificación formal requiere un nivel humano de prueba para poner el sello final de aprobación. ML puede ayudar, pero no sustituir."
• Resolver un SAT de extremo a extremo o diseñar un chip entero de extremo a extremo no es generalizable/verificable.

6) Evaluación en una línea de ejemplos populares de EDA impulsados por IA

Las siguientes tecnologías son prometedoras. Sin embargo, tienden a ser sobrevaloradas por los medios:

• Macrocolocación de Google RL (Nature): El impacto fue grande. Sin embargo, la replicación/comparación es débil.
• DSO.ai / Cerebrus: Un caso en el que se creó valor mediante la automatización de ajuste de flujo en lugar de empaquetar la IA como un "solucionador".
• Agentic EDA / LLM: aún "prometedor", y los problemas de validación/rendición de cuentas/datos permanecen.

7) Resumen

• "¿La IA resuelve NP-difícil?"
  • No. La IA no es una forma de encontrar la solución óptima.
• "¿SAT+AI = síntesis óptima?"
  • No. El espacio de búsqueda sigue siendo el mismo.
• "¿Computación en la nube = resolver? Más recursos informáticos = resolver?".
  • No. La complejidad es una exponencial, por lo que si el exponente es muy grande, no se pueden traer todos los ordenadores del planeta, y los diseños de semiconductores modernos tienen exponentes muy grandes.
  • "¿EDA impulsado por IA sustituye a los diseñadores?"
    • Aún no. Diseño de requisitos + verificación final + responsabilidad humana.