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

Поэтому задача повышения скорости работысовременных РВК за счёт разработки новых методологий балансировкинагрузки является актуальной.Наоснованиианализасуществующихметодовбалансировкивычислительной нагрузкой выявлена необходимость в создании новогометода балансировки нагрузки в РВК, который позволит избавиться отнекоторыхсущественныхограниченийсуществующихметодов.Такбольшинство из них реагирует только на уже возникшую перегрузку, чтоприводитквозникновениюдисбалансавычислительнойнагрузки.Прогностические стратегии лишены этого недостатка.Большинство методов прогнозирования нагрузки, разработанные дляISDN сетей, являются устаревшими и не могут давать точных прогнозныхзначений в современных РВК и компьютерных сетях следующего поколения(NGN).

Основной недостаток рассмотренных методов заключается в том, чтобольшинствоизнихнеучитываютсвойстванестационарностиисамоподобия сетевого трафика и узловой нагрузки. Этот факт определяетнеобходимость разработки методов прогнозирования сетевой и узловойнагрузки для современных РВК, которые учитывают свойства самоподобиясетевого трафика и узловой нагрузки.49Глава 2. РАЗРАБОТКА МЕТОДА БАЛАНСИРОВКИВЫЧИСЛИТЕЛЬНОЙ НАГРУЗКИ НА ОСНОВЕПРОГНОЗНЫХ МОДЕЛЕЙВданнойглавепредлагаетсяметодикапрогнозированиявычислительной нагрузкой гетерогенного РВК, основанной на методеквазилинеаризациидляуправлениявозможнымиперегрузкамивраспределённом комплексе.Как уже неоднократно говорилось, в настоящее время в Сети находитсягромадное количество практически ненагруженных компьютеров, основноеназначение которых заключается в наборе текстов и заполнении электронныхтаблиц. В то же время, имеется достаточный набор задач, для решениякоторых необходимы существенные вычислительные ресурсы, которые невсегда доступны работающим над этими задачами исследователям.

Дляиспользованиянезагруженныхвычислительныхмощностейсоздаютсяраспределенные вычислительные комплексы, состоящие из того, что есть вналичии. (Обычно это компьютеры, основанные на различных аппаратныхплатформах, различной вычислительной мощности – от тяжелых настольныхигровых систем до планшетов, и даже, до смартфонов – и с различнымиоперационными системами.) В этом случае приходится иметь дело сгетерогеннымираспределеннымивычислительнымикомплексами[3].Попытки решать более или менее серьезные задачи с использованиемгетерогенных систем такого вида приводит к необходимости балансировкипотоками задач, раздаваемых появляющимся в РВК свободным ресурсам, дляобеспечения, по возможности, равномерного распределения нагрузкиотдельных узлов комплекса [72].

Результаты данной главы обобщены вработах [106,110].502.1. Постановка задачи балансировки узловой нагрузкиВ общем случае задача балансировки нагрузки в системе сводится кобеспечению равномерной готовностиданных и, по возможности,минимизации количества транзакций между узлами вычислительногокомплекса [110].Способыдостиженияпоставленнойцелиобычносвязанысперераспределением потоков заданий. В [72] рассмотрены наиболееперспективные из них и даны некоторые рекомендации.Из анализа решений, приведенных в [72], следует, что для успешногорешениязадачибалансировкинагрузкинеобходимадинамическаябалансировка, которая заключается в динамическом распределении нагрузкина узлы РВК в процессе функционирования.

Динамическая балансировкаособенно актуальна, например, в задачах математического моделирования,когда каждая итерация требует различных ресурсов.Все рассмотренные [72] методы балансировки нагрузки в гетерогенныхРВК обладают одним существенным недостатком. В них распределениезаданий производится либо по априорным данным о состоянии узлов сети(статические методы), либо по уровню загрузки узла сети (динамическиеметоды). В последних методах для прогнозирования текущей загрузки узловсети применяются корреляционные методы, в частности, фильтр Винера [66].Подход, основанный на использовании динамической модели загрузкиузлов, показан на рисунке 2.1.Понятно, что по сути явлений в узле РВК динамическая модельзагрузки должна быть нелинейной, и хуже того, нестационарной.

Стоит,однако, заметить, что при достаточно большом количестве узлов сети, и придостаточно большом количестве процессов в каждом узле, можнопредположить, что загрузка узла может быть представлена нелинейнойкусочно-стационарной моделью. Под кусочной стационарностью здесь51понимается модель, выходная переменная которой является стационарной нанекоторых отрезках времени эксплуатации. Кроме того, есть все основанияпредполагать, что процессы, выполняемые в отдельных узлах сети, являютсянекоррелированными [72].Рисунок 2.1 — Подход, основанный на использовании динамических моделейзагрузки узлов [110]Что дополнительно осложняет решение задачи предсказания нагрузкиузла РВК, так это недостаточность (а, чаще всего, отсутствие) данных опараметрах модели, описывающих эту загрузку.В данной работе для решения задач идентификации модели и оценкизагрузки узлов сети предлагается использовать метод квазилинеаризации,предложенный в свое время Беллманом и Калабой [73,74,75].522.2.

