Квадратный корень методом CORDIC на FPGA

Содержание

Данной статье объясняется конвейерный поход к методу CORDIC на FPGA. Простая его реализация описана в предыдущей статье «Алгоритмы квадратного корня на FPGA«.

Преимущества конвейерного подхода метода CORDIC

  1. Высокая производительность:
    Конвейеризация позволяет одновременно обрабатывать несколько чисел, разделяя процесс вычисления на последовательные этапы. Каждый этап выполняет свою часть алгоритма, что обеспечивает высокую пропускную способность.
  2. Низкая латентность на выходе:
    Хотя задержка для одного числа определяется числом этапов конвейера, при непрерывной подаче данных результирующий поток имеет минимальные задержки между последовательными выходами.
  3. Оптимизация ресурсов:
    Конвейерный подход позволяет повторно использовать аппаратные блоки (например, сдвиги, сумматоры), равномерно распределяя нагрузку между этапами.
  4. Масштабируемость:
    Такой подход легко адаптируется к разным разрядностям данных и требованиям производительности, увеличивая или уменьшая глубину конвейера.
  5. Энергоэффективность:
    Конвейеризация снижает активное потребление энергии, так как часть этапов может быть выключена в паузах между вычислениями.

Когда применять конвейерный подход?

  1. Высокая частота входных данных:
    Если данные для вычислений поступают с высокой частотой, конвейеризация позволяет обрабатывать их в реальном времени, без задержек.
  2. Задачи с многопоточной обработкой:
    В системах, где одновременно требуется вычислять квадратный корень для множества входных чисел (например, в DSP или алгоритмах машинного обучения), конвейерный метод обеспечивает максимальную эффективность.
  3. Ограниченные ресурсы FPGA:
    Если FPGA имеет ограниченное количество аппаратных ресурсов, конвейеризация помогает оптимально распределить их использование по этапам.
  4. Реализация в высокопроизводительных системах:
    Пример — обработка сигналов, видеопотоков или сетевых данных, где важно минимизировать задержки между входом и выходом системы.
  5. Требования к пропускной способности:
    Если система должна поддерживать определенную скорость вычислений, конвейерный метод помогает достичь нужной производительности без увеличения тактовой частоты.

Пример реализации конвейерного подхода метода CORDIC на FPGA

