Радиотехника и электроника, 2021, T. 66, № 12, стр. 1178-1188

ВВЕДЕНИЕ

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

Традиционно проектируемое цифровое устройство принято представлять в виде операционного устройства (datapath) и устройства управления (control unit), которые обычно проектируются отдельно: операционное устройство – в виде совокупности стандартных функциональных узлов (регистров, шин, мультиплексоров и др.), а устройство управления – в виде конечного автомата (finite state machine – FSM).

В работе [1] предложено объединить вместе операционное и управляющее устройства и представить как конечный автомат с трактом обработки данных (finite state machine with datapath, FSMD). Модель FSMD быстро стала популярной, в [2] приведены варианты FSMD для синхронных и асинхронных проектов. Модель FSMD оказалась очень удобной для проверки эквивалентности двух схем, полученных в результате синтеза или различных проектных преобразований [3, 4]. В работе [5] предложено цифровую систему представлять в виде сети FSMD, которая приводит к реализации аппаратуры, свободной от гонок.

Общая модель FSMD не всегда удобна при проектировании конкретных приложений. Поэтому в ряде работ предложены расширения FSMD: в [6] – для представления архитектуры процессора и ASIC (application-specific integrated circuit); в [7] – для синхронного доступа к памяти; в [8] – для программ обработки массивов. Уменьшение потребляемой мощности путем декомпозиции FSMD рассмотрено в [9], а путем стробирования – в [10]. Сравнение эффективности FSM и FSMD приведено в [11].

Благодаря своей наглядности блок-схемы автоматов (algorithmic state machine, ASM) получили широкое распространение для представления алгоритмов функционирования конечных автоматов. ASM впервые были предложены в [12] как альтернатива графам автоматов. В работе [13] рассмотрена реализация ASM на PROM, FPLA и мультиплексорах, а в [14] предложены методы минимизации числа вершин ASM. В [15] описан инструмент ABELITE синтеза контроллеров, основанных на ASM.

Традиционно ASM используют для представления алгоритма функционирования устройства управления. В [16] предложено использовать ASM как для описания поведения устройства управления, так и для описания регистровых операций, выполняемых в операционном устройстве. Такая ASM получила название блок-схема автомата с трактом обработки данных (algorithmic state machine with datapath, ASMD). Диаграммы ASMD в последнее время все чаще применяют в проектах на FPGA: при реализации промышленных систем управления [17]; для реализации функции asin с помощью алгоритма CORDIC [18]; при аппаратной реализации криптографического алгоритма AES [19]; при проектировании универсального асинхронного приема-передатчика UART [20].

В данной работе исследована основанная на языке Verilog методика ASMD-FSMD при проектировании синхронных умножителей и процессоров PIC на программируемых логических интегральных схемах (ПЛИС – field programmable gate array, FPGA). В методике ASMD-FSMD функционирование устройства представляется в виде схемы ASMD, которая на языке Verilog описывается в виде конечного автомата с трактом обработки данных.

1. ТРАДИЦИОННЫЙ ПОДХОД К ПРОЕКТИРОВАНИЮ ЦИФРОВЫХ УСТРОЙСТВ

Рассмотрим простейший школьный алгоритм умножения, выполняющий арифметическую операцию умножения P = A × B двух двоичных чисел шириной N битов. Вначале P обнуляют. В каждом цикле умножения проверяют значение младшего разряда множителя B[0]. Если B[0] = 1, то к произведению P прибавляется множимое A. Если B[0] = 0, то к произведению P прибавляют ноль или ничего не прибавляют. Затем содержимое множителя B сдвигают на один разряд вправо, а значение произведения P – влево. Алгоритм заканчивается после рассмотрения всех битов множителя B.

На рис. 1 представлена структурная схема синхронного умножителя в виде операционного устройства (Datapath) и устройства управления (FSM). Значения чисел A и B поступают на вход операционного устройства. На выходах операционного устройства формируется произведение P и сигнал done, указывающий на окончание процесса умножения. Кроме того, операционное устройство формирует внутренний сигнал roll, совпадающий с сигналом done. Устройство управления FSM формирует следующие управляющие сигналы: load – для загрузки в регистры операционного устройства значений умножаемых слов A и B; clr – для сброса регистров операционного устройства; ena – для разрешения операции сдвига содержимого сдвиговых регистров.

Рис. 1.

