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

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

Семерникова Евгения Евгеньевна

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

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

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

кандидата технических наук ' 8 ОКТ 2015

Таганрог-2015 005563717

005563717

Работа выполнена в Федеральном государственном автономном образовательном учреждении высшего образования «Южный федеральный университет» (ЮФУ) на кафедре «Интеллектуальные и многопроцессорные системы» (ИМС) и в Научно-исследовательском институте многопроцессорных вычислительных систем имени академика A.B. Каляева федерального государственного автономного образовательного учреждения высшего образования «Южный федеральный университет» (НИИ МВС ЮФУ).

НАУЧНЫЙ РУКОВОДИТЕЛЬ: доктор технических наук, профессор,

Левин Илья Израилевич

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ: Фатхи Владимир Ахатович,

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

Хади Роман Ахмедович, кандидат технических наук, ФГНУ «НИИ «Спецвузавтоматика», директор

ВЕДУЩАЯ ОРГАНИЗАЦИЯ: федеральное государственное

бюджетное образовательное учреждение высшего образования "Юго-Западный государственный университет" (ЮЗГУ), г. Курск

Защита диссертации состоится «23» декабря 2015 г. в 1200 на заседании диссертационного совета Д 212.208.24 при Южном федеральном университете по адресу: г. Таганрог, ул. Чехова, 2, корп. "И", комн. 347.

С диссертацией можно ознакомиться в библиотеке и на сайте Южного федерального университета по следующей ссылке:

http://hub^fedu.ru/diss/announceraent/5bd4ba89-44e44b0c-8104-13fdb7572c3c/.

Автореферат разослан C/z^f-J'iCiCj 2015 г.

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

А.П. Кухаренко

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

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

Применение прикладных интегральных схем (ASIC - Application Specific Integrated Circuit) позволяет эффективно реализовывать алгоритмы, использующие произвольную разрядность операндов. Заказные микросхемы являются максимально оптимизированными по структуре, площади кристалла и быстродействию для решения определенной задачи. В отличие от универсальных микросхем заказные кристаллы обеспечивают очень высокую, в десятки раз быстрее, скорость решения поставленных перед ними задач, однако обладают высокой стоимостью при мелкосерийном производстве. Если исходный алгоритм требует доработок, то появляется необходимость изменений на аппаратном уровне, которые фактически эквивалентны разработке нового проекта заказного кристалла.

Реконфигурируемые вычислительные системы (РВС) на базе программируемых логических интегральных схем (ПЛИС), называемых в зарубежной литературе FPGA (Field-Programmable Gate Array), также лишены ограничений, связанных с разрядностью обрабатываемых данных. Архитектура таких систем подстраивается под вычислительную структуру решаемой задачи, что позволяет достигать очень высоких значений производительности, порядка 90% от значений пиковой производительности, для задач из различных областей знаний.

Несмотря на указанные достоинства, затруднительным остается процесс программирования РВС, особенно для алгоритмов переменной разрядности. Программирование РВС с использованием высокоуровневых систем программирования, базирующихся на синтаксисе и семантике традиционного языка программирования императивного типа С (Catapult С, Handle-C, Mitrion-C, ImpulseC), имеет сильные ограничения при обработке данных на уровне битов. При этом подобные системы не обеспечивают эффективное использование логических ячеек ПЛИС в соответствии с требуемой разрядностью вычислений.

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

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

уровнем параллелизма. Системные средства, предоставляемые фирмами-изготовителями ПЛИС, ориентированы на создание однокристальных проектов, в связи с чем реализация задач, для решения которых необходимо использование нескольких ПЛИС, занимает большое время - до нескольких месяцев по сравнению с программированием многокристальных РВС на языке высокого уровня СОЬАМО.

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

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

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

Объектом исследований являются методы и средства битовой обработки данных в прикладных программах для реконфигурируемых вычислительных систем.

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

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

1) провести анализ методов и средств разработки параллельных программ для

РВС;

2) разработать методы параллельной и последовательной обработки битовых данных;

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

4) разработать методы контекстного определения разрядностей и типов вычислительных макроопераций;

