автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Управление стратегиями распределения заданий внутри вычислительной Грид-системы

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

(рО*"'

Гаевой Сергей Владимирович

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

05.13.01 - Системный анализ, управление и обработка информации (промышленность)

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

005559294

8 2015

Волгоград-2015

005559294

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

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

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

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

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

доктор технических наук, профессор Фоменков Сергей Алексеевич,

Фиыогеев Алексей Германович

доктор технических наук, профессор, ФГБОУ ВПО «Пензенский государственный университет», г. Пенза, кафедра «Системы автоматизации проектирования», профессор;

Лобейко Владимир Иванович

доктор технических наук, профессор, ФГБОУ ВПО «Астраханский государственный университет», г. Знаменск, кафедра «Математика и информатика», заведующий.

ФГБОУ ВПО «Астраханский государственный технический университет» («АГТУ»), г. Астрахань.

Защита состоится «19» марта 2015 года в 14:00 часов на заседании диссертационного совета Д 212.028.04, созданного на базе Волгоградского государственного технического университета по адресу: 400005, г. Волгоград, пр. Ленина 28, ВолгГТУ, ауд. 209.

С диссертацией можно ознакомиться в библиотеке Волгоградского государственного технического университета и на сайте ВолгГТУ по адресу http://vww.vstu.ru/nauka/dissertatsionnye-sovety/d-21202804.html

Автореферат разослан «_» __2015 г.

Ученый секретарь /3

диссертационного совета ¿Г^Ь^лл. Водопьянов Валентин Иванович

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

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

Работы, связанные с эвристиками, моделированием и/или аппроксимацией нагрузки вычислительных систем уже проводились, в частности, Самоваровым О.И., Лукьяновым B.C., Жариковым Д.В., Грушиным Д.А., Роговым Ю.П., Аветисяном А.И., Гайсаряном С.С., Кузюрином H.H., Шокуровым A.B., Михайловым Г.М., Соболевым С.И., Шамакиной A.B., Каляевым A.B., Шелестовым А.Ю., Leland W.E., Ott T.J., Feitelson D. G., Rudolph L., Downey A.B., Jann J., Pattnaik P., Franke H., Wang F., Skovira J., Riodan J., Moreira J.E., Jette M.A., Lublin U., Tsafrir D., Etsion Y., Sulistio A., Buyya R., Murshed M., Dobre C., Stratan C., Cameron D.G., Takefiisa A., Quinson M., Legrand A., Casanova H., Ranganathan K., Foster I., Xia H., Davies A., Plaszczak P., Berman F., Li M„ Catlett C„ Smarr L., Smith R„ Taha H. и др.

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

Однако эти работы имеют ряд недостатков:

1) Модели создаются для конкретной системы, ориентируясь на частный случай.

2) Аппроксимации не учитывают цикличной нагрузки по времени.

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

Целью диссертации является повышение эффективности функционирования вычислительных кластерных и Грид-систем за счет управления распределением потока заданий (эффективность оценивается средним временем ожидания результата).

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

* Автор работы выражает признательность и благодарность ныне покойному Лукьянову Виктору Сергеевичу, д.т.н., профессору кафедры «Электронные вычислительные машины и системы», под руководством которого начиналась данная работа.

1) произвести обзор существующих подходов и моделей кластерных и Грид-систем, аппроксимации нагрузки и распределения заданий внутри Грид-системы;

2) разработать детерминированную дискретно-событийную имитационную модель кластерной и Грид-системы для обслуживания заданного списка заданий;

3) сформировать набор стратегий управления для распределения заданий внутри Грид-системы;

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

5) реализовать программно детерминированную и стохастическую дискретно-событийные модели, а также аппроксимацию нагрузки вычислительных систем с последующей проверкой работоспособности и эффективности разработанных моделей, алгоритмов и программных средств;

6) сформулировать методики моделирования кластеров и Грид-систем, а также методику определения рациональной стратегии управления распределением заданий.

Объектом исследования являются вычислительные Грид- и кластерные системы.

Предметом исследования являются процессы обслуживания в вычислительных Грид- и кластерных системах.

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

Научная новизна работы заключается в следующем:

1) Сформирован набор стратегий распределения заданий в Грид-системе, учитывающих различные характеристики вычислительных систем и позволяющих повысить эффективность управления и принятия решений по распределению заданий в Грид-системе.

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

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

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

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

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

Разработанные модели и методы были реализованы в виде комплекса программных средств БеШгоскег+З^сЬВгоскег, а также отдельного средства 8(:осЫгтО для проведения лабораторных, семестровых и курсовых работ.

Программное средство ЗЬсЫтЮ внедрено в учебный процесс на кафедре «ЭВМ и С» в рамках дисциплин «Вычислительные системы и сетевые технологии» на замену ранее разработанному для этих целей «Опс1Мос1е1» и потенциально может быть внедрено в курсы «Отказоустойчивые системы» и «Надежность и эксплуатация средств ВТ», в которые было внедрено побочно разработанное средство <сЫе18уз». Программные средства «БегВгоскег^осЬВгоскег» внедрены в учебный процесс при моделировании работы кафедрального кластера и выполнении дипломных работ.

Получены четыре свидетельства о регистрации программных средств «Бе1Вгоскег», «Б^сЫтЮ», «^БуБ» и «Спс1Мос1е1» в Федеральной службе по интеллектуальной собственности.

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

1) набор стратегий для распределения заданий внутри Грид-системы;

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

3) методики моделирования работы кластерной системы, Грид-системы и определения рациональной стратегии распределения заданий в Грид-системе;

4) программные средства «БегВгоскег» для детерминированного моделирования, «Б1осЬВгоскег» для стохастической аппроксимации и стохастического моделирования и (^осЫтЮ» для внедрения в учебный процесс.

Достоверность научных результатов обеспечивается использованием апробированных методов (системного анализа, математического моделирования, процедурного и объектно-ориентированного

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

Апробация работы. Результаты работы обсуждались на внутривузовских научных конференциях и кафедральных семинарах кафедр «ЭВМиС» и «САПРиПК», а также докладывались на следующих конференциях: Международная научно-практическая конференция «Инновации на основе информационных и коммуникационных технологий» (г. Сочи, 2010), Международная научно-практическая конференция «Инновационные информационные технологии» (г.Прага, 2013), XI Международная научно-

практическая конференция «Перспективы развития информационных технологий» (г. Новосибирск, 2013), IX международная научно-практическая конференция «Perspektywiczne opracowania sa nauka i technikami» (г. Przemysl, 2013), VI международная научно-практическая конференция «Инновации в технологиях и образовании» (г. Белово, 2013), I всероссийская научно-практическая конференция «России - творческую молодёжь» (г. Камышин, 2013).

В 2014 году за работу по теме диссертации автору была назначена Стипендия Президента РФ на 2014-2015 учебный год.

Публикации. По теме диссертации опубликованы 34 печатные работы, в том числе 7 в изданиях, рекомендованных ВАК, 2 работы в зарубежных журналах (из них 1 работа в зарубежном журнале, входящем в международную базу цитирования «SCOPUS») и 1 монография. По результатам работы созданы 4 программных продукта, которые получили свидетельства о государственной регистрации.

Структура и содержание диссертационной работы. Диссертационная работа состоит из введения, пяти глав, заключения, а также библиографического списка из 155 наименований и двух приложений. Общий объем работы 167 страниц, в том числе 60 рисунков и 35 таблиц.

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

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

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

Демонстрируются отличия моделей, используемых для вычислительных систем, от систем массового обслуживания типа Cl Gin по Кендаллу:

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

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

. 3) введение потоков заданий различной ширины;

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

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

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

Однако эти работы имеют ряд недостатков:

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

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

3) Часто аппроксимации не учитывают цикличной нагрузки (суточный, недельный, годовой цикл).

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

В конце главы сформулированы цели и задачи диссертационного исследования.

Во второй главе описываются предложенные алгоритмы и модели. Представлены алгоритмы и модель вычислительных систем для детерминированного дискретно-событийного имитационного моделирования, использующие бинарные кучи для ускорения вычислений (один из алгоритмов дан на рис. 1). Создан алгоритм продления детерминированных логов для корректного детерминированного моделирования Грид-системы с учетом цикличности нагрузки в течение недели. Также описаны простые, позволяющие сберечь вычислительные ресурсы подходы определения параметров моделируемой системы, основанные на принципе действия формулы Литгла.

