Автоматика и телемеханика, № 6, 2014
Безопасность, живучесть, надежность,
техническая диагностика
( 2014 г. И.В. АШАРИНА, канд. техн. наук (asharinairina@mail.ru), А.В. ЛОБАНОВ, д-р техн. наук (lav@se.zgrad.ru) (ОАО НИИ «Субмикрон», Москва)
ВЫДЕЛЕНИЕ КОМПЛЕКСОВ, ОБЕСПЕЧИВАЮЩИХ ДОСТАТОЧНЫЕ СТРУКТУРНЫЕ УСЛОВИЯ СИСТЕМНОГО ВЗАИМНОГО ИНФОРМАЦИОННОГО СОГЛАСОВАНИЯ В МНОГОКОМПЛЕКСНЫХ СИСТЕМАХ
Рассматривается возможность организации решения в сети произвольной структуры заданного множества взаимодействующих задач с заданными для каждой задачи характеристиками по сбое- и отказоустойчивости. Для каждой задачи выделяется комплекс, все ЦВМ которого решают копии данной задачи (репликация задачи), обмениваются результатами и выбирают из них правильный. Ключевой проблемой таких вычислений является системное взаимное информационное согласование (СВИС), обеспечивающее согласованность системной информации во всех ЦВМ всех комплексов в условиях возникновения допустимых неисправностей. Представлены достаточные структурные условия достижения такого СВИС и методы их поиска. Предложен алгоритм выделения (если это возможно) в сети ЦВМ комплексов, соответствующих решаемым задачам.
1. Введение
В настоящей статье и в [1] рассматривается многомашинная вычислительная система (МВС) или сеть цифровых вычислительных машин (ЦВМ) произвольной структуры.
Между собой ЦВМ соединены двухточечными дуплексными и/или симплексными каналами связи. Структура системы известна. В качестве модели неисправности ЦВМ рассматривается наиболее общий случай враждебной («византийской») неисправности, при которой поведение неисправной ЦВМ может быть произвольным, неодинаковым по отношению к взаимодействующим с ней другим ЦВМ системы и даже подобным «злонамеренному» [2].
При организации многозадачных параллельных вычислений в таких МВС и сетях ЦВМ одной из важнейших является задача достижения согласованности информации в различных ЦВМ системы в условиях возникновения допустимых неисправностей, формулируемая как проблема достижения взаимного информационного согласования (ВИС) [3]. Процесс ВИС представляет со-
бой многораундный обмен индивидуальными согласуемыми значениями данных между пронумерованными с единицы до п ЦВМ. На основе результатов обмена в каждой р-й исправной ЦВМ вычисляется вектор вр = (01,02, ■■■, 0п) согласованных значений, где 0д (д = 1, ■ ■ ■, п) — согласованное значение, соответствующее согласуемому значению 5д д-й ЦВМ. Этот вектор даже в условиях наличия допустимого количества у < п неисправных ЦВМ должен быть одинаковым во всех исправных ЦВМ, причем каждый элемент этого вектора, относящийся к исправной ЦВМ, должен совпадать с согласуемым значением этой ЦВМ.
Комплексом называется система или подсистема, удовлетворяющая определенным структурным требованиям [4, 5], каждая исправная ЦВМ в которой может определить вектор согласованных значений всех ЦВМ этого комплекса. Комплекс является необходимым инструментом при организации сбое- и отказоустойчивых вычислений на основе репликации задач в системах с динамической избыточностью [6] и управляемой деградацией. Репликация состоит в решении одной и той же задачи на всех ЦВМ комплекса с обменом копиями результатов и выбором правильного результата в предположении, что только малая часть этих ЦВМ может быть неисправной. При таком подходе к обеспечению сбое- и отказоустойчивости и при параллельном решении в системе нескольких задач, взаимно обменивающихся информацией, необходимо наличие в системе нескольких комплексов, каждый из которых решает одну из задач и в каждом из которых допускается наличие определенного для данного комплекса количества неисправных ЦВМ. Назовем такие системы многокомплексными. В этих системах процесс достижения системного ВИС можно рассматривать в виде двух последовательных этапов: 1) внут-рикомплексное ВИС для каждого из комплексов, при котором во всех исправных ЦВМ комплекса вычисляется вектор согласованных значений этого комплекса, 2) межкомплексное (системное) ВИС (СВИС), включающее межкомплексный обмен согласуемой информацией по средам межкомплексных посылок и вычисление в каждом комплексе вектора системного ВИС, при котором в каждой исправной ЦВМ системы формируется одинаковый вектор согласованных значений всех ЦВМ системы.
Алгоритмы ВИС оцениваются величинами требуемых аппаратурной, временной и информационной избыточностей [3]. В однокомплексной полносвязной системе при возможности возникновения враждебных неисправностей не более чем в у ЦВМ аппаратурная избыточность п в виде общего количества ЦВМ в системе должна быть п > 3у.
Рассматривается задача в следующей постановке. Имеется МВС или сеть ЦВМ известной структуры. Задано определенное количество пронумерованных непересекающихся комплексов, которые должны быть выделены в этой МВС. Для каждого г-го комплекса задан диапазон допустимого количества неисправных ЦВМ. Допустимое количество неисправных ЦВМ задано и для каждой среды межкомплексного обмена. Необходимо определить, можно ли в заданной структуре МВС выделить и какую структуру будут иметь указанные непересекающиеся комплексы и непересекающиеся среды межкомплексных посылок сообщений такие, что при допустимых количествах неисправ-
ных ЦВМ в этих комплексах и в средах межкомплексных обменов обеспечивается возможность достижения системного ВИС.
Структурные свойства выделенных комплексов и сред межкомплексных обменов, составляющих среду СВИС, позволяют построить искомый алгоритм системного ВИС, и поэтому наличие таких комплексов и сред межкомплексных обменов является достаточным условием достижения СВИС в рассматриваемой многокомплексной системе.
Полученные в работе результаты являются основой методов построения алгоритмов достижения системного ВИС в рассматриваемых системах и сетях ЦВМ. Такие алгоритмы, в свою очередь, являются необходимыми для рассматриваемых систем и сетей ЦВМ при организации в них сбое- и отказоустойчивых параллельных вычислений, построенных на репликации задач и реализации принципов динамической избыточности. Такая избыточность позволяет системе самостоятельно, без участия обслуживающего персонала:
а) обнаруживать и идентифицировать возникающие допустимые неисправности по месту возникновения и по типу (сбой, программный сбой, отказ),
б) восстанавливать вычислительный процесс при сбоях и программных сбоях, в) реконфигурировать систему при отказах с включением в рабочую конфигурацию запасных элементов, г) осуществлять управляемую деградацию системы с сохранением и допустимым снижением заданных характеристик производительности, пропускной способности и сбое- и отказоустойчивости, д) переводить систему в состояние безопасного останова при исчерпании доступных системных ресурсов или при возникновении недопустимых неисправностей.
В данной статье предложен алгоритм А1 выделения в системе заданного множества непересекающихся комплексов, удовлетворяющих заданным характеристикам по сбое- и отказоустойчивости. В [1] представлены условия для выделения сред межкомплексных посылок согласуемой информации, достаточные для достижения СВИС, предложены алгоритм А2, используемый для определения наличия этих достаточных условий, и общий алгоритм А4 последовательного выделения непересекающихся комплексов с промежуточным выделением всех необходимых сред межкомплексных обменов между очередным выделенным комплексом и всеми предварительно выделенными комплексами.
Номера ЦВМ и номера комплексов будут отображаться строчными латинскими буквами. Номер ЦВМ может иметь нижний индекс, определяющий номер комплекса, которому принадлежит эта ЦВМ.
Описываемые в статье объекты (множества, графы, ориентированные графы (орграфы), смешанные графы, ориентированные подграфы (орподгра-фы)) обозначаются прописными латинскими буквами, возможно, с индексами. Множество с элементами а, Ь,..., / обозначается через {а, Ь,..., /}. Система, в которой каждый дуплексный канал может быть представлен разнонаправленной парой симплексных каналов, моделируется системным орграфом, например, С, в котором пронумерованные вершины, составляющие множество, например, А, отображают ЦВМ, а дуги, составляющие множество, например, В - симплексные каналы связи между ними. Такой орграф
задается записью С = (А, В). Термины ЦВМ и вершина орграфа (орподгра-фа) рассматриваются как синонимы. Также синонимами являются термины двухточечный симплексный межмашинный канал связи и дуга орграфа (ор-подграфа), система или подсистема и ее орграфовая модель (ее орграф или орподграф). Кроме того, если задан орграф С = (А, В), то орподграф, например, О = (Е, Е), в орграфе С с множеством Е С А вершин и множеством дуг Е С В может задаваться записью аО = (Е, Е).
Обозначим через аЖ{1) орподграф Н = (1,К) орграфа С = (А,В), порожденный подмножеством IС А вершин, в котором дуга между любой парой вершин имеется, если и только если такая дуга существует между этой парой в орграфе С, т.е. К С В. Пусть в орграфе С = (А, В) определены два орпод-графа сЩЕ) и Тогда орподграфом Ь = сМЗ) = сЩЕ) и сЩ1) =
= с1±{Е и I) будет орподграф Ь из О, порожденный подмножеством вершин 3 = ЕиЕ Операция вычитания орподграфов М = аМ{3) = аИ(Е)\аН{1) = = аМ(Е\1) определяет орподграф М орграфа С, порожденный подмножеством 3 = Е\1 вершин. Вычитание из орграфа С = (А, В) орподграфа сИ(Е) приводит к исключению из С всех вершин, принадлежащих Е, а также всех дуг, инцидентных в С вершинам из Е.
Для орподграфа О = (Е, Е) обозначим через О функцию определения множества вершин, принадлежащих И, т.е. И = Е. Так, если Н = дН(Е), то Н = Е.
Рассматриваются системы, орграфы которых не имеют параллельных дуг.
2. Выделение комплексов из структуры системы
Полным орграфом называется орграф, имеющий пару разнонаправленных дуг между любыми двумя вершинами. Орграфы являются гомеоморфными, если существуют их изоморфные подразбиения, образующиеся в результате подразбиения дуг [7].
Для построения алгоритма внутрикомплексного ВИС предлагается использовать методы построения алгоритма ВИС для однокомплексных непол-носвязных МВС [5, 8], в которых вся система является компл
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.