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

[xakepp35]

решил с гитхабом на данном этапе заморачиваться.
в аттаче - 7zip архив - там исходники и бинарник.

tlf.7z

компилил visual studio community 2017 под win10, возможно требует vcredist для 2017й под x64

[xakepp35]

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

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

[Lavr]

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

Это ещё суровее! Особенно "на голых" и "бородатых Сях"..!

[xakepp35]

Это ещё суровее! Особенно "на голых" и "бородатых Сях"..!

ладно, пусть на практике вышло не так производительно как того хотелось бы, не мегагерцы.. но всётаки, как бы подвязать сюда ввод-вывод?)))

[Lavr]

но всётаки, как бы подвязать сюда ввод-вывод?)))

Спросите у модератора Ternary. Он с ввода и вывода начинал.

[xakepp35]

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

меня посетили мысли по оптимизации.

1) если отказаться от универсальности гейта и принять что все гейты - это полюбому тримуксы, то измеряется прирост до 2.5х раз по производительности (~10кгц->~25кгц для 10к гейтов) и экономия памяти бонус 24 байт на гейт. производительность получается изза сокращения числа выборок трита из памяти с 5 (4 для 4 входов+1 для выхода) до 2 (селектор+выход)

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

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

3) OpenCL? PROFIT... в алгоритме нет условных переходов и одновременного чтения/записи в одну и ту же ячейку памяти. значит это задачка под видяху. И следующая версия будет сразу под OpenCL. Ядро вроде маленькое, писать быстро, читаемость повысится изза отсутствия битового шаманства. Я хочу посмотреть, что можно выжать из парадигмы на максимуме производительности

[Shaos]

нет никакого javascript тут нет и не было. голый c и c++. чуть позже могу выложить исходники если интересно

а нижеследующее тогда зачем?

фронтэнд я предполагаю на node.js

[Shaos]

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

[xakepp35]

нет никакого javascript тут нет и не было. голый c и c++. чуть позже могу выложить исходники если интересно

а нижеследующее тогда зачем?

фронтэнд я предполагаю на node.js

а это - чтобы никто не догадался про бороду ))

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

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

к слову я завершил OpenCL реализацию и погонял её туда-сюда. 10к гейтов на проце 100-400кгц, на видяхе R9 270 и того хуже. основная проблема в архитектуре OpenCL, в том моменте когда надо передать данные с хоста на девайс или обратно. линейная прога для проца этого не требует, и если этого делать не нужно то можно выжать приличную производительность.. я сделаю третью попытку - просто реализацию на С++ с ручным распараллеливанием на 4 ядра цпу. почему я откажусь от видях? скажем так - это невысокая скорость обмена данными с хостом, плюс ширина шины видеопамяти соизмерима с таковой у проца. увидев исходники OpenCL kernel всё становится очевидно. OpenCL вариант (возможно) подойдёт лишь для HBM-видеокарт где адовая шина памяти, и если не гонять данные на хост и обратно каждый такт, что начинает уже больше подходить на какойто бесполезный майнинг.. Ну а покачто можно полюбоваться на мой погромизм, вот исходничек OCL версии. (с отказом от упаковки всё уместилось в 1 файлик и стало читаемо):

trimux_sim_ocl_main.cpp

[xakepp35]

 Нарулил годную версию. Под катом тело цикла:

extern "C" extern void alu_step_asm_64(uint64_t trimuxCount, const uint32_t* inputOffset, const uint8_t* inputTape, uint8_t* outputTape);

Code: Select all

; alu_step.asm
; computes trimux array outputs, fastest possible assembly: 2 substractions, 5 moves, 1 cond jump..
; input data layout:
;        rcx: counter, number of trimuxes to process
;        rdx: pointer to the unsigned int* inputAddress array, organised in 4 dwords pack
;        r8: pointer to const char* inputTape 
;        r9: pointer to char* outputTape array

.code

alu_step_asm_64 proc

; Do not process empty array
test		ecx, ecx
je			trimux_loop_finish

