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

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

Коваленко Алексей Геннадьевич

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

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

Автореферат

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

Таганрог-2013

005532060

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

НАУЧНЫЙ РУКОВОДИТЕЛЬ: Левин Илья Израилевич,

доктор технических наук, профессор кафедры ИМС, НИИ МВС ЮФУ, заместитель директора по науке

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ: Кравченко Павел Павлович,

доктор технических наук, профессор, ЮФУ, заведующий кафедрой

Иванов Андрей Игоревич, кандидат технических наук, в.ч. 26165, заместитель командира

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

унитарное предприятие «Научно-исследовательский институт «Квант» (ФГУП «НИИ «КВАНТ», г. Москва)

Защита диссертации состоится "28" июня 2013 г. в 1420 на заседании диссертационного совета Д 212.208.24 при Южном федеральном университете по адресу: г. Таганрог, ул. Чехова, 2, корп. "И", комн. 347.

С диссертацией можно ознакомиться в зональной научной библиотеке ЮФУ по адресу: г. Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан мая 2013 г.

Просим Вас прислать отзыв, заверенный печатью учреждения, по адресу: 347928, г. ТагаНро1г^гг^остовская область, ГСП-17А, пер. Некрасовский, 44, Технологический Институт Южного федерального университета в г. ТагаНроге, Ученому секретарю диссертационного совета Д 212.208.24 КухаренкоАнатолию Павловичу .Л-;

Ученый секретарь!"^ J-диссертационного совета

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

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

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

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

Для программирования реконфигурируемых систем используются языки описания аппаратуры (языки HDL-группы) и системные средства фирм-изготовителей ПЛИС, которые предназначены для создания однокристальных прикладных программ, поэтому разработка и отладка задач, требующих использования нескольких ПЛИС, занимает длительное время, достигая нескольких месяцев. Для высокоуровневого программирования РВС в качестве альтернативы языкам HDL-группы также применяются системы, которые используют синтаксис и семантику языка программирования С (Catapult С, Mitrion-C, Impulsée, Handie-C) для создания в ПЛИС виртуальных процессов или наложения на ПЛИС промежуточных архитектурных решений, что значительно снижает реальную производительность РВС.

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

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

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

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

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

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

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

1) проведен анализ методов и средств описания параллельных вычислений для РВС;

2) разработан метод преобразования параллельно-конвейерных программ к структурной или мультипроцедурной реализации вычислений в соответствии с архитектурной и конфигурацией РВС;

3) разработан метод преобразования параллельно-конвейерных программ для РВС, содержащих большое число условных операторов;

4) разработан метод преобразования параллельно-конвейерных программ для РВС, соответствующих связанным изоморфным информационным подграфам;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- «Модульно-наращиваемая многопроцессорная вычислительная система с программируемой архитектурой на основе реконфигурируемой элементной базы», итоговый отчет об ОКР, № ГОс. per. 0122.0510630, инв. № 0220 0601017 Таганрог, НИИ МВС ТРТУ, 2006 г.;

- «Создание семейства высокопроизводительных многопроцессорных вычислительных систем с динамически перестраиваемой архитектурой на основе реконфигурируемой элементной базы и их математического обеспечения для решения вычислительно трудоемких задач», итоговый отчет об ОКР, № гос. per. 01.2.007 05707, инв. № 0220.0900079, Таганрог, НИИ МВС ЮФУ, 2007 г.;

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

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

«Разработка теоретических основ построения

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

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

Апробация работы. Основные результаты, представленные в диссертации докладывались и обсуждались на всероссийских и международных научно-технических конференциях: III, IV, VI, VII, VIII, IX ежегодных научных конференциях студентов и аспирантов базовых кафедр ЮНЦ РАН Росгов-на

