Алгоритмы квадратного корня на FPGA

Содержание

На FPGA для вычисления квадратного корня числа с шириной шины до 32 бит применяются различные алгоритмы. Основные подходы включают:

1. Итеративный метод (например, метод Ньютона-Рафсона)

Описание:

  • Этот метод использует итерации для приближения значения корня. Начальное значение подбирается, а затем последовательно уточняется с помощью формулы:
Формула метода Ньютона-Рафсона
Рисунок 1. Формула метода Ньютона-Рафсона

где N — исходное число, корень которого нужно вычислить.

Особенности:

  • Точность: Можно регулировать точность, изменяя число итераций.
  • Ресурсы FPGA: Потребляет меньше логических элементов, но требует множителей и делителей.

Преимущества:

  • Высокая точность.
  • Гибкость в настройке точности и производительности.
  • Легкость реализации на FPGA при наличии аппаратных блоков умножения/деления.

Недостатки:

  • Большая латентность, так как процесс итеративный.

2. Методы на основе табличного поиска (LUT-based approaches)

Описание:

  • Таблицы поиска (LUT) хранят предвычисленные значения квадратных корней для небольших диапазонов чисел. Для входного числа используется поиск в таблице или интерполяция.

Особенности:

  • Ресурсы FPGA: Требует большого объема памяти для хранения таблицы.
  • Точность: Зависит от размера таблицы и метода интерполяции.

Преимущества:

  • Очень низкая латентность, так как основная операция — доступ к памяти.
  • Подходит для чисел с фиксированным диапазоном.

Недостатки:

  • Увеличение объема памяти с ростом диапазона входных чисел.
  • Ограничение точности из-за интерполяции.

3. Аппаратный параллельный алгоритм (CORDIC)

Описание:

  • CORDIC (COordinate Rotation DIgital Computer) — это аппаратный алгоритм, который использует сдвиги, сложения и вычитания для вычисления функций, включая квадратный корень.
  • Для квадратного корня CORDIC преобразует задачу в процесс итеративного приближения.

Особенности:

  • Точность: Зависит от числа итераций.
  • Ресурсы FPGA: Эффективно использует LUTs и не требует делителей или умножителей.

Преимущества:

  • Аппаратный параллелизм для быстрой обработки.
  • Эффективность в использовании ресурсов FPGA.

Недостатки:

  • Сложность реализации по сравнению с методом Ньютона.
  • Ограничение по точности из-за аппаратных операций.

4. Бинарный метод (Bit-serial approach)

Описание:

  • Это метод деления на основе сравнения. Подходит для фиксированной точки. На каждой итерации проверяется, может ли следующий бит быть добавлен в корень, чтобы сохранить значение результата меньше или равно исходному числу.

Особенности:

  • Точность: Подходит для фиксированной точки, но ограничен битовой шириной.
  • Ресурсы FPGA: Эффективно использует ресурсы.

Преимущества:

  • Низкая сложность реализации.
  • Эффективное использование ресурсов FPGA.

Недостатки:

  • Умеренная латентность из-за итеративного характера.
  • Менее гибкий в расширении точности.

Сравнение методов

Таблица 1. Сравнение методов получения квадратного корня

МетодЛатентностьТочностьПотребление ресурсовПростота реализации
Ньютона-РафсонаВысокаяВысокаяСреднееСредняя
Табличный поискНизкаяСредняя/высокаяВысокоеВысокая
CORDICНизкая/средняяСредняяНизкоеСредняя
Бинарный методСредняяСредняяНизкоеВысокая

Рекомендации для выбора

  • Для максимальной точности: Используйте метод Ньютона-Рафсона.
  • Для низкой латентности: Табличный поиск или CORDIC.
  • Для малых ресурсов: Бинарный метод или CORDIC.
  • Для больших диапазонов чисел: Метод Ньютона-Рафсона или комбинированный метод (табличный поиск с уточнением).

FPGA позволяет комбинировать методы для оптимизации производительности и использования ресурсов. Например, можно использовать LUT для грубой оценки и уточнение методом Ньютона.