Структурная схема синхронного умножителя в виде операционного устройства и устройства управления.

Схема операционного устройства, реализующего алгоритм умножения, показана на рис. 2. Операционное устройство включает сдвиговый регистр влево ra, сдвиговый регистр вправо rb и регистр rp для хранения слов A, B и P соответственно, шинный мультиплексор 2-1 и сумматор на 2N разрядов, а также счетчик по модулю counter, который формирует сигнал roll.

Рис. 2.

Схема операционного устройства синхронного умножителя.

Функционирование устройства управления синхронного умножителя можно представить в виде автомата типа Мили (рис. 3a) или автомата типа Мура (рис. 3б). Отметим, что конечный автомат типа Мили содержит два состояния: S₀ и S₁, в то время как автомат типа Мура содержит три состояния: S₀, S₁ и S₂. Детали описания компонентов операционного устройства (см. рис. 2) и конечных автоматов Мили и Мура (см. рис. 3) на языке Verilog при реализации синхронного умножителя в случае традиционного подхода приведены в [21].

Рис. 3.

Представление устройства управления синхронного умножителя в виде графа конечного автомата: a – типа Мили, б – типа Мура.

2. БЛОК-СХЕМЫ АВТОМАТОВ ASM

Блок-схема автомата (ASM) предназначена для наглядного описания алгоритма функционирования конечного автомата и представляет собой ориентированный связный граф [12], содержащий вершины трех типов:

1) прямоугольники – вершины состояний (state box);

2) ромбы – условные вершины (decision box);

3) овалы – вершины выходов по условию (conditional output box).

Вершина состояния ASM (прямоугольник) определяет состояние автомата. Вблизи вершины состояния может записываться имя состояния (например, S0, START, INITIAL и др.), а также двоичный код состояния. В случае автомата Мура внутри вершины состояния записывают выходные сигналы, принимающие единичное значение в данном состоянии. По умолчанию полагается, что все остальные выходные сигналы в данном состоянии имеют нулевое значение.

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

В вершинах выходов по условию (овалах) записывают выходные сигналы автомата Мили, принимающие единичное значение на определенном переходе. В ASM для автоматов Мура отсутствуют вершины выходов по условию (овалы), а в ASM для автоматов Мили в вершинах состояний ничего не записывают.

Главным строительным элементом блок-схемы ASM является блок ASM (ASM block), пример которого показан на рис. 4. Блок ASM описывает поведение автомата в одном состоянии в течение одного такта синхронизации. Поэтому блок ASM включает только одну вершину состояния (прямоугольник) и может иметь несколько условных вершин (ромбов) и вершин выходов по условию (овалов), причем ромбы могут как предшествовать овалам, так и следовать после овалов. Входы и выходы вершин соединяют с помощью дуг. Блок ASM имеет только один вход, который является входом в вершину состояния, и может иметь один или несколько выходов. Внутри блока ASM запрещены обратные связи. Циклы алгоритма и ждущие вершины в ASM реализуют с помощью внешних обратных связей.

Рис. 4.

Блок ASM.

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

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

3. МЕТОДИКА ASMD-FSMD

Блок-схема ASM с трактом обработки данных (ASM with datapath, ASMD) представляет собой ASM, в которой в прямоугольниках и овалах можно записывать любые операции над регистрами, которые допустимы в языке Verilog, а в условных вершинах можно проверять любые логические выражения языка Verilog. Схема ASMD, так же как ASM, состоит из блоков. Действия, описанные внутри блока ASMD, выполняются в течение одного такта синхронизации. Реализуемый по ASMD конечный автомат называется конечным автоматом с трактом обработки данных (FSM with datapath, FSMD). Методику ASMD-FSMD представим в виде следующего алгоритма.

Алгоритм. Методика ASMD-FSMD проектирования цифровых устройств.

Шаг 1. Определяют состояния FSMD.

Шаг 2. Для каждого состояния строят блок ASMD.

Шаг 2.1. В условных вершинах ASMD записывают логические функции, значения которых проверяют в данном состоянии.

Шаг 2.2. Для FSMD Мура в вершинах состояний (прямоугольниках) записывают операции, выполняемые с содержимым регистров в данном состоянии.

Шаг 2.3. Для FSMD Мили в вершинах выходов по условию (овалах) записывают операции, выполняемые с содержимым регистров на данном переходе.