НЗуЧН0Й конФеРенции «Научный сервис в сети ИНТЕРНЕТ», Москва, 2007 г., 2009 г.; международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы -¿007», Таганрог, 2007 г.; международной молодежной научно-технической конференции и Петой международной молодежной школе «Высокопроизводительные вычислительные системы (ВПВС-2008)», Таганрог 2008 г.; международной научно-технической конференции «Суперкомпьютеры^ технологии (СКТ-2010)» и Седьмой международной научной молодежнойХле «Высокопроизводительные вычислительные системы», С. Дивномопское Геленджик, 2010 г, 2-ой Всероссийской научно-техн'ической коГфере™

«Суперкомпьютерные технологии (СКТ-2012)», с. Дивноморское, Геленджик, Личный вклад автора. Все научные результаты получены автором

лично.

оабот X „Г о ГУ аТаМ ДНСССртацИИ имсется 27 опубликованных работ, из них 9 статей, из которых 3 статьи опубликованы в ведущих

рецензируемых научных журналах, входящих в Перечень ВАК РФ тезисы и

материалы 7 докладов на международных и российских научнотехнических

конференциях По теме исследования получено 3 свидетельства о

8 о™^ГнИОКреГИСТРаЦИИ ПР0ГРЗММ "" ЭВМ' РСЗуЛЬтаТЫ Работы осажены в

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

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

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

>и ГЛаВ.

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

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

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

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

Для построения препроцессора языка СОЬАМО определены принципы его функционирования:

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

- принцип выбора организации вычислений: выбор более эффективной организации вычислений (структурной или мультипроцедурной) для РВС в случае наличия неявного типа вычислений, в описании которых используется

конструкция языка , Implicit, и условных операторов осуществляется автоматически препроцессором;

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

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

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

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

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

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

COLAMO и эквивалентный ей информационный граф. Здесь и далее вычислительные блоки, реализуемые структурно, показаны кружками, а блоки, реализуемые процедурно, - квадратиками. Описание подкадров А и С опущено.

X,

Gi

•—ч

V)

var x,y: array integer [n:stream] mem; var cl,c2 : integer com; var i: number;

Define B is SubCadr; Implicit B(in; bin; out: bout);

_ _G2 y

varx.y: array integer [n:stream] mem; var c3 : array integer [m+1 -.vector] com; var ij: number;

Define B is LocalProc » MB; Implicit B(in: bin; out: bout);

Endlmplicit; Cadr CadrGl for i:=0 to n-1 do begin A(x[i],cl); B(cl,c2); C(c2,y[i]); end; EndCadr;

Endlmplicit; Cadr CadrG2 for i:=0 to n-I do begin A(x[i],c3[0]);

for j:-l to m do

B(c3[i'l],c3[j]); C(c3[m],y[i]); end; EndCadr; a) 6)

a) - структурная реализация; б) - мультипроцедурная реализация Рис. 1. Реализации информационного графа задачи F

В условиях ограниченного аппаратного ресурса подграф В необходимо реализовать мультипроцедурно: используется конструкция LocalProc. Результат преобразования показан на рис. 1-6. В этом случае скважность операндов определяется количеством тактов, необходимых для выполнения процедуры. Увеличить скорость обработки данных можно за счет организации вычислений по схеме макроконвейера. В этом случае скважность операндов sm определяется по формуле

=

где tp - количество тактов, необходимых процедуре для обработки одного данного, т - количество процессорных элементов, ][ - операция округления в большую сторону.

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

Q* = q + Q(GP),

где q - ресурс, необходимый для структурной реализации подграфа, не входящего в конструкцию Implicit, Q(Gp) - ресурс, занимаемый одним процедурным блоком Gp.

Р., Структурно

Мультипроцедурно

Э 20"

а) б)

а) - график зависимости при 5<£>; б) - график зависимости при Рис. 2. Графики зависимости производительности Р РВС от ее аппаратного ресурса К для структурной и мультипроцедурной организаций вычислений

При увеличении ресурса системы Я до значения £)

е = * +

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

