Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

MULTI-AGENT ALGORITHM FOR REALLOCATION OF COMPUTATIONAL RESOURCES FOR RESIDUAL PROBLEM SOLVING SCHEME IN GRID

Feoktistov A.G. 1 Kostromin R.O. 1
1 Matrosov Institute for System Dynamics and Control Theory of Siberian Branch of Russian Academy of Sciences
Nowadays, a provision of computational process fault-tolerance in distributed computing environments such as Grid-systems or Cloud-infrastructures remains a relevant issue. The aim of our study is to increase the fault-tolerance for processes of solving large fundamental and applied problems in distributed systems of modular programming. The computational process is represented by an abstract program (a problem solving scheme). This paper proposes a new multi-agent algorithm for the Grid-resources reallocation, when the computational process is failure. The residual problem solving scheme is formed using methods of the abstract program specialization. In comparison to the known algorithms for the same purpose, the proposed algorithm implements an adaptive multi-scenario solving this problem, and therefore increases a degree of computational process fault-tolerance. The algorithm is based on using the finite state machine model of effective and reliable agents interaction.
multi-agent system
finite state machine model
computation management
mixed computation
Grid

Проблема восстановления вычислительного процесса (задания) вследствие отказа программно-аппаратного обеспечения актуальна при решении больших фундаментальных и прикладных задач в разнородных распределенных вычислительных средах, в том числе в Grid различного назначения. Существуют различные подходы к решению данной проблемы [8].

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

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

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

Вычислительная модель

Пусть Z, F и M – это множество параметров, операций и программных модулей вычислительной модели предметной области. Операции из F определяют отношения вычислимости на множестве параметров Z. Каждая операция fi ∈ F реализуется модулем mj ∈ M, где feoktist01.wmf feoktist02.wmf nf – число операций; nm – число модулей. Один модуль может реализовывать несколько операций. С каждой операцией fi связано два множества параметров feoktist03.wmf. Множество feoktist04.wmf определяет параметры, значения которых необходимо задать, чтобы получить значения параметров, представленных множеством feoktist05.wmf. Множества feoktist06.wmf и feoktist07.wmf представляют соответственно множества входных и выходных параметров модуля mj, реализующего операцию fi.

Постановки задач могут формулироваться в полной или сокращенной (процедурной или непроцедурной) форме. По сформулированной постановке задачи строится схема решения задачи на основе сочетания волновых и переборных методов планирования вычислений [4]. В общем случае в вычислительной модели предметной области может существовать множество S эквивалентных схем решения задачи. Схема s ∈ S определяет, какие операции и в какой последовательности должны быть выполнены для решения задачи.

Полная постановка задачи sf, совпадающая со схемой s, определяется структурой feoktist08.wmf где Fs ⊂ F – множество операций, которые нужно выполнить для решения задачи; X0 ⊂ Z – множество исходных параметров, значения которых заданы; Y0 ⊂ Z – множество целевых параметров, значения которых нужно вычислить.

Остаточная схема решения задачи

Пусть c(P, X, Y) – вычислитель, выполняющий программы из множества P, где X – множество параметров программ из P, значения которых вычислены; Y – множество параметров программ из P, значения которых нужно вычислить. Тогда, согласно А.П. Ершову [6], программа px(Y) ∈ P называется остаточной программой (проекцией p на x) такой, что px(y) = p(x, y), x ⊂ X, y ⊂ Y.

Пусть s ∈ P и вычислителем выполнено множество Fr ⊂ Fs операций. Тогда, остаточной схемой sx(y) ∈ P решения задачи называется проекция s на x, где Z ⊆ X, feoktist09.wmf feoktist10.wmf feoktist11.wmf feoktist12.wmf nr – число выполненных операций схемы s, feoktist13.wmf feoktist14.wmf Fw – множество невыполненных операций схемы s, feoktist15.wmf feoktist16.wmf nw – число невыполненных операций схемы s.

Сценарии обработки отказов

Виды, признаки и причины отказов объектов вычислительной среды с различной степенью их детализации описаны в [1]. Мы рассматриваем следующие объекты среды: узлы, агенты и модули.

Соответственно, мы учитываем следующие отказы: отказ узла (узел находится в нерабочем состоянии); отказ агента (агент не отвечает в течение установленного периода времени); отказ модуля (аварийное завершение выполнения модуля). Эти отказы обобщают различные причины и признаки неисправностей рассматриваемых объектов. Каждый отказ приводит к необходимости перезапуска модуля схемы решения задачи или выполнения другого модуля.

Рисунок иллюстрирует сценарии обработки перечисленных выше отказов.

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

Есть три возможных варианта назначения агента для выполнения модуля:

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

pic_30.tif

