Содержание к диссертации
Введение
1. Архитектура систем и алгоритмы цифровой обработки сигналов 11
1.1. Архитектура цифровых сигнальных процессоров 11
1.2. Архитектура СнК, предназначенных для цифровой обработки сигналов 13
1.3. Архитектура параллельных процессоров 16
1.4. Архитектура процессоров с поддержкой явного параллелизма на уровне инструкций (VLIW) 19
1.5. Базовые алгоритмы цифровой обработки сигналов 21
1.5.1. Дискретное и быстрое преобразование Фурье 21
1.5.2. Операции над векторами и матрицами 27
1.5.3. Корреляция и КИХ-фильтры 28
1.5.4. БИХ-фильтры
1.6. Вычисления с плавающей точкой 32
1.7. Выводы и постановка задачи 34
2. Исследование проблем построения параллельных сопроцессоров для ЦОС с использованием многопоточной архитектуры 37
2.1. Модель исполнения OpenCL 37
2.2. Модель сопроцессора Ml с поддержкой многопоточной модели исполнения
2.2.1. Структура и набор инструкций модели сопроцессора Ml 41
2.2.2. Блок выбора исполняемого варпа и выборки инструкции 44
2.2.3. Блок доступа к разделяемой памяти з
2.2.4. Производительность модели сопроцессора Ml с использованием различных параметров архитектуры при реализации алгоритмов ЦОС 51
2.3. Модель сопроцессора М2 с поддержкой многопоточной модели
исполнения и параллелизма на уровне инструкций по принципу VLIW 55
2.3.1. Структура модели сопроцессора М2 55
2.3.2. Набор инструкций модели М2 57
2.3.3. Блок планирования выполнения инструкций и влияние алгоритмов планирования на производительность сопроцессора М2 61
2.3.4. Производительность модели сопроцессора М2 с использованием различных параметров архитектуры при реализации алгоритмов ЦОС 67
2.4. Выводы 70
3. Способы повышения эффективности реализации алгоритмов ЦОС на параллельных сопроцессорах 73
3.1. Применение конвертируемой адресации памяти 73
3.1.1. Расположение матриц в регистровой памяти модели М2 74
3.1.2. Реализация БПФ и свертки для сопроцессора М2 с применением конвертируемой адресации регистров 76
3.1.3. Расположение матриц в векторной памяти с применением скошенной адресации 78
3.2. Применение векторов переменной длины 81
3.2.1. Модель исполнения программы при использовании векторов переменной длины 82
3.2.2. Структура планировщика выполнения инструкций, использующих вектора переменной длины 83
3.2.3. Производительность выполнения программ при использовании векторов переменной длины 88
3.3. Применение инструкций, работающих с комплексными числами 90
3.3.1. Сокращение объема кода алгоритмов ЦОС и числа обращений к памяти 91
3.3.2. Многофункциональный векторный вычислительный блок с изменяемой структурой конвейера 93
3.3.3. Многофункциональный вычислительный конвейер на основе сумматора с 3 операндами 97
3.4. Выводы 102
4. Разработка высокопроизводительного векторного сопроцессора с поддержкой векторов переменной длины и конвертируемой адресации памяти... 105
4.1. Сопроцессор МЗ с поддержкой векторов переменной длины и конвертируемой адресации памяти 105
4.1.1. Структура и модель исполнения сопроцессора МЗ 106
4.1.2. Набор инструкций сопроцессора МЗ 111
4.2. Реализация алгоритмов ЦОС для сопроцессора МЗ 114
4.2.1. Реализация БПФ по алгоритму двумерного разложения 114
4.2.2. Реализация свертки 116
4.2.3. Реализация умножения матрицы на вектор 118
4.2.4. Реализация параллельной редукции
4.3. Производительность сопроцессора МЗ с использованием различных параметров архитектуры при реализации алгоритмов ЦОС 124
4.4. Результаты синтеза RTL-модели сопроцессора МЗ 129
4.5. Сравнение сопроцессоров Ml, М2 и МЗ 132
4.6. Выводы 135
Заключение 136
Перечень используемых сокращений 139
Литература
- Архитектура процессоров с поддержкой явного параллелизма на уровне инструкций (VLIW)
- Модель сопроцессора Ml с поддержкой многопоточной модели исполнения
- Реализация БПФ и свертки для сопроцессора М2 с применением конвертируемой адресации регистров
- Реализация БПФ по алгоритму двумерного разложения
Введение к работе
Актуальность работы
Требования к производительности систем цифровой обработки сигналов постоянно растут: появляются новые стандарты связи с широкими полосами пропускания, используется цифровая модуляция радиосигналов, требуется обрабатывать многоканальные сигналы в одном устройстве, и так далее. В настоящее время основным способом увеличения производительности является применение параллельных вычислений при условии эффективного использования аппаратных ресурсов. В связи с этим актуальной является разработка новых способов построения устройств, выполняющих задачи цифровой обработки сигналов, используя параллельные вычисления, в частности, программируемых сопроцессоров, предназначенных для применения в составе СБИС класса «система на кристалле».
Цель диссертационной работы
Повышение производительности СБИС класса «система на кристалле» при выполнении цифровой обработки сигналов путем применения архитектурных решений, позволяющих эффективно организовать параллельную обработку данных в формате с плавающей точкой. Для достижения данной цели в диссертации решаются следующие задачи:
-
Исследование возможностей и проблем построения сопроцессоров для цифровой обработки сигналов с использованием многопоточной архитектуры с целью определения факторов, ограничивающих производительность, способов повышения производительности, а также определения целесообразности применения многопоточной архитектуры для построения цифровых сигнальных процессоров.
-
Разработка системы векторной памяти, которая бы эффективно работала при использовании характерных для цифровой обработки сигналов режимов адресации.
-
Разработка модели исполнения и системы команд сопроцессора, которая бы позволяла обрабатывать задачи различного размера с минимальным числом циклов и вспомогательных инструкций в программах и способствовала достижению масштабируемости архитектуры.
-
Разработка структуры вычислительного конвейера сопроцессора, позволяющего достичь высокой эффективности реализации основных алгоритмов цифровой обработки сигналов.
-
Разработка структуры и RTL-модели сопроцессора, в котором используются решения, предлагаемые в диссертации, с целью подтверждения достоверности и практической применимости результатов, достигнутых в ходе выполнения вышеозначенных задач.
Научная новизна
-
-
Предложен способ организации векторной памяти с использованием конвертируемых режимов адресации, который позволяет размещать в памяти матрицы и обеспечивать параллельный доступ к элементам строк или столбцов матриц без транспонирования, а также реализовать другие режимы адресации, характерные для алгоритмов цифровой обработки сигналов.
-
Предложено использовать в программируемых сопроцессорах, предназначенных для цифровой обработки сигналов, векторные вычисления с поддержкой векторов переменной длины. Это позволяет исключить внутренние циклы в программах и обеспечить детерминированное время выполнения программ.
-
Предложен способ построения планировщика выполнения векторных инструкций для сопроцессора с поддержкой векторов переменной длины, основанный на расчете длительности блокировок, используемых для разрешения зависимостей по данным в программе. Планировщик, построенный таким образом, обеспечивает высокое быстродействие сопроцессора в широком диапазоне параметров выполняемой программы (длина векторов, длина последовательностей независимых инструкций) и потребляет небольшое количество аппаратных ресурсов.
-
Предложен способ построения быстродействующего конвейерного арифметического блока, выполняющего составные вычислительные операции в действительных и комплексных числах формата с плавающей точкой, такие как умножение со сложением и вычитанием, путем различного соединения арифметических блоков, выполняющих по отдельности сложение и умножение действительных чисел того же формата. Применение такого блока обеспечивает небольшую длину конвейера при выполнении простых операций, минимальное количество обращений к памяти при выполнении сложных операций, и быструю смену типа выполняемых операций.
Практическая значимость
-
-
-
Разработана RTL-модель векторного сопроцессора для цифровой обработки сигналов, которая может быть использована в качестве сложнофунк- ционального блока при реализации СБИС класса «система на кристалле». Разработанная модель обеспечивает возможность эффективной реализации основных алгоритмов цифровой обработки сигналов (быстрое преобразование Фурье, свертка, умножение вектора на матрицу и др.) с применением чисел формата с плавающей точкой. Функционирование данной модели проверено путем выполнения на ней набора функциональных и алгоритмических тестов с использованием различных симуляторов Verilog HDL.
-
Проведен логический синтез и получена логическая структура сопроцессора с 4 вычислительными конвейерами и 96 КБ внутренней памяти данных, которая при изготовлении СБИС по технологическому процессу с проектной нормой 40 нм занимает на кристалле площадь 1,88 мм2 и может работать при тактовой частоте до 1 ГГц. Эффективность работы сопроцессора при реализации алгоритмов цифровой обработки сигналов достигает 98% и при увеличении числа вычислительных конвейеров снижается незначительно, что позволяет при необходимости получить логическую структуру сопроцессоров, имеющих в 2 или в 4 раза большую производительность.
Внедрение результатов диссертации
В ЗАО НТЦ «Модуль» проводилась ОКР «Процессор-1-Модуль» по разработке архитектуры СФ-блока NM-кластера на основе матрично-векторных процессорных ядер. В состав процессорного ядра NM-кластера входит программируемый сопроцессор векторной обработки данных в формате с плавающей точкой, в котором использовались результаты разработки модели сопроцессора М3. Применение такого сопроцессора в составе NM6407 позволяет организовать выполнение алгоритмов цифровой обработки сигналов в числах стандартного 32-битного формата с плавающей точкой с высокой производительностью - до 20 операций за такт при тактовой частоте в 1 ГГц при реализации по технологическим нормам 40 нм. В частности, данный сопроцессор позволяет выполнять быстрое преобразование Фурье размерностью в 1024 точки за 3130 процессорных тактов, что существенно превосходит существующие процессоры цифровой обработки сигналов. Сопроцессор эффективно реализует и другие функции, такие как КИХ-фильтрация и вычисление фрагментов нейросетей.
Основные положения, выносимые на защиту
-
-
-
-
Архитектура и структура масштабируемого векторного сопроцессора, предназначенного для применения в составе СБИС класса «система на кристалле» для цифровой обработки сигналов.
-
Способ организации и адресации векторной памяти с несколькими раздельно адресуемыми банками, который позволяет размещать в памяти матрицы произвольного размера и получать доступ к строкам или к столбцам матрицы без транспонирования, а также упрощать реализацию нематричных алгоритмов цифровой обработки сигналов на векторных процессорах.
-
Способ построения планировщика вычислений для процессора с поддержкой векторов переменной длины. Применение векторов переменной длины позволяет упростить программы и сократить объем кода, требуемый для реализации основных алгоритмов цифровой обработки сигналов по сравнению с процессорами, использующими вектора фиксированной длины, а также обеспечивает детерминированное время выполнения программ.
-
Структура многофункционального векторного вычислительного блока, производящего операции с действительными и комплексными числами при помощи изменения порядка соединения вычислительных блоков.
Апробация работы
Основные результаты диссертации докладывались и обсуждались на Всероссийских научно-технических конференциях «Проблемы разработки перспективных микро- и наноэлектронных систем» (Москва, 2010, 2012), 19- й Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика - 2012» (Москва, МИЭТ, 2012), Научных сессиях НИЯУ МИФИ (Москва, 2008-2012),
По результатам диссертации опубликовано 6 статей (из них 4 - в изданиях, входящих в Перечень периодических изданий, рекомендованных ВАК РФ), 8 тезисов докладов.
Достоверность результатов
Достоверность представленных в диссертации данных о производительности разработанных моделей сопроцессоров подтверждается путем поведенческой симуляции данных моделей при выполнении тестовых программ, включающих реализации алгоритмов ЦОС, с проверкой корректности результатов работы этих программ. Возможность аппаратной реализации сопроцессоров М1 и М3 подтверждается путем логического синтеза их RTL- моделей с использованием проверенных современных средств (Synopsys Design Compiler, Xilinx XST) и поведенческой симуляцией моделей, полученных в результате такого синтеза.
Структура и объем диссертации
Диссертация состоит из введения, 4 глав, заключения, списка литературы, включающего 131 наименование, и 3 приложений, содержащих исходные тексты реализации различных алгоритмов БПФ и акт о внедрении результатов диссертационной работы. Содержание диссертации изложено на 154 страницах машинописного текста, включая 36 рисунков и 23 таблицы.
Архитектура процессоров с поддержкой явного параллелизма на уровне инструкций (VLIW)
Для обработки сигналов часто применяются специализированные процессоры, позволяющие реализовать типичные алгоритмы с минимальными издержками, используя вычислительные ресурсы устройства близко к их максимальным возможностям. Такие процессоры называются ЦСП (Цифровой Сигнальный Процессор). Большинство ЦСП имеют характерные особенности архитектуры [13], позволяющие им эффективно выполнять алгоритмы цифровой обработки сигналов, отличающиеся высокой плотностью вычислений и обилием циклов.
1) Поддержка операции умножения с накоплением (Multiply-Accumulate, или MAC), которая обычно выполняется за один такт. Эта операция очень полезна при реализации алгоритмов ЦОС [14], которые включают скалярное произведение векторов, таких как фильтры с конечной импульсной характеристикой (КИХ-фильтры), корреляция и дискретное преобразование Фурье (ДПФ). Чтобы обеспечить выполнение операции МАС за один такт, ЦСП используют специальные аппаратные блоки, совмещающие умножитель, сумматор и накопительный регистр (аккумулятор). Для того чтобы последовательность таких операций можно было выполнять без переполнения, регистр-аккумулятор содержит несколько дополнительных старших разрядов (например, 8).
2) Возможность выполнять несколько операций доступа к памяти каждый такт. Это позволяет процессору производить выборку инструкции одновременно с загрузкой операндов и выгрузкой результатов предыдущих инструкций. Например, при реализации КИХ-фильтра большинство ЦСП могут выполнять операцию MAC одновременно с загрузкой отсчета и коэффициента для следующей операции MAC. Организация доступа к нескольким значениям в памяти обычно подвержена существенным ограничениям: например, все или почти все операнды должны находиться во внутренней памяти процессора, причем в разных банках. Выборка инструкций производится из отдельной па мяти программы, имеющей свое адресное пространство, т.е. используется гарвардская или расширенная гарвардская архитектура. Это явно отражено в названии одного из самых высокопроизводительных семейств ЦОС - SHARC фирмы Analog Devices (расшифровывается как Super Harvard Architecture).
3) Специальные режимы адресации памяти и блоки генерации адресов. Типичным режимом адресации является косвенная регистровая адресация с постинкрементом, т.е. содержимое адресного регистра увеличивается после выполнения инструкции обращения к памяти. Такая адресация полезна при последовательном доступе к элементам векторов (т.е. массивов) данных, расположенных в памяти. Помимо простой адресации с инкрементом, бывают и другие специализированные режимы: адресация по модулю, когда увеличение адресного регистра происходит по заданному модулю - этот режим применяется для реализации циркулярных буферов; адресация с бит-реверсом, которая позволяет повысить производительность некоторых алгоритмов быстрого преобразования Фурье. Помимо режимов генерации адреса для одной инструкции, ЦСП поддерживают режим прямого доступа к памяти (Direct Memory Access, DMA), который позволяет передавать блоки данных между областями памяти или между памятью и внешними устройствами без непосредственного участия процессора, освобождая его для выполнения других задач.
4) Аппаратная реализация циклов. Обычно предоставляются специальные инструкции, позволяющие организовать цикл со счетчиком (цикл for), не тратя на это дополнительных тактов. В отличие от ЦСП, при реализации циклов на процессорах общего назначения необходимо на каждой итерации цикла явно изменить значение счетчика, сравнить его с конечным значением, и если таковое не достигнуто, производить условный переход на начало цикла. Часто применяются инструкции, объединяющие эти операции. В зависимости от конкретной архитектуры, на организацию цикла уходит от 1 до 3 инструкций на каждой итерации цикла, а операции условного перехода негативно отражаются на производительности конвейерных процессоров, не использующих предсказание ветвлений и спекулятивное выполнение [15, 16].
5) Поддержка выполнения нескольких операций за такт. Большинство процессоров предоставляют возможность параллельной обработки коротких (до 8 элементов) векторов данных при помощи инструкций, выполняющих одну и ту же операцию над каждой парой или тройкой элементов этих векторов, то есть используют архитектуру SIMD (Single Instruction, Multiple Data). Некоторые высокопроизводительные ЦСП позволяют выполнять несколько разнородных операций над несвязанными данными каждый такт; такая архитектура называется VLIW (Very Long Instruction Word), потому что в каждой инструкции необходимо закодировать все выполняемые операции вместе с их операндами, что приводит к кратному увеличению длины слова инструкции.
6) Предсказуемость времени выполнения программы. Поскольку задачи ЦОС часто выполняются в условиях реального времени, эта особенность очень важна. В современных процессорах семейства х86 микроархитектура процессора радикально отличается от видимой программисту архитектуры [17], и программа сначала подвергается трансформации внутри процессора, а затем выполняется уже новая программа, которая только функционально эквивалентна исходной. К тому же, точное количество вычислительных блоков разных типов может быть неизвестно, а доступ к памяти происходит через систему кэшей, которые вносят неопределенные задержки. Эти особенности приводят к тому, что единственным способом получить сведения о производительности на «закрытых» процессорах является измерение времени выполнения конкретной программы. В отличие от х86, предсказуемость времени выполнения программ на ЦСП достигается благодаря относительной простоте и открытости микроархитектуры (внутреннего устройства), а также прямому управлению системой памяти.
Модель сопроцессора Ml с поддержкой многопоточной модели исполнения
Сложность реализации таких операций на параллельных машинах зависит, в основном, от расположения элементов в матрице: если элементы столбцов матрицы расположены в памяти непоследовательно, то могут возникнуть проблемы с загрузкой столбцов матрицы в векторные регистры. Когда загрузка данных организована, дальнейшая реализация достаточно проста и сводится к вычислению множества независимых скалярных произведений. Оптимизация алгоритмов 1 и 2 уровней на GPU описана в работе [95] и ряде других.
Уровень 3 (матрично-матричные операции, кубическая сложность). Основной операцией этого класса является умножение плотных матриц общего вида - GEMM (General Matrix Multiply). Эффективная реализация GEMM часто является нетривиальной задачей, т.к. необходимо задействовать систему памяти вычислительного устройства эффективно, чтобы производительность по возможности была ограничена вычислениями, а не доступом к памяти, как это обычно бывает с алгоритмами 1 и 2 уровней. Этим проблемам посвящено множество работ [96], но они представляют наибольший интерес в контексте научных вычислений, а в ЦОС матричное умножение если и применяется, то только над матрицами небольших размеров.
Результат работы фильтра с конечной импульсной характеристикой (КИХ), обладающего весовыми коэффициентами w и обрабатывающего входной сигнал х, определяется сверткой [97]: {х w)k=yk = ) xnWk_n (8) Корреляция двух сигналов х и w (дискретная кросс-корреляция) определяется выражением: (ас w)k = ук = ) xnwk+n (9) Как видно из выражений (8) и (9), свертка и корреляция - очень похожие операции, причем корреляция может быть выражена через свертку и наоборот, и поэтому в данном разделе они рассматриваются вместе.
Для обычных, т.е. скалярных, ЦСП свертка часто реализуется так, что программа выдает отсчеты выходного сигнала в непрерывном режиме, по мере поступления входных отсчетов вектора х, который в принципе может быть бесконечным. Отсчеты вектора х складываются в кольцевой буфер такой же размерности, как вектор w. При поступлении нового отсчета вектора х удаляется самый старый хранящийся отсчет, и производится расчет скалярного произведения вектора w и содержимого кольцевого буфера. Для этого удобно применять аппаратную организацию циклов, присущую ЦСП, а также специальный режим адресации кольцевых буферов и инструкцию умножения с накоплением. Из-за этих особенностей архитектуры ЦСП часто выполняют расчет свертки, не тратя дополнительных тактов на организацию цикла, что позволяет получить одинаковую производительность независимо от размерности векторов х и м . Поэтому производительность свертки часто представляется в виде количества тактов на входной отсчет [98], возможно, с указанием накладных расходов на запуск программы [99], что позволяет легко рассчитать время выполнения программы.
Вычислительная сложность свертки и корреляции является квадратичной: количество операций умножения с накоплением равняется произведению размерностей векторов х и w. При больших размерах векторов время выполнения прямого алгоритма может стать недопустимо большим, и для его сокращения применяют т.н. быструю свертку, т.е. используют теорему о свертке: Т{х w] = Т{х] X T{w] (10) x w = T-1{T{x}xT{w}} (11)
Теорема о свертке (10) гласит, что свертка двух сигналов во временной области соответствует произведению этих же сигналов в частотной области. То есть, операция с квадратичной сложностью может быть заменена (11) на три БПФ, которые обычно имеют линейно-логарифмическую сложность, и поэлементное умножение двух векторов, которое имеет линейную сложность [100]. Одно из БПФ можно исключить из рассмотрения, если ядро свертки (вектор w) является постоянным — соответственно, и его спектр также является постоянным.
Однако быстрая свертка не лишена недостатков. Во-первых, таким образом нельзя производить потоковую фильтрацию, т.е. выдавать выходные отсчеты по мере поступления входных отсчетов. Необходимо накапливать входные отсчеты в некий буфер и при его заполнении производить блочную обработку. Во-вторых, быстрая свертка на самом деле эквивалентна циклической свертке, а не линейной - это связано со свойствами дискретного преобразования Фурье [101]. Для того чтобы получить линейную свертку, требуется увеличить размерность исходных векторов до размерности ожидаемого результата, добавив к ним нулей или фрагментов соседних блоков.
При реализации на векторных процессорах без аппаратной поддержки операции скалярного произведения векторов свертка носит блочный характер даже при прямой реализации, т.е. без БПФ. Это связано с тем, что расчет значения одного выходного отсчета носит последовательный характер, т.е. является серией операций умножения с накоплением, каждая из которых использует результат предыдущей. Поэтому для задействования векторных вычислений приходится обрабатывать несколько выходных отсчетов в одной векторной операции. Конкретный способ векторизации зависит от того, какие способы адресации памяти поддерживает используемый процессор. Если специальных режимов адресации или сдвига векторных регистров нет, то наиболее вероятный вариант реализации - прямая блочная свертка, описанная в работе [101]. Представим операцию свертки (8) в виде матричного выражения:
Реализация БПФ и свертки для сопроцессора М2 с применением конвертируемой адресации регистров
Таким образом, при увеличении числа каналов (NL) в 4 раза, количество логических ячеек, необходимых для реализации блока LSU, возрастает в 12 раз, а максимальная тактовая частота снижается на 38%.
Данные по времени выполнения основных тестов на вариантах модели Ml с 4, 8 и 16 конвейерами приведены в табл. 2.3. Как видно из приведенных данных, при увеличении числа конвейеров ускоряется только выполнение БПФ по алгоритму Cooleyukey (которое во многих случаях работает медленнее, чем двумерное БПФ), а также свертка и умножение вектора на матрицу больших размеров. Наблюдается корреляция между средним числом активных потоков команд и ускорением выполнения теста: если в среднем активно около 64 потоков, то обеспечивается ускорение на 60-70% при переходе от 4 к 8 конвейерам; если активно меньшее число потоков, то ускорение практически отсутствует.
Отсутствие ускорения тестов, использующих небольшое число потоков, означает, что их производительность ограничена латентностью инструкций. В самом деле, использование 32 потоков означает 8 активных варпов при NL = 4, что достаточно для покрытия латентности вычислительных инструкций при глубине конвейера в 7 стадий. При NL = 8, 32 потока соответствуют 4 варпам, что достаточно только для эффективной загрузки целочисленного конвейера, имеющего 4 стадии. При NL = 16, 32 потока соответствуют всего 2 варпам, т.е. такая задача не может работать эффективно ни при какой программе. Задачи большего размера (с числом потоков более 32) могут работать эффективно на сопроцессорах архитектуры Ml с большим числом стадий конвейера, но они реже используются в цифровой обработке сигналов.
Алгоритм Размер задачи Активно потоков NL = 4 NL = 8 NL= Загрузка FPU Кол-во тактов Кол-во тактов Ускорение отн. NL=4 Кол-во Ускорение тактов отн. NL=8
При вычислении БПФ по алгоритму двумерного разложения для небольших векторов (менее 1024 точек) модель Ml, даже в версии с 4 конвейерами, работает очень неэффективно. Это связано с тем, что каждая инструкция выполняется только тогда, когда предыдущая инструкция из того же варпа завершена, т.е. вышла из конвейера. Такое планирование выполнения инструкций эффективно работает для программ, которые запускают много варпов (8 и более - по числу стадий конвейера), но не обеспечивает ускорение выполнения программ, запускающих мало варпов. Так, БПФ-64 использует всего 8 потоков, что соответствует 2 варпам при NL = 4, или 1 варпу при NL = 8. Скорость выполнения такой программы ограничена латентностью вычислений, что подтверждается тем фактом, что не наблюдается ускорения ее выполнения при переходе на более широкий вариант сопроцессора. Этот недостаток (невозможность эффективного использования конвейера при малом числе активных варпов) учтен при проектировании сопроцессоров М2 (см. раздел 2.3) и МЗ (см. главу 4), что привело к значительному увеличению скорости реализации этого алгоритма БПФ.
Для оценки влияния глубины конвейера (латентности инструкций) на производительность модели сопроцессора Ml, была проведена серия экспериментов. К RTL-модели сопроцессора была подключена программная модель блоков FPU, которая под 53 держивает задание числа стадий конвейера. Все основные тесты были выполнены при значениях глубины конвейера FPU от 1 до 14 стадий. Результаты экспериментов представлены на рис. 2.9. Видно, что время выполнения большинства тестов линейно возрастает с увеличением числа стадий конвейера. Коэффициент линейной зависимости напрямую связан с числом потоков, которое использует программа: чем меньше потоков, тем быстрее растет время выполнения с увеличением числа стадий. От самой программы зависит только средняя длина конвейера используемых инструкций: например, если все инструкции обрабатываются блоком ALU, то от глубины конвейера FPU производительность такой программы зависеть не будет.
Графики на рис. 2.9 показывают также замедление выполнения некоторых тестов при уменьшении глубины конвейера FPU с двух стадий до одной. Это связано с функционированием блока завершения инструкций. Оптимальное быстродействие достигается, если инструкциям, выходящим из самого длинного конвейера, давать наибольший приоритет, и этот блок настроен на следующий порядок приоритетов: сначала FPU, потом LSU, и последний — ALU. При уменьшении глубины конвейера FPU до 1 стадии он становится короче остальных, и оптимальное функционирование конвейера нарушается. Изменение порядка приоритетов на LSU, ALU, FPU устраняет данное замедление.
При выборе числа стадий конвейера для реализации следует учитывать, что реальная производительность зависит не только от числа тактов, затраченных на выполнение программы, но и от тактовой частоты. Поскольку с уменьшением числа стадий тактовая частота уменьшается из-за возрастания задержек в комбинационных схемах, а с увеличением числа стадий уменьшается эффективность работы сопроцессора, существует некоторое промежуточное значение числа стадий, при котором достигается наибольшая производительность. В работе [115] проведены исследования производительности ядра ЦСП от числа стадий конвейера с учетом изменения тактовой частоты.
Реализация БПФ по алгоритму двумерного разложения
Единственной из программ, рассмотренных в главе 2, которая приводит к появлению конфликтов банков при доступе в разделяемую память, является реализация БПФ по алгоритму Cooleyukey, остальные программы адресуют разделяемую память в полностью параллельном режиме. Учитывая то, что реализация БПФ по алгоритму двумерного разложения обеспечивает более высокую производительность и не приводит к появлению конфликтов банков, можно сделать вывод, что для реализации рассматриваемых алгоритмов ЦОС поддержка доступа в разделяемую память при наличии конфликтов банков является необязательной. Исключение блока определения конфликтов банков позволит значительно упростить сопроцессор (см. раздел 2.2.3). Однако наличие такого блока является необходимым для корректной реализации операции косвенной векторной адресации памяти, следовательно, исключение такого блока приведет к необходимости выбора другой модели исполнения, не использующей такую адресацию.
Для реализации рассматриваемых алгоритмов ЦОС необходимо реализовать возможность выполнения следующих операций: 1) Транспонирование матриц произвольного размера, что необходимо для реализации БПФ по алгоритму двумерного разложения. 2) Обращение к векторной памяти по некратному смещению, которое необходимо для реализации свертки. 3) Использование скалярных значений в векторных операциях.
Для решения этой проблемы предлагается использовать векторную память с несколькими банками и с поддержкой специализированных режимов адресации. Такая память автоматически генерирует множество необходимых адресов при поступлении одного запроса в соответствии с заданным режимом адресации, что дает возможность гарантировать отсутствие конфликтов банков, а также упростить схемы коммутации банков и вычислительных конвейеров сопроцессора.
Для оценки сложности и эффективности реализации конвертируемой адресации памяти в модель сопроцессора М2 (см. раздел 2.3) была добавлена поддержка адресации регистровой памяти с использованием различных режимов. Переключение режима адресации производится отдельно для каждой страницы регистров (А, В, С или D) с помощью инструкции REMAP (см. табл. 2.4). Поддерживаются следующие режимы адресации:
1) Простой режим, показанный на рис. 2.11 (стр. 56). Сквозной адрес в странице регистров вычисляется как «NL (номер_регистра + номер_варпа чис-ло_регистров_на_варп) + номер_конвейера». Под сквозным адресом здесь понимается адрес, который увеличивается на единицу при переходе от одного банка к следующему и от последнего банка к следующему значению в первом банке.
2) Режим с заданным шагом. При использовании этого режима сквозной адрес в странице регистров вычисляется как «шаг номер__регистра + номер_потока». Этот режим позволяет транспонировать размещенную в регистрах матрицу (если шаг = число столбцов матрицы + 1), а также читать и записывать данные для удобной реализации свертки (если шаг = 1).
3) Транспонированный режим. При использовании этого режима сквозной адрес в странице регистров вычисляется как «шаг номерпотока + номер_регистра». Этот режим дополняет режим с заданным шагом при реализации транспонирования матрицы. На значение шага накладывается ограничение: шаг должен быть равен NL-+ 1, где к — любое целое положительное число.
Реализация различных режимов адресации показана на рис. 3.. В ячейках памяти записано, какому потоку (Т) и регистру (А) соответствует данная ячейка. Регистры потока ТО во всех режимах выделены цветом. Следует отметить, что при использовании режима с заданным шагом или транспонированного режима в памяти остаются неиспользуемые места. Простой режим, 256 регистров на поток
Различные режимы адресации регистров сопроцессора М2 3.1.2. Реализация БПФ и свертки для сопроцессора М2 с применением конвертируемой адресации регистров
Применение конвертируемых режимов адресации (КРА) позволяет ускорить реализацию БПФ по алгоритму двумерного разложения и уменьшить объем ее кода [117]. Это связано с тем, что для выполнения промежуточного транспонирования матрицы данных не нужно использовать разделяемую память - вместо этого используется одна инструкция REMAP. Для оценки влияния конвертируемых режимов адресации на время выполнения БПФ разработана программа вычисления БПФ-256 по такому упрощенному алгоритму. Сравнительные результаты, полученные при выполнении этой программы, приведены в табл. 3.1.
Из приведенных данных видно, что количество инструкций, использующих LSU, существенно снижается, а эффективность использования FPU возрастает. Вместе с тем снижается число инструкций, использующих ALU, т.к отсутствует необходимость вычислять адреса для транспонирования, но число этих инструкций очень мало, и они не оказывают значительного влияния на время выполнения программы. В целом, производительность сопроцессора при реализации этого алгоритма повышается на 7-11% и ограничивается пропускной способностью FPU, для которого число выполняемых инструкций не изменилось. Режим адресации с заданным шагом можно также использовать для реализации свертки (не блочной), если установить шаг равным 1. На странице памяти с такой адресацией можно организовать векторный регистр, в котором накапливается результат, и смещать базовый адрес страницы после нескольких операций умножения с накоплением. Недостатком такого способа реализации является необходимость барьерной синхронизации после каждой инструкции, работающей с такой страницей. Это связано с тем, что разные варпы могут обмениваться данными, адресуя одни и те же ячейки памяти, выполняющие функции векторных регистров, а для обеспечения корректной работы при обмене данными в многопоточной среде необходима синхронизация или организация атомарного доступа. Производительность такой реализации свертки и ее сравнение с блочной сверткой представлено в табл. 3.2.
Похожие диссертации на Высокопроизводительные сопроцессоры для параллельной обработки данных в формате с плавающей точкой в системах цифровой обработки сигналов
-
-
-
-
-
-
