Реализации алгоритмов для вычисления цепей

Question

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

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

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

Answer 1

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

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

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

Answer 2

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