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

Актуальность темы

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

Для организации многозадачного режима работы вычислительных систем существует два основных метода разделения вычислительного ресурса: метод разделения времени и метод разделения ресурса. Первый метод заключается в выделении квантов времени на использование ресурса системы [1,2,3]. Данный метод, как правило, используется операционными системами (ОС) однопроцессорных систем [4], в этом случае процессорное время последовательно делится между потребителями. Основным недостатком данного метода является существенное падение производительности вычислительных систем при большом числе потребителей из-за роста накладных расходов на переключение процессора между выполняемыми программами.

Метод разделения ресурса предполагает «пространственное» разделение ресурса системы между заданиями, что разрешает одновременный доступ нескольких процессов к вычислительному ресурсу единой вычислительной системы. Функцию разделения ресурса системы (процессоров) между процессами выполняет специальная процедура планирования. Данный метод применяется, как правило, для МВС. Пространственное разделение ресурса в МВС позволяет сократить, а в ряде случаев и устранить накладные расходы на переключение вычислительного ресурса между процессами.

Следует отметить, что на этапе разработки параллельных программ у программиста отсутствует информация о количестве ресурса, которое будет выделено планировщиком заданий для выполнения его программы. Большинство разработчиков решают данную проблему путем перекомпиляции исходного текста программ, учитывая на этапе трансляции количество выделенного ресурса непосредственно перед подстановкой на исполнение. Однако за время перекомпиляции' может измениться динамическая карта состояния системы и, как следствие, решение о постановке задания на выбранный ресурс станет неактуальным. Более того, возможны конфликтные ситуации, и неизбежно неэффективное использование ресурса МВС. Существующие методы автоматического масштабирования (модификации программ с целью выполнения их на различном количестве вычислительного ресурса) имеют низкую эффективность или ориентированы на узкий класс задач.

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

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

Для реконфигурируемых систем известна технология индуктивных параллельных программ (ИПП) [24]. Она подразумевает включение в параллельную программу помимо основной вычислительной компоненты еще и секцию правил модернизации программы в зависимости от степени распараллеливания (количества ресурса, выделенного для выполнения программы), определенной планировщиком заданий. В рамках технологии ИПП программы разрабатываются независимо от степени распараллеливания, а масштабирование выполняется созданной программистом процедурой посттрансляции, выполняющей модернизацию параллельных программ. Основной недостаток данной технологии состоит в существенном повышении требований к квалификации программистов, разрабатывающих индуктивные программы, т.к. трудоемкость написания правил масштабирования соизмерима, а зачастую и превышает трудоемкость создания основной вычислительной компоненты программы.

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

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

Целыо работы является минимизация времени решения потока разнородных заданий на РВС.

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

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

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

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

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

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

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

4) проведен анализ эффективности разработанных методов и средств на примерах решения прикладных задач.

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

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

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

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

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

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

Практическая значимость. В диссертационной работе решена важная задача, заключающаяся в создании методов и программных компонентов операционной системы, обеспечивающих автоматическое масштабирование прикладных параллельных программ на свободный ресурс РВС и позволяющих на 30% сократить время решения потока разнородных заданий. Новые методы автоматического масштабирования позволяют сократить время создания параллельных масштабируемых программ для РВС в 1,5+4 раза. Разработанная подсистема удаленного доступа к вычислительным ресурсам РВС позволяет упростить процесс отладки масштабируемых прикладных параллельных программ и, как следствие, сократить время их создания.

Использование результатов работы. Материалы диссертации использовались при выполнении ряда НИОКР, в том числе в рамках федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007;2012 годы», в рамках научно-технической программы Союзного государства «Развитие и внедрение в государствах-участниках Союзного государства наукоёмких компьютерных технологий на базе мультипроцессорных вычислительных систем», выполняемыми НИИ многопроцессорных вычислительных систем Южного федерального университета (г. Таганрог). К наиболее значимым НИОКР относятся:

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

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

НИР «Разработка и исследование принципов построения самонастраиваемых вычислительных систем на основе реконфигурируемых вычислительных блоков», № гос. per. 01.20.301 381, инв. № 02.2.00 601 553, Таганрог, НИИ МВС ТРТУ, 2005 г.;

— НИР «Разработка и исследование методов синтеза виртуальных специализированных вычислителей в рамках фрейм-архитектуры СВПВС с многоуровневой организацией программирования архитектуры», № гос. per. 01.20.301 382, инв. № 0220.0 601 018, Таганрог, НИИ МВС ТРТУ, 2005 г.

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

