Профессиональный троичный логический симулятор

[xakepp35]

Долго думал, года с 2014 эдак. И решил завести проект, профессиональный симулятор логических гейтов, на котором можно было бы строить логические схемки любой сложности. В частности, я хочу получить симуляцию троичного CPU, ну почти как мсье Shaos делает на тримуксах (четырёхвходовый гейт), но на уровне конкретный гейтов-логических функций, не обязательно с 4 входами. Выходит и без вложений в железо, и с более гибкой возможностью конфигурации и разработки-отладки. И это может быть обширное поле для экспериментов, без необходимости капитальных вложений денег и времени в железо на этапе проэктирования и отладки троичного цп. Кодобаза будет с нуля, ядро и бэкэнд на C/C++, фронтэнд я предполагаю на node.js, но до этого ещё дожить надо. Как будет что показать - заведу гитхаб. Может, кому будет тоже интересно или даже примут участие. Велкам

[xakepp35]

Начну с описания базовых вещей и идей, своего видения деталей эффективной реализации. Итак, непосредственно сам эмулятор, исполнитель. Ядро эффективности эмуляции в том, что любая н-арная троичная логическая функция (тлф) может быть задана номером длиной 3^n трит, и иметь линейное ультрабыстрое временем вычисления O(n+1), где O(1) - это время выборки трита из памяти.

 подробнее

- Разберу на примере -
полусумматор в балансной системе с тритами "-01". Это функция, состоящая из трёх ротаторов отрицательного "1-0" нулевого "-01" и положительного "01-". Если записать их не в таблицу, а подряд, как бы оно располагалось в памяти - то получим номер "1-0-0101-". И условимся, что самый левый трит имеет индекс -4, а самый правый +4. Таким образом полусумматор - это бинарная тлф за нумером 4160, и разрешается она за линейное время O(2+1)=O(3). Сначала мы берём 2 трита - входных аргумента, ставим друг за другом, и получаем некоторый индекс, число от -4 до 4. И далее следует ещё одна выборка - результат полусумматора - это просто трит из номера функции в позиции, определяемой этим индексом.

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

 подробнее

Внутри я планирую использовать 2bct кодирование, 2 бита на трит, например 64 бита могут закодировать 2^64 двоичных значений, но 3^32 троичных значений. Что даёт нам log(3^32)/log(2^64) = 79.248% эффективность. Для эмулятора 80% - это довольно удовлетворительно, учитывая полное отсутствие необходимости колхозить троичную память в железе! гигабайт оперативки на вскидку вместит с десяток миллионов тримуксов, что вполне позволяет запилить полномасштабную симуляцию аналога Pentium4 прям на уровне транзисторов, имея всего несколько гигов. Современные видеокарты имеют эти 4-8 гигов на борту...

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

 подробнее

Каждый вход каждого гейта может быть тритом в одной из двух областей памяти. Это либо некоторые входные данные, либо результат какого-то гейта с последнего шага вычислений. Значит нам нужно три области памяти:
1) input tape, некоторые входные данные, которые ядро будет считать как ROM, но симулятор на более высоком уровне может записывать входные данные перед каждым шагом. Во время шага не изменяются. Доступ на чтение возможен параллельно.
2) output tape, выходные данные, где n-ный трит соответствует n-ному гейту. Каждый гейт на шаге симуляции запишет туда свой результат. Только запись, возможна параллельно.
3) feedback tape - это output tape с предыдущего шага симуляции, таким образом каждый гейт может параллельно считать предыдущий выход на предыдущем шаге любого другого гейта. В текущем шаге значения предыдущего неизменяются, а значит возможен доступ на чтение параллельно.
И разумеется чтобы не заниматься вечным копированием output tape в feedback tape после каждого вычислительного шага, мы будем просто перекидывать указатели перед каждым шагом вычисления, что не занимает времени.

В итоге для m одинаковых гейтов с n входами мы получаем вычислительную сложность O( m*(n+1) ) свободно распараллеливающуюся по m*n. Таким образом, распалаллелив алгоритм, возможна довольно крупномасштабная симуляция на куче ксеонов, или даже на видеокартах с быстрой памятью.

[xakepp35]

