Введение к работе
Актуальность темы исследования. Научно-технический прогресс диктует необходимость повышения реальной производительности вычислительных систем при решении все более усложняющихся научно-технических задач. С этой целью создаются и развиваются новые архитектуры вычислительных систем, так как фон-неймановские архитектуры уже не в состоянии обеспечивать неуклонный рост производительности. Комплексирование микропроцессоров не приводит к пропорциональному увеличению производительности из-за высоких накладных расходов, необходимых для организации параллельных вычислений. В этой связи более широкое распространение получают альтернативные варианты построения суперЭВМ. Принципиально новыми свойствами обладают реконфигурируемые вычислительные системы (РВС), в которых программируемые логические интегральные схемы (ПЛИС) используются не в качестве вспомогательных сопроцессоров, а как основной вычислительный ресурс для обработки информации. Вычислительные поля, построенные на основе множества ПЛИС и сегментов распределенной памяти, позволяют многократно повысить реальную производительность при решении научно-технических задач, в том числе, сильносвязанных задач, за счет адаптации структуры как отдельных ПЛИС к информационной структуре решаемой задачи.
Однако, несмотря на высокую потенциальную эффективность РВС, в настоящий момент отсутствуют удобные и в то же время эффективные средства их программирования. Для программирования реконфигурируемых вычислительных систем используются языки HDL-группы и системы параллельного программирования РВС (Catapult С, Mitrion-C). Для достижения высокой удельной производительности РВС при создании приложений используются языки HDL-группы, которые ориентированы не столько на программистов, сколько на схемотехников, что сдерживает широкое распространения реконфигурируемых вычислителей и приводит к длительным срокам создания прикладных программ. Системы параллельного программирования РВС типа Catapult С, Mitrion-C создают в ПЛИС виртуальные процессы, что значительно снижает реальную производительность РВС.
Для программирования РВС со структурно-процедурной организацией вычислений был разработан язык высокого уровня с неявным описанием параллелизма COLAMO. В связи с ограниченным ресурсом ПЛИС при программировании на COLAMO пользователю было необходимо разделять задачу на отдельные кадры, которые последовательно отображались на базовую архитектуру РВС путем ее перенастройки. В РВС заранее предусматривалось создание базовой архитектуры вычислителя, представляющего собой совокупность элементарных процессоров, подсистемы коммутационных связей между ними и контроллеров распределенной памяти, для обеспечения информационных потоков. Перенастройка базовой архитектуры выполнялась при смене кадров, каждый из которых представлял собой программно неделимый компонент, включающий в себя совокупность команд
элементарных процессоров, коммутаторов и контроллеров распределенной памяти. Версия языка программирования высокого уровня COLAMO позволяла оперативно создавать прикладные программы для решения задач различных предметных областей на РВС, однако использование базовых архитектур приводило к значительному снижению удельной производительности РВС по сравнению с приложениями, созданными на HDL-языках.
В настоящее время современные РВС имеют значительный аппаратный ресурс, что позволяет реализовать прикладные задачи в виде единственной вычислительной структуры, которая может быть отображена на вычислительное поле ПЛИС. В этой связи актуальными являются модернизация языка программирования высокого уровня и создание новых алгоритмов его трансляции для разработки параллельно-конвейерных программ для РВС, выполняемых с высокой удельной производительностью.
Объектом исследования являются методы и средства описания прикладных программ для реконфигурируемых вычислительных систем и алгоритмы трансляции.
Целью диссертационной работы является повышение удельной производительности РВС при выполнении прикладных программ, созданных на языке высокого уровня.
Научная задача состоит в создании методов и алгоритмов трансляции модернизированного языка программирования высокого уровня с неявным описанием параллелизма, обеспечивающих отображение прикладной задачи на реконфигурируемые вьшислительные системы на уровне логических ячеек ПЛИС, и, как следствие, повышающих удельную производительность РВС.
Для достижения поставленной цели необходимо решить следующие задачи исследования:
провести анализ методов и средств описания параллельных вычислений для РВС;
разработать принципы модернизации языка программирования высокого уровня для программирования ПЛИС на уровне логических ячеек;
разработать новые конструкции языка, отвечающие предложенным принципам;
формализовать правила трансляции с языка программирования высокого уровня с неявным описанием параллелизма для РВС;
разработать основные этапы трансляции модернизированного языка для РВС;
разработать алгоритмы трансляции структурного компонента параллельной прикладной программы;
разработать алгоритмы трансляции потокового и процедурного компонентов параллельной прикладной программы;
создать транслятор модифицированного языка высокого уровня.
Методы исследования. При проведении исследований были использованы
методы теории графов, теории множеств, методы объектно-ориентированного
программирования, методы структурно-процедурного параллельного
программирования, методы конструирования компиляторов (трансляторов).
Достоверность и обоснованность полученных в работе результатов подтверждены непротиворечивостью математических выкладок, вычислительными экспериментами на ряде действующих образцов реконфигурируемых систем, а также апробацией полученных научных результатов на международных и всероссийских конференциях.
Научная новизна результатов диссертационной работы определяется тем, что в ней разработаны:
принципы трансляции языка COLAMO для программирования много кадровых параллельных прикладных программ для РВС на уровне логических ячеек ПЛИС, которые отличаются введением в вычислительную структуру прикладной задачи сдвоенных контроллеров распределенной памяти и дополнительных коммутационных структур для переключения информационных потоков;
расширение языка высокого уровня COLAMO, отличающееся от языка COLAMO 2000-го года поддержкой битовых переменных, операций и функций, конструкции для использования внутренней памяти ПЛИС и средства обеспечения процедурной организации вычислений;
формализованные правила трансляции языка программирования высокого уровня с неявным описанием параллелизма COLAMO на уровне логических ячеек ПЛИС, отличающиеся правилами организации доступа к памяти, правилами параллельной и конвейерной обработки данных, правилами обработки конструкций языка;
структура транслятора с модернизированного языка COLAMO, отличающаяся от трансляторов процедурных языков генерацией как структурного, так и процедурного компонентов параллельной прикладной программы в едином вычислительном контуре на основе описания на одном языке программирования;
алгоритмы трансляции структурного компонента параллельной программы, отличающиеся представлением в виде отдельного информационно-эквивалентного графа транслируемой параллельной прикладной программы;
модернизированные алгоритмы генерации процедурных и потоковых компонентов, отличающиеся разделением вычислительных функций и операторов контроллеров распределенной памяти и обеспечивающие эффективную реализацию многокадровых прикладных программ на уровне логических ячеек ПЛИС.
Положения, выдвигаемые на защиту:
- для трансляции приложения, написанного на языке высокого уровня COLAMO,
на уровень логических ячеек ПЛИС структура кадра параллельной программы должна
быть разделена на два компонента: структурный, представляющий аппаратно-
реализуемый информационный граф задачи, и потоковый, организующий передачу
данных через вычислительный конвейер структурного компонента.
Результаты, выносимые на защиту:
- модернизированный язык COLAMO для эффективного программирования РВС
на уровне логических ячеек ПЛИС;
структура транслятора модернизированного языка программирования с неявным описанием параллелизма для создания прикладных программ РВС на уровне логических ячеек ПЛИС;
алгоритмы трансляции структурного компонента параллельной прикладной программы;
алгоритмы трансляции потокового и процедурного компонентов параллельной прикладной программы.
Практическая ценность работы. В диссертации решена важная научная задача, заключающаяся в создании средств описания параллельных прикладных программ для РВС и алгоритмов их трансляции на уровне ячеек ПЛИС, обеспечивающих увеличение удельной производительности РВС в 3-4 раза по сравнению с предыдущей версией транслятора, разработанного в начале 2000-х годов. По сравнению с разработкой приложений на уровне VHDL-описания и программой организации информационных обменов на языке ассемблера ARGUS программирование на модернизированном языке COLAMO-2010 позволяет в 7-10 раз сократить время создания прикладных программ при незначительном снижении реальной производительности системы.
Реализация и внедрение результатов работы. Результаты диссертации использовались при выполнении в НИИ многопроцессорных вычислительных систем ЮФУ ряда НИОКР, направленных на создание системного программного обеспечения реконфигурируемых вычислительных систем различных архитектур и конфигураций. Наиболее важными из них являются:
НИР «Разработка теоретических основ построения, аппаратных средств и математического обеспечения интеллектуальных многопроцессорных вычислительных и управляющих систем с реконфигурируемой архитектурой» (шифр «Ладья», 2006), ЖТ01.2.00707989;
ОКР «Разработка технологии создания высокопроизводительных модульно-наращиваемых многопроцессорных вычислительных систем с программируемой архитектурой на основе реконфигурируемой элементной базы», шифр «Медведь», выполняемая в рамках Федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 гг.» по госконтракту №02.447.11.1007 от «6» июля 2005 года, №ГР0122.0510630;
ОКР «Разработка технологии ресурсонезависимого параллельного программирования для многопроцессорных вычислительных систем различных классов» по государственному контракту от 22 июля 2005 г. № 02.447.11.1005 (шифр ИТ-22.4/005), №ГР0120.0511686;
ОКР «Разработка эскизной конструкторской документации на макет базового модуля модульно-наращиваемой мультипроцессорной системы (МНМС) на основе реконфигурируемой элементной базы и программных средств поддержки масштабируемых программ для решения задач обработки информации и управления в реальном времени на различных конфигурациях МНМС, в том числе при деградации вычислительного ресурса» в рамках мероприятия 1.12-САЗ по программе Союзного
государства «Развитие и внедрение в государствах-участниках Союзного государства наукоёмких компьютерных технологий на базе мультипроцессорных вычислительных систем» (шифр «Триада», 2006 г.), №ГР 01.2.00611470;
НИР «Исследование возможности создания модульно-наращиваемой многопроцессорной вычислительной системы на основе унифицированных базовых модулей для мониторинга систем цифровой связи», выполняемая в рамках договора с ФГУП РНИИРС, № ГР 01.2.00613841;
ОКР «Создание семейства высокопроизводительных многопроцессорных вычислительных систем с динамически перестраиваемой архитектурой на основе реконфигурируемой элементной базы и их математического обеспечения для решения вычислительно трудоемких задач», выполняемой в рамках федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы» по государственному контракту № 02.524.12.4002 от 20.04.2007 г. на выполнение опытно-конструкторских работ, шифр «Большая медведица», №ГР 01.2.007 05707.
Созданные методы, алгоритмы и программные средства внедрены в ФГУП «Курский НИИ» МО РФ (г. Курск), НИВЦ МГУ (г. Москва), Южном научном центре РАН (г. Ростов-на-Дону), НИИ многопроцессорных вычислительных систем ЮФУ (г. Таганрог).
Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях.
- на международной научно-технической конференции «Информационный подход в
естественных, гуманитарных и технических науках» (ИП-2004) (г. Таганрог, 2004); на
IV республиканской научно-практической конференции «Дагинформ-2005»
(г. Махачкала, 2005); на Международной научной конференции «Оптимальные методы
решения научных и практических задач» (г. Таганрог, 2005); на научной молодежной
школе «Высокопроизводительные вычислительные системы ВПВС-2005»
(с. Дивноморское, Россия, 2005); на II, III, IV, VI Ежегодной научной конференции
студентов и аспирантов базовых кафедр Южного научного центра (ЮНЦ) Российской
академии наук (РАН) (2006, 2007, 2008, 2010 гг., г. Ростов-на-Дону); на Седьмой
Международной научно-технической конференции «Интеллектуальные и
многопроцессорные системы-2006» (с. Кацивели, Украина,, 2006); на Всероссийской
научной конференции «Научный сервис в сети Интернет: технологии параллельного
программирования» (г. Новороссийск, 2006); на Международной научно-технической
конференции «Многопроцессорные вычислительные и управляющие системы - 2007,
2009» (с. Дивноморское, Россия, 2007, 2009); на Всероссийской научной конференции
«Научный сервис в сети ИНТЕРНЕТ: многоядерный компьютерный мир. 15 лет РФФИ»
(г. Новороссийск, 2007); на Пятой Международной научной молодежной школе
«Высокопроизводительные вычислительные системы» (с. Кацивели, Украина, 2008); на
Международной научной молодежной школе «Системы и средства искусственного
интеллекта (ССИИ-2008) (с. Кацивели, Украина, 2008); на Третьей международной
научной конференции «Суперкомпьютерные системы и их применение. SSA'2010» (Республика Беларусь, Минск, 2010); на Международной научно-технической конференции «Суперкомпьютерные технологии: разработка, программирование, применение (СКТ-2010)» (с. Дивноморское, Россия, 2010); на Седьмой Международной научной молодежной школе «Высокопроизводительные вычислительные системы» (с. Дивноморское, Россия, 2010).
Личный вклад автора. Все научные результаты получены автором лично.
Публикации. По результатам диссертации опубликована 21 печатная работа, из них - 6 статей, из которых 2 статьи опубликованы в ведущем рецензируемом научном журнале, входящем в Перечень ВАК РФ, тезисы и материалы 15 докладов на международных и российских научно-технических конференциях. По теме исследования получено 2 свидетельства об официальной регистрации программ для ЭВМ, результаты работы отражены в 15 отчетах о НИОКР.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка использованных источников и пяти приложений. Работа содержит 156 страниц основного текста, 52 рисунка, список используемой литературы из 87 источников, 56 страниц приложений.