5) разработать алгоритмы трансляции битовых конструкций языка программирования;

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

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

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

Экспериментальные исследования проводились на реконфигурируемых вычислительных системах последних поколений.

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

Научная новизна диссертации заключается в том, что в ней разработаны:

1) методы последовательной и параллельной обработки битовых данных, отличающиеся от известных способностью масштабирования по разрядности параллельно-конвейерных программ на этапе определения типов данных;

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

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

4) новые алгоритмы трансляции битовых конструкций языка программирования высокого уровня СОЬАМО;

5) структура утилиты транслятора языка программирования высокого уровня СОЬАМО, отличающаяся наличием процедуры приведения к единой степени распараллеливания, процедуры определения разрядностей виртуальных переменных и процедуры подстановки вычислительных устройств.

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

1) обработка битовых данных с возможностью разграничения способа доступа к битам на последовательный и параллельный позволяет создавать масштабируемые по разрядности параллельно-конвейерные программы;

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

Результаты, выносимые на защиту:

1) методы последовательной и параллельной обработки битовых данных, отличающиеся от известных способностью масштабирования по разрядности параллельно-конвейерных программ на этапе определения типов данных;

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

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

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

Практическая ценность работы.

На основании предложенных методов и алгоритмов создана утилита транслятора языка программирования высокого уровня COLAMO для реконфигурируемых вычислительных систем. Применение утилиты позволяет сократить время разработки параллельно-конвейерных программ с битовой обработкой данных на 7-10% по сравнению с разработкой аналогичных программ на языке VHDL. В частности, для задачи реализации КИХ-фильтра на РВС время разработки было сокращено на 7,5%, для задачи цифрового диаграммоформирования - на 10%, для задачи реализации хэш-функции - на 8%. Разработанные методы также позволили сократить время портации прикладной программы по сравнению с ручной переработкой текста программы на VHDL:

- в соответствии с требуемой разрядностью вычислений — в 20-30 раз;

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

Реализация и внедрение результатов работы. Результаты диссертационного исследования использовались при выполнении ряда НИОКР в НИИ МВС ЮФУ, в рамках которых прорабатывались принципы создания системного и прикладного программного обеспечения РВС различных конфигураций и архитектур. Самыми значительными из них являются:

- «Разработка научно-технических основ создания многопроцессорных вычислительных систем сверхпетафлопсной производительности и подготовка кадров высшей квалификации в области распределенных вычислений», отчет о НИР, № гос. per. 01200958384, инв. 05.НОЦ.2011, Таганрог, НИИ МВС ЮФУ, шифр «20091.1-215-002-013», 2011;

- «Разработка методов и инструментальных систем для анализа эффективности работы параллельных программ и суперкомпьютеров», отчет о НИР, № гос. per. И110519102540, Таганрог, НИИ МВС ЮФУ, 2012 г.;

- «Разработка реконфигурируемой вычислительной системы РВС-7 и организация на ее основе производства реконфигурируемых вычислительных систем с производительностью до 1015 операций в секунду в одностоечном конструктиве 47U», отчет об ОКР, № гос. per. 49-15/259, Таганрог, НИИ МВС ЮФУ, 2013 г.;

- «Разработка и исследование принципов построения программных средств для высокопроизводительных реконфигурируемых вычислительных комплексов», отчет о НИР, № гос. per. 01201153442, Таганрог, НИИ МВС ЮФУ, 2013 г.;

- «Разработка и исследование методов синтеза прикладных программ для реконфигурируемых вычислительных систем на основе перспективных ПЛИС сверхвысокой степени интеграции», отчет о НИР, № гос. per. 114061040060, Таганрог, НИИ МВС ЮФУ, 2014 г.;

- «Разработка и исследование технологии создания ресурсонезависимого прикладного программного обеспечения высокопроизводительных вычислительных систем гибридного типа», отчет о НИР, № гос. per. 140912-077192, Таганрог, НИИ МВС ЮФУ, 2014 г.

Созданные методы, алгоритмы и программные средства внедрены в следующих организациях: ОАО «Концерн ПВО «Алмаз-Антей» (г. Москва), ЮНЦ РАН (г. Ростов-на-Дону), ПИИ МВС ЮФУ (г. Таганрог).