После достижения значения £> увеличение числа параллельных процедур не имеет смысла: производительность остается постоянной, несмотря на увеличение ресурса РВС. В то же время при увеличении ресурса системы его может оказаться достаточно для структурной реализации всей задачи На графиках, приведенных на рис. 2-а, на участке АВ эффективнее мультипроцедурная реализация, а на участке СИ - структурная. На графиках, приведенных на рис. 2-6, выгоднее мультипроцедурная реализация, и лишь на участке С£> структурная реализация незначительно превалирует.

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

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

р_ Ь + ЫЩ + к-НЩ

Ь + 2* • ЩЛ + (2* -1) • (МЛ) + ЩМ))' где Ь - число функциональных узлов, не входящих в условный оператор, к-степень вложенности условного оператора, N0 - число вычислительных устройств, необходимых для реализации вычислений соответствующей функции, /- функция, соответствующая одной из альтернативных ветвей,/с - усредненная функция вычисления логических выражений, ЩМ) - число дополнительных вычислительных устройств, которые необходимы для реализации переключателя.

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

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

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

Разработан метод преобразования параллельно-конвейерных программ, содержащих связанные изоморфные информационные подграфы. В настоящее время пользователь вынужден самостоятельно перерабатывать фрагменты программ и определять глубину обратной связи для организации вычислений по схеме конвейера конвейеров. Показано, что в условиях ограниченного ресурса РВС информационный граф задачи в, который состоит из связанных изоморфных подграфов V, реализуется в виде одного подграфа V с организацией обратной связи. Если граф задачи Н представляет собой совокупность изоморфных подграфов в и оборудования системы достаточно для реализации р (р<п) подграфов в, то предварительно над исходным графом задачи выполняется операция конвейеризации. На рис. 3-а показан результат конвейеризации. Если ресурса РВС не хватает для реализации даже одного подграфа в, но достаточно для реализации д (ч<п) подграфов V, то организовать вычисления можно с помощью реализации единственного подграфа V с обратной связью, выполнив распараллеливание подграфа К^раз (рис. З-б). Однако такой подход не является эффективным, поскольку не позволяет подавать новое данное на вход вычислительной структуры до поступления результата обработки предыдущего данного.

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

с! '

где (1 - латентность подграфа V, пг - количество регистров в обратной связи. С точки зрения удельной производительности максимальное значение достигается, когда число регистров в обратной связи равно латентности подграфа V.

var x, y : array integer

[p: vector, m/p : stream] mem;

var xc : array integer

[p : vector, n+1: vector] com;

var i, j, k : number;

var x, y ; array integer [q ; vector, m/q ; stream] mem;

var xc, yc ; array integer [q : vector] com;

var zcl,zc2 : array integer [q ; vector, m/q : stream,

n: stream] com; var i, j, k: number;

Cadr CadrG for к;=0 to p-1 do begin for i;=0 to m/p-1 do begin xc[k, 0]; =x[k, i]; for j:-l to n do

xc[k,j]-~v(xc[kj-l]); y[k,i];=xc[k,n]; end; end; EndCadr;

a)

a)-

Cadr CadrV for k:=0 to q-1 do begin for i;=0 to m/q-1 do begin xc[k]: —x[k, i]; forj;=0 to n-1 do begin

ifj=0then zcl[k,ij];=xc[k]; else zcl[k,ij];=zc2[k,i-l,j];

zc2[k, ijj: =v(zcl[k, i,j]); yc[k]~zc[k,ij]; end;

yfk,i];=ycfk]; end; end; EndCadr;

6)

структурная реализация p подграфов G; б) - реализация q подграфов V Рис. 3. Реализации информационного подграфа//

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

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

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

var х, у : array integer [т/Ы: stream,

r-d: stream] mem; var xc, yc ; integer com; var zc : array integer [m/r-d: stream,

rd: stream, n/r : stream, r+1: vector] com; var i, j, k, h : number;

Cadr CadrQ

for i:=0 to m/r d-1 do begin

for j:-0 to r d-1 do begin xc;=xfij];

________for k:=0 to n/r-1 do begin

