автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Программно-алгоритмический комплекс организации распределенных вычислений с учетом долгосрочного прогноза загрузки сетевых ЭВМ

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

Смирнов Александр Владимирович

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

ЗАГРУЗКИ СЕТЕВЫХ ЭВМ

Специальность 05.13.18 - «Математическое моделирование, численные методы и

комплексы программ»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 в >да да

Санкт-Петербург 2009

003472819

Работа выполнена в государственном образовательном учреждении высш профессионального образования «Санкт-Петербургский государственный технологическ институт (технический университет)»

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

Доктор технических наук, доцент Халимон Виктория Ивановна

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

Доктор технических наук, профессор Константинов Игорь Сергеевич Кандидат технических наук, доцент Смирнова Наталья Николаевна

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

ЗАО «Институт телекоммуникаций», г. Санкт-Петербург

Защита состоится «30» июня 2009 г. в 14-00 часов на заседании совета по защ докторских и кандидатских диссертаций Д212.230.03 при государственном образовательн учреждении высшего профессионального образования «Санкт-Петербургск государственный технологический институт (технический университет)».

С диссертацией можно ознакомиться в фундаментальной библиотеке института.

Отзывы на автореферат в одном экземпляре, заверенный печатью, просим отправлять адресу: 190013. Санкт-Петербург, Московский пр. Д.26, Санкт-Петербургск государственный технологический институт (технический университет), Ученый совет; т 494-93-75, факс 712-77-91. Email: dissovet@Iti-gti.ru.

Автореферат разослан «29» мая 2009 г.

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

Г

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность работы. В настоящий момент наблюдается несоответствие темпов роста ычислительной мощности ЭВМ с одной стороны, и распространенности вычислительных етей и их пропускной способности - с другой. Исследователи указывают на постепенное амедление скорости роста тактовых частот ЦП, и при этом резкое ускорение темпов роста ропускной способности и снижения стоимости эксплуатации коммуникационных сетей. Это вляется предпосылкой к развитию программно-алгоритмических комплексов организации аспределенных вычислений (РВ), ориентированных на отдельных независимых сследователей и организации, на базе доступных корпоративных и домашних сетей ЭВМ. ети ЭВМ, на которые ориентирована данная диссертационная работа, обладают рядом собенностей, отличающих их от глобальных научных и специализированных ычислительных сетей и кластеров. Перечислим ключевые отличия: корпоративные и домашние вычислительные сети (далее корпоративные сети) состоят из сравнительно небольшого числа ЭВМ (чаще всего нескольких десятков, редко до нескольких сотен), объединенных в локальные сети. Отдельные локальные сети могут быть удаленны друг от друга территориально и связанны через internet-cpefly. компьютеры, входящие в такие сети, могут существенно отличаться своими аппаратными характеристиками, физической доступностью, видом и надежностью сетевого подключения и режимом использования. Важно отметить, что компьютеры являются неотчуждаемыми, т.е. они не передаются для решения вычислительных задач полностью, и на них могут выполняться задачи пользователей, имеющие более высокий приоритет; наиболее распространенной операционной системой (ОС) в корпоративных сетях является Microsoft Windows.

Организация распределенных вычислений в данном случае имеет ряд важных собенностей:

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

Объект исследований. Объектом исследований являются корпоративные сети ЭВМ, рименяемые для организации распределенных вычислений.

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

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

проанализировать особенности организации распределенных вычислений в таких сетях;

• синтезировать специализированные алгоритмы организации распределенных вычислений;

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

• спроектировать и реализовать исследовательский прототип программно-алгоритмического комплекса организации распределенных вычислений, основанный на разработанных алгоритмах;

• оценить эффективность синтезированных алгоритмов с помощью программной реализации

имитационной модели;

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

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

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

Научная новизна заключается в том, что получены новые научные результаты:

• разработан алгоритм построения долгосрочного прогноза загрузки ЭВМ задачам пользователя, основанный на выявлении типовых паттернов использования ЭВ пользователем и определении закономерности чередования выявленных паттернов;

• разработан метод оценки времени решения подзадач на ЭВМ и прогнозирован вероятности наступления сбоя, основанный на построенном прогнозе загрузки;

• разработан алгоритм составления плана назначения подзадач на ЭВМ, учитывающи результаты прогноза загрузки ЭВМ задачами пользователя и метода оценки времен решения подзадач на ЭВМ.

Практическая значимость заключается в применении разработанных теоретически положений и алгоритмов при создании программно-алгоритмического комплекса организацн распределенных вычислений в корпоративных сетях. Создано программное обеспечение по ОС Microsoft Windows в среде Microsoft Visual Studio с использованием язы программирования С++. На данное программное обеспечение получены свидетельства о официальной регистрации программ. Данные программы могут быть использованы в любы корпоративных сетях размероностью до 100 ЭВМ. Разработанное программное обеспечени применено для решения задачи молекулярной динамики. Положения, выносимые на защиту:

• алгоритм построения долгосрочного прогноза загрузки ЭВМ задачами пользователя;

• метод оценки времени решения подзадач на ЭВМ и вероятности возникновения сбо основанный на построенном прогнозе загрузки;

• алгоритм составления плана назначения подзадач на ЭВМ.

Апробадия работы. Результаты работы были представлены на III Международно научно-технической конференции «Информационные технологии в науке, образовании производстве», Орел, 24-25 апреля 2008 и на конференции Математические методы технологии ММТТ-22, по материалам которых опубликованы тезисы докладов.

Публикации. По материалам диссертации опубликовано 3 печатные рабо размещенные в журналах, рсцснзирусмыл БАК, пилучени два снидсаслылва и решиiради программ.

Структура и объем диссертации. Диссертационная работа содержит введение, 4 главь заключение и список литературы из 76 источников.

СОДЕРЖАНИЕ РАБОТЫ Бо введении обиснивана актуальность работы, сформулированы ее цель и задач исследования, указаны основные положения, выносимые на защиту.

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

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

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

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

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

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

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

ЭВМ, входящие в комплекс, играют определенные роли, в зависимости от набора модулей комплекса, выполняемых в данный момент на них:

• Вычислительный элемент (ВЭ) - ЭВМ, на которой может быть выполнено решение вычислительной подзадачи.

• Координатор - ЭВМ, осуществляющая регистрацию доступных вычислительных элементов и выделение их на решение задач.

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

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

задачи

Координатор

17

Регистрация и учет

Подзадачи

1Г

О

ВЭ ВЭ ВЭ

1 1 1

Результаты вычислений

Частные результаты

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

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

Модуль сбора статистики Анализатор —► Фильтры База данных

состояния ВЭ

Модуль прогнозирования

Прогнозирование загрузки + —

Прогнозирование сбоев

Оценка времени выполнения подзадачи

ИХ

Модуль обслуживания вычислений

Сетевые —► Модуль расчета —*> Модуль индикации

интерфейсы 4— и интерфейс

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

Запуск-останов Настройки

Выбор модуля задачи Вывод списка станций и справки Выход

Сопйо*

51»! | Ясс |

: I. -а:: • г:»-.': к*:-**:-; гз:;:^ - 6!ЗГ|5Г£ Г. 81131:к

ИИсг !$:.1сЧ

сг-р^с:«:

I $1,!;(Vip.it

"ль*? !С 1?: '•:

э

г т- ч:

"14>. т^-г; Г.- V1 *л<1 г' »'■

!.«*• в; г и;

Р.ерсч ?е^ргосие5з:

Журнал событий Индикация прогресса решения

Рисунок 3 - Окно программы-диспетчера

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

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

Протокол взаимодействия основных компонентов представлен на рисунке 4:

Программа-координатор

Программа-диспетчер

~г

Поограмма-агент

Регистрация

Регистрация сессии

Запрос на выделение ВЭ

Список выделенных ВЭ

Запрос на оценку времени расчета

Оценка

Планирование вычислений

Подзадача

Результат

Окончание сессии

Освобождение

Регистрация

"Л

г

Итеративный процесс решения задачи

Рисунок 4 - Протокол взаимодействия компонентов комплекса

Разработанный программно-алгоритмический комплекс имеет ряд преимуществ: комплекс спроектирован и реализован на основе принципов объектно-ориентированного программирования, что повышает удобство его применения и облегчает дальнейшее развитие. В качестве языка разработки выступает С++;

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

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

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

Задачи

Приближенное ^ планирование

Методы

Эвристическое планирование

Перечислительные

Теории графов

Математического программирования

Теории очередей

Рисунок 5 - Классификация задач планирования распределенных вычислений Последовательность этапов алгоритма планирования распределенных вычислений в самом общем виде представлена на рисунке 6._

Сбор данных о системе

Оценка состояния системы

Прогнозирование состояния системы

Прогноз загрузки

Прогноз времени решения

Прогноз сбоев

Планирование вычислений (составление плана назначений)

Рисунок 6 - Этапы алгоритма планирования распределенных вычислений Дл" каждой поступающее с сястсму подзидичи ^КаоЫоа^Сл вычислительная ресурсоемкость С. Эта оценка вычисляется предварительно разработчиком на основе серии тестовых запусков подзадачи на компьютере с известным индексом производительности:

Т

С=т 0)

' I

, где С - ресурсоемкость, Т - время расчета данной подзадачи, Т, - время выполнения набора тестовых заданий на данной машине. Вычислительная ресурсоемкость задачи показывает, во сколько раз больше времени необходимо для решения данной подзадачи по сравнению со временем решения набора тестовых заданий при условии одинаковой и неизменной загрузки задачами пользователя ЭВМ. Временной интервал решения подзадачи обозначим, как [11,12], где ^ - момент запуска процесса решения, а хг - момент окончания

расчетов.

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

ппи гтгтрприми пагиртпп ">2П\'СКа£ТСЯ "^^КОТККО П23 МГЦ 11Я,-!.П.ЛМ!ПЙ

- -----..г .. "Г ................... ........... . . . .ш^пи-шли ни

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

, где Тг - время выполнения теста на эталонной ЭВМ (в секундах). Фактически, индекс I показывает, во сколько раз данная ЭВМ быстрее эталонной.

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

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

Прогнозирование состояния системы включает в себя три взаимосвязанные задачи.

Задача 1: прогнозирование загрузки ВЭ\ Необходимо спрогнозировать загрузку ВЭ задачами пользователя на заданном интервале времени т.е. сформировать ряд Ь,. На

основе этого прогноза можно будет в дальнейшем рассчитать предполагаемое время решения подзадачи на заданном интервале.

Задача 2: прогнозирование надежности ВЭ: Необходимо оценить вероятность сбоя ВЭ Е на интервале времени />;,

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

Алгоритм решения задачи прогнозирования загрузки ЭВМ задачами пользователя состоит из двух этапов - предварительной обработки и подготовки необходимых данных, и, собственно, построения прогноза. В результате первого этапа на основе информации об истории загрузки ВЭ формируются паттерны загрузки и таблицы вероятностей перехода. На втором этапе на основе этой информации определяется текущее состояние ВЭ и формируется требуемый прогноз. Результаты расчетов первого этапа сохраняются. Их обновление производится через некоторые интервалы времени или в случае, когда начинает наблюдаться ухудшение качества прогноза. Для этого предусмотрена возможность получения апостериорной оценки качества прогноза в результате сравнения построенного прогноза с реальными данными по прошествии временного периода, на который осуществлялось прогнозирование. В основе алгоритма лежит обнаруженное в ходе исследования наличие явно выраженных суточных циклов изменения загрузки ВЭ. При этом можно выделить несколько типовых циклов (паттернов загрузки), и рассматривать непрерывный временной ряд значений загрузки ЭВМ как последовательность этих паттернов. Другим базовым фактом, лежащим в основе алгоритма, является наличие статистических закономерностей в цепочке паттернов. Цикличность может быть вызвана различными причинами, однако в изученных случаях она привязана к 24-часовым периодам. Например, для ЭВМ, применяемой в домашних условиях, можно выделить несколько паттернов загрузки, условно соответствующих дням недели: будний день, пятница, суббота, воскресение. Будние дни характеризуются практически полным отсутствием загрузки в дневное время и сравнительно невысокой загрузкой в вечернее время. Пятница отличается высокой степенью загрузки, начиная с раннего вечера, и до ночи субботы. Выходные дни характеризуются средней загрузкой днем и высокой - вечером. Структура алгоритма приведена на рисунке 7 в виде блок-схемы.

