Реализации алгоритмов оценки цепей

Question

Рассмотрим проблему оценки схемы, где вход является булевой схемой C и входной строкой x, и вы хотите вычислить C (x). (Примите фан-ин 2, если хотите.)

Это «тривиальная» проблема с алгоритмической точки зрения, однако реализовать ее нетривиально, когда C может быть огромным (подумайте о нескольких миллионах гейтов) и управление памятью становится проблемой.

Есть несколько способов решения этой проблемы: обмен памяти, времени и доступа к диску. Но прежде чем сам пройти всю эту работу, кто-нибудь знает какие-либо существующие реализации алгоритмов для этой проблемы? Было бы удивительно для меня, если бы не существует ...

Answer 1

Для C / C ++ стандартная система проектирования и моделирования цифровых цепей уже более 10 лет - SystemC .

Это библиотека, которая позволяет вам проектировать цифровую логику в C ++. Есть вспомогательное программное обеспечение, которое позволяет вам проводить анализ времени и даже создавать схематический список соединений для кода C.

Я только немного поиграл с этим, прежде чем решил, что с Verilog мне удобнее. Но это зрелая часть программного обеспечения с большой отраслевой поддержкой. Поиск в Интернете даст много информации, включая несколько страниц с учебниками.

Answer 2

Похоже, Диаграммы двоичных решений может быть использовано для вашей задачи?Существуют хорошо известные алгоритмы (и реализации), которые очень компактны с точки зрения использования памяти, учитывая, что они предназначены для использования в огромных пространствах состояний.