ifk~0 then zcfij, к, 0]: ~xc; else begin zc[ij,k,0]:=zc[i,j-r d,k,r]; for h:=l to r do

zc[ij, k, h]: =v(zc[ij, k,h-l]); end; yc:=zcfij,k,rj; end; y[ij];=yc; end; end; EndCadr;

Рис. 4. Реализация г подграфов Fno схеме конвейера конвейеров

В третьей главе разработаны общая схема взаимодействия препроцессора с ?П™РГ язык* COLAMO (рис. 5-а) и струюура препроцессора языка CULAMU (рис. 5-6), отличающаяся от известных наличием расширяемой библиотеки процедур д тя автоматического преобразования программ. Разработан сообщенный алгоритм анализа операторов, полученных в результате работы лексического и синтаксического анализаторов.

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

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

а)

6}

а) - общая схема взаимодействия препроцессора с транслятором языка СОЬАМО; б) - обобщенная структура препроцессора языка СОЬАМО Рис. 5. Схема взаимодействия и структура препроцессора языка СОЬАМО

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

Для задачи томографического исследования приповерхностных слоев Земли акустическими и электромагнитными волнами применение препроцессора языка СОЬАМО позволило сократить время портации исходной программы в 4 раза. Трансляция программы, описывающей вычислительную структуры задачи, на плату РВС «Алькор» позволила реализовать один подграф, выполняющий один шаг итерационной схемы решения СЛАУ (рис. 6-а), по схеме конвейера конвейеров. Портация программы на плату РВС «Ригель» (рис. 6-6), ресурс которой позволил реализовать 15 таких подграфов, увеличила реальную производительность при решении задачи в 2,5 раза.

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

Для задачи диагностики дорожных покрытий и аэродромных взлетно-посадочных полос применение препроцессора языка СОЬАМО позволило сократить время портации исходной программы в 1,2 раза.

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

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

а) - на плате РВС «Алькор»; б) - на плате РВС «Ригель» Рис. 6. Реализация задачи томографического исследования слоев Земли

marker

16 ПЛИС \Zirtex-5, 8 млн. вентилей 256 элементарных процессоров (1ЕЕЕ-754)

Пиковая производительность 85 Гфлопс Реальная производительность 64 Гфлопс

8 ПЛИС УИех-6, 24 млн. вентилей 512 элементарных процессоров (1ЕЕЕ-754) Пиковая производительность 200 Гфлопс Реальная производительность 162 Гфлопс

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

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

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

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

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

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

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

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

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

1. Коваленко, А.Г. Макроконвейерная реализация алгоритмов аутентификации на языке высокого уровня COLAMO [Текст] / А.Г. Коваленко // Известия ЮФУ. Технические науки. - Таганрог: Изд-во ТТИ ЮФУ, 2012. - JV«4 -С. 210-215 (ведущий рецензируемый журнал, входит в перечень ВАК);

2. Коваленко, А.Г. Оптимизация информационного графа задачи для ассоциативных операций с помощью препроцессора языка COLAMO [Текст] / А.Г. Коваленко, И.И. Левин, В.А. Гудков // Вестник компьютерных и информационных технологий. - М.: Машиностроение, 2013. - №1. - С. 47-51

(ведущий рецензируемый журнал, входит в перечень ВАК);

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

4. Коваленко, А.Г. Решение обратной задачи диагностики дорог на реконфшурируемой вычислительной системе с применением языка COLAMO [Текст] / А.Г. Коваленко, С.Л. Овчинников, С.Ю. Романов // Труды Всероссийской суперкомпьютерной конференции «Научный сервис в сети ИНТЕРНЕТ: масштабируемость, параллельность, эффективность» - М-Изп-во МГУ, 2009.-С.217-223; ' Д

5. Коваленко, А.Г. Решение задачи томографии приповерхностных слоев земли с использованием языка COLAMO на реконфшурируемой вычислительной системе [Текст] / А.Г. Коваленко, Е.Е. Семерникова // Материалы Международной научно-технической конференции «Суперкомпьютерные технологии: разработка, программирование, применение (СКТ-2010)» Т2 -

