Как ускорить обработку данных. Часть 2: распараллеливание цифровых схем по зависимым операциям / forpes.ru

Главная
Как ускорить обработку данных. Часть 2: распараллеливание цифровых схем по зависимым операциям

Как ускорить обработку данных. Часть 2: распараллеливание цифровых схем по зависимым операциям +5

14.10.2026 11:44

ratragor 0 1700 Источник

Привет, Хабр! Меня зовут Кирилл Алексеев, я ведущий инженер в отделе интеграции систем на кристалле радиочастотного центра YADRO. В прошлых статьях я рассказывал о процедурных и конвейерных вычислениях и распараллеливании цифровых схем по независимым операциям. Сегодня продолжим тему и разберем, как получить конвейерную реализацию КИХ-фильтра через распараллеливание схемы MAC-операции по зависимым операциям.

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

Статья будет полезна молодым специалистам, которые только начинают работу с ПЛИС, опытным инженерам и архитекторам вычислительных устройств: приглашаю обменяться опытом в комментариях.

Цикл статей по архитектуре цифровых устройств:

1. «Архитектура цифровых устройств: разбираемся с процедурными и конвейерными вычислениями».

2. «Как ускорить обработку данных. Часть 1: распараллеливание цифровых схем по независимым операциям».

3. «Как ускорить обработку данных. Часть 2: распараллеливание цифровых схем по зависимым операциям» (сейчас вы тут).

Постановка задачи

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

Выделяют несколько основных видов распараллеливания цифровых схем:

Распараллеливание по независимым операциям (оно же «распараллеливание по данным», «параллелизм данных», Data Parallelism, Task-level Parallelism):
— Схема «вложенный конвейер» (б).
— Мультиконвейерная схема (в).
— Макроконвейерная схема — частный случай мультиконвейерной схемы, когда скважность входного потока данных .
Распараллеливание по зависимым операциям (оно же «распараллеливание по итерациям», «конвейеризация циклов», Cycle Pipelining):
— Конвейерная схема (г).
— Конвейерно-процедурная схема (г).

Что видим на схеме:

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

Под буквой б) приведена схема распараллеливания «Вложенный конвейер», предполагающая параллельную обработку независимых данных, которые последовательно загружаются в схему и обрабатываются одновременно. Построить такую схему можно, когда число тактов обратной связи . Для передачи данных по обратной связи используются регистры $\langle R_1 \div R_L \rangle$ . Предельно возможное число параллельно обрабатываемых данных определяется латентностью схемы (числом регистров).

Под буквой в) приведена мультиконвейерная схема распараллеливания, которая предполагает параллельное вычисление независимых данных. На практике также обычно выделяют частный случай: макроконвейерную схему. В отличие от мультиконвейерной схемы, макроконвейер обрабатывает поток данных, поступающих со скважностью , то есть идущих каждый такт. Фактически макроконвейерная схема возможна только в случае распараллеливания процедурных схем.

Под буквой г) показана схема распараллеливания относительно зависимых данных или же схема «распараллеливания по итерациям». Суть заключается в построении многостадийной обработки — конвейеризации последовательно выполняемых операций. Этот вариант распараллеливания целесообразно применять, когда следующая в цепочке операция может начинать обработку данных до завершения работы предыдущей.

Как и в прошлой статье, для простоты рассуждений положим, что период тактового сигнала $t_{\text{clk}}$ одинаков для всех рассматриваемых схем, а все арифметические операции выполняются за одно и то же время.

Схемы будем сравнивать по нескольким критериям:

число тактов работы схемы $N_{\text{op}}$ или конвейерная задержка схемы: через сколько тактов первые полученные данные появятся на выходе (чем меньше значение, тем лучше);
число вычислительных блоков, в том числе размер подсистем коммутации и синхронизации данных, что определяет требуемые аппаратные затраты на реализацию схемы.
в некоторых случаях будем давать оценку возможности работы схемы на предельной (максимальной) тактовой частоте, что определяет параметр $t_{\text{clk}}$ .

Коротко о КИХ-фильтрации

