автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Методики моделирования низкоплотностных кодеков с использованием массивно-параллельных вычислений

На правах рукописи

НАУМЕНКО Юрий Сергеевич

МЕТОДИКИ МОДЕЛИРОВАНИЯ НИЗКОПЛОТНОСТНЫХ КОДЕКОВ С ИСПОЛЬЗОВАНИЕМ МАССИВНО-ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

Специальность 05.12.13 — Системы, сети и устройства телекоммуникаций

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Воронеж - 2015

Работа выполнена в ФГБОУ технический университет»

ВПО «Воронежский государственный

Научный руководитель:

Официальные оппоненты:

доктор технических наук, доцент Климов Александр Иванович

Манелис Владимир Борисович, доктор технических наук, ведущий научный сотрудник ЗАО «Иркос», г. Москва;

Малютин Александр Анатольевич, кандидат технических наук, начальник сектора ОАО «Концерн «Созвездие», г. Воронеж

Ведущая организация:

ФГБОУ ВПО «Воронежский государственный университет»

Защита состоится « 9 » апреля 2015 г. в 1422 часов на заседании диссертационного совета Д 212.037.10 в конференц-зале ФГБОУ ВПО «Воронежский государственный технический университет» по адресу: 394026, г. Воронеж, Московский просп., 14.

С диссертацией можно ознакомиться в научно-технической библиотеке и на официальном сайте ФГБОУ ВПО «Воронежский государственный технический университет» www.vorstu.ru.

Автореферат разослан « и » февраля 2015 г.

Ученый секретарь диссертационного совета

%

Макаров Олег Юрьевич

российская

государственная библиотека 2015

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. В настоящее время развитие систем, сетей и устройств телекоммуникаций сопряжено с постоянным увеличением объема циркулирующей в них информации. Повышаются требования к скорости передачи, к надежности и качеству приема. Удовлетворение этих требований диктует необходимость совершенствования способов и средств обработки информации, и, в частности, решения задач эффективного использования методов помехоустойчивого кодирования и выбора вариантов построения реализующих эти методы устройств — кодеров и декодеров (кодеков), которые являются одними из наиболее ответственных элементов в архитектуре телекоммуникационных систем.

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

Одними из самых энергетически эффективных и поэтому часто применяемых на практике кодов являются низкоплотностные коды или коды с малой плотностью проверок на четность (LDPC-код от англ. Low-Density Parity-Check code). Такие коды являются базовыми во многих технических стандартах в области телекоммуникаций, например IEEE 802.11 WiFi, ETSI EN302307-2 DVB-S2X и др. При реализации процедур декодирования низкоплотностных кодов результативным оказывается применение параллельных схем вычислений. В этой связи в задаче моделирования низкоплотностных кодеков перспективно применение гетерогенных вычислений с использованием ресурса графического процессора (ГП, GPU от англ. Graphics Processing Unit) ЭВМ, который обычно не задействован, в отличие от ее центрального процессора (ЦП, CPU от англ. Central Processing Unit,). Для ГП характерна массивно-параллельная архитектура, поэтому при достаточной степени распараллеливания алгоритмов моделирования вычисления с помощью ГП оказываются более производительными.

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

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

B.В. Зяблов, Р. Морелос-Сарагоса, Д. Маккей).

Однако вопросы применения параллельных вычислений в гетерогенных системах для решения задач моделирования низкоплотностных кодеков лишь частично затронуты в некоторых работах зарубежных авторов (J.R. Cavallaro,

C. Chang, G. Falcao, S. Kang, G. Wang, Q. Wu) и фактически остаются открытыми. При этом основной акцент сделан преимущественно на задаче адаптации известных алгоритмов декодирования для реализации вычислений при помощи ГП, а процесс моделирования в целом, с учетом полного состава моделей в их взаимосвязи и особенностей реализации в гетерогенной системе рассмотрен недостаточно полно. Кроме того, проверка известных результатов на практике затруднительна в связи с высокими аппаратными требованиями (G. Falcao, G.Wang) и реализацией аппаратно-зависимых решений ввиду использования программно-аппаратной архитектуры CUDA (S. Kang, S. Cheng).

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные теоретические и практические результаты работы в виде методик и автоматизированных средств внедрены на предприятии ОАО «Концерн «Созвездие» города Воронежа, а также в учебный процесс ФГБОУ ВПО «Воронежский государственный технический университет» по дисциплине «Основы конструирования электронных средств» для подготовки бакалавров по на-