Таганрог: Изд-во ТТИ ЮФУ, 2010. - С.207-211;

6. Коваленко, А.Г. Процедура автоматического преобразования параллельно-конвейерных программ для реконфигурируемых вычислительных систем [Текст] / А.Г. Коваленко И Материалы 2-й Всероссийской научно-техническои конференции «Суперкомпьютерные технологии (СКТ-2012)» Ростов-на-Дону: Изд-во Южного федерального университета, 2012. - С. 120-125;

7. Коваленко, А.Г. Оптимизации информационного графа задачи содержащего ассоциативные операции, с использованием препроцессора транслятора языка COLAMO [Текст] / А.Г. Коваленко // Высокопроизводительные вычислительные системы: Сборник научных трудов Выпуск 2. - Таганрог: Изд-во ЮФУ, 2012. - С. 33-37.

8. Коваленко, А.Г. Автоматический выбор эффективной организации вычислений при использовании конструкции Implicit для реконфигурируемых вычислительных систем [Текст] / А.Г. Коваленко // Сборник научных трудов по материалам Международной научно-практической конференции «Современные тенденции в образовании и науке». - Тамбов: Изд-во ТРОО «Бизнес-Наука-Общество», 2013. - Часть 3. - С.81-86;

9. Коваленко, А.Г. Автоматический выбор эффективной организации вычислений при решении задач, содержащих большое число условных операторов, для реконфигурируемых вычислительных систем [Текст] / А.Г. Коваленко // Сборник научных трудов по материалам Международной научно-практической конференции «Образование и наука: современное состояние и перспективы развития». - Тамбов: Изд-во ТРОО «Бизнес-Наука-Общество», 2013 - Часть 3,-С. 91-97.

10. Коваленко, А.Г. Программа обработки данных томографического исследования приповерхностных слоев Земли акустическими и электромагнитными волнами на реконфигурируемых вычислительных системах / А.Г. Коваленко, И.И. Левин // Свидетельство об официальной регистрации программы для ЭВМ № 2009612743, РФ. Зарегистр. в Реестре программ для ЭВМ 10.09.2009 г. Правообладатель: НИИ МВС ЮФУ;

11. Коваленко, А.Г. Программа обработки данных диагностики дорожных покрытий и аэродромных взлетно-посадочных полос на реконфигурируемых вычислительных системах / А.Г. Коваленко, И.И. Левин // Свидетельство об официальной регистрации программы для ЭВМ № 2009615979, РФ. Зарегистр. в Реестре программ для ЭВМ 28.10.2009 г. Правообладатель: НИИ МВС ЮФУ;

12. Коваленко, А.Г. Препроцессор транслятора языка COLAMO для реконфигурируемых вычислительных систем / А.Г. Коваленко, И.И. Левин, В.А. Гудков // Свидетельство о государственной регистрации программы для ЭВМ № 2013611485, РФ. Зарегистр. в Реестре программ для ЭВМ 22.01.2013 г. Правообладатель: Южный федеральный университет.

В совместных работах автором получены следующие результаты: в работе [2] разработан метод преобразования программ, содержащих последовательность ассоциативных операций, в случае количества источников данных, не кратного степени двойки; в [3] разработан метод преобразования программ, содержащих связанные изоморфные информационные подграфы; в [4] представлены результаты реализации на реконфигурирусмой вычислительной системе задачи диагностики дорожных покрытий; в [5] разработан общий алгоритм реализации задачи томографического исследования приповерхностных слоев Земли на реконфигурируемой вычислительной системе.

ЛР №020565 от 23 июня 1997г. Подписано к печати ¿/.05.2013 г. Формат 60x84"". Бумага офсетная. Печать офсетная. Усл. п.л. -1,4. Уч.-издл. -1,1.

Заказ Тираж 130 экз.

