Троичная логика и математика (триты, трайты и прочая нечисть :)

← →
Rouse_ © (2014-12-10 20:14) [0]

Знаю что у нас на форуме есть несколько ребят, которые не то что работали с Эльбрусом, но и принимали непосредственное участие в его создании.
Хотелось бы получить у них определенную консультацию.
В кратце есть сумматор и мультипликатор, реализованный на архитектуре фон Неймана, посредством логического базиса Стрелки Пирса, перетаскиваю все это дело под троичку. Хочется пообщаться с дядькой, который понимает где могут быть затруднения (особливо в мультипликторе).

← →
Rouse_ © (2014-12-10 20:21) [1]

Ну там на самом деле идет пересечение на каждой виртулизированной инструкции через шрих Шеффера (чередуясь), но основная парадигма NOR NAND выдержана.

← →
Rouse_ © (2014-12-10 20:28) [2]

ЗЫ: есесно за такие вещи готов платить :)

← →
Pavia © (2014-12-10 21:34) [3]

Чё правда? За 10 лет впервые слышу.
Кстати китайские аналоги неимоверно подорожали. Думаю пора брать отечественные ноутбуки.

> В кратце есть сумматор и мультипликатор, реализованный на
> архитектуре фон Неймана,

Вообще-то наоборот.

> базиса Стрелки Пирса, перетаскиваю все это дело под троичку.
> Хочется пообщаться с дядькой, который понимает где могут
> быть затруднения (особливо в мультипликтор

Хотелось бы базис увидеть целиком.

Думаю с мультиплексором проблем не будет если его делать через алгоритм Бута. Осталось сделать сумматор. Но он простой на полусумматорах.

← →
Rouse_ © (2014-12-10 23:12) [4]

Я про программную реализацию, не бухти, в вашу аппаратку я не лезу :)

← →
Pavia © (2014-12-10 23:47) [5]

Любая аппаратная реализация это прежде модель. Написанная, отлаженная и оттестированная если хотите программно.

Честно не понимаю вашего вопроса. Так как он очень странный.
Есть система исчисления есть формат представления чисел в памяти.
Из затруднений это только форма в каком коде хранить в прямом или дополненным. Если в прямом то проблем нет. Если в дополненным то с умножением в столбик будут затруднения. А вот у Бута таких нет.
И сумматор делается не трудно: если знаком с динамическим программированием. Кто не понял это я про полусумматоры. Вначале делаете код для него потом собираете из них полный сумматор.

Параллелить и оптимизировать код вам не надо? Иначе как бы смысал стрелки Шифера теряется. Хотя если для запутывания на определённом уровне, можно попробовать с оптимизировать.

← →
Ellisium © (2014-12-11 10:08) [6]

Удалено модератором

← →
Rouse_ © (2014-12-11 10:37) [7]

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

← →
Pavia © (2014-12-11 11:11) [8]

Сумматор:
- Последовательный перенос(на полусумматорах).
- Параллельный перенос.
- многопроходный алгоритм обработки переносов.
- Можно на основе идеи деления пополам сделать.

Слово полусумматор - семантика слова не отражает его смысл.
- сложность T(N)^2;
- сложность O(N*Log(N)); детально не изучал, там оптимизация сложная.Но в целом за рас 4 переноса считает, Правда там параллельные and or от нескольких битовых переменных.
- лучший T(N) худший N(N^2)
- сложность T(2/3*N*Log2(N)); требует дополнительная память.
Делишь по полам и вычисляешь левую часть в двух вариантах с переносом нуля и единицы. Правую и левую вычисляете параллельно

← →
Игорь Шевченко © (2014-12-11 11:12) [9]

> стрелки Шифера

В цитатник

← →
Rouse_ © (2014-12-11 11:43) [10]

> Pavia © (11.12.14 11:11) [8]

Угу, у меня собственно примерно так и получилось (последовательный перенос), просто я не знал что это называется полусумматор :)

← →
Jeer © (2014-12-11 15:48) [11]

https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D1%83%D1%81%D1%83%D0%BC%D0%BC%D0%B0%D1%82%D0%BE%D1%80

← →
Rouse_ © (2014-12-11 16:16) [12]

> Jeer © (11.12.14 15:48) [11]

Это я читал, у меня собственно такое сделано:

Грубо если в виде обычного кода то выглядит вот так:

function FullAdder(A, B, P0: Boolean; var P: Boolean): Boolean; begin Result := ((A or B) and not (A and B)) xor P0; P := (A and B) or (A and P0) or (B and P0); end; function ByteAdd(A, B: Byte): Byte; var I: Integer; ABit, BBit, SFlag, PFlag: Boolean; begin Result := 0; PFlag := False; for I := 0 to 7 do begin ABit := (1 shl I and A) > 0; BBit := (1 shl I and B) > 0; SFlag := FullAdder(ABit, BBit, PFlag, PFlag); Result := Result or (Byte(SFlag) shl I); end; end; function ByteDec(A, B: Byte): Byte; begin Result := ByteAdd(A, -B); end;

все это потом выглядит ввиде сгенерированного машкода, где все инструкици (shl and or и т.п.) эмулируются на стрелке пирса, чередуясь со штрихом шеффера.
Аот с троичным сумматором застрял - никак у меня в голове не складывается эта троичная логика. Буду вечером еще раз вычитывать...

← →
Rouse_ © (2014-12-11 18:55) [13]

> Pavia © (11.12.14 11:11) [8]

Немного почитал еще документации и есть несколько вопросов.

Правильно ли я понимаю следующие вещи:

1. Процессор состоит из элементов логики через которые можно выразить только две операции NOT и AND (т.н. стрелка Пирса). Все остальные эмулируются только на основе данных двух операций.

На данной логике у меня получилось реализовать базовую модель:

type TVMCore = class protected function vmNand(A, B: Integer): Integer; public function vmNot(A: Integer): Integer; function vmAnd(A, B: Integer): Integer; function vmOr(A, B: Integer): Integer; function vmXor(A, B: Integer): Integer; procedure vmMov(A: Integer; var B: Integer); function vmJmp(TrueAddr, FalseAddr: Integer; Cond: Boolean): Integer; end; implementation { TVMCore } function TVMCore.vmAnd(A, B: Integer): Integer; begin Result := vmNand(vmNand(A, B), vmNand(A, B)); end; function TVMCore.vmJmp(TrueAddr, FalseAddr: Integer; Cond: Boolean): Integer; var C: Integer; begin if Cond then C := $FFFFFFFF else C := 0; Result := vmOr(vmAnd(TrueAddr, C), vmAnd(FalseAddr, C)); end; procedure TVMCore.vmMov(A: Integer; var B: Integer); begin B := vmOr(A, A); end; function TVMCore.vmNand(A, B: Integer): Integer; begin Result := not (A and B); end; function TVMCore.vmNot(A: Integer): Integer; begin Result := vmNand(A, A); end; function TVMCore.vmOr(A, B: Integer): Integer; begin Result := vmNand(vmNand(A, A), vmNand(B, B)); end; function TVMCore.vmXor(A, B: Integer): Integer; begin Result := vmOr(vmAnd(A, vmNot(B)), vmAnd(vmNot(A), B)); end;

2. Процессор умеет только складывать (вычитание, умножение и деление производится только посредством сумматоров).

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

3. Сам процессор не работает с числами с плавающей точкой (для этого есть матсопроцессор FPU тобишь) - есть ли для него алгоритмы подобные алгоритму Бута?

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

← →
Rouse_ © (2014-12-11 18:59) [14]

ЗЫ: опять-же я привожу куски кода, которые показывают саму логику работы и на которых я обкатываю идеи, к сожалению ядро движка, который генерирует деревья на основе дизасма привести не могу, ибо ничего не понятно будет без полного включения в задачу, а во вторых пока не готов.

← →
Rouse_ © (2014-12-11 19:03) [15]

Ах да, и еще вопрос.
Я думаю что операции битового смещения SHR, SHL явно работают не через мультипликатор с фиксированной константой, но как именно - пока не знаю, ибо если бы это было бы так, то остаются еще ROL и ROR, где данный подход явно избыточен.
Поэтому по реализации данных функций то-же хочется подсказки.

← →
Rouse_ © (2014-12-11 20:01) [16]

Ну и до кучи, как это переносится (опять-же чисто алгоритмически) на стрелку, реализованную выше:

function TForm4.VMFullAdder(A, B, P0: Byte; var P: Byte): Byte; begin Result := vm.vmXor(vm.vmAnd(vm.vmOr(A,B), vm.vmNot(vm.vmAnd(A, B))), P0); P := vm.vmOr(vm.vmAnd(A, B), vm.vmOr(vm.vmAnd(A, P0), vm.vmAnd(B, P0))); end;