Апробация работы. Основные результаты, представленные в диссертации, докладывались и обсуждались на всероссийских и международных научно-технических конференциях: VIII, XI ежегодных научных конференциях студентов и аспирантов базовых кафедр ЮНЦ РАН, г. Ростов-на-Дону; 2-ой Всероссийской научно-технической конференции «Суперкомпьютерные технологии (СКТ-2012)», с. Дивноморское, г. Геленджик, 2012 г и 9-ой международной молодежной школе «Высокопроизводительные вычислительные системы (ВПВС-2012)», г. Таганрог, 2012 г.; 6-ой всероссийской мультиконференции по проблемам управления (МКПУ-2013), с. Дивноморское, г. Геленджик, 2013 г.; 3-й Всероссийской научно-технической конференции «Суперкомпьютерные технологии (СКТ-2014)», с. Дивноморское, г. Геленджик, 2014 г; 7-ой всероссийской мультиконференции по проблемам управления (МКПУ-2015), с. Дивноморское, г. Геленджик, 2015 г.

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

Публикации. Основные положения диссертации опубликованы в 10 научных печатных работах: из них 3 статьи, 2 статьи из которых опубликованы в ведущих рецензируемых научных журналах из перечня ВАК РФ, а также тезисы и материалы 7 докладов на российских и международных научно-технических конференциях. По теме диссертационного исследования было получено 2 свидетельства об официальной регистрации программ для ЭВМ. Результаты работы используются в 6 отчетах о НИОКР.

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

Диссертация соответствует п. 8 («Модели и методы создания программ и программных систем для параллельной и распределенной обработки данных, языки и инструментальные средства параллельного программирования») паспорта специальности 05.13.11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», технические науки.

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

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

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

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

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

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

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

Во второй главе для расширения возможностей доступа к битам вводится новая конструкция языка, позволяющая не только обращаться к любому биту в отдельности, но и разграничивать способ доступа к нему на параллельный и последовательный: Var <Имя_переменной> : [<Число_бит> : ВИ<Тип_доступа>]; Данная языковая конструкция обеспечивает новое качество программирования за счет введения дополнительных измерений к уже существующим в массивах языка COLAMO.

В дополнение к имеющимся двум измерениям: количеству каналов данных (Vector) и глубине каналов (Stream), вводится размерность каналов данных в битах, которая позволяет разграничивать доступ к битам на параллельный и последовательный: Bit Vector (рис. 1) и Bit Stream (рис. 2). При этом сохраняется ортогональность принципов языка COLAMO, допускаются любые сочетания измерений массивов, работа со смешанными типами.

Var А, В, С : [37:bit vector]; Var i : Number; Const N=36; Cadr Example; For i:=0 to N do C[i]:=A[i] and B[i]; EndCadr;

Рисунок 1 — Параллельный способ доступа к битам

АЮ А1 АО

В10 В1 ВО

Var А, В, С : [I I :bit stream]; Var i: Number; Const N-=10; Cadr Example;

For to N do C[i]:=A[i] and B[i]; EndCadr;

Рисунок 2 - Последовательный способ доступа к битам

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

Var А : [32:bit stream];

Var В : [32:bit vector];

Var i: Number;

Const N=31;

Cadr Example;

For i:=0 to N do

A[i]:=B[i];

EndCadr;

Рисунок 3 - Сопряжение массивов с параллельным и последовательным способом

обработки битов

Var А : [32:bit vector];

Var В : [32:bit stream];

Var i : Number;

Const N=31;

Cadr Example;

For i:=0 to N do A[i]:=B[i];

EndCadr;

0

1

31

Рисунок 4 - Сопряжение массивов с последовательным и параллельным способом

обработки битов

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

на> о)

где N - это размерность битового массива, М - разрядность памяти, а Р -коэффициент приведения разрядности.

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

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

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

L = М х Р - N. (2)

Для доступа к внутренней памяти ПЛИС (BRAM) в языке COLAMO используются типы доступа InterMem и InterMemK, где К - количество доступных портов при работе с внутренней памятью ПЛИС.

