МОДЕЛИ, АЛГОРИТМЫ И ПРОГРАММНО-ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ДЛЯ ОРГАНИЗАЦИИ КОНВЕЙЕРНО-ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ НА МУЛЬТИПРОЦЕССОРНЫХ СИСТЕМАХ Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей Автореферат диссертации на соискание ученой степени кандидата технических наук Переславль-Залесский 2012

Авторефераты по всем темам >> Авторефераты по техническим специальностям

На правах рукописи

Талалаев Александр Анатольевич

МОДЕЛИ, АЛГОРИТМЫ И ПРОГРАММНО-ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ДЛЯ ОРГАНИЗАЦИИ КОНВЕЙЕРНО-ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ НА МУЛЬТИПРОЦЕССОРНЫХ СИСТЕМАХ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени

кандидата технических наук

Переславль-Залесский

2012

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

Научный руководитель

профессор, доктор технических наук

Хачумов Вячеслав Михайлович

Официальные оппоненты:

д.ф.-м.н., доц., зав. лаб. ИЦСА,

ИПС им. А.К. Айламазяна РАН

Знаменский Сергей Витальевич

к. т. н., с.н.с. Лаборатории 0-2, ИСА РАН

Тихомиров Илья Александрович

Ведущая организация:

ОАО Научно-исследовательский центр электронной вычислительной техники

(ОАО НИЦЭВТ)

Защита состоится 27 апреля 2012 г. в 13.00 часов на заседании Диссертационного совета ДМ 002.084.01 при Федеральном государственном бюджетном учреждении науки Институте программных систем им.аА.К.аАйламазяна Российской академии наук по адресу: 152020, Ярославская обл., Переславский район, с. Веськово, ул. Петра Первого, д. 4а.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института программных систем им. А.К. Айламазяна Российской академии наук.

Автореферат разослан л___ __________ 2012 г.

Ученый секретарь диссертационного совета, кандидат технических наук

Пономарева С.М.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы

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

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

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

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

Вопросами организации высокопроизводительных вычислений занимались различные исследователи: Е. Валях, Прангишвили И.В. и Трахтенгерц Э.А. (распараллеливание в процессе трансляции), Гергель В.П., Воеводин В.В., Карцев М.А., Абрамов С.М. (динамическое распараллеливание Т-система) и др.

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

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

Основной целью работы является обеспечение достаточно высоких показателей алгоритмов конвейерно-параллельных вычислений по быстродействию при минимальных временных затратах на их разработку с использованием инструментальных средств. При этом учитывается возможность кроссплатформенной реализации с сохранением принципов универсализма, гибкости и расширяемости программного комплекса. Разработанные автором комплексные решения прошли апробацию в рамках проектов Триада и Космос-НТ, обеспечив достаточно высокие показатели на отечественных вычислителях кластерного типа СКИФ-Аврора ЮУрГУ и К-100 Межведомственного суперкомпьютерного центра РАН (МС - РАН).

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

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

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

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

Результаты, выносимые на защиту:

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

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

Научная новизна работы:

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

Предметом научной новизны являются:

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

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

Программы Союзного государства Развитие и внедрение в государствах-участниках Союзного государства наукоемких компьютерных технологий на базе мультипроцессорных вычислительных систем, шифр ТРИАДА (проект ПР5 Разработка новых алгоритмов, принципов создания систем обработки изображений и другой информации от космических средств наблюдения, ориентированных на применение многопроцессорных вычислительных кластеров повышенной вычислительной мощности);
Программы Союзного государства Космос-НТ (НИР Разработка прототипа программной нейросетевой системы контроля телеметрической информации, диагностики подсистем космических аппаратов, обработки космических снимков);
Государственного контракта №02.740.11.0526. Разработка технологии интеллектуальной обработки информации в командно-измерительных системах космического назначения (шифр заявки л2010-1.1-411-009-033), 2010-2012гг.;
Проекта РФФИ 07-07-12029-офи "Создание интеллектуальной технологии для анализа данных и распознавания образов" (2007-2008гг.);
Проекта РФФИ № 09-07-00006-а "Исследование методов и создание теоретических основ информационной технологии обнаружения, распознавания, определения географического положения и прогнозирования поведения динамических целей" (2009-2011гг.);
Программы фундаментальных исследований Отделения РАН № 1 Информационные технологии и методы анализа сложных систем,
проект № 2.2 Развитие методов интеллектуального управления на основе анализа потоков данных (2009-2011гг.).
Государственного контракта № 07.514.11.4048 от 06 октября 2011 г. на тему Разработка интеллектуальных методов автоматизированного обнаружения и предотвращения распределенных сетевых атак и их реализация в современных системах облачных вычислений (2011-2012гг.).