← →
Pavia © (2014-12-11 20:33) [17]

> 1. Процессор состоит из элементов логики через которые можно
> выразить только две операции NOT и AND (т.н. стрелка Пирса).
> Все остальные эмулируются только на основе данных двух
> операций.

Я до этого ещё не добрался. Поэтому могу немного ошибаться.
В процессоре есть ещё две константы 0,1 , регистры (триггеры), провода, сопротивление.
AND - грубо говоря реализуется простым слиянием проводов. Проводное-И (инженерное-И). NOT - двумя транзисторных ключа.
Железячки поправят если что.

Константы можно и через AND и NOT определить.
A AND (Not A)=0
NOT (0)=1

AND и NOT являются базовыми операциями в Булевой алгебре. Поэтому их и называют базисом так как из них можно получить любую Булевую операцию.
Операция x op y = z. 3 переменных по 2 состояния каждая итого 8 операторов. Для проверки являются тот или иной набор базовым достаточно проделать простой перебор всех вариантов. Можно применят сведение к предыдущему доказанному.

> 2. Процессор умеет только складывать (вычитание, умножение
> и деление производится только посредством сумматоров).

Так уже полвека не делают. Есть VHDL, Verilog.
Verilog - простой язык описания аппаратуры. Комбинаторная логика. Т.е логика на битовых операциях. Есть регистры, провода. Провода есть разные, но чаще всего используют тот который AND. Другие типы проводов можно получить использованием логической операции NOT.

Для регистров определено присвоение. Двух типов с блокировкой и без(с синхронизаций и без так как присвоение может идти паралельно).
Для удобство разработки введено сложение и умножение.

Я уже упоминал про константы. В ПЛИС к примеру операции реализуется на таблицах.
Любую функцию можно представить таблицей, для таблиц есть алгоритмы ДНФ и КНФ (СНКФ, СДНФ) - эти алгоритмы позволяют построить функции из and, or, not.

> 2. Процессор умеет только складывать (вычитание, умножение
> и деление производится только посредством сумматоров).

Не только складывать ещё переходы и сдвиги.
Так было в 8080. Это так называемые процессоры с аккумулятором.
Есть и другие. Где мультипликаторы сделаны в логике.

Минимальный набор процессора можно посмотреть к примеру у TI у них RISC - процессор имеет всего 27 инструкций.
http://www.ti.com/lit/ug/slau259e/slau259e.pdf
Умножение там вообще отдельным блоком.

Сдвиги делаются либо по тактово. Либо через Barrel shifter
https://ru.wikipedia.org/wiki/Barrel_shifter
Перенос на один бит. Это присвоение битов(регистров), но выполняется оно параллельно. И защелкивается, запоминается по фронту в триггере.

> 3. Сам процессор не работает с числами с плавающей точкой
> (для этого есть матсопроцессор FPU тобишь) - есть ли для
> него алгоритмы подобные алгоритму Бута?

Есть, но тут лучше скопипастит готовое, а то долго разрабатывать будете.
К примеру у TI, AVR , ARM, Borland Bascal, Bochs есть эмулятор сопроцессора на процессоре.

Если хотите сами, то математика для алгоритмов есть в.
Байков В. Д., Смолов В. Б. Специализированные процессоры: итерационные алгоритмы и структуры, Москва, «Радио и связь», 1985, 288 стр.
Но она медленная для эмуляции. Всё таки в процессорах исполнение параллельное.

← →
Rouse_ © (2014-12-11 20:43) [18]

> Pavia © (11.12.14 20:33) [17]

Ох тыж блин, спасибо, пошел все это обдумывать.

← →
Rouse_ © (2014-12-11 20:46) [19]

Еще момент:

> Есть, но тут лучше скопипастит готовое, а то долго разрабатывать
> будете.
> К примеру у TI, AVR , ARM, Borland Bascal, Bochs есть эмулятор
> сопроцессора на процессоре.

Это в опенсорсе?

← →
Rouse_ © (2014-12-11 20:52) [20]

> Минимальный набор процессора можно посмотреть к примеру
> у TI у них RISC - процессор имеет всего 27 инструкций.
> http://www.ti.com/lit/ug/slau259e/slau259e.pdf
> Умножение там вообще отдельным блоком.