В данном примере использовался язык Verilog для описании конструкции. Цель этого примера показать принцип применения конвейерного подхода.
module cordic_sqrt (
    input wire clk,                   // Тактовый сигнал
    input wire reset,                 // Сброс
    input wire [31:0] x_in,           // Входное значение
    input wire y_x_in,                // Сигнал принятия данных
    input wire [15:0] bit_start,      // Бит старта для текущего тестируемого бита
    output wire o_ready,               // Готовность результата для шины 3-х битной шины
    output wire [15:0] sqrt_out        // Результат для шины после 1-ой интерации
);

    // Локальные параметры
    reg [31:0] x [15:0];            // Регистр сравнения начального значения
    reg [15:0] bit [15:0];          // Текущеt тестируемый бит
    reg [15:0] sqrt_out_b [15:1];   // Промежуточные вычисления
    reg [15:0] ready;
    reg delay_ready = 0;

    initial begin
        sqrt_out_b[1] <= 0;
        sqrt_out_b[2] <= 0;
        sqrt_out_b[3] <= 0;
        sqrt_out_b[4] <= 0;
        sqrt_out_b[5] <= 0;
        sqrt_out_b[6] <= 0;
        sqrt_out_b[7] <= 0;
        sqrt_out_b[8] <= 0;
        sqrt_out_b[9] <= 0;
        sqrt_out_b[10] <= 0;
        sqrt_out_b[11] <= 0;
        sqrt_out_b[12] <= 0;
        sqrt_out_b[13] <= 0;
        sqrt_out_b[14] <= 0;
        sqrt_out_b[15] <= 0;
        ready <= 0;
        x[0] <= 0;
        x[1] <= 0;
        x[2] <= 0;
        x[3] <= 0;
        x[4] <= 0;
        x[5] <= 0;
        x[6] <= 0;
        x[7] <= 0;
        x[8] <= 0;
        x[9] <= 0;
        x[10] <= 0;
        x[11] <= 0;
        x[12] <= 0;
        x[13] <= 0;
        x[14] <= 0;
        x[15] <= 0;
        bit[0] <= 0;
        bit[1] <= 0;
        bit[2] <= 0;
        bit[3] <= 0;
        bit[4] <= 0;
        bit[5] <= 0;
        bit[6] <= 0;
        bit[7] <= 0;
        bit[8] <= 0;
        bit[9] <= 0;
        bit[10] <= 0;
        bit[11] <= 0;
        bit[12] <= 0;
        bit[13] <= 0;
        bit[14] <= 0;
        bit[15] <= 0;
    end

    assign sqrt_out = sqrt_out_b[15];
    assign o_ready = ready[15];

    always @(posedge clk or posedge reset) begin
        if (reset) begin
            // Сброс значений готовности к последующей передачи
            ready <= 0;
        end else begin
            // Вычисление промежуточного значения
            if ((0 + bit_start) * (0 + bit_start) <= x_in) begin
                sqrt_out_b[1] <= 0 + bit_start;
            end else begin
                sqrt_out_b[1] <= 0;
            end
            if ((sqrt_out_b[1] + bit[1]) * (sqrt_out_b[1] + bit[1]) <= x[1]) begin
                sqrt_out_b[2] <= sqrt_out_b[1] + bit[1];
            end else begin
                sqrt_out_b[2] <= sqrt_out_b[1];
            end
            if ((sqrt_out_b[2] + bit[2]) * (sqrt_out_b[2] + bit[2]) <= x[2]) begin
                sqrt_out_b[3] <= sqrt_out_b[2] + bit[2];
            end else begin
                sqrt_out_b[3] <= sqrt_out_b[2];
            end
            if ((sqrt_out_b[3] + bit[3]) * (sqrt_out_b[3] + bit[3]) <= x[3]) begin
                sqrt_out_b[4] <= sqrt_out_b[3] + bit[3];
            end else begin
                sqrt_out_b[4] <= sqrt_out_b[3];
            end
            if ((sqrt_out_b[4] + bit[4]) * (sqrt_out_b[4] + bit[4]) <= x[4]) begin
                sqrt_out_b[5] <= sqrt_out_b[4] + bit[4];
            end else begin
                sqrt_out_b[5] <= sqrt_out_b[4];
            end
            if ((sqrt_out_b[5] + bit[5]) * (sqrt_out_b[5] + bit[5]) <= x[5]) begin
                sqrt_out_b[6] <= sqrt_out_b[5] + bit[5];
            end else begin
                sqrt_out_b[6] <= sqrt_out_b[5];
            end
            if ((sqrt_out_b[6] + bit[6]) * (sqrt_out_b[6] + bit[6]) <= x[6]) begin
                sqrt_out_b[7] <= sqrt_out_b[6] + bit[6];
            end else begin
                sqrt_out_b[7] <= sqrt_out_b[6];
            end
            if ((sqrt_out_b[7] + bit[7]) * (sqrt_out_b[7] + bit[7]) <= x[7]) begin
                sqrt_out_b[8] <= sqrt_out_b[7] + bit[7];
            end else begin
                sqrt_out_b[8] <= sqrt_out_b[7];
            end
            if ((sqrt_out_b[8] + bit[8]) * (sqrt_out_b[8] + bit[8]) <= x[8]) begin
                sqrt_out_b[9] <= sqrt_out_b[8] + bit[8];
            end else begin
                sqrt_out_b[9] <= sqrt_out_b[8];
            end
            if ((sqrt_out_b[9] + bit[9]) * (sqrt_out_b[9] + bit[9]) <= x[9]) begin
                sqrt_out_b[10] <= sqrt_out_b[9] + bit[9];
            end else begin
                sqrt_out_b[10] <= sqrt_out_b[9];
            end
            if ((sqrt_out_b[10] + bit[10]) * (sqrt_out_b[10] + bit[10]) <= x[10]) begin
                sqrt_out_b[11] <= sqrt_out_b[10] + bit[10];
            end else begin
                sqrt_out_b[11] <= sqrt_out_b[10];
            end
            if ((sqrt_out_b[11] + bit[11]) * (sqrt_out_b[11] + bit[11]) <= x[11]) begin
                sqrt_out_b[12] <= sqrt_out_b[11] + bit[11];
            end else begin
                sqrt_out_b[12] <= sqrt_out_b[11];
            end
            if ((sqrt_out_b[12] + bit[12]) * (sqrt_out_b[12] + bit[12]) <= x[12]) begin
                sqrt_out_b[13] <= sqrt_out_b[12] + bit[12];
            end else begin
                sqrt_out_b[13] <= sqrt_out_b[12];
            end
            if ((sqrt_out_b[13] + bit[13]) * (sqrt_out_b[13] + bit[13]) <= x[13]) begin
                sqrt_out_b[14] <= sqrt_out_b[13] + bit[13];
            end else begin
                sqrt_out_b[14] <= sqrt_out_b[13];
            end
            if ((sqrt_out_b[14] + bit[14]) * (sqrt_out_b[14] + bit[14]) <= x[14]) begin
                sqrt_out_b[15] <= sqrt_out_b[14] + bit[14];
            end else begin
                sqrt_out_b[15] <= sqrt_out_b[14];
            end
            // Переход к следующему биту
            bit[0] <= bit_start;
            bit[1] <= bit[0] >> 1;
            bit[2] <= bit[1] >> 1;
            bit[3] <= bit[2] >> 1;
            bit[4] <= bit[3] >> 1;
            bit[5] <= bit[4] >> 1;
            bit[6] <= bit[5] >> 1;
            bit[7] <= bit[6] >> 1;
            bit[8] <= bit[7] >> 1;
            bit[9] <= bit[8] >> 1;
            bit[10] <= bit[9] >> 1;
            bit[11] <= bit[10] >> 1;
            bit[12] <= bit[11] >> 1;
            bit[13] <= bit[12] >> 1;
            bit[14] <= bit[13] >> 1;
            bit[15] <= bit[14] >> 1;
            
            delay_ready <= y_x_in;
            ready[0] <= delay_ready;
            ready[1] <= ready[0];
            ready[2] <= ready[1];
            ready[3] <= ready[2];
            ready[4] <= ready[3];
            ready[5] <= ready[4];
            ready[6] <= ready[5];
            ready[7] <= ready[6];
            ready[8] <= ready[7];
            ready[9] <= ready[8];
            ready[10] <= ready[9];
            ready[11] <= ready[10];
            ready[12] <= ready[11];
            ready[13] <= ready[12];
            ready[14] <= ready[12];
            ready[15] <= ready[14];

            x[0] <= x_in;
            x[1] <= x[0];
            x[2] <= x[1];
            x[3] <= x[2];
            x[4] <= x[3];
            x[5] <= x[4];
            x[6] <= x[5];
            x[7] <= x[6];
            x[8] <= x[7];
            x[9] <= x[8];
            x[10] <= x[9];
            x[11] <= x[10];
            x[12] <= x[11];
            x[13] <= x[12];
            x[14] <= x[13];
            x[15] <= x[14];
        end
    end