Применение метода квазилинеаризации для оценкизагрузки узлаМетод квазилинеаризации (квазиньютоновский метод) является однимиз наиболее часто применяемых на практике методов идентификациидинамических нелинейных объектов. На сегодняшний момент метод,разработанный Беллманом и Калабой, был обобщён на ряд задач. Методквазилинеаризации представляет собой итерационный процесс решениянелинейной n-го порядка последовательности линейных дифференциальныхуравнений.Метод преобразования нелинейной задачи в линейную позволяетпроизвести идентификацию и оценивание параметров состояния системы,значения которых представлены в виде векторов параметров и векторасостояния системы.

При этом, часть компонентов вектора параметров ивектора состояния может отсутствовать или же не поддаваться полностьюизмерению. Это особенно важно для задачи предсказания загрузки узловРВК, так как здесь параметры модели обычно также неизвестны.Рассмотрим модель загрузки узла РВК на интервале [t1,t2] в виденелинейной системы, описываемой уравнением [106]x (t )  f [ x(t ), u(t ), q] ,где(2.1)x(t ) – вектор состояния размерности n; для определенности будемсчитать, что наблюдаемой величиной – загрузкой узла РВКявляется первая компонента вектора x ,u(t ) – вектор входных воздействий размерности m; под входнымивоздействиями модели понимаются внутренние задачи,выполняемые узлом в данный момент времени,q– вектор параметров системы размерности k,f– гладкая вектор-функция размерности n.Как было показано ранее [106], модель (2.1) рассматривается внепрерывном времени, так как, хотя компьютер и является цифровым53устройством (то есть, по определению, дискретным), элементарные квантывремени компьютера настолько малы (менее 1 нс) по сравнению синтервалами принятия решений о распределении нагрузки между узлами (неменее 10 мс).Будем считать, что векторы u(t ) и x(t ) могут быть измерены, причемu(t ) полностью измерим, а x(t ) может измеряться частично (некоторыекомпоненты в некоторые моменты времени).

Вид компонент вектор-функцииfпредполагается известным, причем из практических соображенийкомпоненты этой функции удобно рассматривать в виде полиномов не вышетретьего порядка [76]. Компоненты вектора q неизвестны и не изменяются вовремени, то есть,q  0 .(2.2)Обозначим через t k текущий момент времени. Так как наша задачазаключается в нахождении прогнозных значений загрузки узла РВК x1 (tk 1 ) ,а измерениям поддается та же величина в предыдущие моменты времениx1 (ti ), i  k , при том, что вектор параметров q нам также неизвестен, товводим новый вектор [106] x1 (t )    x n (t ) (t )  . q1    q k (2.3)Уравнение динамики вектора  (t ) с учетом соотношения (2.2) имеет вид: (t )  (  (t ), u(t )) ,где(2.4)54 f1 (  (t ), u(t ))  f n (  (t ), u(t )).00( 2.5)2.3.

Нахождение прогнозных оценок загрузки узла РВККак было показано ранее [106], метод квазилинеаризации основан нанахождении линеаризованного приближения относительно предыдущейитерации (собственно, поэтому метод и называется квазилинеаризация). Еслинайдена N-я итерация оценки нового вектора состояния (3) ˆ N ( t ) (t ) , то,раскладывая уравнение (2.4) в степенной ряд относительно найденногоприближения ˆ N (t ) и оставляя только члены первого порядка малости,получаем следующее (N+1)-е приближение оценки искомого вектора:ˆ N 1 (t )  ˆ N (t ) ˆ N 1 (t )  где:ˆ  ˆ  xˆ,q ˆ1  x 1ˆ2ˆ  x  x1 ˆ n x1ˆ1x 2ˆ2x 2ˆnx 2ˆ1 x n ˆ2x n  , ˆnx n ˆ  ( t )  ( ˆ N 1 (t )  ˆ N (t )) , (2.6)N (t )ˆ1  q 1ˆ2ˆ  q  q1 ˆ n q1ˆ1q2ˆ2q2ˆnq2ˆ1 qk ˆ2qk  . ˆnqk 55Для получения менее громоздких формул в обозначениях к формуле(2.6) опущен аргумент времени для переменных, однако, надо помнить, чтовсе указанные элементы являются функциями времени [106].Уравнение (2.6) линейно относительно ˆ N 1 (t ) и, следовательно,может быть переписано в следующем линейном виде:ˆ N 1 (t )  Aˆ N (t ) ˆ N 1 (t )  VˆN 1 , (t )(2.7)где:ˆAˆ N (t )   ( t )  ˆˆ, VˆN (t )  N (t ) ( t )  N ( t )ˆ  ( t )  ˆˆ N (t )  Aˆ N (t ) ˆ N .(t )N (t )Уравнение (2.7) является линейным и нестационарным относительнопеременной ˆ N 1 (t ) .