Создание симулятора логических ворот

Question

Мне нужно сделать приложение для создания логических схем и просмотра результатов. Это в первую очередь для использования на компьютерных курсах A-Level (Великобритания, обычно для 16-18 лет).

Я никогда не создавал подобных приложений, поэтому я не уверен в лучшем дизайне для хранения схемы и оценки результатов (с восстанавливаемой скоростью, скажем, 100 Гц на одноядерном компьютере с частотой 1,6 ГГц).

Вместо того, чтобы строить схему из базовых вентилей (и, или, nand, и т. Д.), Я хочу разрешить использовать эти вентили для создания «микросхем», которые затем могут быть использованы в других цепях (например, вы можете захотеть сделать 8-битный регистр или 16-битный сумматор).

Проблема состоит в том, что количество вентилей значительно увеличивается с такими схемами, так что если моделирование работало на каждом отдельном вентиле, у него было бы тысячи вентилей для симуляции, поэтому мне нужно упростить эти компоненты, которые можно поместить в схему чтобы их можно было быстро смоделировать.

Я думал о генерации таблицы истинности для каждого компонента, затем симуляция могла бы использовать таблицу поиска, чтобы найти выходные данные для данного ввода. Проблема возникла у меня, хотя размер таких таблиц значительно увеличивается с входными данными. Если у чипа было 32 входа, то таблице истинности нужно 2 ^ 32 строки. При этом во многих случаях используется большой объем памяти, чем требуется, поэтому он не практичен для нетривиальных компонентов, он также не будет работать с микросхемами, которые могут хранить свое состояние (например, с регистрами), поскольку они не могут быть представлены просто таблица входов и выходов.

Я знаю, что мог бы просто жестко кодировать такие вещи, как регистрировать микросхемы, однако, поскольку это для образовательных целей, я хочу, чтобы люди могли создавать свои собственные компоненты, а также просматривать и редактировать реализации для стандартных. Я рассмотрел возможность создания и редактирования таких компонентов с использованием кода (например, dll или языка сценариев), чтобы сумматор, например, мог быть представлен как «output = inputA + inputB», однако это предполагает, что учащиеся выполнили достаточно программирования на данный язык, чтобы иметь возможность понимать и писать такие плагины, чтобы имитировать результаты их схемы, что, скорее всего, не так ...

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

Что касается хранения компонентов, я думал о сохранении некоторой древовидной структуры, так что каждый компонент оценивается, как только все компоненты, которые ссылаются на его входные данные, оцениваются.

например, рассмотреть: A.B + C Имитатор сначала оценивает логический элемент И, а затем оценивает логический элемент ИЛИ, используя выходные данные логического элемента И и C.

Однако мне только что пришло в голову, что в случаях, когда выходы связываются обратно со входами, вызовет взаимоблокировку, потому что там никогда не будут оцениваться все входы ... Как я могу преодолеть это, так как программа может оценить только один ворота за один раз?

Answer 1

Вы смотрели на симулятор Ричарда Боулза ?

Answer 2

Вы не первый, кто хочет создать свой собственный симулятор цепи; -).

Я предлагаю остановиться на минимальном наборе примитивов. Когда я начал свою (которую я планирую возобновить на днях ...), у меня было два примитива:

• Источник: ноль входов, один выход всегда 1.
• Транзистор: два входа A и B, один выход которого A and not B.

Очевидно, я немного неправильно использую терминологию, не говоря уже о пренебрежении тонкостями электроники. Во втором пункте я рекомендую абстрагироваться от проводов, которые имеют 1 и 0, как я сделал. Мне было очень весело рисовать диаграммы ворот и сумматоров из них. Когда вы сможете собрать их в цепи и нарисовать прямоугольник вокруг набора (с входами и выходами), вы можете начать строить более крупные вещи, такие как множители.

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

Редактировать Что касается вашей озабоченности по поводу масштабируемости, то как насчет использования принципа первого принципа для моделирования каждого компонента с точки зрения его состояния и соседей по восходящему потоку, но предоставьте способы оптимизации подсхем:

• Если у вас есть подсхема S с входами A[m] с m <8 (скажем, с максимумом 256 строк) и с выводами <code>B[n] и без циклов, сгенерируйте таблицу истинности для S и использовать это. Это можно сделать автоматически для идентифицированных подсхем (и использовать повторно, если подсхема появляется более одного раза) или по выбору.