Внедрение результатов работы. Основные результаты диссертационной работы были использованы при разработке программного комплекса ППСаИНС для НИЦЭВТ по проекту Триада (свидетельство на регистрацию программы для ЭВМ №а2010610208), разработке программной системы по проекту Космос-НТ Союзного государства (заявка на регистрацию программы для ЭВМ № 2011618769 от 18 ноября 2011) и разработке ФКомплекса программ инструментальных средств построения универсальной моделирующей среды для высокопроизводительной вычислительной системы СКИФФ для ОАО Российские космические системы. Получен акт использования результатов диссертационной работы от НИИ КСаим.аА.А.аМаксимова от 12 января 2012 г.

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

Вторая международная научно-практическая конференция УИсследование, разработка и применение высоких технологий в промышленностиУ. 07-09.01.2006, Санкт-Петербург, Россия.
Научно-техническая конференция ФГУП "РНИИ КП", посвященной. 60-летию предприятия (10-12 октября 2006 г.).
9th International Conference УPattern Recognition and image analysis: New Information TechnologiesФ (PRIA-9-2008) (Nizhni Novgorod, 14-20.09.2008).
First Specialized Symposium УSpace & Global Security of HumanityФ (November 2-4, 2009, Amathus Beach Hotel, Limassol, Cyprus).
III Всероссийская научно-техническая конференция Актуальные проблемы ракетно-космического приборостроения и информационных технологий (1-3 июня 2010 года).

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

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертации, сформулированы цели и задачи работы, раскрыты научная новизна и практическая ценность результатов работы.

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

Таблица 1 - Сравнение основных характеристик программно--инструментальных средств разработки параллельного ПО

		Разработанная ПС	Kepler	ANSYS EKM	Microsoft Workflow Foundation	CODE
1	Параллелизм исполнения задачи	+	+	+	+	+
2	Конвейеризация исполнения задачи	+	+	-	-	-
3	Поддержка модулей системы с внутренним параллелизмом	+	-	-	-	-
4	Возможность исполнения задачи на SMP-архитектуре	+	+	+	+	+
5	Возможность исполнения задачи с использованием КВУ	+	+	+	+	+
6	GUI с поддержкой визуального программирования	+	+	+	+	+
7	Кроссплатформенность	+	+	+	-	-
8	Открытый исходный код	+	+	-	-	+
9	Язык (платформа) реализации	С/С++	Java	Java	.NET	Tcl

Информация о ряде систем, которые можно отнести к программно-инструментальным средствам разработки параллельного (или конвейерно-параллельного) ПО, таких как HeNCE, GRADE, Triana, BMDFM не включена в результаты сравнительного анализа, поскольку данные системы не превосходят приведенные в таблице по функциональным возможностям.

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

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

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

Рисунок 1 - Общая архитектура программно-инструментального комплекса

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

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

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

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

Рисунок 2 - Структурная модель ядра ПС

Приведенная схема демонстрирует основные компоненты ядра системы, наиболее важными из которых являются:

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

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

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

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

Из особенностей вычислительного ядра можно выделить следующее:

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

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

<?xml version="1.0" standalone="yes"?>

<task xmlns="

</module>

</modules>

</channel>

</channels>

</task>

Структурно, описание задачи состоит из двух основных секций:

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

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

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

<?xml version="1.0" encoding="utf-8"?>