ГСП 17А, Таганрог, 347928, Некрасовский, 44 Типография Технологического института Южного федерального университета в г. Таганроге

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Южный федеральный университет»

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

КОВАЛЕНКО АЛЕКСЕЙ ГЕННАДЬЕВИЧ

ПРЕПРОЦЕССОР ЯЗЫКА ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ ДЛЯ РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ

СИСТЕМ

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

ДИССЕРТАЦИЯ НА СОИСКАНИЕ УЧЕНОЙ СТЕПЕНИ КАНДИДАТА ТЕХНИЧЕСКИХ НАУК

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

доктор технических наук Левин И.И.

Таганрог - 2013 г.

СПИСОК СОКРАЩЕНИЙ

МВС - многопроцессорная вычислительная система

РВС - реконфигурируемая вычислительная система

ПЛИС - программируемая логическая интегральная схема

ЭП - элементарный процессор

ЭВМ - электронная вычислительная машина

ЯПФ - ярусно-параллельная форма

СОДЕРЖАНИЕ

стр.

ВВЕДЕНИЕ 5

1. МЕТОДЫ И СРЕДСТВА ПРОГРАММИРОВАНИЯ РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ 18

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

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

1.3. Язык программирования высокого уровня COLAMO 37

1.4. Препроцессоры 42

1.5. Принципы построения и задачи препроцессора языка COLAMO 46

1.6. Выводы 50

2. МЕТОДЫ ПРЕОБРАЗОВАНИЯ ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНЫХ ПРОГРАММ ДЛЯ РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ 52

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

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

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

2.4. Метод преобразования параллельно-конвейерных программ, содержащих последовательность ассоциативных операций 86

2.5. Выводы 94

3. СТРУКТУРА И АЛГОРИТМЫ ПРЕПРОЦЕССОРА ЯЗЫКА COLAMO 96

3.1. Общая структура препроцессора 97

3.2. Команды препроцессора 101

3.3. Алгоритмы препроцессора языка COLAMO 105

3.3.1. Алгоритм автоматического преобразования текста параллельной программы при использовании конструкции Implicit 105

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

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

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

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

3.5. Выводы 117 4. РЕШЕНИЕ ПРИКЛАДНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ ПРЕПРОЦЕССОРА ЯЗЫКА COLAMO 119

4.1. Реализация задачи томографического исследования приповерхностных слоев Земли акустическими и электромагнитными волнами 119

4.2. Реализация задачи оптимизации расхода топлива турбовинтовентиляторного двигателя 137

4.3. Реализация задачи диагностики дорожных покрытий и аэродромных взлетно-посадочных полос 147

4.4. Выводы 156 ЗАКЛЮЧЕНИЕ 158 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 160 ПРИЛОЖЕНИЕ. Акты о внедрении результатов диссертации 172

ВВЕДЕНИЕ

Актуальность темы. Научно-технический прогресс требует все более высоких вычислительных мощностей от современных многопроцессорных вычислительных систем, способных решать сложные задачи за приемлемое время. Дешевизна составных компонентов и высокий уровень развития средств и методов программирования универсальных процессоров сделали популярными кластерные многопроцессорные системы [1, 2], узлы которых построены по классической фон-неймановской архитектуре. Однако практика показала, что использование в решении задачи большого числа процессоров кластерных систем не только не приводит к линейному росту производительности системы, но и зачастую значительно увеличивает время решения даже по сравнению с использованием однопроцессорной вычислительной системы. В особенности это характерно для сильносвязанных задач, для которых число межпроцессорных обменов информацией, необходимых для корректного решения задачи, соизмеримо или даже превышает собственно вычисления. В итоге производительность кластерных систем не превышает 10-20% от заявленной пиковой производительности.

Указанного недостатка лишены реконфигурируемые вычислительные системы (РВС) [3, 4]. Адаптация архитектуры таких систем под вычислительную структуру решаемой задачи позволяет достигать высоких показателей производительности, которые для некоторых классов задач превышают 90% от значения пиковой производительности.

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

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

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

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

