Implementaciones de algoritmos para evaluar circuitos

Question

Considere el problema de la evaluación de circuitos, donde la entrada es un circuito booleano C y una cadena de entrada x y desea calcular C (x). (Suponga fan-in 2 si lo desea)

Este es un problema "trivial" algorítmicamente, sin embargo no parece trivial implementarlo cuando C puede ser enorme (piense en varios millones de puertas) y la administración de la memoria se convierte en un problema.

Hay varias maneras de abordar este problema, cambiando la memoria, el tiempo y el acceso al disco. Pero antes de pasar por todo este trabajo, ¿alguien sabe de alguna implementación existente de algoritmos para este problema? Sería sorprendente para mí si no existe ...

Answer 1

Para C/C++, el sistema de simulación de circuito digital estándar & durante más de 10 años es SystemC.

Es una biblioteca que le permite diseñar lógica digital en C++. Hay un software de soporte que le permite hacer análisis de tiempo e incluso generar listas de redes esquemáticas para el código C.

Solo he jugado un poco con esto antes de decidir que estaba más cómodo con Verilog. Pero es una pieza de software madura con mucho soporte de la industria. Buscar en Google arrojará mucha información, incluidas varias páginas de tutoriales.

Answer 2

Parece que Binary Decision Diagrams podría ser utilizado para su tarea? Existen algoritmos (e implementaciones) bien conocidos de estos que son muy compactos en términos de uso de la memoria, dado que están diseñados para ser utilizados en grandes espacios de estado.