Как стать автором
Обновить

Комментарии 36

К сожалению в понедельник 30.09.2019 уезжаю на недельку в края, где тырнетов нету, а расскажи местным про такое чудо — в жизни не поверят. Поэтому на комментарии буду отвечать где-то до 16:00 понедельника. Потом уже только через неделю.
Спасибо за статью.

P.S. Не удержался:
уезжаю на недельку в края, где тырнетов нету

На недельку, до log222
Я уеду в Комарово
НЛО прилетело и опубликовало эту надпись здесь
Спасибо! Первый раз тут публикуюсь, опасался что заминусуют :))

Откуда такие предрассудки?))

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

"не читайте до обеда советских газет" и продолжайте писать хорошие статьи.

Я и не сомневался, что это известно(ну не могло быть неизвестно !), но додумываться пришлось самому. По Вашей ссылке бегло посмотрел, вроде бы речь идёт о чём-то похожем. Но сходу увидеть в точности я этого не могу. Возможно тот же алгоритм, возможно другой. Надо подробнее почитать.

Я не в теме, но не является ли это реинкарнацией Кордика?

Совсем нет. Кордик требует таблицы. Вот гляньте ru.wikipedia.org/wiki/CORDIC. Если в теории по ссылке заменить тригонометрические функции гиперболическими, вместо обычного арктангенса будет считаться гиперболический, который и есть логарифм. А тут была цель как раз всё сделать без таблицы. Но поскольку бесплатный сыр бывает только в мышеловке, за это пришлось заплатить умножителем. В том проекте меня такой размен устраивал. Всё равно умножитель там использовался и имел приличное свободное окно. Я его просто дополнительно нагрузил, сэкономив при этом блочную RAM.

А я такие вещи делал на ПЛИС методом Ньютона-Рафсона. Там тоже нужен один умножитель. Интересно дает ли он лучший результат за то же число тактов?

Трудно сказать. Сходимость Ньютона-Рафсона определяется производной. А значит скорее всего меняется от итерации к итерации. У меня тут стабильно и честно один бит на итерацию. С Ньютоном-Рафсоном как-то не догадался. Хотя казалось бы чего проще… Надо будет попробовать. Любопытный вопрос!
А можно раскрыть в форме гайда / туториала тему верификации такого кода на Verilog и синтеза его под физическую FPGA? Какой софт вы для всего этого используете?
Ну как бы не претендую… Вобщем тут немного раскрыта моя манера разработки. Отталкиваясь от чего-то тёплого, лампового и аналогового, сначала перейти к жесткой фиксированной точке, а после к совсем уже жестокому железу. Переход к верилогу от целочисленной (с фиксированной точкой) модели на С как правило достаточно безболезненный. Ибо уже на С становятся достаточно хорошо видны некоторые будущие аппаратные компоненты (счетчики, сдвиговые регистры, аккумуляторы, мультиплексоры и т.п.). Ну и последний этап моделирования — совместная доводка С и верилога до стадии, когда их результаты совпадают бит в бит. Для моделирования использую icarus verilog как симулятор и gtkwave как просмотрщик временных диаграмм. Под Windows это тоже есть. Для громадных тестов — verilator.

Если говорить о реальном железе, это синтезировалось разумеется на Квартусе, чем же ещё Cyclone IV разводить? Ну а если Вы новичок и хотите освоить FPGA, очень советую начать с платки iCE40-HX8K Breakout Board www.latticesemi.com/en/Products/DevelopmentBoardsAndKits/iCE40HX8KBreakoutBoard.aspx. FPGA там не очень большая, всего 8К ячеек. Но во-первых этого вполне достаточно чтобы собрать даже 32-битный процессор для которого написан компилятор С. Во-вторых с ней крайне удобно работать. Там стоит двухканальный чип FTDI. По одному каналу шьётся FPGA. А другой канал работает как UART, выведен на ноги FPGA и виден из проекта. Если Вы реализуете UART в своём проекте (на этом хабе была статья про его реализацию), то сможете общаться с FPGA прямо с компьютера, причем через тот же usb-кабель, через который шили проект. Дико удобно! В третьих софт. В отличии от не к ночи помянутых Квартуса и Вивадо с их десятками гигабайт на диске, у этой есть очень качественный опенсорсный инструментарий, влезающий в 150 мегабайт на диске www.clifford.at/icestorm. Под Windows тоже есть.

