close

Вход

Забыли?

вход по аккаунту

?

Аппаратная реализация кодеков Рида-Соломона на ПЛИС на основе высокоуровневых параметризованных описаний функциональных узлов

код для вставкиСкачать
ФИО соискателя: Тайлеб ур. Мазуз Незхат Шифр научной специальности: 05.13.05 - элементы и устройства вычислительной техники и систем управления Шифр диссертационного совета: Д 212.157.16 Название организации: Московский энергетический институт (техн
На правах рукописи
ТАЙЛЕБ ур. МАЗУЗ Незхат
АППАРАТНАЯ РЕАЛИЗАЦИЯ КОДЕКОВ
РИДА-СОЛОМОНА НА ПЛИС НА ОСНОВЕ
ВЫСОКОУРОВНЕВЫХ ПАРАМЕТРИЗОВАННЫХ ОПИСАНИЙ
ФУНКЦИОНАЛЬНЫХ УЗЛОВ
Специальности: 05.13.05 – Элементы и устройства вычислительной
техники и систем управления
05.13.12 – Системы автоматизации проектирования
(по отраслям)
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Москва – 2012
2
Работа
выполнена
в
Федеральном
государственном
бюджетном
образовательном
учреждении
высшего
профессионального
образования
«Национальный исследовательский университет «МЭИ» (ФГБОУ ВПО «НИУ
МЭИ») на кафедре Вычислительных машин, систем и сетей.
Научный руководитель:
кандидат технических наук, доцент
Поляков Аркадий Константинович
Официальные оппоненты:
Плоткин Арнольд Леонидович, доктор технических
наук, профессор, ЗАО «Интел А/О», руководитель
университетской программы
Смирнов Николай Алексеевич, кандидат
технических наук, профессор, ФГБОУ ВПО «МГТУ
МИРЭА», профессор кафедры Вычислительной
техники
Ведущая организация:
ФГБУН Институт проблем управления
им. В.А. Трапезникова РАН
Защита состоится 26 октября 2012 г. в 16 часов 00 минут на заседании
диссертационного совета Д 212.157.16 при ФГБОУ ВПО «НИУ МЭИ» по адресу:
111250, г. Москва, Красноказарменная улица, д. 17, ауд. Г-306.
С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «НИУ МЭИ».
Отзывы на автореферат в двух экземплярах, заверенные печатью организации,
просим направлять по адресу: 111250, г. Москва, Красноказарменная ул. д. 14,
Ученый совет МЭИ.
Автореферат разослан «___» _______________ 2012 г.
Ученый секретарь
диссертационного совета Д 212.157.16,
к.т.н., доцент
Чернов С.А.
3
Общая характеристика работы
Актуальность работы. Одним из путей повышения помехоустойчивости
систем передачи и обработки данных является использование помехоустойчивого
кодирования и в частности циклического кода Рида-Соломона (РС-код).
Реализующие его устройства (РС-кодеки — обобщенное название РС-кодеров и РСдекодеров) применяются, например, в цифровом телевидении, в спутниковой и
сотовой связи, при передаче данных по телефонным каналам, в системах хранения
информации на магнитных и оптических дисках, в оптоволоконных сетях, например,
сетях стандарта ITU-T G.709 (коротко G.709). Используемые в высокоскоростных
системах реального времени РС-кодеки представляют собой отдельные устройства,
в которых применяются различные методы повышения быстродействия:
параллелизм, конвейеризация и т.д. Проектирование РС-кодеков и реализация их в
виде CБИС или на ПЛИС достаточно сложная задача. При разработке аппаратуры
РС-кодеков с помощью современных САПР приходится находить баланс между:
• качеством проектов как объектов интеллектуальной собственности: уровнем
описания проекта (высокоуровневое/низкоуровневое), повторнопригодностью
проекта, параметризованностью (настраиваемостью на различные РС-коды и
независимость от САПР и элементной базы конкретной фирмы) их описаний;
• техническими характеристиками (аппаратными показателями) конечного
продукта, получаемого при реализации проекта «в железе»: временными (T —
максимальной тактовой частотой работы устройства, Л — латентностью
определяемой как время в тактах от поступления символа на вход кодека до
его выхода из кодека, П — пропускной способностью, числом символов РСкода, обрабатываемых в заданную единицу времени, например в секунду), С
— сложностью аппаратуры (количеством триггеров, логических элементов LUT и блоков памяти, используемых в микросхеме ПЛИС для реализации
данного
устройства),
мощностными
(рассеиваемой
мощностью),
надежностными и др.;
• экономическими характеристиками, которые определяются временем и
трудоёмкостью процесса проектирования, требованиями к квалификации
проектировщиков, к инструментальным ЭВМ, САПР и т.п.
Возможны разные подходы к проектированию РС-кодеков. Первый путьиспользовать готовые IP-ядра. Можно приобрести у сторонних фирм проект РСкодека в виде объекта интеллектуальной собственности (IP-ядра) или создавать его с
помощью генераторов ядер современных САПР. Преимущество этого пути — резкое
уменьшение сроков и трудоёмкости процесса проектирования. Недостаток —
закрытость для пользователя описания IP-ядра и невозможность его изменения.
Отметим ещё, что в Интернете имеется несколько открытых и бесплатных проектов
РС-кодеков в виде высокоуровневых HDL–описаний, но их качество невысокое и
такие проекты в основной массе не параметризованны (рассчитаны только на
определенный РС-код). Второй путь — собственная разработка HDL-описания
4
проекта. Этот путь позволяет приобрести опыт коллективу проектировщиков и
получить повторнопригодные описания. Недостатки такого подхода — высокая
трудоёмкость и большие сроки проектирования, повышенные требования к
квалификации проектировщиков и т.п. В этом случае важен выбор уровня HDLописаний проектов, выбор методологии и технологии проектирования, наличие
наработок в виде наборов HDL-описаний типовых функциональных узлов и блоков
РС-кодеков. Кроме того, помимо разработки HDL-описаний самих РС-кодеков
больших усилий требует расчёт параметров настройки, используемых в HDLописаниях блоков РС-кодеков и подготовка эталонных данных, используемых при
верификации проектов методом имитационного моделирования.
В последнее время отмечается спрос на многоканальные РС-кодеки (Multichannel codecs). Например, вариант OTU-2 международного стандарта передачи
данных в оптоволоконных сетях ITU-T G.709, работающих со скоростью 10.709
Гбит/с предполагает в канале передачу с перекрытием 16-ти кодовых слов.
Соответственно стоит вопрос о создании соответствующих РС-кодеков, в
организации которых актуальные вопросы параллелизма, конвейеризации и
временного мультиплексирования.
Учитывая вышесказанное, представляются актуальной задача анализа
способов организации РС-кодеков, создание методики проектирования таких
устройств на основе высокоуровневых параметризованных HDL-описаний их
типовых функциональных узлов и блоков.
Основная цель работы — разработка средств проектирования РС-кодеков на
базе ПЛИС в виде подмножества высокоуровневых параметризованных HDLописаний типовых функциональных узлов и блоков РС-кодеков, а также
практическая проверка их эффективности на примере проекта многоканального РСкодека для оптоволоконных сетей связи стандарта G.709.
В число задач, которые были поставлены и решены в работе вошли:
1. исследование и анализ алгоритмов основных арифметических операций в
полях Галуа и операций над полиномами, коэффициенты которых
принадлежат этому полю, определение состава и функций типовых
функциональных узлов, эффективно реализующих их аппаратно;
2. анализ и выбор вариантов алгоритмов типовых блоков РС-кодеков с точки
зрения оценки эффективности их аппаратной реализации;
3. исследование и анализ особенностей схемотехники ПЛИС и различных
подходов к автоматизированному проектированию устройств на ПЛИС
применительно к реализации типовых функциональных узлов и блоков РСкодеков;
4. исследование и разработка библиотеки высокоуровневых параметризованных
Verilog-описаний типовых функциональных узлов и блоков РС-кодеков,
учитывающих специфику операций в полях Галуа и особенности элементной
базы ПЛИС;
5
5. разработка библиотеки MATLAB-функций, предназначенных для генерации
значений параметров, используемых в HDL-описаниях узлов РС-кодеков и для
генерации эталонных значений данных, используемых при верификации HDLописаний РС-кодеков методом имитационного моделирования;
6. применение предложенных средств автоматизации проектирования и
исследование их эффективности на примере разработки проектов
одноканальных и многоканальных РС-кодеков с высокой пропускной
способностью применительно к системам оптоволоконной связи стандарта
G.709.
Объектом исследования являются РС-кодеки, их аппаратная реализация в
элементном базисе ПЛИС типа FPGA, высокоуровневые параметризованные
описания функциональных узлов и блоков РС-кодеков, методы и средства
автоматизации проектирования РС-кодеков с использованием HDL-библиотек
высокоуровневых описаний их типовых функциональных узлов и блоков.
Предметом исследования является структура и алгоритмы функционирования
РС-кодеков, их аппаратная реализация в элементном базисе ПЛИС и средства
автоматизации проектирования РС-кодеков на базе библиотек высокоуровневых
описаний типовых узлов и блоков.
Используемыми методами и средствами исследования являются: метод
имитационного
моделирования,
математический
аппарат
полей
Галуа,
помехоустойчивые коды Рида-Соломона, алгоритмы кодирования и декодирования, в
том числе алгоритмы функционирования отдельных блоков этих устройств —
Берлекэмпа-Месси и Евклида, и также формула Форнея. В качестве инструментария
применён пакет прикладных программ MATLAB, ориентированный на решение
задач математических вычислений, язык описания аппаратуры HDL Verilog, САПР
ПЛИС фирмы XILINX, САПР и пакет моделирования Questasim фирмы Mentor
Graphics.
Научная новизна диссертации заключается в:
1. исследовании и анализе различных алгоритмов выполнения арифметических
операций в поле Галуа и создании библиотек высокоуровневых
параметризованных HDL-описаний типовых функциональных узлов,
эффективно реализующих эти операции в элементном базисе ПЛИС типа
FPGA;
2. исследовании и анализе типовых алгоритмов блоков РС-кодеков, оценке
эффективности вариантов их схемной реализации и создании библиотеки
высокоуровневых параметризованных HDL-описаний типовых блоков РСкодеков, эффективно реализуемых на ПЛИС типа FPGA;
3. разработке методики автоматизированного проектирования РС кодеков на базе
расширяющегося подмножества высокоуровневых параметризованных HDLописаний типовых функциональных узлов и блоков;
4. исследовании способов организации многоканальных декодеров и создании
6
HDL-описания проекта многоканального РС-декодера эффективно аппаратно
реализуемого на ПЛИС типа FPGA. Его пропускная способность в два раза
превышает пропускную способность известных аналогов.
Достоверность выводов и рекомендаций, сформулированных в диссертации,
обусловлена корректной постановкой задач и данными, полученными в результате
имитационных и физических экспериментов на отладочных платах ML405 и SP605
фирмы XILINX.
Научные положения, выносимые на защиту:
1. способ высокой параметризации HDL-описаний
функциональных узлов и блоков РС-кодеков;
проектов
типовых
2. методика автоматизированного проектирования РС-кодеков на базе наборов
высокоуровневых
параметризованных
HDL-описаний
их
типовых
функциональных узлов и блоков;
3. подмножество высокоуровневых HDL-описаний типовых функциональных
узлов и блоков РС-кодеков, эффективно аппаратно реализуемых в логическом
базисе ПЛИС типа FPGA. Эти описания могут быть использованы не только
при разработке РС-кодеков, но и как базовые компоненты в проектах систем
обработки информации, основанных на применении полей Галуа. Библиотека
не имеет известных аналогов;
4. проект многоканального декодера для оптоволоконных сетей стандарта G.709
отличающегося от известных более высокой пропускной способностью.
Практическая значимость. Предложенная методика позволяет уменьшить его
сроки и трудоёмкость, повысить качество проектов. Эффективность разработанной
методики продемонстрирована на примере проектирования многоканального РСдекодера стандарта G.709 со скоростью передачи до 51 Гбит/с.
Показана эффективность предложенных решений путём сравнения полученных
результатов с известными аналогами. Авторский проект многоканального РСдекодера обладает более высокой пропускной способностью, чем наилучший из
известных, построенный на базе IP-ядер фирмы XILINX.
Внедрение результатов исследований. Результаты исследования используются
в учебном процессе кафедры ВМСиС МЭИ в курсах «Инженерное проектирование и
САПР». Предполагается их использовать и в курсе «Цифровая обработка сигналов».
Апробация результатов работы. Основные положения диссертации
докладывались на следующих конференциях и семинарах: научный семинар,
посвященный памяти д.т.н., профессора З.М. БЕНЕНСОНА, ВЦ РАН, 2008;
тринадцатая и четырнадцатая международная научно-техническая конференция
студентов и аспирантов МЭИ «Радиоэлектроника, электротехника и энергетика»,
МЭИ (ТУ), 2007 — 2008.
За доклад «Реализация библиотеки арифметических операций над полиномами
в поле Галуа на ПЛИС типа FPGA» в 2008 г. автор получил почетный диплом 1
степени.
7
Публикации автора по теме диссертации. Основные результаты работы,
опубликованы в 6 статьях и докладах на конференциях, в том числе одна статья
опубликована в журнале «Вестник МЭИ», входящий в перечень ВАК РФ.
Структура и объём диссертационной работы. Работа состоит из введения,
четырёх глав, заключения, списка информационных источников из 79 наименований
и 3 приложений. Основная часть работы изложена на 177 страницах машинописного
текста, содержит 70 рисунков, 27 таблиц. Общий объём диссертации 210 страниц.
Существо и логика проведенных исследований
Для определения состава и выбора алгоритмов типовых функциональных
узлов, необходимых для аппаратной реализации РС-кодеков, рассмотрены
арифметические операции в поле Галуа и варианты алгоритмов их выполнения. Эта
область, с точки зрения аппаратной реализации до настоящего времени исследована
мало. По аналогии с временами начального развития вычислительной техники, когда
например варианты алгоритмов умножения имели имена своих создателей (алгоритм
умножения Бута и др.) известны разные алгоритмы умножения в поле Галуа
(алгоритм Мастровито и др.) и если в современных ПЛИС типа FPGA имеются
встроенные блоки умножителей чисел, то появление их аналогов для полей Галуа
ожидается лишь в будущем. В работе проанализированы также известные
алгоритмы кодирования и декодирования РС-кодов (гл. 1) с точки зрения оценки
области эффективности их аппаратной реализации (задержка критического пути
схемы и количество используемых типовых узлов). На базе проведенных
исследований и с учётом специфики элементной базы ПЛИС (гл. 2), особенностей
языков описания аппаратуры и САПР ПЛИС разработаны высокоуровневых
параметризованные HDL-описания (варьируется разрядность, используется разная
аппаратная реализация и т.п.) узлов и блоков РС-кодеков. Для генерации эталонных
данных, необходимых для верификации этих описаний разработана библиотека
функций на языке MATLAB. После верификации описаний типовых узлов и блоков
и синтеза в элементном базисе ПЛИС типа FPGA были исследованы их аппаратные
характеристики и определены области их эффективного использования (гл. 3) для
разных РС-кодов. Публикации по таким HDL-описаниям узлов и блоков для
проектирования РС-кодеков отсутствуют. Для проверки эффективности применения
разработанных узлов и блоков был спроектирован многоканальный РС-декодер для
высокоскоростных оптических каналов связи, по многим параметрам
превосходящий известные аналоги (гл. 4).
Содержание диссертации.
Во введении обоснован выбор темы диссертации, показана её актуальность,
определены цели, задачи и методы исследования, рассмотрены вопросы научной
новизны и практической значимости результатов диссертации, перечислены
основные положения, выносимые на защиту. Представлена структура диссертации.
В первой главе рассмотрены известные понятия из области теории полей Галуа
GF(2m), где: параметр m – число разрядов в двоичном представлении символа поля.
Представлены математические описания арифметических операций в полях Галуа
над элементами (сложения, умножения, инверсии) и над полиномами,
8
коэффициенты которых принадлежат этому полю. Рассмотрены коды РидаСоломона, рассмотрены алгоритмы кодирования и декодирования данных. РС-код
определяют параметры: (n, k, m, p(x), b, G(x)), где n=2m-1 — общее число символов в
кодовом слове, k — общее число символов в кодовом слове (t=(n-k)/2 —
максимальное число корректируемых кодом ошибок), p(x) — примитивный
полином, задающий порядок следования элементов поля, b — начальный элемент
порождающего полинома G(x). Рассмотрены известные алгоритмы кодирования и
декодирования данных с точки зрения возможности их аппаратной реализации.
Рис. 1. Структурная схема РС-кодера
Схема рис. 1 иллюстрирует аппаратную реализацию алгоритма кодирования
(РС-кодера), в которой используется множество регистров d i, применяемых в
качестве элементов памяти. Сумматоры и умножители выполняют операции в поле
Галуа. Типовые узлы в данном случае это m-разрядный умножитель, сумматор,
мультиплексор 2-1 и регистр.
В отличие от кодирования, процесс декодирования РС-кода является более
сложной задачей. Процесс декодирования делится в несколько этапов (1-5),
реализуемых соответствующими блоками рис. 2 (текст в прямоугольниках поясняет
функции блоков РС-декодера).
Рис. 2. Основные блоки типичного РС-декодера
В ходе анализа алгоритмов блоков РС-декодера и способов их аппаратной
реализации и в частности, реализации его второго блока (на рис. 2 это блок № 2
KESOLV — решение ключевого уравнения) были рассмотрены три версии
аппаратной реализации алгоритма Берлекэмпа-Месси (BM): iBM, riBM, RiBM,
алгоритм Евклида и алгоритм Питерсона-Горенштейна-Цирлера. Последний далее
не рассматривался из-за того, что его аппаратная реализация становится слишком
сложной при t — число ошибок больше 3. Получены оценки сложности схем,
9
реализующих алгоритмы в условных единицах (типовые функциональные узлы) и
оценки задержек критического пути, сделан вывод о предпочтительности
применения для высокоскоростных РС-декодеров алгоритма BM версии RiBM,
который отличается регулярностью его структуры.
Показано, что сложность аппаратуры РС-кодеков и величина задержки
критического пути в основном определяется параметрами функциональных узлов,
реализующих арифметические операции в полях Галуа: операции умножения,
инверсии и возведения в степень. К типичным последовательностям этих операций
относится умножение со сложением и запоминанием (см. рис. 1). Типичный
подблок-РС-кодеков линейка (сдвиговый регистр) из (n-k) таких узлов (см. рис. 1). В
блоке вычисления синдрома и решения ключевого уравнения (см. рис. 2) также
выделены соответствующие подблоки. Полученные теоретические оценки
количества типовых узлов и величины задержек критического пути в схемах
устройств РС-кодеков и их блоков, представлены в табл. 1. Эти оценки
экспериментально проверены в главе 3.
Таблица 1
РС-декодер
Оценка количества типовых узлов и величины задержки критического пути блоков
РС-кодека
Блок/Узел
Add
Mult
Reg
Mux
Задержка
критического пути
РС-кодер
2t
2t
2t
2
2·Tadd+Tmult+Tmux
2t
2t
2t
0
Tadd+Tmult
6t+2
6t+2
3t+1
Tadd+Tmult
⌊log 2(2t+b)⌋ +nbr1+2t+2m-3
2t-1
2t-1
max(Tinv, Tpow)
5t
max(Tinv, Tpow)
SCOMP
KESOLV(RiBM) 3t+1
FOURCH
3t-3
Итого РС-декодера 8t-2
⌊log 2(2t+b)⌋ +nbr1+12t+2m-1 10t+1
Примечание — в столбцах Add, Mult, Reg, Mux — количество узлов
(сумматоров, умножителей, регистров и мультиплексоров). Tadd Tmult, Tmux — задержки
критического пути соответствующих узлов. nbr1 — количество единиц в двоичном
представлении числа (2t+b). В зависимости от параметров РС-кода (m, t, b),
задержка РС-декодера равна Tinv=(2m-3)·Tmult или Tpow= ⌊log2 (2t +b)⌋+nbr1−1 ·Tmult..
Во второй главе рассмотрены ПЛИС FPGA фирмы XILINX. Дано описание
основных программируемых (настраиваемых пользователем) блоков трёх семейств
ПЛИС: VIRTEX-4, VIRTEX-6, SPARTAN-6. Представлены этапы проектирования
устройств с применением системы автоматизированного проектирования САПР
ПЛИС. Обоснован выбор HDL — язык Verilog для разработки проектов РС-кодеков.
Показана эффективность использования высокоуровневых описаний проектов и
использования элементов блочной памяти ПЛИС типа FPGA для табличной
реализации функций. Отмечается важность этапа функциональной верификации и
построения проверочных тестов. Это объясняет целесообразность разработки
библиотеки MATLAB-функций, предназначенных для расчёта эталонных данных,
10
используемых при верификации проектов методом моделирования.
Для оценки влияния способа проектирования и стиля HDL-описаний проектов
на качество получаемых при синтезе схем приведен эксперимент с проектами
относительно простого устройства — трёхвходового многоразрядного сумматора.
Предложены и исследованы 7 вариантов его HDL-описаний. Эксперимент показал
недостатки низкоуровневого описания (варианты 1-2 — схемы на основе элементов
серии КР1533), плюсы и минусы поведенческого описания (варианты 3-5) и
описания слишком привязанного к элементной базе (варианты 6-7) специального
типа ПЛИС. Вариант 5 представляет поведенческое описание по формуле (Cout,
S)=A+B+C+Cin, где: A, B, C — входные сигналы, Cin — входной перенос, S —
сумма, Cout — выходной перенос. Вариант 6 использует описание варианта 5 и, при
синтезе которого в САПР активизирована опция «USE DSP48» с целю
использования модули XtremeDSP48 — аппаратное ядро, встроенное в VIRTEX-4
вместо сумматора, реализованного на основе LUT. Вариант 7 проекта сумматора
использует экземпляр модуля XtremeDSP48, который реализует операцию сложения
в виде двух-каскадного конвейера (Cout, S)=DSP48(A, B, C, Cin). Результаты
реализации семи проектов трёхвходового многоразрядного сумматора на ПЛИС типа
FPGA на микросхеме VIRTEX-4FX12-10fft668, представлены в табл. 2.
Таблица 2
Результаты реализации семи проектов многоразрядного сумматора на ПЛИС
Вар.1 Вар. 2 Вар. 3 Вар. 4 Вар. 5 Вар. 6 Вар. 7
Количество LUT
Количество модулей XtremeDSP48
Задержка (нс)
114
185
192
192
49
0
0
0
0
0
0
0
3
2
13.16
16.41
3.02
32.25
27.80 154.55 49.01
Примечание — LUT (Look-Up Table) это простейший логический элемент в
ПЛИС, реализующий любую логическую функцию (с 4 или 6 входами и выходами),
задаваемую при программировании ПЛИС.
По данным табл. 2 вариант 7 имеет наименьшую задержку. Однако более
общим и эффективным решением является высокоуровневое поведенческое
описание варианта 5, так как путём простого указания синтезатору о
целесообразности применения модуля XtremeDSP48 разработчик позволяет
использовать этот блок (вариант 6) и уменьшить количество LUT.
Анализ результатов позволяет предложить следующие рекомендации:
• для проектов, требующих максимального быстродействия, нужно эффективно
использовать особенности конкретной микросхемы ПЛИС и САПР. Однако
переносимость проектов на другие типы ПЛИС при этом низкая;
• если требования к быстродействию проектируемых устройств не столь
критичны, то лучше использовать высокоуровневые поведенческие описания
(вариант 5). Мобильность проектов при этом высокая;
• если перед проектировщиком стоит требование максимального использования
11
старой документации в виде низкоуровневых описаний устройств на
микросхемах СИС, то при римейке проекта на новой элементной базе ПЛИС
следует заранее учесть возможность существенного снижения его
схемотехнических показателей по сравнению с вариантом поведенческого
описания.
Эти положения использовались при проектировании HDL-описаний типовых
узлов и блоков РС-кодеков.
В третьей главе отмечено, что проектирование РС-кодеков традиционным
способом (узлы разрабатываются каждый раз заново под заданный РС-код и т.д.)
уже не решает проблему массового создания устройств данного класса в
приемлемые сроки и с необходимым уровнем качества. Целесообразно иметь
библиотеку параметризованных (с параметрами: n, k, m, b, p(x), G(x)) HDL-описаний
типовых функциональных узлов, блоков и подблоков данного класса устройств.
Определим следующие параметры проектов РС-кодеков:
1. множество внешних входных параметров, которые задаются в начале
проектирования: a1 — диапазон параметров РС-кодов (n, k, m, b, p(x), G(x)), a2
— диапазон семейств ПЛИС, a3 — целевые показатели разработанного
устройства;
2. множество внутренних, варьируемых параметров определяет способы
аппаратной реализации узлов арифметических операций в полях Галуа, это
параметры блоков и подблоков РС-кодека, и общесистемные параметры. Их
общее число 9 (от x1 до x9);
3. множество внешних выходных параметров, определяющих качество
полученного проекта РС-кодека (см. стр. 3). Достижение высоких внешних
информационных показателей проектов РС-кодеков является одной из главных
целей предлагаемой методики их проектирования.
Итак проект РС-кодека характеризуется:
– множеством внешних входных параметров A = {a1, a2, a3};
– множеством внутренних варьируемых параметров X = {x1, ..., x9};
– множеством внешних выходных параметров Y = { y1∪y 2∪y 3 } таких, что:
y j ∈Y
(1)
yj = Fj (a1, a2, a3, x1, ..., x9)
где Fj – некоторые, априори неизвестные функции, показывающие зависимость
внешних выходных параметров от внешних входных и внутренних параметров РСкодека.
– критерий качества проекта z:
z = G(a1, a2, a3, x1, ..., x9)
(2)
где G — априори неизвестная функция качества, показывающая связь z с
внешними входными и внутренними параметрами.
12
Задача проектирования формулируется так: для заданного диапазона
значений входных параметров a1, a2, a3 и заданных ограничений на значения
внешних выходных параметров Y необходимо найти такие значения внутренних
параметров x1, ..., x9 при которых будут выполнены следующие требования:
z = G(a1, a2, a3, x1, ..., x9) = extrem G(a1, a2, a3, x1, ..., x9) x i ∈X i и
yj = Fj(a1, a2, a3, x1, ..., x9) ≤ yj*, y j ∈Y
(3)
Уточненную постановку задачи можно варьировать в зависимости от цели
проектирования. Здесь в качестве примера можно привести две разные цели:
1. разработка минимальных по затратам аппаратуры РС-кодеков с реализацией
проекта на самых простых и дешевых микросхемах ПЛИС;
2. проектирование быстродействующих РС-кодеков. В этом случае решения
должны быть направлены на получение, например, наивысшей максимальной
пропускной способности устройства. Достижение этой цели во многом
определяется алгоритмическими и проектными решениями, выбором
быстродействующих узлов и блоков из HDL-библиотеки, а также дорогих
высокоскоростных ПЛИС.
Предлагаемая методика проектирования РС-кодеков рекомендует
проектировщикам создавать высокоуровневые, параметризованные (параметры: n, k,
m, b, p(x), G(x)), повторнопригодные и модульные HDL-описания проектов РСкодеков с максимальным использованием высокоуровневых параметризованных
HDL-описаний типовых функциональных узлов и блоков. В числе
инструментальных средств поддержки этой методики — библиотека HDL-описаний
типовых узлов и блоков РС-кодеков (коротко HDL-библиотека) и библиотека
MATLAB-функций (коротко MATLAB-библиотека) для их верификации. В свою
очередь, HDL-библиотека строится по таким же принципам и включает в себя
подмножество параметризованных (параметры m, p(x)) описаний функциональных
узлов, выполняющих арифметические операции в поле Галуа (в том числе операции
над полиномами с коэффициентами, принадлежащими этому полю) и
параметризованных описаний типовых подблоков и блоков РС-кодеков (например
узлов, представленных на рис. 1) или блоков SCOMP, KESOLV, FOURCH РСдекодеров, включающих не только операционные, но и управляющие подблоки (см.
рис. 2). MATLAB-библиотека применяется для вычисления параметров,
используемых в HDL-описаниях блоков РС-кодеков и вычисления промежуточных
результатов-эталонов, используемых при верификации HDL-описаний РС-кодеков.
Для автоматизации работы с MATLAB-библиотекой разработан графический
интерфейс, который упрощает процесс её использования.
Принцип высокой параметризации HDL-описаний функциональных узлов
и блоков предполагает возможность настройки использующих их проектов не
только на разные РС-коды но и на разные схемотехнические решения. В
настоящее время при проектировании с применением HDL и САПР в структурных
HDL-описаниях проектов обычно используются параметризованные библиотеки
типовых N-разрядных функциональных узлов (компонентов, макрофункций), в
13
которых N – параметр настройки, значение которого по умолчанию задано в HDLописании узла, а нестандартные указываются в конкретизациях компонентов. В
HDL-описаниях типовых узлов и блоков РС-кодеков число таких параметров может
быть увеличено, за счёт чего достигается простота настройки проекта на разные РСкоды. Например для узла умножения это параметры m и p(x), определяющие поле
Галуа. Другой пример — в параметризованном описании РС-кодера набор
параметров n, k, m, b, G(x) определяет используемый РС-код.
Следующим шагом в направлении повышения уровня настраиваемости HDLописаний проектов является возможность простого изменения функции узлов и
изменения способа их аппаратной реализации (максимальное быстродействие или
минимум аппаратуры и т.п.). Например для умножителя это может быть вариант
простого, ускоренного или конвейерного способа его реализации.
В языке VHDL подобное свойство HDL-описаний обеспечивается
возможностью иметь для одного и того же объекта проекта множество архитектур.
Простой сменой в описании конфигурации (configuration) проекта одной
архитектуры узла на другую проектировщик обеспечивает изменение способа
аппаратной реализации умножителей во всем проекте РС-кодека или его части. В
языке Verilog подобное свойство HDL-описания проекта обеспечивается блоком
конфигурирования (config) путём подключения разных библиотек, содержащих
разные по способу аппаратной реализации модели одноименных узлов (модулей).
Но все эти средства предполагают одинаковые интерфейсы у разных вариантов
одноименных компонентов проекта. Ещё большую гибкость HDL-описаний
проектов можно было бы добиться при обеспечении возможности простой замены
одних компонентов на другие, отличающиеся по именам и составу портов. В ходе
решения этой задачи была обеспечена высокая параметризация описаний узлов и
блоков, являющаяся базовым элементом предложенной методики проектирования
РС-кодеков. Задача решалась с использованием средств препроцессора языка Verilog
(директивы периода компиляции) и особенностей синтезаторов САПР.
Последовательность этапов процесса автоматизированного проектирования РСдекодера и решаемые на них задачи вместе с предлагаемыми средствами их
поддержки, иллюстрируется на рис. 3 в виде IDEF-диаграммы. Каждый
прямоугольник описывает проектное действие или функцию. Номер в правом
нижнем углу прямоугольника определяет номер этапа проектирования. Левая
стрелка каждого прямоугольника указывает входные данные, правая — выходные
данные, верхняя — информация, управляющая функцией и нижняя — механизм или
ресурс используемый данной функцией. Отметим, что в прямоугольнике 2 нужно:
вычислить параметр q (параметр умножителя поля Галуа, соответствующий
коэффициентам примитивного полинома p(x) и таблицы инверсии и возведения в
степень (2t+b) элементов поля Галуа.
Для РС-кодера выполняются те же этапы проектирования, но в прямоугольнике
2 нужно вычислить параметры: q и G — коэффициенты порождающего полинома
G(x).
14
Рис. 3. IDEF-диаграмма процесса автоматизированного проектирования РС-кодеков с
использованием предлагаемой методики
На рис. 3 можно выделить следующие этапы:
1. структурный этап (прямоугольники 1-4) включает:
а. проверку параметров РС-кода (n, k, m, b) с заданным ограничением в
прямоугольнике 1, расчёт необходимых параметров и таблиц,
используемых в узлах и блоках РС-кодека и зависящих от параметров РСкода (n, k, m, b, p(x)) с помощью MATLAB-библиотеки;
б. выбор структуры РС-кодека, анализ и оценка вариантов: одноканальный,
многоканальный и т.п.;
в. разбиение проекта РС-кодека на блоки и модули по основным алгоритмам и
функциям, оценка вариантов алгоритмов с точки зрения эффективности их
аппаратной реализации, анализ возможности использования типовых узлов
и блоков РС-кодека из HDL-библиотеки для этой цели;
15
г. интеграцию типовых блоков для создания HDL-описания модуля верхнего
уровня (РС-кодека).
2. функционально-алгоритмический этап включает:
а. выбор алгоритмов нестандартных (в смысле отсутствия в HDL-библиотеке
компонентов с нужными параметрами) блоков РС-кодека;
б. реализацию нестандартного блока с использованием типовых узлов из
HDL-библиотеки;
в. верификацию и включение блока в HDL-библиотеку.
3. этап функциональной верификации проекта (прямоугольник 5).
Верификация упрощается за счёт использования в тестирующей программе
эталонных значений, полученных с помощью MATLAB-библиотеки;
4. этапы синтеза проекта и реализации в заданном проектировщиком
элементном базисе и конструктиве (прямоугольники 6-8). Эти этапы идут по
стандартной процедуре соответствующей САПР и после временного
моделирования позволяют получить файл программирования ПЛИС.
Подмножество высокоуровневых описаний типовых узлов РС-кодеков включает
специфические для РС-кодеков узлы (арифметические) и универсальные (регистры,
счётчики, мультиплексоры, компараторы и т.д.) сложные по аппаратуре и имеющие
большую задержку узлы имеют несколько вариантов описаний архитектур.
Полученные в первой главе теоретические оценки сложности аппаратных
реализаций алгоритмов отдельных блоков РС-кодека (см табл. 1) были
экспериментально проверены (см. табл. 3). В целом эксперимент подтвердил
правильность теоретических оценок.
Таблица 3
Экспериментальные оценки сложности аппаратуры и задержки критического пути
блоков РС-кодека, реализованных на ПЛИС
Блок/Узел
РС-декодер
РС-кодер
Add Mult
Reg
Mux Mem
Задержка критического пути
2t
2t
2t
2
0
2TGF_ADD+TGF_MUL+Tmux
SCOMP
2t+1
2t
4t+1
2t+4
0
TGF_ADD+TGF_MUL+ Tmux
KESOLV (RiBM)
3t+1 6t+2
6t+5
6t+4
0
TGF_ADD+TGF_MUL+ Tmux
FOURCH
3t-3
2t+6
2t
2
TGF_MUL+Tmux
2
TGF_ADD+TGF_MUL+Tmux
Итого РС-декодера
2t
8t-1 10t+2 12t+12 10t+8
В рамках оценки эффективности предложенной методики проектирования РСкодеков исследован и разработан проект одноканального РС-кодера (ENCODER_T1).
Проект описан на языке Verilog, настроен на код РС (n=255, k=239) с параметрами
m=8, p(x)=1+x+x2+x3+x4+x8, b=0, реализован с использованием САПР фирмы
XILINX. Описание проекта построено на основе модулей HDL-библиотеки. Для
оценки его схемотехнических показателей, приведёны результаты сравнения их с
16
характеристиками РС-кодера фирмы XILINX (ENCODER_X1), создаваемым
генератором IP-ядер (CoreGenerator версии 5.1) САПР фирмы XILINX (см. табл. 4).
Таблица 4
Сравнительные характеристики авторского РС-кодера ENCODER_T1 и
ENCODER_X1 фирмы XILINX
VIRTEX-4
VIRTEX-6
Параметры
ENCODER_T1
ENCODER_X1
ENCODER_T1
ENCODER_X1
Т (МГц)
343
333
405.6
441
Л (такты)
1
3
1
3
П (Мбит/с)
2.74
2.66
3.24
3.5
С (слайсы)
136
150
157
187
Видно, что проекты РС-кодеров имеют примерно равные характеристики.
В ходе оценки эффективности HDL-библиотеки разработан базовый проект
одноканального РС-декодера. Его параметризованное HDL-описание выполнено на
языке Verilog и настроено на РС-код РС (255, 239). Первая версия проекта на основе
библиотечных узлов прямой схемной интерпретации комбинационными схемами
операций возведения в степень и инверсии оказалась неэффективной. Вторая версия,
была реализована на основе имеющегося в HDL-библиотеке табличного способа
вычисления этих функций. Это позволило повысить тактовую частоту примерно в
пять раз (с 33 МГц до 152 МГц на микросхеме VIRTEX-4).
Отметим, что при создании базового проекта одноканального РС-декодера
20.5% из количества строк проекта занимают строки конкретизаций библиотечных
модулей узлов типовых арифметических операций. 72% из общего количества строк
проекта занимают строки типовых узлов и блоков (число строк типовых
арифметических операций зависит от параметра t (здесь они рассчитаны для t=1).
Таблица 5
Результаты реализации на ПЛИС проектов авторского декодера DEC_T1, DEC_X1
фирмы XILINX и DEC_IP1 фирмы IPrium
VIRTEX-4
Параметры
VIRTEX-6
SPARTAN-3ADSP
DEC_T1 DEC_X1 DEC_T1 DEC_X1 DEC_T1
DEC_X1
DEC_IP1
Т (МГц)
152
136
281.29
257.4
132
144
149
Л (такты)
286
466
286
466
286
466
/
П (Мбит/с)
1.21
1.08
2.25
2.05
1.05
1.15
1.19
С (слайсы,
память)
2632
3
755
2
907
3
249
2
3157
3
802
2
1851
/
В табл. 5 приведёны результаты сравнения аппаратных показателей базового
проекта одноканального РС-декодера с РС-декодером фирмы XILINX (DEC_X1) —
17
IP-ядром, создаваемом САПР ISE фирмы XILINX (CoreGenerator версии 7.1).
Результаты показывают, что при реализации на микросхемах VIRTEX-4 и
VIRTEX-6 DEC_T1 по максимальной тактовой частоте авторский декодер
превосходит на 9% продукт фирмы XILINX DEC_X1. Его латентность на 180 тактов
меньше, но он расходует в 3.5 раза больше ресурсов ПЛИС (общее количество
эквивалентных вентилей приблизительно равно 400000), чем продукт фирм XILINX
DEC_X1. На микросхеме SPARTAN-3ADSP (см. табл. 5) схема декодера DEC_T1 по
количеству слайсов оказалась больше (примерно в 1.7 раза), чем схема декодера
DEC_IP1 — продукт фирмы IPrium.
Исследованы зависимости максимальной тактовой частоты (T) и сложности
аппаратуры (С) базового проекта РС-декодера от параметров РС-кода. Показано, что
T и C линейно зависят от разрядности передаваемого символа (параметр m) и
количества исправляемых ошибок (параметр t). Базовый проект РС-декодера
DEC_T1 оказался не конкурентным при применении его в качестве одноканального
декодера для декодирования непрерывного потока данных т.к. при постановке задачи
проектирования базового декодера был сделан выбор быстродействующего РСдекодера с минимальной латентностью. Но тем не менее, полученные примеры
авторских проектов РС-кодеков имеют преимущества открытого кода по сравнению
с конкурентами. Соответственно авторские проекты могут модифицироваться и
быть реализованы на ПЛИС разных фирм, что использовано в проекте
многоканального декодера в гл. 4. Кроме того диапазон РС-кодов, на которые они
могут быть настроены, шире (m от 3 до 16), чем у генератора IP-ядер декодеров
фирмы XILINX (m от 3 до 12).
В четвёртой главе в качестве примера практического применения
предложенной автором методики проектирования РС-кодеков исследуются варианты
проектов многоканального РС-декодера для оптоволоконных сетей связи. Стандарт
G.709 как уже отмечалось предполагает в канале одновременную передачу с
перекрытием 16-ти кодовых слов. Соответственно стоит вопрос о создании
соответствующих 16-ти канальных РС-кодеров и декодеров. Ниже рассматриваются
особенности исследованных вариантов многоканальных декодеров.
Первый вариант (В1) — параллельная установка 16 одноканальных базовых
декодеров DEC_T1 собственной разработки. Каждый декодер DEC_T1 является
классическим одноканальным декодером. Его разработка была рассмотрена в
третьей главе. Однако такое решение представляется наихудшим, так как DEC_T1 по
аппаратным показателям в несколько раз уступает фирменному одноканальному
декодеру DEC_X1, генерируемому САПР фирмы XILINX в виде IP ядра.
Второй вариант (В2) — параллельная установка двух восьми-канальных
декодеров DEC_T2 авторской разработки. Анализ пути распространения потока
данных в базовом РС-декодере (см. рис. 2) показал, что информация проходит блоки
(SCOMP, KESOLV, FOURCH) последовательно (каждый блок — стадия конвейера),
задерживаясь в них на разное время (в SCOMP на n тактов, в KESOLV на 2t тактов и
т.д.). Естественно было предложить вариант балансировки конвейера в DEC_T2 за
счёт разделения времени (мультиплексирование) блока решения ключевого
18
уравнения KESOLV (см. рис. 2 блок № 2). Можно использовать один и тот же блок
KESOLV для обработки нескольких потоков данных. Этот вариант имеет число
каналов L, определяемое как: 2·t·L<n.
Третий вариант (В3) — параллельная установка двух восьми-канальных
авторских декодеров DEC_T3 с конвейерным блоком KESOLV. Многоканальный
декодер DEC_T3 отличается от DEC_T2 конвейерным блоком KESOLV (обозначим
его как PKESOLV), который способен принимать и обрабатывать одновременно L
каналов данных при условии, что 2·t·L<n. Конвейерный блок PKESOLV имеет m
стадий конвейеризации и реализован на основе узла конвейерного умножения в
поле Галуа (см. гл. 3). Такая структура РС-декодера способна выполнить
одновременную обработку нескольких L каналов при условии, что L ≥ m.
Четвертый вариант (В4) — параллельная установка 16 IP-ядер
одноканального РС-декодера фирмы XILINX DEC_X1. Декодер В4 построен по
параллельной схеме варианта В1 применения одноканальных декодеров с
использованием IP-ядра одноканального декодера фирмы XILINX (обозначим его
как DEC_X1), полученного с использованием генератора IP-ядер (CoreGenerator)
САПР этой фирмы для кода РС (255, 239).
Пятый вариант (В5) — параллельная установка восьми IP-ядер двухканальных РС декодеров фирмы XILINX. Декодер В5 по структуре схож с
декодерами В2 и В3, реализованными на основе многоканальных DEC_T2 и
DEC_T3. Для того, чтобы формировать РС-декодер стандарта G.709 (16 каналов),
можно использовать двухканальный декодер фирмы XILINX, обозначим его как
DEC_X2 и параллельно подключить восемь его экземпляров.
В табл. 6 даны результаты сравнения характеристик пяти вариантов В1-В5
декодера G.709, реализованных на микросхеме VITREX-6 (XC6VLX130T-1ff1156).
Таблица 6
Сравнение характеристик пяти вариантов проекта РС-декодера G.709,
реализованных на ПЛИС VIRTEX-6 (XC6VLX130T-1ff1156)
B1
B2
B3
B4
B5
Открытость кода
Да
Да
Да
Нет
Нет
Использование ПЛИС других фирм
Да
Да
Да
Нет
Нет
Пропускная способность, Гбит/с
36.005
34.56
51.2
32.94
21.37
Тактовая частота (макс.), МГц
281.29
270
400
257.4
334
466
926
Латентность в тактах
286
289 — 422 398 — 405
Количество используемых слайсов
40768
7244
4796
3984
3200
Количество блоков блочной памяти
48
48
48
32
16
Примечание — в декодерах DEC_T2 и DEC_T3 латентность зависит от номера
канала. Например, в DEC_T3 латентность первого канала 398 тактов и латентность
восьмого канала 405 тактов.
19
Можно за основу взять проект на базе IP-ядра XILINX (вариант В5) и сравнить
с ним данные остальных четырёх вариантов РС-декодера G.709 — (разделить
значения параметров каждого варианта на соответствующее ему значение параметра
варианта В5). Это даст информацию о том, что насколько варианты В1, В2, В3 и В4
по аппаратным показателям хуже или лучше фирменного варианта В5.
Таблица 7
Результаты сравнения четырёх вариантов проекта РС-декодера стандарта G.709 с
вариантом В5
B1
B2
B3
B4
B5
Пропускная способность
1.68
1.61
2.39
1.54
1
Тактовая частота (макс.)
0.84
0.80
1.2
0.77
1
Латентность
0.30
0.31 - 0.45
0.42 - 0.43
0.50
1
Количество слайсов
12.74
2.26
1.5
1.24
1
Из табл. 7 видно, что по сравнению с декодером фирмы В5 на базе IP-ядра
XILINX, разработанный автором вариант В3 проекта многоканального декодера
стандарта G.709 (количество строк кода Verilog более 4700) имеет наилучшие
характеристики по максимальной тактовой частоте. Пропускная способность
декодера В3 в два раза превосходит аналогичный параметр декодера В5.
Латентность декодера В3 в два раза меньше чем B5. Сложность схемы декодера В3
лишь 1.5 раза превосходит сложность декодера В5 фирмы XILINX. Отметим, что
при скорости 51.2 Гбит/c, декодер В3 способен работать не только с вариантом
OTU-2 стандарта G.709 (10 Гбит/с), но и с другим вариантом OTU-3 (40 Гбит/с).
Кроме того, проект РС-декодера В3 в отличие проекта В5 на базе IP-ядра фирмы
XILINX
обладает
преимуществами
открытости
кода
и
высокой
параметризованности
Verilog-описания.
Это
обеспечивает
возможность
модификации отдельных блоков проекта и его реализации на микросхемах ПЛИС
различных производителей.
Основные научные и практические результаты диссертации:
1. предложена методика автоматизированного проектирования аппаратно
реализуемых РС-кодеков на базе подмножества высокоуровневых
параметризованных HDL-описаний типовых узлов и блоков;
2. исследованы типовые алгоритмы кодирования и декодирования РС-кодов с
точки зрения эффективности их аппаратной реализации. На базе этих
исследований определен состав типовых узлов и блоков РС-кодеков, для
подмножества, которых разработаны высокоуровневые параметризованные
HDL-описания, эффективно реализуемые в элементном базисе ПЛИС типа
FPGA. Общий объём этих описаний более 4000 строк Verilog-кода;
3. для упрощения процесса верификации проектов РС-кодеков разработана
библиотека MATLAB-функций с дружественным пользовательским
интерфейсом в составе 15 модулей на языке MATLAB, общим объёмом более
20
3000 строк кода;
4. показана эффективность предложенной методики и её инструментальных
средств на примере проектирования семейства многоканальных РС-декодеров,
работающих по стандарту G.709. Высокоуровневость, параметризованность,
модульность
и
повторнопригодность
HDL-описаний
обеспечивают
возможность модификации отдельных блоков проекта и его реализации на
микросхемах ПЛИС различных производителей (общий объём HDL-описаний
проектов многоканальных декодеров — более 4700 строк кода).
В приложении A приведён пример процесса кодирования и декодирования.
В
приложении
Б
представлены
элементы
HDL-библиотеки
—
параметризованные Verilog-описания узлов, реализующих арифметических
операций в полях Галуа GF(2m).
В приложении В рассмотрена реализация блоков одноканального РС-декодера
на ПЛИС. Представлены результаты моделирования проектов одноканального РСкодека и многоканального РС-декодера стандарта G.709.
Публикации по теме диссертации:
1. Тайлеб-Мазуз Н. Параметризованный проект высокоскоростного
многоканального декодера кода Рида-Соломона // Вестник МЭИ. - M.:
Издательский дом МЭИ, 2011. № 5, -С 112-118.
2. Тайлеб Н., Поляков А.К. Проектирование кодеров и декодеров кода РидаСоломона на ПЛИС типа FPGA // Сборник трудов научного семинара,
посвященного памяти д.т.н., профессора З.М. БЕНЕСОНА.- М.: ВЦ РАН, 2008.
-С. 26-29.
3. Тайлеб ур. Мазуз Н., Поляков А.К., Реализация библиотеки арифметических
операций над полиномами в поле Галуа на ПЛИС типа FPGA //
Радиоэлектроника, электротехника и энергетика: 14-ая междунар. Науч.-техн.
Конф. студентов и аспирантов МЭИ: тез докл. : В 3-х т., - M.: Издательский
дом МЭИ, 2008. - Т.1. -С 345-346.
4. Введение в САПР ПЛИС фирмы XILINX: Лабораторный практикум:
методическое пособие / Тайлеб Н. [и др.] / под ред. Полякова А. К. и Дерюгина
А. А. - М.: Издательский дом МЭИ, 2007.
5. Тайлеб Н., Поляков А. К., Тайлеб М. Библиотека VERILOG-описаний
арифметических операций в поле Галуа // Современная Электроника. -M.:
СТА-ПРЕСС, 2007. № 5, -С. 46-48.
6. Тайлеб Н., Поляков А. К., Тайлеб М. Некоторые вопросы перепроектирования
старой цифровой аппаратуры на новой элементной базе ПЛИС типа FPGA //
Радиоэлектроника, электротехника и энергетика: 13-ая междунар. Науч.-техн.
Конф. студентов и аспирантов МЭИ: Тез. докл. : в 3-х т. -M.: Издательский дом
МЭИ, 2007. - Т. 1. -С 418-419.
Документ
Категория
Технические науки
Просмотров
401
Размер файла
429 Кб
Теги
кандидатская
1/--страниц
Пожаловаться на содержимое документа