endmodule

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

  • Сигналы:
    • clk — тактовый сигнал
    • reset — асинхронный сброс
    • x_in — входной информационный сигнал
    • y_x_in — входной сигнал валидации входных данных
    • bit_start — входной текущий тестируемый бит
    • o_ready — выходной бит готовности
    • sqrt_out — выходной информационный сигнал
  • Регистры:
    • x — регистр начального значения
    • bit — текущий тестируемый бит
    • sqrt_out_b — результирующее значение i- интерации
    • ready — регистр готовности
    • delay_ready — задержка регистра готовности
  • Объяснение кода:
    • 1-ый процедурный блок «initial» объявляет начальные значения
    • В блоке always реализован конвейерная передача данных регистров с реализацией методом CORDIC(см. метод CORDIC).
    • Через непрерывное присваивание assign передаются заключительные значения на выход модуля
Тестбенч на 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;
    reg [15:0] bit_start;
    wire [15:0] sqrt_out_t;
    wire ready_t;

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

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

    initial begin
        $monitor("At time %t, result = %0d, ready = %0d", $time, sqrt_out_t, ready_t);
        // Инициализация
        clk_t = 0;
        reset_t = 1;
        x_in_t = 0;
        y_x_in_t = 0;

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

        // Тест 1: sqrt(144) = 12
        #10 x_in_t = 32'd144;
        y_x_in_t = 1;
        bit_start = 8;
        #10;
        y_x_in_t = 0;

        // Тест 2: sqrt(25) = 5
        #10 x_in_t = 32'd25;
        y_x_in_t = 1;
        bit_start = 16;
        #10;
        y_x_in_t = 0;

        // Завершение тестов
        #1000;
        $finish;
    end
endmodule
Полученный результат в Icarus Verilog:
At time                    0, result = 0, ready = 0
At time                  165, result = 8, ready = 0
At time                  175, result = 12, ready = 1
At time                  185, result = 7, ready = 0
At time                  195, result = 5, ready = 1
At time                  205, result = 5, ready = 0
cordic_sqrt_tb_con.v:52: $finish called at 1050 (1ps)

Заключение

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

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

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

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

3. Влияет ли конвейеризация на точность вычислений?
Нет, точность результатов остается такой же, как и у неконвейерного метода CORDIC. Точность зависит от разрядности входных данных и количества итераций, а не от архитектуры вычислений.

4. Как настроить глубину конвейера для метода CORDIC?
Глубина конвейера определяется числом итераций алгоритма. Для увеличения пропускной способности можно добавить дополнительные этапы, но это потребует больше аппаратных ресурсов. Настройка производится в среде разработки, например, Quartus Prime.

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