; start the loop from end, so need to set "current" trimux inputs pointer rdx to the last element (past the array end) and make address and pointer decrements first operations
; tried  LEA rdx, [rdx+rcx*10h] but cant... and "MOV rax, 16" + "MUL rcx" wrecks rdx.. so LEA is easiest way to go here
mov			rax, rcx						; eax will store offsets in out algorithm
lea			rax, [rax * 4]
lea			rax, [rax * 4]
lea			rdx, [rdx+rax]

trimux_loop:
lea         rdx, [rdx-10h]					; inputOffsetPointer -= 4; // that is where trimux reads indexes
mov         eax,dword ptr [rdx]				; index_t selectorOffset = inputOffsetPointer;
movzx       r10d,byte ptr [r8+rax]			; trit_t selectorValue = inputTape[selectorOffset];
mov         eax,dword ptr [rdx+r10*4+4]		; index_t outputOffset = inputOffset[selectorValue + 1];
movzx       r10d,byte ptr [r8+rax]			; trit_t outputValue = inputTape[outputOffset];
mov         byte ptr [r9+rcx-1],r10b		; outputTape[i-1] = outputValue;
dec         ecx								; i -= 1; // loop counter, sets zero flag if (ecx == 0). must be near JNE instruction for Macro-Operation Fusion on Sandy Bridge
jne			trimux_loop						; if( !i ) goto trimux_loop; // continue looping while non-zero iterations left: ( ecx != 0 )

trimux_loop_finish:
ret
alu_step_asm_64 endp

end

 Для 4 потоков (OpenMP помогает) результаты следующие:

1k тримуксов ~1.5Mhz
10k тримуксов ~350Khz
100k тримуксов ~40Khz
1m тримуксов ~1Khz

Вывод:
Даже на среднем пользовательском i7 можно с комфортом симулировать десятки тысяч тримуксов, не падая ниже сотни кгц.
За сим работу над бенчмарком и анализ производительности можно считать завершённой.

 Упёрся в аппаратные ограничения

- ёщё пробовал simd - и не получилось, тк нужна поддержка инструкции VPGATHERDD, а это AVX2 - не для моего ivy bridge..
- ещё есть такая вещь в винде, large pages. Требует прав админа и возможно позволит на 20% поднять производительность, но это также рассчитано под работу с SIMD

И ещё, можно сильно улучшить показатели, минимум в 4 раза, если заиметь процессор 6950х.

 Причины на то:

1) наличие gather-scatter IO: VPGATHERDD => потенциально более полное и эффективное использование каналов памяти.
2) 4-канальная память DDR4 2400-3200mhz, что просто замечательно для выборок из неё!
3) частота работы также 4ггц, но физических ядер 10 штук, против 4 у 3770k.
это обеспечит высокую стабильность выдаваемой частоты, если распределить ядра примерно так:
- 8 рабочих потоков с полной загрузкой, каждый назначен на свой поток.
- 1 основной поток с высшим приоритетом: контроллер событий ввода-вывода, запуск задания для рабочих потоков, измеритель частоты.
- оставшееся ядро полностью под нужды прочих программ и ОС

Пожалуй, пора запускать кампанию по сбору средств на X99 платформу. Дорогая игрушка, зараза

 уже собрано 300 долларов, осталось ещё немного

BTC: 16WWJX4DBgmqHH2JthxZ2KLguMFK8AqQMr
ETH: 0xeeb0c92dbe5917c24ed06dc98a6549d98bc8cf3e
ETC: 0x6c7faf1562cfb44a84a96aa96ca678ff8252037f
XMR: 4JUdGzvrMFDWrUUwY3toJATSeNwjn54LkCnKBPRzDuhzi5vSepHfUckJNxRL2gjkNrSqtCoRUrEDAgRwsQvVCjZbRw7M3gq5ifC5S5mnqW

Теперь буду думать, над вводом выводом и оформлением всего этого дела в некоторый законченный и работоспособный сервер.
До следующих выходных, наверное, не раньше.