• Если у вас есть схема с циклами, вы все равно сможете создать таблицу истинности. Здесь могут быть методы поиска с фиксированной точкой.

• Если ваша подсхема имеет задержки (и они имеют большое значение для замкнутой цепи), таблица истинности может включать столбцы состояний. Например. если подсхема имеет вход A, внутреннее состояние B и выход C, где C <- A и B, B <- A, таблица истинности может быть: </p>

  A B | B C
  0 0 | 0 0
  0 1 | 0 0
  1 0 | 1 0
  1 1 | 1 1

• Если у вас есть подсхема, которая, как утверждает пользователь, реализует конкретный известный шаблон, такой как «сумматор», предоставьте возможность использовать жестко запрограммированную реализацию для обновления этой подсхемы вместо моделирования ее внутренних частей.

Answer 3

Когда я сделал эмулятор схемы (к сожалению, также неполный и еще не выпущенный), вот как я справился с циклами:

• Каждый элемент схемы хранит свое логическое значение
• Когда элемент «E0» меняет свое значение, он уведомляет (через шаблон наблюдателя) всех, кто от него зависит
• Каждый элемент наблюдения оценивает свое новое значение и аналогично

Когда происходит изменение E0, список уровня 1 сохраняется со всеми затронутыми элементами. Если элемент уже присутствует в этом списке, он запоминается в новом списке уровня 2, но не продолжает уведомлять своих наблюдателей. Когда последовательность, которую начал E0, перестала уведомлять новые элементы, обрабатывается следующий уровень очереди. То есть: последовательность следует и завершается для первого элемента, добавленного к уровню-2, затем следующего, добавленного к уровню-2, и т. Д., Пока весь уровень-x не будет завершен, затем вы перейдете к уровню- (x + 1)

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

Answer 4

Возможно, вы захотите взглянуть на программу From Nand To Tetris в 12 шагов. На YouTube есть видео, рассказывающее об этом.

Страница курса: http://www1.idc.ac.il/tecs/

Answer 5

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

Я произвольно настроил провода для жесткого изменения входов при каждом изменении выхода и действия по изменению входа в любой цепи, чтобы запланировать функцию передачи, которая будет вызываться после задержки затвора. Имея это под рукой, я мог бы приспособить как тактированные, так и незапертые элементы схемы (для синхронизированного элемента настроено, чтобы его передаточная функция выполнялась при «следующем переключении такта плюс задержка затвора», любой разлоченный элемент зависит только от задержки затвора). *

Никогда не удосужился создать графический интерфейс для него, поэтому я никогда не выпускал код.

Answer 6

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

Оценка схемы без петель должна быть простой - просто используйте алгоритм BFS с «соединениями» (соединениями между логическими элементами) в качестве элементов в списке. Начните со всех входов для всех ворот в неопределенном состоянии. Как только у шлюза все входы «определены» (1 или 0), рассчитайте его выход и добавьте его выходные соединения в список BFS. Таким образом, вы должны оценивать каждый шлюз и каждый перекресток только один раз.

Если есть петли, можно использовать тот же алгоритм, но схема может быть построена таким образом, чтобы она никогда не доходила до «покоя», а некоторые соединения всегда меняются от 1 до 0.

Упс, на самом деле, этот алгоритм не может быть использован в этом случае, потому что зацикленные ворота (и ворота в зависимости от них) навсегда останутся "неопределенными".

Answer 7

Вы можете познакомить их с концепцией карт Карно, которая поможет им упростить значения истинности для себя.

Answer 8

Вы можете жестко закодировать все распространенные. Затем позвольте им создавать свои собственные из жестко закодированных (которые будут включать ворота низкого уровня), которые будут оцениваться путем оценки каждого подкомпонента. Наконец, если один из их «чипов» имеет меньше X входов / выходов, вы можете «оптимизировать» его в справочной таблице. Может быть, определить, насколько это распространено, и делать это только для наиболее часто используемых чипов Y? Таким образом, вы получите хороший компромисс между скоростью и пространством.

Вы всегда можете JIT компилировать схемы ...

Поскольку я на самом деле не думал об этом, я не совсем уверен, какой подход я бы выбрал ... но, возможно, это был бы гибридный метод, и я бы определенно жестко закодировал популярные "фишки". 1005 *