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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   Личный вклад автора. Все научные результаты получены автором лично.

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

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

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

   

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

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

   

   Математическое и программное обеспечение географических информационно-аналитических систем регионального уровня : На примере Красноярского краяПесегов Дмитрий Александрович

   Принципы построения и реализации базового уровня кластерной операционной системы КЛОСКопытов, Герман Васильевич

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

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

   

   Разработка препроцессора подготовки данных для комплексов конечноэлементного моделирования контактных систем Вдовиченко Антон Александрович

   

   Разработка синтаксических анализаторов языков программирования с учетом контекстных условий Зо Зон Су 0

   Унифицированная реализация системы типов языка программирования баз данныхКоситов, Валерий Александрович

   Системы автоматизации построения трансляторов и их применение для эффективной реализации языков программированияСеребряков, Владимир Алексеевич