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

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

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

В настоящее время имеется несколько универсальных систем, которые можно рассматривать как комплекс инструментальных средств для разработки прикладных систем. К ним можно отнести такие системы как: HeNCE, GRADE, CODE, Triana, технологию Microsoft Workflow Foundation, ANS YS EKM, Kepler.

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

Вопросами организации высокопроизводительных вычислений занимались различные исследователи: Е. Валях [1], Прангишвили И. В. [2] и Трахтенгерц Э. А. [3,4] (распараллеливание в процессе трансляции), Гергель В. П. [5,6], Воеводин В. В. [7,8], Карцев М. А. [9], Абрамов С. М. [10−12] (динамическое распараллеливание Т-система) и др.

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

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

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

1. Исследование существующих методов организации конвейерно-параллельных вычислений на мультипроцессорных вычислительных системах;

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

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

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

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

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

1. Архитектурные решения программно-инструментального комплекса, обеспечивающие модульность, гибкость и расширяемость на уровне построения прикладных задач и при их решении на МВС.

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

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

Практическая значимость полученных результатов определяется их применением для решения комплекса актуальных задач обработки данных. Полученные результаты отражены в отчетах выполненных научных исследований в рамках:

1. Программы Союзного государства «Развитие и внедрение в государствах-участниках Союзного государства наукоемких компьютерных технологий на базе мультипроцессорных вычислительных систем», шифр «ТРИАДА» (проект ПР5 «Разработка новых алгоритмов, принципов создания систем обработки изображений и другой информации от космических средств наблюдения, ориентированных на применение многопроцессорных вычислительных кластеров повышенной вычислительной мощности»);

2. Программы Союзного государства «Космос-НТ» (НИР «Разработка прототипа программной нейросетевой системы контроля телеметрической информации, диагностики подсистем космических аппаратов, обработки космических снимков»);

3. Государственного контракта № 02.740.11.0526. «Разработка технологии интеллектуальной обработки информации в командно-измерительных системах космического назначения» (шифр заявки «2010;1.1−411−009−033»), 2010;2012гг.;

4. Проекта РФФИ 07−07−12 029;офи «Создание интеллектуальной технологии для анализа данных и распознавания образов» (2007;2008гг.);

5. Проекта РФФИ № 09−07−6-а «Исследование методов и создание теоретических основ информационной технологии обнаружения, распознавания, определения географического положения и прогнозирования поведения динамических целей» (2009;2011гг.);

6. Программы фундаментальных исследований Отделения РАН № 1 «Информационные технологии и методы анализа сложных систем», проект № 2.2 «Развитие методов интеллектуального управления на основе анализа потоков данных» (2009;2011гг.).

7. Государственного контракта № 07.514.11.4048 от 06 октября 2011 г. на тему «Разработка интеллектуальных методов автоматизированного обнаружения и предотвращения распределенных сетевых атак и их реализация в современных системах облачных вычислений» (2011;2012гг.).

Основные результаты диссертационной работы были использованы при разработке программного комплекса «ППС ИНС» для НИЦЭВТ по проекту «Триада» (свидетельство на регистрацию программы для ЭВМ № 2 010 610 208), разработке программной системы «ПС НСКиД» по проекту «Космос-НТ» Союзного государства (заявка на регистрацию программы для ЭВМ № 2 011 618 769 от 18 ноября 2011) и разработке «Комплекса программ инструментальных средств построения универсальной моделирующей среды для высокопроизводительной вычислительной системы „СКИФ“» для ОАО «Российские космические системы». Разработанное алгоритмическое и программное обеспечение внедрено в Научно-исследовательском институте космических систем им. А. А. Максимова.

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

1. Вторая международная научно-практическая конференция «Исследование, разработка и применение высоких технологий в промышленности». 07−09.01.2006, Санкт-Петербург, Россия.

2. Научно-техническая конференция ФГУП «РНИИ КП», посвященной. 60-летию предприятия (10−12 октября 2006 г.).

3. 9th International Conference «Pattern Recognition and image analysis: New Information Technologies» (PRIA-9−2008) (Nizhni Novgorod, 14−20.09.2008).

4. First Specialized Symposium «Space & Global Security of Humanity» (November 2−4, 2009, Amathus Beach Hotel, Limassol, Cyprus).

5. Ill Всероссийская научно-техническая конференция «Актуальные проблемы ракетно-космического приборостроения и информационных технологий» (1−3 июня 2010 года).

Кроме того, результаты работы докладывались и обсуждались на семинарах Исследовательского центра мультипроцессорных систем ИПС им. А. К. Айламазяна РАН в г. Переславль-Залесский (2005;2012).

Основные результаты диссертационной работы изложены в 15 печатных работах, в числе которых 7 статей опубликованы в рецензируемых изданиях, рекомендованных ВАК РФ.

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

3.3. Основные выводы.

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

Предложенный алгоритм диспетчеризации является «жадным» алгоритмом локально оптимального выбора применимых команд, но, не смотря на простоту, является достаточно эффективным решением, позволяющим задать ограничения на количество используемых аппаратных ресурсов МВС. Говоря об аналогичных системах, следует указать, что используемые в них принципы диспетчеризации, по мнению автора, уступают предложенному. Система CODE не имеет диспетчера нагрузки, поскольку является, по своей сути, системой кодогенерации. Технология Microsoft Workflow Foundation использует принцип очереди заданий без приоритетов, последовательно запуская.

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

Глава 4. Реализация прикладных систем с использованием инструментальных средств и исследование эффективности комплекса.

С использованием ПС, в рамках нескольких научно исследовательских проектов, были построены прикладные системы решающие следующие задачи:

• задача поиска и классификации объектов на изображениях, базирующейся на аппарате искусственных нейронных сетей. Данная задача, помимо реализации ИНС, включает в себя набор модулей предобработки (включая и параллельные реализации) и использует практически все функциональные возможности, предоставляемые разработанным инструментальным комплексом;

• задача обработки снимков ДЗЗ;

• задача контроля и диагностики подсистем космического аппарата.

В рамках Государственного контракта № 07.514.11.4048 от 06 октября 2011 г. на тему «Разработка интеллектуальных методов автоматизированного обнаружения и предотвращения распределенных сетевых атак и их реализация в современных системах облачных вычислений» (Шифр «2011;1.4−514−017−004») указанная ПС была использована в составе тестового стенда, выступая в качестве атакуемой распределенной системы.

4.1. Библиотека модулей для решения прикладных задач.

Для решения прикладных задач, в ПС реализовано 26 программных модулей. Их краткое описание (включая параметры их настройки) приведено в таблице 7.

Заключение

.

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

В ходе работы над диссертацией были решены следующие задачи:

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

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

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

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

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

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

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