ALGORITHM FOR LOAD BALANCING IN A HETEROGENEOUS COMPUTING SYSTEM ENVIRONMENT

Гетерогенная среда вычислительной системы включает в себя совокупность технических устройств (компьютеров, вычислительных кластеров, микрокомпьютеров), которые по своим характеристикам похожи на GRID-системы:

1. Динамические свойства системной конфигурации.

2. Распределенность элементов в вычислительной системе.

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

4. Как правило, решаемых в вычислительной системе задач достаточно много, данный процесс не представляется возможным чётко контролировать

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

В последнем случае информация становится полноценным ресурсом гетерогенной среды вычислительной системы

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

Цель исследования – представить алгоритм балансировки нагрузки в гетерогенной среде вычислительной системы.

Задачи исследования:

1. Привести виды балансировки нагрузки в гетерогенной среде вычислительной системы.

2. Отразить методы балансировки нагрузки в гетерогенной среде вычислительной системы.

3. Систематизировать достоинства и недостатки существующих методов балансировки нагрузки в гетерогенной среде вычислительной системы.

4. Представить результаты разработки алгоритма балансировки нагрузки в гетерогенной среде вычислительной системы на основе платформы "DIET".

Объект исследования – гетерогенная среда вычислительной системы.

Предмет исследования – балансировка нагрузки в гетерогенной среде вычислительной системы.

Научная новизна исследования:

1. Систематизация достоинств и недостатков существующих методов балансировки нагрузки в гетерогенной среде вычислительной системы.

2. Разработка алгоритма балансировки нагрузки в гетерогенной среде вычислительной системы на основе платформы "DIET", сравнительный анализ платформы DIET с другими аналогичными решениями, выделение ограничений алгоритма и возможных сценариев его применения.

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

Для того чтобы сформировать гетерогенную среду вычислительной системы, целесообразно найти эффективный метод к решению задачи. В данном исследовании рассматривается одна из значимых задач вычислительного комплекса – балансировка нагрузки в гетерогенной среде. В современных условиях имеется разнообразие подходов к балансировке нагрузки в гетерогенной среде вычислительного комплекса. Ключевые виды балансировки нагрузки в вычислительном комплексе представлены на рисунке 1.

Рисунок 1 - Ключевые виды балансировки нагрузки в вычислительном комплексе

Примечание: источник [6]

DOI:10.60797/IRJ.2025.155.67.1

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

Рисунок 2 - Пример централизованной схемы работы вычислительного комплекса

Примечание: цель – минимизация нагрузки на вычислительную систему; источник [7]

DOI:10.60797/IRJ.2025.155.67.2

Рисунок 3 - Пример централизованной схемы работы вычислительного комплекса (циклический алгоритм)

Примечание: источник [7]

DOI:10.60797/IRJ.2025.155.67.3

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

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

Для гетерогенной среды вычислительного комплекса зачастую в качестве методов используются зондирование, модель переговоров и реализация задач кластеризации. В контексте зондирования имеется несколько стратегий, применимых в гетерогенной среде вычислительного комплекса: жадная стратегия, предельное значение и стратегия кратчайшего пути. Жадная стратегия – это подтип пороговой стратегии, который в ходе зондирования узлов применяет циклический алгоритм. При распределенной схеме работы вычислительного комплекса в соответствии с жадной стратегией порог – нагрузка владельца системы, максимальный объём пользовательских оценок – 3 (см. рис. 4).

Рисунок 4 - Пример распределенной схемы работы вычислительного комплекса в соответствии с жадной стратегией

Примечание: источник [7]

DOI:10.60797/IRJ.2025.155.67.4

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

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

Пример практического использования распределенной схемы в вычислительном комплексе на базе модели переговоров представлен на рисунке 5. Инициатор заявки – исполнитель.

Рисунок 5 - Пример практического использования распределенной схемы в вычислительном комплексе на базе модели переговоров

Примечание: источник [7]

DOI:10.60797/IRJ.2025.155.67.5

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

Помимо обозначенных выше методов балансировки нагрузки в гетерогенной среде вычислительном комплексе, можно применить кластеризацию узлов, которые обладают похожими параметрами, например, пропускной способностью, объёмом и частотой работы ресурсов процессора, дисковым пространством. Подобная кластеризация узлов может быть применена в целях отображения решаемых задач по группам в разрезе узлов, которые будут их выполнять. Метод кластеризации наиболее эффективно работает при смешанном подходе к балансировке нагрузки в гетерогенной среде.

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

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

