Trabajé durante una década en un inicio realizando mejoras lógicas computarizadas para diseñadores de chips; finalmente fuimos comprados por Cadence.
Tuvimos, entre un montón de otras herramientas, un minimizador de lógica heurística. Era una cosa bastante simple que simplemente empujaba "burbujas" (negaciones) alrededor e intentaba absorber las puertas en las compuertas compuestas AOI u OAI un poco más eficientes. Luego, calcularía una función de costo para ver si esto era una buena idea.
Lo que resultó ser mucho más crítico fue la lógica duplicación . Parece contradictorio agregar más compuertas que computen la misma función lógica, pero lo importante en el rendimiento ASIC es la ruta crítica . La ruta lógica que demora más en calcular determina la velocidad de todo el chip. Agregar salidas adicionales desde una compuerta lo hace más lento, especialmente si esas salidas se encuentran en ubicaciones lejanas. Podría obtener una mejora notable si tiene dos copias de la lógica para calcular f (A, B, C) donde una era "rápida" y cerca de donde se necesitaba y otra "lenta" para un destino menos crítico.
El extremo de esto es el búfer. Una función de eliminación de lógica ingenua eliminaría todos tus búferes, después de todo, son solo la función de identidad, lo que te ahorraría mucho espacio pero arruinaría la velocidad.
Lógica óptima la colocación es, creo, también NP-completa. Es muy similar a la suma de subconjuntos. Una vez más, este es uno de esos problemas que es más fácil de resolver en la práctica, simulando que es lineal, lanzándolo a un solucionador de LP y haciendo que otros bits del programa se dirijan a la no linealidad.