Оценка влияния системных параметров распределённого вычислительного комплекса на эффективность работы алгоритмов балансировки нагрузки
Рассмотрение вопроса зависимости производительности алгоритмов балансировки вычислительной нагрузки для глобально распределённых вычислительных комплексов, реализующих принцип добровольных вычислений, от основных атрибутов распределённой системы.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | статья |
Язык | русский |
Дата добавления | 07.03.2019 |
Размер файла | 1,5 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru//
Размещено на http://www.allbest.ru//
Оценка влияния системных параметров распределённого вычислительного комплекса на эффективность работы алгоритмов балансировки нагрузки
Алпатов Алексей Николаевич
ассистент
Аннотация
Целью данной статьи является рассмотрение вопроса зависимости производительности алгоритмов балансировки вычислительной нагрузки для глобально распределённых вычислительных комплексов (РВК), реализующих принцип добровольных вычислений, от основных атрибутов распределённой системы. В качестве основных фиксируемых атрибутов рассмотрены структура файловой системы и тип сетевого протокола. Объектом исследования является глобально распределенный вычислительный комплекс, с комплексом диспетчирования загрузки узлов. Предметом исследования являются методы балансировки загрузки узлов РВК, реализующие принцип динамической стратегии балансировки вычислительной нагрузки. В данной статье, методологической основой являются методы фундаментальных и прикладных наук: методы анализа, методы математической статистики, имитационного моделирования. Предложена модель узловой вычислительной нагрузки в виде нелинейной кусочно-стационарной модели. В работе показана методика проведения вычислительного эксперимента по определению эффективности работы алгоритмов балансировки и разработана имитационная модель распределённого комплекса, с возможностью фиксации основных системных параметров вычислительного комплекса, а также произведена оценка их влияния на время отклика системы. Показано, что особое влияние на эффективность работы алгоритмов балансировки нагрузки оказывают такие параметры, такие как структура файловой системы и тип сетевого протокола. Таким образом, показана необходимость учёта таких параметров для обеспечения адекватности разрабатываемой модели распределённого вычислительного комплекса, реализованного по принципу добровольных вычислений.
Ключевые слова: распределённые системы, балансировка нагрузки, добровольные вычисления, имитационное моделирование, Grid Computing, квазилинеаризация, РВК, динамические методы балансировки, расписание выполнения задач, прогноз
алгоритм балансировка вычислительный
Abstract
The purpose of this article is to consider the correlation of the performance of computational load balancing algorithms for globally distributed computing systems implementing the principle of volunteer computing and the basic attributes of a distributed system. As the main considered parameters the author examines file system structure and the type of network protocol. The object of the study is a globally distributed computing system with scheduling nodes loading. The subject of the study are the balancing methods of loading units of the system, implementing the principle of dynamic computational load balancing strategy. In this article, the methodological basis of the article makes methods of fundamental and applied sciences: analysis methods, methods of mathematical statistics, simulation modeling. The author suggests a model of node computational load in form of nonlinear piecewise-stationary model. The paper shows a method of computing experiment to determine the effectiveness of the balancing algorithms. The author develops a simulation model of distributed complex with the possibility of setting the basic system parameters computer system and assess their impact on system response time. It is shown that a particular impact on the efficiency of load balancing algorithms have such parameters as file system structure and the type of network protocol. Thus, the necessity of taking into account these parameters to ensure the adequacy of the developed model of the distributed computing system implemented on the basis of volunteer computing.
Keywords:
quasilinearization, Grid Computing, simulation, volunteer computing, load balancing, distributed systems, DCS, dynamic balancing methods, schedule tasks, forecast
Введение
В результате проведённого анализа ряда публикаций [1,2,3] выявлено, что на производительность алгоритмов балансировки вычислительной нагрузки и, в целом, всей распределённой системы сильное влияние оказывает её конфигурация. В работе [3] автором показано, что подбор правильных параметров распределённого вычислительного комплекса (РВК) позволяет повысить его пропускную способность на 24,5%, а также снизить время отклика системы на 28,1%. Однако основной проблематикой в данном вопросе является то, что большинство современных РВК строится в условиях гетерогенности среды, что приводит к необходимости выбора и последующей фиксации этих параметров на глобальном уровне. Стоит отметить, что в зависимости от целевого назначения вычислительного комплекса и в зависимости от требуемого уровня детализации, набор фиксируемых параметров может разниться. В частности, рассматривая организацию вычислений для локальной многопроцессорной системы, для обеспечения корректного описания модели системы, нас, в первую очередь интересуют соответствующие атрибуты вычислительного задания, такие как их размер, максимальное время ожидания в очереди на обработку, а также время обработки задания. Соответственно, ряд существующих подходов к управлению вычислительной нагрузкой были разработаны с учётом данных атрибутов. Например, одним из возможных вариантов решения задачи балансировки вычислительной нагрузки является её рассмотрение в рамках задачи ортогональной упаковки [5,6]. При данном подходе каждая вычислительная задача представляется прямоугольником, где ширина может быть представлена, например, требуемым вычислительным ресурсом процессора, а высота может быть представлена временем выполнения задачи.
Современный же этап развития вычислительной техники характеризуется повсеместным внедрением распределённых систем, построенных с использованием технологии Grid Computing. Учитывая все недостатки первых систем, а именно невозможность реализации данных систем в гетерогенной среде, I. Foster и C. Kesselman предложили [4] новый подход к организации глобально-распределённых комплексов и систем[5], что позволило решить данную задачу. Данный подход позволил объединить глобально рассредоточенные вычислительные узлы, посредством сети Интернет, в некоторую абстрактную решётку [5], где каждый узел системы выделяется для выполнения конкретного вычислительного задания. Дальнейшее развитие данной технологии привело к созданию и повсеместному развитию концепции добровольных вычислений, что позволило объединить не только крупные вычислительные центры, но и обычные персональные компьютеры пользователей в единую Grid среду. Соответственно, для глобально распределённых вычислительных комплексов, построенных на основе добровольных вычислений при создании её модели, а также организации системы балансировки заданиями, необходимо учитывать ряд дополнительных параметров системы, в частности, модель нагрузки для рабочих мест, характер использования памяти, тип файловой системы и т.д.
Далее, дадим описание разработанной имитационной модели РВК и рассмотрим вопрос оценки степени влияния таких параметров, как структура файловой системы и тип сетевого протокола на эффективность работы алгоритмов балансировки нагрузки.
Разработка имитационной модели распределённого вычислительного комплекса
Как было уже сказано выше, для решения этой задачи необходимо разработать систему, которая обеспечивает возможность проведения необходимых экспериментов, и которая позволит оценить степень влияния параметров распределённой системы на производительность и эффективность работы алгоритмов балансировки. В ходе анализа было выявлено, что для решения данной задачи необходимо было разработать имитационную модель РВК.
Имитационная модель, по сравнению с аналитической, обладает рядом преимуществ. Имитационное моделирование, для нашей задачи, позволяет [8]:
- производить многократное измерение интересующих нас параметров;
- осуществлять полный контроль всех параметров исследуемой системы, с возможностью текущей модификации алгоритма поведения исследуемой системы.
Так как построение имитационной модели сложного комплекса основывается на принципах иерархического многоуровневого моделирования [9], необходимо определить базовую модель, которая будет проста в реализации. Соответственно, выделим следующие модели РВК:
1. Базовая модель - распределённый вычислительный комплекс с гомогенным составом узлов, линий связи.
2. Глобальная модель (3-го уровня) - распределённый вычислительный комплекс с гетерогенным составом узлов, линий связи.
Одним из важнейших параметров, учёт которых необходим в разрабатываемой системе, является модель загрузки вычислительного узла комплекса. В данном эксперименте узловая нагрузка была представлена в виде однородного гомогенного потока событий (распределение Пуассона) и нелинейной кусочно-стационарной модели, описанной в виде уравнения:
где: |
- |
вектор состояния размерности n ; для определенности будем считать, что наблюдаемой величиной - загрузкой узла РВК является первая компонента вектора , |
||
- |
вектор входных воздействий размерности m ; под входными воздействиями модели понимаются внутренние задачи, выполняемые узлом в данный момент времени, |
|||
- |
вектор параметров системы размерности k , |
|||
- |
вектор-функция размерности n . |
|||
Под кусочной стационарностью здесь понимается модель, выходная переменная которой является стационарной на некоторых отрезках времени эксплуатации.
На рисунке 1 показан подход к балансировке нагрузки на основе динамических моделей загрузки узлов [10].
Рисунок 1 --Балансировка нагрузки с использованием динамических моделей загрузки узлов [10]
С целью приближенности к реальным условиям эксплуатации, тестирование разработанного алгоритма производилось на глобальной модели, с различным набором параметров, описанных выше. В качестве основных алгоритмов балансировки нагрузки были выбраны следующие алгоритмы: алгоритм балансировки со случайным распределением задач (англ. randomized load balancing algorithm), циклический алгоритм (англ. Round-Robin), алгоритм наименьшего количества соединений (англ. Least-Connection), прогностический алгоритм на основе метода экспоненциального сглаживания (exponential smoothing) и прогностический алгоритм на основе метода квазилинеаризации.
После описания основных требований к имитационной модели была произведена её разработка. Структура разработанной системы представлена на рисунке 2.
Рисунок 2 -- Функциональная схема разработанной системы
В качестве входных параметров используется готовый набор целевых параметров (модель узловой нагрузки, тип сетевого протокола, структура файловой системы, применяемый алгоритм балансировки и т.д.). Далее, перед каждым запуском системы, происходит анализ входных параметров, с целью выявления необходимости конфигурирования системы под каждый конкретный набор параметров. Если пользователь пытается запустить систему без изменения параметров, например при повторном запуске предыдущей части моделирования, то запуск осуществляется без переконфигурирования системы. Далее, генератор осуществляет генерацию модели с соответствующим набором параметров, после чего происходит запуск модели. После запуска системы имитационного моделирования возможен контроль хода выполнения работы, с помощью логирования основных контролируемых параметров. В результате работы системы происходит сбор требуемых статистических данных и их дальнейшая фильтрация. Фильтрация полученных данных необходима для выявления только существенных для исследования данных. Далее происходит интерпретация полученных отфильтрованных данных. С целью удобства анализа полученных данных, существует возможность их преобразования в удобный к восприятию вид (графики, таблицы).
На рисунке 3 приведены параметры эксперимента исследуемого РВК с различными характеристиками.
Рисунок 3 -- Фиксируемые параметры распределённого вычислительного комплекса
Анализ влияния структуры файловой системы на эффективность работы алгоритмов балансировки
В результате анализа полученных экспериментальных данных было выявлено, что структура файловой системы оказывает существенное влияние на производительность алгоритмов балансировки нагрузки. Так, при загрузке системы, стремящейся к 1, резко (см. рисунок 5) ухудшалась работа системы, построенной на основе бездисковой модели структуры файловой системы. Разработанный прогностический алгоритм на основе метода квазилинеаризации, так же как и метод на основе экспоненциального сглаживания, показали наилучшие результаты (см. рисунок 4 и рисунок 5). Данный эффект можно объяснить тем, что при больших нагрузках, а именно при больших количествах операций ввода/вывода, общий файловый сервер становится «узким» местом всего вычислительного комплекса. Особо остро данный проблема встаёт на тех узлах, на которых используется файл подкачки (англ. paging ).
Рисунок 4 -- Производительность различных алгоритмов при файловой структуре с локальными дисками
Рисунок 5 -- Производительность различных алгоритмов при файловой структуре с общим файловым сервером
Анализ влияния протокола передачи данных
Для оценки влияния выбора коммуникационного протокола, было произведено сравнение двух протоколов передачи данных TCP и UDP. Предполагалось оценить влияние коммуникационного протокола для дисковых и бездисковых рабочих станций. Особое внимание было уделено бездисковым рабочим станциям с общим файловым сервером, так как предполагалось, что при больших нагрузках на систему, происходит большое число обращений к файловому серверу, что может приводить к флуктуациям сетевого трафика.
Результаты эксперимента для протокола TCP приведены на рисунке 6 и рисунке 7. Результаты для бездисковых и систем с локальными дисками с протоколом UDP представлены, соответственно, на рисунке 8 и рисунке 9.
Рисунок 6 -- Производительность алгоритмов для протокола TCP (бездисковые системы)
Рисунок 7 -- Производительность алгоритмов для протокола TCP (локальная структура)
Рисунок 8 -- Производительность алгоритмов для протокола TCP (бездисковые системы)
Рисунок 9 -- Производительность алгоритмов для протокола UDP (локальная структура файловой системы)
Как видно из графиков, уменьшение времени отклика, как для дисковых, так и бездисковых систем произошло при использовании сетевого протокола UDP. Данный факт объясняется тем, что протокол UDP организует передачу пакетов без предварительного установления соединения, что приводит к снижению объёма передаваемых данных. Однако стоит проявлять осторожность при интерпретации полученных результатов. Так, при построении модели не учитывалась внутренняя структура сетей передачи данных, а именно наличие активного сетевого оборудования (коммутаторы, прокси-серверы и т.д.) в её составе и надёжность данного оборудования. Однако полученные результаты могут быть применены для локальных комплексов, таких как университетские вычислительные центры.
Заключение
Полученные в ходе анализа результатов эксперимента данные, позволили отметить важность учёта, при создании адекватной модели современного распределённого вычислительного комплекса, таких параметров как модель вычислительной нагрузки, структура файловой системы комплекса и тип сетевого протокола. Однако, как отмечено в данной работе сетевая составляющая в полной мере не учитывается, что поднимает ряд проблем для дальнейших исследований. Связано это, прежде всего, со сложностью построения адекватной модели, учитывающие все свойства сетевого трафика и промежуточных передающих узлов, между сервером и хостом, а также все возможные варианты передачи пакета данных. Для решения данной задачи, в дальнейшем, планируется рассмотреть древовидную структуру представления grid архитектуры, с целью построения более адекватной модели.
Библиография
1. |
Benmohammed-Mahieddine K. An evaluation of load balancing algorithms for distributed systems : дис. - The University of Leeds, 1991.- p. 197. |
|
2. |
Leland W., Ott T. J. Load-balancing heuristics and process behavior. - ACM, 1986. - Т. 14. - №. 1. - pp. 54-69. |
|
3. |
Zhang F. et al. Performance Improvement of Distributed Systems by Autotuning of the Configuration Parameters //Tsinghua Science & Technology. - 2011. - Т. 16. - №. - pp. 440-448. |
|
4. |
I. Foster and C. Kesselman. The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann, San Francisco, CA, 1998, -p. 748. |
|
5. |
Алпатов Алексей Николаевич Развитие распределенных технологий и систем // ПНиО. 2015. №2 (14) -С.60-66. |
|
6. |
Кузюрин Н. Н., Грушин Д. А., Фомин А. Проблемы двумерной упаковки и задачи оптимизации в распределенных вычислительных системах // Труды ИСП РАН . 2014. №1 С.483-501. |
|
7. |
Ntene N. An algorithmic approach to the 2D oriented strip packing problem: дис. - Department of Logistics, University of Stellenbosch, 2007.-p. 189. |
|
8. |
Бабина О. И. и др. Сравнительный анализ имитационных и аналитических моделей //Сборник докладов Четвертой всероссийской научнопрактической конференции «Имитационное моделирование. Теория и практика. ИММОД-2009».- 2009 -c.73-77. |
|
9. |
Алиев Т. И. Исследование сложных систем на основе комбинированного подхода //Сборник докладов всероссийской научнопрактической конференции «Имитационное моделирование. Теория и практика. ИММОД-2003».-ТОМ I. - С. 50. |
|
10. |
Алпатов А.Н., Михайлов Б.М., Рощин А.В. Методы балансировки и оценки нагрузки узлов распределенной вычислительной системы. Естественные и технические науки. 2016. № 6 (96). -С. 165-170. |
|
11. |
B. Yagoubi and Y. Slimani(2007)” Task Load Balancing Strategy for Grid Computing”, Journal of computer science,ISSN 1546-9239, pp. 186-194 |
|
Размещено на Allbest.ru
...Подобные документы
Исследование структуры типовой вычислительной сети. Модель процесса вскрытия вычислительной сети и взаимосвязь основных его этапов. Конфликт в информационной сфере между субъектом и объектом познания. Описания алгоритмов динамического масштабирования.
дипломная работа [2,9 M], добавлен 21.12.2012Основные особенности эволюционных алгоритмов. Описание алгоритмов селекции, мутации, скрещивания, применяемых для реализации генетических алгоритмов. Вычисление функции приспособленности. Программная реализация. Тестирование и руководство пользователя.
курсовая работа [1,3 M], добавлен 11.03.2014Анализ алгоритмов, оценка параметров алгоритма (эффективности, сложности, правильности). Комплексный анализ эффективности алгоритма на основе комплексной оценки ресурсов формальной системы. Верификация при коллективной разработке программных систем.
презентация [234,9 K], добавлен 22.10.2013Микропроцессорные системы обработки данных. Специальные алгоритмы-планировщики для распределения операторов параллельных алгоритмов по процессорам вычислительной сети. Алгоритм построения и уплотнения нитей. Интерфейс программы, результаты работы.
курсовая работа [1,8 M], добавлен 22.02.2011Трудности использования эволюционных алгоритмов. Построение вычислительных систем, основанных на принципах естественного отбора. Недостатки генетических алгоритмов. Примеры эволюционных алгоритмов. Направления и разделы эволюционного моделирования.
реферат [187,4 K], добавлен 21.01.2014Способы организации вычислительного процесса в системах с несколькими процессорами. Разработка программы на основе алгоритмов мультипроцессорных систем при пакетной обработке задач. Вычисление основных показателей эффективности для каждого алгоритма.
курсовая работа [102,3 K], добавлен 21.06.2013Использование бинарных деревьев для поиска данных. Схемы алгоритмов работы с бинарным деревом. Проектирование алгоритмов и программ. Структура программного комплекса. Язык С# как средство для разработки автоматизированной информационной системы "Адрес".
курсовая работа [914,9 K], добавлен 14.11.2013Изучение особенностей создания алгоритмов вычислительных задач. Визуальное программирование стандартных компонентов среды программирования Delphi. Технология создания компонента Delphi для решения производственной задачи. Выполнение блок-схемы алгоритма.
курсовая работа [638,0 K], добавлен 30.01.2015Нахождение рационального порядка следования запросов для обеспечения максимального критерия эффективности использования компонентов вычислительного процесса в системе. Метод ветвей и границ для максимально быстрого выполнения вычислительного процесса.
курсовая работа [196,3 K], добавлен 23.08.2009Трехмерное моделирование: улучшение алгоритмов рендеринга и просчета трехмерных изображений. Обоснование выбора алгоритмов. Выбор языка программирования и среды разработки. Структура данных и программного комплекса. Системные требования для работы.
курсовая работа [263,8 K], добавлен 24.06.2009Процесс создания автоматизированной системы управления. Требования, предъявляемые к техническому обеспечению вычислительной системы. Разработка общей концепции и алгоритмов работы вычислительной системы. Выбор аппаратных средств локальных сетей.
дипломная работа [7,6 M], добавлен 28.08.2014Положения алгоритмов сжатия изображений. Классы приложений и изображений, критерии сравнения алгоритмов. Проблемы алгоритмов архивации с потерями. Конвейер операций, используемый в алгоритме JPEG. Характеристика фрактального и рекурсивного алгоритмов.
реферат [242,9 K], добавлен 24.04.2015Комплексное исследование истории развития, основных понятий, области применения и особенностей генетических алгоритмов. Анализ преимуществ генетических алгоритмов. Построение генетического алгоритма, позволяющего находить максимум целочисленной функции.
курсовая работа [27,9 K], добавлен 23.07.2011Обзор рекурсивных алгоритмов с позиции теории алгоритмов, теории сложности, с точки зрения практического программирования. Имитация работы цикла с помощью рекурсии. Способы изображения древовидных структур. Синтаксический анализ арифметических выражений.
курсовая работа [432,2 K], добавлен 16.01.2013Создание схем алгоритмов и составление программы на языке Pascal для вычисления значений заданных функций. Сущность и порядок нахождения значения определенного интеграла. Анализ работы подпрограмм. Разработка тестов для проверки правильности алгоритмов.
контрольная работа [831,0 K], добавлен 24.11.2013Использование нестандартных функций и подпрограмм (процедур) для составления алгоритмов вычислений. Программы для вычисления значение корней нелинейного уравнения по методу половинного деления. Составление алгоритма операций над матрицами и интегралами.
курсовая работа [580,0 K], добавлен 23.08.2015Описание сервиса электронного кафе и определение основных требований к системе. Модели вариантов использования, состояний, последовательности, классов, компонентов и развертывания. Описание алгоритмов, реализующих бизнес-логику серверной части.
курсовая работа [3,3 M], добавлен 23.12.2014Проведение четырех основных арифметических операций над целыми числами – подзадача, реализованная в большинстве пользовательских программ. Реализация многоэтапных алгоритмов вычисления. Список макросов, процедур и описание их функциональной нагрузки.
курсовая работа [25,9 K], добавлен 17.05.2013Шифрование - широко используемый криптографический метод сохранения конфиденциальности информации. Описание схемы шифрования и расшифрования. Структура алгоритмов на основе сети Фейстеля. Скриншоты работающей программы. Скорость работы алгоритмов.
курсовая работа [545,2 K], добавлен 29.11.2010Функциональное диагностирование вычислительного устройства (ВУ), требования к нему по производительности, диапазону представления чисел, точности вычислений, сложности реализации и достоверности функционирования. Контроль по модулю ВУ с плавающей точкой.
реферат [1,2 M], добавлен 14.12.2012