Одной из платформ проектирования вычислительных комплексов выступает "DIET". Её функциональное предназначение – организация вычислительной системы в условиях гетерогенной среды, распределения элементов в системе. Архитектура платформы "DIET" проиллюстрирована на рисунке 6.

Компоненты архитектуры:

1. Client – мобильное приложение клиента, предназначенное для осуществления конкретных задач.

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

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

4. SeD – серверная служба, которая работает на конечных узлах в вычислительном комплексе, нужна, для того, чтобы получить данные о гетерогенной среде, объёме ресурсов, степени загруженности на конкретный момент времени.

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

Рисунок 6 - Архитектура платформы «DIET»

Примечание: составлено на основании [8], [9], [10]

DOI:10.60797/IRJ.2025.155.67.8

Преимущества платформы «DIET»:

- достаточно простой алгоритм автоматического подбора ресурсов: технических устройств, баз данных, оперативной памяти;

- осуществление наблюдения за текущим состоянием элементов вычислительного комплекса;

- можно скорректировать работу планировщика при помощи добавления необходимых модульных блоков;

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

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

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

Аналогичными платформенными решениями являются:

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

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

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

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

Алгоритм балансировки нагрузки в гетерогенной среде вычислительной системы на основе платформы «DIET» подразумевает последовательное осуществление перечисленных ниже стадий:

1. Построение вычислительной системы.

Сформирована мультипроцессорная вычислительная система с применением архитектуры и функциональных блоков платформы. Свойства мультипроцессорной вычислительной системы – ресурсы взаимоисключения, число процессов, используемая политика планирования решаемых задач. Архитектура платформы сформирована на базе дискретно-событийного языка программирования.

2. Выявление асинхронных событий вычислительной системы.

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

3. Практическое применение функциональных блоков платформы:

- отметка времени в процессе динамического изменения нагрузки на узлы;

- выявление общей продолжительности решения одной задачи;

- определение атрибутивных характеристик узлов;

- передача информации управляющим агентам;

- обработка информации управляющими агентами;

- получение клиентом ответа от управляющего агента.

Приведенная модель проиллюстрирована на рисунке 7.

Рисунок 7 - Модель балансировки нагрузки в гетерогенной среде мультипроцессорной вычислительной системы на основе платформы «DIET»

DOI:10.60797/IRJ.2025.155.67.9

В соответствии с рисунком 7 модель балансировки нагрузки в гетерогенной среде мультипроцессорной вычислительной системы на основе платформы "DIET" даёт возможность сократить эффект чрезмерной осцилляции на фоне избыточного применения буфера импорта данных внутри кластера узлов.

Несмотря на достоинства алгоритма балансировки нагрузки в гетерогенной среде мультипроцессорной вычислительной системы на основе платформы "DIET", присутствуют некоторые ограничения в его использовании:

1. Каждый рабочий сервер должен обладать одинаковым перечнем и объёмом ресурсов.

2. Пользовательские запросы – исключительно независимые и атомарные.

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

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

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

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

3. Исходя из достоинств и недостатков существующих методов балансировки нагрузки в гетерогенной среде вычислительной системы, присутствует потребность в разработке алгоритма балансировки нагрузки в гетерогенной среде вычислительной системы на основе платформы "DIET".

4. Алгоритм балансировки нагрузки в гетерогенной среде вычислительной системы на основе платформы "DIET" подразумевает последовательное осуществление перечисленных ниже стадий:

- построение вычислительной системы;

- выявление асинхронных событий вычислительной системы;

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

- выявление общей продолжительности решения одной задачи;

- определение атрибутивных характеристик узлов;

- передача информации управляющим агентам;

- обработка информации управляющими агентами;

- получение клиентом ответа от управляющего агента.

5. Модель балансировки нагрузки в гетерогенной среде мультипроцессорной вычислительной системы на основе платформы "DIET" даёт возможность сократить эффект чрезмерной осцилляции на фоне избыточного применения буфера импорта данных внутри кластера узлов.

6. Несмотря на достоинства алгоритма балансировки нагрузки в гетерогенной среде мультипроцессорной вычислительной системы на основе платформы "DIET", присутствуют некоторые ограничения в его использовании: каждый рабочий сервер должен обладать одинаковым перечнем и объёмом ресурсов; пользовательские запросы – исключительно независимые и атомарные; нет автоматизации планирования ресурсных требований к решению поставленных задач.

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