Определение начального сдвига

Разбиение рядов

Вычисление корреляции

Этап 1

Кластеризация

Формирование патгеонов

Именование паттернов

Кластеризация

Кодирование начальных данных

1 г

Генерация таблицы переходов

Определение состояния системы

г

Построение прогноза

Декодирование прогноза

Вычисление оценки

Л

V Этап 2

J

^ Конец ^

Рисунок 7 - Блок-схема алгоритма построения прогноза загрузки ВЭ задачами пользователя

Рассмотрим этапы алгоритма и их реализацию подробнее.

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

...______________________ЙГ--------------------------

uvujim-itim -irivjiv иилпшл vj 1ил о DDivyannuM дпсшозипс лак и.

Фильтрация данных производится с помощью комбинированного фильтра, состоящего из фильтра скользящего среднего с окном усреднения, равным 3 минутам (180 измерений), и фильтра экспоненциального сглаживания с коэффициентом сглаживания у = 0,96.

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

А*м ->min,

(3)

где к соответствует количеству измерений за 24 часа, а с1 - индекс периода, с!е[1;1)]. Иными словами, мы стремимся подобрать точку разбиения так, чтобы она попадала на

оменты продолжительного отсутствия загрузки.

После получения Б производится разбиение исходных данных на О отдельных суточных еменных рядов На рисунке 8 показан пример найденного наилучшего разбиения сходного ряда. Сплошные вертикальные линии отмечают переход локального реального емени через полночь, а пунктир - наилучшее разбиение.

Рисунок 8 - Пример разбиения исходного временного ряда на 24-ти часовые периоды На следующем этапе вычисляют корреляцию всех полученных рядов между собой, юго говоря, вычисляют не корреляцию, как таковую, а некоторую функцию расстояния между рядами. Всего таких расстояний будет 0(0-1)/2. Расстояние между парой рядов ^ вычисляется по формуле:

га» О

(4)

После этого осуществляют кластеризацию, т. е. разбиение исходного множества еменных рядов на несколько непересекающихся множеств, объединяющих схожие еменные ряды. Обозначим количество выделенных кластеров, как И, s¡ - мощность 1-го астера, а множество входящих в него рядов как Р!, где ¡е[ 1;Ы].

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

м

(5)

,где - элемент, соответствующий времени I .¡-го ряда, входящей в кластер с,. На сунках 9 и 10 приведены примеры выявленных паттернов для двух ЭВМ, отличающихся рактером использования.

I. часы 24 " I. часы " I- йен 0 [.часы : 1

Рисунок 9 - Выявленные паттерны загрузки домашнего компьютера

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

L'd=i:RdeP(c,) (

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

Например, для офисного компьютера, имеющего 2 типовых паттерна загрузки, таблш вероятностей перехода порядка 3 может иметь следующий вид (таблица 1): Таблица 1 - Вероятности перехода для офисной ЭВМ

s[ s2 s| s| si 0.00 1.00

S|S|S2 0.00 1.00

Si s2 S| 0.50 0.50 P= s,s2s2 0.00 1.00 s2s,s, 0.67 0.33 s2s, S2 0.00 1.00 s2s2s, 0.75 0.25 s2s2s2 0.40 0.60

Здесь s, соответствует выходному дню, a s2 - рабочему. Данная таблица получена результате анализа набора исходных данных за 8 недель. Можно заметить, что, наприме система, находящаяся в состоянии, описываемом последовательностью периодо соответствующих двум выходным дням и следующего за ним рабочего (S| S| S2), однознач! перейдет в состояние, отвечающего рабочему дню S|.

Построение прогноза осуществляют следующим образом:

• выбирают участок ряда, включающий в себя m полных суток, где m - порядок це Маркова, и интервал с окончания последнего суточного периода до текущего момента;

- последовательность из целых сушчныл временных рядов кодируют путем поиска наибол близкого паттерна для каждого периода;

• для текущего суточного периода составляют прогноз на основе цепей Маркова вычисляют значение функции расстояния между текущим периодом и спрогнозированны шаблоном;

• для текущего периода находят наиболее близкий паттерн, и вычисляют значение ф'ункци расстояния;

• из двух полученных таким образом символов выбирают тот, отклонение от которо наименьшее, и подставляют в цепочку;

• цепочку дополняют заданным числом периодов;

• сгенерированную последовательность символов декодируют с помощью паттернов.

Задача прогнозирования времени решения Т. На основе предполагаемо

есурсоемкости подзадачи С, прогноза загрузки Ц1) и индекса производительности ВЭ I тановится возможным оценить время решения подзадачи [I|, I}] на данном ВЭ:

и

1-]{\-ит=с (7)

/1

Определение 12 осуществляется итеративно с помощью численного интегрирования с агом, равным интервалу фиксации статистики, пока значение интеграла не превысит есурсоемкость подзадачи. Для отображения момента времени I на реальное время необходимо известному начальному моменту времени запуска решения на ЭВМ прибавить Тг (1- 1|) /1 кунд.

Задача прогнозирования надежности ВЭ решена путем хранения дополнительных анных для каждого выявленного паттерна загрузки. Для каждого участка паттерна хранятся анные о том, в какой доле исходных суточных рядов, из которых сформирован паттерн, в этот омент наблюдался продолжительный сбой. Это дает возможность определить вероятность аступления продолжительного сбоя на заданном участке как максимальное значение казанного числа на интервале 12]. Например, если для некоторого компьютера был ормирован паттерн из четырех суточных временных рядов, в трех из которых в ночное емя компьютер был отключен, то вероятност ь сбоя в ночное время будет составлять 75%. На исунке 11 показан пример суточного ряда, в течение которого наблюдался продолжительный ой (с 9 до 19 часов).