правлению 211000.62 — Конструирование и технология электронных средств (профиль «Проектирование и технология радиоэлектронных средств») для всех форм обучения.

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

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

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

2. Для ограничения коммуникационных взаимодействий уровней ЦП-ГП модель источника помех целесообразно реализовывать на уровне процессорных элементов ГП. Использование разработанной методики моделирования источника помех обеспечивает достаточную точность получаемых результатов и повышение производительности вычислений за счёт уменьшения количества обращений к внешнему регистру состояния генератора псевдослучайных чисел. Экспериментально оцененный прирост производительности вычислений достигает 30 %.

3. Влияние низкой пропускной способности глобальной и локальной памяти ГП на производительность вычислений автоматизированных средств моделирования низкоплотностных кодеков может быть снижено за счет использования разработанных схем вычислений, предусматривающих минимизацию обращений к этим разделам памяти и применение процедур кэширования. Экспериментально оцененный прирост производительности вычислений для кодов длиной 96...9972 в среднем составляет 11 %.

4. Типовая схема организации гетерогенных вычислений в задаче моделирования низкоплотностных кодеков может быть модифицирована за счет использования дополнительного потока расчетов на ЦП. Применение разработанной методики моделирования низкоплотностных кодеков в однопроцессорных гетерогенных системах позволяет повысить производительность вычислений для кодов длиной 96...3000. Экспериментально оцененный выигрыш при малых значениях длины (до 273) составляет 80...41 для длин 273..3000 устанавливается на уровне 21 %.

5. Результаты моделирования, полученные при использовании разработанных автоматизированных средств, соответствуют известным, в частности, приведенным в работах Р. Морелос-Сарагоса, при этом экспериментально оцененный выигрыш в производительности параллельных вычислений по отношению к однопоточным при длине кода N>2000 составляет при использовании декодера: по алгоритму с инвертированием бита — 1,1-5,3 раз: по алгоритму распространения доверия — 6,4-15 раз; по логарифмической версии алгоритма распространения доверия — 47-76 раз.

Степень достоверности н апробация результатов подтверждается применением стандартных методик и известных моделей для исследования характеристик устройств телекоммуникаций, известных методов обеспечения статистической достоверности полученных результатов, сопоставлением результатов экспериментальных исследований с известными данными других авторов. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих конференциях, совещаниях и семинарах: Всероссийской научно-технической конференции «Современные проблемы радиоэлектроники» (Красноярск, 2013); Международном симпозиуме «Надежность и качество» (Пенза, 2013); Международной научно-практической конференции «Охрана, безопасность, связь — 2013» (Воронеж, 2013); Региональной научной конференции студентов, аспирантов и молодых ученых «Инновационные разработки молодых ученых Воронежской области на службу региона» (Воронеж, 2014); финале конкурса по программе «Участник молодежного научно-инновационного конкурса» (Воронеж, 2014); Международной конференции, Российской научной школы и Форума «Системные проблемы надежности, качества, компьютерного моделирования, информационных и электронных технологий в инновационных проектах (Инноватика—2014)» (Сочи, 2014).

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

Публикации. По теме диссертации опубликовано 16 печатных работ, в том числе 10 — в изданиях, рекомендованных ВАК РФ

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 106 наименований и приложения. Основная часть работы изложена на 128 страницах, содержит 47 рисунков и 4 таблицы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Особое внимание уделено анализу процедуры декодирования, являющейся наиболее ресурсоемкой и во многом определяющей результат применения кодирования. Рассмотрены типовые, пригодные для программной реализации, алгоритмы декодирования кодов с малой плотностью проверок на четность — алгоритм с инвертированием бита (BF от англ. Bit Flip; с жесткими решениями) и алгоритм распространения доверия (BP от англ. Belief Propagation: с мягкими решениями) и его логарифмическая версия (logBP). Приведены оценки эффективности алгоритмов для низкоплотностных кодов различной длины.

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

