Содержание к диссертации
Введение
ГЛАВА 1. Существующие подходы к моделированию грид-систем 13
1.1 Описание проблемной области 13
1.2 Способы аппроксимации входного потока заявок вычислительной системы 16
1.2.1 Модели „Calzarossa and Serazzi, 1985" (модель №1) и „Leland and Ott, 1986" (модель №2) 16
1.2.2 Модель „Feitelson, 1996" (модель №3) 17
1.2.3 Модель „Downey, 1997" (модель №4) 19
1.2.4 Модель „Jann et al, 1997" (модель №5) 20
1.2.5 Модель „Lublin, 1999" (модель №6) 22
1.2.6 Модель „Tsafrir, 2005" (модель №7) 30
1.3 Имитационное моделирование стратегий распределения заданий 32
1.3.1 Первая модель отИСПРАН (модель №1) 32
1.3.2 Вторая модель отИСПРАН (модель №2) 34
1.3.3 Третья модель отИСПРАН (модель №3) 36
1.3.4 GridSim (модель №4) 36
1.3.5 GridMe (модель №5) 39
1.4 Цели и задачи диссертационного исследования 39
ГЛАВА 2. Алгоритмическое обеспечение процесса выбора стратегии в грид-системе 41
2.1 Детерминированная модель кластерной и Грид-системы 41
2.2 Стратегии распределения заданий внутри Грид-системы 45
2.3 Определение показателей кластерной и Грид-систем 49
2.4 Правила использования логов 54
2.5 Стохастическая аппроксимация параметров кластерной системы 56
2.6 Распределения для аппроксимации параметров кластерной системы 58
2.7 Модели для имитации нагрузки кластерной системы 65
2.7.1 Простая модель (модель №1) 66
2.7.2 Многопоточная модель (модель №2) 66
2.7.3 Нестационарная модель (модель №3) 67
2.7.4 Многопоточно-нестационарная модель (модель №4) 70
2.7.5 Нестационарно-многопоточная модель (модель №5) 71
2.7.6 Прочие модели 72
2.8 Стохастические модели кластерной и Грид-систем 72
2.9 Генерация случайных величин 73
2.10 Выводы по главе 2 75
ГЛАВА 3. Разработка автоматизированных систем моделирования 77
3.1 Программа DetBrocker 77
3.1.1 Требования к системе 77
3.1.2 Выбор средства реализации 78
3.1.3 Архитектура и функциональная схема DetBrocker 80
3.1.4 Использование высокопроизводительных вычислений 81
3.2 Программа StochBrocker 81
3.3 Программа StochlmiG 83
3.3.1 Разработка GridModel 83
3.3.2 Требования к системе 84
3.3.3 Архитектура и функциональная схема StochlmiG 85
3.4 Выводы по главе 3 86
ГЛАВА 4. Анализ работоспособности и эффективности созданных средств 87
4.1 Источник данных для моделирования 87
4.2 Проверка имитационной модели аналитическим решением 88
4.3 Валидация неравномерной нагрузки 94
4.4 Валидация стохастической аппроксимации длины заданий 97
4.5 Валидация стохастической аппроксимации интервалов между приходами заданий 100
4.6 Валидация моделирования работы кластера на примере СТС 102
4.7 Сравнение моделирования работы кластера с GridSim 106
4.8 Сравнение моделирования работы Гридас GridSim 107
4.9 Выводы по главе 4 108
ГЛАВА 5. Методическое обеспечение процесса выбора стратегии в грид-системе
5.1 Детерминированная имитационная модель кластера ПО
5.2 Детерминированная модель Грид-системы 112
5.3 Аппроксимация стохастических параметров кластера на примере LPC EGEE 116
5.4 Выбор стохастической модели кластера на примере LANL СМ5 117
5.5 Стохастическая модель кластеров 127
5.6 Стохастическая модель Грид-системы 129
5.7 Сравнение детерминированной и стохастической моделей 131
5.8 Адекватность использования стратегий при различной нагруженности 134
5.9 Методика моделирования 136
5.10 Внедрение разработок 140
5.11 Выводы по главе 5 141
Заключение 142
Список использованных источников
- Модели „Calzarossa and Serazzi, 1985" (модель №1) и „Leland and Ott, 1986" (модель №2)
- Определение показателей кластерной и Грид-систем
- Архитектура и функциональная схема DetBrocker
- Валидация стохастической аппроксимации интервалов между приходами заданий
Модели „Calzarossa and Serazzi, 1985" (модель №1) и „Leland and Ott, 1986" (модель №2)
Эта модель создают некоторый абстрактный поток входных заданий без моделирования их исполнения, на основе анализа шести существующих потоков. Целью ставится создание модели, которая бы описывала абстрактную, реально не существующую вычислительную систему, поэтому сравнить ее с чем-то реальным проблематично.
При изучении логов авторами модели №3 были сделаны два вывода. Во-первых, узкие задания доминируют над широкими: во всех логах имеет значительное количество работ единичной ширины, многие неединичные работы используют менее 10 узлов даже на машинах с сотнями узлов. Во-вторых, это дискретная природа распределения ширин заданий с преобладанием одних размеров над другими. Наиболее популярные размеры в большей степени являются степенями двойки, даже для тех кластеров, где нет архитектурной обусловленности для этого.
Модель распределения заданий основана на гармоническом распределении порядка 1,5 (вероятность размера п пропорциональна — ) с выделением некоторых «особо популярных» размеров. Также два факта определяют моделирование длин заданий. Во-первых, это хорошо известный факт, что эти значения сильно варьируются, так что коэффициент вариации этого распределения больше единицы. Второй — это то, что имеется слабая корреляция между размером задания и его длиной. Несмотря на то, что есть узкие задания, которые выполняются долго, и широкие задания, которые выполняются быстро, обычно более широкое задание исполняется дольше.
Модель для длин заданий представляется гиперэкспоненциальным распределением, так что его коэффициент вариации больше одного. Также введено линейное соотношение между размером задачи и вероятностью использования экспоненты с большим матожиданием. Таким образом, для каждого размера используется свое распределение, и матожидание длины для более широких заданий больше.
Часто допускается, что задания независимы. В [98, 99, 145] анализ логов показывает, что это не всегда справедливо. В частности, принимается, что не редки случаи, когда один и тот же пользователь запускает одну и ту же задачу многократно, создавая последовательности задач с одинаковыми свойствами.
В [98, 99, 145] было обнаружено, что число запусков задачи распределено по закону Ципфа. Поэтому вероятность п запусков пропорциональна и"2 5 .
На практике, это означает, что следующее исполнение задания должно начинаться после предыдущего. То есть выходной поток заданий, обработанных кластером, будет влиять на входной поток. В частности, время генерации повторных заданий необходимо будет определять лишь после исполнение предыдущего экземпляра этого задания.
Времена прихода заданий в работе [98,99, 145] даются простейшим (стационарным пуассоновским потоком), за исключением повторных исполнений заданий, которые приходят мгновенно после завершения предыдущего исполнения.
Реализация модели открытая с условием сохранения ссылки на публикации, что позволяет нам ее апробировать. Этот код доступен в двух версиях: 1996 года и исправленная 1997. Отличия проявляются в деталях распределений. Для использования авторами модели рекомендуется версия 1997 года.
Данная модель4 описана в [95, 96, 143]. Она создана с целью моделировать различные стратегии масштабирования масштабируемых заданий и вводит функцию ускорения выполнения задания в зависимости от числа используемых процессоров. Мы не будем касаться стратегий масштабирования и функции ускорения, но затронем сам процесс моделирования исполнения заданий.
Модель была создана в результате анализе логов SDSC и была подтверждена логами СТС [131].
В модели [95,96, 143] отвергается доминирование степеней двойки в ширинах заданий. Предложенная модель заявлена логравномерной: вероятность, что задание использует меньше п процессоров, пропорциональна log (и) . Это называется средним параллелизмом задания и используется для определения его ускорения при распараллеливании.
Из-за изменчивой ширины модель оперирует не длиной задания, а тем, что в работе называется «куммулятивной длиной» и определяется как суммарная машинная работа над заданием вне зависимости от того, на скольких процессорах она исполняется. Длина определяется через функцию ускорения5.
Предложенная аппроксимация снова логравномерная: вероятность того, что задание использует менее tузел секунд , пропорциональна log(t) .
Поток поступления заданий принимается пуассоновским, но не простейшим. Каждые сутки делятся на два 12-часовых интервала. В течение первой (день) части задания прибывают простейшим потоком событий. Они могут быть поставлены на исполнение или в очередь, если исполнение не возможно. В течение второй части (ночь) задания не приходят, но уже пришедшие задания продолжают исполняться. Возможности программы, приложенной к публикациям, несколько шире: можно задать коэффициент поправки интенсивности для каждых двух часов суток. Правда, при моделировании это сопровождается небольшой неточностью: изменения интенсивности пуассоновского потока происходят не в описанные моменты времени каждые два часа, а в моменты прихода заданий. Таким образом, в ночное время может все-таки приходит одно заданий, которое осталось от дневного потока. Именно в момент прихода этого задания входной поток заданий «выключается». После этого он уже не может «включиться», так как ночью задание уже не может прийти, чтобы изменить интенсивность потока.
Имитационная модель предельно проста: она мало отличается от имитационных моделей классических СМО. В модели всего два события: приход нового задания и завершение обслуживания. Приход нового задания ведет к постановки его в очередь, завершение обслуживания — к освобождению ресурсов. После каждого освобождения ресурсов производится попытка изъятия заданий из очереди (здесь используют предложенные авторами [95,96, 143] стратегии, которые подразумевают, что извлекаемых заданий может быть несколько в результате одного освобождения ресурсов; это самое серьезное отличие от классических СМО из учебников). На этом этапе происходит масштабирование заданий, причем задания влияют друг на друга при масштабировании, если их несколько в очереди.
Определение показателей кластерной и Грид-систем
Измерения показателей кластерной системы ведется как измерение показателей системы массового обслуживания, что рассматривается в [69-71, 74]. Используется подход, аналогичный выводу формулы Литтла [11].
Рассмотрим рисунок 2.4 [11]. Он описывает процесс пребывания задания в произвольном блоке.
Для этого рисунка справедливы следующие соотношения [11]: где Т; - время пребывания в блоке і-го задания, Л - площадь гистограммы, n(t) 5 a(t) , 5(t) - число заданий в системе, число пришедших заданий, число вышедших заданий как функций времени, Т - среднее время пребывания заявки в блоке, N - среднее число заявок в блоке, t - время моделирования (отсчитанное от нуля), А - множество пришедших в систему заданий за время моделирования.
Определение Т можно концептуально проводить по-разному. Это связано с тем, что в момент окончания моделирования могут содержаться задания в блоке. Предложенный выше вариант рассматривает их как ползадания.
При достаточно большом периоде моделирования a(t) 5(t) 5 поэтому предложенную формулу можно упростить: где А - множество вышедших из системы заданий за время моделирования.
С ростом времени моделирования ( a(t) 5(t) ), поэтому Т =Т . Найдем сумму всех времен, которые задания простояли в очереди. Если разделить эту сумму на число заданий, то мы получим среднее время ожидания, а, если разделить на время моделирования, то получится средняя длина очереди. Повторив аналогичные расчеты для блока обслуживания, получим среднее число обслуживаемых заданий и среднее время обслуживания (сумма времен выполнения и число заданий известны еще до моделирования, поэтому последний параметр также можно определить до моделирования). Повторив для всей системы в целом (или сложив предыдущие результаты попарно, так как время в системе — это время ожидания плюс время выполнения), получим среднее число заданий в системе и среднее время пребывания в системе.
Чтобы получить среднюю ширину очереди (или среднее число занятых каналов, обозначим М ), нужно просуммировать произведения времени ожидания (выполнения) и ширины для всех заданий, а затем разделить эту сумму на время моделирования.
Использование — это отношение среднего числа занятых каналов к числу каналов. Долю системного времени, проведенного в очереди, определим как отношение среднего времени ожидания к среднему времени пребывания в системе. Долю заданий, побывавших в очереди, определим просто подсчитав число заданий, попавших в очередь. Если разделить среднее время ожидания на эту долю, то получим среднее время ожидания среди побывавших в очереди. площади под гистограммами (интегралы функций по интервалу моделирования) соответственно числа обслуживаемых заявок, длины очереди, числа заданий в системе, числа занятых каналов, ширины очереди;
Все вышеназванное можно рассчитать и для Грид-системы. Единственным различием в измерении этих параметров для кластера и для Грид-системы является следующее. В Грид-системе каналы разных кластеров имеют разную производительность, поэтому необходимо оперировать приведенным к эталонной машине временем для соотношений нагруженности и использования. Используем обозначения из 1.1, где уже были введены понятия нагруженности и использования кластерной системы, и снабдим все обозначения параметров кластеров индексом кластера. использование Грид-системы, Mt - число каналов обслуживания (вычислительных машин) і-го кластера, - среднее число используемых каналов і-го кластера, Pt - производительность і-го кластера, К - количество кластеров. [131] предоставляет реальные логи работы вычислительных систем. Очищенные логи (cleaned) рекомендуются сайтом для научных изысканий, поэтому в дальнейшем мы будем использовать именно их. Часть заданий отброшена по причине отсутствия необходимой информации (время, длина и/или ширина) для их моделирования, но это практически не должно сказаться на результате из-за малой доли таких задач. Здесь и далее при наличии очищенных логов работа будет вестись именно с ними, если в тексте явно не будет указано иное. В логах присутствуют задания, для которых не указан хотя бы один из тройки параметр (время прихода, исполнения или ширина). Такие задания отбрасываются. Использование логов «как есть» нерационально по двум причинам: во-первых, входной поток заданий обладает определенной циклической закономерностью в течение рабочей недели ( W=76H. у а, во-вторых, логи имеют разную длину. Из-за такой цикличности (рис. 2.5) кластера будут испытывать пики нагрузки синхронно, поэтому этот фактор надо учесть при моделировании.
Архитектура и функциональная схема DetBrocker
В данном разделе мы рассмотрим системы массового обслуживания М/М/128 и G/G/l . В концепции нашей модели мы исследуем вырожденный вариант, когда все задания имеют одинаковую ширину. Поскольку стохастическая модель является всего лишь небольшим расширением детерминированной, то будем валидировать сразу стохастическую модель. В качестве эталонного решения воспользуемся аналитическим марковским для М/М/128 [44, 45, 47, 132, 154] и немарковскими для M/G/1 , для G/G/1 и для G/M/1 решениями [20]. Расчетными параметрами будут: средняя длина очереди и среднее время пребывания задания в системе. Будем допускать, что средняя длина задания — [дГ1 = 1 сек .
Необходимо ввести некоторые дополнительные обозначения для модели Кендалла: G 5 GI - произвольное распределение параметра при независимости любых двух экземпляров случайной величины (под G уже подразумевает независимость, но обозначение GI используется для явной демонстрации этого), Е(п) , Еп или просто Е - распределение Эрланга п -го порядка, D - детерминированный случай (временной параметр — константа), covk и cov - коэффициенты вариации соответствующих параметров. Также нам потребуются обозначения из 1.1 и 2.3.
Структура уравнения делает удобным использование метода итераций [107, 108]. При старте из точки о=1/2 все варианты привели нас к требуемому корню.
Результаты сравнения с аналитическими решениями приведены в табл. 4.2-4.5. Время имитации выберем равным 100ч., а количество итераций равным 80 (погрешность не более 5%). Очевидно соответствие эталонных данных и полученных при помощи разработанной модели. При больших размерах очереди имитация несколько занижает ее размер. Это связано с тем, что процесс еще не успевает установиться. Результат сильно зависит от коэффициентов вариации: даже увеличение его до 2,0 способно сильно изменить результат. Для реальных величин он может достигать 10-20.
На рисунке 2.5 представлено изменение интенсивности потока входящих заданий кластера LANL СМ5 (лог LANL-CM5-1994-4.l-cln.swf). Также в подразделе 2.7 приведены способы аппроксимации этой неоднородности в моделях №№3-5. Аппроксимации всех логов данного кластера и их моделирование будут подробно описаны в подразделе 5.4. В данном разделе по предложенным моделям были синтезированы искусственные логи. Использовались следующие законы распределения для моделей: М (ММ и МНИ дают один результат), IN (ММ), /А , Г (ММ), нг(2) (МНИ).
Длина каждого лога принималась равной четырем годам. Затем с синтезированных логов были сняты интенсивности и сопоставлены с оригинальной интенсивностью (рис. 4.1-4.3). Очевидно, что они практически совпадают. Для сравнения так же были проведены аналогичные процедуры и для моделей №№1-2 (рис. 4.4-4.5).
Эталонная и аппроксимированные по модели №2 неоднородности потока входных заданий Очевидно, что модели используют стационарные потоки: они не учитывают колебания интенсивности в течение дня, а всплески и падения являются результатом погрешности синтеза.
Также на рисунке 4.6 была оценена интенсивность «зацикленного лога» (см. подраздел 2.4). Совпадение позволяет нам говорить о довольно точной передаче неоднородности в продолженных детерминированных логах.
С целью валидации методов аппроксимации поступим следующим образом: возьмем стороннюю разработку, которая создает нагрузку, определяемую интересующим нас законом распределения, а затем по выходным данным сторонней модели восстановим саму модель.
В качестве первого примера возьмем модели из работ [98, 99, 145]. В рамках этих работ было предложено две модели: (в терминологии самой этой работы) оригинальная (в значение «первая», "original") и новая. Рассмотрим их обе. Первая дает аппроксимацию длин заданий распределением я(2) 5 вторая — я(з) . Они обе полагают простейший (стационарный пуассоновский) входящий поток заданий. В модели ширины заданий варьируются от 1 до 128. Ограничимся рассмотрением только степени двойки.
Начнем с распределения я(2) (табл. 4.6). Сторонние модели будем называть эталонными. Очевидно, что в некоторых случаях в аппроксимации переставлены ветви распределения. Это не изменяет результат, но для удобства восприятия в таблице приведены вероятности всех веток, несмотря на то, что последняя всегда является излишней.
В таблице 4.7 приведены аналогичные расчеты для новой модели с я(з) . Некоторые ветви снова переставлены, но очевидно, что в обоих случаях аппроксимация довольно точно передает закон распределения.
Теперь проведем валидацию аппроксимации яг(2) . Для этого воспользуемся программной разработкой из [84, 122, 123, 146]. В этих разработках используется гиперэрланговское распределение общего порядка, которое является частным случаем гиперэрланговского распределения, которое в свою очередь является частным случаем гипер-гамма-распределения. Поэтому можно использовать гипер-гамма-распределение для аппроксимации гиперэрланговского распределения общего порядка.
Валидация стохастической аппроксимации интервалов между приходами заданий
В данном подразделе будет рассмотрен вопрос, насколько адекватно использование стратегий при различной нагруженности. Для моделирования мы будем использовать детерминированную модель, а в качестве примера — пример из подразделов 5.2 и 5.6. Исследуемым параметром будем среднее время ожидания результата, так как именно является самым важным для пользователей системы. Стратегии Rotate, MaxProd и FreeExec не будут рассмотрены из-за низкого качества.
Оригинальный пример имеет нагруженность практически равную 70%. Будем варьировать нагруженность системы, умножаю длину всех заданий на некоторый коэффициент. Результаты представлены нарис. 5.24-5.25.
Очевидно, что при нагруженности менее 55% использование стратегий нерационально и лишь увеличивает время ожидания результата: очередь кластеров не успевает сформироваться, поэтому эвристики передают задания первым в списке (см. табл. 5.2,5.9) кластерам, которые имеют низкую производительность.
На основе вышеизложенного примера можно сформулировать инженерные методики для конечного пользователя. На рис. 5.27 и 5.28 представлена методика моделирования кластерных и Грид-систем, соответственно, а на рис. 5.29 выбор подходящих стратегий для Грид-системы.
В отличие от классических блок-схем, на рисунках присутствуют пунктирные стрелки. Они обозначают переход, который трудно алгоритмизировать: направление выбирается на основе текущей ситуации. Также присутствуют синие стрелки, которые описывают направление упрощенного перехода в случае повторного моделирования.
Порядок следования действий в методиках несколько отличается от примера, но это касается лишь пунктов, порядок выполнения которых можно изменить.
Как можно видеть, в результате работы могут быть выявлены подозрения аномальности входных данных. Под аномальностью понимаются в том числе: 1) Неправильное измерение показателей нагрузки; 2) Зависимость входного потока от внутреннего состояния системы (например, случай NASA iPSC); 3) Серьезное изменение интенсивности входного потока, не подпадающее под цикличность (например, у LPC EGEE полностью отсутствуют задания в течение более ем месяца); 4) Серьезное изменение характеристик входящих заданий.
Методика определения подходящей стратегии может быть изменена для нахождения любого интересующего нас параметра Грид-системы и/или отдельного кластера, который всегда может быть рассмотрен как Грид-система из одного элемента (поэтому методика моделирования кластера является по сути излишней, но приведена для полноты картины). Осуществляем детерминированное моделирование кластера
Методика выбора стратегии для распределения заданий в Грид-системе В качестве критерия качества нами предлагается среднее время ожидания результата, так как именно оно показывает, через какое время (с момента подачи запроса) в среднем будет получен результата. В конкретной ситуации возможна иная картина, например, приоритеты выполнения заданий могут оказаться разными.
Нами везде было выполнено два вида моделирования: детерминированное и стохастическое. Согласование этих результатов говорит нам о высокой вероятности правильности результата, а несоотвествие — о возможности аномальности данных либо некачественности аппроксимации. Пользователь может отказаться от одной из этих моделей на свой страх и риск.
Разработанные средства рассчитаны на пользователей, занимающихся проектированием и модификаций вычислительных кластерных и Грид-систем для определения параметров распределения заданий и показателей обслуживания.
Предложенные средства могут быть внедрены не только в сферы деятельности, связанные с вычислительными системами, но в сферы, связанные с различными разделениями любой нагрузки, например, между отделами организации, работниками call-центра и т.д.
Разработанные модели и методы были реализованы в виде комплекса программных средств DetBrocker+StochBrocker, а также отдельного средства StochlmiG для проведения лабораторных, семестровых и курсовых работ.
Программное средство StochlmiG внедрено в учебный процесс на кафедре «ЭВМ и С» в рамках дисциплин «Вычислительные системы и сетевые технологии» на замену ранее разработанному для этих целей «GridModel» и потенциально может быть внедрено в курсы «Отказоустойчивые системы» и «Надежность и эксплуатация средств ВТ», в которые было внедрено побочно разработанное средство «NetSys». Программные средства «DetBrocker+StochBrocker» внедрены в учебный процесс при моделировании работы кафедрального кластера и выполнении дипломных работ.
![Рациональное управление системой психологической помощи на основе медицинского мониторинга и организации психопрофилактического процесса [Электронный ресурс]](/i/i/4409/168295.png "Рациональное управление системой психологической помощи на основе медицинского мониторинга и организации психопрофилактического процесса [Электронный ресурс] Склярова Татьяна Петровна")
