|
nedoPC.orgElectronics hobbyists community established in 2002 |
|
Профессиональный троичный логический симулятор
Author |
Message |
xakepp35
Novelist
Joined: 10 Feb 2016 16:59 Posts: 26
|
Долго думал, года с 2014 эдак. И решил завести проект, профессиональный симулятор логических гейтов, на котором можно было бы строить логические схемки любой сложности. В частности, я хочу получить симуляцию троичного CPU, ну почти как мсье Shaos делает на тримуксах (четырёхвходовый гейт), но на уровне конкретный гейтов-логических функций, не обязательно с 4 входами. Выходит и без вложений в железо, и с более гибкой возможностью конфигурации и разработки-отладки. И это может быть обширное поле для экспериментов, без необходимости капитальных вложений денег и времени в железо на этапе проэктирования и отладки троичного цп. Кодобаза будет с нуля, ядро и бэкэнд на C/C++, фронтэнд я предполагаю на node.js, но до этого ещё дожить надо. Как будет что показать - заведу гитхаб. Может, кому будет тоже интересно или даже примут участие. Велкам
Last edited by xakepp35 on 19 Jan 2018 13:42, edited 1 time in total.
|
19 Jan 2018 13:31 |
|
|
xakepp35
Novelist
Joined: 10 Feb 2016 16:59 Posts: 26
|
Начну с описания базовых вещей и идей, своего видения деталей эффективной реализации. Итак, непосредственно сам эмулятор, исполнитель. Ядро эффективности эмуляции в том, что любая н-арная троичная логическая функция (тлф) может быть задана номером длиной 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. Таким образом, распалаллелив алгоритм, возможна довольно крупномасштабная симуляция на куче ксеонов, или даже на видеокартах с быстрой памятью.
Last edited by xakepp35 on 19 Jan 2018 13:42, edited 1 time in total.
|
19 Jan 2018 13:33 |
|
|
xakepp35
Novelist
Joined: 10 Feb 2016 16:59 Posts: 26
|
Второй компонент системы включает загрузчик, служебные форматы, чтобы читать например из файла схему соединения этих гейтов, начальные ромы, всяческий маппинг памяти, и сопутствующие утилиты например чтобы эти файлы генерировать не вручную в HEX редакторе а из более высокоуровнего языка (как ассемблер и линкер), и возможно даже гуи для наглядного редактирования. Это второстепенная задача и достаточно прозрачна для реализации. Самое сложное тут пожалуй - это наличие времени на разработку фишечек и хорошее видение гуи редактора логики, чтобы можно было оперировать как с отдельными гейтами так и с целыми блоками и с блоками блоков, разумеется с зуммированием копированием и переиспользованием рекурсивно, путём простых манипуляций мышкой с выключенным мозгом)) Это я предполагаю оставить напоследок или на аутсорс =) Сначала нужно реализовать ядро системы и оценить эффективность однопоточной работы на небольших ромах составленных вручную или специальной тестовой программой. А также решить следующий важный вопрос.
Last edited by xakepp35 on 19 Jan 2018 13:52, edited 1 time in total.
|
19 Jan 2018 13:35 |
|
|
xakepp35
Novelist
Joined: 10 Feb 2016 16:59 Posts: 26
|
Я надеюсь я смог обьяснить базовую идею. Всётаки пришлось дать некоторый объём текста. И предлагаю обсудить, что в данном случае мне непонятно, и вызывает самые большие вопросы и сомнения - так это третий компонент - модуль ввода вывода для симулятора. Без него - это как проц без материнки. Как подвязать весь этот скоп гейтов и тритов, к внешним устройствам? Нужен какой-то простой интерфейс, который позволит подключать программный эмулятор монитора, клавиатуры, вшешнего накопителя, сетевой или звуковой карты. Вроде понятно что это просто куча самописных драйверов, сводящимся к вызовам sockets api или opengl. Я про саму парадигму, хочу ваших советов, мыслей, идей. Как это сделать универсально, эффективно и расширяемо? Как в процессорах ввод вывод этот организован?
|
19 Jan 2018 13:41 |
|
|
Lavr
Supreme God
Joined: 21 Oct 2009 08:08 Posts: 7777 Location: Россия
|
Для троичных конструкций у нас есть специальная ветка Ternary. ( Перенёс в Ternary.)
_________________ iLavr
|
19 Jan 2018 16:33 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22735 Location: Silicon Valley
|
я боюсь, что тормоза JS съедят все изыски по бинарному ускорению симуляции
|
19 Jan 2018 18:57 |
|
|
Lavr
Supreme God
Joined: 21 Oct 2009 08:08 Posts: 7777 Location: Россия
|
А как же предкомпиляция в нативный код? Сам тут как-то про это рассказывал...
_________________ iLavr
|
19 Jan 2018 20:09 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22735 Location: Silicon Valley
|
JavaScript? Это вряд ли...
|
19 Jan 2018 21:26 |
|
|
Lavr
Supreme God
Joined: 21 Oct 2009 08:08 Posts: 7777 Location: Россия
|
Ну здрасти! Как работает JS: о внутреннем устройстве V8 и оптимизации ...https://habrahabr.ru/company/ruvds/blog/337460/И другие ссылки есть, хотя я этим никогда не интересовался вплотную...
_________________ iLavr
|
19 Jan 2018 21:41 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22735 Location: Silicon Valley
|
Ну никто не сказал, что тут будет V8 Интерпретаторов JS - море
|
19 Jan 2018 21:55 |
|
|
Lavr
Supreme God
Joined: 21 Oct 2009 08:08 Posts: 7777 Location: Россия
|
Не буду спорить, но про предкомпиляцию в нативный код я тут от тебя слышал, когда ты писал какой-то он-лайн схемный интерпретатор. Это я потом поинтересовался, насколько соответствует действительности...
_________________ iLavr
|
19 Jan 2018 22:09 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22735 Location: Silicon Valley
|
Ну на голых сях по любому было бы быстрее
|
19 Jan 2018 22:43 |
|
|
xakepp35
Novelist
Joined: 10 Feb 2016 16:59 Posts: 26
|
нет никакого javascript тут нет и не было. голый c и c++. чуть позже могу выложить исходники если интересно ночка кода, запилил бенчмарк и результаты печальные. 10000 тримуксов (четырёхвходовых гейтов) работают с частотой ~10 килогерц я правда ожидал хотя бы в 10 раз лучший результат.. ну, вкратце там нету никаких if, тоесть это branchless (добавляя if скорость падает раза так в полтора) если я комменчу основные операции по сборке входного данного из разрозненных трит - то скорость возрастает раз эдак в 7, до 70кгц.. =) а операции - это просто разименования указателей, выборка значений из памяти да битовые сдвиги с умножениями, над беззнаковыми целыми.. также посмотрел на зависимость частоты симуляции от разных параметров: от количества гейтов ширины 4: от ширины входа гейта(создаю все 10к гейтов каждый одинаковой ширины inputWidth):
|
19 Jan 2018 23:17 |
|
|
xakepp35
Novelist
Joined: 10 Feb 2016 16:59 Posts: 26
|
шутники.. какой яваскрипт))) код либы это и есть самый что ни наесть голый C и как видно просто адовая кучень разименований памяти, и выборки выборок, плюс чуть умножений делений сдвигов операций И и один цикл фор. это всё что нужно чтобы вычислить значение гейта. я оптимизировал всё что только можно... =( код хоста бенчмарка с++, не влияет на скорость. и, к слову, конфиг компа не самый плохой.
|
19 Jan 2018 23:21 |
|
|
Lavr
Supreme God
Joined: 21 Oct 2009 08:08 Posts: 7777 Location: Россия
|
Это очень сурово... так прямо сходу всё и не понять!
_________________ iLavr
|
19 Jan 2018 23:44 |
|
|
Who is online |
Users browsing this forum: No registered users and 0 guests |
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot post attachments in this forum
|
|