nedoPC.org

Community of electronics hobbyists established in 2002

...
Atom Feed | View unanswered posts | View active topics It is currently 21 May 2018 03:23



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

Joined: 10 Feb 2016 17:59
Posts: 25
Reply with quote
решил с гитхабом на данном этапе заморачиваться.
в аттаче - 7zip архив - там исходники и бинарник.
Attachment:
File comment: исходники и бинарник
tlf.7z [13.1 KiB]
Downloaded 22 times

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


20 Jan 2018 00:50
Profile
Novelist

Joined: 10 Feb 2016 17:59
Posts: 25
Reply with quote
Lavr wrote:
Это очень сурово... так прямо сходу всё и не понять! :o

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


20 Jan 2018 00:57
Profile
Supreme God
User avatar

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

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

_________________
iLavr


20 Jan 2018 01:04
Profile
Novelist

Joined: 10 Feb 2016 17:59
Posts: 25
Reply with quote
Lavr wrote:
Это ещё суровее! :o Особенно "на голых" и "бородатых Сях"..! :esurprised:

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


20 Jan 2018 01:07
Profile
Supreme God
User avatar

Joined: 21 Oct 2009 09:08
Posts: 7777
Location: Россия
Reply with quote
xakepp35 wrote:
но всётаки, как бы подвязать сюда ввод-вывод?)))

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

_________________
iLavr


20 Jan 2018 01:14
Profile
Novelist

Joined: 10 Feb 2016 17:59
Posts: 25
Reply with quote
ладно, может, придёт идея.. мне надо просто читать и читать про устройство шины ввода-вывода в пк, и я что-нибудь придумаю со временем. наверняка там не так уж и много опций по организации буферизованного I/O. ну а пока, с такими показателями производительности ввод вывод всётаки отходит на второй план.

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

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

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

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

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


20 Jan 2018 10:35
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 16522
Location: Colorado
Reply with quote
xakepp35 wrote:
нет никакого javascript тут нет и не было. голый c и c++. чуть позже могу выложить исходники если интересно


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

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

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


20 Jan 2018 11:42
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 16522
Location: Colorado
Reply with quote
А не сделать ли автору композицию простых схем в более сложные? Тогда сигнатура будет длиннее и выборок станет меньше? Кстати наверное эту мысль надо добавить в DDT, который пока есть наоборот декомпозиция таблиц истинности в цепочки троичных мультиплексоров, а вот симуляция там тупо в лоб по отдельным мультиплексорам, хоть и компилируемое в "голые бородатые си" :)

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


20 Jan 2018 11:47
Profile WWW
Novelist

Joined: 10 Feb 2016 17:59
Posts: 25
Reply with quote
Shaos wrote:
xakepp35 wrote:
нет никакого javascript тут нет и не было. голый c и c++. чуть позже могу выложить исходники если интересно


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

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

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


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


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

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


Last edited by xakepp35 on 20 Jan 2018 14:39, edited 1 time in total.



20 Jan 2018 14:31
Profile
Novelist

Joined: 10 Feb 2016 17:59
Posts: 25
Reply with quote
 Нарулил годную версию. Под катом тело цикла:
extern "C" extern void alu_step_asm_64(uint64_t trimuxCount, const uint32_t* inputOffset, const uint8_t* inputTape, uint8_t* outputTape);
Code:
; 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

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


20 Jan 2018 14:37
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 25 posts ]  Go to page Previous  1, 2

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.