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

В настоящее время происходит интенсивное развитие локализации обработки данных с использованием краевых серверов (edge servers) [1 , 2] , пользовательских устройств или «умных» датчиков (end devices, user devices), а также устройств, составляющих самоорганизующиеся сети различного назначения и специфики (MONET, VANET, FANET) [3 –5] .

Такой подход обеспечивает снижение длительности обработки данных и делает возможными реализацию технологии дополненной реальности, позволяет производить управление объектами в режиме реального времени и существенно снижает нагрузку на сетевую инфраструктуру. Однако при этом формируется общая проблема управления вычислительными процессами, которые реализуются на ресурсно-ограниченных устройствах, составляющих географически распределенную гетерогенную в общем случае вычислительную среду(ВС) [6] .

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

К настоящему времени сложились два основных направления в планировании вычислений в рассматриваемом классе ВС:

• (1 )    простые эвристики (жадный подход) [7 , 8] ;

• (2)    метаэвристики [9 –11] .

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

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

Также интерес представляют работы [13] , где предложена многокритериальная модификация алгоритма медоеда, и [14] , где предложен метод гибридизации использования простых эвристик.

Одним из известных способов повышения эффективности метаэвристик является, в рамках эволюционного подхода, интеграция различных эволюционных принципов, например, ламарковской и дарвиновской эволюций, или дарвинской и эволюции Болдуина. Такой подход сформировал отдельное направление метаэвристических алгоритмов — так называемые меметические алгоритмы, которые для ряда задач демонстрируют значительное превосходство по скорости сходимости и достигаемой точности, что отражено в ряде публикаций [15 –18] .

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

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

Исследуется ресурсная эффективность основанного на эволюционном подходе Ламарка алгоритма распределения вычислительных ресурсов для несвязанных задач «Bag of Tasks». Задача заключается в распределении ряда вычислительных задач различной вычислительной сложности по заданному количеству устройств с известными ресурсами, учитывающее (1 ) энергозатраты устройств (что критично для автономных ресурсноограниченных узлов, составляющих вычислительную среду),

• (2)    вариативность загруженности узлов.

2.    Модель распределения вычислительных ресурсов

В качестве примерной задачи распределения вычислительных ресурсов рассмотрим следующую:

Заданы:

• ^•    Гетерогенное множество с точки зрения производительности вычислительных устройств количеством M . Поскольку предполагается сценарий информационно несвязанных задач, то будем считать, что накладными расходами на управления в коммуникационной среде можно пренебречь Каждый узел характеризуется производительностью P _i и некоторым средним энергопотреблением на процессорную операцию e i , а также запасом энергии E i _max , который является ограничением для возможных расходов энергии устройства.

• •    Гетерогенное по вычислительной сложности множество задач G = {X}, где X = {x j } — вычислительные сложности, оцененные в миллионах процессорныx операций, количеством N .

• ^•    Переменные являются матрицей A с бинарными значениями, означающими закрепление задач за узлами:

a 11

a 1 N

A =

a M 1

a MN

где