Шаг 3. Блоки ASMD соединяют между собой в соответствии с алгоритмом работы устройства. При этом каждый выход блока ASMD может быть соединен только с одним входом данного или другого блока ASMD.

Шаг 4. При необходимости выполняют оптимизацию ASMD.

Шаг 5. Непосредственно по ASMD строят код FSMD на языке Verilog. Переменным ASMD в коде соответствуют регистры или триггеры (для однобитных переменных). Логическим функциям, проверяемым в условных вершинах ASMD, соответствуют логические выражения в операторах if. Действия, выполняемые в блоках ASMD, описывают в виде процедурных блоков begin…end. Операции, выполняемые в прямоугольниках ASMD (для автоматов Мура), описывают вначале блока begin…end, а операции, выполняемые в ромбах (для автоматов Мили), описывают в соответствующих местах операторов if (возможно с использованием операторных скобок begin…end).

Шаг 6. Выполняют реализацию FSMD с помощью соответствующего средства проектирования.

Шаг 7. Конец.

Главным этапом методики ASMD-FSMD является построение ASMD на основе алгоритма функционирования устройства. Представление функционирования цифрового устройства в виде ASMD больше напоминает алгоритмическое описание устройства [21]. Однако в отличие от алгоритмического описания в ASMD явно определены состояния FSMD, которые могут соответствовать состояниям устройства управления. В отличие от традиционного подхода, в ASMD отсутствует строгое разделение на операционное устройство и устройство управления, а также в ASMD явно не определяется структура операционного устройства. Кроме того, представленная методика ASMD-FSMD позволяет реализовывать как автоматы типа Мили, так и автоматы типа Мура, а также совмещенную модель автоматов Мили и Мура (в [16] рассмотрена ASMD только для автоматов типа Мура).

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

На рис. 5 представлена ASMD, которая соответствует FSMD типа Мили для реализации рассматриваемого синхронного умножителя. Особенностью схемы ASMD на рис. 5 является то, что здесь имеются только два блока ASMD: в состоянии S₀ выполняется инициализация регистров, а состояние S₁ соответствует одному циклу умножения.

Рис. 5.

Схема ASMD для автомата Мили, обеспечивающая наибольшее быстродействие синхронного умножителя.

Из рисунка видно, что один цикл умножения выполняется за один такт синхронизации, поэтому умножение N-разрядных двоичных чисел по ASMD на рис. 5 осуществляется за n тактов синхронизации, где n = N + 1.

Отметим отличия методики ASMD-FSMD от известных подходов к проектированию цифровых устройств. Методика ASMD-FSMD позволяет:

а) описывать как автоматы типа Мили, так и автоматы типа Мура (в [16] ASMD описывают только автоматы Мура), а также совмещенные модели автоматов типа Мили и Мура;

б) объединять в одной схеме ASMD описание операционного устройства и устройства управления (в [16] ASMD отдельно описывают операционные и управляющие устройства);

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

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

4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ

Исследование эффективности методики ASMD-FSMD проводили при реализации на FPGA семейства Cyclone IV E с помощью системы Quartus Prime версии 18.1 известных методов умножения [22]. Были исследованы следующие классические методы умножения:

1) алгоритм a, когда проверяется младший разряд множителя, множитель сдвигается вправо, а множимое – влево (рассмотренный выше школьный алгоритм);

2) алгоритм b, когда проверяется старший разряд множителя, множитель сдвигается влево, а множимое – вправо;

3) алгоритм c, когда проверяется старший разряд множителя, множитель и частные произведения сдвигаются влево;

4) алгоритм d, когда проверяется младший разряд множителя, множитель и частные произведения сдвигаются вправо.

Кроме того, был исследован алгоритм умножения Бута и модифицированный алгоритм умножения Бута (всего шесть методов умножения).

Каждый метод умножения был реализован с помощью традиционного подхода в виде операционного устройства и устройства управления, а также с помощью методики ASMD-FSMD (всего 12 проектов). Проекты исследовали с шириной входных слов 4, 8, 16, 32, 64 и 128 битов (72 примера).

Результаты экспериментальных исследований приведены в табл. 1.

Анализ табл. 1 показывает, что использование методики ASMD-FSMD для большинства примеров позволяет уменьшить стоимость реализации и увеличить быстродействие. При этом в отдельных случаях стоимость реализации уменьшается в 1.47 раза, т.е. на 47% (пример mult_a_128), а быстродействие увеличивается в 2.96 раза (пример mult_d_16). Эти значения выделены полужирным шрифтом.