</designer>

<init>

</init>

</channels>

</module>

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

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

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

Рисунок 3 - Пример сети Петри, демонстрирующей прикладную задачу

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

ModuleA - непараллельная реализация поставщика ресурсов;
ModuleB - модуль обработчик данных, имеющий параллельную реализацию;
ModuleС - непараллельная реализация потребителя ресурсов.

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

Указанный граф S является конечным автоматом, описывающим основные состояния работы системы диспетчеризации, и может быть формально определен как S = (Q, X, , q0, F) где:

Qа=а{Start, Init, Update, Select, Apply, Wait, End} - конечное множество состояний автомата, описывающих фазы функционирования диспетчера задач;

Xа=а{,аCMD_SENDED, аEVENT_RECEIVED, аCMD_SELECTED, аNO_APPLICABLE_CMDS, аCMDS_NOT_AVAILABLE} - входной алфавит КА, указанные входные символы подаются на вход КА после вычисления предикатов, оценивающих внутреннее состояние системы диспетчеризации (описываемое таблицами занятости вычислителей, списками доступных и применяемых в настоящий момент команд)

- лямбда-переход, оценка внутреннего состояния системы диспетчеризации не производится;
CMD_SENDED - выбранная (применимая) команда передана вычислителю;
EVENT_RECEIVED - получено подтверждение от вычислителя о выполнении команды или создании ресурса подлежащего обработке;
CMD_SELECTED - выбрана применимая команда;
NO_APPLICABLE_CMDS - нет применимых команд;
CMDS_NOT_AVAILABLE Ц список исполняемых в настоящий момент команд пуст.

Рисунок 4 - Граф состояний системы диспетчеризации

: QxX Q - функция перехода КА;

q0 = Start - начальное состояние автомата;

F = {End} - множество терминальных состояний КА.

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

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

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

Алгоритм 1. Общий алгоритм функционирования системы

Чтение xml-файла с описанием решения задачи, чтение xml-описания каждого из требуемых для решения задачи модулей.
Передача вычислительному ядру списка модулей, которые необходимо загрузить. Равномерная загрузка модулей на вычислительных узлах МВС с учетом наложенных пользователем ограничений.
Инициализация каналов передачи данных. Первоначально все каналы находятся в отключенном состоянии. Установка связей переводит их в состояние ожидания.
Начальная инициализация всех модулей на заданных узлах МВС. Ядру передаются значения переменных, которые необходимо установить для каждого из загруженных модулей.
Запуск системы, передача данных через каналы, ожидание завершения работы всех модулей.
Завершение работы системы.

Общая схема взаимодействия Диспетчер управляющих команд ВычислителиМодули, в ходе решения прикладной задачи, представлена на рисунке 5. На данной схеме введены следующие обозначения: S - диспетчер управляющих команд, Wj - вычислитель, ассоциированный с узлом j, mij - модуль i, загруженный на узле j.

Рисунок 5 - Схема взаимодействия компонент системы диспетчеризации

Данная схема определяет связи следующих типов:

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

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

Алгоритм 2. Общий алгоритм работы системы диспетчеризации

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

7.1) Ждать подтверждения от вычислителей

7.2) Обновление внутреннего состояния системы, далее переход к п. 2

Завершение работы.

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

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

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

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

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

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

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

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

Результаты тестирования в виде графиков производительности представлены в таблицах 2-5 и на рисунках 6-8 соответственно.

Прикладная задача поиска и распознавания объектов

Таблица 2 Результаты тестирования производительности (ускорение счета)

		Кол-во вычислительных потоков на узел
		1	2	3	4	5	6	7	8
Кол-во узлов КВУ	1	-	-	-	-	-	-	-	-
	2	1,00	2,19	2,72	2,77	2,93	2,96	2,94	2,96
	3	1,20	3,67	3,59	4,73	4,59	4,61	4,58	4,49
	4	1,26	3,60	3,34	4,81	5,17	5,09	4,83	5,03
	5	1,23	3,43	3,60	5,46	5,78	5,92	5,69	5,56
	6	1,22	3,60	3,08	5,38	4,13	4,73	5,35	3,46