a ^ij = {о,

если задача j расположена на узле i, в противном случае

Ограничения приняты следующие:

• ^•    Время выполнения пакета задач — T .

• ^•    Ограничение на загруженность каждого узла, когда загруженность узла не может превышать 1:

T < ¹

где T i — время занятости i-го узла.

Vi,

• ^•    Возможный максимальный расход электроэнергии узла:

E i i max Vi,

где

N

E i = e i

j =1

a ij x j

Критериями распределения вычислительных ресурсов являются энергозатраты системы и выравнивание вычислительной нагрузки:

M

T k

1 ^M

T → min

_M i → mn

∀k ⩽ M

M

Ei → min i=1

Сформируем обобщенный критерий с учетом нормализации критериев

(1) и (2) :

min max ^⃓ T _k A k⩽M

M

1 ∑︂T Mj j = 1

M ∑︂_{E j} j =1

MN

e j

x i

3.    Алгоритм на основе принципа эволюции Ламарка

Рассмотрим основные этапы генетического алгоритма, реализующего дарвиновскую эволюцию [20 , 21] .

• ^•    Инициализация: создание начальной популяции особей (хромосом) случайным образом.

• ^•    Оценка пригодности (Fitness Evaluation): расчет значения целевой функции для каждой особи в популяции.

• ^•    Селекция (Selection): выбор наиболее приспособленных особей для последующего размножения. Используются методы, такие как рулеточный отбор, турнирный отбор или ранжированный отбор.

• ^•    Скрещивание (Crossover / Recombination): объединение генетического материала (частей хромосом) родительских особей для формирования потомства.

• ^•    Мутация (Mutation): случайное изменение небольшого числа генов у особей, чтобы предотвратить преждевременную остановку и поддерживать разнообразие популяции.

• ^•    Создание нового поколения: замена старой популяции новыми особями (смесью старых и вновь созданных особей).

• ^•    Проверка условия останова (если не достигнуто, переход к этапу 2).

• ^•    Возврат результата.

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

Ниже приведены основные шаги оптимизации с применением Ламар-ковских принципов эволюции [22] :

• ^•    Инициализация населения (Initialization): Создание начальной популяции случайных особей (хромосом).

• ^•    Местная оптимизация (Local Search): Каждая особь временно улучшает себя с помощью какого-то локального поискового механизма (например, градиентного спуска, метода ближайшего соседа и т.д.).

• ^•    Оценка пригодности (Evaluation): расчёт функции пригодности – fitness function – для каждой особи.

• ^•    Передача улучшений (Inheritance of Acquired Traits):Улучшенные особи остаются неизменёнными и участвуют в следующем этапе отбора и воспроизведения.

• ^•    Блок стандартных генетических операторов – Standard GA Operators:

• ^•    Селекция (Selection): лучше приспособленные особи получают больший шанс стать родителями следующего поколения.

• ^•    Кроссовер (Crossover): комбинирование генетического материала родителей для создания потомства.

• ^•    Мутация (Mutation): случайное изменение элементов хромосомы.

• ^•    Новое поколение (New Generation):Новое поколение формируется из улучшившихся особей предыдущего этапа и их потомков. Старая популяция замещается новым набором особей.

• ^•    Проверка условия останова (Stopping Criterion).

• ^•    Возврат результата.

Далее, при построении процедуры локального поиска, обратимся к известным подходам, описанным в [22]. Рассмотренные подходы ранее использовались при планировании грид-вычислений.

Локальный поиск на основе перемещений (Move-based local search): окрестность решения определяется перемещением задачи с одного ресурса на другой. Таким образом, два решения являются соседними, если они отличаются только в одной позиции их вектора назначений задача-ресурс (vector of assignments task-resource).

При этом возможны следующие варианты перемещений:

• ^•    Local Move (LM) перемещает случайно выбранную задачу с её ресурса на другой случайно выбранный ресурс;

• ^•    Steepest Local Move (SLM) перемещает случайно выбранную задачу на ресурс, обеспечивающий наибольшее улучшение критериев оптимизации;

• ^•    Local MCT Move (LMCTM) основан на эвристике MCT ( Minimum Completion Time ). В LMCTM задача перемещается на ресурс, обеспечивающий наименьшее время завершения среди всех ресурсов;

• ^•    Local Minimum Flowtime Move (LMFTM) перемещает задачу, которая обеспечивает наибольшее сокращение времени потока.

В данном исследовании использовалась самая простая эвристика, а именно Local Move:

• ^•    выбирается случайная задача;

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

• ^•    если это решение дает выигрыш функции пригодности, то вносится изменение в популяцию.

4.    Экспериментальное исследование ресурсной эффективности применения эволюционных принципов Ламарка

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

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

В следующем разделе статьи приводятся экспериментальные исследования эволюционного алгоритма Ламарка в сравнении с известным генетическим алгоритмом NSGA-II, широко применяемым для решения задач распределения ВР по нескольким критериям.

Для оценки ресурсной эффективности применения эволюционных принципов Ламарка были проведены расчеты для следующих комбинаций входных параметров: 100 задач – 10 узлов, 100 задач – 15 узлов, 250 задач – 15 узлов, 250 задач – 20 узлов, 500 задач – 20 узлов, 500 задач – 25 узлов. Вычислительная сложность задач формировалась случайным образом в интервале [500 , 5000] млн. процессорных операций, равно как и производительность узлов формировалась случайным образом в интервале [500 , 5000] млн. процессорных операций/с использованием равномерного закона распределения (см. Приложение). Ниже приведены наиболее значимые результаты, характеризующие эффект применения принципов ламарковской эволюции.

На рисунке 1 видно, что при заданных параметрах распределения

Рисунок 1. 100 задач, 10 узлов

100 ВЗ по 10 узлам добавление эволюционных принципов Ламарка не оказывает положительного эффекта на ресурсную эффективность планирования. Более того, дополнительные циклы локальных улучшений увеличивают ресурсную стоимость вычислений на фоне NSGA-II.

На рисунке 2 видно, как при увеличении размерности задачи распределения ВР появилась область количества итераций, где использование принципов Ламарка оправдано (от 7000 вызовов фитнес-функции).

При дальнейшем увеличении размерности задачи распределения ВР получаем схожий результат экспериментальных испытаний (рисунки 3 –5) : имеется некоторое пороговое значение количества вызовов фитнес-функций, после которого использование принципов Ламарка целесообразно, при этом значение вызовов фитнес-функций находится в интервале [5000 , 8000] (с учетом доверительных интервалов).

Таким образом, на выбранных экспериментальных данных проведенные эксперименты позволяют сделать следующие выводы: целесообразность применения эволюционных принципов Ламарка с точки зрения ресурсной стоимости решения задач планирования/распределения ВР зависит от размерности решаемой задачи. На рисунке 1 видно, что на задаче относительно малой размерности целесообразность сомнительна, скорость сходимости алгоритма с использованием эволюции Ламарка совпадает со

Рисунок 2. 250 задач, 15 узлов

Рисунок 3. 250 задач, 20 узлов скоростью сходимости генетического алгоритма NSGA-II, и не обнаружено интервалов ресурсного бюджета, на которых бы ламарковская эволюция позволила получать более точные решения. Однако, с увеличением

Рисунок 4. 500 задач, 25 узлов

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

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

5.    Заключение

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

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

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

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