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

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

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

24.09.2026 12:03

ratragor 0 2500 Источник

Привет, Хабр! Меня зовут Кирилл Алексеев, я ведущий инженер в отделе интеграции систем на кристалле радиочастотного центра YADRO. Сегодня снова поговорим «за разработку под ПЛИС».

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

В этой статье разберем основные виды параллелизма цифровых схем, которые (естественно) сильно отличаются от видов распараллеливания программ. Как и в предыдущем моем тексте, виды параллелизма сравним на примере распараллеливания микроархитектуры КИХ-фильтра, реализованной с использованием MAC-операции. Я отвечу на вопрос, какой вид стоит использовать, когда ключевой критерий — пропускная способность схемы throughput,то есть определена скорость поступления и обработки данных.

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

Виды распараллеливания цифровых схем

Распараллеливание цифровых схем — основной способ увеличения скорости обработки данных за счет использования дополнительных аппаратных ресурсов системы. В контексте ПЛИС-разработки речь идет об обмене «площади» кристалла на скорость обработки данных. Получается, за счет увеличения числа реализуемых в ПЛИС операций, увеличивается утилизация ПЛИС (используемая площадь), а время решения задачи уменьшается.

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

С точки зрения теории выделяют несколько основных видов распараллеливания цифровых схем. Не все используемые термины устоялись в научной среде, поэтому приведу классификацию со всеми названиями, встречающимися в литературе:

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

Основные виды распараллеливания цифровых схем

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При выполнении КИХ-фильтрации сигнала, схему MAC-операции в пределе можно распараллелить по числу выходных данных.

При расчете каждого результирующего элемента данных все операции умножения также независимы по отношению друг к другу.

Зависимые — это операции, которые привязаны к результатам промежуточных расчетов. Для КИХ-фильтрации это все операции суммирования.

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

Макроконвейер

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

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

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

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

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

Принцип работы схемы проиллюстрирован ниже временной диаграммой. Входные слова данных поступают на обработку по шине i_D вместе с сигналом валидации i_v. Первое входное слово данных поступает на обработку в блок MAC 1. Четыре следующих такта работы блок MAC 1 будет занят вычислением первого выходного результата, как это проиллюстрировано на временной диаграмме. Второе слово данных вместе с первым поступают в блок MAC 2 и так далее. Результаты вычислений Q1–Q4 выходят с блоков MAC 1–MAC 4, поступают на выходной мультиплексор и последовательно коммутируются на выход схемы o_Q.

После того как блок MAC 1 выдаст первый результат, он примет на обработку данные x1–x4 и будет их обрабатывать следующие четыре такта. В это время блоки MAC 2–MAC 4 будут обрабатывать следующие порции входных данных: x2–x5, x3–x6 и x4–x7 соответственно.

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

Отдельно отмечу, что блок Data Delay помимо линии задержки содержит подсистему коммутации: на каждом из выходов блока D1–D4 стоит мультиплексор, который коммутирует на выход один из регистров блока задержки. Также в блоке выделена подсистема управления ctrl unit, которая управляет выходными мультиплексорами.

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

$N_{\text{op}}^{\text{mac\_macro}} = N_{\text{signal}} \cdot \frac{N_{\text{coef}}}{M} + L_{\text{mac}},$

где $L_{\text{mac}} = N_{\text{coef}} + 2$ — latency макроконвейерной схемы.

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

$L_{\text{mac}} \ll N_{\text{signal}} \cdot \frac{N_{\text{coef}}}{M},$

из-за чего при подсчете числа тактов работы схемы слагаемым $L_{\text{mac}}$ можно пренебречь:

$N_{\text{op}}^{\text{mac\_macro}} \approx N_{\text{signal}} \cdot \frac{N_{\text{coef}}}{M}.$

Получается, при фильтрации сигнала с заданными параметрами потребуется такое количество тактов:

$N_{\text{op}}^{\text{mac\_macro}} \approx N_{\text{signal}} \cdot \frac{N_{\text{coef}}}{M} = 1024 \cdot \frac{4}{4} = 1024$

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

Вместе с этим вырос и аппаратный ресурс на реализацию подсистем коммутации и управления в блоке Data Delay. Для представленной схемы дополнительные расходы на коммутацию данных не сильно влияют на общие аппаратные затраты. Но такая реализация схемы КИХ-фильтра большего порядка (с большим числом коэффициентов импульсной характеристики фильтра) приводит к необходимости использования большего коэффициента распараллеливания $(N_{\text{coef}} = M > 64)$ . Из-за этого подсистема коммутации будет занимать значительный процент аппаратного ресурса, причем из-за увеличения мультиплексоров при реализации на ПЛИС ресурс будет расти нелинейно. Также из-за увеличения уровней логики для сохранения возможности работы схемы на максимальной тактовой частоте может потребоваться дополнительная конвейеризация используемых мультиплексоров и дешифраторов.

Мультиконвейер

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

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

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

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

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

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

Теперь рассмотрим второй вариант мультиконвейерной схемы, когда на вход КИХ-фильтра поступает полифазный сигнал: данные приходят по двум параллельным каналам данных i_D1 и i_D2 со скважностью . Заметим, что для хранения двух входных данных, поступающих каждый такт, требуется второй сдвиговый регистр в блоке Data Delay. Также в блоке Data Delay усложняются схемы управления (ctrl unit) и коммутации, а именно увеличивается число выходных мультиплексоров: один на каждую реализуемую MAC-операцию.

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

