Содержание к диссертации
Введение
Глава 1. Параллельные и распределённые вычисления 10
1.1 Закрытые распределённые вычисления 14
1.2 Кластерные распределённые вычисления 16
1.3 Сетевые распределённые вычисления
1.3.1 Основные компоненты BOINC 25
1.3.2 Механизм планирования BOINC 26
1.4 Цели и задачи исследования 30
Основные результаты и выводы к первой главе 34
Глава 2. Разработка моделей и методов планирования внутри сети добровольных вычислений 36
2.1 Стратегии планирования распределённых вычислений 36
2.2 Классификация задач и типы алгоритмов планирования 40
2.3 Общий анализ задач теории расписаний 42
2.4 Составление расписаний в условиях неопределённости
2.4.1 Постановка задачи планирования 53
2.4.2 Способы представления исходной информации 58
2.5 Генетический алгоритм для планирования вычислений 66
2.5.1 Общая схема генетических алгоритмов 68
2.5.2 Дискретная задача планирования
2.5.3 Интервальная задача планирования
2.5.4 Динамическая задача планирования
2.5.5 Планирование с дублированием
Основные результаты и выводы ко второй главе
Глава 3. Прогнозирование времени выполнения работы
3.1 Анализ способов формирования исторической базы
3.2 Нейронные сети прямого распространения
3.3 Алгоритмы обучения нейронных сетей прямого распространения по методу
3.3.1 Численные методы локальной оптимизации
3.3.2 Модификации метода Левенберга-Марквардта
3.3.3 Оптимизация вычислений по методу Левенберга-Марквардта
3.3.4 Реализация параллельных вычислений Левенберга-Марквардта
3.3.5 Регуляризация Байеса
3.3.6 Вычисление интервалов предсказания
3.3.7 Алгоритм интервального прогнозирования .
3.4 Другие способы обучения
3.4.1 Метод наискорейшего спуска
3.4.2 Метод резкого изменения направления Пауэлла вычислительных
Глава 4. Описание ПО и экспериментов 121
4.1 Программная реализация 121
4.1.1 Окружение разработчика 121
4.1.2 Архитектура управляющего сервера 122
4.1.3 Технология параллельного программирования OpenMP 127
4.1.4 Библиотека LMA-math 129
4.1.5 Библиотека LMA-learning 131
4.1.6 Библиотека LMA-predictor 131
4.1.7 Библиотека генетического алгоритма GA 134
4.2 Апробация метода Левенберга-Марквардта 134
4.2.1 Обучение простой функции 135
4.2.2 Обучение в условиях неопределённости 136
4.2.3 Обучение в условиях зашумлённости данных 137
4.2.4 Сравнение производительности при различных способах оптимизации вычислений 138
4.2.5 Вычисление интервалов предсказания 145
4.3 Эксперименты по планированию 149
4.3.1 Проверка гипотезы №3 150
4.3.2 Составление расписания 151
Основные результаты и выводы к четвёртой главе 162
Заключение 165
Список использованных источников
- Сетевые распределённые вычисления
- Составление расписаний в условиях неопределённости
- Алгоритмы обучения нейронных сетей прямого распространения по методу
- Технология параллельного программирования OpenMP
Введение к работе
Актуальность темы исследования. Параллельное и распределенное
программирование – два базовых подхода к повышению эффективности и
надежности процессов обработки и передачи информации. Для
распределенных сетей замечено, что чем слабее связь между компонентами, тем проще аккумулировать вычислительные ресурсы, но сложнее поддерживать высокий уровень эффективности их использования. Например, большое количество вычислительной техники подключено к глобальной сети Интернет, но ее ресурсы используются далеко не полностью. Задачу их аккумуляции и распределения по различным проектам решают сети добровольных вычислений (Volunteer Computing), которые относятся к распределенным вычислительным сетям. Основными платформами для организации добровольных вычислений являются BOINC, Distributed.net и др. В работах D.P. Anderson, B. Javadi, D. Kondo, D. Toth и других рассмотрены основные механизмы работы платформы BOINC, при этом предполагается, что исполнители (волонтёры) независимы и их поведение в целом характеризуется значительным уровнем неопределенности.
Сети добровольных вычислений являются открытыми и
масштабируемыми. К их характерным особенностям относятся
неопределенность в распределении оборудования для решения множества
задач, поступивших в систему в определенный момент времени;
динамический характер загрузки оборудования; различное время выполнения
задач на разных типах оборудования; неравномерность общей нагрузки.
Повышение эффективности функционирования сетей добровольных
вычислений возможно на основе совершенствования механизмов
планирования и оптимального распределения нагрузок внутри сети. Развитию методов планирования для распределенных вычислительных сетей и, в частности, для сетей добровольных вычислений посвящены работы В.В. Топоркова, В.Б. Иверсена, М.А. Посыпкина, О.С. Заикина, С.А. Лупина и других. Структурно данные задачи относятся к классу NP-полных задач дискретной оптимизации, поэтому в общем случае предполагают нахождение удовлетворительного субоптимального решения. Именно данная проблема решается в рамках проведенного исследования, что обусловливает его своевременность и актуальность.
Диссертационная работа выполнена в рамках одного из основных
научных направлений Воронежского государственного университета
«Математическое моделирование, программное и информационное
обеспечение, методы вычислительной и прикладной математики и их применение к фундаментальным исследованиям в естественных науках».
Цель и задачи исследования. Цель работы заключается в разработке моделей и алгоритмов для организации распределенных вычислений на основе комбинации эволюционного и нейросетевого методов моделирования с целью повышения эффективности решения задач с помощью массово доступных вычислительных ресурсов.
Для достижения цели решались следующие задачи:
-
Анализ существующих методов планирования для параллельных и распределённых систем, в частности, основанных на платформе BOINC.
-
Разработка нейросетевого метода прогнозирования времени выполнения программы в условиях неопределенности.
-
Разработка генетического алгоритма для нахождения субоптимального решения задачи планирования распределённых вычислений.
-
Разработка программного обеспечения для решения задачи планирования и распределения нагрузки в сети добровольных вычислений с учетом прогнозирования времени выполнения заданий и проведение вычислительных экспериментов для апробации предложенных алгоритмов.
Методы исследования основаны на теории и методах оптимизации, интервальной арифметике, теории эволюционных вычислений, теории нейронных сетей. При разработке программного комплекса использовались современные методы и технологии программирования.
Тематика работы соответствует следующим пунктам специальности 05.13.18 «Математическое моделирование, численные методы и комплексы программ»: п. 2. «Развитие качественных и приближенных аналитических методов исследования математических моделей», п. 3. «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий», п. 4. «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента».
Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:
алгоритм интервального прогнозирования времени выполнения работы (программы), основанный на нейронной сети прямого распространения, обученной методом Левенберга-Марквардта, отличительной особенностью которого является использование регуляризации Баейса, а также альтернативных критериев остановки обучения на основе следа обратной матрицы Гессе, что позволяет улучшить обобщающую способность нейронной сети;
результаты анализа подходов к сокращению времени выполнения одной итерации обучения нейронной сети методом Левенберга-Марквардта, включая распараллеливание матричных вычислений с помощью технологии параллельного программирования с общей памятью, точный аналитический расчёт и приближенное вычисление матрицы Якоби методом Бройдена, при этом показана возможность экономии памяти компьютера за счёт отказа от хранения матрицы Якоби целиком, ограничившись только её построчным расчётом;
модели планирования (статическая, динамическая, интервальная) и генетический алгоритм для нахождения субоптимального решения, особенностью которого является возможность модификации хромосомы и функции приспособленности, что позволяет обеспечить быструю адаптацию к
изменяющейся ситуации в сети добровольных вычислений и обеспечивает ее эффективное функционирование;
- программное обеспечение для планирования и распределения нагрузки в сети добровольных вычислений, включая специализированные библиотеки, в частности, библиотеку для обучения нейронных сетей прямого распространения, отличительной особенностью которой является применение современной технологий параллельного программирования OpenMP, а также активное использование векторизованных циклов (такие циклы активно используют SIMD инструкции процессора), появившихся в последних версиях стандарта.
Практическая значимость и внедрение результатов работы.
Предложенные методы планирования для сетей добровольных вычислений, учитывающие прогнозные оценки времени выполнения заданий различными типами вычислительных устройств, могут быть положены в основу систем планирования в условиях постоянного изменения состава исполнителей и работ. Предложенный комплекс алгоритмов является самоадаптирующимся за счет предусмотренной возможности корректировки параметров, а соответствующее программное обеспечение может быть использовано не только для проведения вычислительных экспериментов, но и позволяет решать практические задачи прогнозирования и планирования на качественно новом уровне.
Разработанные в рамках исследования библиотеки программ «LMA-math 1.0», «LMA-leaming 1.0», «LMA-predictor 1.0», в которых реализованы предложенные алгоритмы, внедрены в производственную деятельность ООО НТЦ «РЕЛЭКС». Результаты диссертационной работы используются в учебном процессе ФГБОУ ВО «Воронежский государственный университет» при выполнении выпускных квалификационных работ.
Апробация работы. Основные результаты диссертационного исследования докладывались и обсуждались на следующих международных и всероссийских конференциях: XLII заочная научная конференция International Research Journal (Екатеринбург, 2014), VII Международная научно-практическая конференция «Научное обозрение физико-математических и технических наук в XXI веке» (Москва, 2014), XXIII заочная научная конференции Research Journal of International Studies (Екатеринбург, 2014), интернет-конференция «Междисциплинарные исследования в области математического моделирования и информатики» (Тольятти, 2013), ежегодные научные сессии Воронежского государственного университета.
Публикации. По теме диссертации опубликовано 10 печатных работ, в том числе 2 работы в изданиях, рекомендованных ВАК РФ, и зарегистрировано 3 программы ЭВМ. В работах, выполненных в соавторстве, лично соискателю принадлежат: [1] - алгоритм интервального прогнозирования; [2] - модификация метода Левенберга-Марквартда для обучения нейронной сети прямого распространения; [6] - генетический алгоритм для решения задачи планирования для интервальных данных.
Объём и структура работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка использованных источников, включающего 95 наименований и приложения. Основная часть работы изложена на 167 страницах и содержит 26 рисунков и 14 таблиц.
Сетевые распределённые вычисления
Вычислительный кластер — это группа вычислительных узлов, объединенных высокоскоростными каналами связи, представляющая с точки зрения пользователя единую вычислительную систему [7]. Использование высокоскоростного канала связи вместе с специализированным протоколом обмена информации является ключевой особенностью кластерных распределённых вычислений.
В программном обеспечении кластера, как правило, можно выделить два компонента — менеджер ресурсов и планировщик. Менеджер отвечает за распределение вычислительных ресурсов, их аутентификацию, создание и миграцию процессов. Планировщик определяет очерёдность работ и их назначение на те или иные ресурсы.
В основе многих систем управления ресурсами лежит архитектура «клиент-сервер» [58]. Пользователь взаимодействует с системой через клиент 17 скую программу — пользовательский интерфейс. На узлах (серверах), где выполняются работы, устанавливаются исполнительные демоны, которые поддерживают обновляемые таблицы данных о том окружении, в котором функционирует система управления ресурсами. Чаще всего реализуется не интерактивный доступ к ресурсам, а режим пакетной обработки (обработке пакетного задания, batch job).
Для организации высокопроизводительного и масштабируемого соединения узлов кластера часто применяется технология InfniBand, развиваемая в последнее время компаниями Intel и Mellanox Technologies. Основными преимуществами технологии перед обычным скоростным Ethernet-соединением являются высокая пропускная способность сети (до 56Gb/s на порт по 4 линиям), низкий уровень задержек, что важно для приложений с интенсивным обменом данными, и сохранение высокой производительности сети с ростом количества узлов [14,73].
Для программирования систем с распределённой памятью существует технология MPI. С её помощью обеспечивается организация вычислений и взаимодействие процессов через обмен сообщениями. В настоящее время MPI входит в стандартный комплект программного обеспечения практически любого многопроцессорного вычислительного комплекса.
В состав среды программирования MPI входит библиотека с интерфейсом одного или нескольких языков программирования (обычно Fortran, C и C++), а также средства для запуска и сборки параллельного приложения. Интерфейс библиотеки соответствует стандарту версии 1.1, принятому в 1995 году или более позднему варианту версии 2.0, принятому в 1998 году [31].
MPI-программа — это множество параллельных взаимодействующих процессов. По стандарту MPI 1.0 все процессы порождаются один раз, образуя параллельную часть программы. Порождение и уничтожение дополнительных процессов в ходе выполнения MPI-программы появились в MPI 2.0. Так же в стандарте описан широкий набор функции передачи сообщений. Они отличаются друг от друга способами синхронизации, принципами подготовки данных к отправке.
Реализация стандарта MPI представляет собой библиотеку и программную среду. Среда обеспечивает процесс обмена сообщениями с помощью выбранной комбинации фабрик. Фабрики определяют конкретные механизмы и протоколы передачи данных. Например, Intel MPILibrary поддерживает: shm (общая память), dapl (Direct Access Transport Libraries, библотека поддерживает работу с InfniBand, iWarp, Dolphin, XPMEM), tcp, tmi, ofa. С помощью набора библиотечных функций программист формирует потоки данных между узлами.
Самыми распространёнными реализациями MPI являются: MPICH (на её базе часто основываются Open Source и коммерческие реализации); OpenMPI; Intel MPILibrary (коммерческая реализация, основанная на MPICH. Предоставляет расширенный набор протоколов передачи данных, в том числе через различные коммерческие высокопроизводительные адаптеры, поддержку клиентов, улучшенную интеграцию с технологиями компании Intel).
Одной из систем управления и распределения ресурсов вычислительного кластера используется является SLURM. SLURM — это надежный, переносимый, масштабируемый на большое количество узлов, отказоустойчивый, открытый менеджер кластеров. SLURM поддерживает очередь ожидающих заданий и управляет общей загрузкой ресурсов в процессе выполнения работы, управляет доступными вычислительными узлами в эксклюзивной или неэксклюзивной форме (как функция потребности в ресурсах), обеспечивает мониторинг параллельных заданий вплоть до их завершения и распределяет нагрузку по выделенным узлам [11]. Работа планировщика SLURM, с плагином Backfll, основана на двух принципах [2,86]: работы выстраиваются в очередь в порядке приоритета; работы с меньшим приоритетом будут запущены в том случае, если из-за них не задерживается запуск любой из более высоко приоритетных работ.
На приоритет влияют следующие факторы [2,86]: вытесняемость работы: возможность прервать выполнение одной или нескольких менее приоритетных работ с целью обеспечения непрерывного выполнения высоко приоритетной работы; расписание выполнения работ (механизм резервирования ресурсов): задаче может быть предписан интервал времени, внутри которого она имеет эксклюзивный доступ к вычислительным ресурсам. Дополнительно существуют возможность использования внешних планировщиков, например, Maui [2].
Для организации «честного» распределения ресурсов кластера между пользователями, возможна установка дополнительных ограничений на длительность выполнения работы, объёма дискового пространства, правил предварительного резервирования ресурсов (один пользователь договаривается со всеми остальными о предоставлении ему всех ресурсов кластера в эксклюзивный доступ для решения особо сложной задачи
Составление расписаний в условиях неопределённости
Обобщение конвейерных и параллельных вычислений. Вместо цепи из компьютеров, используют рабочих центров, состоящих из определённого числа идентичных, параллельно работающих компьютеров. Каждая работа имеет свой определённый путь по центрам. Внутри центра работа может быть обработана только на одном компьютере, причём каждый компьютер должен быть способен выполнить её. Если допускается выполнение работы на одном и том же центре несколько раз, то делается отметка в атрибутах. свободные вычислительные цепи, Open shop () Существует компьютеров, причём работа может быть обработана на каждом из них. Однако, на некоторых компьютерах время обработки мо жет быть равно нулю. Нет никаких ограничений на маршрут обхода ком пьютеров. Планировщик может самостоятельно определять маршрут для каждой работы. Необязательно каждая работа должна иметь одинаковый маршрут. Как уже отмечалось, значением параметра могут быть один атрибут, список из нескольких или полное их отсутствие. В теории расписания обычно рассматриваются следующие атрибуты [25,83]: время запуска, Release dates () Наличие атрибута подразумевает, что работа не будет выполняться до определённого момента . Отсутствие атрибута означает возможность старта работы в любое время. вытеснение, Preemptions (или допустимость прерывания) () Вытеснение подразумевает, что не обязательно выполнять работу с самого её старта до конца. Планировщику разрешается прервать работу в любой точке и перейти к другой. В процессе выполнения новой задачи результаты предыдущей работы не теряются. Когда возобновляется выполнение прерванной работы (возможно уже на другом компьютере), требуется только завершить её. Если атрибут отсутствует, то вытеснение не разрешено. очерёдность, Precedence constraints () Этот атрибут можно применить только для конфигураций, состоящих из одного компьютера или из параллельно работающих. Наличие атрибута подразумевает, что существуют определённые требования в порядке выполнения работ: одна или несколько работ должны быть обработаны для того, чтобы обрабатывать последующие. Существует несколько особых форм очерёдностей (рис. 2.2): если у работы есть не более одного предшественника и не более одного последователя, то очередь выстраивается в цепь (Chains); если у работы не более одного предшественника, то очередь называется входящим деревом (Intree); если у работы не более одного последователя, то очередь называется выходящим деревом (Outtree). смежные задачи, Job families () Подразумевается, что имеется работ, принадлежащих различным классам работ. Работы одного класса могут иметь различное время выполнения, но они могут работать одна за другой без каких-либо задержек, связанных с подготовкой к вычислениям. Однако, при смене класса, например, с класса на , возникают задержки, выражаемые через (или , если зависит только от инициализации одного класса). пакетная обработка, Batch processing (()) Компьютер может взять пакет, состоящий из не более, чем работ, которые будут обрабатываться одновременно. Время выполнения работ в пакете не обязательно должно быть одинаковым, и обработка пакета считается завершённой тогда, когда все работы в нём выполнены. Если = 1, то проблема сводится к обычному планированию. Задача становится гораздо интереснее, если = , т. е. в пакете может быть неограниченное число задач. доступность, Breakdowns () Допускается, что компьютер может быть недоступен, например, из-за технического обслуживания или поломок. Если рассматривается архитектура с параллельной обработкой, то можно выделить функцию () — зависимость количества работающих компьютеров от времени. ограниченные права, Machine eligibility restrictions () Этот атрибут может использоваться при параллельной обработке. Его присутствие () означает, что не все компьютеров могут взять -ю работу, а только те, которые им обозначены. размещение, Permutation () Ограничение, появляющееся при использовании конвейерных вычислительных сетей, представляет собой наличие жёстко заданной очереди («первый вошёл — первый вышел») работ. Наличие атрибута позволяет предопределить очередь обработки.
блокировки, Blocking () Это феномен, которому подвержены конвейерные вычислительные сети. Если в таких сетях ограниченный буфер между двумя компьютерами, то это может привести к тому, что переполнение буфера на следующем компьютере не позволит передать ему результаты работы предыдущего. Блокировка подразумевает, что выполненная работа остаётся на компьютере (т. е. блокируется), не допуская выполнения на нём следующей работы. Достаточно распространённым случаем считается вариант с нулевым размером буфера. В этом случае, компьютер не получит новую работу, пока не обработает текущую. без ожидания, No-wait () Пример другого феномена в конвейерных цепях. Недопустимо, чтобы работы задерживались между двумя компьютерами. Подразумевается, что работа не поступит на первый компьютер до тех пор, пока не будет уверенности в том, что она пройдёт по всей цепочке без единой задержки (с учётом подчинения правилу «первый вошёл — первый вышел»). рециркуляция, Recirculation () В предопределённых вычислительных сетях (в том числе и гибких), работе разрешено посещать один компьютер или вычислительный центр несколько раз.
В заключение необходимо рассмотреть последний компонент триады — объект минимизации — . Обычно задача теории расписаний характеризуется целевой функцией (критерием оптимальности), которую необходимо минимизировать (реже, максимизировать) на множестве допустимых расписаний. Она вычисляется на основе некоторого набора штрафов (штрафных функций), которые возникают при фиксации порядка обслуживания требований в расписании.
Алгоритмы обучения нейронных сетей прямого распространения по методу
Механизм прогнозирования времени выполнения работы является ключевым элементом в стратегии прогнозирования. В основе механизма лежит историческая база, которая используется в получении оценки. В [72] отмечается, что использование исторической базы в планировании хорошо изучено и доказана эффективность использования, однако проблема её организации пока остаётся открытой. Для каждой отдельной задачи прогнозирования подбирается конкретный, оптимальный для неё способ сбора статистических данных. В случае с добровольными вычислениями, за основу можно взять проблему составления прогноза для нового участника сети: на чём основать прогноз для участника, который ещё не принимал участия в решении задач?
После сбора данных необходимо провести их обработку и подобрать алгоритм, по которому из них выводится оценка. Например, в [87] определяется степень подобия запускаемой и ранее выполнявшихся программ по ряду параметров, которые фигурируют в соответствующей метрике «близости». В силу того, что в сети добровольных вычислений участники постоянно сменяют друг друга (или просто уходят на время), необходимо получить и обработать сведения о времени выполнения работ приложений на ограниченном парке машин таким образом, чтобы иметь возможность получить оценку для широкого множества оборудования.
Анализ способов формирования исторической базы Сформулируем и проверим гипотезу 1: использование постоянных характеристик вычислительной аппаратуры даёт однозначную прогнозируемую оценку. Для наглядности в качестве постоянной характеристики примем частоту процессора. Для этого будем ориентироваться на очевидную зависимость: чем выше частота процессора, тем меньше времени затрачивается на выполнение работы. Формально эту зависимость можно представить в виде правила: если v\ v i, то t\ 2, где ti,t2— время выполнения работы на компьютерах с частотой процессора v\ и v i соответственно.
Для проверки гипотезы был проведён вычислительный эксперимент, суть которого заключается в определении времени выполнения некоторой тестовой программы 25 участниками-компьютерами с известной частотой процессора. Тестовая программа была разработана так, чтобы влияние остальных характеристик компьютера (например, объём памяти, частота шины и прочие) оказывали минимальное влияние на её время работы. На основе полученных данных G\ = {(Vn, іп)}п=тзї составлен график (рис. 3.1(а)).
Проанализировав график на рис. 3.1 (a), отметим, что данные имеют высокую степень зашумлённости. Из этого следует, что оценка времени выполнения приложения тоже будет приближенной. Среди данных Gi, можно отметить появление нескольких компьютеров с одинаковой частотой процессора, но разным временем выполнения тестовой программы, что приводит к неопределённой ситуации, в которой данные, представленные в виде набора из точек с координатами (,), — значение некоторого параметра, — значение времени, () — вероятность выполнения события , т. е. функция зависимости времени работы приложения от одного фактора в общем случае является многозначной.
Чтобы более полно учитывать факторы, влияющие на работу программ, можно воспользоваться дополнительными тестовыми программами, собирающими информацию о производительности отдельных частей компьютера. Например, в качестве оценочных задач для набора тестов SPEC92 для оценки производительности коммерческих систем используются: задача сжатия информации, задача упрощения булевой функции, проецирование лучей через оптическую систему и прочие [69]. Таким образом, замеряется скорость работы с целыми, дробными, логическими переменными, работа с памятью и внешними запоминающими устройствами. Тестовые приложения позволяют учитывать не только аппаратную составляющую компьютера, но и программную. Время их работы и будем считать относительным параметром. Совокупность относи t 18 сек. 14 12 10 8 6 4 График зависимости времени выполнения от частоты процессора; пунктиром выделены графики функций степенной регрессии тельных параметров позволяет снизить степень неопределённости, поскольку множество не учитываемых факторов влияют на работу не только контрольной программы, но и тестовых. Это значит, что найти компьютеры с одинаковым временем выполнения тестовых программ сложнее, чем с одинаковым процессором [36-40,82].
Основываясь на вышесказанном, построим гипотезу 2: использование относительных параметров позволяет получить более точную оценку. Соответственно, ожидаемую зависимость можно сформулировать следующим образом: чем меньше время выполнения тестовых (замерочных) работ, тем меньше прогнозируемое время контрольных.
Технология параллельного программирования OpenMP
Сети добровольных вычисления являются одним из способов аккумулирования вычислительных ресурсов для решения научно-практических задач. Однако поддержание высокой эффективности их работы является сложной проблемой, поскольку она лежит за пределами возможностей классических алгоритмов управления и оптимизации. Это связано с тем, что добровольные сети подразумевают слабую связанность компонентов и отсутствие возможности управления исполнителями (волонтёрами), что порождает большое количество свободных параметров. Поэтому в рамках стратегии прогнозирования времени выполнения работ, предложен общий подход к планированию внутри сети добровольных вычислений на основе метаэвристических и интеллектуальных методов. Получены основные результаты работы: 1) На примере BOINC исследован механизм планирования в открытых динамических распределённых вычислительных системах, определены его недостатки, что позволило сформулировать цель и задачи исследования. 2) Предложен способ формирования и обработки исторической базы данных, содержащей наблюдения за процессом выполнения различных работ приложения; показана вариативность составления базы, допускающая комбинирование данных разного типа, сочетая описание не только характеристик исполнителя, но и работ. 3) Разработан нейросетевой алгоритм интервального прогнозирования, и в рамках вычислительных экспериментов продемонстрированы возможно 166 сти его и отдельных компонентов, включая различные модификации, направленные на оптимизацию вычислений с учётом обработки большого количества данных, повышения качества обучения и точности решения. Прогнозирование времени выполнения задания позволяет реализовать соответствующую стратегию планирования и, тем самым, обеспечить дифференцированный подход к оценке сложности работ, что повышает эффективность функционирования сети распределенных вычислений. 4) Предложены механизмы адаптации генетического алгоритма для решения задачи планирования вычислений с учетом различных постановок задач (динамическая, интервальная). 5) С использованием современных технологий программирования разработаны библиотеки для обработки исходных данных с помощью нейронной сети прямого распространения, входящие в состав интеллектуального планировщика для динамических вычислительных систем.
Для реализации полноценного планировщика требуются дальнейшие исследования в области добровольных вычислений в целом и дальнейшей адаптации интеллектуальных технологий в частности. Например, для модели на рис. 4.1 модуль подготовки обучающей выборки требует тщательной проработки. Он особенно важен, поскольку от него зависит качество и скорость обучения нейронных сетей: если сеть обучена плохо, то возможна перегрузка одного или нескольких волонтёров, что негативно сказывается на эффективности, однако если размер обучающей выборки будет слишком большим, то потребуется много времени на обучение. Таким образом этот механизм можно представить как фильтр для исторической базы данных, который должен основываться на следующих принципах: необходимо сохранять область определения обучающей выборки, чтобы задача интерполяции не переходила в задачу экстраполяции; данные статистики собираются в режиме реального времени и условно считаются корректными, однако возможны случайные выбросы; необходимо корректное разграничение выбросов и статистически редких, но реальных данных, которые важны для поддержания широкой области определения.
Актуальной проблемой является концентрирование массы почти одинаковых наблюдений в различных регионах области определения обучающей выборки: с одной стороны большая часть этих наблюдений не оказывают большого влияния на качество обучения и их можно отбросить, с другой — нарушается статистическая целостность данных, что оказывает влияние на интервальное прогнозирование.
Другим интересным направлением исследования является самоорганизация вычислений в сети добровольных вычислений, под которой подразумевается автоматическое выстраивание многоуровневой иерархии и передача некоторых функций планировщика от сервера проекта на нижестоящие узлы этой иерархии.
Сети добровольных вычислений опираются на рядовых пользователей Интернета. Таким образом, они не могут не затрагивать вопросы из гуманитарных сфер исследования. Необходимо исследование проблем наращивания пользовательской базы (их мотивации к участию в проекте), разработки различных способов поощрения участников, понижения порога вхождения в сети добровольных вычислений, развития интерактивных качеств проектов, а также способов применения в образовательном процессе, распространения научных знаний, актуальных исследований и их результатов.