Методы разработки архитектуры и ускоренного моделирования полностью программируемых низкоплотностных декодеров с использованием массивно-параллельных вычислений Башкиров Алексей Викторович

Введение к работе

Актуальность темы исследования. В настоящее время наблюдается бурный рост и развитие систем передачи данных с лавинообразным увеличением объема передаваемой и принимаемой информации. Развитие спутникового вещания и телефонии, наземного телевизионного и мобильного вещания, кабельных, локальных и городских сетей (LAN/MAN) и др. невозможно без развития средств помехоустойчивого кодирования как на уровне алгоритмизации, так и на аппаратном уровне. Скорость и объем передачи данных через вышеуказанные радиоэлектронные сети растет почти по экспоненциальной зависимости, как и зашумленность частотного диапазона, что приводит к новым, все более жестким требованиям к надежности передачи данных. Одним из главных методов защиты передаваемой информации от искажения и потерь является помехоустойчивое кодирование. Кодеры и декодеры – это, бесспорно, наиважнейшая часть архитектуры построения любых линий цифровой передачи данных с особыми требованиями к надежности исправления ошибок.

При проектировании радиотехнической системы, надежно защищенной от помех, перед разработчиками стоит проблема выбора помехоустойчивого корректирующего кодека, при этом необходимо учитывать множество ограничений на системном и аппаратном уровне и требований стандартов передачи данных. Поиск оптимального варианта требует многократного и ресурсоемкого моделирования кодеков с помощью высокопроизводительных ЭВМ. Применение кодеков, построенных на известных, зачастую устаревших алгоритмах, не может обеспечить требуемой надежности передачи возрастающего потока данных и требований к сокращению временных и аппаратных затрат моделирования при разработке современных радиотехнических систем. Вышеизложенная проблема порождается большой вычислительной сложностью надежных, современных алгоритмов, способных обеспечивать требуемую вероятность ошибки при декодировании огромных потоков информации. Процесс верификации работы кодеков стандартными средствами, входящими в состав современных программных комплексов, занимает значительную часть процесса проектирования и не всегда обеспечивает нахождение всех ошибок RTL-модели будущего устройства, в нашем случае декодера, что требует поиска усовершенствований.

Декодеры для корректирующих кодов с малой плотностью проверок на четность (LDPC) стали в последнее десятилетие популярными в системах связи, благодаря их высокой производительности и возможности параллельной аппаратной реализации. Программируемые логические интегральные схемы (ПЛИС) идеально подходят для мелкосерийного выпуска LDPC-декодеров благодаря возможности их перепрограммирования. Это делает применение ПЛИС экономически более эффективным, чем применение специализированных интегральных схем. В последние годы опубликовано большое число научных работ, посвященных этой проблематике, которые существенно различаются с точки зрения выбора способа реализации архитектуры декодера и критериев оценки производительности. Это затрудняет их сравнение, анализ и оценку

пригодности для внедрения в той или иной системе связи, поэтому необходимо провести всесторонний анализ существующей предметной области с выработкой рекомендаций, методов и средств по улучшению качества моделирования и проектирования архитектуры и аппаратной реализации LDPC-декодеров на базе ПЛИС.

В свете всего вышесказанного, проблема разработки новых методов и средств, обеспечивающих повышение качества моделирования помехоустойчивых кодеков и реализации их на ПЛИС с возможностью обеспечения декодирования произвольного LDPC-кода, является актуальной.

Мировая практика построения таких систем подразумевает распараллеливание процедур вычислений, а следовательно, требует применения гетерогенных вычислений с задействованием графических процессоров (ГП). В стандартных же средствах моделирования ГП или GPU (Graphics Processing Unit) для исследования современных низкоплотностных кодеков не задействуется, а загружается исключительно ЦП (центральный процессор) или (CPU – Central Processing Unit). Высокая производительность ГП по сравнению с ЦП при решении этой задачи достигается за счет использования массивно-параллельной архитектуры ГП. Такой подход позволяет при разработке и моделировании помехоустойчивых радиотехнических систем существенно сократить временные затраты на моделирование при сохранении его точности (т.е. при заданной вероятности ошибки, полноты верификации и др.).

При оценке степени научной разработанности темы следует иметь в виду, что методика помехоустойчивого кодирования, в том числе с использованием низкоплотностных кодов, является глубоко проработанной не только зарубежными, но и отечественными учеными и специалистами и, в частности, детально представлена в работах Овечкина Г.В., Золотарёва В.В., Зяблова В.В., Р. Морелоса-Сарагосы, Д. Маккея. Работы ученых Борисова Ю.П., Комашницкого В.И., Голяницкого И.А., Хорафас Д.Н. посвящены вопросам математического моделирования структурных частей радиотехнических средств, а труды Быкова В.В., Васильева К.К., Поляка Ю.Г. и Нила Р. посвящены практическому имитационному моделированию на ЭВМ.

