Недавно я увлёкся программированием FPGA и решил, что будет интересно реализовать на FPGA алгоритм игры FizzBuzz. FPGA (программируемая пользователем вентильная матрица) — интересная микросхема. Она программируется на выполнение произвольной цифровой логики. Можно сконструировать сложную схему, не прокладывая физические каналы между отдельными вентилями и триггерами. Микросхема способна превратиться во что угодно, от логического анализатора до микропроцессора и видеогенератора.

Тест FizzBuzz — написать программку, которая выдаёт числа от 1 до 100, где кратные трём заменяются словом “Fizz”, кратные пяти — словом “Buzz”, а кратные пятнадцати — “FizzBuzz”. Поскольку такая программа реализуется в нескольких строчках кода, то её часто задают на собеседованиях чтобы отсеять тех, кто вообще не умеет программировать.


Плата Mojo FPGA, подключенная к порту serial-to-USB. Большой чип на плате — это Spartan 6 FPGA

Реализация FizzBuzz в цифровой логике, а не в коде, довольно бессмысленна, но показалась мне хорошим примером для обучения.¹ Для этого проекта я использовал простую плату разработки Mojo V3 FPGA для начинающих. На ней установлен FPGA семейства Xilinx Spartan 6. Это один из самых маленьких FPGA, но у него 9000 логических ячеек и 11 000 триггеров — так что малыш на многое способен.

Реализация последовательного вывода на FPGA

Что значит реализовать FizzBuzz на FPGA? Это значит, что контакты интерфейса ввода/вывода общего назначения (GPIO) с платы можно подключить к чему угодно, так что выдача FizzBuzz предстанет в разном виде: светодиодами, на семисегментных индикаторах, ЖК-дисплее, мониторе VGA. Я решил, что вывод текста в терминал по последовательному каналу наиболее соответствует духу «стандартной» программы FizzBuzz. Так что первым делом следует реализовать последовательный вывод на FPGA.

Основная идея последовательной связи — передача битов по одному. Последовательный порт RS-232 — простой протокол для последовательной передачи данных, изобретённый в 1960 году для подключения телетайпов и модемов. На диаграмме внизу показано, как символ “F” (двоичный 01000110) последовательно передаётся по каналу. Сначала отсылается стартовый бит (нулевой), чтобы указать начало символа.² Затем передаются восемь бит символа в обратном порядке. В конце отправляется стоповый бит. Между символами полоса остаётся в режиме ожидания (единица) до передачи следующего символа. При скорости передачи 9600 бод передача каждого бита занимает 1/9600 секунды. С восемью битами данных без бита чётности и одним стоповым битом этот протокол известен как 8N1. Существует много протоколов для последовательной передачи данных, но 9600 8N1 очень распространён.


Последовательная передача символа “F” на 9600 бод / 8N1

Первый шаг в реализации такой последовательной передачи — создать интервалы по 1/9600 секунды для каждого бита. Такой интервал измеряется подсчётом 5208 тактовых импульсов на Mojo.³ Я сделал 13-битный счётчик для периодического отсчёта от 0 до 5207. Простой конечный автомат отслеживает, какой бит выводится в каждом интервале. Он начинает работу с начального бита, меняет своё состояние по мере обработки восьми бит данных и стопового бита. Состояние хранится в четырёхбитном регистре (вообще, в FPGA вам придётся иметь дело с большим количеством тактовых импульсов, счётчиков и конечных автоматов).

Для создания интервала и регистров состояний в FPGA я написал код на языке описания аппаратуры Verilog. Не буду подробно объяснять Verilog — надеюсь, вы поймёте, как он работает. В следующем коде первые строки задают 13-битный регистр counter и четырёхбитный регистр state. Счётчик увеличивается до значения 5207, потом сбрасывается до 0, при этом state увеличивается на единицу для обработки следующего выходного бита. (Обратите внимание, что <= — это оператор присваивания, а не сравнения⁴). Строка always @(posedge clk) указывает, что процедурный блок срабатывает по положительному фронту тактовой частоты.

reg [12:0] counter;
reg [3:0] state;

