nedoPC.org

Community of electronics hobbyists established in 2002

...
Atom Feed | View unanswered posts | View active topics It is currently 24 May 2020 19:55



Reply to topic  [ 25 posts ]  Go to page 1, 2  Next
Профессиональный троичный логический симулятор 
Author Message
Novelist

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


Last edited by xakepp35 on 19 Jan 2018 14:42, edited 1 time in total.



19 Jan 2018 14:31
Profile
Novelist

Joined: 10 Feb 2016 17:59
Posts: 26
Reply with quote
Начну с описания базовых вещей и идей, своего видения деталей эффективной реализации. Итак, непосредственно сам эмулятор, исполнитель. Ядро эффективности эмуляции в том, что любая н-арная троичная логическая функция (тлф) может быть задана номером длиной 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 14:42, edited 1 time in total.



19 Jan 2018 14:33
Profile
Novelist

Joined: 10 Feb 2016 17:59
Posts: 26
Reply with quote
Второй компонент системы включает загрузчик, служебные форматы, чтобы читать например из файла схему соединения этих гейтов, начальные ромы, всяческий маппинг памяти, и сопутствующие утилиты например чтобы эти файлы генерировать не вручную в HEX редакторе а из более высокоуровнего языка (как ассемблер и линкер), и возможно даже гуи для наглядного редактирования. Это второстепенная задача и достаточно прозрачна для реализации. Самое сложное тут пожалуй - это наличие времени на разработку фишечек и хорошее видение гуи редактора логики, чтобы можно было оперировать как с отдельными гейтами так и с целыми блоками и с блоками блоков, разумеется с зуммированием копированием и переиспользованием рекурсивно, путём простых манипуляций мышкой с выключенным мозгом)) Это я предполагаю оставить напоследок или на аутсорс =) Сначала нужно реализовать ядро системы и оценить эффективность однопоточной работы на небольших ромах составленных вручную или специальной тестовой программой. А также решить следующий важный вопрос.


Last edited by xakepp35 on 19 Jan 2018 14:52, edited 1 time in total.



19 Jan 2018 14:35
Profile
Novelist

Joined: 10 Feb 2016 17:59
Posts: 26
Reply with quote
Я надеюсь я смог обьяснить базовую идею. Всётаки пришлось дать некоторый объём текста. И предлагаю обсудить, что в данном случае мне непонятно, и вызывает самые большие вопросы и сомнения - так это третий компонент - модуль ввода вывода для симулятора. Без него - это как проц без материнки. Как подвязать весь этот скоп гейтов и тритов, к внешним устройствам? Нужен какой-то простой интерфейс, который позволит подключать программный эмулятор монитора, клавиатуры, вшешнего накопителя, сетевой или звуковой карты. Вроде понятно что это просто куча самописных драйверов, сводящимся к вызовам sockets api или opengl. Я про саму парадигму, хочу ваших советов, мыслей, идей. Как это сделать универсально, эффективно и расширяемо? Как в процессорах ввод вывод этот организован?


19 Jan 2018 14:41
Profile
Supreme God
User avatar

Joined: 21 Oct 2009 09:08
Posts: 7777
Location: Россия
Reply with quote
Для троичных конструкций у нас есть специальная ветка Ternary.
(Перенёс в Ternary.)

_________________
iLavr


19 Jan 2018 17:33
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18573
Location: Silicon Valley
Reply with quote
я боюсь, что тормоза JS съедят все изыски по бинарному ускорению симуляции ;)

_________________
:eugeek: https://twitter.com/Shaos1973


19 Jan 2018 19:57
Profile WWW
Supreme God
User avatar

Joined: 21 Oct 2009 09:08
Posts: 7777
Location: Россия
Reply with quote
Shaos wrote:
я боюсь, что тормоза JS съедят все изыски по бинарному ускорению симуляции ;)

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

_________________
iLavr


19 Jan 2018 21:09
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18573
Location: Silicon Valley
Reply with quote
Lavr wrote:
Shaos wrote:
я боюсь, что тормоза JS съедят все изыски по бинарному ускорению симуляции ;)

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

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