Использование методов распараллеливания проиллюстрирую на примере микроархитектуры фильтра с конечной импульсной характеристикой, или КИХ-фильтра. Математически КИХ-фильтрация описывается операцией свертки:

$y = x \cdot h$

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

$y_i = \sum_{j=0}^{N_{\text{coef}}-1} x_{i-j} \cdot h_j,$

где — элемент массива данных, представляющего собой исходный цифровой сигнал, $N_{\text{signal}}$ — размер массива ; — элемент массива данных, представляющего собой импульсную характеристику фильтра; $N_{\text{coef}}$ — размер массива .

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

Если вам интересно работать с архитектурой устройств, вы можете откликнуться на вакансии в нашу команду. Сейчас открыты такие позиции:

— разработчик FPGA;
— инженер по интеграции на FPGA;
— инженер по тестированию цифровых модемов.

Все вакансии — на карьерном сайте.

Распараллеливание по зависимым операциям

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

Для КИХ-фильтрации зависимыми являются все операции суммирования промежуточных данных. Причина в том, что один результат вычислений напрямую определяется множеством промежуточных результатов умножения. Получается, чтобы реализовать распараллеливание по зависимым данным, нужно распараллеливать не сами MAC-операции, а операции суммирования внутри них, выполняемые аккумулятором.

В общем виде аккумулятор суммирует элементы массива любой длины. Но когда длина массива фиксирована, можно выполнить распараллеливание по зависимым операциям. Так, вместо последовательного суммирования элементов входного массива данных, поступающих на вход i_D, можно выполнить их параллельное суммирование по представленной ниже схеме. То есть при распараллеливании по зависимым операциям обратная связь разворачивается в конвейерную схему. Если при этом коэффициент распараллеливания , где — предельное количество суммируемых элементов, из схемы полностью исключается обратная связь.

Предельное распараллеливание аккумулятора по зависимым операциям

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

Распараллеливание аккумулятора по зависимым операциям при коэффициенте распараллеливания M=2

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

В конвейерной схеме, в отличие от конвейерно-процедурной схемы, при коэффициенте распараллеливания , число сумматоров равно .

Отмечу: если коэффициент распараллеливания , рационально подбирать такое значение , чтобы при делении на получалось целое число: оно будет определять количество тактов, за которое будет получен результат вычислений. В то же время на практике коэффициент распараллеливания часто бывает степенью двойки.

Конвейеризация КИХ-фильтра

Конвейеризированная схема суммирования в предельном случае требует наличия входных каналов данных. Из-за этого в схеме MAC-операции также нужно распараллелить умножители с коэффициентом . Распараллеливание умножителей относится к распараллеливанию по независимым операциям, и как мы видим, в этом случае виды распараллеливания тесно связаны друг с другом. Использование одного вида распараллеливания операций внутри MAC-операции влечет за собой использование и второго вида распараллеливания.

Структурная схема конвейерной реализации КИХ-фильтра с последовательным суммированием

В представленной выше схеме блок Data Delay — это обычный сдвиговый регистр и реализует функцию организации «плавающего окна». В отличие от примера из предыдущей статьи, в этом блоке нет дополнительных мультиплексоров.

Временная диаграмма работы блока Data Delay

Фактически в блоке Data Delay выполняется «разворот» части последовательно поступающих данных в параллельный вид. При этом берется срез входного массива данных, размером по числу регистров, подключенных последовательно. В качестве примера на временной диаграмме выделены элементы входных данных x5–x8, поступающие на вход блока последовательно, но появляющиеся на выходах D1–D4 параллельно и одновременно.

Блок COEF REGFILE представляет собой регистровый файл, в котором хранятся коэффициенты импульсной характеристики КИХ-фильтра. В отличие от архитектур из первых двух статей, доступ ко всем коэффициентам должен осуществляться параллельно, поэтому этот блок невозможно реализовать в виде памяти RAM или ROM. Коэффициенты загружаются перед началом непосредственных вычислений. В рабочем режиме значения коэффициентов будут выведены на выходы блока С1–С4 параллельно и не будут меняться до окончания расчетов.

