?

Log in

No account? Create an account
LiveJournal for Vadim Radionov.

View:User Info.
View:Friends.
View:Calendar.
View:Memories.
You're looking at the latest 20 entries. Missed some entries? Then simply jump back 20 entries.

Monday, September 17th, 2018

Subject:Квантовые компьютеры. Кажется это уже было
Time:8:20 am.

Не могу сказать, что я понимаю архитектуру будущих квантовых компьютеров. Пожалуй все я я знаю это то что они будут использовать т.н. суперпозицию квантовых состояний (одновременное нахождение в нескольких состояниях) для параллельных вычислений и тем самым добивается (в теории) ускорения на порядки как минимум некоторых оптимизационных задач. И знаете что? А ведь такие задачи уже сейчас можно ускорить на порядки (практически мгновенно — со скоростью света), с помощью примитивного аналогового компьютера, который, к слову, был доступен еще до появления цифровых компьютеров. Хотите. например найти оптимальный путь на кaрте. Не проблема. C помощью обычный резисторов строите эквивалентную схему. Ответ через какую точку проходит оптимальный путь даст нам обычный вольтметр. Я часто замечал как компьютер призадумывается чтобы проложить оптимальный путь. А электрической схеме из резисторов требуется всего лишь время для прохождения света из одного конца в другой. Как свет и электричество решает эту задачу так быстро? Ответ: c помощью той же суперпозии всех возможных путей света. Выходит что обычная схема из резисторов это уже квантовый компьютер, причем доступный нам давным давно.

Comments: Add Your Own.

Sunday, September 16th, 2018

Subject:Интерференция в клеточном автомате. Причины неудачи
Time:8:18 am.

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


data Expr a = At !Index  | PlusMul [(a, Expr a)]


Cтрою его с помощью следующего шага:


step = do cur <- at


          left <- atLeft


          right <- atRight


          return $ PlusMul [((1/3), cur), ((1/3), left), ((1/3), right)]


step это контекстная функция (читалка) которая строится из примитивных читалок at, atLeft, atRight. Она принимает текущий контекст (тек позицию и ее значение,  значение соседей) и возвращает новое значение для текущей позиции. (Другими словами это т.н. reader монада). 


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


initial `coBindZ` step `coBindZ` step 


(initial тут изначальный контект состоящих из ...,At -1 At 0, At 1,... а название coBind как бы должно нам намекать что контекст это комонада)


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


Read more...Collapse )
Comments: Add Your Own.

Saturday, September 15th, 2018

Subject:Неожиданный выбор между IntMap, Map HashMap и Array в haskell
Time:2:11 pm.

Долго мучался выбирая между различными реализациями словарей в плане производительности операции объединения с функцией. Хотел для каждого (key,value) плодить маленькие локальные мапы, с последующим объединением. Своего рода, моноид. Но затем, неожиданно решил, что используя обратное отображение - окружения (соседних элементов) в текущую ячейку, будет проще с производительностью. и выбрал комонаду ZipList a = MkZip [a] !Int [a] вместо словарей. Посмотрим, действительно ли это проще и производительнее. Фактически это функциональный аналог указателей с дешевыми инкрементами.  



Comments: Add Your Own.

Monday, March 26th, 2018

Subject:шкала давления - ноль или один
Time:7:54 am.

Вот что меня сбивает с толку, так это шкала давления в барах. Когда пишут что выпускной клапан открывается при 1.3 бара, а впускной открывается при 0.10, значит ли это что на монометре я увижу не 1.3 бара, а 0.3 бара (минус атмосферное давление снаружи)?



Comments: Add Your Own.

Friday, March 23rd, 2018

Subject:barell shifter в logisim
Time:8:51 am.
Ранее я постил реализацию сдвига вправо на верилоге. Но нашел у себя в архиве более раннюю свою реализацию в logisim.
В отличии от реализации в прошлом посте, в этой реализации  есть сдвиг в обе стороны. Причем без дублирования логики сдвига.


'
Comments: Read 1 orAdd Your Own.

Thursday, October 12th, 2017

Subject:замена MIPS на RISC-V в литературе
Time:8:57 pm.
Классические книги по компьютерной архитектуре потихоньку заменяют MIPS на RISC-V:

1)

Computer Organization and Design RISC-V Edition: The Hardware Software Interface (The Morgan Kaufmann Series in Computer Architecture and Design) 1st Edition