Спасибо, гляну, я свою первую вариацию RISC делал на 52 инструциях и в итоге все получилось не правильно, ибо на тот момент я вообще, как оказалось, даже не представлял чего хочу добиться.
Сейчас уже четвертая попытка реализации виртуального процессора :)

← →
Rouse_ © (2014-12-11 20:54) [21]

ЗЫ: в качестве шутки, самая первая закончилась на том этапе, что я не смог написать отладчик для виртуальной модели и банально не смог развивать дальше саму VM :)

← →
Inovet © (2014-12-12 03:17) [22]

Чёт не пойму: ты хочешь эмуляцию аппаратуры сделать?

← →
Rouse_ © (2014-12-12 10:09) [23]

> Inovet © (12.12.14 03:17) [22]
> Чёт не пойму: ты хочешь эмуляцию аппаратуры сделать?

Нет, просто идея эмуляции строится на принципах работы процессора.

← →
Romkin © (2014-12-12 11:24) [24]

Э. А зачем моделировать схемотехнику процессора? Неужели тебе просто эмуляции команд недостаточно?

← →
Romkin © (2014-12-12 11:29) [25]

Тебя, например, триты (-1,0,1) не устроят? Там NEG весело делается :)
PS. "вкратце". Или объясняй, что такое "кратец".

← →
Rouse_ © (2014-12-12 11:30) [26]

> Romkin © (12.12.14 11:24) [24]

А что в твоем понимании есть виртуализация?
Замена одной инструкции идентичным набором пары других?
В моем случае даже в однопроходном варианте банальный INC EAX превращается в лапшу из порядка 15 тысяч асм кода в 99 процентов состоящих из операций NOT, AND и OR, что меня вполне устраивает.
Это примерно на том-же уровне который выдает StarForce или ExeCryptor (который тоже использует стрелку пирса и разворачивает все циклы VM в виде асм кода)

← →
Rouse_ © (2014-12-12 11:31) [27]

> Romkin © (12.12.14 11:29) [25]
> Тебя, например, триты (-1,0,1) не устроят? Там NEG весело
> делается :)

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

← →
Romkin © (2014-12-12 11:52) [28]

> А что в твоем понимании есть виртуализация? Замена одной
> инструкции идентичным набором пары других?

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

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

> Вот и интересно, какой уровень ты эмлировать собрался?

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

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

Нелогично. Команда процесстора - по сути функция. Я спрашивал немного о другом: тебя устроит эмуляция на уровне регистров или ты хочешь опуститься на уровень битов (каждый считать отдельно) или еще ниже, эмулировать работу логического элемента, соединяя их?

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

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

http://mzhurkin.ru/wp-content/uploads/2012/11/%D0%90%D1%80%D1%85%D0%B8%D1%82%D0%B5%D0%BA%D1%82%D1%83%D1%80%D0%B0-%D0%BA%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80%D0%B0_%D0%A2%D0%B0%D0%BD%D0%B5%D0%BD%D0%B1%D0%B0%D1%83%D0%BC_2003-4-%D0%B5-%D0%B8%D0%B7%D0%B4.pdf

начиная с главы 4.
Да и вообще полезная для чтения книга

Ну вот, еще один здоровый букварь в копилку :)
http://rouse.drkb.ru/books.php

А про новый закон о авторских правах кто ни будь в курсе?

http://publication.pravo.gov.ru/Document/View/0001201411250005?index=0&rangeSize=1

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

> > Inovet © (12.12.14 03:17) [22]
> > Чёт не пойму: ты хочешь эмуляцию аппаратуры сделать?
>
> Нет, просто идея эмуляции строится на принципах работы процессора.

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

> Inovet © (13.12.14 00:19) [38]
> Работа процессора может быть очень разнообразно реализована,
> в том числе и программы могут там работают, не те которые
> на АСМ пишутся - другие.

Это как? ARM начнет интеловский машкод выполнять? :)

> С точки зрения программера - это все аппаратная реализация

С точки зрения моего пользователя, он даже не знает как это все работает. Его задача просто показать начало и конец защищаемого блока, а остальное не его забота :)

> ARM начнет интеловский машкод выполнять?

к сожалению моему, как обладателю горстки армов (а то и двух горстей), не начнет....

Троичная логика и математика (триты, трайты и прочая нечисть :) Найти похожие ветки