Однако следует отметить лишь поверхностное упоминание о применении метода распараллеливания при решении задач моделирования LDPC-кодеков в части работ зарубежных авторов, а именно Chang C., Cavallaro J.R., Wang G., Falcao G., Wu Q., Kang S. Причем в этих известных исследованиях делается акцент на моделировании в гетерогенных системах уже давно известных помехоустойчивых кодов, применительно к устаревшим стандартам передачи данных. Вопросы моделирования кодеков, взаимосвязи модели с особенностью реализации ее в гетерогенной системе в литературе практически не рассматриваются или рассматриваются поверхностно, а приводимых данных недостаточно для их применения в решении конкретных практических задач. Не существует также общей практики создания на ПЛИС гибкой (перепрограммируемой) архитектуры LDPC-декодера, способного декодировать произвольный низкоплотно-стный код, а проверка приведенных в работах зарубежных авторов результатов моделирования LDPC-кодеков в гетерогенных системах крайне затруднительна

в связи с высокими аппаратными требованиями и применением программно-аппаратной архитектуры CUDA (Compute Unified Device Architecture) (Kang S., Cheng S., Falcao G., Wang G.). В связи с изложенным выше, степень проработанности данной научно-практической области следует признать явно недостаточной.

Работа была выполнена в рамках одного из основных научных направлений ФГБОУ ВО «Воронежский государственный технический университет» «Перспективные радиоэлектронные и лазерные устройства и системы передачи, приема, обработки и защиты информации» и ГБ НИР 2013.17 «Исследование и разработка методов оптимального проектирования устройств и комплексов радиоэлектронных средств».

Цель и задачи исследования. Целью диссертационного исследования являлась разработка методов, алгоритмов и средств ускоренного проектирования различных низкоплотностных декодеров, применяемых в радиотехнических средствах, работающих во всевозможных стандартах связи.

Для достижения поставленной цели решались следующие задачи:

1. Анализ известных методов эмпирического исследования параметров и характеристик LDPC-кодов и поиск возможных путей оптимизации работы известных алгоритмов низкоплотностного кодирования и декодирования с точки зрения их моделирования в массивно-параллельных гетерогенных вычислительных системах;

2. Анализ современных LDPC-декодеров, реализуемых на основе ПЛИС, пригодных для работы во всех современных и вновь разрабатываемых стандартах связи, и особенностей построения оптимальной архитектуры таких декодеров. Разработка рекомендаций для разработчиков по использованию архитектуры ПЛИС для построения программируемых декодеров;

3. Формирование математических моделей, позволяющих реализовывать алгоритмы декодирования LDPC-кодов при моделировании декодеров в гетерогенных массивно-параллельных вычислительных системах;

4. Разработка новой методики моделирования помех, соответствующей реальным воздействиям источников искажений на передаваемую информацию, пригодной для использования на уровне отдельных процессорных элементов ГП и отвечающей требованиям к организации массивно-параллельных вычислений;

5. Разработка методики моделирования низкоплотностных кодеков, ориентированной на массивно-параллельные вычисления, учитывающей особенности выбранной аппаратной платформы реализации и позволяющей обеспечить более высокую производительность вычислений в сравнении с известными;

6. Реализация моделей и алгоритмов функционирования полностью программируемого параллельного LDPC-декодера на ПЛИС;

7. Выбор перестановочной сети, позволяющей организовать оптимальное обращение к памяти, используемой для хранения матрицы проверки на четность, данных работы декодера, внешней памяти. Сравнение сложности реализации различных перестановочных сетей при построении архитектуры гибкого LDPC-декодера на ПЛИС;

8. Численная оценка аппаратной сложности реализации архитектуры LDPC-декодера с точки зрения общего количества базовых логических элементов, блоков памяти и количества цифровых сигнальных процессоров DSP48;

9. Оценка временного выигрыша, получаемого от предложенного в работе метода массивно-параллельных вычислений по сравнению с общепринятым подходом при помощи имитационного моделирования с использованием разработанных программных средств;

10. Разработка архитектуры полностью программируемого декодера для
однофазной передачи сообщений и многоуровневого декодирования, позво
ляющего декодировать произвольные LDPC-коды с использованием оптималь
ного алгоритма управления декодером и его памятью.

Научная новизна результатов исследования. В работе были получены следующие теоретические и практические результаты, которые характеризуются научной новизной:

