Диагностика многопроцессорных вычислительных систем на основе «И-ИЛИ» графов

Диагностика многопроцессорных вычислительных систем на основе

«И-ИЛИ» графов

Чжо Зо Е, Лисов О.И.

Московский государственный институт электронной техники

(технический университет)

Данная статья посвящена разработке модели для построения алгоритма определения неисправностей в МВС на основе «И-ИЛИ» графов. Представленная модель в виде «И-ИЛИ» графов позволяет составить необходимый алгоритм, который по входной информации о правильности решения задач позволяет выдать сообщение о потенциально неисправном компьютере.

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

            Задача диагностики неисправностей относится к задачам распознавания образов, но также может рассматриваться как задача построения рассуждений. Характерно то, что данная задача трудно разрешима, особенно для больших, в том числе кластерных вычислительных систем, количество компьютеров в который может достигать несколько тысяч.  Причиной этого является сложность формализации информации о неисправностях многомашинных вычислительных систем (МВС), так как для этого требуется найти способы описания таких трудно  формализуемых сведений, как интенсивность задач, особенности работы машин в процессе решения задач до и во время возникновения неисправности и т.д[3-4]. Следует также эффективно обрабатывать данную информацию.

            Теоретическую и методологическую базу исследования составили  логическая модель в виде «и-или» графа, элементы общей теории систем, методы интеллектуальных технологий, модели и алгоритмы технической диагностики[1]. И-ИЛИ граф (рис1.)- это ориентированный граф, обладающий следующими свойствами[2].

Рис.1.  Представление «И-ИЛИ» графа используемого для решения

 задачи  диагностики компьютеров.

·        При передаче информации от входных дуг, ведущих в некоторую вершину, реализуется либо конъюкция «и», либо дизъюнкция «или». В первом случае вершина становится активной и принимает информацию только тогда, когда возбуждены все дуги, входящие в нее. Во втором случае для возбуждения вершины достаточно возбуждения любой входящей в нее дуги[2].

·        При возбуждении вершины возбуждаются либо все выходящие из вершины дуги «и», либо только одна, выбираемая вершиной (исключающее «или» для числа аргументов, равного числу выходящих дуг). Часто под «и-или» графом понимают граф, для которого выполнено первое свойство, а для выходных дуг всегда имеет место функции  «и». И-ИЛИ графы широко используются в системах планирования целесообразного поведения автономных роботов и в других системах искусственного интеллекта[2].

            Основной рассматриваемой задачей является разработка алгоритма поиска неисправного компьютера в системе машин. Рссмотрим пример задачи диагностики МВС: при условии имеется сеть из 7 компьютеров, которые решают 5 однотипных  задач. Можно сформулировать несколько ситуаций диагностики таких систем. Например:

1)     Каждая задача решается на нескольких компьютерах одновременно, разными методами. Результат решения заранее не известен. При совпадении результатов решения на всех компьютерах, все компьютеры считаются исправными. Если результаты решения задачи не совпадают, то один компьютер является неисправным.

2)     Каждая задача решается на одном из n компьютеров. Компьютер, решающий задачу, неизвестен, т.е выбирается самойсистемой случайным образом  Результат решения заранее известен и неисправный  компьютер определяется по неправильному ответу.

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

            В общем случае, при достаточном большом количестве компьютеров решение о правильности выполнения задачи принимается по мажоритарному принципу, т.е., правильным считается одинаковый результат, полученный более чем на половине компьютеров, если их не менше 2m+1 в случае дружественной неисправности и не менше 3m+1 в случае враждебной неисправности[3-4]. В данной работе неисправности являются только дружественными.

            Рассмотрим пример решения задачи диагностики. Исходное распределение задач по компьютерам представлено матрицей “D” в таблице .1.

Таблица.1.

Матрица 'D'- распределения задач по компьютерам

ком задача
А	+			+		+
Б	+	+			+
В	+	+	+			+
Г	+	+	+				+
Д			+	+	+		+

           

            В матрице “D” строки (А,Б,В,Г,Д) соответствуют номеру задачи, и указаны номера компьютеров (,,,,,,), на которых она решается. После анализа решения задачи результатов сравниваем и обрабатываем их с применением «и-или» графов. Получаемый ответ, указывающий на неисправную машину в системе. Далее рассматривается модель-схема решения задачи для первой задачи на основе «И –ИЛИ»  графа(рис.2.).

                    Рис. 2. Модель-схема решения  1_ой задачи на основе «и-или» графов

            Имеется 5 задач (А,Б,В,Г,Д), которые решаются на 7 компьютерах. Результат решения задачи заранее не известен. Каждая задача решается на 3 компьютерах. Например, задача А- на 1, 4 и 6 компьютерах; задача Б - на 1, 2, 5 и т.д. Таким образом, компьютер 1 решает задачи А,Б,В и Г компьютер 2 решает задачи Б,В и Г и т.д. По результатам решения каждой из задач можно определить неисправный компьютер. Компьютер считается неисправным, если при решении задачи получены несовпадающие результаты (если решение хотя бы одной из задач А и Г не совпадает ответами других компьютеров, то неисправен  компьютер 1 и т.д.) Таким образом., каждый неправильный ответ при решении задачи в разрабатываемом алгоритме соответствует 0, а правильный -1. Если решения задач А и Г совпадают  каждый со своим ответом, то результат=1, иначе -0.        Таким образом, представленная модель в виде  И-ИЛИ  графа позволяет составить алгоритм, который по входной информации о правильности решения задач позволяет выдать сообщение о потенциально неисправном компьютере.

Литературы

1.                          Берников А.Р., Графов Р.П. Согласование экспертных оценок для формирования модели деятельности оператора в тренажерах // Научно-технический и научно производственный журнал «Информационные технологии». – М. – 2003. – № 6. – С. 44-47.

2.                          Модель Автоматизированного синтеза учебных объектов с использованием метода И-ИЛИ деревьев // Геркушенко Г.Г., Дворянкин A.M. Волгоградский государственный технический университет, Волгоград, 2003. http://www.ict.edu.ru/vconf/index.php?a=vconf&c=getForm&r=thesisDesc&d=light&id_sec=49&id_thesis=1482.

3.                          Генинсон Б.А., Панкова Л.А., Трахтенгерц Э.А. Отказоустойчивые методы обеспечения взаимной информационной согласованности в распределенных вычислительных системах // АиТ. 1989. № 5. С. 3-18.

4.                          Lamport L., Shostak R., Pease M. The byzantine generals problem // ACM Trans. Progr. Lang. and Syst. 1982. V. 4. № 3. P. 382-401.