Введение к работе
Актуальность темы исследования. Развитие науки и техники приводит к увеличению числа расчётоёмких вьшислительных задач, решение которых на рабочих станциях неприемлемо вследствие больших временных затрат. Для сокращения времени решения расчётоёмких задач на практике используются кластерные многопроцессорные вычислительные системы, созданные из унифицированных узлов на базе универсальных процессоров, однако такие системы эффективны только для решения слабосвязанных задач, где количество информационных обменов между различными процессорами относительно невелико. Принципиально новыми свойствами обладают реконфигурируемые вычислительные системы (РВС): архитектура самого вычислителя подстраивается под структуру решаемой задачи. В настоящее время основным аппаратным компонентом РВС является совокупность программируемых логических интегральных схем (ПЛИС). Подобные системы могут быть сконфигурированы для решения конкретной прикладной задачи и обеспечить высокую реальную производительность. Кроме того, РВС потенциально обладают близким к линейному ростом производительности при увеличении вычислительного ресурса.
С программированием реконфигурируемых систем связана парадигма структурной организации вычислений, согласно которой программа прикладной задачи формируется в виде информационного графа, вершины которого соответствуют операциям, а дуги - информационным зависимостям между ними. Такие программы будем называть структурными программами. В отличие от процедурного программирования, когда текст исходной программы транслируется компилятором в набор инструкций, последовательно во времени исполняемых на процессоре (или совокупности процессоров), текст структурной программы для РВС преобразуется с помощью программы-синтезатора в совокупность логических блоков, команд функциональных устройств, расположенных в кристаллах ПЛИС, и связей между ними.
Для решения расчётоёмких задач из различных предметных областей при разработке структурных параллельных прикладных программ зачастую недостаточно одной ПЛИС, так как информационный граф задачи превышает ресурс кристалла. Поэтому для реализации структурных программ требуется множество взаимосвязанных ПЛИС. В этом случае информационный граф структурной программы должен быть разделён на непересекающиеся подграфы, каждый из которых структурно реализуется в отдельном кристалле ПЛИС реконфигурируемого вычислителя.
В настоящее время для программирования РВС используются языки HDL-группы (Hardware Description Language - язык описания аппаратуры) и различные графические системы, которые предназначены для программирования отдельных ПЛИС, а не их совокупности. Программирование РВС на языках HDL представляет собой разработку отдельных проектов для каждой ПЛИС. При разработке многокристальных решений пользователю РВС приходится распределять элементы информационного графа алгоритма расчётоёмкой задачи между различными проектами, каждый из которых
структурно реализует фрагмент параллельной прикладной программы в отдельной ПЛИС реконфигурируемого вычислителя. При этом программист должен следить за корректностью структуры связей между элементами информационного графа из разных проектов и обеспечивать синхронизацию потоков данных и управляющих сигналов как внутри каждого проекта, так и в общем графе алгоритма решаемой задачи.
При использовании известных средств программирования ПЛИС срок разработки структурной параллельной прикладной программы для многокристальной РВС может составлять несколько месяцев, что окажется неприемлемым. В то же время существует большой класс задач, при решении которых реконфигурируемые вычислители показывают производительность на два-четыре десятичных порядка выше, чем у традиционных МВС, - это так называемые потоковые задачи, для которых характерна обработка больших массивов данных по фиксированному алгоритму.
В этой связи актуальной является разработка методов и средств автоматического отображения ресурсонезависимых информационных графов структурных параллельных прикладных программ на аппаратный ресурс многокристальных РВС, которые позволят значительно сократить время разработки структурных программ и обеспечат высокую реальную производительность многокристальных РВС при решении расчётоёмких задач из различных предметных областей. Данные методы и средства должны обеспечить автоматическое разбиение информационных графов на подграфы, каждый из которых отображается в отдельную ПЛИС многокристальной РВС, осуществить пространственную коммутацию информационных связей между всеми задействованными в вычислениях кристаллами и обеспечить синхронизацию управляющих и информационных потоков как в отдельных кристаллах, так и в общем графе прикладной задачи.
Объектом исследований являются методы автоматического отображения информационных графов параллельных прикладных программ на аппаратный ресурс многокристальных реконфигурируемых вычислительных систем.
Целью диссертационной работы является сокращение времени разработки ресурсонезависимых параллельных прикладных программ для многокристальных РВС.
Научная задача состоит в создании методов и алгоритмов автоматического отображения информационных графов на ресурс многокристальных РВС, обеспечивающих сокращение времени создания ресурсонезависимых параллельных прикладных программ для многокристальных РВС при высокой реальной производительности формируемых решений.
Для достижения поставленной цели решены следующие задачи исследования:
проведён анализ существующих методов и средств разработки решений трудоёмких прикладных задач для многокристальных РВС;
разработан общий алгоритм работы синтезатора структурных параллельных прикладных программ для многокристальных реконфигурируемых вычислительных систем, независимый от архитектуры РВС;
разработаны и исследованы методы компоновки информационных графов параллельных прикладных программ, решаемых на многокристальных РВС;
разработаны и исследованы методы размещения и трассировки информационных графов параллельных прикладных программ;
на основании разработанных и исследованных методов компоновки, размещения и трассировки разработан синтезатор для автоматического отображения информационных графов параллельных прикладных программ на аппаратный ресурс многокристальных РВС.
Методы исследования. При проведении исследований были использованы теория графов, теория множеств, методы потокового программирования, методы структурного программирования.
Достоверность и обоснованность полученных в работе результатов подтверждены непротиворечивостью математических выкладок, экспериментами на ряде действующих образцов реконфигурируемых систем, а также апробацией полученных научных результатов на международных и всероссийских конференциях.
Научная новизна результатов диссертационной работы определяется тем, что в ней разработаны:
новый алгоритм работы синтезатора структурных параллельных прикладных программ для многокристальных РВС, отличающийся от известных включением этапа загрузки описания структуры РВС и обеспечивающий автоматическое отображение информационных графов на аппаратный ресурс многокристальных РВС различных архитектур и конфигураций с высокой реальной производительностью формируемых решений;
модернизированная многоуровневая схема компоновки (multilevel partitioning scheme) информационных графов структурных параллельных прикладных программ, отличающаяся от известной введением этапа расчёта ограничений для формируемых подграфов, а также введением новых алгоритмов для этапов огрубления и восстановления;
новые методы компоновки информационных графов структурных параллельных прикладных программ, отличающиеся от известных введением модернизированной многоуровневой схемы компоновки, а также процедуры последовательной компоновки, основанной на модернизированном алгоритме «жадного» роста регионов (greedy graph growing) и разработанном алгоритме обхода локально-оптимальных решений (локальных тупиков);
модернизированный волновой алгоритм Ли для трассировки информационных связей подграфов структурных параллельных прикладных программ, который отличается от известного приращением значений волнового фронта не на единицу, а на минимальное число занимаемых физических каналов связей для трассируемой шины, что позволяет улучшить качество трассировки.
Положения, выдвигаемые на защиту:
использование процедуры оптимизации на этапе огрубления информационного графа структурной параллельной прикладной программы для многоуровневой схемы компоновки позволяет сократить суммарное число внешних связей в формируемых подграфах и, тем самым, обеспечить лучшие условия для этапа трассировки;
использование модифицированной процедуры формирования карты волновых фронтов в алгоритме трассировки информационных связей подграфов структурных параллельных прикладных программ, которая отличается от известной тем, что значение волны равно минимальному числу занимаемых каналов связи от источника сигнала, позволяет проводить трассы с использованием ранее проложенных равнопотенциальных связей и шин и, тем самым, снижает суммарное число занятых каналов связи.
Результаты, выносимые на защиту:
новый алгоритм работы синтезатора ресурсонезависимых структурных параллельных прикладных программ для многокристальных РВС;
метод компоновки информационных графов структурных параллельных прикладных программ, содержащий модифицированную многоуровневую схему и модифицированный последовательный алгоритм компоновки с обходом локальных тупиков;
метод трассировки внешних связей размещённых подграфов структурных параллельных прикладных программ, содержащий модифицированную процедуру формирования карты волновых фронтов для волнового алгоритма трассировки Ли;
синтезатор структурных параллельных прикладных программ для многокристальных РВС различных архитектур и конфигураций.
Практическая ценность работы. В диссертации решена актуальная научная задача разработки методов и средств автоматического отображения информационных графов структурных параллельных прикладных программ на ресурс многокристальных РВС. Разработанные методы и средства позволяют в 5-10 раз сократить время создания структурных параллельных прикладных программ для многокристальных РВС по сравнению с временем разработки в существующих графических средах, а также в 10-20 раз сократить время портации многокристальных проектов на РВС различных архитектур и конфигураций.
Диссертация соответствует пункту 8 («Модели и методы создания программ и программных систем для параллельной и распределенной обработки данных, языки и инструментальные средства параллельного программирования») паспорта специальности 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей».
Реализация и внедрение результатов работы. Результаты диссертации использовались при выполнении ряда НИОКР. Наиболее важными из них являются:
- ОКР «Создание семейства высокопроизводительных многопроцессорных
вычислительных систем с динамически перестраиваемой архитектурой на основе
реконфигурируемой элементной базы и их математического обеспечения для решения вычислительно трудоемких задач», выполняемой в рамках федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы» по государственному контракту № 02.524.12.4002 от 20.04.2007 г., №ГР 01.2.007 05707;
ОКР «Разработка эскизной конструкторской документации на макет базового модуля модульно-наращиваемой мультипроцессорной системы (МНМС) на основе реконфигурируемой элементной базы и программных средств поддержки масштабируемых программ для решения задач обработки информации и управления в реальном времени на различных конфигурациях МНМС, в том числе при деградации вычислительного ресурса» в рамках мероприятия 1.12-САЗ по программе Союзного государства «Развитие и внедрение в государствах-участниках Союзного государства наукоёмких компьютерных технологий на базе мультипроцессорных вычислительных систем», №ГР 01.2.00611470;
ОКР «Разработка технологии создания высокопроизводительных модульно-наращиваемых многопроцессорных вычислительных систем с программируемой архитектурой на основе реконфигурируемой элементной базы», выполняемая в рамках Федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 гг.» по госконтракту №02.447.11.1007 от «6» июля 2005 года, №ГР0122.0510630;
ОКР «Разработка технологии ресурсонезависимого параллельного программирования для многопроцессорных вычислительных систем различных классов» по государственному контракту № 02.447.11.1005 от 22 июля 2005 г.;
НИР «Исследование возможности создания модульно-наращиваемой многопроцессорной вычислительной системы на основе унифицированных базовых модулей для мониторинга систем цифровой связи», выполняемая в рамках федеральной целевой программы «Национальная технологическая база» на 2002-2006 годы», № ГР 01.2.00613841.
Результаты диссертации внедрены в НИВЦ МГУ (г. Москва), ФГУП «НИИ «Квант» (г. Москва), ФГУП «Курский НИИ» МО РФ (г. Курск), Южном научном центре РАН (г. Ростов-на-Дону), НИИ MB С ЮФУ (г. Таганрог).
Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях.
- на II, III, IV, V, VI Ежегодной научной конференции студентов и аспирантов
базовых кафедр Южного научного центра Российской академии наук (2006, 2007, 2008,
2009, 2010 гг., г. Ростов-на-Дону); на Седьмой Международной научно-технической
конференции «Интеллектуальные и многопроцессорные системы-2006» (с. Кацивели,
Украина,, 2006); на Международной научно-технической конференции
«Многопроцессорные вычислительные и управляющие системы - 2007, 2009»
(с. Дивноморское, Россия, 2007, 2009); на Всероссийской научной конференции
«Научный сервис в сети ИНТЕРНЕТ: многоядерный компьютерный мир. 15 лет РФФИ»
(2007 г. Москва); на Пятой Международной научной молодежной школе «Высокопроизводительные вьшислительные системы» (с. Капивели, Украина, 2008); на Международной научной молодежной школе «Системы и средства искусственного интеллекта (ССИИ-2008) (с. Капивели, Украина, 2008); на Международной научно-технической конференции «Суперкомпьютерные технологии: разработка, программирование, применение (СКТ-2010)» (с. Дивноморское, Россия, 2010); на Седьмой Международной научной молодежной школе «Высокопроизводительные вьшислительные системы» (с. Дивноморское, Россия, 2010).
Личный вклад автора. Все научные результаты диссертации получены автором лично.
Публикации. По результатам диссертации опубликовано 15 печатных работ, из них 6 статей, из которых 2 статьи опубликованы в ведущих рецензируемых научных журналах, входящих в Перечень ВАК РФ, тезисы и материалы 9 докладов на международных и российских научно-технических конференциях. По теме исследования получено 2 свидетельства об официальной регистрации программ для ЭВМ, результаты работы отражены в 9 отчетах о НИОКР.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка использованных источников и четырёх приложений. Работа содержит 156 страниц основного текста, 50 рисунков, список используемой литературы из 99 источников, 45 страниц приложений.
