В отличие от алгоритма Холецкого, где уравнения (1) – (6) реализованы как один вложенный четырехуровневый цикл, решатель QR использует один конечный автомат (FSM) для циклического выполнения четырех основных операций: нахождения квадрата модуля вектора в уравнении (2), скалярного произведения двух векторов в уравнении (4), вычитания скалярного произведения вектора в уравнении (6) и скалярного произведения в уравнении (7) для нахождения вектора d. Блок NestedLoop из набора расширенных блоков DSP Builder используется на всех этапах работы FSM для генерации всех управляющих сигналов событий для тракта данных.
Общим блоком обработки в четырех упомянутых выше операциях является генератор скалярного произведения. Для повышения производительности используется векторная обработка для вычисления скалярного произведения. Аналогично конструкции Холецкого, размер вектора является параметром времени компиляции. Для повторного использования этого генератора в четырех состояниях конечного автомата на входе используется мультиплексор данных, управляемый обработчиком событий конечного автомата. Мультиплексор выбирает правильные входные данные для генератора скалярного произведения в каждом состоянии конечного автомата. Детали генератора скалярного произведения и аккумулятора с плавающей запятой аналогичны тем, что используются в конструкции Холецкого, поэтому здесь они не приводятся.
Память, необходимая для QR-разложения, оптимизируется за счет повторного использования основного блока памяти ядра, который изначально содержит матрицу A и входной вектор b. Обработка происходит по столбцам, слева направо, в памяти ядра. Как только столбец заполнен и больше не нужен, он перезаписывается соответствующим столбцом новой матрицы. Когда старый массив A разрушается, исходное содержимое этого блока памяти заменяется новым массивом, что позволяет поддерживать сквозную вычислительную мощность массива без пауз.
В первых двух состояниях конечного автомата элементы матрицы R генерируются поэлементно в направлении строк, начиная с диагонального элемента для каждой строки. В состоянии вычитания конечного автомата столбцы матрицы A в основной памяти рекурсивно обновляются и заменяются частично вычисленными векторами. Например, в столбце k все столбцы k+1 и обновляются в памяти путем вычитания масштабированной версии из каждого из столбцов от k+1 до n. Этот процесс рекурсивно вычисляет векторы от uk+1 до un и является более эффективной версией уравнения (6) для аппаратной реализации. При обработке в направлении столбцов в четвертом состоянии конечного автомата каждый вновь вычисленный uk умножается на входной вектор b для генерации одного элемента dk вектор-столбца d. Матрица Q не генерируется явно, но ее ортогональные столбцы uk генерируются и используются на более поздних этапах конечного автомата. Затем эти столбцы перезаписываются в соответствующем столбце ak новой матрицы в следующем цикле конечного автомата. На рисунке 5 показана организация памяти и последовательность обработки подсистемы QR-разложения.
Выходами первой подсистемы являются матрица R и вектор-столбец d. Матрица R представляет собой верхнетреугольную матрицу и генерируется по столбцам слева направо, как показано в уравнениях (3) и (4). Применяется треугольная структура памяти типа «пинг-понг». Пока верхняя треугольная часть обрабатывается в подсистеме обратной подстановки, нижняя треугольная часть заполняется подсистемой декомпозиции, и наоборот. Вектор-столбец d добавляется к матрице R и генерируется по столбцам сверху вниз. Выходом обратной подстановки является вектор решения x линейных уравнений Ax = b.
Решатель QR-проверки может быть реализован в многоканальном формате, аналогичном решателю Холецкого, для повышения эффективности использования ресурсов, уменьшения задержки и повышения производительности проектирования. Повышение производительности в основном обусловлено эффективным сокращением задержки в аккумуляторе операций с плавающей запятой.
3. Методология оценки
процесса проектирования и инструментария.
Для этой оценки компания Altera предоставила BDTI реализации решателей Холецкого и QR-критериев, созданные с использованием набора блоков DSP Builder Advanced Blockset. Altera предоставила инженерам BDTI ПК с предустановленными инструментами Altera и MathWorks. Затем инженеры BDTI изучили, смоделировали и синтезировали проекты Altera в среде Simulink. Синтезированные проекты были затем применены к двум различным устройствам: ПЛИС Stratix V и Arria V. В ходе этого процесса BDTI оценила процесс проектирования Altera и производительность двух примеров проектов.
Поскольку платы, использованные для этой оценки, не могли генерировать стимулы для примеров проектов, каждый проект содержит блок генерации стимулов, реализованный с использованием блоков DSP Builder Advanced Blockset и скомпилированный вместе с проектом тестируемого приложения. Для минимизации влияния блока стимулов на производительность тестового проекта и использование ресурсов FPGA, матрица A генерируется в режиме реального времени блоком стимулов из гораздо меньшего набора случайных данных. Этот небольшой набор данных генерируется с помощью m-файловых скриптов в MATLAB, загружается в память блока стимулов и компилируется вместе с проектом. Эти скрипты MATLAB используют тот же алгоритм, что и блок стимулов в тестовом проекте, для генерации эталонных данных с плавающей запятой двойной точности для вектора решения x с целью измерения уровня ошибки моделей и проектов Simulink, подаваемых на FPGA. В проекте Холецкого этот алгоритм гарантирует положительное эрмитово определение матрицы A, в то время как проект с использованием решателя QR гарантирует создание хорошо обусловленной матрицы A. Для проекта решателя Холецкого были реализованы четыре конфигурации размера вектора, матрицы и канала: три на FPGA Stratix V и две на устройстве Arria V, при этом одна конфигурация является общей для обоих. Для проектирования QR-решателя были реализованы четыре конфигурации на ПЛИС Stratix V, две из которых также были реализованы на устройстве Arria V. Все конфигурации были оценены с точки зрения использования ресурсов ПЛИС, максимальной тактовой частоты, производительности и функциональной корректности. Ограничения проектирования ПЛИС, такие как тактовая частота, выбор устройства и уровень скорости, задаются в среде Simulink.
Производительность и возможности оценивались как на уровне модели Simulink, так и на уровне аппаратной платформы. Модель Simulink для обеих конфигураций была оснащена инструментами для визуализации как прямого процесса, так и общего числа циклов прямой и обратной обработки, в то время как программное обеспечение Quartus II предоставляло максимальную частоту (Fmax), достигнутую для каждой конфигурации. Затем каждая конфигурация загружалась на аппаратную платформу, ее рабочая частота устанавливалась на Fmax, и процесс запускался. Векторы решений (x) каждого решателя для каждой конфигурации фиксировались и сравнивались с соответствующими эталонными значениями чисел с плавающей запятой двойной точности, сгенерированными в MATLAB.
Скрипт, выполняющийся после моделирования, вычисляет разницу между выходными данными Simulink IEEE 754 с одинарной точностью и векторами значений с плавающей запятой двойной точности, сгенерированными в MATLAB. Аналогичным образом, скрипт вычисляет разницу между выходными данными, полученными в результате моделирования на аппаратном уровне, и векторами значений с плавающей запятой двойной точности, сгенерированными в MATLAB.
Оценка инструментария Simulink
основана на среде MATLAB и, следовательно, требует её использования. В среде Simulink оцениваемые проекты используют блоки из набора блоков DSP Builder Advanced Blockset, который является отдельным набором блоков от стандартной библиотеки DSP Builder. Набор блоков DSP Builder Advanced Blockset ориентирован на блочную реализацию алгоритмов цифровой обработки сигналов и трактов данных и использует более высокий уровень абстракции, чем стандартная библиотека DSP Builder, которая включает более общие и элементарные блоки. Библиотека DSP Builder Advanced Blockset содержит более 50 распространенных тригонометрических, арифметических и булевых функций, в дополнение к более сложным функциональным блокам для быстрого преобразования Фурье (БПФ) и КИХ-фильтров. К заметным дополнениям в версии Quartus II 12.0 относятся блок для вычисления квадратного корня с низкой задержкой, вложенный цикл for и настраиваемые блоки для аккумулятора с плавающей запятой. Элементы стандартного набора блоков и набора блоков DSP Builder Advanced Blockset нельзя смешивать в структуре тракта данных на одном и том же уровне иерархии; Только блоки из набора блоков DSP Builder Advanced поддерживают компилятор чисел с плавающей запятой. Блоки из набора блоков Standard не оптимизированы для обработки чисел с плавающей запятой. Кроме того, хотя импорт HDL-кода, написанного вручную, доступен для набора блоков Standard, он недоступен для набора блоков DSP Builder Advanced, поскольку этот инструмент не может выполнять реализацию на уровне HDL. В целом, блочный подход к вводу данных для проектирования хорошо подходит для алгоритмов DSP; однако, поскольку такие конструкции, как `case` или `switch`, недоступны в библиотеке блоков, текстовый подход более интуитивно понятен для проектов с интенсивным управлением и проектов, включающих конечные автоматы.
Запуск симуляции с помощью DSP Builder Advanced Blockset компилирует модель Simulink, генерирует HDL-код и ограничения для программной среды Altera Quartus II, создает тестовый стенд и скриптовые файлы для среды ModelSim, а также моделирует модель Simulink. Время симуляции для различных конфигураций варьировалось от 3 до 28 минут в зависимости от размера массива, используя ПК с процессором Intel Xeon W3550. Симуляция Simulink предоставляет подробные оценки использования ресурсов без необходимости компиляции программного обеспечения Quartus II, что помогает разработчику быстро определить необходимый размер устройства. При использовании комплекта разработки оборудования пользователь должен указать назначение выходных контактов в соответствии с компоновкой платы. Пользователь может применить ограничения для выходных контактов в прилагаемом файле .qsf в папке проекта программного обеспечения Quartus II для проектирования или использовать конфигурацию контактов программного обеспечения Quartus II для назначения и управления выходными контактами с самого начала.
Были проведены тесты модели для оценки простоты исследования алгоритма и генерации соответствующего HDL-кода. Входные параметры, такие как размер скалярного произведения, размер матрицы и тип данных, изменялись в блоке стимулов и во время выполнения моделирования. Во всех случаях корректный RTL-код генерировался в течение нескольких минут, а результаты моделирования соответствовали эталонному коду MATLAB.
Все конфигурации были синтезированы с использованием программного обеспечения для проектирования Quartus II, которое можно запускать непосредственно из среды Simulink. Разработчик может использовать Quartus II в режиме «нажатия кнопки» с параметрами оптимизации по умолчанию или выбранными пользователем, либо использовать инструмент Design Space Explorer (DSE). DSE, являющийся частью Quartus II, автоматически выполняет несколько проходов маршрутизации, используя разные начальные значения для каждого прохода. Маршрут с наилучшей тактовой частотой сохраняется. Это автоматизированный процесс, не требующий вмешательства пользователя, но занимающий значительно больше времени, чем метод «нажатия кнопки», который с Quartus II занимал от 1 до 6,5 часов в зависимости от размера проекта.
Высокий уровень абстракции, применяемый в процессе проектирования DSP Builder Advanced Blockset, ускоряет циклы исследования и моделирования алгоритмического пространства, тем самым сокращая общее время, необходимое для достижения оптимизированного конечного проекта. Однако это преимущество не является неотъемлемой частью Simulink в той же мере, как, например, распространение типов данных. Чтобы воспользоваться преимуществами исследования проектного пространства, предлагаемыми блочным методом проектирования по сравнению с написанным вручную RTL-кодом, разработчик должен предпринять дополнительные шаги при создании модели Simulink. В частности, модель должна быть структурирована таким образом, чтобы позволить исследование алгоритмического пространства на основе параметров. В примерах, проанализированных в этой статье, модели были реализованы таким образом, чтобы позволить тестирование с различными размерами матриц, размерами векторов и (в случае решателя Холецкого) количеством параллельных каналов. После создания модели, включающей эту гибкость, можно исследовать оценки производительности и использования ресурсов для различных конфигураций проекта, изменяя эти параметры. Для достижения хороших показателей производительности и эффективного использования ресурсов также необходимо понимать конструкцию аппаратного обеспечения, как это показано на примере аккумулятора с плавающей запятой, рассмотренного в разделе 2 данной статьи.
Обучение работе с DSP Builder Advanced Blockset включает 4 часа лекций от Altera и около 10 часов онлайн-семинаров и демонстраций. Кроме того, BDTI потратила около 90 часов на изучение инструмента и обеих моделей на практических занятиях. Время и усилия, необходимые для освоения инструментария, будут зависеть от навыков и предварительных знаний разработчика.
Инженер, имеющий опыт проектирования на основе блоков Simulink и проектирования аппаратного обеспечения, скорее всего, сочтет метод на основе DSP Builder Advanced Blockset эффективным и простым в использовании. Для разработчика FPGA с небольшими или нулевыми знаниями MATLAB и Simulink проектирование на более высоком уровне абстракции может представлять собой новый способ мышления и, следовательно, первоначальную проблему, которая может повлиять на кривую обучения. После ознакомления с методологией разработчик может добиться значительно более быстрых циклов проектирования, чем при использовании HDL. Он может сосредоточиться на реализации алгоритма, не беспокоясь о деталях проектирования аппаратного обеспечения, таких как сегментация. Время проектирования и верификации значительно сокращается, поскольку большая часть моделирования и функциональной верификации выполняется в среде Simulink. Полученный в Simulink RTL-код можно затем запустить в программе ModelSim для полного функционального моделирования.
Для инженера, обладающего предварительными знаниями в области проектирования систем и практически не имеющего опыта проектирования аппаратного обеспечения, кривая обучения может быть менее крутой. Хотя инструментарий интегрирует компиляцию, синтез, трассировку и автоматическую генерацию скриптов в среде Simulink и абстрагирует множество сложных концепций проектирования, таких как сегментация данных и векторизация сигналов, для завершения реализации все же необходимы некоторые знания в области аппаратного обеспечения.
(Продолжение в апреле)
Автор:
Разработано командой Berkeley Design Technology, Inc. Октябрь 2012 г