2)
Computer Architecture: A Quantitative Approach ("The sixth edition of this classic textbook is fully revised with the latest developments in processor and system architecture. It now features examples from the RISC-V (RISC Five) instruction set architecture, a modern RISC instruction set developed and designed to be a free and openly adoptable standard")
Comments: Read 3 orAdd Your Own.

Saturday, October 7th, 2017

Subject:"ардуино" нынче уже не тот
Time:2:27 pm.
https://www.sifive.com/products/coreplex-risc-v-ip/u54-mc/

U54-MC Coreplex IP is the world’s first RISC-V based 64-bit quad-core application processor, supporting full-featured operating systems such as Linux. The U54-MC Coreplex’s high-performance and flexible memory system makes it ideal for applications such as AI, machine learning, networking, gateways, and smart IoT devices.
Comments: Add Your Own.

Subject:концепция итераторов
Time:1:54 pm.
Попытался разобраться с Traversable в Хаскелле. Но понял что надо начать хотя бы с "Аппликативных функторов". Начал смотреть последних и набрел на следующую статью:

"The Essence of the Iterator Pattern",
Jeremy Gibbons and Bruno C. d. S.
Oliveira Oxford University Computing Laboratory


В общем, если вы думали что итераторы это просто. Обязательно почитайте эту статью. Взрыв мозга гарантирован.
Comments: Add Your Own.

Saturday, April 8th, 2017

Subject:условные переходы в mips
Time:11:33 am.
Если спросить у гугля про условные переходы в MIPS процессоре, то все ссылки ведут на образовательные сайты.
C армом будет иначе. Я конечно, понимаю что mips гораздо лучше подходит для образования чем arm, но где живет официальная документация?

А хотел я узнать есть ли переход по условию "меньше чем". Потому как, если судить по книге "Computer Organization and Design", разработчики архитектуры mips предпочитают иметь дело только с двумя сравнениями: "равно" и "не равно".
Потому что это условие можно вычислить на стадии декодирования и уменьшить тем самым цену неверного предсказания перехода. Все остально можно сделать комбинацией с инструкцией slt.
Comments: Read 9 orAdd Your Own.

Friday, March 17th, 2017

Subject:как найти в арм коде место использования строки
Time:3:16 pm.
arm проигрывает RISC-V в читаемости

Вчера вечером пытался c помощью objdump -d найти место, в котором вызывается dlsym c нужной мне строкой.
Это ад! Смещение строки в файле известно. Известны все места вызова dlsym.
Проблема в том, что таких мест очень много. Но самая большая проблема в том, как в arm загружается адрес строки.

