Введение к работе
Актуальность темы. Научно-технический прогресс требует решения все более сложных вычислительных задач за все более короткие промежутки времени. Производительности однопроцессорных систем уже недостаточно для обеспечения постоянно растущего спроса на решение вычислительно-трудоемких задач. Для обеспечения роста производительности создаются новые архитектуры многопроцессорных систем, предлагаются способы технической реализации их компонентов, а также разрабатываются методы организации параллельных вычислений. Множество организаций и суперкомпьютерных центров на сегодняшний день имеют в своем распоряжении высокопроизводительные многопроцессорные вычислительные системы (МВС). В то же время большинство специалистов в области МВС сталкиваются с острой проблемой эффективного использования вычислительного ресурса этих систем. Рациональное использование МВС диктует необходимость решения на таких системах различных задач: от вычислительно-трудоемких, требующих всего ресурса системы, до задач, решаемых за короткие промежутки времени на минимальном количестве процессоров. В связи с этим важным является эффективное планирование вычислительного ресурса системы с целью минимизации времени прохождения потока разнородных заданий. Особенно важно эффективно планировать вычислительный ресурс в многозадачном режиме функционирования МВС.
Известно, что для распределения вычислительного оборудования МВС между множеством потребителей используется метод разделения ресурса. Данный метод предполагает одновременное выделение каждому заданию некоторой доли общего вычислительного ресурса, на котором это задание решается, по тем или иным правилам.
Следует отметить, что на этапе разработки параллельных программ у программиста отсутствует информация о ресурсе, который будет выделен системой планирования для выполнения его программы. Большинство разработчиков решает данную проблему путем перекомпиляции исходного кода программ с учетом количества ресурса, выделенного для ее выполнения непосредственно перед подстановкой задания на решение. Однако за время перекомпиляции может измениться динамическая карта состояния вычислительного ресурса системы, и, как следствие, решение о постановке задания на выбранный ресурс станет неактуальным. Более того, возможны конфликтные ситуации и, как следствие, неизбежно неэффективное использование ресурса МВС. Существующие методы автоматического изменения степени распараллеливания (масштабирования) программ имеют низкую эффективность, либо ориентированы на узкий класс задач.
Проблема распределения ресурсов МВС в многозадачном режиме еще более усложняется для одних из наиболее перспективных и бурно развивающихся классов многопроцессорных вычислительных систем - реконфигурируемых вычислительных систем (РВС). Такие системы имеют потенциально высокий запас производительности за счет более рационального использования ресурсов системы, адаптированных под структуру решаемой задачи. Однако процесс создания параллельных программ на основе структурно-процедурных методов для РВС накладывает дополнительные сложности на выполнение процедуры масштабирования прикладных программ.
Для РВС известна технология индуктивных параллельных программ (ИПП), которая подразумевает включение в параллельную программу, помимо основной вычислительной компоненты, секцию правил модернизации программы в зависимости от ресурса, выделенного для выполнения программы планировщиком заданий. В рамках технологии ИПП прикладные программы разрабатываются независимо от степени распараллеливания, масштабирование выполняется созданной программистом процедурой посттрансляции, модернизирующей параллельную программу под выделенный ресурс. Поскольку трудоемкость написания правил масштабирования соизмерима, а зачастую и превышает трудоемкость создания основной вычислительной компоненты программы, то при использовании технологии ИПП существенно повышаются требования к квалификации программистов.
В связи с этим актуальной является задача создания методов и средств автоматического масштабирования параллельных программ для РВС, позволяющих сократить время разработки параллельных масштабируемых программ и организовать эффективный многозадачный режим функционирования РВС с целью сокращения времени прохождения потока заданий.
Цель работы и задачи исследования. Целью диссертационной работы является минимизация времени решения потока разнородных заданий на РВС.
Для достижения этой цели в работе были решены следующие задачи:
1) проведен анализ методов организации параллельных вычислений в РВС;
2) разработан метод автоматического масштабирования кадров параллельных программ путем конвейеризации в зависимости от степени распараллеливания;
2) разработан метод автоматического масштабирования кадров путем распараллеливания в зависимости от вычислительного ресурса;
4) разработан метод масштабирования многокадровых параллельных программ;
5) разработаны программные компоненты операционной системы многозадачного режима функционирования РВС, в том числе: планировщик заданий, подсистема посттрансляции исполняемых модулей параллельных программ в зависимости от параметра распараллеливания, загрузчик исполняемых модулей параллельных программ, подсистема удаленного доступа к вычислительным ресурсам, драйвер и библиотеки низкоуровневого программного доступа к РВС.
6) проведен анализ эффективности разработанных методов и средств на примерах решения прикладных задач.
Методы исследования. При проведении исследований были использованы основы теории вычислительных машин, теории графов, теории множеств, методы объектно-ориентированного программирования, методы структурно-процедурного параллельного программирования. Экспериментальные исследования проведены на действующих образцах реконфигурируемых многопроцессорных вычислительных систем.
Научная новизна работы состоит в том, что в ней разработаны:
1) метод масштабирования кадров путем конвейеризации, отличающийся от существующих автоматическим применением типовых процедур конвейеризации к кадрам прикладных параллельных программ;
2) метод масштабирования кадров путем распараллеливания, отличающийся от существующих автоматическим применением типовых процедур распараллеливания к кадрам прикладных программ;
3) метод масштабирования многокадровых задач, отличающийся от известных выбором наиболее оптимального параметра распараллеливания для совокупности кадров параллельной прикладной программы;
4) алгоритм подсистемы посттрансляции параллельных программ, отличающийся от известных динамической модификацией исполняемых модулей прикладных параллельных программ непосредственно перед постановкой их на выполнение;
5) модифицированный алгоритм планировщика заданий, отличающийся от известного поддержкой возможности планирования фиксированных, индуктивных и автоматически-масштабируемых параллельных программ.
Достоверность и обоснованность полученных в работе результатов подтверждается полнотой и корректностью исходных посылок, теоретическим обоснованием, непротиворечивостью математических выкладок, а также исследованиями и экспериментами, проведенными на действующих образцах РВС.
Научная и практическая ценность работы.
В диссертационной работе решена важная научно-техническая задача, заключающаяся в создании методов и программных компонентов операционной системы, обеспечивающих автоматическое масштабирование прикладных параллельных программ на свободный ресурс РВС и позволяющих на 30% сократить время прохождения потока разнородных заданий. Новые методы автоматического масштабирования позволяют сократить время создания параллельных масштабируемых программ для РВС в 1,54 раза. Разработанная подсистема удаленного доступа к вычислительным ресурсам РВС позволяет упростить процесс отладки масштабируемых прикладных параллельных программ и, как следствие, сократить время их создания.
Реализация и внедрение результатов работы. Материалы диссертации использовались при выполнении ряда НИОКР, в том числе в рамках федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы», в рамках научно-технической программы Союзного государства «Развитие и внедрение в государствах-участниках Союзного государства наукоёмких компьютерных технологий на базе мультипроцессорных вычислительных систем», выполняемыми НИИ многопроцессорных вычислительных систем Южного федерального университета (г. Таганрог). Созданные методы и программные компоненты внедрены в в.ч. 26165 (г. Москва), ФГУП «Курский НИИ» МО РФ (г. Курск), Южном научном центре РАН (г. Ростов-на-Дону), НИИ многопроцессорных вычислительных систем Южного федерального университета (г. Таганрог).
Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях.
На международной научно-технической конференции «Интеллектуальные и многопроцессорные системы», 2003 г., 2005 г., Геленджик; на Международной научно-технической конференции «Искусственный интеллект. Интеллектуальные и многопроцессорные системы», 2004 г., 2006 г., Кацивелли; на Международной научной школе «Высокопроизводительные вычислительные системы», 2004 г., 2005 г, 2006 г.; на ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН, 2005г., 2006г. 2007г., Ростов-на-Дону; на IV республиканской научно-практической конференции «Дагинформ-2005», 2005г., Махачкала; на международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы», 2007г., Геленджик.
Основные положения и результаты, выносимые на защиту:
- методы автоматического масштабирования кадров параллельных программ позволяют: за счет модернизации фрагментов исполняемого кода программ сократить время постановки программ на выполнение, и, как следствие, организовать эффективный многозадачный режим функционирования РВС; за счет автоматического применения типовых схем масштабирования кадров программ сократить время создания масштабируемых параллельных программ;
- метод масштабирования многокадровых задач позволяет за счет выбора наиболее оптимального параметра распараллеливания сократить количество незадействованных при реализации кадров базовых модулей, и, как следствие, повысить скорость прохождения потока заданий через РВС;
- подсистема посттрансляции обеспечивает автоматическое масштабирование прикладных программ для достаточно широкого класса задач: задач символьной обработки, линейной алгебры и математической физики;
- программные компоненты многозадачной операционной системы для РВС.
Личный вклад автора. Все научные и практические результаты получены автором лично.
Публикации. По теме диссертационной работы опубликовано 17 печатных работ, из них: 5 статей, 2 из которых входят в список ведущих рецензируемых журналов ВАК, 12 тезисов и материалов докладов на российских и международных научно-технических конференциях.
Структура и объем работы. Диссертация состоит из введения, трех глав с выводами, заключения, списка использованных источников из 98 наименований. Диссертация содержит 170 страниц печатного текста и 84 рисунка.