Ж

"о <1 14

I. Ч;!С[.|

Рисунок 11 - Пример суточного ряда, в течение которого наблюдался сбой. Если этот суточный ряд окажется характерным для данной ЭВМ (периодически будет озникать схожая суточная история загрузки), то на основе этих рядов будет сформирован аттерн, для которого вероятность возникновения продолжительного сбоя на интервале с 9 до 9 часов будет составлять 100%.

Алгоритм составления плана назначений подзадач на ВЭ состоит из двух ветвей, ыбираемых в зависимости от текущего состояния системы (рисунок 12). Если в системе есть более одного ВЭ и более одной подзадачи: если количество подзадач в пуле больше, чем количество доступных ВЭ, отбирается 1шличс1лви задач, равное числу ВЭ, в первую очередь - наиболее ресурсоемкие, формируется набор значений вычислительной ресурссемкости подзадач; задается порог надежности (требуемая минимальная вероятность того, что во время вычислений не наступит сбой);

полученный набор отсылается на каждый из доступных в данный момент ВЭ, не занятых вычислениями;

каждый ВЭ формирует ответный набор оценок времени решения;

на основе этих перебираются все варианты назначения подзадач на ВЭ и оценивается время вычислений по каждому полученному плану;

выбирается план назначений подзадач, для которого суммарное время выполнения расчетов минимально;

подзадачи рассылаются на ВЭ в соответствии с составленным планом.

При освобождении одного ВЭ и наличии в пуле нескольких подзадач, ожидающн решения:

• формируется набор значений вычислительной ресурсоемкости имеющихся подзадач;

• задается порог надежности (требуемая минимальная вероятность того, что во врем вычислений не наступит сбой);

• полученный набор отсыпается на ВЭ;

• ВЭ формирует ответный набор оценок времени решения;

• элементу назначается подзадача со временем решения, наиболее близким к среднему рамках данной задачи для этого ВЭ.

Рисунок 12 - Алгоритм составления плана назначений подзадач на ВЭ.

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

Метод получения интервала решения подзадачи [t|,t2] на конкретном вычислительно; элементе описан выше (формула 7). L(t) в нашем случае является табличной дискретно функцией, т.е. можно перейти от интеграла к сумме и рассчитать t2 из выражения:

/¿(1-L,)-'1"'1 .* = С, (8)

Lt=L(i,+'' l,-k) (9)

n

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

Формализуем задачу. Пусть на накопительный пул поступает п подзадач. Пронумеруем ix индексом /, где ¿el...n=Qj. Пускай также у нас имеется п вычислительных элементов,

бозначим множество этих элементов, как тогда задача эффективного распределения

одзадач сводится к нахождению перестановки л, такой что время расчета в каком то смысле инимально, где я:П¡->^2' Т0ГДа - индекс ВЭ, которому назначена ¡-ая подзадача. Всего

аких перестановок п\. Очевидно, что время в данном случае - случайная величина, зависящая т различных факторов, таких, как загрузка компьютера задачами пользователя, надежность и бои, и работать с ним, как с обычным скаляром, нельзя. Поэтому необходимо шнимизировать математические ожидания. Поясним это. Пускай время расчета / задачи, при 1ерестановке л, есть tn(i). Таким образом, задача сводится к отысканию такой перестановки к, ри которой:

Mmaxt„(i) min ПО)

:е£1| '

Нам понадобится следующая лемма.

Лемма 1. Пускай есть функция f.R*R^>R, такая чтоДй, •) иД-,А) возрастающие функции, i.e. / - возрастающая функция двух аргументов. Предположим что еще имеется два ряда фонумерованных в порядке возрастания: а\<а2<...а \<ап и b\<b2<-<bn_\<bn. Пускай 7t 1ерестановка как было определенно выше. Положим /т = шах Да,,^,,,), тогда

min/, =/,.,Где я-*:/-»и-/+1 (П)

л

Доказательство. Пусть - как определено выше, тогда В s£[l+n], такой что

/„. =/(a,.,6„_lt|). Возьмем произвольную перестановку я. Рассмотрим те пары (i,n(0) Для оторых верно ¿>s. Ясно, что таких пар и-s+l штук. Л значит, среди таких пар найдется такая, то л(;')>и-5+1. Зафиксируем это /. Легко видеть что /(a^b,,,^)^ f(a,,bnM). Таким

бразом получаем что /т, = /(о,,6„_>+1) < /(в,,&,„,) < . Лемма доказана.

Теперь приступим к решению самой задачи. Обозначим за Lft) процесс загрузки /

ычислительного элемента. Рассмотрим сначала простой случай, когда все процессы загрузки стационарные процессы (процессы с независимыми приращениями, такие, что для любого омента t верно 0)). Нам понадобится следующая формула:

/ Гп - ¡.(tWdt = С. (!2) л -

В этой формуле Т - время расчета задачи, T=t2-ti. Выразим Т:

T = mm{g-.l)(\-L(t))dt>C} (13)

о

Используя приближенную формулу для подсчета интеграла с числом разбиений к, получаем:

^к к %

к м

Оирптдпро что Т\С) ^ есть процесс восстановления. Пусть математическое ожилан.

М1(1-Ц())=а. Тогда можно применить теорему восстановления:

кС