Для программирования РВС в настоящее время используются языки описания аппаратуры, так называемые языки НОЬ-группы [6, 7]. Подобные языки ориентированы больше на схемотехников, чем на программистов. Имеющиеся у фирм-изготовителей ПЛИС системные средства предназначены для создания однокристальных проектов, поэтому разработка и отладка задач, требующих использования нескольких ПЛИС, занимает длительное время, достигая нескольких месяцев.

Для высокоуровневого программирования РВС в качестве альтернативы языкам НОЬ-группы также используются системы

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

Особую позицию в системах программирования РВС занимает язык высокого уровня COLAMO [4, 10]. Программист с помощью конструкций языка описывает виртуальный информационный граф задачи, который транслируется на уровень логических ячеек ПЛИС синтезатором Fire ¡Constructor, поддерживающим укладку элементов графа между несколькими ПЛИС [11]. В языке COLAMO отсутствуют явные формы описания параллелизма. Язык позволяет быстро и просто описывать различные параллельно-конвейерные организации вычислений.

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

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

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

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

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

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

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

1) проведен анализ методов и средств описания параллельных вычислений для РВС;

2) разработан метод преобразования параллельно-конвейерных программ к структурной или мультипроцедурной реализации вычислений в соответствии с архитектурой и конфигурацией РВС;

3) разработан метод преобразования параллельно-конвейерных программ для РВС, содержащих большое число условных операторов;

4) разработан метод преобразования параллельно-конвейерных программ для РВС, соответствующих связанным изоморфным информационным подграфам;

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

6) выполнен анализ эффективности реализации задач различных предметных областей.

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

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

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

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

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

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

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

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

Использование результатов работы. Материалы диссертации использовались при выполнении ряда НИОКР, среди которых можно выделить следующие:

- «Модульно-наращиваемая многопроцессорная вычислительная система с программируемой архитектурой на основе реконфигурируемой элементной базы», итоговый отчет об ОКР, № гос. per. 0122.0510630, инв. № 0220.0601017,Таганрог, НИИ МВС ТРТУ, 2006 г.;

- «Создание семейства высокопроизводительных многопроцессорных вычислительных систем с динамически перестраиваемой архитектурой на основе реконфигурируемой элементной базы и их математического обеспечения для решения вычислительно трудоемких задач», итоговый отчет

об ОКР, № гос. per. 01.2.007 05707, инв. № 0220.0900079, Таганрог, НИИМВСЮФУ, 2007 г.;

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

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

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

Апробация работы. Основные результаты, представленные в диссертации, докладывались и обсуждались на всероссийских и международных научно-технических конференциях: III, IV, VI, VII, VIII, IX ежегодных научных конференциях студентов и аспирантов базовых кафедр ЮНЦ РАН, Ростов-на-Дону; всероссийской научной конференции «Научный сервис в сети ИНТЕРНЕТ», Москва, 2007 г., 2009 г.; международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы - 2007», Таганрог, 2007 г.; международной молодежной научно-технической конференции и Пятой международной молодежной школе «Высокопроизводительные вычислительные системы (ВПВС-2008)», Таганрог, 2008 г.; международной научно-технической конференции «Суперкомпьютерные технологии (СКТ-2010)» и Седьмой международной научной молодежной школе «Высокопроизводительные вычислительные системы», с. Дивноморское, Геленджик, 2010 г.; 2-ой

Всероссийской научно-технической конференции «Суперкомпьютерные технологии (СКТ-2012)», с. Дивноморское, Геленджик, 2012 г.

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

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

2. Коваленко, А.Г. Оптимизация информационного графа задачи для ассоциативных операций с помощью препроцессора языка COLAMO [Текст] / А.Г. Коваленко, И.И. Левин, В.А. Гудков // Вестник компьютерных и информационных технологий. - М.: Машиностроение, 2013. - №1. - С. 47-51 (ведущий рецензируемый журнал, входит в перечень ВАК);

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