Рисунок 6 График эффективности параллельной реализации

Тестирование показывает, что конвейеризация счета в пределах одного вычислительного узла дает прирост производительности почти в три раза. Наивысшая производительность достигнута при запуске счета задачи в конфигурации 5 узлов КВУ, по шесть вычислительных потоков на каждом, при этом максимальное достигнутое ускорение составляет 5.92.

Прикладная задача обработки изображений ДЗЗ

Таблица 3 Результаты тестирования производительности (ускорение счета)

		Кол-во вычислительных потоков на узел
		1	2	3	4	5	6	7	8
Кол-во узлов КВУ	1	1,00	1,03	1,03	1,03	1,04	1,04	1,03	1,03
	2	2,00	2,05	2,05	2,05	2,05	2,05	2,05	2,05
	3	2,93	2,96	2,96	2,97	2,96	2,96	2,95	2,95
	4	3,08	3,10	3,09	3,67	3,66	3,10	3,09	3,67
	5	3,78	3,82	3,82	3,74	3,81	3,82	3,82	3,81
	6	5,52	5,65	5,56	5,59	5,65	5,61	5,62	5,64

Рисунок 7 График эффективности параллельной реализации

Тестирование производительности на задаче обработки снимков ДЗЗ показывает отсутствие ускорения от конвейеризации вычислений, что объясняется подходом к декомпозиции общего алгоритма решения задачи. Малое количество модулей входящих в схему решения задачи не позволяет эффективно использовать конвейер обработки данных, однако, за счет внутреннего параллелизма основного модуля обработки, присутствует, близкое к линейному, ускорение счета при увеличении количества использованных узлов КВУ.

Прикладная задача контроли и диагностики подсистем КА

Таблица 4 Результаты тестирования производительности (ускорение счета)

		Кол-во вычислительных потоков на узел
		1	2	3	4	5	6	7	8
Кол-во узлов КВУ	1	1,00	1,97	2,43	2,51	2,55	2,55	2,59	2,58
	2	1,77	3,45	3,87	4,59	4,73	4,80	4,78	4,79
	3	2,42	4,54	5,57	6,39	6,47	6,44	6,45	6,47
	4	3,11	5,63	6,35	7,09	7,10	7,21	7,13	7,23
	5	3,60	5,73	7,35	7,90	8,15	8,25	8,06	8,26
	6	3,99	6,33	8,50	8,21	8,12	8,04	8,08	8,10

Рисунок 8 График эффективности параллельной реализации

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

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

В приложении приведены копии документов, подтверждающих практическое использование и внедрение результатов диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

работы из списка, рекомендованного ВАК РФ

Виноградов А.Н., Калугин Ф.В., Недев М.Д., Погодин С.В., Талалаев А.А., Тищенко И.П., Фраленко В.П., Хачумов В.М. Выделение и распознавание локальных объектов на аэрокосмических снимках. - Авиакосмическое приборостроение, 2007, №9, с.39-45. (лично автором - 1 с.)
Ватутин В.М., Круглов А.В., Сашов А.А., Заднепровский В.Ф., Недев М.Д., Талалаев А.А., Фраленко В.П., Хромов О.В., Хачумов В.М., Снегирев В.М. Использование нейронных сетей и средств распараллеливания для высокопроизводительной обработки данных. - Информационно-измерительные и управляющие системы, 2007, №7, т.5, с.48-53. (лично автором - 1 с.)
Талалаев А.А. Особенности архитектуры параллельной программной системыараспознавания графических образов на основе искусственных нейронныхасетей - Нейрокомпьютеры: разработка, применение, 2008, №9, с.43-51.
Константинов К.А., Талалаев А.А., Тищенко И.П., Хачумов В.М. Концепция архитектуры нейросетевой системы контроля, диагностики и обработки изображений космического назначения - Авиакосмическое приборостроение, 2009, №5, с.39-47. (лично автором - 3 с.)
Недев М.Д., Талалаев А.А., Тищенко И.П., Хачумов В.М. Задачи распознавания, географической привязки и наблюдения объектов на основе анализа полутоновых снимков - Авиакосмическое приборостроение, 2009, №12, с. 19-24. (лично автором - 2 с.)
Талалаев А.А. Организация конвейерно-параллельных вычислений для обработки потоков данных - Информационные технологии и вычислительные системы, 2011, №1, с.8-13.
Хачумов В.М. Талалаев А.А. Технические характеристики кластерных вычислителей и анализ эффективности параллельных программных средств обработки потоков данных - Авиакосмическое приборостроение, 2011, №12, c.3-17 (лично автором - 4 с.)

другие работы

Талалаев А.А., Тищенко И.П., Фраленко В.П., Хачумов В.М. Анализ эффективности применения искусственных нейронных сетей для решения задач распознавания, сжатия и прогнозирования. - Искусственный интеллект и принятие решений,а2008, №2, с.24-33.
Талалаев А.А., Тищенко И.П., Хачумов М.В. Выделение и кластеризация текстовых и графических элементов на полутоновых снимках. - Искусственный интеллект и принятие решений, 2008, №3, с.72-84.
Виноградов А.Н., Коданев И.В., Талалаев А.А., Хачумов В.М. Программная система для распознавания графических образов с помощью моделей искусственных нейронных сетей. - Высокие технологии, фундаментальные и прикладные исследования, образование. Сборник трудов Второй международной научно-практической конференции УИсследование, разработка и применение высоких технологий в промышленностиУ. 07-09.01.2006, Санкт-Петербург, Россия. / Под ред. А.П. Кудинова, Г.Г. Матвиенко, В.Ф. Самохина. СПб.: Изд-во Политехн. ун-та, Т. 6:, 2006, с. 6.
Виноградов А.Н., Коданев И.В., Талалаев А.А., Тищенко И.П., Хачумов В.М., Щербаков А.В. Библиотека нейронных сетей для распознавания графических образов на кластерном вычислительном устройстве. - Сб. трудов 2-ой Международной научн.-практической конференции Исследование, разработка и применение высоких технологий в промышленности (07-09.02.2006, Санкт-Петербург) - Санкт-Петербург: Издат.-во Политехнического университета, 2006, с.8-10.
Круглов А.В., Ватутин В.М., Заднепровский В.Ф., Талалаев А.А. Применение нейронных сетей и средств распараллеливания для высокоскоростной обработки потоков данных. - Тезисы докладов научно-технической конференции ФГУП "РНИИ КП", посвященной. 60-летию предприятия (10-12 октября 2006 г.) - М.: ФГУП "РНИИ КП", 2006, с.79-80.
TalalaevаA.A., TishchenkoаI.P., FralenkoаV.P., KhachumovаV.M.. Neural methods in aerospace systems. - 9th International Conference УPattern Recognition and image analysis: New Information TechnologiesФ (PRIA-9-2008): Conference proceedings. (Nizhni Novgorod, 14-20.09.2008) - Н. Новгород, издательство УДиалог КультурФ, т. 2, с.193-196.
Khachumov V.M., Talalaev A.A., Tishenko I.P., Fralenko V.P., Emelyanova J.G., Konstantinov K.A., Pogodin S.V. Program neural network system of telemetric information control, spacecraft subsystems diagnostic and space images processing. Ц First Specialized Symposium УSpace & Global Security of HumanityФ (November 2-4, 2009, Amathus Beach Hotel, Limassol, Cyprus).
КругловаА.В., ВатутинаВ.М., ПоповаС.В., ЗаднепровскийаВ.Ф., ТалалаеваА.А.,аХачумоваВ.М. Методы контроля и диагностики космических подсистем с применением суперкомпьютерных технологий - тезисы трудов III Всероссийской научно-технической конференции Актуальные проблемы ракетно-космического приборостроения и информационных технологий (электронный сборник, 1-3 июня 2010 года).

Авторефераты по всем темам >> Авторефераты по техническим специальностям

Blog