В плане оптимизации системы помехоустойчивого кодирования на предварительном этапе проектирования телекоммуникационных устройств рассмотрена задача моделирования низкоплотностных кодеков, для решения которой обычно используются средства универсальных математических пакетов (в основном, пакета MATLAB). Универсальные системы автоматизированного проектирования (САПР) оказываются непригодны для решения подобных задач по следующим причинам:

1) математическое обеспечение универсальных САПР, ориентированных на решение широкого круга технических задач, часто является недостаточно полным для решения специфических задач:

2) универсальные средства зачастую оказываются недостаточно оптимизированными, уступая в производительности «ручной» пользовательской реализации;

3) прямое использование кода программ моделирования или их фрагментов в большинстве случаев затруднительно;

4) программные средства универсальных САПР имеют весьма высокую стоимость, что существенно ограничивает их доступность и ставит под сомнение целесообразность использования для решения узкоспециальных задач.

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

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

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

Отдельно рассмотрена модель источника помех и его главный элемент -генератор псевдослучайных чисел, качество которого определяет адекватность получаемых результатов. Предложена программная реализация модели двоичного симметричного канала с аддитивным белым гауссовским шумом, обеспечивающая за счет использования генератора псевдослучайных чисел с повышенным периодом достаточную для практики проектирования кодеков точность и высокую производительность. Проведена экспериментальная сравнительная оценка характеристик модели источника помех с ГПСЧ с повышенным периодом (263) по отношению к известным реализациям с применением стандартного для среды Visual С++ ГПСЧ rand (период 232). Модель источника помех с ГПСЧ с повышенным периодом и использованием преобразования Бокса-Мюллера показывает лучшие результаты, близкие к представленным в работах Р. Морелос-Сарагоса.

Для обеспечения статистической устойчивости получаемых результатов и определения необходимого количества циклов вычислений применено выражение N = t/,'(l + Р')/{32 Р'), предлагаемое в работах Б.В. Матвеева, где

ô = \P"-p\jp\ tß= Ф"'(1 + /?/2). Выражение определяет требуемый объем выборки N, при этом ожидаемая вероятность битовой ошибки Р' входит в относительный интервал 8 с доверительной вероятностью ß. Для удобства программной реализации, вместо таблиц вычисления нормальной квантильной функции Ф 1 (обратной нормальной функции распределения) использован численный метод, основанный на известном выражении Ф 1 через нормальную функцию ошибок erfix): Ф(р) = ~j2erf (2р - \ ) и аппроксимации для обратной нормальной функции ошибок.

В третьей главе обоснован выбор целевой аппаратной платформы и среды разработки средств моделирования низкоплотностных кодеков. Рассмотрена параллельная архитектура декодера по алгоритму распространения доверия и сделан вывод о возможности ее реализации в массивно-параллельной среде. Показано, что такие вычисления можно выполнять с помощью гетерогенной ЭВМ с графическим ускорителем (адаптером). Рассмотрена условная архитектура центрального процессора по отношению к графическому процессору. Для удобства выполнения вычислений общего назначения на ГП применена открытая аппаратно-независимая среда OpenCL (от англ. Open Computing Language -открытый язык вычислений) и среда разработки Visual Studio 2010.

Модифицирована известная схема параллельных вычислений для декодера низкоплотностного (N.J.K) кода по алгоритму распространения доверия: применение массивно-параллельных вычислителей позволяет дополнительно использовать МхК, M=NxJ/K процессорных элементов (рис. 1, б) на первом этапе алгоритма и NxJ процессорных элементов (рис. 2, б) на втором этапе.

Изменению подверглись блоки обработки сообщений от кодовых вершин к проверочным (рис. 1, а) и от проверочных — к коловым (рис. 2, а).

ю

к—I-

а)

б)

Рис. 1. Схемы блока обработки сообщений от кодовых вершин к проверочным

и-

И',

ЛП — ха 4>

л,, — ха

1 1

— ха -Г»

а)

! J

I 2

"■"и

га

V:

I__гттт

р.

б)

Рис. 2. Схемы блока обработки сообщений от проверочных вершин к кодовым

В соответствии с алгоритмом распространения доверия блоки Р|...РМ обработки сообщений от кодовых вершин к проверочным содержат условные

