Диссертация (1150736), страница 14
Текст из файла (страница 14)
Поскольку прямое сравнение противоречит лицензионному соглашению библиотеки, была выполнена собственная реализация блока на основе документациии синтеза полупроводниковой схемы. Эта реализация была использована длясравнения.Сравнение показывает, что сокращение размера таблиц на практике приводит к уменьшению размера полупроводникового блока аппроксимации функций.
Вычислительные компоненты могут быть переиспользованы для вычисления нескольких функций, в этом случае для хранения таблиц следует использовать блок ПЗУ, что приведет к дополнительному уменьшению площади.В таблице 2.3 приведено сравнение площадей блока и вещественного умножителя FP32. Практический выигрыш в площади логической схемы существенноменьше, чем оценка сокращения размера таблиц. Это - ожидаемый результат, поскольку логическая схема кроме таблиц содержит и вычислительныеэлементы, площадь которых не уменьшается.
При этом выигрыш в 35-45%достаточно значителен для оправдания замены кусочно-полиномиальной аппроксимации на предложенную схему.Таблица 2.1: Относительный размер блока при задержке 5 нсТочность = 2, к-сплайн-4 = 2,к-сплайн-2 = 2 = 32455%72%110%100%3268%84%112%100%76Таблица 2.2: Относительный период максимальной тактовой частотыТочность = 2, к-сплайн-4 = 2,к-сплайн-2 = 2 = 32470%74%78%100%3278%74%78%100%Таблица 2.3: Относительный размер блока по сравнению с вещественнымумножителемВид блокаРазмерMUL FP32 w/o denorm1SINCOS24, = 2, к-сплайн-41.5SINCOS32, = 2, к-сплайн-43.277Глава 3Поточный алгоритм БПФ намногобанковой памятиВ данной главе изучаются алгоритмы реализации БПФ по произвольнымоснованиям на антимашине Хартенштейна.Антимашиной по классификации Хартенштейна [23] называется крупногранулярная реконфигурируемая вычислительная машина.
Принципиальнымотличием антимашины является отсутствие программы в виде последовательности инструкций. Программа задается выбором конфигурации крупногранулярных компонент на продолжительном интервале времени. Это обеспечиваетупрощение блока вычислений за счет уменьшения памяти программ и декодера инструкций, которые могут отнимать до половины площади и энергиивычислительного блока.
Антимашина не является в общем случае универсальной, упрощение приводит к ограничению исполнения алгоритмов. Толькоспециально разработанные алгоритмы, учитывающие архитектуру антимашины, могут быть выполнены.Характерным свойством алгоритма БПФ и других частотных преобразований является связь всех точек во входных и выходных данных.
Распараллеливание таких алгоритмов сопряжено с усложнением архитектуры памяти дляобеспечения одновременного чтения и записи нескольких точек по сложномузакону адресации.78Определение 5 Бабочкой называют алгоритм расчёта ДПФ без расщепления по определению =−1∑︁2 − ,0 ≤ ≤ − 1,=0−1где — размер или основание бабочки, ( )−1=0 — входной массив, ( )=0 —выходной массив.Поточные алгоритмы обеспечивают вычисление одной бабочки БПФ с интервалом запуска в один такт. Они хорошо подходят для реализации на антимашине. К достоинствам поточных алгоритмов относятся:∙ высокая скорость;∙ возможность варьировать длину БПФ во время работы;∙ использование энергоэффективных библиотечных компонент памяти;∙ возможность переиспользования вычислительных компонент и памяти вдругих алгоритмах.Блок–схема поточного блока вычислений БПФ с бабочкой размера показана на рис.
3.1. Данный блок является вариантом реализации антимашины.Вычислительная компонента (Processing Unit) выполняет операцию бабочкис интервалом запуска в один такт. Исходными данными для этой операцииявляются чисел, по одному из каждого банка данных.
С помощью реконфигурации блока вычислительные ресурсы, задействованные в вычислении бабочек БПФ, также могу использоваться для выполнения векторных операцийкомплексного и вещественного сложения и умножения, вычисления элементарных и логических функций, фильтрации и свертки данных.Пусть требуется выполнить БПФ на = отсчётов с некоторым натуральным . Если перестановки в блоках Interconnect не приводят к дополнительным запаздываниям и если чтение и запись в блоках памяти осуществляется за один и тот же такт, то общее время вычислений ДПФ равно ( ) =log ( ) + ,79Address GenerationtwiddlesaddressInterconnectInterconnectbank 0bank 1...Processing Unitbank R-11r1w RAMРис.
3.1: Архитектура блока потокового вычисления БПФ с 1r1w памятью. — длина конвейера внутри вычислительной компоненты.В данном разделе изучаются способы реализации БПФ на антимашинеХартенштейна, требующего именно этого минимального времени расчёта ( ).При разработке алгоритмов были поставлены следующие дополнительныеограничения:∙ отсутствие дополнительной памяти для промежуточных значений;∙ использование оперативной памяти с формулой 1rw;∙ полное использование скорости доступа к памяти;∙ отсутствие кеширования памяти;∙ отсутствие арбитрирования одновременных доступов;∙ изменение параллелизма на этапе проектирования схемы;∙ эффективное изменение длины БПФ во время работы схемы;∙ отсутствие отдельного шага переупорядочивания данных.80В первом разделе доказаны формулы, представляющие БПФ в терминахпроизведения Кронекера.
Во втором разделе описаны алгоритмы реализацииБПФ с фиксированным набором банков памяти. Третий раздел посвящён самосортируюшимся алгоритмам БПФ с ограничениями по чтению и записи.3.1Общий подход к разработке поточных акселераторов БПФРассмотрим поточную архитектуру акселератора БПФ на основе многопортовой памяти с произвольным доступом. Многопортовая память используется для обеспечения одновременной записи и чтения нескольких данныхпо различным адресам. Предположим, что банки памяти на рис. 1 содержатэлементы 1r1w, в которых за один такт можно осуществить одно считываниеи одну запись.Конфликтом доступов к памяти называется ситуация нескольких одновременных доступов по различным адресам к одному порту банка памяти.
Поскольку порт банка памяти может обеспечить доступ только к одному значению, конфликт памяти приводит к необходимости реализации логики арбитрирования (упорядочивания) одновременных доступов и задержкам вычислений. Поставим задачу о поиске такого способа считывания и записи послекаждой бабочки, при котором не будет происходить конфликтов. Тем самым,процессор и память будут загружены полностью, что минимизирует как времяработы, так и объём используемой памяти.3.1.1Синхронные графы потоков данныхФормализуем требования архитектуры с помощью теории синхронныхграфов потока данных [74].
Введем несколько определений.Определение 6 Назовем синхронным графом потока данных (SDF) ориентированный граф = (, , , , ), где - множество узлов, представляющих актеров (вычислительные блоки), - множество дуг, представляющих ориентированные каналы передачи данных.81Актеры пересылают дискретные сообщения по каналам данных. Актер ∈ активируется, когда на его входных дугах находится ( ), ∈ сообщений. В момент активации актер стирает ( ) входных сообщений и записывает ( ), ∈ исходящих сообщений. Дуги могут содержать начальный набор сообщений ( ).Определение 7 Назовем расписанием синхронного графа потока данных последовательность активации узлов = 1 2 .. , > 0, возвращающуюсостояние графа в исходное состояние.Определение 8 Назовем итерацией синхронного графа потока данных выполнение расписания .Выполнение расписания для синхронного графа потока данных может бытьсмоделировано в дискретном времени.Определение 9 Назовем гомогенным синхронным графом потока данных(HSDF), граф потоков данных = (, , , , ), если ( ) =( ) = 1, ∈ .Рассмотрим набор операций над данными, реализуемый данным графом потока данных .
Каждый из узлов может быть сконфигурирован для выполненияодной операции из подмножества, реализуемого данным узлом.Определение 10 Назовем архитектурным шаблоном гомогенный синхронныйграф потока данных = (, , , , ), где ( ) ⊂ , ∈ - множествоподдерживаемых узлом операций, ≥ 0 - длина внутреннего конвейера (задержка исполнения в тактах).Задержка означает время срабатывания узла. Нулевая задержка означаетнемедленное исполнение в том же кванте времени. Чтобы существовало расписание, суммарная задержка в любом цикле должна быть больше 0.Определение 11 Назовем конфигурацией архитектурного шаблона ,если ( ) ∈ ( ), ∈ .82Определение 12 Назовем = (, ) инструкцией архитектурного шаблона , где - конфигурация и - константное количество итерацийсинхронного графа потока данных, определяемого конфигурацией.Определение 13 Назовем = 1 ..
, > 0 программой архитектурногошаблона , где - инструкции.Будем говорить, что алгоритм реализуем архитектурным шаблоном на набореданных, если существует программа архитектурного шаблона, реализующаявыполнение этого алгоритма на данном наборе данных.На рис. 3.2 показан архитектурный шаблон, соответствующий архитектурена на рис.
3.1 без учета многобанковой памяти.CARRExpMulAWFWРис. 3.2: Архитектурный шаблон блока потокового вычисления БПФ.Здесь - счетчик, - блок вычисления комплексных экспонент, , - генераторы адресов чтения и записи, , - порты чтения и записи, - векторный комплексный умножитель, - блок вычисления бабочки.833.1.2Расщепляющее правило БПФПусть — натуральное число и = −2. Дискретное преобразованиеФурье (ДПФ) порядка является линейным оператором с матрицейℱ = [ ]0≤,< .Для произвольных целых > 0 и 0 ≤ < введём обозначение , для–го стандартного орта в R .Далее ⊗ обозначает произведение Кронекера: если = ⊗ , размерности матриц и равны × и × ℓ, соответственно, то +,ℓ+ = , ,при всех 0 ≤ < , 0 ≤ < , 0 ≤ < , 0 ≤ < ℓ.Далее будем использовать следующие свойства произведения Кронекера:( ⊗ ) = ⊗ ,( ⊗ )( ⊗ ) = () ⊗ (),( ⊗ ) ⊗ = ⊗ ( ⊗ ).Второе равенство справедливо только при условии корректности произведений и .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
