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

Основная часть декомпозиции состоит из генератора комплексного скалярного произведения (также называемого векторным умножителем), который вычисляет уравнения (3) и (4). Для устройства Stratix V используется размер вектора (VS) до 90 комплексных элементов данных, тогда как для устройства Arria V реализован размер вектора до 45 комплексных элементов данных. Размер вектора соответствует количеству параллельных операций чтения из памяти, необходимых для предоставления генератору скалярного произведения нового набора данных для каждого такта, и, таким образом, определяет ширину и разбиение встроенной двухпортовой памяти. По соображениям реализации хранение массива заданного размера делится на (N/VS) блоков памяти ceiling, где ceiling(VS) — функция ceiling, а N — размер массива.
Конструкция решателя Холецкого является многоканальной. Максимальное количество каналов является параметром времени компиляции и ограничено только доступной памятью на устройстве. Разбиение памяти идентично одноканальной реализации, с той разницей, что создается определенное количество копий одной и той же структуры.

Разложение выполняется поэлементно, столбец за столбцом, начиная с верхнего левого угла и продвигаясь вертикально зигзагом, заканчивая в нижнем правом углу матрицы, как показано на рисунке 3(а). Сначала вычисляется диагональный элемент каждого столбца, затем все недиагональные элементы под ним в том же столбце, после чего происходит переход к диагональному элементу в верхней части следующего столбца справа. Расписание событий и итераций контролируется вложенным четырехуровневым циклом for. Внешний цикл обрабатывает столбец; второй цикл обрабатывает банк; третий внутренний цикл обрабатывает строки; и самый внутренний цикл обрабатывает различные каналы. Размещение обработки каналов в качестве самого внутреннего цикла фактически превращает аккумулятор с плавающей запятой в аккумулятор с разделением времени и лучше скрывает его задержку. Блок NestedLoops в DSP Builder Advanced Blockset объединяет до трех вложенных циклов в один блок обработки, ускоряя реализацию и более эффективно используя ресурсы по сравнению с аналогичной функцией, реализованной в виде трех отдельных блоков цикла for. Данный блок извлекает сложные сигналы управления контуром, сокращает время проектирования и отладки, а также делает структуру контура более читабельной

Генератор скалярных произведений работает со строками матрицы и одновременно за один цикл вычисляет умножения до размера вектора в сумме уравнений (3), (4) и (6). На входе генератора скалярных произведений используется циклическая структура памяти, охватывающая построчные циклы нескольких входных матриц.

Для скалярных произведений короче размера вектора неиспользуемые члены маскируются и не включаются в сумму. Для скалярных произведений длиннее размера вектора вычисляются частичные суммы произведений, которые сохраняются в пределах границ банков до тех пор, пока не будут суммированы все доступные банки для данного элемента в соответствующей строке для получения окончательной суммы, как показано на рисунке 3(b). Суммирование выходов банков выполняется в одном цикле аккумулятора с использованием блока сумматора с плавающей запятой из набора расширенных блоков DSP Builder. Задержка петли обратной связи составляет 13 циклов. За счет замены циклов банков и строк относительно их традиционного порядка реализации в программном обеспечении и добавления многоканальной обработки задержка аккумулятора с плавающей запятой скрывается, что повышает эффективность использования оборудования.
Набор расширенных блоков DSP Builder автоматически вычисляет задержки цикла для устранения этой задержки. Инструмент можно настроить для вычисления и использования минимальной задержки, установив флажок «Минимальная задержка» в блоке «Задержка цикла». Пути, вызывающие одинаковые задержки, могут быть снабжены номером группы эквивалентности, после чего инструмент присвоит одинаковое значение задержки всем членам группы. Хотя в примерах, рассмотренных в этой статье, это не использовалось, набор блоков DSP Builder Advanced Blockset предоставляет специализированный аккумулятор с плавающей запятой, который пользователь может настроить для оптимизации скорости и требований к ресурсам, задав такие параметры, как максимальный размер входного сигнала и требуемая точность накопления. Этот блок позволяет осуществлять накопление одного потока чисел с плавающей запятой за один цикл на выборку при высокой тактовой частоте.

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

Автор:

Разработано командой Berkeley Design Technology, Inc. Октябрь 2012 г

(Продолжение в марте)