процедуры Сг вычисления логарифмов вероятностей л*1,»/ того, что

проверка т удовлетворяется, если 1-й бит вектора кодовых символов имеет значение х, а остальные биты независимы с вероятностями Л,„г, где т) — множество кодовых позиций, участвующих в /?;-ом проверочном уравнении.

Блоки Р'|...Р*ы обработки сообщений от проверочных вершин к кодовым

содержат процедуры нормализации коэффициентом а = ~\е"'' +е"'") логарифмов вероятностей Ягт/ того, что 1-й бит вектора кодовых символов имеет значение х по информации, полученной от всех проверочных вершин кроме т. Для

каждого блока »е {1,2.....М } вероятности Л'ц вычисляются последовательно

для каждого значения к е (1,2,..., АГ} и могут быть вычислены параллельно при помощи дополнительных К процессорных элементов. Аналогично для каждого

блока И*,, /е {1,2,..., ДО} вероятности л"',;, у"е {1,2,..., У} могут быть вычислены параллельно при помощи дополнительных 5 процессорных элементов.

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

С Вход

1Г

1 2 М

к КхМ

^ЧК \ N

Х.2К V

V 4

М МхЫ

1 2 N

и

!г,

Шр

-В1

ли1 N

"2К ч

Лу ^ ч

М МхЫ

Д

С Выход )

Рис. 3. Архитектура программной реализации декодера по алгоритму распространения доверия

Для определения размеров рабочих групп ГП разработаны аналитические выражения (1). Количество выполняемых потоков Ж (GlobalThreads по стандарту OpenCL) и размер двумерной рабочей группы Th"A (LocalThreads по стандарту OpenCL) для NxJ потоков вычислений на ГП определяются выражениями:

Tli" = Tli" = J\ N>mxN, Tli' =N + mxN~[N mod(m.v/V)l Th! = mxN\

(1)

N <mxN, Th[ = Th] = N, где mxN = jloor(Thl:iaJJ\ThlmAli — максимально допустимый размер локальной одномерной рабочей группы (CL_KERNEL_WORK_GROUP_SIZE согласно стандарту OpenCL), а функция floor{x) возвращает значение х, округленное до ближайшего целого числа вниз. Аналогичные выражения применены для МхК потоков вычислений на ГП.

Вычислительные эксперименты показали, что применение новой архитектуры с измененной схемой параллельных вычислений вместо известной полно-параллельной обеспечивает увеличение производительности для кодов (96,3,6)...(9972,3,6) в среднем в 1,85 раза.

Рассмотрена проблема снижения производительности вычислений вследствие коммуникационных взаимодействий уровней ЦП - ГП. Для ее решения предложено перенести расчеты для модели источника помех на процессорные элементы ГП и, соответственно, использовать параллельный ГПСЧ. Разработана архитектура параллельной реализации модели источника помех, пригодная для переноса расчетов на ГП (рис. 4).

На рис. 4 обозначено: S - состояние ГПСЧ (64-битный регистр сдвига); i - номер параллельного потока генерации псевдослучайных чисел (ПСЧ); 2- amp - инициализирующий коэффициент декодера.

Реализация архитектуры осуществляется по разработанной методике моделирования источника помех:

1. За состояние S берется состояние предыдущего цикла вычислений;

2. Блоком инициализации производится параметризация: Х\ = /3; с\ = /3;

3. Производится 1+1 mod(3) итераций алгоритма генерации ПСЧ (умножение с переносом, Дж. Марсагли)

=(aX„-,+c„_,)modè,C„ = (аХ„_г + c„_Jb),n > г, (2)

где Хи,..., X;t'r_, <а - инициализирующие значения;

4. Вектор из N реализаций значений шума генерируется блоками по D значений. Генерация осуществляется в N/D потоков;

5. Последнее значение ПСЧ, полученное в последнем потоке, заносится в регистр состояния;

6. Над сгенерированным набором ПСЧ производятся преобразования в соответствии с процедурой Бокса-Мюллера.

Вычислительные эксперименты показали, что применение параллельного ГПСЧ с реализацией на уровне ГП обеспечивает прирост производительности до 30 %.

С Вход )