always @(posedge clk) begin
  if (counter < 5207) begin
     counter <= counter + 1;
  end else begin
    counter <= 0;
    state <= state + 1;
  end
end

Хотя это похоже на обычный программный код, но работает он совершенно иначе. На обычном языке программирования операции обычно выполняются последовательно, так как программа выполняется построчно. Например, процессор проверяет значение counter. Затем добавляет единицу к counter. Но в Verilog нет ни процессора, ни выполняемой программы. Вместо этого код создаёт аппаратуру для выполнения операций. Например, для увеличения counter создаётся одна схема сложения, а для увеличения state — другая схема. Дополнительная логика создаётся для сравнения с 5207. В отличие от последовательного процессора, FPGA всё выполняет параллельно. Например, FPGA одновременно на каждом такте выполняет сравнение 5207, увеличение и сброс counter, а также увеличение state. Из-за этого в сильно параллельных задачах FPGA может работать быть гораздо быстрее, чем процессор.

Следующая часть кода выводит соответствующий бит для каждого состояния. Как и раньше, он выглядит как обычный программный код, но генерирует аппаратные цепи, а не операции, которые выполняются последовательно. В данном случае код создает логический вентиль (по сути мультиплексор) для выбора правильного значения out.

case (state)
  IDLE: out = MARK; // high
  START: out = SPACE; // low
  BIT0: out = char1[0];
  BIT1: out = char1[1];
  ...
  BIT6: out = char1[6];
  STOP: out = MARK;
  default: out = MARK;
endcase

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

Алгоритм FizzBuzz

Следующий шаг — определить, что конкретно отправить по последовательному каналу. Как перевести числа от 1 до 100 в символы ASCII? Это тривиально на микропроцессоре, но трудно в цифровой логике. Проблема в том, что преобразование двоичного числа в десятичное требует деления на 10 и 100, а деление очень неудобно реализовать в вентилях. Я решил использовать
двоично-десятичный счётчик (BCD), хранящий отдельно каждый из трёх разрядов. Это немного усложнило счётчик, поскольку в схему счётчика вводятся узлы, обеспечивающие корректировку процесса счёта при переполнении в ту или иную сторону от девятки. Но зато упрощается выдача цифр.

Я написал модуль BCD (исходный код) для трёхразрядного счётчика. У него три четырёхбитных счётчика digit2, digit1, и digit0. Флаг increment сигнализирует об увеличении счётчика. Обычно увеличивается только digit0. Но если он достигает девятки, то обращается в 0, а увеличивается digit1. Если digit1 тоже становится 9, то он обращается в 0, а увеличивается digit2. Таким образом, идёт отсчёт от 000 до 999.

if (increment) begin
  if (digit0 != 9) begin
    // Regular increment digit 0
    digit0 <= digit0 + 1;
  end else begin
    // Carry from digit 0
    digit0 <= 0;
    if (digit1 != 9) begin
      // Regular increment digit 1
      digit1 <= digit1 + 1;
    end else begin
      // Carry from digit 1
      digit1 <= 0;
      digit2 <= digit2 + 1;
    end
  end
end

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

Следующая задача — проверить делимость на 3 и 5. Как простое деление, деление с остатком тоже легко реализовать на микропроцессоре, но трудно в цифровой логике. Здесь нет встроенной операции деления, поэтому приходится создавать целую кучу вентилей. Хотя IDE может синтезировать их для деления с остатком, но это безвкусно. Вместо этого я просто сделал счётчики для остатков от деления на 3 и на 5. Например, mod3 просто будет выдавать 0, 1, 2, 0, 1, 2...⁵

Последняя часть FizzBuzz — код для вывода каждой строки символ за символом. В программе мы можем просто вызвать процедуру последовательного вывода для каждого символа. Но в FPGA нужно отслеживать, какой символ отправляется на вывод, с помощью ещё одного конечного автомата. Обратите внимание, что при преобразовании каждой цифры в ASCII двоичный 11 конкатенируется с использованием немного странного синтаксиса 2'b11. Приведённый здесь код немного упрощён. Полный код содержит проверки на нули в начале, так что “001” выводится как “1”.

