автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.15, диссертация на тему:Анализ и оценка факторов, влияющих на скорость параллельной обработки информации в ГРИД-системах

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

ДРОБНОВ СЕРГЕЙ ЕВГЕНЬЕВИЧ

АНАЛИЗ И ОЦЕНКА ФАКТОРОВ, ВЛИЯЮЩИХ НА СКОРОСТЬ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ИНФОРМАЦИИ В ГРИД-СИСТЕМАХ

Специальность 05.13.15 - "Вычислительные машины, комплексы и компьютерные сети"

Автореферат диссертации на соискание ученой степени кандидата технических наук

1 и АПР ¿2]

Москва-2014

005546990

005546990

Работа выполнена на кафедре «Информатика и информационные системы» (ИИС) федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Московский государственный технический университет радиотехники, электроники и автоматики» (МГТУ МИРЭА).

Научный руководитель: доктор технических наук, профессор

Раев Вячеслав Константинович, профессор кафедры ИИС МГТУ МИРЭА

Кулагин Владимир Петрович

доктор технических наук, профессор, заместитель директора Московского института электроники и математики Национального исследовательского университета «Высшая школа экономики»

Замковец Сергей Всеволодович

кандидат технических наук, заведующий лабораторией Учреждения Российской академии наук «Институт проблем информатики РАН» Ведущая организация: ОАО «Институт электронных

управляющих машин им. И.С.Брука» («ИНЭУМ им. И.С.Брука»)

Защита состоится 14 мая 2014 года в 14-30 на заседании диссертационного совета Д212.131.05 в МГТУ МИРЭА по адресу 119454 г. Москва, пр.Вернадского, д.78, ауд. Д412.

С диссертацией можно ознакомиться в библиотеке МГТУ МИРЭА.

Автореферат разослан 4 апреля 2014 г.

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим направлять по адресу: 119454, г. Москва, пр. Вернадского, д. 78, МГТУ МИРЭА, Д212.131.05.

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

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

Андрианова Е.Г.

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

Актуальность темы. В ИТ-сообществе продолжает возрастать интерес к распараллеливанию ресурсоемких вычислительных задач для последующего их решения посредством ГРИД-систем. В этих системах вычислительная среда представлена в виде соединенных сетью вычислительных узлов, слабосвязанных, гомогенных или гетерогенных компьютеров, работающих вместе для выполнения большого количества заданий. Объемы данных в ГРИД-системах составляют десятки терабайт, а для расчетов задействуются компьютеры по всему миру. Вычислительные мощности, которые обеспечивают ГРИД системы такого масштаба, очень велики и продолжают увеличиваться.

С увеличением масштабов вычислительных систем, состоящих из разнесенных на большие расстояния вычислительных узлов требуются дополнительный анализ, уточнения и обобщения математических методов и оценок с введением новых факторов риска. Становятся все более значимыми и весомыми специфические факторы, сказывающиеся на скорости вычислений и времени, затрачиваемом на решение задач посредством ГРИД-систем. К таким факторам относятся: топология системы, географическая удаленность вычислительных узлов, нестабильность работы большого количества вычислительных узлов и сети, ограничение скорости обмена данными между клиентом и вычислительным узлом, сегментированность, архитектура построения, гомогенность/гетерогенность системы, высокая интенсивность и сложность внешнего информационного обмена, работа на высоких уровнях модели OSI, доступность, настраиваемость и масштабируемость, управляемость параметров. Фундаментальный вклад в теорию и практику параллельных вычислительных технологий и грид-систем внесли выдающиеся ученые, среди которых Е.П. Балашов, В.Б. Бетелин, B.C.

Бурцев, B.B. Васильев, B.B. Воеводин, Вл.В. Воеводин, В.М. Глушков, В.Ф. Евдокимов, Э.В. Евреинов, A.B. Забродин, В.П. Иванников, М.Б. Игнатьев, A.B. Каляев, JI.H. Королёв, С.А. Лебедев, А.О. Лацис, В.К. Левин, Г.И. Марчук, Ю.И. Митропольский, Д.А. Поспелов, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов, В.Г. Хорошевский, I. Foster, G. Amdahl, М. Hill, С. Kesselman и другие. Существующие открытые научные публикации посвящены в основном алгоритмам распределения нагрузки в ГРИД-системах, а также разработке алгоритмов параллельных вычислений.

Цель работы и задачи исследования. Целью настоящей диссертационной работы является восполнение пробела в области анализа и оценки факторов, влияющих на скорость обработки информации в ГРИД-системах, разработка методов расчета скорости вычислений и смежных показателей ГРИД-систем. Предмет исследований диссертации соответствует исследовательской области №4 «Разработка научных методов и алгоритмов организации параллельной и распределенной обработки информации, многопроцессорных, многомашинных и специальных вычислительных систем» специальности 05.13.15 и определяется следующими задачами:

1. Провести анализ зависимости ускорения вычислений от архитектурных особенностей ГРИД-систем с определением оптимального в смысле ускорения вычислений количества вычислительных узлов в конкретных ГРИД-системах.

2. Разработать математическую модель клиент-серверного взаимодействия с учетом особенностей архитектуры и организации ГРИД-систем.

3. Исследовать процесс обучения нейронных сетей с применением ГРИД-систем.

4. Исследовать влияние многоядерности вычислительных узлов на ускорение вычислений в ГРИД-системах.

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

6. Разработать имитационную модель ГРИД-систем для анализа и имитации их работы.

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

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

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

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

Значение полученных соискателем результатов исследования для практики подтверждается тем, что: определены зависимости скорости вычислений в ГРИД-системах от количества вычислительных узлов, что позволило получить уточненные оценки для временных и ресурсных затрат при решении конкретных задач с использованием ГРИД-систем; разработаны методы оценки оптимального в смысле ускорения вычислений количества вычислительных узлов в ГРИД-системах, учитывающие в совокупности и взаимосвязи параметры ГРИД-системы и условия решаемых задач; разработаны методы анализа и оценки времени и ускорения вычислений в ГРИД-системах, что позволило уточнить определение необходимого на решение поставленной задачи времени при известных параметрах системы. На основе рекомендаций диссертационной работы при участии диссертанта в рамках комплекса внедренческих работ и мероприятий Центра НИТ МИРЭА-МГДД(Ю)Т в 2012-2013 гг. на высокопроизводительных вычислительных кластерах разработана и развернула ГРИД-система на основе программной платформы BOINC.

Результаты диссертации внедрены в учебный процесс МГТУ МИРЭА в форме информационного обеспечения блока дисциплин «Математическое моделирование» на факультете «Информационные

технологии» МГТУ МИРЭА, а так же в лекционных курсах «Моделирование» и «Математическое моделирование», читаемых диссертантом.

Апробация работы. Результаты работы доложены и обсуждены на IV, V, VI, VII Всероссийских конференциях "Искусственный интеллект: философия, методология, инновации", конференции «Стандартизация, сертификация, обеспечение эффективности, качества и безопасности информационных технологий» 2011 г., международной заочной научно-практической конференции "Современные вопросы науки и образования -XXI век" 2012 г., 11-ой научно-практической конференции «Современные информационные технологии в управлении и образовании» ФГУП НИИ «Восход» - МИРЭА - МЭСИ, международной научно-практической конференции «Современные направления теоретических и прикладных исследований 2012».

Публикации. По теме диссертации опубликовано 15 статей (включая 3 статьи в журналах из перечня ВАК и 1 монографию в немецком издательстве). Получено свидетельство о государственной регистрации программы для ЭВМ №2012660211 от 24 сентября 2012 г. «Анализатор ускорения распределенных вычислений на алгоритмах кластеризации».

Структура и объем диссертации. Структура диссертации включает в себя развитый Глоссарий из 120 современных терминов и дефиниций, относящихся к теме диссертации, Введение, три главы основного текста, Заключение, Библиографию (116 наименований) и 3 Приложения. Объем диссертации 145 страниц, в т.ч. 50 рисунков и 5 таблиц.

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

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

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

При расчете ускорения вычислений, достигаемого при распараллеливании задачи, часто используют теорию ограничения роста производительности вычислительной системы с увеличением количества вычислительных узлов, известную, как «закон Амдала». Оценку ускорения по Амдалу обычно применяют в отношении практически любой параллельной системе и распараллеливаемой для нее задаче. Кроме того, теория Амдала позволяет получить приближенную оценку максимально достижимого ускорения вычислений. В то же время отмечается, что влияние архитектурных особенностей ГРИД-систем может приводить к падению ускорения вычислений при добавлении вычислительных узлов.

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

С учетом выявленных пробелов в теории и в технических решениях расширены и уточнены задачи исследования.

Во второй главе разработаны и исследованы методы анализа скорости параллельной обработки информации в ГРИД-системах. Рассмотрены факторы, замедляющие процесс параллельной обработки информации. Получено обобщенное выражение для ограничения роста производительности вычислительной ГРИД-системы. Решена задача о минимизации количества вычислительных узлов ГРИД-системы для заданного времени вычислений. Разработаны методы оценки скорости параллельной обработки в ГРИД-системах гомогенного и гетерогенного типа. Проведен анализ производительности вычислительных узлов с многоядерными процессорами. Для ускорения вычислений в ГРИД-системах приняты во внимание три общие рекомендации: 1) передача за одно соединение между вычислительным узлом и сервером несколько пакетов, 2) уменьшение объема пакетов, 3) увеличение количества параллельных потоков для обработки вычислительных узлов. Передача нескольких пакетов за одно соединение позволяет избежать лишних временных задержек Т/ во столько раз, сколько будет передаваться за раз

пакетов. Уменьшение объема пакетов уменьшит временную задержку Т2 и позволит быстрее обмениваться данными серверу и вычислительным узлам. Каждый добавляемый поток обработки берет на себя часть потока запросов от вычислительных узлов, что позволяет не допустить падения ускорения вычислений как можно дольше. Проведен анализ обучения нейронных сетей в ГРИД-системах. Рассмотрены взаимосвязи объема последовательных вычислений и времени обработки пакетов в ГРИД-системах. Приведена динамика характеристик загруженности ГРИД-систем в процессе обработки данных. Показано, что при применении для обучения нейронной сети эволюционных алгоритмов, например, «генетического алгоритма», можно практически на порядок увеличить скорость расчетов в ГРИД-системе.

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

С целью учета этого фактора в работе получено обобщенное выражение для оценки производительности 5 вычислительной ГРИД-системы {Б<1 - замедление расчетов, Б>1 - ускорение расчетов). В этом выражении а - доля последовательных вычислений (значение в интервале от 0 до /); с - количество вычислительных узлов; к - задержка перед началом передачи данных (сек.); t - время расчета одного пакета на одном вычислительном узле (сек.); г - объем пакета (бит), е - скорость передачи

со стороны сервера (бит/сек.); п - количество каналов обработки вычислительных узлов на сервере; т - длина очереди к серверу (2); р -вероятность возникновения очереди к серверу (3):

1

5 (а, с, к, (,е,г,п)~

О)

а + (1 _в).|+ ~ 1 + рЦс, Г-,<),*|,я I

т(г, п) = -

п • и!-

I--

2" г—

> — +-

и!- шах((п — 2),0)

(2)

р(-,п) = ■

й=0

^ и

д! к\ п! шах((и-2),0)

(3)

Максимум ускорения вычислений в зависимости от количества вычислителей определяется выражением:

— 8 (а,с, к^,е,г,п) = 0. 8с

(4)

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

Р(с) = л£. (5)

Применение функции производительности (5) к ГРИД-системам позволяет определить ускорение вычислений, как:

'_ (6)

где <7 - количество ядер в процессоре вычислительного узла, Р -функция оценки производительности при последовательных вычислениях от количества ядер.

Ускорение расчетов в ГРИД по (6) проиллюстрировано на Рис. 1. Из рисунка следует, что количеством ядер д вносится существенный вклад, позволяющий ускорить вычисления в ГРИД-системе и с большей эффективностью использовать задействованные вычислительные узлы.

Рис. 1. Зависимость ускорения расчетов S от количества ядер q в процессоре вычислительного узла: q= 1 (кривая 1), q=5 (кривая 2) и q=40

(кривая 3).

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

В гомогенных ГРИД-системах количество вычислительных узлов, дающее наибольшее ускорение вычислений, будет определяться, как:

^НотоеепеоияС^»^» '"'^тах ) "

, 2-г 1,Г<-

е

е г2 г 2-г _ ,

— е[-,...,--Ст„].

2 г ее

ст„,г>—-ст„

е

(7)

где Г - время расчета одного пакета, е - скорость передачи данных между вычислительными узлами и сервером, г - объем пакета (бит), Стах - общее количество вычислительных узлов.

Для гетерогенных ГРИД-систем количество требуемых вычислительных узлов определяется согласно (8). Здесь N — вычислительная мощность узла (количество вычисленных одним узлом эталонных пакетов в секунду, [ед./сек]), — множество пакетов

решаемой в ГРИД-системе задачи, С (И) — множество вычислительных узлов ГРИД-системы, Qau-cmmt ~ общее количество пакетов.

2-г

V С,

е- I 7Г

е- У — £ в,

2 г

С„,/>-

2 -г

2-г

С, "

(В)

б/

е. У ^

& е,

2-г

о..-™, г

к о,

} ^ [и * -- С1:И-с<т,и \

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

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

Рис. 2. Ускорение вычислений (5) в зависимости от количества вычислителей (с) и времени обработки (Д) одной особи на сервере. В работе проанализирована зависимость между долей последовательных вычислений задач в ГРИД-системе и временем расчета одного пакета.

5 ' х ' 5 а ш 20 30 а

Рис. 3. Зависимость между долей последовательных вычислений и временем расчета одного пакета при 1)8 = 1,2) Б = 2. е- время расчета пакета, а - доля последовательных вычислений.

2)

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

В работе исследована динамика характеристик загруженности ГРИД-систем в процессе решения различного рода задач (Рис. 4).

з- 8-

1

С "тепень

3 атружен •гости серв ера................... -- 2

-

................. 3

вычислительных зщгав

0 0 0.1 2 0.3 0 4 0 5 0 6 0 7 0 8 6 9...... 1

Рис. 4. Области стабильности ГРИД-системы в ходе параллельной обработки информации.

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

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

на базе учебных высокопроизводительных вычислительных кластеров в МГТУ МИРЭА и МГДД(Ю)Т с использованием инфраструктуры BOINC. Проведено компьютерное моделирование решения задач.

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

Рис. 5, 6. Результаты эксперимента, время расчетов (слева). Значения ускорения вычислений по результатам эксперимента (8) и по формуле (1)

(та1Ь_8) (справа).

В ходе проведения эксперимента установлено, что среднее отклонение результатов эксперимента от теоретических значений, полученных диссертантом по разработанной в Главе 2 методике определения ускорения вычислений в ГРИД-системах, составляет 7,77%. Такое отклонение объясняется как задержками во времени на стороне сервера, вычислительных узлов (достаточно сильное влияние на значение

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

В проектах, реализуемых Центром НИТ МИРЭА-МГДЦ(Ю)Т в 2012-2013 гг. при непосредственном участии диссертанта на высокопроизводительных вычислительных кластерах развернула ГРИД-система на основе программной платформы BOINC. На Рис. 7 представлена схема развернутой ГРИД-системы. Для каждого блока пакетов данных выделяется четыре этапа его передачи:

1. Передача пакетов от сервера к клиентам в рамках системы BOINC. За счет информации о кластерах сервер может передать за раз столько пакетов, сколько сможет параллельно обрабатываться на кластерах.

2. Передача заданий от клиентов к вычислительным узлам в рамках структуры кластеров. Кластеры принимают пакеты от сервера и распределяют их по вычислительным узлам в рамках своей структуры. Вычислительные узлы производят параллельную обработку пакетов.

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

4. Передача результатов от клиентов к серверу в рамках системы BOINC. Кластеры отправляют результаты обработки пакетов на сервер.

Рис. 7. Развернутая ГРИД-система на основе программной платформы

BOINC.

Результаты диссертации внедрены в учебный процесс МГТУ МИРЭА в форме информационного обеспечения блока дисциплин «Моделирование», «Математическое моделирование» по кафедре ИИС МГТУ МИРЭА.

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

На защиту выносятся:

1. Метод определения ускорения вычислений в ГРИД-системах, учитывающий влияние архитектурных особенностей этих систем, подкрепленный свидетельством о государственной регистрации программы для ЭВМ №2012660211 "Анализатор ускорения распределенных вычислений на алгоритмах кластеризации". Метод позволяет осуществлять рациональный выбор количества вычислительных узлов исходя из критерия скорости решения конкретной задачи.

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

характеристики вычислительных узлов, особенности архитектуры и организации ГРИД-систем.

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

4. Метод определения ускорения вычислений в ГРИД-системах с учетом влияния многоядерности вычислительных узлов, позволяющий определить влияние устройства вычислительных узлов на ускорение вычислений в анализируемых системах.

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

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

7. Развернутая при непосредственном участии соискателя ГРИД-система на базе вычислительных кластеров в МГТУ МИРЭА, в рамках которой были проведены апробация и внедрение научных положений, выводов и рекомендаций диссертации в учебный процесс факультета «Информационные технологии» МГТУ МИРЭА.

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

Публикации в рецензируемых журналах из списка ВАК:

1. Дробнов С.Е., Раев В.К., Силаев A.B. Оценка ускорения параллельных вычислений в GRID-системах с интенсивным межпроцессорным обменом. // Журнал «Информатизация образования и науки», №3(15)/2012 - М. «Информика», 2012. - С. 135-147.

2. Дробнов С.Е., Сигов A.C., Кошкин Д.Е. Кластеризация текста на основе анализа слов с применением распределенных вычислений. // Журнал «Информатизация образования и науки», №2(10) 04.2011. - М. «Информика», 2011, С. 74-80.

3. Дробнов С.Е. Оценивание ускорения вычислений в распределенных системах. // Научно-практический журнал «Прикладная информатика», Москва, «Синергия», №1(43) 2013, С. 40-48.

Другие статьи и материалы конференций:

4. Дробнов С.Е., Кошкин Д.Е. Анализ ускорения обучения нейронных сетей при применении grid-систем. // IV Всероссийская конференция "Искусственный интеллект: философия, методология, инновации", г. Москва, МИРЭА, 10-12.11.2010.

5. Дробнов С.Е., Кошкин Д.Е. Анализ алгоритмов обучения нейронных сетей в распределенных системах. // Сборник статей, тезисов докладов и материалов к конференции «Стандартизация, сертификация, обеспечение эффективности, качества и безопасности информационных технологий», Москва, 2011.

6. Дробнов С.Е. Анализ количества гетерогенных вычислителей в GRID-системах. // Сборник научных трудов по материалам Международной заочной научно-практической конференции "Современные вопросы науки и образования - XXI век", Тамбов, 29.02.2012.

7. Дробнов С.Е., Кошкин Д.Е. Расчет оптимального количества вычислителей grid-системы. //11 -ая научно-практическая конференции «Современные информационные технологии в управлении и образовании» ФГУП НИИ «Восход» - МИРЭА - МЭСИ, 24.04.2012, Москва, С. 149-155.

8. Дробнов С.Е. Обобщение закона Амдала для большого объема параллельных вычислений в GRID. // Научный вестник МИРЭА, М.:МИРЭА - 2010 - № 2(9), С. 4-7.

9. Дробнов С.Е., Кошкин Д.Е. Кластеризация текстов с помощью нейронных сетей и временная оценка работы алгоритма. // V Всероссийская конференция "Искусственный интеллект: философия, методология, инновации" г. Москва, МИРЭА, 9-11.11.2011, С. 199-202.

10.Дробнов С.Е. Анализ гетерогенных GRID-систем с существенным количеством вычислителей. // Материалы международной научно-практической конференции «Современные направления теоретических и прикладных исследований 2012». - Выпуск 1. Том 3. - Одесса: КУПРИЕНКО, 2012.

11.Дробнов С.Е. Временная оценка обучения нейронных сетей в grid-системах. // Материалы VI Всероссийской конференции студентов, аспирантов и молодых ученых «Искусственный интеллект: философия, методология инновации.», М.: «Радио и Связь», МИРЭА, 29-30.11.2012 -Часть 1,С. 57-63.

12. Дробнов С.Е. Анализ ускорения распределенной обработки информации в GRID-системах. // Lambert Academic Publishing, 27.12.2012, Germany, 67 с.

13.Дробнов С.Е., Кошкин Д.Е. Учебный высоко-производительный вычислительный кластер макромедиа обеспечения на основе дистрибутива PelicanHPC с поддержкой открытой программной

платформы BOINC в учебно-технологических комплексах МИРЭА и МГДЦТ(Ю)Т. // Выпуск 2. ФГУ ГНИИ ИТТ «Информика», МИРЭА, МГДТТ(Ю)Т, 2012/13, С. 73-78.

И.Дробнов С.Е., Раев В.К. Обобщение закона Амдала для распределенных вычислений в информационном образовательном облаке ЭКТРАНЕТ 4 МГДЦ(Ю)Т - МИРЭА. // Избранные материалы докладов, круглых столов и мастер-классов научно-практической конференции "Инновационные пути построения научно-практического образования.", 25.10.2010 г., М.:МГГД(Ю)Т, 2010., С. 25-30.

15.Дробнов С.Е. Аспекты обучения нейронных сетей с применением эволюционных алгоритмов в GRID-системах. // Материалы VII Всероссийской конференции студентов, аспирантов и молодых ученых «Искусственный интеллект: философия, методология инновации», М.: «Радио и Связь», МИРЭА, 13-15.11.2013 г. - Часть 1, С. 106-111.

Подписано в печать: 24.03.2014 Объем: 1,0 п. л. Тираж 100 экз. Заказ №225 Отпечатано в типографии «Реглет» 119526, г. Москва, пр-т Вернадского, д. 39 (495) 363-78-90; www.reglet.ru

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ "МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ"

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

ДРОБНОВ СЕРГЕЙ ЕВГЕНЬЕВИЧ

АНАЛИЗ И ОЦЕНКА ФАКТОРОВ, ВЛИЯЮЩИХ НА СКОРОСТЬ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ИНФОРМАЦИИ В

ГРИД-СИСТЕМАХ

Специальность 05.13.15 - " Вычислительные машины, комплексы и компьютерные сети" (область исследований №4)

ДИССЕРТАЦИЯ

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

Научный руководитель -доктор технических наук, профессор В.К. Раев

Москва-2014

ОГЛАВЛЕНИЕ

ОГЛАВЛЕНИЕ....................................................................................................2

ГЛОССАРИЙ......................................................................................................5

ВВЕДЕНИЕ.......................................................................................................25

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

1.1 Состояние исследований и разработок в области ГРИД-систем. Пути развития распределенных систем................................................................28

1.2 Особенности параллельных вычислений в ГРИД-системах..............31

1.3 Классификация архитектур ГРИД-систем...........................................34

1.4. Стек протоколов ГРИД-систем.............................................................42

1.5 Постановка задачи..................................................................................46

ГЛАВА 2 ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ АНАЛИЗА СКОРОСТИ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ИНФОРМАЦИИ В ГРИД-СИСТЕМАХ......................................................................................................52

2.1 Факторы, замедляющие процесс параллельной обработки информации...................................................................................................52

2.2 Обобщенная формула ограничения роста производительности вычислительной ГРИД-системы.................................................................56

2.3 Задача минимизация количества вычислительных узлов в ГРИД-системах.........................................................................................................58

2.4. Метод оценки скорости параллельной обработки в ГРИД-системах гомогенного типа..........................................................................................60

2.5. Метод оценки скорости параллельной обработки в ГРИД-системах гетерогенного типа.......................................................................................64

2.6. Анализ производительности вычислительных узлов с многоядерными процессорами....................................................................68

2.7 Анализ обучения нейронных сетей в ГРИД-системах........................71

2.8. Взаимосвязь объема последовательных вычислений и времени обработки пакетов в ГРИД-системах.........................................................78

2.9. Динамика характеристик загруженности ГРИД-систем в процессе обработки данных.........................................................................................81

2.10. Краткие выводы...................................................................................83

ГЛАВА 3 ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННЫХ МЕТОДИК ОЦЕНКИ ПРОИЗВОДИТЕЛЬНОСТИ ГРИД-СИСТЕМ. ВОПРОСЫ ПРАКТИЧЕСКОГО ПРИМЕНЕНИЯ..........85

3.1 Разработка архитектуры и структурной схемы моделируемой ГРИД-системы. Имитация решения задач в ГРИД-системе................................85

3.2 Развертывание ГРИД-системы на примере учебных высокопроизводительных вычислительных кластеров МГТУ МИРЭА. .......................................................................................................................102

3.3 Развертывание высокопроизводительного вычислительного кластера на базе дистрибутива РеНсапНРС.............................................................102

3.4 Разработка ГРИД-системы на основе инфраструктуры BOINC......104

3.5 Краткие выводы....................................................................................109

ЗАКЛЮЧЕНИЕ...............................................................................................111

БИБЛИОГРАФИЯ..........................................................................................118

БЛАГОДАРНОСТИ........................................................................................132

ПРИЛОЖЕНИЯ..............................................................................................133

Приложение 1: Акты внедрения ГРИД-системы на базе МГТУ МИРЭА и Московского Государственного Дворца Детского (Юношеского) Творчества.......................................................................................................134

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

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

ГЛОССАРИЙ

1. Abstraction - абстракция - изменение интерфейса объекта и преобразование его в более полезную и подходящую форму.

2. Access - доступ - возможность взаимодействия с системной сущностью (system entity) с целью ее обработки, использования, извлечения сведений и/или получения представления о некоторых или всех ресурсах системной сущности. [RFC 2828]

3. Access control - управление доступом - защита ресурсов от неавторизованного доступа; процесс, посредством которого использование ресурсов регулируется в соответствии с политикой безопасности (security policy) и разрешается только авторизованным системным сущностям (system entity), [RFC 2828].

4. Access control information - информация для управления доступом -

a) Любая информация, используемая в целях управления доступом (access control), включая контекстную информацию. [Х.812]

b) Контекстная информация может содержать исходные 1Р-адреса, шифры, тип запрашиваемой операции, время суток и т.д. Часть информации для управления доступом (access control) может относиться к самому запросу, часть - к связи (connection), посредством которой запрос передается, часть к "среде" (например, время суток) [RFC 2829].

5. Access rights - права доступа - Описание типов авторизованных взаимодействий, которые субъект может иметь с ресурсом. Например, это чтение, запись, исполнение, добавление, модификация и удаление. [WSIA Glossary]

6. Accounting Subsystem (AS) - подсистема учета - предназначена для учета использования вычислительных ресурсов (таких как процессорное время, использование оперативной памяти и так далее), и, в частности, может использоваться для формирования информации о стоимости использования данного ГРИД-ресурса

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

7. Actor - актор -

a) Человек или организация (person or organization) - которые могут быть владельцами агентов (agents), запрашивающих или поставляющих Web-службы (Web services).

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

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

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

10. Anonymity - анонимность - свойство или состояние, при котором имя или идентичность неизвестны или скрыты. [RFC 2828]

11. Anonymous network - анонимная сеть - компьютерные сети, созданные для достижения анонимности в Интернете и работающие поверх глобальной сети.

12. Application - приложение - в контексте толкования ГРИД-компьютинга в целом, "приложение" относится к некоторому "уровню" компонентов, расположенному над уровнями инфраструктуры и ресурсов, Приложение - термин, используемый для идентификации некоторого множества элементов программного обеспечения. Приложение выполняет вычислительные работы,

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

13. Application Layer - прикладной уровень модели OSI - описывает пользовательские приложения, работающие в среде виртуальной организации; приложения функционируют, используя протоколы, определенные на нижележащих уровнях.

14. Application middleware - прикладное промежуточное программное обеспечение - представляет собой специально ориентированное на приложение 111Ю, встроенные индивидуальные возможности и интерфейсы которого отличны от тех, что общеприняты. Например, это программы сбора информации и средств конфигурации службы обнаружения и мониторинга (Monitoring and Discovery Service, MDS). lillllO тесно связано с общецелевым промежуточным программным обеспечением ГРИД-инфраструктуры.

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

16. Architecture - архитектура -

a) архитектура системы программного обеспечения или вычислительной системы - структура или структуры этой системы. Такая структура включает программные компоненты, визуализированные свойства этих компонент, отношения между компонентами и ограничения на их использования;

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

многих фаз работы, и каждый уровень и каждая фаза могут иметь свою архитектуру.

17. Artifact - артефакт - порция цифровой информации. Артефакт может иметь любой объем и может состоять из других артефактов. Примеры артефактов: сообщение, URI (Uniform Resource Identifier), XML-документ, PNG-изображение, поток битов.

18. Attribute - атрибут - отличительная характеристика, описывающая объект. Атрибуты реальных объектов часто специфицируются в терминах физических характеристик объектов, таких как размер, форма, вес, цвет и т.д. Атрибуты объектов киберпространства могут описывать их размер, способ кодирования, сетевой адрес и т.д. [WSIA Glossary]

19. Audit guard - защита аудита - используемый от имени владельца механизм, который позволяет контролировать действия и агентов (agents) для подтверждения выполнения обязательств (obligations).

20. Authentication - аутентификация - процесс проверки и подтверждения, что потенциальный партнер по общению действительно представляет человека или организацию (person or organization).

21. Base GRID service - базовая служба ГРИД - обеспечивает работу всей ГРИД-системы в целом; службы подразделяются на следующие подсистемы: подсистема управления загрузкой (Workload Management System, WMS), подсистема управления данными (Data Management System, DM), подсистема информационного обслуживания и мониторинга ГРИД-системы (Information System, IS), подсистема безопасности и контроля прав доступа (Grid Security Infrastructure, GSI), подсистема протоколирования (Logging and Bookkeeping, LB), подсистема учета (Accounting Subsystem, AS).

22. Binding - связывание -

а) связь между интерфейсом (interface), конкретным протоколом (protocol) и форматом данных. Связывание определяет, какой

8

протокол и какой формат данных нужно использовать для передачи сообщений, определенных связанным интерфейсом [WSD Reqs];

b) установление соответствия между интерфейсом (interface) и связанными с ним операциями (operations), с одной стороны, и форматом конкретного сообщения и протоколом его передачи (protocol), с другой стороны;

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

24. Calculation acceleration - ускорение вычислений - изменение скорости вычислений в одной системе при сравнении со скоростью вычислений в другой системе.

25. capability - возможность, способность - поименованная часть функциональности (или свойство), которая объявлена как поддерживаемая или запрашиваемая агентом (agent).

26. Certificate - сертификат - имеющее электронную подпись утверждение одной сущности (например, сертификационного центра) о том, что открытый ключ (и какая-то другая информация) другой сущности (например, пользователя ГРИД) имеет некоторый определенный смысл. Стандарт Х.509 определяет, какая информация должна содержаться в сертификате, и описывает, в каком виде она должна быть в нем записана (формат данных).

27. Certificate authority - сертификационный центр - сущность, которая выпускает сертификаты. В OSG признаются сертификаты, выпускаемые целым рядом сертификационных центров, например, Сертификационная Служба DOEGrids.

28. Choreography - хореография -

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

независимыми агентами (agent). При помощи этого обмена выполняется задача достижения целевого состояния.

Ь) Хореография Web-служб касается взаимодействия служб с их пользователями. Любой пользователь Web-службы, автоматический или нет, является клиентом этой службы. В качестве пользователей могут выступать другие Web-службы, приложения или люди. Транзакции между Web-службами и их клиентами должны быть четко определены во время их выполнения и могут состоять из множества отдельных взаимодействий, чья композиция составляет полную транзакцию. Эта композиция, ее протоколы передачи сообщений, интерфейсы, установление последовательности и ассоциированная логика и составляет то, что называется хореографией. [WSC Reqs]

29. Cluster - кластер - доступная по сети группа рабочих узлов (при необходимости вместе с головным узлом), размещённая на некотором сайте. Согласно определению в схеме GLUE, кластер это контейнер, который группирует вместе подкластеры или компьютерные узлы.

30. Cluster and multi-cluster GRIDs model - кластерная и мультикластерная модель ГРИД.

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

32. Collective Layer - коллективный уровень отвечает за координацию использования имеющихся ресурсов.

33. Collision domain - домен коллизий - это часть сети ethernet, все узлы которой конкурируют за общую разделяемую среду передачи и, следовательно, каждый узел которой может создать коллизию с любым другим узлом этой части сети.

34. Color Pétri net - Цветная сеть Петри.

35. Component - компонент -

a) Объект программного обеспечения, предназначенный для взаимодействия с другими компонентами, инкапсулирующий некоторую функциональность или набор функциональностей. Компонента имеет четко определенный интерфейс и ведет себя заранее определенным образом, общим для всех компонент в рамках архитектуры [ССА T&D].

b) Абстрактная единица программного обеспечения и внутреннего состояния, которая обеспечивает преобразования данных через свой интерфейс [Fielding].

c) Единица архитектуры с определенными границами.

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

37. Connection - соединение - виртуальный канал связи транспортного уровня, установленный между двумя программами для их коммуникации [RFC 2616].

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

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

40. Data center - центр обработки данных - специализированное здание для размещения (хостинга) серверного и коммуникационного оборудования и подключения абонентов к каналам сети Интернет.

41. Data communication protocol - протокол передачи данных - набор соглашений интерфейса логического уровня, которые определяют обмен данными между различными программами.

42. Data federation - объединение данных - процесс интеграции данных в одном виртуальном месте для быстрого удовлетворения запроса прикладной программы.

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

44. Decommissioning - вывод из эксплуатации - процесс уничтожения компонента ГРИД, после которого компонент становится недоступным для планировщика.

45. Digital signature - цифровая подпись - значение, которое вычисляется по криптографическому алгоритму и присоединяется к объекту данных таким образом, что любой получатель этих данных может использовать эту подпись для проверки источника и целостности данных. (См data origin authentication service, data integrity service, digitized signature, electronic signature, signer в [RFC 2828]).

46. Discovery - обнаружение - определение местонахождения машинно-обрабатываемого описания ресурса, связанного с Web-службой (Web service) Ресурс до