Представлен список стратегий распределения заданий, включающий как существующие стратегии (QueueWidth, QueueLen, QueueDif), так и предлагаемые (Rotate, FreeExec, QueueProd, MaxProd, EqualLoading, EqualQueueLen, EqualQueueWidth). Все стратегии, кроме Rotate, предполагают выбор кластера с наименьшей стоимостью исполнения задания. Узлы, которые не имеют достаточного количества машин для исполнения задания, получают оценку, равную бесконечности. При совпадении оценок будем выбирать кластер, раньше стоящий в списке кластеров Грид-системы. Предполагается, что для всякого задания существует хотя бы один кластер, способный обеспечить его ширину.

Рисунок 1 — Алгоритм функционирования дискретно-событийной модели при останове по завершению обслуживания нагрузки

Перечислим рассматриваемые эвристики:

1) Rotate. Список кластеров просматривается циклически, начиная со следующего за тем, который получил последнее задание. Если кластер не

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

2) РгееЕхес:

V?

Эта предложенная нами оценка считает «более дорогим» более загруженный кластер. Используется при быстром выполнении заданий в отсутствие очереди.

3) (2иеие"МсШ1:

Ъ=-1-

^ . (2)

4) (ЗиеиеЬеп:

,.1+С?

V . (3)

5) С}иеие01£

С + 2 С зад] '

г--1-

П . (4)

6) С?иеиеРгос1:

Сэад]

Z=-¡~

W-P . (5)

7) MaxProd:

z={w-p)-\ (6)

8) EqualLoading:

z=Z

7^. (7)

9) EqualQueueLen:

Z=Q . (8)

10) EqualQueue Width:

Z=?*4 (9)

Обозначения: W - количество машин кластера, Лт - количество свободных машин кластера, - ширина задания, для которого определяется кластер, wMaj - ширина j-ro задания в очереди кластера, Q - длина очереди кластера, с3ад - сложность задания, для которого выбирается исполнитель, сзац

- сложность j-ro задания в очереди кластера, р - производительность узла, z

- стоимость исполнения задания на кластере.

Введем «одиннадцатую стратегию» — «Self» —отсутствие стратегии, когда каждый кластер исполняет свои задания без обмена с другими.

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

вводят зависимость между шириной и длиной задания. Для обозначения моделей используются модифицированные нами обозначения Кендалла.

Простая модель подразумевает введение рекуррентного потока Пальма для времен прихода заданий. Ширины заданий генерируются в момент прихода в соответствии с распределением вероятностей. Обозначается как А1$В*1п . Многопоточная модель подразумевает введение отдельного потока для заданий каждой ширины. Обозначается как $А1$В*/п . Нестационарная модель использует введение нестационарного рекуррентного потока Пальма (наше собственное обобщение) для времен прихода заданий. Обозначается как ~А/5Вл/п . Многопоточно-нестационарная и нестационарно-многопоточная вводят отдельный нестационарный рекуррентный поток Пальма для заданий каждой ширины. Обозначается как $~А1$Вл/п и ~$А1$В*1п , соответственно. Отличия в том, что в первом случае для каждого потока рассчитывается своя интенсивность. Во втором случае интенсивность каждого потока рассчитывается как доля от интенсивности прихода всех заданий (доля равна вероятности прихода заданий определенной ширины). Во всех моделях для каждой ширины задания вводится свой собственный закон распределения длины заданий. В рамках данной работы законы для различных ширин будут различаться только параметрами.

Нестационарные рекуррентные потоки Пальма вводятся по формуле:

I