state <= state + 1; // Different state from serial
if (mod3 == 0 && mod5 != 0) begin
  // Fizz
  case (state)
   1: char <= "F";
   2: char <= "i";
   3: char <= "z";
   4: char <= "z";
   5: char <= "\r";
   6: begin
     char <= "\n";
     state <= NEXT; // Done with output line
     end
  endcase
end else if (mod3 != 0 && mod5 == 0) begin
  ... Buzz case omitted ...
end else if (mod3 == 0 && mod5 == 0) begin      
 ... Fizzbuzz case omitted ...
end else begin 
  // No divisors; output the digits of the number.
  case (state)
    1: char <= {2'b11, digit2[3:0]};
    2: char <= {2'b11, digit1[3:0]};
    3: char <= {2'b11, digit0[3:0]};
    4: char <= "\r";
    5: begin
     char <= "\n";
     state <= NEXT;
    end
  endcase
end

Если собрать всё вместе, то окончательная схема FizzBuzz состоит из многочисленных конечных автоматов и счётчиков. Основной конечный автомат контролирует код вверху, перемещаясь по символам строки. Для каждого символа конечный автомат активирует модуль последовательного вывода и ожидает вывода символа. Внутри модуля конечный автомат проходит по каждому биту символа. Он ожидает, пока счётчик скорости передачи данных не отсчитает ширину бита. Когда передача символа завершена, модуль последовательного вывода отправляет сигнал главному конечному автомату. Тогда тот переходит к следующему символу в строке. Когда строка завершена, главный конечный автомат увеличивает счётчик BCD (который считает от 1 до 100) — и начинает вывод следующей строки.

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

Запуск FizzBuzz на плате FPGA

Для компиляции кода Verilog я использовал инструмент Xilinx ISE (см. ниже). В этой среде разработки можно писать код, моделировать его и синтезировать логические схемы для загрузки в FPGA. Инструмент ISE довольно понятен и объясняется в руководствах Mojo. Процесс синтеза выполняется гораздо медленнее компиляции: для моей программы FizzBuzz он занял около 45 секунд.


Написав код Verilog в инструменте Xilinx ISE, вы можете запрограммировать функциональность FPGA

Как только мой код заработал в симуляторе⁷, я загрузил его на плату FPGA по USB-кабелю. Я подключил контакт вывода FPGA к адаптеру USB-to-serial⁶ и использовал эмулятор терминала (screen) для отображения последовательного вывода на компьютере. Нажал кнопку перезагрузки на доске Mojo — и (после небольшой дополнительной отладки) появился вывод FizzBuzz (ниже).


Первая страница вывода FizzBuzz FPGA в эмуляторе терминала

Изображение ниже показывает необработанные данные последовательного вывода с FPGA (жёлтый). Это конечный результат работы схемы FizzBuzz на плате FPGA — последовательность импульсов. Осциллограф также демонстрирует расшифрованные символы ASCII (зелёный). На изображении — выдача FizzBuzz для 2, 3 и 4 (CR и LF — это символы возврата каретки и перевода строки).


Сигнал последовательного вывода данных (жёлтый) в начале вывода FizzBuzz. Расшифровка ASCII — зелёного цвета

Что происходит внутри FPGA?

Вы можете спросить, как описание схемы Verilog преобразуется в цифровую логику и как FPGA реализует эту логику. Инструмент синтеза ISE берёт описание Verilog — и генерирует схемы, подходящие для реализации внутри FPGA. Сначала из кода Verilog он синтезирует «список соединений» (netlist), определяя логику и соединения. Затем переводит списки в примитивы FPGA в соответствии с возможностями конкретного чипа (в нашем случае Spartan 6). В конце запускается процедура оптимизации для максимального сокращения пути сигнала.


Схема цепи FizzBuzz

На рисунке выше показана цепь FizzBuzz в том виде, в каком её генерирует инструмент синтеза. Как видите, код Verilog превращается в большой клубок схем. Каждый блок — это триггер, логический элемент, мультиплексор или другой элемент. Из блоков состоят счётчики, регистры состояний и логика схемы FizzBuzz. Хотя кажется, что здесь много логических элементов, на самом деле используется менее 2% мощности чипа. Крупным планом (ниже) показана схема триггера (с надписью “fdre”)⁸ и поисковой таблицы (с надписью “lut5”) из счётчика BCD. Что удобно в Verilog, так это что вы проектируете схему на высоком уровне — и она превращается в схему низкого уровня. Это называется RTL (уровень регистровых передач) и позволяет применять регистры и высокоуровневых операции над ними, не беспокоясь о низкоуровневой аппаратной реализации. Например, вы можете просто написать count + 1 — и получите схему двоичного сумматора.


Детальная схема триггера и поисковой таблицы

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

Например, часть логики для выходного контакта эквивалентна логической схеме ниже. Она реализуется сохранением 64-битного значения FFFFA8FFFFA8A8A8 в поисковой таблице. В микросхеме Spartan 6 эта LUT размещается в 64 битах статической оперативной памяти, которая загружается при инициализации FPGA. Поскольку в микросхеме 5720 отдельных таблиц, то её можно запрограммировать на реализацию множества произвольных схем.


Логические элементы, реализованные одной поисковой таблицей в FPGA

Последняя часть задачи — матричный переключатель, который произвольным образом соединяет схемы. В Spartan 6 несколько LUT, триггеров и мультиплексоров собраны в конфигурируемые блоки логики (CLB)⁹. Эти CLB соединяются матричными переключателями, как показано ниже. Каждый блок матричного переключателя запрограммирован на соединение разных шин, что позволяет прокладывать контакты FPGA как угодно. Важная часть процесса синтеза FPGA — позиционирование блоков для минимизации расстояния проводки. Это нужно как для минимизации задержки распространения сигнала, так и для сохранения резерва путей межсоединений.


Матричный переключатель в Spartan 6 FPGA допускает произвольные соединения между CLB. Из руководства пользователя

Стoит ли мне попробовать FPGA?

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

Однако я бы не рекомендовал эксперименты с FPGA, если вы хоть немного не знакомы с подключением светодиодов/переключателей и не понимаете базовую цифровую логику: вентили, триггеры и конечные автоматы. Но если вам хорошо с Arduino, то FPGA — это разумный следующий шаг.

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

Mojo — хорошая плата для начала?

Плату разработки Mojo FPGA продают Adafruit и Sparkfun, так что я подумал, что это хороший хакерский выбор. Плата создана для новичков в программировании FPGA, и она хорошо справляется с этой ролью. Создатели Mojo написали большую коллекцию руководств по использованию Verilog.¹⁰. Если руководство написано для конкретной платы, то проблемы с платой и инструментами решаются гораздо быстрее. Mojo программируется по стандартному кабелю USB — это удобнее, чем специальные переходники JTAG.


Плата Mojo FPGA с чипом Spartan-6 FPGA

Хотя на Mojo много контактов ввода/вывода, но с ней не продаётся никакой периферии, кроме восьми светодиодов. Приятнее было бы поэкспериментировать с платой, если есть кнопки, семисегментные дисплеи, выход VGA, сенсоры и так далее. (Их нетрудно подключить к Mojo, но удобно было бы иметь в комплекте). Кроме того, у некоторых плат разработки есть внешняя оперативную память, а у Mojo нет. Это проблема для приложений вроде логического анализатора, требующего много памяти.¹¹ (Хотя вы можете расширить Mojo с помощью накладки IO или накладки RAM).

Хорошая книга для начала работы с Mojo — «Программирование FPGA». В ней описываются и значительно более дешёвые платы Papilo One и Elbert 2. Если хотите посмотреть другие варианты, вот список плат разработки FPGA.

Заключение

Задачу FizzBuzz непрактично реализовать на FPGA, но это было интересно, я узнал много нового о программировании FPGA. Но конечно, я не получу работу, если вопрос FizzBuzz зададут на интервью! Мой код на GitHub, но имейте в виду, что я пока новичок в этом деле.

Примечания и ссылки

1. Реализовать микропроцессор на FPGA — тривиальная задача. Например, с чипом Spartan 6 можно нажать пару кнопок в визарде IDE — и он сгенерирует схему для процессора MicroBlaze. Поэтому умный человек написал бы код FizzBuzz в нескольких строчек C, а потом запустил его на процессоре внутри FPGA. Но для меня это слишком просто. ^

2. Начальный бит необходим, иначе получатель не сможет определить начало символа, если первый бит символа равен 1. ^

3. Поскольку в Mojo тактовая частота составляет 50 МГц, то на 9600 бод каждый бит займёт 50000000/9600 или примерно 5208 тактов. Это не очень высокая скорость, так что для эксперимента я запустил код на скорости 10 млн бод (отсчёт до пяти тактов для каждого бита) — и схема выдержала (интерфейс USB-to-serial поддерживает скорость только до 230400 бод, так что я проверял результат на осциллографе). ^

4. В Verilog <= является неблокирующим оператором присваивания, а = — это блокирующий оператор присваивания. Неблокирующие присваивания происходят параллельно и обычно используются для последовательной логики (тактовый триггер). Блокирующие присваивания используются для комбинаторной логики (без тактов). Это немного путанно, подробнее см. здесь. ^

5. Я использовал не двоичный, а двоично-десятичный счётчик, так что остаток от деления на 5 определяется почти тривиально, глядя на последнюю цифру. Но остаток от деления на 3 нетривиален, так что пришлось оставить вариант со счётчиком. ^

6. Нельзя было направить последовательный ввод напрямую на компьютер, потому что у него нет последовательного порта. Вместо этого я использовал переходник USB-to-serial, FTDI Friend от Adafruit. Этот адаптер может принимать ещё и 3,3-вольтовый сигнал, в отличие от неудобных +/? 15 вольт в оригинальном RS-232. ^

7. Отладка FPGA совершенно отличается от отладки программы. Поскольку FPGA — это по сути чёрный ящик, то сначала нужно всё проверить в симуляторе, иначе вы попадёте в «FPGA-ад» с моргающими светодиодами, пытаясь понять, что происходит. В процессе отладки для имитации схемы нужно написать «испытательный стенд» (testbench) — код Verilog, который в разное время подаёт разные входные данные (пример). Затем запустите симулятор (ниже) и проверьте, что выдача правильная.


Симулятор ISim от Xilinx позволяет проверить схему FPGA

Если что-то пойдёт не так, симулятор позволяет пройтись по внутренним сигналам и выявить проблему. После полного тестирования в симуляторе при запуске на реальном FPGA у моего кода остались только самые тривиальные проблемы. Главная из них заключалась в том, что я назначил последовательный вывод на неправильный контакт, поэтому вывода не было. ^

8. Spartan 6 FPGA поддерживает несколько типов триггеров. FDRE — это D-триггер с синхронным входом сброса/установки и работой по синхросигналу. ^

9. Конфигурируемые блоки логики Spartan 6 FPGA (CLB) довольно сложны. Они содержат модули LUT, 8 триггеров, широкие мультиплексоры, логику, распределенную RAM и регистры сдвига. Жёстко впаянные компоненты этих блоков немножко снижают гибкость, но сильно упрощают конструкцию матричных переключателей. CLB подробно описаны в Руководстве пользователя по CLB. В Spartan 6 FPGA есть и другие типы блоков, в том числе блоки генерации тактовых импульсов и блоки DSP, способные производить быстрое умножение 18?18 бит. ^

10. Альтернативой языку Verilog является VHDL, который тоже поддерживается средой разработки. Mojo поддерживает ещё и Lucid, более простой язык FPGA, разработанный командой Mojo. Руководства по Lucid от Mojo объясняют язык, а есть ещё книга на эту тему. Впрочем, я решил, что лучше выучить стандартный язык, чем Lucid. ^

11. У Mojo нет внешней RAM, но есть 576 килобит внутренней памяти. Хотя это крошечный объём по сравнению с платами, у которых мегабайты внешней DRAM. ^