Еще в схеме есть два блока синхронизирующих задержек Delay 1 и Delay 2. Это обусловлено тем, что результат умножения третьего отсчета должен быть синхронизирован с результатом суммирования двух предыдущих результатов умножения. В нашем случае, когда latency операции суммирования равна 1, Delay 1 осуществляет задержку данных на один такт. По тому же принципу работает блок Delay 2, в котором задержка данных выполняется на два такта. В общем случае для latency операции суммирования L_add задержка в блоке Delay 1 равна L_add, а в блоке Delay 2 равна 2∙L_add.

Работа конвейерной схемы КИХ-фильтра показана на временной диаграмме ниже. Данные на входе i_D и на выходах блока Data Delay D1–D4 обновляются каждый такт работы схемы и поступают в блок фильтрации. В нем параллельно реализованы все операции умножения и сложения, которые нужны для расчета одного результирующего данного.

Временная диаграмма работы конвейерной схемы КИХ-фильтрации с последовательным суммированием

Количество тактов работы конвейерной схемы КИХ-фильтрации с последовательным суммированием c коэффициентом распараллеливания можно рассчитать по формуле:

$N_{\text{op}}^{\text{(pipe\_add\_line)}} = \frac{N_{\text{signal}} \cdot N_{\text{coef}}}{M} + N_{\text{coef}} \cdot L_{\text{add}}$

В предельном случае, когда коэффициент распараллеливания $M = N_{\text{coef}}$ , формула будет такой:

$N_{\text{op}}^{\text{(pipe\_add\_line)}} = N_{\text{signal}} + N_{\text{coef}} \cdot L_{\text{add}}$

В случае, если $N_{\text{coef}} \cdot L_{\text{add}} \ll N_{\text{signal}}$ , слагаемым $N_{\text{coef}} \cdot L_{\text{add}}$ можно пренебречь:

$N_{\text{op}}^{\text{(pipe\_add\_line)}} \approx N_{\text{signal}}$

Это соотношение отлично иллюстрирует особенность конвейерных схем:

При обработке больших объемов данных latency конвейера можно не учитывать, а время обработки определяется скоростью входного потока данных.

При фильтрации сигнала размером $N_{\text{signal}} = 1024$ с импульсной характеристикой фильтра $N_{\text{coef}} = 4$ c коэффициентом распараллеливания потребуется такое количество тактов:

$N_{\text{op}}^{\text{(pipe\_add\_line)}} = N_{\text{signal}} + N_{\text{coef}} \cdot L_{\text{add}} = 1024 + 4 \cdot 1 = 1028$

На практике при реализации на ПЛИС AMD (Xilinx) такая конвейерная схема позволяет задействовать аппаратно-реализованные примитивы DSP, используя их каскадное подключение. В таком случае схема подстраивается под архитектуру ПЛИС. Чтобы задействовать каскадный выход первого DSP-блока, нужно использовать его выходной сумматор-аккумулятор. По сути, он будет выполнять «незначимые» вычисления — суммирование результата с нулем. Но это позволит правильно передать данные с первого DSP-блока на следующий, в котором уже будет выполняться суммирование двух результатов умножения.

Структурная схема примитива DSP48e2 AMD (Xilinx) UltraScale

Из-за использования выходного сумматора-аккумулятора немного меняется схема синхронизации: вместо двух блоков задержек используется три блока Delay 1–Delay 3.

Структурная схема конвейерной реализации КИХ-фильтра с последовательным суммированием, использующая DSP-блоки

Оптимизация последовательности суммирования данных

Представленную схему конвейерной реализации КИХ-фильтра с последовательным суммированием можно несколько оптимизировать для реализации без использования каскадирования DSP блоков.

На первом этапе оптимизации перенесем задержки Delay 1–Delay 2 со входов умножителей на выходы. Такая оптимизация позволяет выполнять все операции умножения одновременно.

Конвейерная реализация КИХ-фильтра с переносом блоков задержек на выходы умножителей в схеме с последовательным суммированием

На втором этапе оптимизации заменим схему последовательного суммирования на схему с каскадным суммированием. Кроме уменьшения аппаратного ресурса, за счет удаления задержек Delay 1–Delay 2 у схемы меньшая latency.

Конвейерная реализация КИХ-фильтра: схема с каскадным суммированием