Внутренняя память ПЛИС позволяет хранить и адресоваться к битовым данным с последовательной и параллельной обработкой битов без дополнительных преобразований. При этом ширина памяти будет равна 1, а глубина будет зависеть от способа хранения Stream или Vector. Для способа хранения и доступа к битам Stream глубина памяти будет равна размерности массива, а для способа хранения Vector будет использовано М блоков внутренней памяти, хранящих по 1 элементу массива, где М — размерность массива.

Функциональные особенности типа данных InterMem позволили разработать механизм связывания переменных Union в области многопортовой внутренней памяти (рис. 5). Начальные точки хранения связанных переменных в области памяти совпадают, при этом количество портов внутренней памяти должно равняться числу связываемых переменных. Таким образом, достигается переключение между битовым массивом, размерность которого соответствует разрядности любого из стандартных типов данных (Integer, Int64 и т.д.), и переменной соответствующего типа. При этом переход от битового массива к переменной происходит без использования дополнительного оборудования путем чтения из внутренней памяти.

Var А : Integer lnterMem2; n

Var В : [27:bit stream] InterMem2;

Var С : Integer Reg;

Var D : [27:bit stream] Reg;

Var i, j : Number;

Const N = 26;

Cadr Example;

Union(A,B);

A := C;

For j:= 0 to N do D[i] := B[i];

EndCadr;

Рисунок 5 - Использование двухпортовой внутренней памяти для связывания

переменных Union

со

Cl

С31

AddWR

Data DI Data DO

AddR

Type

DO

Dl

D26

Разработаны правила сопряжения битовых массивов с Конструкциями языка СОЬАМО и условным оператором. При вызове конструкции 8иЬСас1г в тексте программы в информационном графе в точке вызова подкадра происходит добавление соответствующего информационного подграфа. Распараллеливание

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

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

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

Vara, Ъ, е : [19:bit vector] Com; а

Var i: Number; HJ"

Const n= 19; —

SubCadr Computation (In : lnl, In2; Out: Outl); L_

Var In 1 : Bit Com; :

Var ln2 ; [3:bit vector] Com;

Var Outl : [19:bit vector] Com; 1—

Outl :=F,(lnl,ln2); EndSubCadr; Cadr One;

Computation (a[*], b[3:5], e[*]); EndCadr;

Рисунок 6 - Сопряжение подкадра с битовыми массивами

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

Var а: [100: Vector][22: Bit Vector] Com; Var c,d: array Integer [100: Vector] [22: Bit Stream] Mem;

Var b: array Integer [100: Vector] [22: Bit Vector] Mem; Var ij: Number; Const n=99; Const m = 21; Cadr ExamplelfStream; For i:=0 to n do

For j:=0 to m do lfb[ij] = 0then a[i j] := fi(c[ij]);

Else

a[ij]:- f.(d[ij]);

Endcadr;

Рисунок 7 - Нераспараллеленный условный оператор

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

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

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

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

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

Основными макрооперациями являются: «+», «-», «*», аргументами которых будут битовые массивы Bit Vector или Bit Stream. В зависимости от способа обработки битов, указанных при описании массивов, на место соответствующей макрооперации программой автоматического разбора и преобразования исходного текста будут подставляться параллельные (для Bit Vector) или последовательные (для Bit Stream) арифметические устройства требуемой разрядности из программной библиотеки вычислительных устройств с переменной разрядностью. Макрооперации делятся на два типа: масштабирующие и немасштабирующие. В зависимости от типа макрооперации на ее место будут подставляться соответствующие арифметические устройства (масштабирующие или немасштабирующие). Масштабирующие арифметические устройства возвращают результат той разрядности, которая задана пользователем, немасштабирующие - возвращают значения с увеличенной разрядной сеткой: для сложения и вычитания на 1 разряд, для умножения — сумма разрядностей входных операндов.

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

Однако для более детального описания правил работы с виртуальными переменными необходимо рассматривать их как совокупность произвольного числа одновременно доступных битов, то есть поставить в соответствие переменной типа Virtual виртуальный битовый массив [Virtual : bit vector], размерность которого будет определяться в процессе разбора программного кода в соответствии с предлагаемыми правилами.