Алгоритм вычисления квадратного корня методом CORDIC

Метод CORDIC (COordinate Rotation DIgital Computer) применяется для вычисления квадратного корня, тригонометрических функций, логарифмов и других операций. Этот алгоритм подходит для реализации на FPGA благодаря своей простоте: он использует только сложение, вычитание и сдвиг.

Основная идея метода для вычисления квадратного корня

  1. Предположение: Мы хотим найти y = sqrt{N}, где N — входное число.
  2. Итеративный процесс: Алгоритм начинает с некоторого начального приближения и уточняет его на каждом шаге.
  3. Проверка условия: Для каждой итерации добавляется текущий бит, если это не превышает остаток N.
  4. Конвергенция: После нескольких итераций результат сходится к точному значению квадратного корня.

Шаги алгоритма

1. Инициализация

  • N — число, для которого требуется вычислить квадратный корень.
  • result = 0 — начальное значение результата.
  • bit = 2^{(n-1)} — старший бит, с которого начинается процесс (например, 2152^{15} для 16-битного числа).

2. Итеративный процесс

На каждом шаге выполняются следующие действия:

  • Проверяем: (result + bit)^2 <= N.
    • Если условие истинно: добавляем bitbit к resultresult.
    • Иначе: переходим к следующему шагу без изменения resultresult.
  • Сдвигаем bitbit вправо: bit = bit >> 1.

3. Завершение

После обработки всех битов результат в result содержит квадратный корень с нужной точностью.

Пример для 16-битного числа

Рассмотрим N=25.

Таблица 2. Интераций примера квадратного корня методом CORDIC

Итерацияbit(result + bit)^2Условие (≤25)result
11616^2 = 256Нет0
288^2 = 64Нет0
344^2 = 16Да4
42(4+2)^2 = 36Нет4
51(4+1)^2 = 25Да5

Результат: 5.

Реализация алгоритма CORDIC в FPGA на языке Verilog

Вот простой пример реализации вычисления квадратного корня числа методом CORDIC на языке Verilog. Этот пример подходит для работы с фиксированной точкой (fixed-point) и 32-битной шириной данных.
module cordic_sqrt (
    input wire clk,                // Тактовый сигнал
    input wire reset,              // Сброс
    input wire [31:0] x_in,        // Входное значение
    input wire y_x_in,             // Валидации входных данных
    output reg [15:0] sqrt_out,    // Результат
    output reg ready               // готовность результата
);

    // Локальные параметры
    reg [31:0] x = 0;               // Остаток (остаток от вычитания текущего квадрата)
    reg [15:0] bit = 0;             // Текущий тестируемый бит
    reg [4:0]  counter = 0;         // Счетчик подсчета интераций

    always @(posedge clk or posedge reset) begin
        if (reset) begin
            // Сброс значений
            x <= 0;
            bit <= 16'h8000; // Старший бит (для начала с половины диапазона)
            sqrt_out <= 0;
            ready <= 0;
            counter <= 0;
        end else begin
            // Итерационный процесс с задержкой 16 тактов
            // Вычисление промежуточного значения
            if (y_x_in == 0) begin
                if ((sqrt_out + bit) * (sqrt_out + bit) <= x) begin
                    sqrt_out <= sqrt_out + bit;
                end
                // Переход к следующему биту
                bit <= bit >> 1;
                if (counter == 15) ready <= 1; else ready <= 0;
            end else begin 
                // Инициализация перед вычислением
                x <= x_in;
                bit <= 16'h8000; // Начальный шаг бита (самый старший бит)
                sqrt_out <= 0;
                ready <= 0;
                counter <= 0;
            end
            if (counter < 16) counter <= counter + 1;
        end
    end
endmodule