На международной научно-технической конференции «Интеллектуальные и многопроцессорные системы», 2003 г., 2005 г., Геленджикна Международной научно-технической конференции «Искусственный интеллект. Интеллектуальные и многопроцессорные системы», 2004 г., 2006 г., Кацивеллина Международной научной школе «Высокопроизводительные вычислительные системы», 2004 г., 2005 г, 2006 г.- на ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН, 2005 г., 2006 г. 2007 г., Ростов-на-Донупа IV республиканской научно-практической конференции «Дагинформ-2005», 2005 г., Махачкалана международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы», 2007 г., Геленджик.

Наиболее важными из публикаций являются:

1) Шматок А. В., Каляев З. В., Структурно-функциональный и структурно-декларативный методы разработки компонентов масштабируемых параллельных программ. Тематический выпуск «Интеллектуальные и многопроцессорные системы». Известия ТРТУ. — Таганрог: Изд-во ТРТУ, 2004. -С. 64−70.

2) Каляев З. В., Коваленко А. Г., Многозадачная распределенная операционная система многопроцессорной вычислительной системы с программируемой архитектурой. Известия ТРТУ. — Таганрог: Изд-во ТРТУ, 2006.-С. 179.

3) Левин И. И., Шматок A.B., Каляев З. В., Средства разработки параллельных программ для многопроцессорных вычислительных систем с программируемой архитектурой. Искусственный интеллект. Донецк (Украина): изд-во ДонГИИИ «Наука i освгга», № 3, 2003. — С. 147−149.

4) Шматок A.B., Каляев З. В., Декларативный и функциональный методы разработки компонентов масштабируемых параллельных программ. Материалы международной научно-технической конференции «Искусственный интеллект. Интеллектуальные и многопроцессорные системы», 20−25 сентября 2004 г. -Таганрог: Изд-во ТРТУ, 2004. — Т 1. — С. 227−229.

5) Каляев З. В. Процедура масштабирования задачи сложения чисел для МВС ПА. Материалы первой ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН. — Ростов-на-Дону: Изд-во ЮНЦ РАН, 2005. — С. 231−232.

6) Каляев З. В. Процедура масштабирования операции умножения матриц. Материалы Международной научной молодежной школы «Высокопроизводительные вычислительные системы», Таганрог: Изд-во ТРТУ, 2005. С.176−178.

7) Каляев З. В. Масштабирование операции умножения матриц. Материалы IV республиканской научно-практической конференции «Дагинформ-2005». -Махачкала: ДНЦ РАН, 2006. — С. 190−192.

8) Каляев З. В. Многозадачная распределенная операционная система. Искусственный интеллект. — Донецк: Наука i осв1та, 2006. — № 3. — С. 144−147.

9) Каляев З. В. Структура многозадачной распределенной операционной системы. Международной научно-технической конференции «Искусственный интеллект. Интеллектуальные и многопроцессорные системы». — Таганрог: Изд-во ТРТУ, 2006. — Т. 2. — С. 102−103.

10) Каляев З. В. Компоненты многозадачной операционной системы для реконфигурируемой вычислительной системы. Материалы Третьей ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН. -Ростов-на-Дону: Изд-во ЮНЦ РАН, 2007. — С. 140−141.

11) Каляев З. В. Система автоматического масштабирования параллельных программ для реконфигурируемых вычислительных систем. Материалы Международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы — 2007». — Таганрог: Изд-во ТТИ ЮФУ, 2007. — Т. 1. — С. 285−289.

Структура диссертации. Диссертация состоит из введения, трех глав, библиографического списка и приложения.

3.6. Выводы.

1) На основе методов автоматического масштабирования кадров параллельных программ разработана подсистема посттраисляции исполняемых модулей для реконфигурируемых вычислительных систем. Подсистема пострансляции производит анализ и модификацию секций исполняемого кода параллельных программ. Эксперименты показали, что разработанные средства масштабирования за счет автоматического выбора и применения типовых схем масштабирования кадров позволяют в 1,5−4 раза сократить время создания масштабируемых прикладных программ.

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

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

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

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

ЗАКЛЮЧЕНИЕ

.

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

При проведении исследований и разработок в диссертации получены следующие теоретические и прикладные результаты.

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

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

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

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

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

6) Разработан метод масштабирования многокадровых задач, заключающийся в выборе более близкого к оптимальному параметра распараллеливания для совокупности кадров параллельной программы.

7) На основе методов автоматического масштабирования кадров параллельных программ разработана подсистема посттрансляции исполняемых модулей для реконфигурируемых вычислительных систем. Подсистема пострансляции производит анализ и модификацию секций исполняемого кода параллельных программ. Эксперименты показывали, что разработанные средства масштабирования за счет автоматического выбора и применения типовых схем масштабирования кадров позволяют в 1,5−4 раза сократить время создания масштабируемых прикладных программ.

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

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

Основные научные результаты диссертации опубликованы в работах [73, 78−83].

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

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

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