1. Операция присваивания виртуальному массиву значений битового массива

а<со> := P<N>

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

2. Обратная операция

P<N> := а<со>

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

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

y<N> := а<со>хр<о>,

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

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

у<со> := a<N>xp<o>,

разрядность о теоретически может быть любой, однако для простоты будем принимать ее равной N, в то время как разрядность результата такой арифметической операции со может быть больше либо равной N в зависимости от типа арифметической операции. Немасштабирующая операция сложения-вычитания co=N+l, немасштабирующая операция умножения ю = 2N, в остальных случаях m = N.

5. Если результатом немасштабирующей операции в выражении является виртуальный битовый массив

7<w> u<N>*p<N>,

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

Для осуществления вычислений на уровне заданной точности введены

масштабирующие арифметические макрооперации: ©, ©, О, О, где N -разрядность операции. Их использование порождает иные правила определения разрядности для виртуальных битовых конструкций. Расчёт разрядностей

виртуальных битовых массивов, участвующих в вычислениях масштабирующих макроопераций y<N> := а<ш>© Р<а>, определяется следующей теоремой.

Выполнение масштабирующей макрооперации на уровне заданной точности М над виртуальными битовыми массивами с записью результата в битовый массив разрядностью N накладывает ограничение: N>M и определяет разрядность виртуальных битовых массивов в зависимости от типа макрооперации, равной М для операции сложения/вычитания, и М/2 - для умножения.

Для масштабирующих операций в выражениях, в которых все битовые массивы являются виртуальными у<со> := а<т]>® р<о>, расчёт значений разрядностей виртуальных битовых массивов определяется следствием из теоремы.

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

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

Доказано, что если конструкция If ... Else в каждой из своих альтернативных веток присваивает различные значения одному и тому же виртуальному битовому массиву

If© then у<ш> := a<N> Else 7<ш> := Р<М>,

то виртуальный битовый массив у в зависимости от логического выражения в может получить значения размерностью и N, и М данных. Для того чтобы избежать потери данных при записи большего количества данных в массив меньшей размерности, необходимо установить размерность массива у, равной максимальному значению размерности записываемого битового массива из всех возможных, то есть co=Max(N,M).

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

If© then y<N> := а<со> Else Р<М> := а<со>,

то в таком случае необходимо, с одной стороны, сформировать разрядность виртуального битового массива <u<N, а с другой стороны, <и<М. Однако учитывая тот факт, что аппаратно реализуется каждая альтернативная ветка условного оператора, необходимо объединить эти ограничения по разрядности в одно. Таким образом, результирующая разрядность виртуального битового массива будет равной <D<Min(N,M).

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

D<a<co>> — произвольный массив, размерность которого заранее не известна и определяется размерностью виртуального битового массива а<со>. В процессе работы

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

