Содержание к диссертации
Введение
1 Методы повышения эффективности использования вычислительных ресурсов для выполнения вычислительных задач 15
1.1 Параллельные вычисления 15
1.2 Распределенные вычисления 17
1.3 Архитектуры программного обеспечения для организации распределенных вычислений 1.3.1 Клиент-сервер 19
1.3.2 Трехуровневая архитектура 20
1.3.3 Сервис-ориентированная архитектура 22
1.3.4 Сравнение архитектур программного обеспечения для организации распределенных вычислений 24
1.4 Технологии создания программного обеспечения для организации распределенных вычислений 25
1.4.1 Сокеты Беркли 25
1.4.2 Удаленный вызов процедур 26
1.4.3 CORBA 27
1.4.4 Java Platform Enterprise Edition 28
1.4.5 Сервисная шина предприятия 29
1.4.6 Windows Communication Foundation 31
1.4.7 Анализ технологий создания программного обеспечения для организации распределенных вычислений 32
1.5 Современные реализации программного обеспечения для организации распределенных вычислений з
1.5.1 BOINC 33
1.5.2 GPU: Global Processor Unit 35
1.5.3 Базис 35
1.6 Выводы 37
2 Модель программной платформы организации распределенных вычислений в локальной сети 40
2.1 Требований к программному комплексу организации распределенных вычислений 40
2.2 Концепция единой вычислительной среды 41
2.3 Способы распределения задач по узлам сети
2.3.1 Алгоритм случайного распределения задач 44
2.3.2 Алгоритм детерминированного распределения задач 45
2.3.3 Алгоритм пульсирующего кольца 47
2.3.4 Адаптивно-оптимальный алгоритм 51
2.4 Функциональная модель платформы единой вычислительной среды 56
2.4.1 Узел А-0 56
2.4.2 Узел А0 57
2.4.3 Узел А1 60
2.4.4 Узел А2 61
2.4.5 Узел А5 62
2.4.6 Узел А52 63
2.4.7 Узел А54 65
2.4.8 Узел А6 66
2.5 Модель протоколов взаимодействия 67
2.5.1 Протокол Узел – Узел 67 2.5.2 Протокол Узел – Пользовательское приложение 69
2.5.3 Протокол Узел – Вычислительный модуль 70
2.6 Структурная модель платформы единой вычислительной среды 70
2.6.1 Общая структура системы 70
2.6.2 Структура диспетчера 73
2.6.3 Структура пользовательского приложения 75
2.6.4 Структура вычислительного модуля 76
2.7 Выводы 77
3 Проект программной платформы единой вычислительной среды 79
3.1 Проектирование взаимодействия объектов 80
3.1.1 Основные сценарии функционирования 80
3.1.2 Сценарий запроса о выполнении задачи 81
3.1.3 Сценарий выбора узла и отправки задачи 81
3.1.4 Сценарий выполнения вычислительной задачи при помощи модуля
3.1.5 Сценарий возврата результата вычислений пользовательскому приложению 85
3.1.6 Сценарий включения узла в вычислительную среду 87
3.1.7 Сценарий выключения узла 88
3.1.8 Сценарий получения модуля узлом 89
3.1.9 Сценарий поиска узлов в сети 90
3.2 Проектирование структуры компонентов и классов 91
3.2.1 Алгоритм распределения задач по узлам сети 95
3.2.2 Результаты имитационного моделирования алгоритмов распределения задач по узлам сети 98 3.2.3 Поиск узлов в локальной сети 132
3.2.4 Канал взаимодействия пользовательского приложения и диспетчера.. 139
3.3 Выводы 142
4 Исследование прототипа программной платформы единой вычислительной среды 145
4.1 Методы исследования прототипа 145
4.2 Численное интегрирование методом прямоугольников 147
4.3 Определение площади фигуры методом Монте-Карло 148
4.4 Применение медианного фильтра к растровому изображению 150
4.5 Обобщение результатов тестирования 154
4.6 Выводы 155
Заключение 157
Список сокращений и условных обозначений 159
Список литературы 160
- Сравнение архитектур программного обеспечения для организации распределенных вычислений
- Способы распределения задач по узлам сети
- Сценарий возврата результата вычислений пользовательскому приложению
- Определение площади фигуры методом Монте-Карло
Введение к работе
Актуальность диссертационного исследования. В настоящее время задача интеграции вычислительных и информационных ресурсов в единую среду и организация эффективного доступа к ним является одной из основных в современных информационных технологиях. Связано это, в первую очередь, с бурным развитием сетевых технологий и значительным увеличением скорости и надежности передачи данных в сетях. Существующие реализации направленных на интеграцию технологий варьируются от крупных бизнес-ориентированных решений, включающих в себя автоматизацию документооборота и управление технологическим процессом (Microsoft SharePoint, Microsoft Team Foundation, 1С-Предприятие, SCADA и др.) до решений для широкого круга потребителей, направленных на упрощение обмена и хранения пользовательских данных (Apple iCloud, Dropbox, Microsoft OneDrive и др.).
Характерной особенностью перечисленных систем является их ориентированность на информационный обмен, в то время как вопрос об интеграции именно вычислительных ресурсов в них либо не решен вовсе, либо имеет узкоспециализированную направленность и ориентирован на специальный класс прикладных задач. Вместе с тем, основной целью интеграции вычислительных ресурсов является повышение эффективности использования вычислительных ресурсов для выполнения вычислительных задач. В первую очередь это обусловлено постоянно повышающимися потребностями предприятий в проведении комплексной обработки больших объемов данных. В качестве примеров подобных потребностей могут служить:
научные вычисления, проводимые в научных лабораториях и комплексах, в том числе тематическая обработка экспериментальных данных;
имитационное моделирование различных систем;
-обработка большого объема графической, видео и аудио информации в различных целях, в том числе в системах безопасности;
- и другие.
Несомненно, одним из путей увеличения производительности компьютерных систем и уменьшения времени выполнения вычислительных задач является модернизация вычислительного оборудования. Однако подобное решение сопряжено с большими финансовыми затратами на его реализацию. Поэтому особенно остро стоит проблема эффективного использования доступных вычислительных ресурсов, особенно в свете их интеграции в вычислительную сеть. Таким образом, объектом
диссертационного исследования являются методы интеграция вычислительных ресурсов.
Двумя основными подходами к увеличению эффективности использования вычислительных ресурсов являются параллельные вычисления и распределенные вычисления. Эти подходы дополняют друг друга, при этом распределенные системы применимы для более широкого класса задач, отдельные части которых могут быть параллельными, за счет одновременного выполнения нескольких задач одновременно.
Отдельное место в проблеме интеграции вычислительных ресурсов занимает вопрос об интеграции ресурсов отдельной локальной корпоративной сети, так как локальные сети имеют следующие особенности:
высокая скорость передачи данных по сравнению с глобальными сетями;
высокая надежность передачи данных по сравнению с глобальными сетями;
низкие задержки при передаче данных.
Существует множество методов и технологий, позволяющих распределить вычисления по узлам локальной сети, от самых простых (сокеты Беркли, удаленный вызов процедур) до высокоразвитых и сложных (Java Enterprise Edition, Windows Communication Foundation). Использование данных технологий позволяет разработчику приложения использовать вычислительные ресурсы нескольких компьютеров для решения своих прикладных задач.
Однако для этих технологий все вопросы по управлению вычислительным процессом - такие как приоритеты операций, выбор узла для вычисления, отслеживание ошибок и другие ложатся на плечи разработчика. Таким образом, увеличивается трудоемкость разработки программного обеспечения и, как следствие, длительность и стоимость разработки.
Очевидным решением данной проблемы является реализация автоматического управления вычислительным процессом. В связи с этим свое бурное развитие получили технологии «облачных вычислений» и GRID. Однако существующие реализации таких технологий являются централизованными, что существенно сказывается на отказоустойчивости подобных систем - неработоспособность сервера может сделать неработоспособной всю вычислительную сеть. Другими словами, проблемной ситуацией в объекте диссертационного исследования является потребность в эффективном методе интеграции вычислительных ресурсов отдельной локальной сети при отсутствии в настоящее время решений данной задачи, удовлетворяющих большинству требований практики.
Из вышесказанного следует, что актуальной является проблема создания распределенной платформы с децентрализованным управлением,
обеспечивающей эффективную интеграцию доступных вычислительных
ресурсов локальной сети. Подобная платформа должна, с одной стороны,
обеспечивать необходимую гибкость и поддерживать широкий круг задач,
повысить надежность системы в целом, с другой стороны, снимать с
разработчиков приложений необходимость решать вопросы планирования и
управления вычислительным процессом, что позитивно скажется на сроках и
стоимости разработки распределенных приложений. Новая методология
должна существенно повысить эффективность использования имеющихся
вычислительных ресурсов и позволить увеличить сложность решаемых задач
без использования дополнительного оборудования. Предметом
диссертационного исследования является организация распределенных вычислений в локальной сети путем реализации адаптивных протоколов распределения задач по процессорам и программной платформы с децентрализованным управлением.
Актуальность данной задачи подтверждается включением задачи «Информационно-телекоммуникационные системы» в список приоритетных направлений развития науки, технологии и техники в Российской Федерации и внесением «Технологии и программное обеспечение распределенных и высокопроизводительных систем» в перечень критических технологий Российской Федерации.
Целью настоящей работы является повышение эффективности
интеграции вычислительных ресурсов локальной сети, а также
эффективности проектирования, создания и эксплуатации распределенных приложений путем создания модели методов распределения вычислительных задач по узлам сети и реализации платформы, объединяющей локальные вычислительные ресурсы в единую вычислительную среду. Для достижения поставленной цели необходимо решить следующие задачи:
-
Определение набора требований к платформе по эффективной интеграции вычислительных ресурсов.
-
Функциональное проектирование модели платформы.
-
Структурное проектирование модели платформы.
-
Разработка моделей методов распределения задач по узлам сети.
-
Оценка эффективности моделей методов распределения задач по узлам сети путем численного моделирования.
-
Проектирование взаимодействия элементов платформы.
-
Реализация прототипа платформы.
-
Исследование прототипа платформы для оценки эффективности распределения.
Научная новизна.
1. Разработаны адаптивные гибридные алгоритмы распределения
вычислительных задач по узлам сети, реализующие в зависимости от
нагрузки случайный или детерминированный метод доступа и
обеспечивающие значительное увеличение скорости решения
вычислительных задач.
-
Разработан численный метод оценки параметров модели распределения вычислительных задач по узлам сети, основанный на методе моделирования дискретных событий и переходов состояний, позволяющий оценить среднее время ожидания вычислительных задач, среднюю задержку вычислительных задач, количество передаваемых данных и отношение «операции алгоритма/полезная работа».
-
Разработана программная платформа распределенных вычислений, реализующая принцип единой вычислительной среды с децентрализованным управлением, объединяющая вычислительные ресурсы локальной сети в единую среду и обеспечивающая существенное повышение степени использования доступных вычислительных ресурсов сети.
Положения, выносимые на защиту:
-
Математическая модель адаптивного гибридного (случайный/детерминированный) метода распределения задач по узлам сети, обеспечивающего сокращение временных затрат на инициализацию вычисления задачи (ожидание и распределение) в 2-3 раза.
-
Численный метод оценки параметров модели распределения вычислительных задач по узлам сети, основанный на методе моделирования дискретных событий и переходов состояний, позволяющий оценить среднее время ожидания вычислительных задач, среднюю задержку вычислительных задач, количество передаваемых данных и отношение «операции алгоритма/полезная работа».
-
Программная платформа распределенной обработки информации, реализующая единую вычислительную среду, отличающаяся тем, что с целью повышения надежности и оперативности развертывания, использовано децентрализованное управление, обеспечивающая увеличение скорости решения задач в 3 раза при сравнении с однопоточными реализациями и на 30% при сравнении с многопоточными реализациями.
Методы исследования. В качестве основных методов исследования выбраны методы системного анализа, метод имитационного моделирования и эксперимент, опирающийся на математический аппарат статистического анализа; метод функционального проектирования по методологии IDEF0: метод структурного проектирования; методы объектно-ориентированного проектирования; методы функционального и объектно-ориентированного программирования.
Теоретическая и практическая значимость работы.
1. Разработанные модель и программное обеспечение платформы по объединению вычислительных ресурсов локальной сети в единую вычислительную среду послужили основой для создания программного
комплекса «DistributedSystem» – универсальной платформы для организации научных вычислений и решений широкого круга вычислительных задач.
-
Разработанные в диссертации гибридные алгоритмы распределения задач по узлам сети, сочетающие в себе алгоритмы случайного распределения задач и детерминированного распределения задач в зависимости от нагрузки, могут быть использованы при реализации распределенных приложений различного масштаба.
-
Разработанная в диссертации модель платформы использована в проведении в научно-исследовательской работы «Разработка технологий активного и пассивного зондирования атмосферы земли в оптическом и радио диапазонах для создания распределенной информационно-вычислительной системы комплексной обработки, передачи и использования экспериментальных данных», проведенной на кафедре оптико-электронного систем и дистанционного зондирования Томского Государственного Университета (ТГУ) (шифр работы «2013-1.5-14-515-0036-109»).
-
Программно-техническая система создания единой вычислительной среды «DistributedSystem», созданная в рамках диссертационного исследования, используется в Федеральном государственном бюджетном учреждении науки Институт оптики атмосферы им. В.Е. Зуева Сибирского отделения Российской академии наук (ИОА СО РАН) для решения вычислительных задач атмосферной оптики.
-
Теоретические результаты исследования используются в учебном процессе на факультете автоматизированных систем Томского государственного университета систем управления и радиоэлектроники (ТУСУР) в рамках группового проектного обучения (ГПО).
Достоверность результатов диссертационной работы
подтверждается экспериментальными данными, полученными при
использовании программно-технических систем, созданных при
непосредственном участии соискателя, имеющими как научную, так и
практическую ценность. Достоверность результатов, выводов и положений
диссертационной работы обеспечивается тщательной разработкой методик и
алгоритмов создания и функционирования распределенных систем, а также
практическим использованием результатов в научно-исследовательском и
образовательном процессе Томского государственного университета (ТГУ) и
Томского государственного университета систем управления и
радиоэлектроники (ТУСУР).
Личный вклад автора в работы заключается в непосредственном участии на всех этапах исследований: аналитический обзор современных архитектур, технологий и реализаций систем распределенных вычислений, формулирование требований к эффективной платформе, разработка алгоритмов и программ, проведение имитационного моделирования и экспериментов, анализ и интерпретация результатов экспериментов,
написание статей. Основные результаты, включенные в диссертацию и выносимые автором на защиту, получены автором самостоятельно. Постановка задач исследований осуществлена соискателем как единолично, так и в соавторстве с научным руководителем.
6. Внедрение работы. На разработанный программных комплекс
получено свидетельство о регистрации программ для ЭВМ №2013616043
«Программа создания единой вычислительной среды в локальной сети:
DistributedSystem», дата регистрации 26 июня 2013 г. Программно-
техническая система создания единой вычислительной среды
«DistributedSystem» используется в Федеральном государственном
бюджетном учреждении науки Институт оптики атмосферы им. В.Е. Зуева
Сибирского отделения Российской академии наук (ИОА СО РАН) для
решения вычислительных задач атмосферной оптики. Положения
диссертации нашли отражение в научно-исследовательской работе,
выполненной Национальным исследовательским Томским государственным
университетом с участием автора в рамках программ Минобразования и
науки РФ, «Разработка технологий активного и пассивного зондирования
атмосферы земли в оптическом и радио диапазонах для создания
распределенной информационно-вычислительной системы комплексной
обработки, передачи и использования экспериментальных данных» (шифр
2013-1.5-14-515-0036-109) в рамках ФЦП «Исследования и разработки по
приоритетным направлениям развития научно-технического комплекса
России на 2007-2013 годы». Результаты диссертационной работы,
используются в учебном процессе кафедры оптико-электронных систем и
дистанционного зондирования РФФ ТГУ для бакалаврской подготовки по
направлению 12.03.02-«Оптотехника», для магистерской подготовки по
направлению 12.04.02-«Оптотехника». Разработанные автором модели,
алгоритмы и программные средства используются при проведении
практических занятий по дисциплинам «Информационные технологии в
оптотехнике», «Компьютерные технологии». Результаты диссертационной
работы используются в учебном процессе кафедры АСУ
(автоматизированные системы управления) ФСУ ТУСУР для бакалаврской
подготовки по направлению 230100.62-«Информатика и вычислительная
техника». Разработанные автором модели, алгоритмы и программные
средства используются при проведении практических занятий по дисциплине
«Параллельное программирование».
Связь работы с научными программами и темами.
Диссертационная работа выполнена в федеральном государственном
автономном образовательном учреждении высшего образования
«Национальный исследовательский Томской государственный университет» в соответствии с планами государственных и отраслевых научных программ: проект «Разработка технологий активного и пассивного зондирования
атмосферы земли в оптическом и радио диапазонах для создания распределенной информационно-вычислительной системы комплексной обработки, передачи и использования экспериментальных данных» (шифр 2013-1.5-14-515-0036-109) в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технического комплекса России на 2007-2013 годы».
Апробация работы.
Основные научные результаты работы докладывались и обсуждались
на следующих конференциях: международная заочная научно-практическая
конференция «Вопросы образования и науки: теоретический и методический
аспекты» (г. Тамбов, 2012); международная научно-практическая
конференция «Перспективные инновации в науке, образовании, производстве
и транспорте ‘2012» (г. Одесса, 2012); XIV международная научно-
техническая конференция «Измерение, контроль, информатизация» (г.
Барнаул, 2013); международная научно-практическая конференция
«Актуальные проблемы радиофизики» (г. Томск, 2013, 2015);
международный симпозиум «Оптика атмосферы и океана. Физика атмосферы» (г. Новосибирск, 2014, г. Томск, 2015).
Основное содержание диссертации отражено в 14 публикациях, в том
числе 5 статей в журналах, включенных в Перечень рецензируемых научных
изданий, в которых должны быть опубликованы основные научные
результаты диссертаций на соискание ученой степени кандидата наук, на
соискание ученой степени доктора наук, и приравненных к ним (из них 1
свидетельство о государственной регистрации программы для ЭВМ), 2
публикации в сборниках материалов научных конференций, изданных за
рубежом и индексируемых Web of Science, 2 статьи в научных журналах, 2
статьи в сборниках научных трудов, 3 публикации в сборниках материалов
международной научно-практической конференции и международного
симпозиума.
Структура диссертации. Диссертация состоит из введения, основной части, включающей в себя четыре главы, заключения, списка сокращений и условных обозначений, списка используемой литературы из 74 источников, 4 приложений. Объем диссертационной работы составляет 190 страниц. Работа иллюстрируется 80 рисунками и 7 таблицами.
Сравнение архитектур программного обеспечения для организации распределенных вычислений
Распределенная система — это набор независимых компьютеров, представляющиеся их пользователям единой объединенной системой [21]. Распределенные вычисления не могут производиться на одной вычислительной машине, а параллельные вычисления могут производиться как на одной (многопоточность), так и на нескольких машинах. Возможность выполнения параллельных вычислений в распределенных системах и приводит к частому заблуждению, что это одно и тоже, однако это не так.
Распределенные вычисления обладают рядом преимуществ по сравнению с параллельными вычислениями: - Распределенные системы способны решать значительно более широкий круг задач, включая параллельные и последовательные алгоритмы обработки данных. Эффективность последовательных вычислений достигается за счет одновременного решения многих задач [22]. - Возможность неограниченного наращивания производительности за счет простоты масштабирования [21]. - Кроссплатформенность. Слабосвязность компонентов распределенных систем позволяет создавать их в гетерогенной среде, в том числе на наборе узлов, управляемых разными операционными системами.
С точки зрения полномочий участников распределенной системы их можно разделить на централизованные и децентрализованные.
В централизованных распределенных системах доступом к ресурсам управляет сервер, который играет роль главного компьютера для всех остальных узлов распределенной системы. Основными архитектурами централизованных распределенных систем являются клиент-сервер, трёхуровневая архитектура, облачные вычисления и GRID. Наиболее распространённым примером существующих реализаций подобных систем можно считать BOINC. Минус централизованных распределенных систем очевиден – неработоспособность сервера может сделать неработоспособной всю вычислительную сеть. Неработоспособным сервером следует считать сервер, производительности которого не хватает на обслуживание всех клиентов, а также сервер, находящийся на ремонте, профилактике и т.д. [23]
Децентрализованная распределенная система основана на равноправии её участников. Часто в такой системе отсутствуют выделенные серверы, а каждый узел является как клиентом, так и выполняет функции сервера. Данный тип распределенных систем лишен главного недостатка централизованных, позволяет сохранять работоспособность сети при любом количестве и любом сочетании доступных узлов [24]. Основной архитектурой децентрализованных распределенных систем является сервис-ориентированная архитектура, а примером реализации – Базис.
Второй по важности вопрос, связанный с построением распределенных систем – ориентированность на глобальные и локальные сети. Использование глобальных распределенных систем выглядит очень перспективно и позволяет использовать вычислительные мощности большого числа компьютеров. Однако это накладывает серьезное ограничение на круг задач, решаемых распределенной системой. Основными препятствиями являются нестабильность, плохая предсказуемость времени отклика на запрос и низкие скорости передачи данных. Распределенная система, ориентированная на использование в глобальных сетях, вынуждена учитывать данные препятствия в используемых алгоритмах распределения, что в значительной мере увеличивает время обработки вычислительных задач и не позволяет эффективно организовать вычисления с интенсивным обменом информацией между процессорами, выполняющими отдельные подзадачи [25]. Использование же локальной сети лишает распределенную систему данного недостатка и существенно расширяет круг задач, которые данная система способна эффективно решать.
Клиент-сервер (англ. Client-server) – вычислительная или сетевая архитектура, в которой задания или сетевая нагрузка распределены между поставщиками услуг (сервисов), называемыми серверами, и заказчиками услуг, называемыми клиентами. Функциональные части системы взаимодействуют по схеме «запрос-ответ». Если рассмотреть две взаимодействующие части этого комплекса, то одна из них (клиент) выполняет активную функцию, т. е. инициирует запросы, а другая (сервер) пассивно на них отвечает [26]. Упрощенная схема архитектуры представлена на рис. 1.1.
Такая архитектура позволяет распределить функции вычислительной системы между несколькими независимыми компьютерами в сети, хранить все данные на сервере, защищенные от несанкционированного доступа, объединять различных клиентов для решения одной задачи. Однако существенным недостатком такой архитектуры является асимметрия системы, в результате которой нагрузка на сервер всегда выше, чем на остальные процессоры сети. Кроме того, эксплуатация системы требует наличия высококвалифицированных специалистов – системных администраторов, обеспечивающих эффективную работоспособность. Что касается надежности системы, неработоспособность сервера может сделать неработоспособной всю вычислительную сеть [26].
Способы распределения задач по узлам сети
Суть детерминированного алгоритма состоит в том, что при поступлении новой вычислительной задачи от пользователя платформа собирает информацию о загруженности всех входящих в вычислительную среду узлов, ранжирует узлы по значению целевой функции и отправляет задачу на тот узел, значение целевой функции которого минимально.
В качестве информации о загруженности могут выступать следующие числовые параметры узлов: 1. Параметра канала связи [45]: 1.1. пропуская способность канала связи между узлом, на который поступила задача и оцениваемым узлом; 1.2. время прохождения единичного пакета по каналу связи между узлом, на который поступила задача и оцениваемым узлом; 1.3. процент потерянных пакетов в канале связи между узлом, на который поступила задача и оцениваемым узлом. 2. Постоянные параметры узла [46]: 2.1. общий объем оперативной памяти узла; 2.2. производительность процессора узла (количество операций в секунду) [47]. 3. Переменные параметры узла [46]: 3.1. текущий объем свободной оперативной памяти; 3.2. текущая загруженность процессора; 3.3. скорость обмена страниц в памяти; 3.4. средняя длина очереди диска. В качестве целевой функции достаточно использовать взвешенную дискретную весовую функцию: п І = 1 где at - нормированный -тый параметр, п - количество параметров, & j - весовой коэффициент і-того параметра (весовые коэффициенты параметров определяются на этапе развертывания вычислительной среды).
Несомненным плюсом данного алгоритма является оптимальное распределение вычислительных задач по узлам сети. При правильном подборе набора параметров и значений весовых коэффициентов можно гарантировать, что вычислительная задача будет направлена на наименее загруженный узел в вычислительной среде, а время ее выполнения будет минимальным.
Недостатком такого подхода является тот факт, что для эффективного функционирования системы требуются значительные вычислительные затраты. Для каждой вычислительной задачи, поступившей в вычислительную среду, каждый из узлов должен собрать значения оценочных параметров и направить их на узел, в который задача поступила. Несомненно, что часть параметров меняются редко (группы параметров 1 и 2), и их можно вычислять лишь через определенные промежутки времени, а не для каждой поступившей вычислительной задачи. Но, тем не менее, остаются параметры группы 3, которые необходимо вычислять для каждой задачи отдельно. Кроме того, передача полного набора значений параметров для каждой задачи остается необходимой. Таким образом, каждая поступившая в вычислительную среду задача вызывает серию тестов для определения параметров на каждом из узлов среды и передачу значений этих параметров на узел, в который задача поступила. В режиме низкой нагрузки подобный подход может и имеет значение, но в режимах средней и высокой нагрузок и при большом количестве узлов в сети затраты на данный алгоритм становятся неоправданно большими.
В алгоритме пульсирующего кольца каждому узлу вычислительной сети назначается определенное количество элементарных ячеек вычисления. Под элементарной ячейкой понимается логическая единица возможности узла по проведению вычисления. Количество ячеек, назначенных узлу, определяется производительностью узла; это количество равно количеству задач, которые узел может вычислять одновременно и параллельно без существенного возрастания времени их выполнения. Считается, что количество ячеек узла определено заранее и не меняется в процессе функционирования системы.
Ячейки объединены в кольцо S и разбиты на логические группы V = {vlt v2, vm}. В каждую группу может входить от одной до п ячеек. Количество групп в процессе функционирования системы меняется в моменты так называемых «пульсаций». Также в системе имеет маркер М, указывающий на одну из групп. Графически логические элементы алгоритма представлены на рисунке 2.2. v2
Процесс функционирования системы тактирован. Допустим, что в любой момент времени все узлы вычислительной системы имеют полную и актуальную информацию о состоянии кольца. Между тактами платформа накапливает поступающие задачи пользователя. На каждом такте работы системы ее работа проходит по следующему алгоритму: Маркер М сдвигается на следующую группу. (і + 1, если і \V\ М - О, если і = \V\ Обрабатываются j поступивших с момента прошлого такта вычислительных задач. На данном этапе возможны следующие варианты: 2.1. Задач нет (j = 0). В этом случае текущая группа vt объединяется с группой vm, количество групп сокращается на 1 (кроме случая, когда группа уже одна и включает все ячейки). 2.2. Поступила одна задача (j = 1). В этом случае из текущей группы выбирается одна ячейка, в которую и отправляется вычислительная задача.
Количество поступивших задач меньше или равно количеству ячеек в текущей группе (у \Vi\). В этом случае текущая группа делится на j равных по количеству ячеек групп. Затем обработка каждой задачи происходит по сценарию пункта 2.2, при этом каждая группа обрабатывает свою вычислительную задачу.
Количество поступивших задач больше, чем ячеек в текущей группе (j \vt\). В этом случае часть задач (j — \vt\) переносится на следующий такт. Оставшиеся \vt\ задач обрабатываются по сценарию 2.3.
После того, как вычислительная задача отправлена в ячейку вычисления, это ячейка изымается из кольца и возвращается в кольцо после освобождения.
Опишем процесс функционирования алгоритма в терминах теории взаимодействующих процессов. Пусть S - процесс функционирования протокола пульсирующего кольца.
Алфавит процесса S состоит из следующих событий: діщ - і-тая группа вошла в кольцо; gout і - і-тая группа вышла из кольца; stirii - i-тый узел вошел в группу; stouti - i-тый узел вышел из группы; - tb - начало такта; - te - конец такта; - s- поступление вычислительной задачи; - щ - за время такта поступило і вычислительных задач; - ж і - маркер указывает на группу і. Процесс S состоит из следующих процессов: - Gt - процесс группы і. Входные события: БПЩ, stouti. - Р - процесс счетчика поступивших за такт задач. Входные события: tb, z, te. Выходные события: щ. -М- процесс маркера. Входные события: te. Выходные события: т{. - А о - процесс обработки ситуации, когда за такт не пришло ни одной задачи. Входные события: щ,т{. Выходные события: goutt. - А±- процесс обработки ситуации, когда за такт пришла одна задача. Входные события: щ,т - А2 - процесс обработки ситуации, когда за такт пришло задач меньше или равно количеству узлов в текущей группе. Входные события: п}, mt.
Сценарий возврата результата вычислений пользовательскому приложению
Результат структурного проектирования основан на результатах функционального проектирования и представлен в виде серии структурных диаграмм, на которых прямоугольниками обозначены структурные элементы системы, а линиями – связи между ними.
Общая структура платформы единой вычислительной среды На каждом узле вычислительной сети расположен Диспетчер, который реализует основные функции платформы, представленные в IDEF0-диаграммах (за исключением некоторых функции, которые берут на себя пользовательские приложения и вычислительные модули). Между собой диспетчеры обмениваются сообщениями по протоколу Узел – Узел (см. раздел 2.5.1). Диспетчеры связаны с модулями. Модули выполняют функцию выполнения вычисления, и обмениваются сообщениями с диспетчером своего узла по протоколу Узел – Вычислительный модуль (см. раздел 2.5.3). Пользовательские приложения связаны с диспетчером своего узла и отправляют ему запросы на выполнение вычислительных задач по протоколу Узел – Пользовательское приложение (см. раздел 2.5.2).
Таким образом, набор диспетчеров и представляет собой вычислительную среду на рисунке 2.1. К каждому диспетчеру подключены модули, диспетчер предоставляет интерфейс для запроса о выполнении вычислительной задачи пользовательским программам (рисунок 2.17).
Структура системы в концепции единой вычислительной среды Структура диспетчера, пользовательского приложения и вычислительного модуля детализирована в последующих подразделах.
В структуре диспетчера можно выделить 3 части: сетевую, внутреннюю и локальную. В сетевой части расположены структурные элементы диспетчера, связанные с взаимодействием диспетчера с локальной сетью. Часть включает в себя: 1. Сетевой обозреватель. Выполняет функцию сбора данных об активных узлах локальной сети (I3 на диаграмме А0). 2. Менеджер сообщений. Выполняет функции по обмену сообщениями с другими диспетчерами сети по протоколу Узел – Узел. Реализует функции А3, А4, А53, А55, А22, А24, А25. В локальной части расположены структурные элементы диспетчера, связанные с взаимодействием диспетчера с модулями и пользовательскими приложениями. Часть включает в себя: 1. Менеджер вычислительных запросов. Выполняет функцию по обмену сообщениями с пользовательскими приложениями по протоколу Узел – Пользовательское приложение и управление процессами принятия задачи и отправки результата. Реализует функции А11, А14. 2. Менеджер модулей. Выполняет функцию по обмену сообщениями с вычислительными модулями по протоколу Узел – Вычислительный модуль и управление ими. Реализует функцию А21.
Остальные структурные элементы диспетчера расположены во внутренней части структуры. Они не связаны с внешними по отношению к диспетчеру структурами и выполняют основные функции платформы по организации единой вычислительной среды. Во внутреннюю часть входят: 1. Список активных узлов. Содержит информацию об активных узлах сети, получая информацию от сетевого обозревателя и других диспетчеров через менеджер сообщений. Таким образом, элемент реализует функцию А522. 2. Структура выбора узла. Данный элемент организует информационную структуру выбора узла и содержит в себе алгоритмы по выбора узла для вычислений. Таким образом, элемент реализует функцию А523. 3. Определитель узла для вычислений. Управляет процессом определения узла, используя алгоритмы, заложенные в структуре выбора узла и информацию об активных узлах. Реализует функции А521, А524, А525. 4. Очередь вычислительных задач. Организует хранилище задач, поступивших от пользовательского приложения через менеджер вычислительных запросов. Реализует функцию А14. 5. Инициализатор вычислительной задачи. Управляет процессом вычисления задачи после её помещения в очередь вычислительных задач. Реализует функции А51, А53. 6. Менеджер вычислений. Управляет непосредственным актом вычисления задачи после её получения от другого диспетчера через менеджер сообщений. Реализует функцию А541. 7. Хранилище модулей. Организует расположение модулей в вычислительной среде и предоставляет эти модули для непосредственных вычислений менеджеру вычислений. Реализует функцию А23.
Определение площади фигуры методом Монте-Карло
В алгоритме случайного распределения обмен данными, связанными с принятием решения, отсутствует, поэтому объем данных равен 0. Алгоритм детерминированного распределения обладает достаточно низким объемом передаваемых данных, однако это количество резко возрастает при большой частоте поступления задач (1000-2000 мс). Среднее количество передаваемых данных и величина пика в области большой частоты поступления задач линейно возрастает при увеличении количества узлов в сети. Количество передаваемых данных в алгоритме пульсирующего кольца не зависит от времени прибытия задачи и времени её выполнения, а зависит только от количества узлов в сети. Результаты адаптивно-оптимального алгоритма выглядят похоже на результаты алгоритма детерминированного распределения: постоянное малое количество передаваемых данных во всей исследуемой области с пиком в области высокой частоты поступления задач. Однако, в отличие от алгоритма детерминированного распределения, возрастание среднего количества данных и величины пика при увеличении количества узлов происходит не так резко. Таким образом, с точки зрения объема передаваемых данных алгоритм случайного распределения превосходит остальные. Среди остальных алгоритмов наименьшим количеством передаваемых данных обладает адаптивно-оптимальный алгоритм. Так же этот алгоритм обладает наименьшим приростом в количестве передаваемых данных при увеличении узлов в сети.
Задержка задачи. На рисунке 3.18 приведены поверхности средней задержки задач при зафиксированном количестве узлов в режиме низкой нагрузки. На рисунках 3.19 и 3.20 показаны соответственно зависимости среднего и наибольшего по выборке времени задержки задач от количества узлов в сети. 4000
Алгоритм случайного распределения Алгоритм детерминированного распределения Алгоритм пульсирующего кольца Адаптивно-оптимальный алгоритм Алгоритм случайного распределения Алгоритм детерминированного распределения Алгоритм пульсирующего кольца Адаптивно-оптимальный алгоритм
Количество узлов Алгоритм случайного распределения Алгоритм детерминированного распределения Алгоритм пульсирующего кольца Адаптивно-оптимальный алгоритм Алгоритм случайного распределения Алгоритм детерминированного распределения Алгоритм пульсирующего кольца Адаптивно-оптимальный алгоритм
В алгоритме случайного распределения задержки задачи, связанные с приостановкой выполнения задачи для принятия решения по поводу другой задачи, отсутствуют, поэтому среднее время задержки равно 0. При использовании алгоритма детерминированного распределения средняя задержка задачи практически постоянна на всей исследуемой области. Это среднее время задержки задачи равно 54 мс и не зависит от количества узлов в сети. При использовании алгоритма пульсирующего кольца среднее время задержки задач линейно возрастает от 0 до максимального значения при увеличении времени выполнения задачи. Это максимальное значение, до которого возрастает величина средней задержки, увеличивается при увеличении количества узлов. Среднее время задержки при использовании адаптивно-оптимального алгоритма, аналогично алгоритму детерминированного распределения, мало и практически постоянно во всей исследуемой области. Это время равно 1 мс и не зависит от количества узлов в сети. Таким образом, с точки зрения среднего времени задержки алгоритм случайного распределения превосходит остальные. Среди остальных алгоритмов наименьшим средним временем задержки обладает адаптивно-оптимальный алгоритм.
Отношение «операции алгоритма/полезная работа». На рисунке 3.21 приведены поверхности исследуемого отношения при зафиксированном количестве узлов в режиме низкой нагрузки. На рисунках 3.22 и 3.23 показаны соответственно зависимости среднего и максимального значения исследуемого отношения от количества узлов в сети.
Алгоритм случайного распределения Алгоритм детерминированного распределения Алгоритм пульсирующего кольца Адаптивно-оптимальный алгоритм Алгоритм случайного распределения Алгоритм детерминированного распределения Алгоритм пульсирующего кольца Адаптивно-оптимальный алгоритм
В алгоритме случайного распределения работа по принятию решения отсутствует, поэтому отношение равно 0. Алгоритм детерминированного распределения имеет малое практически постоянное отношение во всей исследуемой области. Отношение практически не меняется и остается очень малым и при увеличении числа узлов в сети. Алгоритм пульсирующего кольца имеет два региона исследуемого отношения в исследуемой области. Первый регион соответствует большим значениям рассматриваемого отношения (вплоть до бесконечности), в которой узлы большую часть времени занимаются принятием решения, нежели полезной работой. Этот регион расположен в области малого времени выполнения задач (0 – N мс), N растет при увеличении числа узлов в сети. При данных условиях моделирования при количестве узлов 14 и выше узлы практически перестают выполнять полезную работу, и все время заняты принятием решения. Второй регион на всем своем протяжении имеет низкое исследуемое отношение, равное 2-3%. Адаптивно-оптимальный алгоритм имеет низкое значение исследуемого отношения во всей исследуемой области. Таким образом, с точки зрения отношения «операции алгоритм/полезная работа» алгоритм случайного распределения выглядит предпочтительнее остальных алгоритмов. Среди остальных алгоритмов низким исследуемым отношением обладают алгоритм детерминированного распределения и адаптивно оптимальный алгоритмы, которое практически не меняется при увеличении числа узлов в сети.
Суммируя результаты моделирования в режиме низкой нагрузки, можно утверждать, что алгоритм случайного распределения имеет наименьшую нагрузку на сеть и узлы, однако его применения нецелесообразно из-за большого времени принятия решения. Поэтому наиболее оптимальным для режима низкой нагрузки является адаптивно-оптимальный алгоритм, так как он имеет наименьшее время принятия решения, наименьшее время задержки задач и наименьшую нагрузку на узлы среди неслучайных алгоритмов.