Сценарии обработки отказов

– децентрализованное назначение модуля путем проведения торгов между агентами, которые могут выполнить данный модуль;

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

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

Алгоритм

Пусть Z* – это множество простых и составных логических параметров, принимающих значения из множества {0, 1, θ}, Z* ⊂ Z. Составной параметр реализует логическое выражение, сформированное из простых параметров и логических операторов. Составной параметр не определен, если не определен хотя бы один из его простых параметров. Обозначим через A и PR множество действий по обработке отказов и множество продукций, определяющих правила выбора действий: feoktist17.wmf zj ⇒ ak; feoktist18.wmf, где предусловие продукции определяется как

feoktist19.wmf

zj ⇒ ak -  ядро продукции, интерпретируемое как выбор действия ak ∈ A по обработке отказа, zj ∈ Z*, feoktist20.wmf – постусловие продукции. Каждая продукция имеет приоритет.

Связи между продукциями и логическими параметрами в левых частях их ядер представлены булевой матрицей B, размерности np×nz, где np – число продукций; nz – число логических параметров. Элемент матрицы b i,j = 1 означает, что продукция pri использует параметр zj. Связи между продукциями и действиями представлены булевой матрицей R, размерности np×na, где na – число действий. Элемент матрицы ri,k = 1 означает, что продукция pri описывает правило выполнения действия ak. Зависимости между действиями представим булевой матрицей D размерности na×na. Элемент матрицы feoktist21.wmf означает, что действие feoktist22.wmf зависит от действия feoktist23.wmf.

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

1. Обработка предусловий feoktist24.wmf продукций pri, feoktist25.wmf.

2. Если feoktist26.wmf, то задача неразрешима. Переход на шаг 10.

3. Формирование списка продукций feoktist27.wmf ядра которых могут быть выполнены: feoktist28.wmf feoktist29.wmf feoktist30.wmf feoktist31.wmf

4. Вычисление левых частей feoktist32.wmf ядер продукций feoktist33.wmf: feoktist34.wmf feoktist35.wmf feoktist36.wmf

5. Если feoktist37.wmf то задача неразрешима. Переход на шаг 10.

6. Выбор действия ak:rn,k = 1, где feoktist38.wmf, feoktist39.wmf – приоритет продукции feoktist40.wmf.

7. Выполнение действия ak и обработка постусловия продукции pn.

8. Если feoktist41.wmf то задача решена. Переход на шаг 10.

9. Конкретизация вычислительной модели: A = A\{ak}, PR = PR\{pn}. Переход на шаг 1.

10. Завершение работы алгоритма.

Обработка предусловий продукций обеспечивает адаптацию работы алгоритма к текущему состоянию Grid и выбор наиболее подходящего сценария действий по устранению отказа. Алгоритмы, применяемые при выполнении децентрализованного назначения модулей, идентификации отказов и резервирования узлов, рассмотрены в [3, 5, 7].

Модель функционирования агентов

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

feoktist42.wmf

где STS – множество состояний агента; sts0 ∈ STS – начальное состояние агента; ACT – множество действий, совершаемых агентом, которое включает подмножество локальных действий ACTlocl ⊂ ACT, а также подмножества коммуникационных взаимодействий с другими агентами: отправки сообщений ACTsend ⊂ ACT и приема сообщений ACTrecv ⊂ ACT; MES – множество входных и выходных сообщений агента, SLT – система логического времени для датировки событий мультиагентной системы, gl – логическая функция переходов из одного состояния в другое в результате действий, совершаемых агентом.

Система логического времени SLT представлена следующей структурой:

feoktist43.wmf

где T – область значений логического времени; Tm – область значений временных маркеров датировки сообщений, Tm ⊆ T; gt – функция логического времени; gm – функция датировки сообщений; gr – функция сравнения значений логического времени. Система логического времени использует векторные логические часы, в которых число компонент вектора времени равно числу агентов виртуального сообщества.

Реализация агентов осуществляется с помощью Java Agent DEvelopment framework (JADE) [2]. Сообщения создаются с помощью языка Agent Communication Language [2]. Очередь сообщений агента в JADE формируется в порядке поступления сообщений на физическом уровне. Этот порядок может не соответствовать логической обусловленности событий мультиагентной системы. Причинами такого несоответствия могут быть как рассинхронизация физических часов агентов, так и задержка передачи сообщений в коммуникационных каналах связи.

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

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

Заключение

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

Исследование выполнено при финансовой поддержке РФФИ, проекты № 15-29-07955-офи_м и № 16-07-00931-а, а также при частичной финансовой поддержке Совета по грантам Президента Российской Федерации для государственной поддержки ведущих научных школ Российской Федерации (НШ-8081.2016.9).