/?1(0л=л* , (Ю)

где В" - неотрицательная случайная величина с единичным матожиданием, 'о - время прихода последнего задания (для первого задания — время начала моделирования), / - время прихода следующего задания.

Модели даются с сопутствующими законами распределения: М экспоненциальное распределение, Г - гамма-распределение, V -распределение Вейбулла, Ш - логнормальное распределение, ГIV - гамма-вейбуллово распределение (название не является общепринятым), Я(п) -гиперэкспонециальное распределение с п ветками, НГ(п) - гипер-гамма-распределение с п ветками, ¡А - логарифмическая кусочно-линейная аппроксимация. Для определения параметров (кроме /А ) используются метод моментов (ММ) для негиперраспределений и метод наибольшего, или максимального, правдоподобия (МНП) для всех распределений.

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

В третьей главе производится описание программных разработок «Ве1Вгоскег», «ЗЬсЬВгоскег» и «БкюЫгшС»: даны требования, подходы к реализации, функциональные описания и архитектуры.

. «Бе1Вгоскег» моделирует работу кластерной системы или нескольких кластерных систем, объединенных в единую вычислительную систему (вариант Грид-системы). В качестве источников данных используются детерминированные списки заданий. Предусмотрена конвертация во входные

данные разработанной программы логов формата Standard Workload Format (SWF), которые представляют собой задокументированные нагрузки вычислительных систем, предоставленные в публичный доступ архивом Parallel Workloads Archive. Разработка велась на платформе Linux Mint 13 Maya (хб4) с использованием компилятора GCC и прочих его утилит. Это избавляет нас лицензионной зависимости, но теоретически разрешает перевод кода на платформу Windows с минимумом изменений (используя пакет MinGW).

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

1) События погружены в бинарную кучу, что обеспечивает нам быструю выборку следующего события.

2) Все списки заданий кластеров поступают на моделирование в отсортированном по времени прибытия порядке и объединяются в один константный список. Сведение осуществляется алгоритмом std::merge().

3) Использовалось распараллеливание вычислений с применением технологии ОрепМР.

4) Использование профилирования и подбор ключей компиляции сократили время выполнения программы примерно на 20-30%.

Как таковая программа «StochBrocker» не существует: существует набор надстроек над программой «Deffirocker». Генерация нагрузки производится по одной из пяти моделей нагрузки.

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

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

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

Таблица 1 — Валидация аналитическими моделями (фрагменты)

р С0УХ СОУ„ Модель Средняя длина очереди Среднее время пребывания задания в системе, Хц"1 .

Разработка Эталон Разработка Эталон

0,75 1 1 М/М/128 0,00314476 0,00339964 0,999761 1,00004

0,9375 1 1 М/М/128 5,36205 5,47428 1,04495 1,04562

0,96875 1 1 М/М/128 19,4308 19,4473 1,15716 1,15683

0,3 1 1 М/М/1 0,12880 0,12857 1,42880 1,42857

0,5 1 1 М/М/1 0,50130 0,50000 2,00296 2,00000

0,7 1 1 М/М/1 1,63036 1,63333 3,33038 3,33333

0,9 0 0 0 =0 1 =1

0,9 0 0,5 С/£4/1 0,832048 =1,0125 1,92462 =2,125

0,9 0 1 тми 3,76839 3,76079 5,18752 5,17866

0,9 0 2 Д/Г/1 15,8492 =16,2 18,6107 =19

0,9 0,5 1 EJM.I1 4,83890 4,84474 6,37657 6,38305

0,9 1 0 М/С/1 4,06235 4,05 5,51221 5,5

0,9 1 0,5 М/Е4/1 5,05254 5,0625 6,61323 6,625

0,9 1 1 М/М/1 8,04713 8,10000 9,94385 10,00000

0,9 I 2 М/Г/1 20,3454 20,25 23,6038 23,5

0,9 2 1 Г/М/1 21,29620 21,13100 24,64590 24,47889

Таблица 2 — Сравнение результатов ОпсШт и БйВгоскег

вгИБЫ* БегВгоскег

Время прихода последнего задания, сек 254828 254828 254828

Время завершения выполнения всех заданий, сек 7465006 7465004 7464980

Средняя длина/ширина очереди 0,339306 0,339226 0,339592

Среднее число исполняемых задач/Среднее число занятых каналов 30,5052 30,5051 30,5052

Среднее число заданий в системе 30,8445 30,8443 30,8448

Средняя площадь очереди 56509 56497 56566

Среднее время ожидания, сек 2473,55 2472,97 2475,63

Среднее время исполнения, сек 222384 222383 222383

Средне время в системе, сек 224858 224856 224859

Время выполнения имитации, сек 1 12 0,4

Таблица 3 — Результаты моделирования Грид-системы (фрагмент)

Rotate (DetBrocker) Rotate (GridSim) QueueLen (DetBrocker) QueueLen (GridSim) MaxProd (DetBrocker) MaxProd (GridSim)