1. Архитектура декодера, реализованного по алгоритму распространения доверия, оптимизированная для моделирования в массивно-параллельных вычислителях с использованием графического процессора, позволяющая повысить производительность расчетов за счет применения схем параллельных вычислений.

2. Методика генерирования помех, реализованная на системном уровне графического процессора, применяемая для исследования параметров и характеристик низкоплотностных кодеков с применением массивно-параллельных вычислений, отличающаяся процедурой инициализации потоковых генераторов псевдослучайных чисел (ГПСЧ) при снижении числа итеративных обращений к внешнему регистру состояний, что обеспечивает более высокую производительность.

3. Методика моделирования LDPC-декодера в гетерогенной (однопроцессорной) системе, позволяющая предварительно оценить производительность вычислений на центральном и графическом процессорах и увеличить производительность расчетов благодаря перераспределению потоков вычислений и отведению их части с графического на центральный процессор.

4. Архитектура полностью программируемого LDPC-декодера со специализированной возможностью реализации на ПЛИС, отличающаяся уменьшением сложности обращения к памяти, в сравнении с другими известными архитектурами, что достигается за счет применения двухпортовой памяти вместо однопортовой и применения перестановочной сети Бенеша, не используемой в известных из открытых источников программируемых декодерах.

5. Полностью программируемая параллельная архитектура LDPC-декодера с уменьшением сложности реализации, что достигнуто за счет уменьшения количества требуемых блоков памяти (p вместо 3р), сокращения числа перестановочных связей с четырех до двух и отказа от использования в схеме мультиплексоров.

6. Полностью программируемая архитектура декодера, способная декодировать произвольные LDPC-коды, отличающаяся высокой пропускной способностью, не имеющая проблем доступа к памяти, а также поддерживающая

произвольный набор LDPC-кодов со структурированной или случайной матрицей проверки на четность.

Теоретическая значимость работы заключается в постановке проблемы моделирования низкоплотностных кодеков, применяемых в современных помехоустойчивых радиотехнических системах связи, при разработке моделей и алгоритмов, позволяющих реализовывать алгоритмы декодирования низкоплот-ностных кодов в гетерогенных массивно-параллельных вычислительных системах, при реализации на ПЛИС программируемого параллельного LDPC-декодера, способного декодировать произвольный низкоплотностный код. Теоретическая значимость исследования подтверждается применением полученных результатов при выполнении научно-исследовательских работ, в рамках ГБ НИР 2013.17 «Исследование и разработка методов оптимального проектирования устройств и комплексов радиоэлектронных средств». Полученные теоретические сведения используются в процессе преподавания дисциплин, читаемых в ФГБОУ ВО «Воронежский государственный технический университет» для бакалавров направлений 11.03.03 «Конструирование и технология электронных средств» (профиль «Проектирование и технология радиоэлектронных средств»), 12.03.01 «Приборостроение» (профиль «Приборостроение») и 11.04.03 «Конструирование и технология электронных средств» (магистерская программа «Автоматизированное проектирование и технология радиоэлектронных средств специального назначения»).

Практическая значимость полученных в диссертационном исследовании результатов состоит в разработанных методиках и архитектурных решениях, которые позволили значительно сократить время на моделирование низкоплот-ностных декодеров, а также получить универсальные архитектуры программируемых LDPC-декодеров, оптимально подходящие для реализации на ПЛИС.

Предложенные технические решения использованы в ряде проектных и производственных задач, а также в работах по определению направлений и путей совершенствования радиоприемных и радиопередающих средств, при обосновании тактико-технических требований к радиоэлектронным изделиям на ведущих предприятиях радиотехнического комплекса Воронежской области и г. Москвы, а именно: АО «Концерн «Созвездие» (г. Воронеж), ОАО «Электросигнал» (г. Воронеж), АО «НВП «ПРОТЕК» (г. Воронеж), АО «ИРКОС» (г. Москва), АО «Воронежское центральное конструкторское бюро «Полюс» (г. Воронеж). На полученный в работе способ организации массивно-параллельных вычислений при моделировании помехоустойчивых низкоплот-ностных кодеков в радиотехнических системах получен патент на изобретение № RU 2604985, зарегистрированный Федеральной службой по интеллектуальной собственности 20.12.2016.

Методология и методы исследования. Исследования основаны на применении методов теории систем передачи информации, элементов теории обработки и моделирования цифрового сигнала, теории вероятностей и математической статистики, методов массивно-параллельных вычислений на ЭВМ, теории арифметики чисел с плавающей точкой, элементов теории верификации и программирования на языке С++.

Положения, выносимые на защиту:

1. Архитектура декодера низкоплотностного кода (N,J,K), функционирующего по алгоритму распространения доверия, которая реализуется с применением массивно-параллельных вычислений на графическом процессоре по модифицированной схеме, отличием которой является применение дополнительных процессорных элементов (NxJ). Проведенные эмпирические изыскания показали получение выигрыша в производительности вычислений в среднем в 1,87 раза, в сравнении с традиционной архитектурой для кодов (96,3,6)... (9972,3,6).

2. Методика моделирования помех, реализованная на уровне отдельных элементов графического процессора, которая ограничивает коммуникационные взаимодействия уровней центральный процессор - графический процессор и позволяет повысить производительность вычислений за счет сокращения обращений к внешнему регистру состояний генератора помех. Проводимые в ходе диссертационной работы эмпирические исследования показали выигрыш производительности на 27% в сравнении со стандартной организацией вычислений.

3. Разработанная методика ускоренных вычислений, производимых на графическом процессоре при моделировании низкоплотностных кодеков, позволяющая минимизировать влияние на них низкой пропускной способности интегрированной в ГП памяти, отличающаяся минимизацией обращений в момент вычисления к этим областям памяти и использованием процедур кэширования. Прирост производительности, оцененный эмпирическим путем, для кодов 90

4. Модификация общепринятой модели гетерогенных вычислений, проводимых при моделировании низкоплотностных кодеков, обеспечивающая повышение производительности расчетов за счет распараллеливания и отведения потока вычислений на центральный процессор, который в общепринятой системе не задействуется. Такой подход показал выигрыш в 41% для длин кода 90

5. Получаемые эмпирическим путем результаты моделирования низкоплотностных кодеков полностью соответствуют известным, приведенным, в частности, в работах Р. Морелос-Сарагоса. При этом получен выигрыш в производительности предложенных гетерогенных вычислений в сравнении с общепринятыми при моделировании кодов (96,3,6)...(9972,3,6) в среднем в 1,1-5,3 раза для декодера, работающего по алгоритму с инвертированием бита, и в 6,4 раза - для декодера, работающего по алгоритму распространения доверия.

6. Разработанная упрощенная архитектура LDPC-декодера, реализуемого на ПЛИС, с уменьшением сложности обращений к памяти, что достигнуто благодаря применению перестановочной сети Бенеша и двухпортовой памяти. Упрощение архитектуры и ее эффективность были подтверждены сравнением разработанной архитектуры с известными по всем значимым параметрам и проведением моделирования для набора LDPC-кодов разной длины.

7. Синтезированная архитектура LDPC-декодера, способная работать с произвольным низкоплотностным кодом, что подтверждается имитационным

моделированием набора структурированных и неструктурированных кодов с измерением скорости возникновения битовых ошибок при их декодировании.

Степень достоверности и апробация результатов. Достоверность результатов подтверждается применением общепринятых стандартных методик и известных моделей для исследования показателей декодеров, работающих с LDPC-кодами, известных методов проверки статистической достоверности получаемых в процессе исследований результатов, сопоставлением полученных результатов эмпирических исследований с известными данными отечественных и зарубежных авторов. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих конференциях, совещаниях и семинарах: на Всероссийских научно-технических конференциях «Современные проблемы радиоэлектроники» (Красноярск, 2006, 2010-2016); Международных симпозиумах «Надежность и качество» (Пенза, 2011-2017); XVIII Международной научно-технической конференции «Радиолокация, навигация, связь – RLNC 2012» (Воронеж); Международной научно-практической конференции «Охрана, безопасность, связь – 2013» (Воронеж, 2013); 18-й Международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникации» (Рязань, 2015); Международной конференции Российской научной школы и Форумов «Системные проблемы надежности, качества, компьютерного моделирования, информационных и электронных технологий в инновационных проектах (Инноватика)» (Сочи, 2005, 2006-2014); Международной конференции «International Conference on Recent Advances in Engineering, Technology and Applied Sciences» (USA, Detroit 2017).

По результатам работы получен патент на изобретение № RU 2604985, зарегистрированный Федеральной службой по интеллектуальной собственности 20.12.2016, и зарегистрировано программное средство в государственном информационном фонде неопубликованных документов ФГАНУ «ЦИТиС» №50201450816 от 04.12.2014.

Публикации. По теме диссертационного исследования опубликовано в общей сложности 75 печатных работ, в том числе 37 – в изданиях, рекомендованных ВАК РФ, 2 статьи в журналах, входящих в SCOPUS, в 2014 и в 2016 годах опубликованы 2 монографии.

Структура и объем работы. Диссертационная работа состоит из введения, шести глав, заключения, списка литературы, включающего 254 наименования. Основная часть работы изложена на 259 страницах, содержит 75 рисунков и 13 таблиц.