5= mj

и

64

Инициализация

.. i i

1 2 N ID

D —1 \

1£

- {К след. циклу расчетов

Проц. Бокса-Мюллера

2атр\

1 2

N

II

( Выход

Рис. 4. Архитектура параллельной реализации модели источника помех

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

Приведено описание разработанной методики моделирования низкоплот-ностных кодеков в однопроцессорных гетерогенных системах. Новая методика предусматривает процедуру предварительной оценки производительности вычислений на ГП и ЦП и позволяет повысить производительность вычислений за счет повышения нагрузки на ЦП. На рис. 5 представлена архитектура программной реализации предлагаемых решений.

В состав архитектуры программной реализации входят: 1 - блок моделирования канала с аддитивным белым гауссовским шумом (АБГШ); 2 - блок инициализирующих процедур; 3 и 4 - блоки условной архитектуры итеративного декодера по итеративному алгоритму распространения доверия; 5 - блок финального декодирования и принятия жестких решений, 6 - блок оценки вероятности битовой ошибки (от англ. Bit Error Rate, BER). Блоки 3 и 4 в обоих потоках отвечают за передачу сообщений от проверочных вершин к кодовым и обратно, однако в первом потоке, соответствующем вычислениям на ГП, блоки

выполняются параллельно, а в потоке, соответствующем вычислениям на ЦП — последовательно. Вычислительная задача решается потоками параллельно с разделением в соотношении, пропорциональном соотношению производительности вычислений на ГП к ЦП.

( Вход )

Поток 1

X

Поток 2

Модель АБГШ

Инициализация

1 2 3 м

К, Кч К, Км

1

1 2 3 N

.1, •Ь

Декодирование и принятие жестких решений

±

Модель АБГШ

Инициализация

1 к, 1 *

2 к2 2 ь

3 К? 3 н

М Км N

Декодирование и принятие жестких решений

Счет числа допущенных ошибок, оценка ВЕИ

±

Счет числа допущенных ошибок, оценка ВЕЯ

ГП

( Выход)

ЦП

Рис. 5. Схема организации моделирования низкоплотностных кодеков по разработанной методике

Установлено, что эффективность применения предложенной методики зависит от длины кода и аппаратных характеристик вычислителей. Вычислительные эксперименты показали, что наибольший положительный эффект от применения данной методики характерен для кодов длиной (96...3000), причем прирост производительности при малых значениях длины (до 273) достигает 80-41 % и устанавливается на уровне 21 % для кодов большей длины.

В четвертой главе на основе описанных выше новых математических моделей и алгоритмов создан программный комплекс повышенной производительности, отвечающий требованиям к объемам вычислительных ресурсов для моделирования низкоплотностных кодеков при использовании дополнительного вычислителя — ГП графического ускорителя. Приведена архитектура разработанного программного обеспечения, отличающаяся открытостью и обеспечи-

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

Приведены архитектура и описание реализованной тестовой моделирующей оболочки (ТМО), предоставляющей пользователю интерфейс взаимодействия с разработанным комплексом библиотек, а также составлено описание реализованной системы интерфейса и механизмов взаимодействия с пользователем.

Рассмотрены особенности оптимизации системы помехоустойчивого низкоплотностного кодирования. Проведен вычислительный эксперимент, демонстрирующий зависимость принимаемого решения об эффективности того или иного кода от количества циклов вычислений. В конфигурации вычислителя - GPU + параллельный ГПСЧ при моделировании кодов (4000,3,6), (4000,4,8), (8000,3,6), (8000,4,8) в диапазоне 0...2,5 дБ с верификацией по ожидаемому уровню вероятности битовой ошибки 10"3 группа кодов с J = 3 оказалась более эффективной. Однако моделирование с верификацией по ожидаемому уровню вероятности битовой ошибки 107 для кодов длиной 8000, для значений отношения сигнал/шум больших 2,625 дБ, код (8000,4,8) более эффективен, чем код (8000,3,6). Отношение производительностей вычислений на ГП в сравнении с однопоточными последовательными вычислениями на ЦП оказывается не менее 14 раз для кода (8000,3,6) и 16 раз для кода (8000,4,8), т.е. в однопо-точном режиме для моделирования кодов длиной 8000 центральному процессору потребовалось бы около 23 часов, тогда как ГП с параллельным ГПСЧ потребовалось 1,55 часа.

Экспериментально произведена оценка относительного выигрыша в производительности разработанных инструментальных средств (рис. 6).

1922

3748 5574

Длина кода

7401

9227

Рис. 6. Относительный временной выигрыш вычислений в конфигурации СРУ+СРи (ВР, 1одВР декодер)

Относительный временной выигрыш отражен графиками зависимости значения ТСри/ТСри+сри от длины низкоплотностного кода при моделировании в

конфигурации GPU+CPU с декодером BP и logBP по отношению к однопоточ-ным (кривые BP и logBP) и многопоточным (кривые BP+thrd и logBP+thrd) вычислениям на ЦП.

В экспериментальных исследованиях использовались ЦП Intel Core 2 Duo Е8400 (ядер - 2, с частотой 3,6 ГГц); ГП AMD Radeon HD 5770 (процессор Juniper (R800), 800 потоковых процессоров с частотой 850 МГц). Полученные результаты позволили сделать вывод, что при весьма высоких требованиях к вычислительным ресурсам для получения объема выборки, достаточного для принятия решения в течение приемлемого по срокам проектирования времени, разработанные в диссертации средства повышенной производительности дают наибольший положительный эффект по сравнению с традиционными.

В заключении представлены основные результаты диссертационного исследования.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

4. Разработана методика моделирования низкоплотностных кодеков в однопроцессорных гетерогенных системах, содержащая процедуру предварительной оценки производительности вычислений на графическом и центральном процессорах, позволяющая в отличие от аналогичных увеличить производительность расчетов за счет повышения нагрузки на центральный процессор гетерогенной системы. Составлена и подана заявка № 2014145373 от 11.11.2014 на выдачу патента на изобретение «Способ организации вычислений на графических процессорах для моделирования помехоустойчивых низкоплотностных кодеков».

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

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

тально оцененный выигрыш в производительности параллельных вычислений по отношению к однопоточным, при длине кода N>2000 составляет: при использовании декодера по алгоритму с инвертированием бита — 1,1-5,3 раз; при использовании декодера по алгоритму распространения доверия — 6,4-15 раз; при использовании декодера по логарифмической версии алгоритма распространения доверия — 47-76 раз.

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

Список работ, опубликованных автором по теме диссертации.

Публикации в изданиях, рекомендованных ВАК РФ

1. Науменко, Ю.С. Обзор методов турбо-кодирования в контексте сложности их аппаратной реализации [Текст] / Ю.С. Науменко, A.B. Башкиров // Радиотехника. - 2012. - № 8. - С. 70-74.

2. Обзор основных технологий, реализующих эффективные методы помехоустойчивого кодирования, нечувствительных к задержке сигнала [Текст] / Ю.С. Науменко, A.B. Башкиров, A.M. Белицкий, А.И. Климов, A.B. Муратов // Радиотехника. - 2013. - № 12. - С. 30-33.

3. Науменко, Ю.С. Обзор основных технологий, реализующих эффективные методы помехоустойчивого кодирования, чувствительных к задержке сигнала [Текст] / Ю.С. Науменко, A.B. Башкиров // Радиотехника. - 2013.

- № 3. - С. 89-92.

4. Перспективы моделирования параметров алгоритмов помехоустойчивого кодирования с высокой степенью параллелизма при помощи аппаратной платформы на базе GPU [Текст] / Ю.С. Науменко, A.B. Башкиров, А.И. Климов, A.B. Муратов, B.C. Цымбалюк// Радиотехника. -2013. -№ 12.-С. 26-29.

5. Влияние характеристик используемых в моделировании генераторов шума на качество оценки параметров помехоустойчивых кодеков [Текст] / Ю.С. Науменко, A.B. Башкиров, А.И. Климов, JI.H. Короткое // Радиотехника. - 2014.

- № 3. - С. 14-18.

6. Науменко, Ю.С. Возможности недвоичного применения блочных и сверточных кодов с исправлением ошибок [Текст] / Ю.С. Науменко, A.B. Башкиров, Л.Н. Короткое // Радиотехника. - 2014. -№ 3. - С. 59-61.

7. Построение алгоритмов верификации функциональных моделей декодеров [Текст] / A.B. Башкиров, A.B. Муратов, Ю.С. Науменко, A.B. Ситников. // Радиотехника. - 2014. - № 3. - С. 72-76.

8. Науменко, Ю.С. Проблемы моделирования помехоустойчивых кодеков в гетерогенных системах [Текст] / Ю.С. Науменко // Радиотехника. - 2014. -№ 3. - С. 80-82.

9. Науменко, Ю.С. Массивные параллельные вычисления в гетерогенных системах при моделировании низкоплотносных кодеков [Текст] / Ю.С. Науменко // Радиотехника. - 2014. -№ 6. - С. 43-46.

10. Архитектурные особенности графических процессоров семейства Radeon и их применение в сфере ресурсоемкого моделирования помехоустойчивых кодеков [Текст] / Ю.С. Науменко, A.B. Башкиров, A.M. Белицкий, А.И. Климов, A.C. Самодуров, В.М. Питолин // Радиотехника. - 2014. - № 11. -С. 15-18.

Статьи и материалы конференций

11. Науменко, Ю.С. Современные методы декодирования недвоичных кодов с малой плотностью проверок на четность: краткий обзор и сравнение [Текст] / Ю.С. Науменко, A.B. Башкиров // Современные проблемы радиоэлектроники: труды всероссийской науч.-техн. конф. - Красноярск. - 2013. _С. 414-416.

12. Науменко, Ю.С. Стандарты применения кодов с малой плотностью проверок на четность [Текст] / Ю.С. Науменко, A.B. Башкиров // Современные проблемы радиоэлектроники: труды всероссийской науч.-техн. конф. - Красноярск. - 2013. - С. 420-421.

13. Науменко, Ю.С. Недвоичные низкоплотностные коды: алгоритмы декодирования и их вычислительная сложность [Текст] / Ю.С. Науменко, A.B. Башкиров, А.И. Климов // Надежность и качество: труды междунар. симпозиума. - Пенза, 2013.-Т.2.-№ 1-1.-С. 19.

14. Науменко, Ю.С. Исследование влияния характеристик цифровых генераторов шума на результаты оценки параметров помехоустойчивых кодеков [Текст] / Ю.С. Науменко, A.B. Башкиров // Охрана, безопасность, связь - 2013: материалы междунар. научн.-практ. конф. - 4.1. - Воронеж: Воронежский институт Министерства внутренних дел России, 2014. - С. 49-51.

15. Науменко, Ю.С. Среда ускоренного моделирования помехоустойчивых низкоплотностных кодеков в гетерогенных вычислительных системах [Текст] / Ю.С. Науменко // Научно-техническая конференция молодых ученых и специалистов Воронежской области в сфере промышленности и высоких технологий: сб. докл. научн. конф. студентов, аспирантов и молодых ученых. - Воронеж: Воронежский ЦНТИ - филиал ФГБУ «РЭА» Минэнерго РФ, 2014. -С. 163-166.

16. Науменко, Ю.С. Особенности обеспечения производительности вычислений при моделировании помехоустойчивых низкоплотностных кодеков в гетерогенных системах [Текст] / Ю.С. Науменко // Системные проблемы надежности, качества, компьютерного моделирования, информационных и электронных технологий в инновационных проектах (ИННОВАТИКА - 2014): материалы междунар. конф., рос. науч. школы и форума. - М., 2014. - С. 105-107.

Зарегистрированные программы для ЭВМ

Науменко, Ю.С. Среда ускоренного моделирования помехоустойчивых низкоплотностных кодеков в гетерогенных вычислительных системах / Ю.С. Науменко, A.B. Башкиров. - М.: ФГАНУ «Центр информационных технологий и систем органов исполнительной власти». -№ 50201450816от04.12.2014.

//

iL ...

Подписано в печать 06.02.2015. ' ft'

Формат 60x84/16. Бумага для множительных аппаратов. / Усл. печ. л. 1,0. Тираж 90 экз. Заказ № 10

ФГБОУ ВПО «Воронежский государственный технический университет» 394026 Воронеж, Московский просп., 14

2014251047