_________________
:eugeek: https://twitter.com/Shaos1973


19 Jan 2018 22:26
Profile WWW
Supreme God
User avatar

Joined: 21 Oct 2009 09:08
Posts: 7777
Location: Россия
Reply with quote
Shaos wrote:
Lavr wrote:
Shaos wrote:
я боюсь, что тормоза JS съедят все изыски по бинарному ускорению симуляции ;)

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

JavaScript? Это вряд ли...
Ну здрасти! :esurprised:

Как работает JS: о внутреннем устройстве V8 и оптимизации ...
https://habrahabr.ru/company/ruvds/blog/337460/
Quote:
При первом исполнении JS-кода V8 задействует компилятор full-codegen, который напрямую, без каких-либо дополнительных трансформаций, транслирует разобранный им JavaScript-код в машинный код. Это позволяет очень быстро приступить к выполнению машинного кода.

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

_________________
iLavr


19 Jan 2018 22:41
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18573
Location: Silicon Valley
Reply with quote
Ну никто не сказал, что тут будет V8 ;)
Интерпретаторов JS - море

_________________
:eugeek: https://twitter.com/Shaos1973


19 Jan 2018 22:55
Profile WWW
Supreme God
User avatar

Joined: 21 Oct 2009 09:08
Posts: 7777
Location: Россия
Reply with quote
Не буду спорить, но про предкомпиляцию в нативный код я тут от тебя слышал,
когда ты писал какой-то он-лайн схемный интерпретатор.
Это я потом поинтересовался, насколько соответствует действительности...

_________________
iLavr


19 Jan 2018 23:09
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18573
Location: Silicon Valley
Reply with quote
Ну на голых сях по любому было бы быстрее ;)

_________________
:eugeek: https://twitter.com/Shaos1973


19 Jan 2018 23:43
Profile WWW
Novelist

Joined: 10 Feb 2016 17:59
Posts: 26
Reply with quote
нет никакого javascript тут нет и не было. голый c и c++. чуть позже могу выложить исходники если интересно
ночка кода, запилил бенчмарк и результаты печальные.
10000 тримуксов (четырёхвходовых гейтов) работают с частотой ~10 килогерц
Attachment:
operation.png
operation.png [ 31.12 KiB | Viewed 5633 times ]

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

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

от количества гейтов ширины 4:
Attachment:
File comment: зависимость частоты от количества гейтов ширины 4
frequency_vs_gates_count.png
frequency_vs_gates_count.png [ 32.29 KiB | Viewed 5633 times ]


от ширины входа гейта(создаю все 10к гейтов каждый одинаковой ширины inputWidth):
Attachment:
File comment: зависимость частоты симуляции от ширины входа гейта при 10к гейтов
frequency_vs_input_width.png
frequency_vs_input_width.png [ 37.23 KiB | Viewed 5633 times ]


20 Jan 2018 00:17
Profile
Novelist

Joined: 10 Feb 2016 17:59
Posts: 26
Reply with quote
шутники.. какой яваскрипт))) код либы это и есть самый что ни наесть голый C
Attachment:
File comment: алу
impl.png
impl.png [ 37.93 KiB | Viewed 5632 times ]

Attachment:
File comment: бцт
impl1.png
impl1.png [ 21.01 KiB | Viewed 5632 times ]

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

код хоста бенчмарка с++, не влияет на скорость.
и, к слову, конфиг компа не самый плохой.
Attachment:
File comment: конфиг хост пк
pc_config.png
pc_config.png [ 25.88 KiB | Viewed 5632 times ]


20 Jan 2018 00:21
Profile
Supreme God
User avatar

Joined: 21 Oct 2009 09:08
Posts: 7777
Location: Россия
Reply with quote
xakepp35 wrote:
адовая кучень разименований памяти, и выборки выборок, плюс чуть умножений делений сдвигов операций И

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

_________________
iLavr


20 Jan 2018 00:44
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 25 posts ]  Go to page 1, 2  Next

Who is online

Users browsing this forum: No registered users and 2 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

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.