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

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

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

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

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

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

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

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

           

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

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

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

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

Intellectual-training complex for learning processes of technical diagnostics in multiprocessor systems

Kyaw Zaw Ye, Lisov.O.I.

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

This paper is dedicated to the development of intellectual-training complex to study the processes of technical diagnosis in  multiprocessor systems. The training complex contains a block of theoretical data, the issues involved and contains the model associated with the diagnosis of multiprocessor systems, demonstration block unit to test the trainee’s job.

В настоящее время в системах поддержки процессов обучения (СППО) все более важное место занимает использование компьютерных технологий. Они используются для повышения эффективности и качества учебного процесса. Можно привести такие примеры, как использование e-learning, дистанционного обучения и обучающих интеллектуальных тренажеров. Особенно актуальным это становится для обучения некоторым разделам технической диагностики в МВС. Наилучшим подходом, по нашему мнению, является создание ТОК, предназначенного для повышения квалификации обслуживающего персонала без отрыва от производства и представляющего собой систему интеллектуальной поддержки процессов обучения и переподготовки инженерно-технического персонала в  технологическом процессе производства [1-3].

В данный момент существует широкий спектр средств тестового диагностирования от простейших внешних или встроенных средств до универсальных многофункциональных внешних средств. Существуют различные модели поиска неисправностей. Для систем тестового диагностирования дискретных устройств чаще всего используется модель константной неисправности. Для систем функционального диагностирования дискретных устройств применяется модель логической неисправности. Однако эти модели неисправностей для логических элементов являются малоприемлемыми для таких крупных объектов как ЭВМ или вычислительная система. Особый интерес в данной работе представляют вопросы диагностики многопроцессорных вычислительных систем, которые реализуют одну из трех ситуаций: 1) репликацию задач, 2) выполнение сложных задач, требующих распределенных вычислений, 3) выполнение нескольких взаимодействующих задач [1-2].

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

В качестве предметной области нашего исследования является разработка алгоритмов, моделей и программных блоков ТОК, а также модель области знаний, рассматривающей методы диагностики МВС, представленная в виде «И-ИЛИ» графов. Модель области знаний, необходимая для функционирования контента ТОК, обеспечивает: учет степени компетентности по обеспечивающим дисциплинам; автоматизация генерации заданий; автоматический «решатель» задач; использование трех технологий обучения (индуктивной, дедуктивной и абдуктивной), развитие и корректировку структуры и контента ТОК в процессе эксплуатации [1-2].

Рис. 1. Схема структуры ТОК

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

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

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

Подготовка сотрудников может отличаться достаточно сильно. Использование ТОК призвано приблизить процесс обучения к индивидуальному подходу к каждому сотруднику, поэтому ТОК содержит в своем составе блок настройки на уровень компетентности  обучаемого.

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

Список литературы

1.      Чжо Чжо Кхаин. Создание автоматизированной обучающей системы для изучения методов технической диагностики// "Инновации в условиях развития информационно-коммуникационных технологий". Материалы научно-практической конференции ИНФО-2007: Тез. докл. Сочи, 2007. -С. 283 - 286.

2.      Чжо Чжо Кхаин, Ашарина И.В. Автоматизированная обучающая система диагностирования электронных схем// "Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий систем". Всероссийская межвузовская научно-техническая конференция: Тез. докл. М.: МИЭТ, 2007. -С. 175.

3.      Лисов О.И., Лисовец Ю.П., Бавин Эй. Тренажерно-обучающий комплекс(ТОК) по теории вероятностей и математической статистики в среде MATLAB// “ Труды международной конференции «Информационные технологии в науке, образовании, телекоммуникации, и бизнесе»”. 2008: XXXV международная конференция.

4.      Чжо Зо Е «Тренажерно-обучающий комплекс по диагностике параллельных вычислительных систем» // XIV Международная телекоммуникацинная конференция студентов и молодых ученых «МОЛОДЕЖЬ И НАУКА» Тезисы докладов часть 3 М.: НИЯУ МИФИ, 2010. – 270 с.