32bit_me (32bit_me) wrote,
32bit_me
32bit_me

Category:

Делитель

Взять все, да и поделить
(c)


Деление является довольно сложной операцией для FPGA. Если мы просто напишем в коде что-то типа такого:

module divider(
        input wire rst_n,
        input wire clk,
        input wire[31: 0] in1,
        input wire[31: 0] in2,
        output reg[32: 0] res
);
 reg[31: 0] in1_reg;
 reg[31: 0] in2_reg;
 
 always@(posedge clk, negedge rst_n)
 begin
     if(!rst_n)
     begin
          res <= 0;
          in1_reg <= 0;
          in2_reg <= 0;
     end
     else
     begin
          in1_reg <= in1;
          in2_reg <= in2;
          res <= in1_reg / in2_reg;
     end;
 end
endmodule



То мы получим такой результат синтеза:
Total logic elements 1,180
Total registers 96
Total pins 99
Total virtual pins 0
Total memory bits 0


1180 логических элементов - это очень много. Это объём небольшого процессора (и не самого маленького из возможных).
(Небольшое примечание: здесь мы не учитываем количество входных и выходных триггеров, нас интересует только объём комбинаторики между ними).
А что с частотой?
С частотой ещё хуже: Fmax = 9,39 MHz. Такая реализация делителя не пригодна для практических целей однозначно.
Что насчёт делителя меньшего размера?
Уменьшим разрядность делителя до 16/8->8 бит.
Результат: 234 LE, Fmax = 30,81. Уже лучше, но всё ещё недостаточно хорошо.
Уменьшим разрядность делителя до 8/4->4 бит.
Результат: 75 LE, Fmax = 88,26 MHz. Это неплохо по расходу LE, но плохо по частоте.
Делитель 4/2->2:
Результат: 21 LE, Fmax = 296,56 MHz (250 MHz restricted)

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

Модуль делителя

Это первый вариант, самый простой. Обеспечивает деление 32-разрядных целых чисел, как со знаком, так и без знака. Одновременно с делением происходит вычисление остатка от деления. Деление происходит за фиксированное время (33 такта). В дальнейшем я планирую существенно улучить этот показатель.



Проект занимает 375 LE и имеет частоту 143,23 МГц. Частоту можно (и нужно) увеличить, но сначала нужно оптимизировать структуру делителя, для того, чтобы деление занимало меньше тактов.

Тест делителя (кликабельно):



Тест содержит 10.000 тестовых случаев (test case). Написание такого теста тоже имеет свои нюансы. Например, если просто генерировать случайные числа в диапазоне от 0 до (2^32 - 1), то получится очень мало чисел с маленьким числом значащих разрядов. То есть, так как весь диапазон содержит 2^32 ~ 4е9 чисел, то вероятность, что в числителе, например, окажется ноль, будет 0.25e-9, то есть в тесте разумных размеров такой случай гарантированно не встретится. На самом деле, в моём тесте сначала случайным образом генерируется количество значащих разрядов (от 0 до 32), а затем уже само число. То есть вероятность попадания нуля на место числителя (или знаменателя), равна 1/33, а вероятность случая 0/0 - примерно 1 случай на 1000, т.е. таких случаев в тесте должно быть около 10.

Дальнейшая оптимизация возможна по двум путям:
1. Использование алгоритма деления по основанию, отличному от 2, например, radix 4.
2. Использование нормализации делимого, тогда вычисление будет занимать переменное число тактов. Например, если делимое равно нулю, то результат будет сформирован на следующем такте, и деление займёт 1 такт, если половина старших разрядов равна нулю, то будет в два раза меньше тактов, чем для полного алгоритма.
Tags: fpga, verilog
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 13 comments