В зависимости от выбранного уровня абстракции, такая микроархитектура одновременно является:

мультиконвейерной схемой, состоящей из восьми процедурных блоков MAC-операций;

мультиконвейерной схемой, состоящей из двух параллельных макроконвейеров.

Структура мультиконвейерной реализации КИХ-фильтра с использованием MAC-операций при поступлении данных по двум каналам со скважностью S=1

Принцип работы схемы проиллюстрирован в виде временной диаграммы ниже (не пугаемся). Блок Data Delay выполняет распределение заданий между доступными блоками MAC-операций, но несколько иначе, чем в предыдущих случаях. Так как уже в первом такте работы схема получит два слова входных данных, потребуется две MAC-операции для получения двух слов результата. В этом случае рационально первое задание передать в первый макроконвейер (D11), а второе – во второй (D21). Тогда на выходе будут одновременно сформирована пара значений y0 и y1.

Временная диаграмма работы схемы КИХ-фильтрации. Реализована на восьми MAC-операциях при двух входных каналах данных и скважности поступления данных S=1

Подсчитаем число тактов работы двух представленных мультиконвейерных схем. Для этих архитектур так же, как и для предыдущих, не будем учитывать параметр $L_{\text{mac}}$ , так как это слагаемое все еще значительно меньше второго слагаемого: $L_{\text{mac}} \ll N_{\text{signal}} \cdot \frac{N_{\text{coef}}}{M}$ , где $L_{\text{mac}} = N_{\text{coef}} + 2$ . Но в случае, когда порядки данных слагаемых становятся сопоставимы, этот параметр следует учитывать в формулах.

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

$N_{\text{op}}^{(\text{mac\_m2})} \approx \frac{N_{\text{signal}} \cdot N_{\text{coef}}}{M} = \frac{1024 \cdot 4}{2} = 2048$

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

$N_{\text{op}}^{(\text{mac\_m8})} \approx \frac{N_{\text{signal}} \cdot N_{\text{coef}}}{M} = \frac{1024 \cdot 4}{8} = \frac{1024}{2} = 512$

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

Вложенный конвейер

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

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

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

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

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

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

Число тактов работы представленной выше схемы можно рассчитать по формуле:

$N_{\text{op}}^{(\text{Lacc\_4\_clock\_cycles})} = N_{\text{signal}} \cdot N_{\text{coef}} \cdot L_{\text{FB}} + L_{\text{mac}},$

где $L_{\text{FB}} = 4$ – число тактов обратной связи конвейерной схемы суммирования, $L_{\text{mac}} = N_{\text{coef}} \cdot L_{\text{FB}} + 1$ .

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

$N_{\text{op}}^{(\text{Lacc\_4\_clock\_cycles})} = 16401$

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

Если же сумматор представляет собой конвейерную схему с задержкой, равной четырем тактам, можно использовать принцип распараллеливания «Вложенный конвейер». Стоит отдельно отметить, что для его использования не нужно менять схему. Меняется только порядок поступления и обработки данных.

Как видно на временной диаграмме, на вход схемы i_D поступают сразу четыре набора входных данных (по количеству тактов задержки в обратной связи). Каждое слово входных данных умножается на коэффициент импульсной характеристики C и поступает на вход сумматора. В тот момент, когда на выходе сумматора Acc (и, соответственно, на его же втором входе) появится результат суммирования, на выходе умножителя Mult появится результат умножения соответствующего входного элемента из блока Data Delay на следующий множитель импульсной характеристики. После умножения входных данных на все элементы импульсной характеристики на выходе сумматора Acc будет сформировано четыре результата rez0-rez3, которые последовательно передадутся на выход схемы.

Число тактов работы схемы «Вложенный конвейер» можно рассчитать по формуле:

$L_{\text{mac}} = N_{\text{coef}} \cdot L_{\text{FB}} + 1,$

где $L_{\text{FB}} = 4$ — число тактов обратной связи конвейерной схемы суммирования, но при фильтрации сигнала размером $N_{\text{signal}} = 1024$ с импульсной характеристикой фильтра $N_{\text{coef}} = 4$ временем задержки данных $L_{\text{mac}}$ можно пренебречь.

Число тактов обработки данных схемой «Вложенный конвейер» с коэффициентом распараллеливания можно рассчитать по формуле:

$N_{\text{op}}^{(\text{nested\_pipeline})} \approx \frac{N_{\text{signal}} \cdot N_{\text{coef}} \cdot L_{\text{FB}}}{M} = 4096$

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

К чему пришли

После рассмотрения макроконвейерной и мультиконвейерной схем распараллеливания и схемы «Вложенный конвейер» делаем выводы:

При использовании любой схемы распараллеливания по независимым операциям время решения задачи уменьшается линейно и пропорционально коэффициенту распараллеливания. Но в некоторых случаях большую роль может играть latency схемы, из-за чего при использовании больших коэффициентов распараллеливания время решения задачи все же будет уменьшаться медленнее.
При использовании макроконвейерной или мультиконвейерной схем распараллеливания аппаратный ресурс на реализацию вычислений увеличивается линейно и пропорционально коэффициенту распараллеливания.
Аппаратный ресурс на реализацию подсистемы коммутации может увеличиваться нелинейно и требовать дополнительной конвейеризации.
При использовании схемы распараллеливания «Вложенный конвейер» аппаратный ресурс на реализацию вычислений и подсистемы коммутации не меняется при условии конвейерной реализации используемых операций, а схема не требует глобальной переработки.

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