Второй компонент системы включает загрузчик, служебные форматы, чтобы читать например из файла схему соединения этих гейтов, начальные ромы, всяческий маппинг памяти, и сопутствующие утилиты например чтобы эти файлы генерировать не вручную в HEX редакторе а из более высокоуровнего языка (как ассемблер и линкер), и возможно даже гуи для наглядного редактирования. Это второстепенная задача и достаточно прозрачна для реализации. Самое сложное тут пожалуй - это наличие времени на разработку фишечек и хорошее видение гуи редактора логики, чтобы можно было оперировать как с отдельными гейтами так и с целыми блоками и с блоками блоков, разумеется с зуммированием копированием и переиспользованием рекурсивно, путём простых манипуляций мышкой с выключенным мозгом)) Это я предполагаю оставить напоследок или на аутсорс =) Сначала нужно реализовать ядро системы и оценить эффективность однопоточной работы на небольших ромах составленных вручную или специальной тестовой программой. А также решить следующий важный вопрос.

[xakepp35]

Я надеюсь я смог обьяснить базовую идею. Всётаки пришлось дать некоторый объём текста. И предлагаю обсудить, что в данном случае мне непонятно, и вызывает самые большие вопросы и сомнения - так это третий компонент - модуль ввода вывода для симулятора. Без него - это как проц без материнки. Как подвязать весь этот скоп гейтов и тритов, к внешним устройствам? Нужен какой-то простой интерфейс, который позволит подключать программный эмулятор монитора, клавиатуры, вшешнего накопителя, сетевой или звуковой карты. Вроде понятно что это просто куча самописных драйверов, сводящимся к вызовам sockets api или opengl. Я про саму парадигму, хочу ваших советов, мыслей, идей. Как это сделать универсально, эффективно и расширяемо? Как в процессорах ввод вывод этот организован?

[Lavr]

Для троичных конструкций у нас есть специальная ветка Ternary.
(Перенёс в Ternary.)

[Shaos]

я боюсь, что тормоза JS съедят все изыски по бинарному ускорению симуляции

[Lavr]

я боюсь, что тормоза JS съедят все изыски по бинарному ускорению симуляции

А как же предкомпиляция в нативный код? Сам тут как-то про это рассказывал...

[Shaos]

я боюсь, что тормоза JS съедят все изыски по бинарному ускорению симуляции

А как же предкомпиляция в нативный код? Сам тут как-то про это рассказывал...

JavaScript? Это вряд ли...

[Lavr]

я боюсь, что тормоза JS съедят все изыски по бинарному ускорению симуляции

А как же предкомпиляция в нативный код? Сам тут как-то про это рассказывал...

JavaScript? Это вряд ли...

Ну здрасти!

Как работает JS: о внутреннем устройстве V8 и оптимизации ...
https://habrahabr.ru/company/ruvds/blog/337460/

При первом исполнении JS-кода V8 задействует компилятор full-codegen, который напрямую, без каких-либо дополнительных трансформаций, транслирует разобранный им JavaScript-код в машинный код. Это позволяет очень быстро приступить к выполнению машинного кода.

И другие ссылки есть, хотя я этим никогда не интересовался вплотную...

[Shaos]

Ну никто не сказал, что тут будет V8
Интерпретаторов JS - море

[Lavr]

Не буду спорить, но про предкомпиляцию в нативный код я тут от тебя слышал,
когда ты писал какой-то он-лайн схемный интерпретатор.
Это я потом поинтересовался, насколько соответствует действительности...

[Shaos]

Ну на голых сях по любому было бы быстрее

[xakepp35]

нет никакого javascript тут нет и не было. голый c и c++. чуть позже могу выложить исходники если интересно
ночка кода, запилил бенчмарк и результаты печальные.
10000 тримуксов (четырёхвходовых гейтов) работают с частотой ~10 килогерц

operation.png

я правда ожидал хотя бы в 10 раз лучший результат..

ну, вкратце там нету никаких if, тоесть это branchless (добавляя if скорость падает раза так в полтора)
если я комменчу основные операции по сборке входного данного из разрозненных трит - то скорость возрастает раз эдак в 7, до 70кгц.. =)
а операции - это просто разименования указателей, выборка значений из памяти да битовые сдвиги с умножениями, над беззнаковыми целыми..
также посмотрел на зависимость частоты симуляции от разных параметров:

от количества гейтов ширины 4:

frequency_vs_gates_count.png

от ширины входа гейта(создаю все 10к гейтов каждый одинаковой ширины inputWidth):

frequency_vs_input_width.png

[xakepp35]

шутники.. какой яваскрипт))) код либы это и есть самый что ни наесть голый C

impl.png

impl1.png

и как видно просто адовая кучень разименований памяти, и выборки выборок, плюс чуть умножений делений сдвигов операций И
и один цикл фор. это всё что нужно чтобы вычислить значение гейта. я оптимизировал всё что только можно... =(

код хоста бенчмарка с++, не влияет на скорость.
и, к слову, конфиг компа не самый плохой.

pc_config.png

[Lavr]

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

Это очень сурово... так прямо сходу всё и не понять!