Для общения с железкой со стороны компа очень рекомендую писать на яве, используя библиотеку jSerialComm fazecast.github.io/jSerialComm. Исключительно удобно! А для меня так просто спасение, учитывая что я под линуксом, а заказчики в основном под Windows.

А вообще сейчас эта платка со связкой верилог + ява — мой главный инструмент для разборок со всяческой электроникой. И Вам советую с неё же начинать. Вот примерно так…
Спасибо!
Вот это я понимаю — программирование!
А можете что-нибудь похожее для моей Аскоты придумать? У неё есть сложение, вычитание и логика, но нет умножения, деления и десятичного сдвига.
Глянул — жуть! Аж обзавидовался белой и черной завистью! :)))
Надо же какие вещи у людей ещё сохранились! Но придумать для неё боюсь что-либо сложно. 50 шагов программы это увы… Наверно можно сделать эмулятор на джаваскрипте, и выложить куда-нибудь для желающих попробовать себя в таком экзотическом деле :)
Правда, при каждом возведении в квадрат у нас удваивается погрешность. Так что нужно выполнять вычисление в формате, у которого количество значащих битов хотя бы вдвое больше желаемой точности.
Давайте считать. Пусть в аккумуляторе оказалось число X с погрешностью d. Если принять Х за 1 (условно), то d будет порядка 2 ^(-17) (один разряд 17-разрядного числа). Возведём в квадрат, пренебрегая квадратом d:
(x + d)^2 = x^2 + 2dx, где величина 2dx тоже порядка 2^(-17) и можно сказать что она примерно равна d.
Пусть в результате отбрасывания младших разрядов, наложилась новая погрешность d1, тоже порядка 2^(-17) и тоже примерно равная d. Тогда после итерации в аккумуляторе будет число (x1+2d) и т.д. Т.е. (x2+3d), (x3+4d), (x4+5d)…
Иными словами погрешность растёт в худшем случае ЛИНЕЙНО, а не экспотенциально (каждый раз удваиваясь), как Вы утверждаете. И при 16 итерациях поражает только 4 младших разряда. На самом деле она растёт ещё медленнее. Но чтобы это доказать, надо лезть в дебри.
После первой итерации — да, 2d*x. А после второй итерации у нас получается (x1+2dx)^2=x1^2+4d*x1, после третьей — (x2+4dx)^2=x2^2+8d*x2 и так далее. Так что всё же экспоненциально.

Утверждение, что «2d*x примерно равно d» — это, извините, очень странное утверждение.
Практика показывает что погрешности здесь не растут. Запустите сишный код где считается целочисленная версия и убедитесь. Он там сравнивается с библиотечной функцией log2 и ошибки там на уровне 2^(-16) при 16 разрядах. Признаю, с предыдущим комментарием был не прав. С погрешностями я тут разбирался, но это было 4 года назад. Сейчас несколько подзабыл это дело. Буду разбираться. Но это уже через неделю. Завтра уезжаю и у меня там не будет ничего кроме планшетника и телефона. И интернета тоже не будет.

Ради прикола, сделал ваш алгоритм в Matlab/Simulink.


Тестовая модель с входным и выходным результатом(входные floating point преобразуются в fixed point с умножением на 2^17 и обратно с делением):

Сама реализация уже с фиксированной точкой(блок Log2):

Результаты моделирования (сигналы U, S, res c модели выше (помечено синим)). Выход компаратора S — это, собственно и есть результат побитно, он сдвигается.


