Диссертация (Математическое и программное обеспечение балансировки вычислительных заданий для распределенных вычислительных комплексов на основе прогнозных моделей)

МИНОБРНАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯМосковский технологический университет____________________________________________________________На правах рукописиАлпатов Алексей НиколаевичМатематическое и программное обеспечение балансировкивычислительных заданий для распределенныхвычислительных комплексов на основе прогнозных моделейСпециальность 05.13.11 – Математическое и программное обеспечениевычислительных машин, комплексов и компьютерных сетейДИССЕРТАЦИЯна соискание ученой степеникандидата технических наукНаучный руководитель:кандидат технических наук, профессорРощин А.В.Москва – 20162ОГЛАВЛЕНИЕСПИСОК СОКРАЩЕНИЙ .....................................................................................

5ВВЕДЕНИЕ .............................................................................................................. 6Актуальность исследования ................................................................................... 6Степень разработанности ....................................................................................... 7Объект и предмет исследования ..........................................................................

10Цель работы ........................................................................................................... 10Задачи работы ........................................................................................................ 10Методология и методы исследования ................................................................. 11Научная новизна диссертационной работы........................................................ 12Теоретическая и практическая значимость работы ........................................... 12Соответствие паспорту специальности...............................................................

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

17Структура работы .................................................................................................. 19Глава 1. ИССЛЕДОВАНИЕ ЗАДАЧИ БАЛАНСИРОВКИВЫЧИСЛИТЕЛЬНОЙ НАГРУЗКИ В ГЛОБАЛЬНО РАСПРЕДЕЛЁННЫХВЫЧИСЛИТЕЛЬНЫХ КОМПЛЕКСАХ ............................................................ 201.1. Исследование особенностей и задач реализации современныхраспределённых комплексов ................................................................................

201.1.1. Распределённые вычислительные комплексы и их классификация .. 211.1.2. Особенности архитектуры современных РВК ..................................... 231.1.3. Концепция GRID Computing .................................................................. 271.1.4. Задача балансировки вычислительной нагрузки в РВК .................... 301.2. Анализ существующих подходов к решению задачи балансировкинагрузки для распределённых комплексов......................................................... 321.3.

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

401.5. Прогностический подход к балансировке нагрузки в распределённыхвычислительных комплексах ............................................................................... 45Выводы по 1 главе ................................................................................................. 47Глава 2. РАЗРАБОТКА МЕТОДА БАЛАНСИРОВКИ ВЫЧИСЛИТЕЛЬНОЙНАГРУЗКИ НА ОСНОВЕ ПРОГНОЗНЫХ МОДЕЛЕЙ...................................

492.1. Постановка задачи балансировки узловой нагрузки .................................. 502.2. Применение метода квазилинеаризации для оценки загрузки узла ......... 522.3. Нахождение прогнозных оценок загрузки узла РВК ................................. 54Выводы по 2 главе ................................................................................................. 57Глава 3. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ МЕТОДАБАЛАНСИРОВКИ НАГРУЗКИ ДЛЯ РАСПРЕДЕЛЁННЫХВЫЧИСЛИТЕЛЬНЫХ КОМПЛЕКСОВ.............................................................

583.1. Анализ влияния параметров модели на производительностьраспределённого вычислительного комплекса .................................................. 593.2. Разработка имитационной модели исследуемого комплекса .................... 613.3. Анализ полученных результатов ..................................................................

683.3.1. Расчёт индекса безразмерной ошибки прогнозирования и анализпроизводительности работы разработанного алгоритма .............................. 683.3.2. Анализ влияния структуры файловой системы .................................. 743.3.3. Анализ влияния протокола передачи данных ...................................... 75Выводы по 3 главе .................................................................................................

78Глава 4. МЕТОДЫ РЕАЛИЗАЦИИ ПРОГРАММНЫХ СРЕДСТВБАЛАНСИРОВКИ ВЫЧИСЛИТЕЛЬНОЙ НАГРУЗКИ ДЛЯРАСПРЕДЕЛЁННЫХ ВЫЧИСЛИТЕЛЬНЫХ КОМПЛЕКСОВ ..................... 794.1. Концепция разработки сложных программных систем ............................. 794.2. Обоснование выбора программно-аппаратных средств реализацииразрабатываемой программной системы ............................................................ 844.3.

Организация программной системы балансировки вычислительнойнагрузки в РВК ...................................................................................................... 92Выводы по 4 главе ................................................................................................. 98ЗАКЛЮЧЕНИЕ ..................................................................................................... 994СПИСОК ЛИТЕРАТУРЫ...................................................................................

102ПРИЛОЖЕНИЕ 1 Копия свидетельства о государственной регистрациипрограммного обеспечения для ЭВМ ............................................................... 114ПРИЛОЖЕНИЕ 2 Копии актов внедрения внедрении результатовдиссертационной работы .................................................................................... 115ПРИЛОЖЕНИЕ 3 Фрагменты исходного кода приложения .......................... 1185СПИСОК СОКРАЩЕНИЙБД – база данныхООСУБД – объектно-ориентированные системы управления базами данныхРВК – распределённый вычислительный комплексСМО – системы массового обслуживанияСУБД – система управления базами данных2-SP – 2 Dimensional Strip Packing2-BP – 2 Dimensional Bin PackingIDE – Integrated development environmentISDN – Integrated Services Digital NetworkJDK – Java Development KitJPF – Java Plug-in FrameworkJVM – Java Virtual MachineMDA – Model Driven ArchitectureNDEI – non-dimensional error indexNGN – Next Generation NetworksORM – Object-Relational MappingP2P – peer-to-peerRMSE – Root Mean Squared ErrorUML – Unified Modeling LanguageWLCA – Weighed Least Connection AlgorithmX86 – архитектура процессоров компании INTELXP – extreme programming6ВВЕДЕНИЕАктуальность исследованияСпрос на высокопроизводительные вычислительные системы растёт скаждым годом.

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

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

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

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

Она определяется также соответствием темы работы тематикеосновных направлений фундаментальных исследований, определённыхРоссийской академией наук на период до 2025, в области теоретических иприкладных проблем создания научной распределённой информационновычислительной грид- среды [1].Степень разработанностиСтремительное развитие информационных технологий в областисоздания архитектур и программных средств реализации гетерогенныхраспределённых вычислительных комплексов, привело кросту числанаучных публикаций в данной области.