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

Содержание к диссертации

Введение

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

1.1. Реконфигурируемые вычислительные системы 19

1.2. Языки программирования реконфигурируемых вычислительных систем

1.3. Методы работы с битами и принципы организации систем работы с битовыми операциями

1.4. Принципы модернизации языка COLAMO для битовой обработки данных

1.5. Выводы 52

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

2.1. Параллельный и последовательный доступ к битам 54

2.2. Сопряжение битовых структур с элементами памяти 61

2.3. Сопряжение с конструкциями языка COLAMO и условным оператором

2.4. Алгоритмы трансляции битовых конструкций 77

2.5. Выводы 84

3. Методы работы с виртуальными битовыми структурами 87

3.1. Построение арифметических устройств переменной разрядности 88

3.2. Методы контекстного определения разрядностей и типов макроопераций

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

3.4. Алгоритмы трансляции виртуальных битовых конструкций 113

3.5. Выводы 120

4. Утилита транслятора языка COLAMO 122

4.1. Общая структура утилиты транслятора языка COLAMO 124

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

4.3. Реализация КИХ-фильтра на РВС с использованием утилиты транслятора языка СOLAMO

4.4. Реализация задачи цифрового диаграммоформирования с 137

использованием утилиты транслятора языка СOLAMO

4.5. Реализации хэш-функции с использованием утилиты транслятора языка СOLAMO

4.6. Выводы 150

Заключение 152

Список использованных источников 154

Приложение 1 164 Приложение 2 170

Приложение 3 178

Приложение 4 1

• Языки программирования реконфигурируемых вычислительных систем
• Сопряжение битовых структур с элементами памяти
• Методы контекстного определения разрядностей виртуальных битовых конструкций
• Использование утилиты транслятора языка COLAMO в интегрированной среде разработки прикладных программ

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

Актуальность темы исследования. В настоящее время широкое

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

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

Реконфигурируемые вычислительные системы (РВС) на базе

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

Несмотря на указанные достоинства, затруднительным остается процесс
программирования РВС, особенно для алгоритмов переменной разрядности.
Программирование РВС с использованием высокоуровневых систем

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

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

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

уровнем параллелизма. Системные средства, предоставляемые фирмами-

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

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

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

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

реконфигурируемых вычислительных систем.

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

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

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

1. провести анализ методов и средств разработки параллельных программ для РВС;

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

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

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

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

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

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

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

параллельного программирования, основы теории множеств и теории графов.

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

вычислительных системах последних поколений.

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

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

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

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

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

4. новые алгоритмы трансляции битовых конструкций языка программирования высокого уровня COLAMO;

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

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

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

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

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

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

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

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

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

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

На основании предложенных методов и алгоритмов создана утилита
транслятора языка программирования высокого уровня COLAMO для

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

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

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

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

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

– «Разработка методов и инструментальных систем для анализа эффективности
работы параллельных программ и суперкомпьютеров», отчет о НИР,

№ гос. рег. И110519102540, Таганрог, НИИ МВС ЮФУ, 2012 г.;

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

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

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

– «Разработка и исследование технологии создания ресурсонезависимого прикладного программного обеспечения высокопроизводительных вычислительных систем гибридного типа», отчет о НИР, № гос. рег. 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 «Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей», технические науки.

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

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

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

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

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

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

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

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

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

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

Сопряжение битовых структур с элементами памяти

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

В языке COLAMO переменные разделяются по способу хранения на мемориальные, хранящиеся во внешней памяти (Mem), коммутационные (Com), регистровые (Reg) и хранящиеся во внутренней памяти (InterMem) [47].

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

Для преобразования 32-разрядных слов к битовым массивам произвольной длины при чтении из памяти и обратно (преобразование битовых массивов к словам при записи в память) требуется преобразование данных на уровне приведения разрядности , (2.1) где N – это размерность битового массива, M – разрядность памяти, а P – коэффициент приведения разрядности. В случае, когда данные из мемориальной переменной необходимо преобразовать в битовый массив размерностью 19 битов (рис. 2.13). Расчёт коэффициента приведения разрядности по формуле (2.1) составит

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

Фрагмент программы чтения из внешней памяти 32-разрядных данных и записи их в битовый массив (а); информационный граф чтения из внешней памяти 32-разрядных данных и записи их в битовый массив (б) При этом параметру « » соответствует срезу всех доступных бит, которые читаются из внешней памяти. Такая запись порождает неявный вызов функций Separate [66], скрытый от пользователя, который выполняет разложение всех доступных бит 32-разрядного в коммутационный битовый массив (рис. 2.13-б).Для чтения данных из внешней памяти в битовый массив размерностью 47 бит, то есть преобразование с увеличением разрядности, расчет коэффициента приведения по формуле (1) составит