Ну и вишенка, HDL код из блока LOG2. Хотите Verilog, хотите VHDL. С комментариями и ссылками, что из каких блоков получилось.


Source Code
// -------------------------------------------------------------
// 
// File Name: hdlsrc\log2\Log2.v
// Created: 2019-09-29 21:03:43
// 
// Generated by MATLAB 9.5 and HDL Coder 3.13
// 
// 
// -- -------------------------------------------------------------
// -- Rate and Clocking Details
// -- -------------------------------------------------------------
// Model base rate: 1
// Target subsystem base rate: 1
// 
// -------------------------------------------------------------

// -------------------------------------------------------------
// 
// Module: Log2
// Source Path: log2/Log2
// Hierarchy Level: 0
// 
// -------------------------------------------------------------

`timescale 1 ns / 1 ns

module Log2
          (clk,
           In_rsvd,
           Out_rsvd);

  input   clk;
  input   [17:0] In_rsvd;  // ufix18
  output  [17:0] Out_rsvd;  // ufix18

  reg [7:0] Counter_Limited_out1;  // uint8
  wire Compare_To_Constant_out1;
  wire [35:0] Bit_Shift_out1;  // ufix36
  wire [35:0] Bit_Shift1_out1;  // ufix36
  wire [17:0] Bit_Shift1_out1_dtc;  // ufix18
  wire [17:0] Bit_Shift_out1_dtc;  // ufix18
  wire S_S;
  wire [17:0] U_U;  // ufix18
  reg [17:0] Delay_out1;  // ufix18
  wire [17:0] U_U_1;  // ufix18
  wire [35:0] Divide_out1;  // ufix36
  wire Relational_Operator_relop1;
  wire [17:0] Data_Type_Conversion1_out1;  // ufix18
  wire [17:0] res;  // ufix18
  reg [17:0] Delay1_out1;  // ufix18
  wire [17:0] Bit_Shift2_out1;  // ufix18

  initial begin
    Counter_Limited_out1 = 8'b00000000;
    Delay_out1 = 18'b000000000000000000;
    Delay1_out1 = 18'b000000000000000000;
  end

  // Count limited, Unsigned Counter
  //  initial value   = 0
  //  step value      = 1
  //  count to value  = 16
  // 
  // <S1>/Counter Limited
  always @(posedge clk)
    begin : Counter_Limited_process
      if (Counter_Limited_out1 >= 8'b00010000) begin
        Counter_Limited_out1 <= 8'b00000000;
      end
      else begin
        Counter_Limited_out1 <= Counter_Limited_out1 + 8'b00000001;
      end
    end

  // <S1>/Compare To Constant
  assign Compare_To_Constant_out1 = Counter_Limited_out1 == 8'b00000000;

  // <S1>/Bit Shift1
  assign Bit_Shift1_out1 = Bit_Shift_out1 >> 8'd1;

  assign Bit_Shift1_out1_dtc = Bit_Shift1_out1[17:0];

  assign Bit_Shift_out1_dtc = Bit_Shift_out1[17:0];

  // <S1>/Switch1
  assign U_U = (S_S == 1'b0 ? Bit_Shift_out1_dtc :
              Bit_Shift1_out1_dtc);

  // <S1>/Delay
  always @(posedge clk)
    begin : Delay_rsvd_process
      Delay_out1 <= U_U;
    end

  // <S1>/Switch
  assign U_U_1 = (Compare_To_Constant_out1 == 1'b0 ? Delay_out1 :
              In_rsvd);

  // <S1>/Divide
  assign Divide_out1 = U_U_1 * U_U_1;

  // <S1>/Bit Shift
  assign Bit_Shift_out1 = Divide_out1 >> 8'd17;

  // <S1>/Relational Operator
  assign Relational_Operator_relop1 = Bit_Shift_out1 > 36'h00003FFFF;

  assign S_S = Relational_Operator_relop1;

  // <S1>/Data Type Conversion1
  assign Data_Type_Conversion1_out1 = {17'b0, S_S};

  // <S1>/Delay1
  always @(posedge clk)
    begin : Delay1_process
      Delay1_out1 <= res;
    end

  // <S1>/Bit Shift2
  assign Bit_Shift2_out1 = Delay1_out1 <<< 8'd1;

  // <S1>/Bitwise Operator
  assign res = Data_Type_Conversion1_out1 | Bit_Shift2_out1;

  assign Out_rsvd = res;

endmodule  // Log2

Могу также сгенерить VHDL, кому интересно.
Код, возможно, не самый оптимизированный, но должен быть 100%-но рабочий. Синтезатор лишнее все равно выкинет.

Жуть!!! АДЪ и Израиль! :))))))))))
Жаль картинки тут плохо видны, трудно понять что за модель. И последний рисунок у Вас неверный. Вы очевидно трактуете res как просто число. Сначала маленькое, но постепенно заполняющее старшие разряды. А тут скорее надо себе представить, что разряды заполняются начиная со старших и вправо. Т.е. первым появляется самый старший разряд, за ним следующий, следующий и т.д. Тогда получится картинка не экспотенциального роста, а экспотенциального приближения к результату, причем строго снизу, без колебаний.
С кодом да, любопытно было бы. Кстати что удивительно, он более не менее читаем!!! Вот чего не ожидал… К сожалению Вы забыли реализовать сигналы wr (начинающий вычисление) и rdy (готовность результата). Без них моделировать нельзя. Вычисления надо как-то начать и как-то остановить. Если я полезу сейчас вставлять их ручками, боюсь чего-нибудь напортачу. Да и впечатление будет немного не то.

А вообще побаиваюсь я честно говоря таких вещей. Когда я вижу верилог (по крайней мере в той манере в которой пишу сам) я неплохо представляю себе, во что это развернется. А с такой моделью — хрен знает… Впрочем у меня тут сильно испорченное ассемблером прошлое. Я из-за этого и С долго не мог освоить. Мол не понимаю я этих ваших операторов! Скажите что машина делает! Сейчас привык и неплохо себе представляю, во что разворачивается С. Но по той же причине не могу освоить Rust. Для меня очень важная штука — «прозрачность» языка.
Жаль картинки тут плохо видны, трудно понять что за модель

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


И последний рисунок у Вас неверный. Вы очевидно трактуете res как просто число. Сначала маленькое, но постепенно заполняющее старшие разряды. А тут скорее надо себе представить, что разряды заполняются начиная со старших и вправо

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


К сожалению Вы забыли реализовать сигналы wr (начинающий вычисление) и rdy (готовность результата). Без них моделировать нельзя.

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


Если я полезу сейчас вставлять их ручками, боюсь чего-нибудь напортачу. Да и впечатление будет немного не то

Не надо никуда лезть ручками, тем более в сгенерированный код! Если хотите, могу дорисовать пару регистров. Тогда моя модель будет работать как ваш verilog код, и сгенерированный код будет так же bit and cycle-true.


А вообще побаиваюсь я честно говоря таких вещей. Когда я вижу верилог (по крайней мере в той манере в которой пишу сам) я неплохо представляю себе, во что это развернется.

Просто Verilog — он как ассемблер для ПЛИС. Вы работаете на уровне базовых физических блоков — сигналов, ячеек, регистров. А надо не бояться и здесь переходить на языки более высокого уровня — так вы абстрагируетесь от железа и можете сконцентрироваться на решении основной задачи, получая результат гораздо быстрее. Да и знания Verilog/VHDL тогда становятся не такими критичными — главное, понимать ограничения ПЛИС — задержки и фиксированную запятую.


А вообще интересно мнение здешних ITшников — ваш Си код они, конечно, понимают, а понимают ли они представленную модель из Матлаба? Ведь из нее с тем же успехом можно сгенерить как HDL код, так и тот же Си-код для какого-нибудь микроконтроллера, причем хоть 8-и битного, хоть 32-х битного и оно будет работать.

Я не забыл, просто они для моделирования не нужны — у вас же в Си коде их тоже нет?

Как бы в С они неявно тоже есть. Сигнал wr — начать вычисления это вызов функции. А rdy — готовность, это выход из функции. Что-то подобное должно быть в любом модуле, действующем с «началом и концом» так сказать. Ладно, прошу прощения, уже собираюсь тут в дорогу. Теперь появлюсь через неделю, вряд ли раньше.
Как бы в С они неявно тоже есть. Сигнал wr — начать вычисления это вызов функции. А rdy — готовность, это выход из функции. Что-то подобное должно быть в любом модуле, действующем с «началом и концом» так сказать.

Ну вы же сами писали:


Языки описания аппаратуры(верилог в частности) описывают не программу как последовательность исполняемых команд, а сеть параллельных процессов. Всё выполняется по всей «программе» (на самом деле сети), как только возникли подходящие для этого условия. Что кстати требует от разработчика мышления сильно не такого, как у программистов.

То есть начала и конца у данной функции нет, так как она будет сделана в железе из физических ячеек и сигналов и будет молотить постоянно и независимо от других. И "подходящие условия" необязательно должны определяться сигналами wr и RDY. Можно легко сделать так, что новое входное значение для нее будет готово как раз к тому моменту, когда она закончит считать предыдущий логарифм (что, собственно, частый кейс в обработке сигналов) и это мы еще не смотрели на возможность конвейеризации, upsampling и TDM, которую я не моделировал, но должна быть здесь легко возможна — и интерфейсные сигналы будут в этом случае совсем другие.
А результат из этой функции может браться опять же ровно через 16 тактов — это же фиксированное число.
То есть wr и rdy — это больше условности для интерфейса в "стиле Си" — с вызовом функции сигналом wr и возвращением результата по сигналу rdy. А мышление ПЛИСовода должно быть другим.


Но это мое ИМХО, не обращайте внимания.

Это уже где то видел, автор не сбайтил?
Ну если Вы господин Пак, то безусловно. Года 4 назад я Вам это показывал, а Вы очень долго не могли понять как это работает :)))
Надо протактировать в регистр это (cnt != 0), и только потом использовать многократно по всему модулю.
Надо протактировать в регистр это (cnt != 0), и только потом использовать многократно по всему модулю.

Языки описания аппаратуры(верилог в частности) описывают не программу как последовательность исполняемых команд, а сеть параллельных процессов. Всё выполняется по всей «программе» (на самом деле сети), как только возникли подходящие для этого условия. Что кстати требует от разработчика мышления сильно не такого, как у программистов. Если Вы имеете в виду, что «протактировал» я где-то не в самом начале исходника, это без разницы. Мог бы хоть в самом конце. Я тут как бы скорее не программирую, а расставляю на плате микросхемки и соединяю их проводочками.
Вот гляньте книжку www.twirpx.com/file/51125. Очень полезно будет почитать для начала.
Вы даже не поняли мой коментарий. FPGA это моя специализация последние 17 лет.
Признаюсь честно — да, немного не понял.
Надо протактировать в регистр это (cnt != 0), и только потом использовать многократно по всему модулю.

Что всё-таки Вы имели в виду?
Вот это

always @(posedge clk)
if(wr) cnt<=nbits+1;
else
if(cnt != 0)
cnt<=cnt-1;


заменить этим.

reg cnt_down;
always @(posedge clk) cnt_down <= (cnt == 'd1);

always @(posedge clk)
if(wr) cnt<=nbits+1;
else
if(!cnt_down )
cnt<=cnt-1;


Так код чище, легче будет placement & routing.
Аналогично

always @(posedge clk)
if(wr) res<=0;
else
if(!cnt_down) begin
res[nbits-1:1]<=res[nbits-2:0];
res[0]<=bit;
end


И это

always @(posedge clk) rdy<=cnt_down;
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации