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

Его решение в форме Коши имеет вид:tˆ N 1 (t )  Y N (t, t0 ) ˆ N 1 (t0 )   YN (t , )VN ( ) d ,(2.8)t0иначе, с учетом обозначений к (2.7),tˆ N ( )d ˆ N 1 (t )  Y N (t , t0 ) ˆ N 1 (t0 )   Y N (t , )t0t  Y N (t , ) Aˆ N ( ) ˆ N ( )d ,(2.9)t0где XN(t,) – фундаментальная матрица уравненияˆ N 1 (t )  Aˆ N (t ) ˆ N ! (t ) .(2.10)Как было показано ранее [106], для оценки прогнозных значенийзагрузки узла РВК x1 (tk 1 ) следует найти вектор ˆ N 1 (t ) размерности n+k,включающий в себя n компонент вектора состояния x(t ) и k компонентоценки вектора параметров модели q .

Для этого необходимо иметь n+kизмерений. Как уже говорилось, измерению поддаются предыдущиезначения первой компоненты вектора x(t ) в t j моменты времени. Тогда56новый вектор состояния наN  1 итерацииˆ N 1 (t0 )удовлетворяетграничному условиюx1 (t j )  Y1, N (t j , t0 ) ˆ N 1 (t0 )  1, N (t j ) , j  1, n  k ,(2.11)гдеtj1, N (t j )   Y1, N (t j , )VN ( ) d , j  1, n  k .(2.12)t0В уравнениях (2.11) и (2.12) Y1, N () представляет собой 1-ую строкуфундаментальной матрицы Y N () . Так как произведено n+k измерений, тоуравнений (2.11) тоже n+k, и они представляют собой полную системулинейных алгебраических уравнений с n+kпеременными. Решение этойсистемы дает n+k компонентов, составляющих вектор ˆ N 1 (t0 ) , последние kкомпоненткоторого представляют собой оценку искомого векторапараметров q .

По найденному значению ˆ N 1 (t0 ) и фундаментальнойматрице Y1, N () легко ищется прогнозное значение загрузки узла [106]:x1, N (tk 1 )  1 0  0 ˆ N 1 (tk 1 ),t k 1ˆ N ( )d ˆ N 1 (t k 1 )  Y N (t k 1 , t0 ) ˆ N 1 (t0 )   Y N (t k 1 , )t0t k 1  Y N (t k 1 , ) Aˆ N ( ) ˆ N ( )d ,( 2.13)t0Метод квазилинеаризации отличается квадратичной сходимостью [4],если только он вообще сходится. Для обеспечения сходимости алгоритманеобходимо, чтобы начальное приближение было не очень далеко отистинного значения параметров. Для получения адекватного начальногоприближенияимеетсмыслиспользоватьметодыоснованные на фрактальных свойствах трафика [66,76].прогнозирования,57Выводы по 2 главеСовременныебалансировкиисследованиязаданийвузлахвобластиРВКразработкипоказываютметодовограниченностьобщепринятых подходов для решения этой задачи. В статье показано, чтоиспользованиепрогностическихмоделей,основанныхнаметодеквазилинеаризации, позволяет повысить скорость процессов балансировкипотоковвРВК.Таккакдляобеспечениясходимостиалгоритмаквазилинеаризации необходимо иметь достаточно хорошее начальноеприближение, для его получения предлагается использовать известныеметоды прогнозирования, основанные на фрактальных свойствах интернеттрафика.

Шаг дискретизации, глубина прогноза, размер интервала [t1,t2]определяются особенностями среды grid и набором сетевого оборудования.58Глава 3. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕМЕТОДА БАЛАНСИРОВКИ НАГРУЗКИ ДЛЯРАСПРЕДЕЛЁННЫХ ВЫЧИСЛИТЕЛЬНЫХ КОМПЛЕКСОВДаннаяглавадиссертационногоисследованияпосвященаэкспериментальной проверке разработанного метода балансировки нагрузки.Рассматриваетсяимитационнойметодикамоделипроведенияраспределённогоэкспериментакомплекса.ипостроенияРассматриваютсяосновные параметры модели системы, которые должны быть отражены вразработанной имитационной модели, с возможностью их изменения ификсации в ходе работы. Методика эксперимента заключается в проверкепрогностической стратегии балансировки нагрузки, на основе методаквазилинеаризации и сравнения ее с известными методами прогнозирования.Также произведено тестирование программного обеспечения, разработанногона основе предложенного метода балансирования вычислительной нагрузкойдля распределённых вычислительных комплексов с гетерогенной структурой,с целью выявления функциональных особенностей,влияющих навозникновение дисбаланса нагрузки в РВК.С цельюреализации данного эксперимента были поставлены ивыполнены следующие задачи:1.

Разработка имитационной модели РВК.2. Расчёт средней абсолютной ошибки (в процентах) и точностипрогнозирования предложенного метода.3. Расчёт этих величин для других, наиболее часто используемых напрактике методов прогнозирования, и их сравнение.4. Тестированиепредложенногометодабалансировкинагрузки,включающее в себя компоненту прогнозирования и определениявозникновения будущей перегрузки.595. Выявлениеуровняузловогодисбаланса,прииспользованииразработанного метода балансировки и сравнение его с известнымистратегиями.Материалы данной главы были использованы при написании работ[110,114].ВданнойглавеиспользованытакжерезультатыработBenmohammed-Mahieddine [77] и W.

E. Leland и T. J. Ott [78].3.1. Анализ влияния параметров модели напроизводительность распределённого вычислительногокомплексаВ результате проведённого анализа ряда работ [77, 78] выявлено, чтопроизводительность распределённых вычислительных комплексов сильнозависит от параметров конфигурации системы, и наибольший интерес дляизучения представляет методика использования этих параметров дляповышения производительности комплекса. Так в [79] показано, что подборнаилучших параметров вычислительного комплекса позволяет повысить егопропускную способность на 24,5%, а также снизить время отклика системына 28,1%.

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

Отсутствие в модели рядасущественных параметров может привести к неполноте и неадекватностиполученной модели, что в свою очередь может привести к недооценке уровнявозникающей нагрузки и, следовательно, к неточности полученныхрезультатов по определению производительности алгоритма балансировкинагрузки. Адекватная же модель позволяет создавать комплексные рабочиенагрузки, с возможностью модификации и контроля ряда атрибутов. Далеерассмотрим наиболее важные параметры гетерогенного распределённоговычислительного комплекса, которые оказывают существенное влияние наполноту и адекватность модели.К основным таким параметрам относятся [77]: структура файловойсистемы, количество подключённых клиентов, сетевой протокол передачиданных, модель вычислительной нагрузки.Эффект влияния на производительность алгоритмов балансировкинагрузки должен быть оценен для следующих параметров вычислительногокомплекса:1.

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

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

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

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

Сложность получениятакой модели заключается в необходимости формулировки законоввзаимодействия компонентов системы, выявления динамики развитиясистемы и запись их в виде функциональных отношений [80]. В качествевозможной модели, пригодной для описания принципов работы ифункционирования РВК, может использоваться аналитическая модельраспределённой системы в виде её описания, как системы массовогообслуживания.Примоделированииреальногосовременногораспределённого вычислительного комплекса, посредством модели СМО,необходимо определить характер распределения двух основных величин:моментов появления заявок на выходе источника и значений интервалов(длительностей)обслуживанияраспределениямихарактеризующиеузламикомплекса.процессывочередяхОсновнымиявлялисьпуассоновское (или марковское) распределение и распределение Эрланга.Однако, развитие сетей передачи данных (переход к пакетной коммутации) иразработка новых архитектур построения распределённых комплексовпривело к недостаточной точности применяемых ранее моделей на основеСМО.