Фрагмент программы чтения из внешней памяти 32-разрядных данных и записи их в битовый массив (а); информационный граф чтения из внешней памяти 32-разрядных данных и записи их в битовый массив (б) При записи битовых массивов произвольной размерности во внешнюю память происходят обратные преобразования. Битовые массивы объединяются в 32-разрядные слова, однако, коэффициент приведения разрядности рассчитывается аналогичным образом, что и при чтении, по формуле (2.1).

Для записи во внешнюю память битового массива размерностью памяти по 32 бита. При этом в пустующие старшие разряды будут записаны нули. Количество лидирующих нулей L будет определяться по формуле: Фрагмент программы записи во внешнюю память битового массива с размерностью меньшей разрядности памяти (а); информационный граф записи во внешнюю память битового массива с размерностью меньшей разрядности памяти (б) Так, для записи во внешнюю память битового массива размерностью 47 битов, превышающую разрядность памяти, коэффициент приведения составит . Это означает, что каждому элементу массива A на (рис. 2.16-а) будут 19 битов, которая меньше разрядности памяти, коэффициент приведения составит будет соответствовать 1 ячейка соответствовать две ячейки памяти по 32 бита. При этом в пустующие старшие разряды будут записаны нули. Количество лидирующих нулей L будет определяться по формуле (2.2) и составит 17.

Фрагмент программы записи во внешнюю память битового массива с размерностью превышающей разрядность памяти (а); информационный граф записи во внешнюю память битового массива с размерностью, превышающей разрядность памяти (б) При этом параметру « » принадлежит срез всех доступных битов, который передается во внешнюю память. Такая запись порождает неявный вызов функций Combine [66], скрытый от пользователя, который выполняет сборку всех доступных битов параметра « » в 32-разрядные слова в соответствии с коэффициентом приведения разрядности и расчётом количества лидирующих нулей (рис. 2.16-б).

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

Как было показано выше, для чтения из внешней памяти данных и записи их в битовый коммутационный массив неявно вызывается функция Separate (рис. 2.13-а, 2.14-а), которая выполняет разложение 32-разрядого значения мемориальной переменной на последовательность независимых битов. Обращение к полученному набору битов будет осуществляться через параметр « ». Так как в объявлении переменной B указывается параллельная обработка битов, то для присвоения ей последовательности битов переменной А не требуется никакого дополнительного оборудования (рис. 2.17).

Методы контекстного определения разрядностей виртуальных битовых конструкций

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

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

Пусть ==Q, где Q M. Как было доказано в теореме 3.1: если M _ операция сложения/вычитания, то для гарантированного получения разрядности результата на уровне заданной точности необходимо выполнение —JV условия Q=M, если M - операция умножения, то для гарантированного получения разрядности результата на уровне заданной точности необходимо выполнение условия 2Q=M, отсюда следует, что Q= — . Случай Q M противоречит решаемой в диссертации научной задаче, так как использование аппаратно-реализованных блоков (соответствующих макрооперации) с избыточной разрядностью будет неизбежно вести к снижению удельной производительности решаемой задачи в целом.

Разрядность принимающего массива должна удовлетворять следующему требованию: М. Для доказательства этого утверждения воспользуемся методом от противного. Предположим, что М, тогда M-=R - разница в битах. Так как R 0, то размерность принимающего виртуального битового массива будет на R меньше разрядности полученного результата М, что приведет к потере данных. Таким образом, для корректного хранения результата макрооперации необходимо, чтобы P=0, но это противоречит исходному утверждению P 0.

Таким образом, следствие доказано. На рис. 3.30 приведен пример работы с масштабирующей операцией умножения двух виртуальных битовых массивов с записью результата также в виртуальный битовый массив. Фрагмент программы и эквивалентный ей информационный граф использования масштабирующей операции сложения для виртуальных битовых массивов Использование виртуальных битовых массивов в условном операторе, реализуемом структурно, также имеет свои особенности. При структурной реализации условного оператора аппаратно конфигурируются все его альтернативные ветви If Then F Else G, где F и G – множество альтернативных операторов, а - логическое выражение. Операторы множества F выполняются, если истинно логическое выражение , иначе - выполняются операторы множества G.

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

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

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