МТ{С)к -» — (1

а

Производя предельный переход, получаем:

МТ=С/а (1

Пускай т=Ма и задачи пронумерованы в порядке возрастания индек производительности: С^<С2< - Сп_^<Сп, а вычислительные элементы в порядке возрастай

параметра т:т\<т2<—тп_\<тп. Ясно, что функция МТесть возрастающая от параметров т С. Тогда, согласно лемме 1, решением задачи организации эффективных распределеннь вычислений в этом частном случае будет перестановка л*.

Теперь рассмотрим более общий случай, когда процессы загрузки ¿({/) - произвольнь

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

расчета задачи на_/' вычислительном элементе, тогда есть время вычисления / задачи п

перестановке л. Как и в первом случае, нам понадобиться вспомогательная лемма.

Лемма 2. Пускай есть функция>/?, такая, что/а,-) и/(■,&) возрастающие функци Предположим, что еще имеется два ряда: й1<а2<---'3я-|<ал и бр^,...,^,,^. Пусть и

перестановка, как было определенно выше. Положим /, = тах/(я1,6„1)), тогда

тт/х =/т_, где ;г*:/-*л-/ + 1 (1

я*:\-+ агёшах,.еП| {&,};2 -> argmax¡ш¡u.ií){bl};...■,j а^тах,^,.^,„{6,} (1

Доказательство. Рассуждения такие же, как и в первой лемме: покажем ч V Ясно, что 3 5, такой что /т =шах/(а,,й,(„). Действуя аналогично доказательст

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

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

Теперь рассмотрим вариант, когда п>ш. Но тогда мы можем к ВЭ добавить п-гп элемент с вероятностью сбоя, равной 1 на каждом не нулевом интервале. Ясно, что от прибавлещ таких элементов система не меняется, а задача опять сводится к предыдущей.

16

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

• вариации индекса производительности отдельных элементов; ® наличие случайных отказов при проведении вычислений;

• различная вычислительная ресурсоемкость передаваемых на обработку подзадач;

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

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

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

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

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

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

Каждый шаг моделирования состоит из в 3 этапов: расчёт действующих сил, расчет еремещений, расчет температуры.

Расчёт действующих сил осуществляется по следующим формулам:

=Р1(Г),где1 = \,2,..,п (20)

£ - суммарная сила, действующая на ьый атом со стороны остальных частиц:

дЩГ)

Ъ(Г) = - в (21)

дг,

Температура определяется как средняя кинетическая энергия, приходящаяся на одну тепень свободы системы:

-г., ч

'^^„.¿^ >гое*1 = <22> .ЗЛУ* , = | Ш

Ван-дер-ваальсовые взаимодействия между атомами:

"v

а _ в

12 6

Сила электростатических взаимодействий определяются законом Кулона:

Расчет перемещений. Производится численное интефирование системы с заданны шагом времени. В качестве метода интегрирования применяется метод leap-frog:

Д/ч

v(t -

1 = v" ■

' 2 ' 4 2' т r(l + At) = r(t) + v(l + t

it K'*

(2

(2

Расчет изменения температуры. Отклонения температуры Т от её равновесного значен То корректируются согласно уравнению Ландау-Теллера:

Щ0 = тв-т«у

Ш т

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

г

1 +

м

(2

где X - коэффициент пересчёта скоростей, Т| - постоянная времени порядка 1 пс.

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

Блок-схема алгоритма представлена на рисунке 13. В данном случае пространст разбито на 27 ячеек. В среднем в каждой из них в начальный момент времени содержит около 12 тысяч частиц. Для уменьшения объема передаваемых данных отдельные небольш подзадачи вычисления Ван-дер-ваальсовых и электростатических потенциалов объединяются группы по числу доступных ВЭ. Соотношение размеров групп определяется соотношениям ожидаемых индексов производительности ВЭ, построенных на основе прогнозов загрузки В задачами пользователя на следующем временном интервале, равном времени выполнен предыдущей итерации.

Итерация Реальное время, мин Результаты моделирования, мин

С прогнозом Случайный Без прогноза

1 81 80 205 99

2 80 79 216 95

3 90 89 207 107

4 95 90 213 95

5 96 95 190 98

6 94 79 194 92

7 105 104 203 99

Я 99 93 190 99

9 88 85 205 88

10 86 80 204 89

11 85 83 227 87

Суммарное время, мин 999 953 2254 1048

Как видно из таблицы 2. предложенный метод дает наилучший результат и обеспечива выигрыш на 9.1% по сравнению с алгоритмом формирования плана назначений б прогнозирования. Приведены данные только по стадии расчета электростатически потенциалов, так как другие стадии занимают 4-5 минут (стадия расчета Ван-дер-ваальсовы потенциалов) и менее минуты для стадий расчета перемещений и температур. Алгорит случайного назначения дал наихудшие результаты, так как у ЭВМ сети в данном случае инде

производительности имеет широкий разброс значений. Имитационная модель обеспечивает качественное и, в достаточной мере, количественное соответствие реальной системе.

Рисунок 13 - Блок-схема распределенного алгоритма метода молекулярной динамики Вычислительная сеть, применяемая для расчета, состояла из 5 элементов с индексами роизводительности 3.25, 2.343, 1.818, 2.024 и 0.946.

ВЫВОДЫ

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

19

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

2. Разработаны алгоритмы и методы управления распределенными вычислениями в корпоративных сетях:

• алгоритм построения долгосрочного прогноза загрузки ЭВМ задачами пользователя, основанный на выявлении типовых паттернов использования ЭВМ и закономерности их чередования;

• метод вычисления оценки времени решения фрагмента вычислительной задачи и вероятности наступления сбоя на конкретной ЭВМ;

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

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

3. Разработан исследовательский прототип программно-алгоритмического комплекса организации распределенных вычислений "Network Calculation Library", в котором применены предложенные алгоритмы. Комплекс позволяет осуществлять распределенные вычисления в корпоративных сетях ЭВМ, функционирующих под управлением ОС Microsoft Windows. Комплекс включает три программы: программу-агент, программу-координатор и программу-диспетчер. Также в комплекс входит исходный код модуля, представляющего вычислительную задачу, что позволяет быстро и эффективно реализовывать модули решения различных прикладных вычислительных задач.

4. Комплекс применен для распределенного решения практической задачи молекулярной динамики.

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

1. Халимон, В.И. Механизм децентрализованного распределения задач между вычислительными элементами. / В.И. Халимон, A.B. Смирнов // Известия ОрелГТУ. Серия «Фундаментальные и прикладные проблемы техники и технологии: информационные системы и технологии», 2007. - №4-2/268 (535).

2. Халимон, В.И. Прогнозирование загрузки ЭВМ, входящих в корпоративные вычислительные сети. / В.И. Халимон, A.B. Смирнов // Известия ОрелГТУ. Серия «Фундаментальные и прикладные проблемы техники и технологии: информационные системы и технологии», 2008. -№1-4/269 (544).

3. Халимон, В.И. Алгоритм долгосрочного прогноза ЭВМ задачами пользователя. / В.И. Халимон, A.B. Смирнов // Вестник компьютерных и информационных технологий. М.: Машиностроение, 2008.-№12, С. 34-38.

4. Свидетельство об официальной регистрации программы для ЭВМ №2009612133 «Network Calculation Library». / В.И. Халимон, A.B. Смирнов, О.В. Проститенко -№2009610805; заявл. 04.03.09; зарег 17.04.2009.

5. Свидетельство об официальной регистрации программы для ЭВМ №2009612134 «Graf, PctriNet, SMO. (3 Tools Solution)». / В.И. Халимон, А.Ю. Рогов, O.B. Проститенко. A.B. Смирнов -№2009610806: заявл. 04.03.09; зарег 27.04.2009.

27.05.09 г. Зак. 144-70 РТП ИК «Синтез» Московский пр., 26

Условные обозначения.

Введение.

1. Обзор методов организации распределенных вычислений.

1.1 Концепция параллелизма.

1.1.1 Классификации видов параллелизма.

1.1.2 Принцип распараллеливания процесса решения вычислительных задач

1.1.3 Обмен данными между процессами.

1.2 Классификация сред организации распределенных вычислений.

1.2.1 Локально распределенные среды. 1 б

1.2.2 Организация вычислений в распределенных средах.

1.2.3 Глобальные распределенные среды. Технология Grid.

1.3 Функция планирования и балансировка загрузки.

1.3.1 Классификация и обзор алгоритмов планирования.

1.4 Постановка задачи исследования.

2. Разработка программно-алгоритмического комплекса организации распределенных вычислений.

2.1 Общая структура комплекса.

2.2 Описание программы-координатора.

2.3 Описание программы-диспетчера.

2.4 Описание программы-агента.

2.5 Описание процесса решения задачи.

2.6 Выводы по главе 2.

3. Описание метода повышения качества алгоритма планирования вычислений.

3.1 Формализация задачи.

3.2 Сбор данных о функционировании вычислительных элементов.

3.2.1 Сбор данных.

3.2.2 Предварительная обработка и фильтрация данных.

3.3 Оценка и прогнозирование состояния системы.

3.4 Алгоритм составления плана назначения.

3.5 Оценка качества функционирования алгоритма составления плана назначений.

3.6 Выводы по главе 3.

4. Пример использования разработанного комплекса для ускорения решения практической задачи молекулярной динамики.

4.1 Описание метода молекулярной динамики.

4.2 Адаптация метода для применения на разработанном комплексе.

4.3 Выводы по главе 4.

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

В настоящий момент наблюдается несоответствие темпов роста вычислительной мощности ЭВМ с одной стороны, и распространенности вычислительных сетей и их пропускной способности - с другой. Исследователи указывают на постепенное замедление скорости роста тактовых частот ЦП, и при этом резкое ускорение темпов роста пропускной способности и снижения стоимости эксплуатации коммуникационных сетей [39].

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

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

• корпоративные и домашние вычислительные сети (далее корпоративные сети) состоят из сравнительно небольшого числа ЭВМ (чаще всего нескольких десятков, редко до нескольких сотен), объединенных в локальные сети. Отдельные локальные сети могут быть удаленны друг от друга территориально и связанны через internet-среду.

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

• наиболее распространенной операционной системой в корпоративных сетях является Microsoft Windows.

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

• необходимо учитывать характер использования ЭВМ, входящих в такие сети; можно использовать только свободное процессорное время, не мешая пользователю работать на ЭВМ;

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

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

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

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

• изучить особенности функционирования ЭВМ в целевых сетях;

• проанализировать особенности организации распределенных вычислений в таких сетях;

• синтезировать специализированные алгоритмы организации распределенных вычислений;

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

• спроектировать и реализовать исследовательский прототип программно-алгоритмического комплекса организации распределенных вычислений, основанный на разработанных алгоритмах;

• оценить эффективность синтезированных алгоритмов с помощью программной реализации имитационной модели;

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

Диссертационная работа содержит 4 главы.

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

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

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

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

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

• алгоритм построения долгосрочного прогноза загрузки ЭВМ задачами пользователя;

• метод оценки времени решения подзадач на ЭВМ и вероятности возникновения сбоя, основанный на построенном прогнозе загрузки;

• алгоритм составления плана назначения подзадач на ЭВМ.

Апробация работы и публикации

Результаты работы были представлены на III Международной научно-технической конференции «Информационные технологии в науке, образовании и производстве», Орел, 24-25 апреля 2008.

По материалам диссертации опубликовано 3 печатные работы, размещенные в журналах, рецензируемых ВАК, 1 тезис доклада, получено два патента и один акт о внедрении.

• Халимон В.И. Смирнов А.В. Механизм децентрализованного распределения задач между вычислительными элементами. // Известия ОрелГТУ. Серия «Фундаментальные и прикладные проблемы техники и технологии: информационные системы и технологии». - 2007. - №42/268 (535).

• Халимон В.И. Смирнов А.В. Прогнозирование загрузки ЭВМ, входящих в корпоративные вычислительные сети. // Известия ОрелГТУ. Серия «Фундаментальные и прикладные проблемы техники и технологии: информационные системы и технологии». - 2008. - №14/269 (544).

• Халимон В.И. Смирнов А.В. Алгоритм долгосрочного прогноза ЭВМ задачами пользователя. // Вестник компьютерных и информационных технологий №12, М.: Машиностроение, 2008, сс. 34-38.

• Халимон В.И. Смирнов А.В. Оптимизация распределенных вычислительных процессов в корпоративных сетях. // Математические методы в технике и технологиях - ММТТ-22, сб.трудов XXII между народ, науч. копф.

• Свидетельство об официальной регистрации программы для ЭВМ №2009610805 «Network Calculation Library». / Халимон В.И., Смирнов А.В., Проститенко О.В.// Федеральная служба по интеллектуальной собственности, патентам и товарным знакам: Реестр программ для ЭВМ.-04.03.09.

• Свидетельство об официальной регистрации программы для ЭВМ №2009610806 «Graf, PetriNet, SMO. (3 Tools Solution)». / Халимон В.И., Рогов А.Ю., Проститенко О.В., Смирнов А.В.// Федеральная служба по интеллектуальной собственности, патентам и товарным знакам: Реестр программ для ЭВМ. - 04.03.09.

ВЫВОДЫ ПО РАБОТЕ

По результатам выполненной работы можно сделать следующие выводы.

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

2. Разработаны алгоритмы и методы управления распределенными вычислениями в корпоративных сетях:

• алгоритм построения долгосрочного прогноза загрузки ЭВМ задачами пользователя, основанный на выявлении типовых паттернов использования ЭВМ и закономерности их чередования;

• метод вычисления оценки времени решения фрагмента вычислительной задачи и вероятности наступления сбоя на конкретной ЭВМ;

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

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

3. Разработан исследовательский прототип программно-алгоритмического комплекса организации распределенных вычислений "Network Calculation Library", в котором применены предложенные алгоритмы. Комплекс позволяет осуществлять распределенные вычисления в корпоративных сетях ЭВМ, функционирующих под управлением ОС Microsoft Windows. Комплекс включает три программы: программу-агент, программу-координатор и программу-диспетчер. Также в комплекс входит исходный код модуля, представляющего вычислительную задачу, что позволяет быстро и эффективно реализовывать модули решения различных прикладных вычислительных задач. 4. Комплекс применен для распределенного решения практической задачи молекулярной динамики.

1. Ахназарова СЛ., Кафаров В.В. Методы оптимизации эксперимента в химической технологии. Учеб. пособие для хим.-технолог, спец. вузов. — 2-е изд., перераб. и и доп. М.: Высш. шк., 1985. - 327 с.

2. Барский А. Б. Параллельные процессы в вычислительных системах. Планирование и организация. М.: Радио и связь, 1990. - 256 с.

3. Боровиков В. Statistical искусство анализа данных на компьютере. Питер, 2003 г.-688 стр.

4. Бокс Д., Ватте Д. Анализ временных рядов. Прогноз и управление. Выпуск 1, М.: Мир, 1974. 409 с.

5. Бокс Д., Ватте Д. Анализ временных рядов. Прогноз и управление. Выпуск 2, М.: Мир, 1974. 198 с.

6. Бродская Е.Н., Пиотровская Е.М. Метод молекулярной динамики в физической и коллоидной химии. СПбГУ, 1999. 27 с.

7. Бриллинджер Д. Временные ряды. Обработка данных и теория: Пер. с англ. М.:Мир, 1980.-536 с.

8. Бухарев Р.Г. Основы теории вероятностных автоматов. М.: Наука, Главная редакция физ.-мат. литературы 1985г. 288 с.

9. Вентцель А.Д. Курс теории случайных процессов. М.: Наука. Физматлит 1996.-399 с.

10. Ю.Витязев В.В. Спектрально-корреляционный анализ равномерных временных рядов. Учеб. пособие. СПб.: Изд.-во С.-Петерб. Ун-та, 2001. -48 с.

11. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2002. 608 с.

12. Воеводин Вл.В., Жуматий С.А. "Вычислительное дело и кластерные системы".-М.: Изд-во МГУ, 2007. 150 с.

13. З.Головкин Б. А, Расчет характеристик и планирование параллельных вычислительных процессов. — М.: Радио и связь, 1983. —- 272 с.

14. Кирьянов А.К., Рябов Ю.Ф. Введение в технологию Грид: Учебное пособие. Гатчина: ПИЯФ РАН, 2006. - 39 е.

15. Коваленко В.Н., Корягин Д.А. Организация ресурсов грид. Препринт ИПМ им. М.В.Келдыша РАН №63, Москва, 2004.

16. Конвей, Р.В.; Максвелл, B.JT.; Миллер, JI.B. Теория расписаний. М: Наука., 1975 г.-360 с.

17. Теория расписаний и вычислительные машины / Под ред.Э.Г.Коффмана.-М.: Наука, 1984.-335 с.

18. Крутиков В.К. Вероятностный машинный эксперимент в приборостроении. JT.: Машиностроение, Ленингр. Отд-ние, 1985. - 247 с.

19. Клейнрок Л. Вычислительные системы с очередями. Пер. с англ.- М.: Мир, 1979.-600 с.

20. Ларионов А. М., Майоров С. А., Новиков Г. И. Вычислительные комплексы, системы и сети. Л.: Энергоатомиздат, 1987 г. 288 с.

21. Лут Р. Распределенные вычисления в малом и среднем офисе Электронный ресурс. Режим доступа: http://www.dtf.ru/articles/read.php?id=46196, свободный. - Загл. с экрана.

22. Морозов, В.К.; Долганов, А.В. Основы теории информационных сетей. М.: Высшая школа, 1987 г. 271 с.

23. Советов Б.Я., Яковлев С.А. Моделирование систем. Издание 3-е, переработанное и дополненное. М.: Высш. шк., 2001. 343 с.

24. Таненбаум Э., Стеен М. Распределенные системы. Принципы и парадигмы. Питер, 2003 г. 880 с.

25. Топорков В. Модели распределенных вычислений М.: 2004 г. 320 с.

26. Тюрин Ю.Н., Макаров А.А. Анализ данных на компьютере. М.: Инфра-М, 2003.-544 с.

27. Поспелов Д.А. Вероятностные автоматы. М.: Энергия, 1970. 88 с.

28. Проценко С. П. Компьютерное моделирование молекулярных систем. Екатеринбург: УрГУ, 1995. 92 с.

29. Феррари Д. Оценка производительности вычислительных систем. М.: Мир, 1981.- 573с.

30. ЗО.Эндрюс, Г.Р. Основы многопоточного, параллельного и распределенного программирования. Издательство: Вильяме, 2003 г. 512 с.

31. Халимон В.И., Комаров П.И., Жуковец Ю.Э. Автоматизированный выбор программного фильтра. Метод. Указания / СПб.технол.ин-т. - СПб., 1999.-35с.

32. Халимон, В.И. Алгоритм долгосрочного прогноза ЭВМ задачами пользователя. / В.И. Халимон, А.В. Смирнов // Вестник компьютерных и информационных технологий №12, М.: Машиностроение, 2008, С. 34-38.

33. Халимон, В.И. Оптимизация распределенных вычислительных процессов в корпоративных сетях. / В.И. Халимон, А.В. Смирнов // Математические методы в технике и технологиях ММТТ-22.

34. Якобовский М.В. Распределенные системы и сети. Учебное пособие. М.: МГТУ "Станкин", 2000. - 118 с.

35. Berman, F., Wolski, R. Scheduling from the perspective of the application. In Proceedings of the Fifth IEEE Symposium on High Performance Distributed Computing FIPDC96, August 1996, pp. 100-111.

36. David J. Farber; K. Larson (Sept 1970). "The Architecture of a Distributed Computer System—An Informal Description". Technical Report Number 11, University of California, Irvine.

37. Grama A., Gupta A., Karypis G., Kumar V. Introduction to Parallel Computing, Second Edition., Addison Wesley, 2003. 656 pp.

38. Basney, J. Livny, M, Deploying a High Throughput Computing Cluster // High Performance Cluster Computing, Rajkumar Buyya, Editor, Vol. 1, Chapter 5, Prentice-Hall, Upper Saddle River, NJ, USA, 1999, pp. 116-134.

39. Beaumont O., Legrand A. and Robert Y. The master-slave paradigm with heterogeneous processors. In Daniel S. Katz, T. Sterling, M. Baker, L. Bergman, M. Paprzycki and Rajkumar Buyya editors, Cluster'2001, IEEE Computer Society Press, 2001, pp 419-426.

40. Bryant, M., Finkel, R. A. "A stable distributed scheduling algorithm," inProc. 2nd Int. Conf. Distrib. Comput., Apr. 1981, pp. 314-323.

41. Buyya R., Fligh Performance Cluster Computing: Architectures and Systems, Volume 1, ISBN 0-13-013784-7, Prentice Hall, NJ, USA, 1999. 855 p.

42. Casavant, T.L, and Kuhl, J.D.: A communicating finite automata approach to modeling distributed computation and its application to distributed decision making, IEEE trans. Comput., may 1990, 39 (5), pp. 628-639.

43. Casavant, T. L., Kuhl, J. G. A taxonomy of scheduling-in general-purpose distributed computing systems. IEEE Trans. Software Eng., vol. SE-14, Feb. 1988, pp. 141-154.

44. Dinda, P. A. "A Prediction-based Real-time Scheduling Advisor," presented at Proceedings of the 16th International Parallel and Distributed Processing Symposium (IPDPS 2002), 2002, pp. 10 17.

45. Dinda, P. A., O'Hallaron D. R. "An Evaluation of Linear Models for Host Load Prediction," presented at Proceedings of the 8th IEEE International Symposium on High-Performance Distributed Computing (HPDC-8), Redondo Beach, CA, 1999, pp. 87-96.

46. Dinda, P. A., O'Hallaron D. R. Host load prediction using linear models. Cluster Computing, 3(4), 2000, pp. 87 96.

47. Eager, D., Lazowska, E, and Zahorjan, K.: Adaptive load sharing in homogeneous distributed systems, IEEE trans. Software eng., may 1986, se-12, (5), pp. 662-675.

48. Efe, K. Heuristic models of task assignment scheduling in distributed systems. IEEE Computer, June 1982, pp. 50-56.

49. Hansen P. B. Model programs for computational science: a programming methodology for multicomputers //Concurrency: Practice and Experience. — 1993, —V. 5, pp. 407-423.

50. Haynos, M.: Perspectives on grid: Grid computing next-generation distributed computing, http://www.ibm.com/developerworks/grid/library/gr-heritage.

51. Jackson, D.B., Snell, Q., Clement, M.J.: Core Algorithms of the Maui Scheduler. JSSPP 2001. pp. 87-102, Cambridge, MA, USA.

52. Foster I., Kesselman C., Tuecke S. The Anatomy of the Grid: Enabling Scalable Virtual Organizations. International J. Supercomputer Applications, vol 15 n. 3, August, 2001, pp. 200-222.

53. Foster I., Kesselman C., Tuecke S., Nick J. M. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration. Morgan Kaufmann Publishers, 2002.

54. Foster I. What is the Grid? A Three Point Checklist. GRIDToday, July 20, 2002.

55. Limin Fu, Enzo Medico. FLAME, a novel fuzzy clustering method. BMC Bioinformatics, England, 2007; vol 8: pp. 3-3.

56. Mullender, s., van Rossum, g., Tannenbaum, a.s., van Renesse, г., and van Staveren, h.: 'amoeba: a distributed operating system for the 1990s', ieee. Computer, may 1990, 23, (5), pp. 44-53.

57. Patton J.J. and Brickell C. Second Evaluation of Job Queuing/Scheduling Software: Phase 1 Report. NASA Technical Report NAS-97-013 June 1997.

58. Shao G., Wolski Rn Berman F. Performance effects of scheduling strategies for master/slave distributed applications // UCSD CSE Technical Report W CS98A598. University of California, San Diego. 1998. — 13 p.

59. Stockinger H. Defining the grid: a snapshot on the current view. // The Journal of Supercomputing, Springer Netherlands ISSN 0920-8542 (Print) 1573-0484 (Online), Volume 42, Number 1 / 2007.

60. Shivaratri, N.G., Krueger, P., and Singhal, M.: Load distributing for locally distributed systems, IEEE Computer, dec. 1992, 25 (12), pp. 33-44.

61. Yang, L., Foster, I., Schopf, J.M. Homeostatic and Tendency-based CPU Load Predictions. Proc. IEEE Press, 2003, pp. 42 50.