Длина лога, сек 254828 254828 254828 254828 254828 254828

Время завершения выполнения, сек 6802300 6802313 7582330 7574266 7898550 7898555

Средняя длина/ширина очереди 16,4545 16,455 3,60098 3,67948 20,6698 20,6694

Среднее число занятых каналов 19,0929 19,093 24,9143 25,70609 28,8307 28,8307

Среднее число заданий в системе 35,5475 35,548 28,5153 29,3856 49,5005 49,5001

Средняя площадь очереди 4064600 1577127 794077 791591 4786730 4786644

Среднее время ожидания, сек 109306 109308 26663,9 27216,2 159435 159432

Среднее время исполнения, сек 126832 126833 184481 190141 222383 222383

Средне время в системе, сек 236137 236141 211145 217358 381818 381816

Сначала демонстрируется функционирование детерминированных моделей кластерных (рис. 2) и Грид-систем (рис. 3-4). Затем показывается использование различных законов распределения на примере времени выполнения заданий из простой (все задания выполняются на одной машине) нагрузки из лога LPC EGEE.

Далее вводятся пять моделей нагрузки (табл. 4) для более сложного случая LANL СМ5 (задания имеют ширины 32, 64, 128, 256, 512 или 1024 машины). С их помощью осуществляется переход от детерминированных к стохастическим моделям кластерных (рис. 2) и Грид-систем (рис. 3-4).. Демонстрируется выигрыш (или проигрыш) от использования стратегий при различной нагруженности (рис. 5). В конце главы сформулированы инженерные методики по моделированию вычислительных кластерных и Грид-систем (рис. 6) и выбору стратегии распределения заданий (рис, 7).

LPC EGEE HPC2N CTC SP2 '96

SDSC Раг96 SDSC Раг95

LANL СМ5

NASA iPSC

1

10 100 Среднее время ожидания результата, мин

0 Детерминированная модель я Стохастическая модель Рисунок 2 — Среднее время ожидания результата в кластерах

MaxProd EqualQueueWidth J EqualQueueLen Equal Loading QueueProd QueueDif QueueWidth QueueLen FreeExec Rotate Self

2 3 4 5 Время, лет

8 9 10 11 12

и Детерминированная модель и Стохастическая модель

в Время прихода последнего задания

Рисунок 3 — Время выполнения пакета заданий в Грид-системе

EqualQueueWidth ¡Д8™ EqualQueueLen EqualLoading QueueProd ШШШШШШ

QueueDif QueueWidth QueueLen

Self ^

0 15 30 45 60 75 90 105 120 135 150 165 180 Среднее время ожидание результата, мин

а Детерминированная модель в Стохастическая модель Рисунок 4 — Среднее время ожидания результата в Грид-системе

После этого описывается внедрение предложенных разработок. Разработанные средства могут быть применены при проектировании и модификации вычислительных Грид-систем для показателей обслуживания. Средства «DetBrocker» и «NetSys» были внедрены в учебный процесс кафедры «ЭВМиС». Средство «GridModel» активно использовалось при проведении лабораторных работ по курсу «Вычислительные системы и сетевые технологии» на кафедре «ЭВМиС» и было заменено на более продуктивное "StochlmiG".

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

Таблица 4 — Сравнение различных моделей для LANL СМ5

НГ/ $НГЛ/1024 $НГ/ $НГл/1024 ~НГ/ $НГА/1024 $~НГ/ $НГл/1024 ~$НГ/ $НГл/1024 Детер. модель

Использование 0,742312 0,760039 0,743287 0,743577 0,743111 0,743525

Среднее время пребывания задания в системе, сек 5844,01 8957,71 9377,6 8455,26 10146,3 8876,86

Среднее время ожидания в очереди,сек 3263,03 6340,28 6796,97 5873,79 7564,95 6295,27

Среднее время обслуживания, сек 2580,98 2617,43 2580,63 2581,47 2581,37 2581,59

Среднее число используемых узлов 760,127 778,279 761,126 761,423 760,945 761,369

Среднее число заданий под обслуживанием 5,05155 5,12017 5,05768 5,0607 5,05747 5,05866

Среднее число заданий в системе 11,4404 17,5292 18,382 16,5777 19,8814 17,3944