If then := N Else := M , где - виртуальный битовый массив, - потенциальная разрядность виртуального битового массива, и - битовые массивы, разрядность которых равна N и М соответственно

= & N & М . Виртуальный битовый массив в зависимости от логического выражения может получить значения размерностью и N, и М данных. Для того чтобы избежать потери данных при записи большего количества данных в массив меньшей размерности, необходимо установить размерность массива , равной максимальному значению размерности записываемого битового массива из всех возможных, то есть =Max(N, М) (рис. 3.31). то в таком случае необходимо с одной стороны сформировать разрядность виртуального битового массива N, а с другой стороны М, однако учитывая тот факт, что аппаратно реализуется каждая альтернативная ветка условного оператора, необходимо объединить эти ограничения по разрядности в одно. Таким образом, результирующая разрядность виртуального битового массива будет равной Min(N, М) (рис. 3.32).

Одной из основных конструкций языка COLAMO является подкадр (SubCadr) [49]. При вызове конструкции SubCadr в тексте программы в информационном графе в точке вызова подкадра происходит добавление соответствующего информационного подграфа.

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

Виртуальный подкадр является гибким инструментом, который позволяет использовать одно и то же тело подкадра для обработки данных различной разрядности (см. рис. 3.33). Так, в приведенном выше примере один и тот же виртуальный подкадр Calc осуществляет масштабируемое арифметическое сложение двух виртуальных битовых массивов и записывает результат также в виртуальный битовый массив. Однако при вызове Calc в теле кадра One в первом случае входные аргументы имеют разрядность 19 и 3 бита соответственно, а во втором случае – 19 и 6 битов. При этом разрядность аргументов дополняется до 19 разрядов нулями в старших битах, а разрядность результата, исходя из вышеизложенных правил, должна быть равна 19 битам.

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

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

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

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

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

Алгоритм SHA-1 [95,96] реализует хеш-функцию, которая осуществляет сжатие входной информации, разбитой на блоки, сообщения длиной 512 битов, при этом выход представляет собой 160-разрядное хэш-значение.

Исходное сообщение обрабатывается блоками по 512 битов в каждом. Последний блок необходимо дополнить до длины 512 бит, таким образом, что в конец сообщения присоединяется 1, а затем нули с тем, чтобы длина блока достигла значения 448 бит. Далее необходимо в оставшиеся 64 бита записать длину исходного сообщения в битах. Если длина последнего блока больше 448 битов, но меньше 512 битов, то необходимо выполнить следующее дополнение: для начала добавляется 1 в конец сообщения, а затем добавляются нули, пока длина блока не расширится до 512 битов. После этого формируется ещё один 512-битный блок, первые 448 битов которого заполняются нулями, а в остальные 64 бита записывается значение длины исходного сообщения в битах. Дополнение последнего блока выполняется в любом случае, даже если

Однако на рис. 4.18-а приведена реализация с использованием введенных битовых конструкций, а на рис. 4.18-б – в старой нотации языка. На данном примере показана особенность использования битовых массивов с возможностью управления способом обработки битов. На рис. 4.18-а каждый объявленный массив получил дополнительные измерения по битам, которые позволяют обрабатывать 32 бита не параллельно, как в предыдущей реализации на рис. 4.18-б, а последовательно-параллельно, при этом все возможные комбинации разбиения на группы параллельно обрабатываемых битов задаются параметрами N и M на этапе объявления массивов. Такой подход позволяет сократить и используемый аппаратный ресурс с замедлением темпа обработки данных.

Однако на рис. 4.18-а приведена реализация с использованием введенных битовых конструкций, а на рис. 4.18-б – в старой нотации языка. На данном примере показана особенность использования битовых массивов с возможностью управления способом обработки битов. На рис. 4.18-а каждый объявленный массив получил дополнительные измерения по битам, которые позволяют обрабатывать 32 бита не параллельно, как в предыдущей реализации на рис. 4.18-б, а последовательно-параллельно, при этом все возможные комбинации разбиения на группы параллельно обрабатываемых битов задаются параметрами N и M на этапе объявления массивов. Такой подход позволяет сократить и используемый аппаратный ресурс с замедлением темпа обработки данных.

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

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

2) Разработанный алгоритм контекстного определения разрядностей виртуальных переменных и вычислительных устройств позволяет на 7,5-10% сократить время создания прикладной параллельной программы с битовой обработкой данных на РВС для различных алгоритмов ЦОС.

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

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