Выглядит это так (пример из другого кода):

  82b8:       e59f3024        ldr     r3, [pc, #36]   ; 82e4 <main+0x34>
  82bc:       e08f3003        add     r3, pc, r3
   ...
  82e4:       0000a290        .word   0x0000a290
Тут есть подсказка в виде комментария с адресом ячейки, в котором хранится смещение строки относительно pc.
Получается чтобы узнать какой же адрес строки тут грузится, нам надо вручную просуммировать pc c содержимой промежуточной ячейки (82e4, в примере). Это надо делать  для каждого места в котором загружается адрес строки. И у каждого такого места своя промежуточная ячейка. Для thumb-2 та же фигня.

Если бы это был не arm, а скажем RISC-V, то было бы проще:

 10220:       0000c517                auipc   a0,0xc
 10224:       e9450513                addi    a0,a0,-364 # 1c0b4 <__clzsi2+0x84>
Опять же тут есть подсказка. Но в отличии от arm, она указывает на загружаемый адрес строки, который нам известен и вычисляется один раз на основе смещения строки в файле. Т.е. дальше нам бы осталось только запустить поиск.
Comments: Add Your Own.

Monday, March 6th, 2017

Subject:еще один toolchain для RISC-V (rv32i)
Time:9:30 am.
https://github.com/michg/riscv32_lcc
Comments: Read 1 orAdd Your Own.

Sunday, March 5th, 2017

Subject:Самое свежее руководство по RISC-V ISA
Time:10:38 am.
Последние исправления в руководство можно найти здесь:

https://github.com/riscv/riscv-isa-manual

Это исходники руководства в tex формате.
Так что есть возможность видеть историю изменений.
Comments: Read 1 orAdd Your Own.

Tuesday, February 28th, 2017

Subject:Сколько циклов требуется для перехода на обработчик прерывания/ловушки
Time:8:08 am.
Я тут разбираюсь с системными вызовами на Risc-V. ECall как-то слабовато документировал. Да и MRET местами не без вопросом, поэтому полез в исходники эмулятора spike.
Если опустить делигирование прерываний и исключений то логика выглядит следующим образом:

state.pc = state.mtvec;
state.mepc = epc;
state.mcause = t.cause();
if (t.has_badaddr())
state.mbadaddr = t.get_badaddr();
reg_t s = state.mstatus;
s = set_field(s, MSTATUS_MPIE, get_field(s, MSTATUS_UIE << state.prv));
s = set_field(s, MSTATUS_MPP, state.prv);
s = set_field(s, MSTATUS_MIE, 0);
set_csr(CSR_MSTATUS, s);
set_privilege(PRV_M);

Если представить что у нас есть специальный регистровый файл для CSR's, то нам понадобится четыре записи в него. И два чтения.
C однопортовым файлом получится 6 циклов для работы с csr файлом. Плюс еще fetch и decode если не конвеер.
Посмотрел на реализацию Z-scale. Там вроде один порт записи.
Comments: Add Your Own.

Sunday, February 26th, 2017

Subject:сборка 32-битного прокси ядра для RISC-V
Time:11:39 pm.
наконец-то удалось запустить под  эмулятором (spike) 32битную risc-v программу.
Проблема  была в том что pk программа, которая отвечает за вызовы ядра линукс была собрана по умолчанию для RV64.

Но чтобы собрать 32-битную пришлось повозиться. В readme написанно что нужно использовать --enable-32bit
опцию в configure, но эта опция добавляет -m32, который не распознается riscv32-unknown-elf-gcc. Пришлось лезть внутрь configure и удалять эту опцию. Ну или собирать мультиверсионный gcc, который бы понимал -m32
Comments: Read 3 orAdd Your Own.

Tuesday, February 21st, 2017

Subject:Как посмотреть инструкции ассемблера в первозданном виде
Time:10:10 pm.
Бывает смотришь на вывод команды objdump -d и не понятно, где псевдо-инструкция, а где реальная инструкция.

например инструкция ble a0,a1, <label> в RISC-V выглядит как настоящая, а на самом деле это bge a1,a0, <label>

Чтобы не гадать, есть замечательная опция в objdump: -M no-aliases

С ней мы легко убедимся что:

li a0, 10 это addi a0, zero, 10
ret это jalr zero, 0(ra)

и т.д.

кстати, названия регистров выше это тоже своего рода алиасы. Например ra это x1, а zero - это x0.

Чтобы вывод содержал только реальные имена регистров нужно передать опцию -M numeric.

Получится что-то вроде следующего:

00000000 <lt>:
 0: 00b54663         blt x10,x11,c <.L3>
 4: 01400513         addi x10,x0,20
 8: 00008067         jalr x0,0(x1)
0000000c <.L3>:
 c: 00a00513         addi x10,x0,10
10: 00008067         jalr x0,0(x1)
Comments: Read 1 orAdd Your Own.

Sunday, February 19th, 2017

Subject:Конвертация объектника для симуляции в верилог
Time:8:31 am.
Оказывается, в утилите objcopy есть прекрасный флажок: -O verilog позволяющий преобразовать elf формат в вид пригодный
для загрузки в верилог с помощью $readmemh задачи.

скажем мы хотим просимулировать следующий код в верилог:

void test() {
int arg1 = *((int *)0x100);
int arg2 = *((int *)0x104);
*((int *)0x108) = arg1 + arg2;
}

Функция читает два слова по адресу 0x100 и 0x104, суммирует их и записывает результат по адресу 0x108.
В качестве платформы для которой мы будем испытывать симуляцию выберем RISC V, поэтому наш Makefile будет выглядеть следующим образом:

OBJCOPY := riscv32-unknown-elf-objcopy
GCC := riscv32-unknown-elf-gcc

code.hex: test.o
$(OBJCOPY) -O verilog test.o code.hex
test.o: test.c
$(GCC) -O3 -c test.c
После сборки, code.hex будет выглядеть следующим образом:

@00000000
03 27 40 10 83 27 00 10 B3 87 E7 00 23 24 F0 10
67 80 00 00

Здесь содержатся две команды lw, команда add, и команды sw и ret (jalr zero, 0(ra)).

Для наглядности, вот вывод команды objdump для test.o:

00000000 <test>:
0: 10402703         lw a4,260(zero) # 104 <test+0x104>
4: 10002783         lw a5,256(zero) # 100 <test+0x100>
8: 00e787b3         add a5,a5,a4
c: 10f02423         sw a5,264(zero) # 108 <test+0x108>
10: 00008067         ret

Чтобы просимулировать этот код, в верилог мы загружаем code.hex,
устанавливаем PC в ноль, а регистр возврата ra инициализируем значением EXIT_ADDR (0x400).
Загружаем начальные значения в память по адресам 0x100 и 0x104. Затем запускаем на выполнение и вычитываем результат
из памяти по адресу 0x108:

initial begin
$readmemh(PROGRAM_FILE, MEM);
PC = 0;
R[1] = EXIT_ADDR;
write_mem('h100,3);
write_mem('h104,5);
while (PC <= 'h10)
  begin
    fetch;
    execute;
  end
$display("PC = %h", PC);
$display("result = %d", read_mem('h108));
$finish;
end

Здесь выше представлена высокоуровневая поведенческая модель (вернее ее часть с циклом). Для синтезирования она не годится, а вот для проверки правильности нашего понимания ISA очень даже годится.

Вот результат выполнения симуляции:

fetch: IR = 10402703
fetch: IR = 10002783
fetch: IR = 00e787b3
fetch: IR = 10f02423
fetch: IR = 00008067
PC = 00000400
result =          8

Как видим, результат правильный: 3+5=8. PC принимает значение EXIT_ADDR.
Comments: Read 3 orAdd Your Own.

Wednesday, February 1st, 2017

Subject:сложение когда нет регистра с флагами и переносом
Time:8:23 am.
Решил проверить как на 32 битном Risc V (riscv32i) выглядит сложение 64битных чисел:

   0: 00050793         mv a5,a0
 4: 00c50533         add a0,a0,a2
 8: 00f537b3         sltu a5,a0,a5
 c: 00d585b3         add a1,a1,a3
10: 00b785b3         add a1,a5,a1


Дело в том, что на riscv нет статусного регистра с хранимым переносом, поэтому нет команды adc. Вместо нее используется sltu и дополнительный add. Как я понимаю, на MIPS тоже самое.
Непривычно, конечно. Но говорят, что отсутствие флагов упрощает реализацию высокопроизводительных микроархитектур.
Кстати, как и отсутствие branch delay slot'ов.
Comments: Add Your Own.

Saturday, December 31st, 2016

Subject:считаем биты, номер младшей и старшей единицы
Time:1:28 am.
В этот раз вроде работает правильно:


mbc = 0x12131210
hbc = 0xffffaa50
cbc = 0x3ee9e994
> print "val,\tmb,\thb,\tcb"
> for val in range(16):
>     mb = (mbc >> (val << 1)) & 3
>     hb = (hbc >> (val << 1)) & 3
>    cb = (cbc >> (val << 1)) & 3
>    print bin(val),"\t", bin(mb),"\t", bin(hb),"\t",cb

val, mb, hb, cb
0b0  0b0  0b0  0
0b1  0b0  0b0  1
0b10  0b1  0b1  1
0b11  0b0  0b1  2
0b100  0b10  0b10  1
0b101  0b0  0b10  2
0b110  0b1  0b10  2
0b111  0b0  0b10  3
0b1000  0b11  0b11  1
0b1001  0b0  0b11  2
0b1010  0b1  0b11  2
0b1011  0b0  0b11  3
0b1100  0b10  0b11  2
0b1101  0b0  0b11  3
0b1110  0b1  0b11  3
0b1111  0b0  0b11  0

Comments: Add Your Own.

Sunday, December 25th, 2016

Subject:магия цифр или симуляция с помощью lut
Time:9:50 pm.
если я правильно понял, то следующая формула найдет самую младшую единицу в четырех мл. разрядах x и подсчитает ее смещение

x = x & 0xf;
shift = (0xf4 >> x) & 1 | (((0xe >> x) & 1) << 1);

Самое забавное это то как я получил ее:

написал логику на verilog, затем с помощью yosys синтезировал в схему с использованием lut'ов. Результат записал обратно в verilog. Откуда и взял константы для формулы:
Comments: Read 3 orAdd Your Own.

Wednesday, December 14th, 2016

Subject:связывание разделяемых библиотек
Time:10:57 am.
Проверил свою догадку: если брать адрес функции malloc, или любой функции из сторонней библиотеки,
то в каждой библиотеке этот адрес функции malloc будет различным.
Действительно, так и есть. Адрес указывает на внутренности секции .plt. своей библиотеки или исполняемого модуля.

Это чтобы минимизировать таблицу переразмещений.
Comments: Add Your Own.

LiveJournal for Vadim Radionov.

View:User Info.
View:Friends.
View:Calendar.
View:Memories.
You're looking at the latest 20 entries. Missed some entries? Then simply jump back 20 entries.