Средняя длина очереди 6,38882 12,409 13,3244 11,517 14,8239 12,3357

0,4 0,5 0,6 0,7 Нагруженность

QueueLen QueueWidth EqualQueueLen EqualQueueWidth

Рисунок 5 — Выигрыш от использования стратегий по сравнению с вариантом Seif

Рисунок 6 — Методика моделирования вычислительной Грид-системы (методика №2)

Рисунок 7 — Методика выбора стратегии для распределения заданий в Грид-системе (методика №3)

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Создан комплекс средств (алгоритмическое, программное, математическое и методическое обеспечение) для решения следующих задач: детерминированного и стохастического дискретно-событийного имитационного моделирования вычислительных и Грид-систем; средства аппроксимации стохастической нагрузки вычислительных систем; выбора стратегии распределения заданий внутри Грид-системы.

Полученные результаты можно сформулировать следующим образом:

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

2) Сформирован набор стратегий распределения заданий в Грид-системе, учитывающих различные характеристики вычислительных систем и позволяющих повысить эффективность управления и принятия решений по распределению заданий в Грид-системе.

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

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

5) Предложены программные реализации моделей: комплект "DetBrocker+StochBrocker" для осуществления детерминированного и стохастического моделирования (включая стохастическую аппроксимацию) и "StochlmiG" для внедрения в учебный процесс.

6) Произведена валидация разработанных средств путем: сравнения полученных нами данных с предоставленными архивом нагрузок; сопоставления с аналитическим (марковским и немарковским) решением; имитации сторонних стохастических нагрузок; сопоставлением с альтернативным решением сторонними средствами.

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ Статьи в журналах, рекомендуемых ВАК

1. Гаевой, C.B. Детерминированная имитационная модель кластеров грид-системы, обслуживающих задания / Гаевой C.B., Аль-Хадша Ф.А.Х., Лукьянов B.C. // Вестник компьютерных и информационных технологий. -2014,-№6.-С. 39-43.

2. Детерминированная имитационная модель кластеров грид-системы для сравнения эффективности использования эвристик распределения заданий / Гаевой C.B., Аль-Хадша Ф.А.Х., Фоменков С.А., Лукьянов B.C. // Прикаспийский журнал: управление и высокие технологии. - 2014. - № 2. - С.

148-157.

3. Гаевой, C.B. Аппроксимация времени выполнения заданий на примере вычислительного кластера LPC EGEE 2004 / Гаевой C.B., Аль-Хадша Ф.А.Х., Фоменков С.А. // Известия ВолгГТУ. Серия "Актуальные проблемы управления, вычислительной техники и информатики в технических системах". Вып. 21 : межвуз. сб. науч. ст. / ВолгГТУ. - Волгоград, 2014. - № 12 (139). - С. 135-141.

4. Имитационная модель гетерогенной вычислительной системы / Лукьянов B.C., Жариков Д.Н., Гаевой C.B., Попов Д.С. // Изв. ВолгГТУ. Серия "Актуальные проблемы управления, вычислительной техники и информатики в технических системах". Вып. 11 : межвуз. сб. науч. ст. / ВолгГТУ. - Волгоград, 2011,-№9. -С. 85-88.

5. Сравнение эвристик распределения заданий в Грид-системе путем детерминированного имитационного моделирования / Гаевой C.B., Фоменков С.А., Аль-Хадша Ф.А.Х., Лукьянов B.C. // Известия ВолгГТУ. Серия "Актуальные проблемы управления, вычислительной техники и информатики в технических системах". Вып. 22 : межвуз. сб. науч. ст. / ВолгГТУ. - Волгоград, 2014.-№ 25 (152). - С. 159-164.

6. Гаевой, C.B. Модели аппроксимации нагрузки кластера на примере LANL СМ5 для стохастического имитационного моделирования I Гаевой C.B., Фоменков С.А. // Известия ВолгГТУ. Серия "Актуальные проблемы управления, вычислительной техники и информатики в технических системах". Вып. 22 : межвуз. сб. науч. ст. / ВолгГТУ. - Волгоград, 2014. - № 25 (152). - С. 151-158.

7. Лукьянов, B.C. Оценка показателей надёжности сетей / Лукьянов