Для исследования методики ASMD-FSMD при проектировании более сложных проектов были созданы следующие проекты процессора PIC [21]:

а) PIC_1_cycle_N – однотактовый процессор PIC;

б) PIC_multi_N – многотактовый процессор PIC;

в) PIC_2_cycle_N – двухтактовый процессор PIC;

г) PIC_4_cycle_N – четырехтактовый процессор PIC,

где число N обозначает ширину шины данных в битах.

Каждый проект был реализован с помощью традиционного подхода и с помощью методики ASMD-FSMD (всего восемь проектов). Проекты процессора PIC исследовали при ширине шины данных N, равной 4, 8, 16, 32, 64 и 128 битов (всего 48 примеров). Результаты исследования проектов процессоров PIC приведены в табл. 2.

Анализ табл. 2 показывает, что при проектировании процессоров PIC методика ASMD-FSMD уступает традиционному подходу по стоимости реализации, однако в большинстве случаев выигрывает по быстродействию, для отдельных примеров в 1.46 раза (проект PIC_2_cycle_128). Это значение выделено полужирным шрифтом.

Среднеарифметические значения отношений L_T/L_A и t_T/t_A для каждого метода умножения представлены в табл. 3.

Из табл. 3 следует, что методика ASMD-FSMD позволяет в среднем уменьшить стоимость реализации для большинства методов умножения (исключение составляют методы mult_c и mbooth), а также для всех методов увеличить быстродействие. Особенно заметно увеличение быстродействия для методов mult_c и mult_d (выделено полужирным шрифтом).

Аналогичные средние значения отношений L_T/L_A и F_T/F_A для проектов процессоров PIC представлены в табл. 4. Анализ табл. 4 показывает, что использование методики ASMD-FSMD позволяет увеличить быстродействие процессоров PIC в среднем в 1.1 раза (т.е. на 10%), а для двухтактовых процессоров PIC – в 1.26 раза (т.е. на 26%) (выделено полужирным шрифтом). В то же время методика ASMD-FSMD уступает традиционному подходу по стоимости реализации в среднем от 2 до 16%.

Чтобы оценить время проектирования при традиционном подходе и с использованием методики ASMD-FSMD, все проекты создавались одним разработчиком. Время в минутах, затраченное на разработку каждого проекта, приведено в табл. 5.

Анализ табл. 5 показывает, что использование методики ASMD-FSMD позволяет значительно (в среднем в 6.25 раза) уменьшить время разработки проектов. Это связано с тем, что в случае применения методики ASMD-FSMD отпадает необходимость в разработке (написании кода и отладке) каждого компонента операционного устройства, самогó операционного устройства, устройства управления, а также главного модуля проекта.

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

1) при проектировании цифровых устройств, поведение которых хорошо представляется в виде алгоритма функционирования, методика ASMD-FSMD по стоимости реализации и быстродействию имеет преимущество по сравнению с традиционным подходом;

2) при проектировании сложных функциональных блоков (например, процессоров, цифровых фильтров и др.) традиционный подход и специальные методы проектирования могут иметь преимущество над методикой ASMD-FSMD;

3) во всех случаях методика ASMD-FSMD имеет преимущество над традиционным подходом по времени проектирования.

ЗАКЛЮЧЕНИЕ

На примере проектирования синхронных умножителей и процессоров PIC рассмотрены две технологии проектирования цифровых устройств: традиционный подход и методика ASMD-FSMD.

Методика ASMD-FSMD может использоваться при проектировании цифровых устройств на любой элементной базе (не обязательно FPGA), например, на специализированных интегральных схемах ASIC. В качестве языка проектирования может использоваться любой язык описания аппаратуры (не обязательно Verilog), например, VHDL или SystemVerilog.

Методика ASMD-FSMD требует дальнейшего совершенствования путем:

а) использования особенностей языков проектирования, например, применение в одном блоке ASMD нескольких операторов блокирующего назначения к одному и тому же регистру [22];

б) разработки методов повышения быстродействия ASMD, например, путем уменьшения числа состояний в циклах алгоритма;

в) разработки методов оптимизации ASMD с целью повышения производительности и надежности, а также уменьшения стоимости реализации.

Перспективным направлением также видится использование методики ASMD-FSMD для высокоуровневого проектирования сложных проектов.