Как получить квадратный корень для 32-битного ввода только за один такт?

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

Источник

6 ответов

[Edit1] исправленный код

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

Лучшее, что я могу придумать (кроме аппроксимации или большого LUT), это бинарный поиск без умножения, здесь код C++:

//---------------------------------------------------------------------------
WORD u32_sqrt(DWORD xx) // 16 T
    {
    DWORD x,m,a0,a1,i;
    const DWORD lut[16]=
        {
        //     m*m
        0x40000000,
        0x10000000,
        0x04000000,
        0x01000000,
        0x00400000,
        0x00100000,
        0x00040000,
        0x00010000,
        0x00004000,
        0x00001000,
        0x00000400,
        0x00000100,
        0x00000040,
        0x00000010,
        0x00000004,
        0x00000001,
        };
    for (x=0,a0=0,m=0x8000,i=0;m;m>>=1,i++)
        {
        a1=a0+lut[i]+(x<<(16-i));
        if (a1<=xx) { a0=a1; x|=m; }
        }
    return x;
    }
//---------------------------------------------------------------------------

Стандартный бинарный поиск sqrt(xx) устанавливает биты x от MSB до LSB, так что результат x*x <= xx, К счастью, мы можем избежать умножения, просто переписав вещь как увеличивающийся мультипликатор... в каждой итерации старшая x*x Результат можно использовать так:

x1 = x0+m
x1*x1 = (x0+m)*(x0+m) = (x0*x0) + (2*m*x0) + (m*m)

куда x0 это значение x из последней итерации и x1 фактическая стоимость m вес фактического обработанного бита. (2*m) а также (m*m) являются постоянными и могут использоваться как LUT и битовое смещение, поэтому нет необходимости в умножении. Нужно только дополнение. К сожалению, итерация связана с последовательным вычислением, запрещающим паралелизацию, поэтому результат 16T в лучшем случае.

В коде a0 представляет последний x*x а также a1 представляет фактическое повторение x*x

Как вы можете видеть sqrt сделано в 16 x (BitShiftLeft,BitShiftRight,OR,Plus,Compare) где сдвиг битов и LUT могут быть зашиты.

Если вы получили супер быстрые ворота для этого по сравнению с остальными, вы можете умножить входные часы на 16 и использовать это как внутреннюю синхронизацию для модуля SQRT. Нечто похожее на старые времена, когда в старых процессорах Intel /MCU были часы MC как деление тактовой частоты процессора... Таким образом, вы можете получить 1T время (или его кратность зависит от коэффициента умножения).

Источник

В 2018 году Т. Багала, А. Фибич, М. Хагара, П. Кубинец, О. Ондрачек, В. Штофаник и Р. Стоянович разработали алгоритм вычисления квадратного корня для одного тактового сигнала, основанный на биномиальных рядах и его реализацию на ПЛИС.

Гетеродин работает на частоте 50 МГц [… для 16-битной входной мантиссы]. Значения [аппаратного] эксперимента были такими же, как и значения при моделировании […]. Полученные средние значения задержки составили 892 пс и 906 пс соответственно.

(Нет объяснений относительно несоответствия между 50 МГц и 0,9 нс или указанного разрешения ps и использования осциллографа 10 Гбит / с. Если это было около 18 циклов (из-за конвейерной обработки, а не зацикливания?)/~900* нс *, интерпретация Single Clock Квадратный корень... остается открытым - может быть один результат за цикл.)
Далее в документе не раскрываются подробности об оценке биномиального ряда.
Хотя уравнения также представлены в общей форме, я предполагаю, что количество оборудования, необходимого для большего числа битов, быстро становится непомерно высоким.

Источник

Существует преобразование в логарифм, деление пополам и обратное преобразование.
Для получения идеи о том, как реализовать "комбинаторный" журнал и антилог, см . Статью EDN Майкла Данна, в которой показаны кодировщик приоритетов, смещение бочек и таблица поиска, с тремя вариантами журналов в System Verilog для загрузки.
(Приоритетный кодер, бочкообразный сдвиг и справочная таблица выглядят многообещающе для "одношагового вавилонянина / цапли / ньютона /-Рафсона.

Хотя не показывая "Verilog",
Толе Сутикно: "Оптимизированный алгоритм квадратного корня для реализации в оборудовании ПЛИС" демонстрирует комбинаторную реализацию модифицированного (двоичного) цифрно-цифрового алгоритма.

Источник

Моя версия Spektre с переменными битами учитывается, поэтому она может быть быстрее на коротких квадратах.

          const unsigned int isqrt_lut[16] =
{
    //     m*m
    0x40000000,
    0x10000000,
    0x04000000,
    0x01000000,
    0x00400000,
    0x00100000,
    0x00040000,
    0x00010000,
    0x00004000,
    0x00001000,
    0x00000400,
    0x00000100,
    0x00000040,
    0x00000010,
    0x00000004,
    0x00000001,
};
/// Our largest golf ball image is about 74 pixels, so lets round up to power of 2 and we get 128.
/// 128 squared is 16384 so out largest sqrt has to handle 16383 or 14 bits. Only positive values.
/// ** maxBits in is 2 to 32 always an even number **
/// Input value mist always be less than (2^maxBits) - 1
unsigned int isqrt(unsigned int xx, int maxBitsIn) {
    DWORD x, m, a0, a1, i;

    for (x = 0, a0 = 0, m = 0x01 << (maxBitsIn / 2 - 1), i = 16 - maxBitsIn / 2; m; m >>= 1, i++)
    {
        a1 = a0 + isqrt_lut[i] + (x << (16 - i));
        if (a1 <= xx) {
            a0 = a1;
            x |= m;
        }
    }
    return x;
}
Источник

Я получил код здесь

    module sqrt(
input[31:0]a,
output[15:0]out
    );
reg [31:0]temp;
reg[14:0]x;

always@(a)
begin
if(a<257)x=4;
if(a>256 && a<65537)x=80;
if(a>65536 && a<16777217)x=1000;
if(a>16777216 && a<=4294967295)x=20000;
temp=(x+(a/x))/2;
temp=(temp+(a/temp))/2;
temp=(temp+(a/temp))/2;
temp=(temp+(a/temp))/2;
temp=(temp+(a/temp))/2;
temp=(temp+(a/temp))/2;
temp=(temp+(a/temp))/2;
end

assign out=temp;
endmodule
Источник

Обычный способ сделать это аппаратно - это использовать CORDIC. Общая реализация позволяет вычислять различные трансцендентные функции (cos/sin/tan) и... квадратные корни в зависимости от того, как вы инициализируете и работаете с CORDIC.

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

В частности, если вы работали с CORDIC в векторном режиме, инициализируйте его с помощью [x, 0] и поверните на 45 градусов, и конечный результат [x', y'] будет мультипликативной постоянной. то есть sqrt(x) = x' * sqrt(2) * K

Источник
Другие вопросы по тегам