B.C., Гаевой C.B., Аль-Хадша Ф.А.Х. // Вестник компьютерных и информационных технологий. - 2013. - № 8. - С. 47-52,

Статьи в журналах SCOPUS

8. Аль-Хадша, Ф.А.Х. The coverage analysis of hierarchical networks with specified reliability indices / Аль-Хадша Ф.А.Х., Гаевой C.B., Лукьянов B.C. // International Review on Computers and Software (TRECOS). - 2013. - Vol. 8, No. 5. -

C. 1199-1202.

Свидетельства о регистрации программных систем

9. Свид. о гос. регистрации программы для ЭВМ № 2010610693 от 20 янв. 2010 г. РФ, МПК (нет). Имитационная модель грид-системы (GridModel) / Лукьянов B.C., Жариков Д.Н., Гаевой C.B., Шафран Ю.В.; ВолгГТУ. - 2010.

10. Свид. о гос. регистрации программы для ЭВМ № 2013614201 от 25 апреля 2013 г. РФ, МПК (нет). Имитационная модель для оценки влияния параметров надёжности и иных характеристик на производительность кластерной системы (SrvModel) / Гаевой C.B., Лукьянов B.C.; ВолгГТУ. - 2013.

11. Свид. о гос. регистрации программы для ЭВМ № 2015610916 от 21 января 2015 г. РФ, МПК (нет). Детерминированная дискретно-событийная имитационная модель вычислительных кластерной и Грид-систем для оценки их производительности при различных нагрузках и различных стратегиях распреде-

ления заданий (DetBrocker) / Гаевой C.B., Фоменков С.А.; ВолгГТУ. - 2015.

12. Свид. о гос. регистрации программы для ЭВМ № 2015610935 от 21 января 2015 г. РФ, МПК (нет). Стохастическая дискретно-событийная имитационная модель вычислительной Грид-системы для оценки ее производительности при различных стратегиях распределения заданий (StochlmiG) / Гаевой C.B., Фоменков С .А.; ВолгГТУ. - 2015.

Монографии

13. Имитационное моделирование грид-систем : монография / Лукьянов B.C., Андреев А.Е., Жариков Д.Н., Островский А.А., Гаевой C.B.; ВолгГТУ. - Волгоград, 2012. - 215 с.

Статьи в журналах и сборниках

14. Гаевой, C.B. Аппроксимация стохастических параметров вычислительного кластера на примере LANL СМ5 / Гаевой C.B., Аль-Хадша Ф.А.Х. // Perspektywiczne opracowania sa nauka i technikami - 2013 : mater. IX miedzynarod. nauk.-prakt. konf., 7-15 listopada 2013 r. Vol. 33. Matematyka. -Przemysl, 2013. - S. 67-70.

15. Гаевой, C.B. Моделирование работы вычислительного кластера на примере LANL СМ5 [Электронный ресурс] / Гаевой C.B., Аль-Хадша Ф.А.Х. // SCI-ARTICLE.RU : электронный периодический научный журнал. - 2013. - № 3 (ноябрь). - С. 304-313. - Режим доступа : http://sci-article.ru/stat.php?

i=modelirovanie_rabotY_vYchislitelnogo_klastera_na_primere_LANL_CM5.

16. Гаевой, C.B. Эвристики распределения заявок в Грид-системах (Grid) / Гаевой C.B., Аль-Хадша Ф.А.Х., Лукьянов B.C. // Perspektywiczne opracowania sa nauka i technikami - 2013 : mater. IX miedzynarod. nauk.-prakt. konf., 7-15 listopada 2013 r. Vol. 33. Matematyka. - Przemysl, 2013. - S. 63-66.

17. Аль-Хадша, Ф.А.Х. Assessment of the Network Reliability / Аль-Хадша Ф.А.Х., Гаевой C.B., Лукьянов B.C. // Communications in Control Science and Engineering (CCSE). - 2013. - Vol. 1, Issue 4, October. - C. 58-62.

Подписано в печать 26.01.2015 г. Формат 60x84 1/16. Бумага офсетная. Печать трафаретная. Печ. л.1,0. Тираж 100 экз. Заказ № 44.

Типография ИУНЛ Волгоградского государственного технического университета. 400005, г. Волгоград, просп. им. В.И. Ленина, 28, корп. №7.