Количество тактов работы конвейерной схемы КИХ-фильтрации с каскадным суммированием c коэффициентом распараллеливания можно рассчитать по формуле:

$N_{\text{op}}^{\text{(pipe\_add\_cascad)}} = \frac{N_{\text{signal}} \cdot N_{\text{coef}}}{M} + \left\lceil \log_2(N_{\text{coef}}) \right\rceil \cdot L_{\text{add}}$

В предельном случае, когда коэффициент распараллеливания $M = N_{\text{coef}}$ , формула такая:

$N_{\text{op}}^{\text{(pipe\_add\_cascad)}} = N_{\text{signal}} + \left\lceil \log_2(N_{\text{coef}}) \right\rceil \cdot L_{\text{add}}$

Так, при фильтрации сигнала размером $N_{\text{signal}} = 1024$ с импульсной характеристикой фильтра $N_{\text{coef}} = 4$ c коэффициентом распараллеливания потребуется такое количество тактов:

$N_{\text{op}}^{\text{(pipe\_add\_cascad)}} = 1024 + 2 \cdot 1 = 1026$

Выводы

Если сравнивать аппаратный ресурс на реализацию конвейерных схем КИХ-фильтрации, видно, что схема с последовательным суммированием требует больше ресурсов для реализации подсистемы синхронизации данных, а именно блоков задержек входных данных Delay. При этом она отлично подходит для использования каскадного подключения DSP-блоков.

Схема с каскадным суммированием не требует дополнительной синхронизации входных данных. Ее стоит использовать при реализации КИХ-фильтра, без возможности использования каскадного подключения DSP-блоков. В то же время отдельные арифметические операции могут быть реализованы как на LUT, так и на DSP. Отмечу, что в самом каскаде сумматоров могут встречаться задержки, если коэффициент распараллеливания не равен степени двойки.

Время обработки данных конвейерными схемами КИХ-фильтра приблизительно равно времени работы макроконвейерной схемы, построенной на базе MAC-операций. Но для конвейерных схем значительно упрощается логика работы блока Data Delay, в котором не требуется реализовывать мультиплексирование данных. Также конвейерные схемы обычно не требуют мультиплексирования данных на выходе конвейера. При этом нужно учитывать, что в конвейерной схеме блок хранения коэффициентов фильтра реализуется не в виде памяти, а в виде регистрового файла.

Конвейерные схемы также можно распараллелить относительно независимых операций. Так, параллельная реализация двух рассмотренных выше конвейерных схем будет равна по производительности мультиконвейерной схеме с коэффициентом распараллеливания MAC-операций — рассматривали этот пример в предыдущей статье. Такие схемы используются на практике и известны как полифазные КИХ-фильтры.

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

Так в каких случаях рационально использовать те или иные методы распараллеливания, чтобы отношение времени работы схемы (число тактов работы умноженное на период тактовой частоты) к ее аппаратным затратам было минимальным?

Сначала нужно выбрать распараллеливание по зависимым операциям. Так мы сможем построить конвейерную схему, обладающую наименьшими затратами на дополнительную синхронизацию данных и на реализацию подсистемы коммутации. То есть схема будет проще как в реализации, так и в понимании.
Если после предыдущего пункта в схеме остались обратные связи (или же его выполнение в принципе невозможно), для распараллеливания схемы с обратной связью, latency которой больше одного такта, стоит использовать схему «Вложенный конвейер» (если это возможно).
После этого стоит использовать распараллеливание по независимым данным: мультиконвейерную и макроконвейерную схемы.

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

При разработке цифровых устройств основные параметры — это скорость обработки данных и аппаратные затраты. Чтобы подобрать оптимальный вариант микроархитектуры, нужно владеть теоретическим аппаратом распараллеливания цифровых схем. Если хотите этому научиться —приходите на соревнования по разработке СнК или летнюю стажировку Импульс, а если уже умеете, ждем на собеседованиях.

Что еще почитать по теме:

— «Архитектура цифровых устройств: разбираемся с процедурными и конвейерными вычислениями».
— «Как ускорить обработку данных. Часть 1: распараллеливание цифровых схем по независимым операциям».