w = ]Log2(Max(x,y,z,...))[.

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

Показано, что виртуальная битовая структура может использоваться в качестве счетчика цикла For: for p<co>:= N to (downto) M. В зависимости от диапазона работы генератора определяется количество битов, необходимых для кодировки значения со,

со = ]Log2(M-N+l)[

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

со = ]Log2(Max(N,M))[.

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

В четвертой главе на основании разработанных методов обработки и трансляции битовых и виртуальных конструкций создана утилита транслятора языка COLAMO для битовой обработки данных. Разработана общая схема взаимодействия утилиты с комплексом математического обеспечения: транслятором, синтезатором, библиотекой VHDL описания. Разработана структура утилиты (рис. 8), отличающаяся наличием библиотеки вычислительных устройств с переменной разрядностью, а также наличием процедур поиска битовых конструкций, приведения к единой степени распараллеливания, определения разрядностей виртуальных переменных и подстановки вычислительных устройств в место вызова арифметической макрооперации.

/Текст параллельной / программы на языке / COLAMO

литеры

/

списки операторов списки операторов

Поисп конструкций типа Bit Vector иШstream Поиск виртуаль^чых конструкции

модифицированный список операторов

операторов

Процедура приведения к единои степени распараллеливания

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

Процедура определения разрядностей в и ртуальных переменных

таблица макроопераций и их разрядное гей

Процедура подстановки вычислительных устройств

Модифицированные" текст параллельной программь^аязыке

Рисунок 8 -Структура утилиты транслятора языка COLAMO

В результате работы утилиты транслятора языка СОЬАМО происходит модификация исходного текста программы.

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

; Ф Конфигурация 'ШМШЖ

; Библиотеки ! Средства транспл*«« ! Средства синтеза [ Настройки оболочки I ГЬоект!

Транслятор Способ отображения сообщений

Ж С01АМ0 | Отображе»»* сообщений во оры* трансляции И

4<ди» | Зч^гГ-зЬ'^Ьг^^ ы

Ш Включить геиФраинс операторе» загрузи и выгрухм данн»« О Ьслючить режи* отгадки Щ Использовать маркеры »апис» для регистров и внутре»**ея памяти О Использовать а^о-рониаатор обратной «язи

Генера1>1Я потокового компонента

О Для каждого еыч. модуля »»зюпьэоватъ отдельной оиСиэйп Создать фейлычх-гисадея сегментов пзмяги КРП

| Подллючдя-'ъ« модули

Ш СгМОВ^ато^Сото^кЦЫв^иЫ.«« ... ^ | Добавить \

\. Удашть . \

{ Настройки \

ОТМвИв [ Лр»В*ЖПЬ И,8с ЩЬЯЪ

Рисунок 9 — Окно подключения утилиты к интегрированной среде разработки параллельных программ

Для анализа эффективности созданных методов и средств обработки битовых данных для языка высокого уровня разработан ряд масштабируемых по разрядности прикладных программ из области ЦОС и из области символьной обработки данных.

При реализации КИХ-филыра на РВС использование утилиты позволило сократить время разработки программного компонента на 7,5% по сравнению с реализацией на языке УНБЬ, при этом доля битовых преобразований в данной задаче составила порядка 10%.

Решение задачи цифрового диаграммоформирования в заданном направлении в фазированной антенной решетке позволило сократить время разработки программной реализации на 22% по сравнению с реализацией на языке VIЮЬ, при этом доля битовых преобразований в данной задаче составила порядка 13%.

Еще больший выигрыш по времени достигается при переходе к новой разрядности, что связано с изменением технических характеристик устройств, подающих входные данные, таких как АЦП или антенные элементы. Показано, что время портации прикладной программы под требуемую разрядность вычислений удалось сократить в 20-30 раз по сравнению с ручной переработкой текста программы на УНОЬ.

При реализации на РВС хэш-функции с использованием разработанной утилиты транслятора языка СОЬАМО для битовой обработки данных удалось сократить время создания программного компонента на 8% по сравнению с аналогичной реализацией на языке УНБЬ. В то же время достигается практически

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

В заключении работы сформулированы основные научные, теоретические и прикладные результаты диссертационной работы.

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

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

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

1) методы последовательной и параллельной обработки битовых данных, отличающиеся от известных способностью масштабирования по разрядности параллельно-конвейерных программ на этапе определения типов данных;

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

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

4) структура утилиты транслятора языка программирования высокого уровня СОЬАМО, отличающаяся наличием процедур приведения к единой степени распараллеливания по битам и масштабирования по разрядности.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Семерникова, Е.Е. Разработка масштабируемых реализаций алгоритмов символьной обработки для реконфигурируемых вычислительных систем [Текст] / Е.Е. Семерникова // Известия ЮФУ. Технические науки. - Таганрог: Изд-во ТТИ ЮФУ, 2012. - №4. - С. 215-218 (ведущий рецензируемый журнал, входит в перечень ВАК №1008).

2. Семерникова, Е.Е. Организация битовой обработки данных для реконфигурируемых вычислительных систем на языке программирования высокого уровня [Текст] / Е.Е. Семерникова, И.И. Левин, В.А. Гудков // Вестник компьютерных и информационных технологий. - М.: Машиностроение, 2015. - №5. - С. 3-9 (ведущий рецензируемый журнал, входит в перечень ВАК №262).

3. Семерникова, Е.Е Масштабируемая программа задачи цифровой обработки сигналов / Е.Е. Семерникова, В.А. Гудков // Свидетельство об официальной регистрации программы для ЭВМ № 2013619582, РФ. Зарегистр. в Реестре программ для ЭВМ 10.10.2013 г. Правообладатель: НИИ МВС ЮФУ.

4. Семерникова, Е.Е Утилита транслятора языка высокого уровня СОЬАМО для битовой обработки данных / Е.Е. Семерникова, И.И. Левин, В.А. Гудков // Свидетельство об официальной регистрации программы для ЭВМ №

2015619592, РФ. Зарегистр. в Реестре программ для ЭВМ 08.09.2015 г. Правообладатель: федеральное государственное автономное образовательное учреждение высшего образования «Южный федеральный университет».

5. Семерникова, Е.Е. Перестановки элементов последовательностей в быстрых алгоритмах цифровой обработки сигналов [Текст] / Е.Е. Семерникова, Е.А. Семерников // Вестник Южного научного центра Российской академии наук, 2006. -Т.2, № 4. - С. 25-30;

6. Семерникова, Е.Е. Масштабируемые конвейерные реализации алгоритмов символьной обработки на языке COLAMO [Текст] / Е.Е. Семерникова // Материалы 2-й Всероссийской научно-технической конференции. - Таганрог: Изд-во ЮФУ, 2012. -С. 174-177;

7. Семерникова, Е.Е. Оценка пиковой производительности реконфигурируемой вычислительной системы для задач цифровой обработки сигналов с использованием языка COLAMO [Текст] / Е.Е. Семерникова, А.Г. Коваленко // Тезисы докладов VIII ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН. Росгов-на-Дону, 2012. - С.128-129;

8. Семерникова, Е.Е. Использование языка COLAMO для оценки производительности реконфигурируемой вычислительной системы на задачах цифровой обработки сигналов [Текст] / Е.Е. Семерникова // Высокопроизводительные вычислительные системы: Сборник научных трудов, Выпуск 2. - Таганрог: Изд-во ЮФУ, 2012.-С. 46-47;

9. Семерникова, Е.Е. Использование расширения языка COLAMO для решения задачи цифровой обработки сигналов [Текст] / Е.Е. Семерникова // Материалы 6-й всероссийской мультиконференции по проблемам управления - Ростов-на-Дону: Издательство Южного федерального университета, 2013. Т.4. - С. 178-180;

10. Семерникова, Е.Е. Использование переменной разрядности данных в языках программирования высокого уровня для реконфигурируемых вычислительных систем [Текст] / Е.Е. Семерникова // Материалы 3-й Всероссийской научно-технической конференции "Суперкомпьютерные технологии" (СКТ-2014), с. Дивноморское, 2014. Т.1. - С. 182-184;

11. Семерникова, Е.Е. Битовая обработка данных с использованием языка программирования COLAMO на реконфигурируемых вычислительных системах [Текст] / Е.Е. Семерникова // Тезисы докладов XI ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН. Ростов-на-Дону, 2015. - С.90-91;

12. Семерникова, Е.Е. Битовая обработка данных на языке программирования высокого уровня COLAMO для задач управления [Текст] / Е.Е. Семерникова // Материалы 7-й всероссийской мультиконференции по проблемам управления -Ростов-на-Дону: Издательство Южного федерального университета, 2015. Т.З. - С. 130-134.

В совместных работах автором получены следующие результаты: в работе [2] разработан общий подход к организации битовой обработки данных на РВС; в [5] сформулирован и доказан ряд теорем; в [7] показана программная реализация задачи ЦОС.

Подписано к печати_. 10.2015 г.

Формат 60х84"16. Бумага офсетная. Печать ризография. Усл. п.л. - 1,25. Уч.-изд.л. - 1,15.

Заказ № -/09 Тираж 130 экз.

Отпечатано в Секторе обеспечения полиграфической продукцией в г.Таганроге отдела полиграфической, корпоративной и сувенирной продукции ИПК КИБИ МЕДИА ЦЕНТРА ЮФУ ГСП 17А, г.Таганрог, 28, Энгельса, 1 тел.(8634)371717