Описание кода:

  1. Входные и выходные сигналы:
    • clk — входной тактовый сигнал
    • reset — асинхронный сброс
    • x_in — 32-битное значение, квадратный корень которого нужно вычислить.
    • y_x_in — сигнал валидации входных данных
    • sqrt_out — 16-битный результат, который возвращает квадратный корень.
    • ready — сигнал валидации выходных данных
  2. Параметры и регистры:
    • x — остаток, используется для итеративного сравнения
    • bit — текущий шаг тестируемого бита.
  3. Алгоритм работы:
    • Начинаем с самой старшей бита (16’h8000).
    • Итеративно проверяем, можно ли увеличить результат на текущий шаг без превышения остатка x.
    • Если это возможно, добавляем текущий бит к результату.
    • Сдвигаем бит вправо для уточнения следующего приближения.
  4. Процессорная логика:
    • Каждая итерация проверяет (result+bit)^2≤x.
    • После 16 итераций результат точен для 16-битного числа.

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

Тестбенч на языке Verilog:
`timescale 1ps/1ps
module cordic_sqrt_tb;

    reg clk_t;
    reg reset_t;
    reg [31:0] x_in_t;
    reg y_x_in_t;
    wire [15:0] sqrt_out_t;
    wire ready_t;

    cordic_sqrt uut (clk_t, reset_t, x_in_t, y_x_in_t, sqrt_out_t, ready_t);

    // Генерация тактового сигнала
    always #5 clk_t = ~clk_t;

    initial begin
        // Инициализация
        clk_t = 0;
        reset_t = 1;
        x_in_t = 0;
        y_x_in_t = 0;

        // Сброс
        #10 reset_t = 0;

        // Тест 1: sqrt(25) = 5
        #10 x_in_t = 32'd25;
        y_x_in_t = 1;
        #10;
        y_x_in_t = 0;
        @(posedge ready_t) $display("At time %t, result = %0d, ready = %0d", $time, sqrt_out_t, ready_t );

        // Тест 2: sqrt(144) = 12
        #10 x_in_t = 32'd144;
        y_x_in_t = 1;
        #10;
        y_x_in_t = 0;
        @(posedge ready_t) $display( "At time %t, result = %0d, ready = %0d", $time, sqrt_out_t, ready_t );

        // Тест 3: sqrt(1024) = 32
        #10 x_in_t = 32'd1024;
        y_x_in_t = 1;
        #10;
        y_x_in_t = 0;
        @(posedge ready_t) $display("At time %t, result = %0d, ready = %0d", $time, sqrt_out_t, ready_t);

        // Завершение тестов
        $finish;
    end
endmodule
Вывод с помощью Icarus Verilog:
At time                  165, result = 4, ready = 1
At time                  335, result = 12, ready = 1
At time                  505, result = 32, ready = 1
cordic_sqrt_tb.v:49: $finish called at 505 (1ps)

Заключение

Метод CORDIC для вычисления квадратного корня демонстрирует сочетание простоты и эффективности, делая его отличным выбором для аппаратной реализации на FPGA. Используя только базовые операции (сложение, вычитание и сдвиг), этот алгоритм позволяет достичь высокой производительности при минимальных затратах ресурсов. Важно учитывать, что точность вычислений зависит от ширины данных и количества итераций, но при правильной настройке метод обеспечивает результат, сравнимый с другими более сложными подходами. Благодаря своей универсальности, CORDIC находит применение в задачах обработки сигналов, математического моделирования и машинного обучения.

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

FAQ: Часто задаваемые вопросы

1. Почему метод CORDIC эффективен для FPGA?
CORDIC требует минимального количества операций: он использует только сложение, вычитание и сдвиг, которые хорошо оптимизируются в аппаратной реализации. Это снижает потребление ресурсов FPGA и обеспечивает высокую производительность.

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

3. Какую максимальную точность можно достичь при использовании CORDIC?
Точность ограничивается разрядностью входных данных и количеством итераций. Например, для 16-битных данных точность вычисления составит до 16 бит, что соответствует точному представлению результата в этом диапазоне.

4. Что делать, если число выходит за пределы диапазона?
Число NN следует нормализовать перед началом вычислений. Это можно сделать, сдвигая его влево или вправо, чтобы оно попадало в допустимый диапазон. После вычисления корня необходимо масштабировать результат обратно.

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