Автоматика и телемеханика, № 8, 2014
А втоматизированные информационно-управляющие системы, системы управления производством
© 2014 г. И.В. АШАРИНА, канд. техн. наук (asharinairina@.mail.ru) А.В. ЛОБАНОВ, д-р техн. наук (lav@se.zgrad.ru) (ОАО НИИ "Субмикрон", Москва)
ВЫДЕЛЕНИЕ СТРУКТУРНОЙ СРЕДЫ СИСТЕМНОГО ВЗАИМНОГО ИНФОРМАЦИОННОГО СОГЛАСОВАНИЯ В МНОГОКОМПЛЕКСНЫХ СИСТЕМАХ
Предложен алгоритм выделения в сети произвольной структуры среды! системного взаимного информационного согласования, включающей комплексы решения задач и среды межкомплексного взаимообмена, если такое выделение возможно. Такое согласование необходимо при организации параллельного решения в компьютерной сети взаимодействующих задач с заданными характеристиками по их сбое- и отказоустойчивости, реализуемой на основе динамической избыточности. Предлагаемые подход, методы и алгоритмы применимы при организации вычислений с заданной достоверностью в распределенных системах, в grid- и "облачных" вычислениях.
1. Введение
В настоящей статье и в [1] представлены достаточные условия достижения системного взаимного информационного согласования (СВИС) в многокомплексных системах, осуществляющих параллельное вычисление множества взаимодействующих задач с заданными характеристиками по сбое- и отказоустойчивости. Используемые в статье термины, определения и обозначения представлены в [1], где в полном объеме приведена постановка задачи и предложен алгоритм А1 выделения в системе заданного множества непересекающихся комплексов, удовлетворяющих заданным характеристикам по сбое- и отказоустойчивости. В данной статье определены условия для выделения сред межкомплексных обменов согласуемой информации, удовлетворяющих заданным характеристикам по сбое- и отказоустойчивости и достаточных для достижения СВИС. Также предложены алгоритм А2, используемый для определения наличия этих достаточных условий, и общий алгоритм А4 выделения среды СВИС путем последовательного выделения непересекающихся комплексов с промежуточным выделением всех требуемых непере-
секающихся сред межкомплексных обменов между очередным выделенным комплексом и всеми, предварительно выделенными.
2. Выделение структурной среды СВИС
Пусть в системном орграфе О выделены два непересекающихся комплекса фk (к = г,;) с Тк, Нк = (Хк и Рк, Бк), Хк, N = Рк и Qк, где Тк - орпод-граф комплекса фк, Нк = (Хк и Рк ,0к) - орподграф из Тк, гомеоморфный полному орграфу, в котором Хк - множество основных вершин, Рк - множество разделительных вершин, Ок - множество дуг [1]. Кроме того, пусть в О определен орподграф Rфi^фj = сВ-ф^ф^ области межкомплексного обмена
Т и Т такой, что, во-первых, Rфi^фj П Т = 0 и Rфi^фj П Т) = 0, и, во-вторых, посылка из любой вершины, принадлежащей Т (Т) в любую вершину из Т (Т) должна проходить только по пути, принадлежащему орподграфу сИф^ф^и Кф^ф^ иТ,-). Предположим, что для орподграфа Кф^ф^ задано максимально возможное число неисправных вершин, принадлежащих
этому орподграфу.
Второй этап достижения системного ВИС включает межкомплексный обмен согласуемой информацией и вычисление вектора системного ВИС в каждой цифровой вычислительной машине (ЦВМ) каждого комплекса системы. Межкомплексный обмен информацией состоит в том, что каждый г-й комплекс, будучи комплексом-источником, посылает копии своего вектора согласованной информации по путям в орподграфе сИф^ф ХТг и Кф^ф:) иТ,-) каждому другому ;-му комплексу, являющемуся комплексом-получателем. При этом наличие допустимых неисправностей в комплексах-источниках, комплексах-получателях и средах межкомплексной посылки между ними не должно препятствовать вычислению в каждой исправной ЦВМ каждого комплекса-получателя правильного вектора согласованных значений каждого комплекса-источника.
Рассмотрим комплекс-источник фi с орподграфом комплекс-получатель фj с орподграфом Т и их область межкомплексного обмена Вф^ф^. Выделим в множество Wфi^фj каждую вершину из Т, например, bi, имеющую непустую дизъюнктивную нормальную форму (ДНФ) исходящей смежности
, СЕ(Ы и Кф^ф^Т,)) [1].
Отметим, что по результатам внутрикомплексного ВИС в г-м комплексе-источнике все исправные вершины множества Wфi^фj должны иметь одинаковый правильный вектор согласованных значений г-го комплекса. При этом не более ^ неисправных вершин из множества Wфi^фj могут иметь произвольные значения этого вектора, отличные от правильного. Отсюда следует правильность утверждения 1.
Утверждение 1. Для достижения межкомплексного ВИС для каждой пары г-го комплекса-источника и ;-го комплекса-приемника необходимо | ^ + 1.
После этапа внутрикомплексного ВИС в каждой исправной вершине из Т формируется вектор согласованных значений Vi этого комплекса. Для достижения межкомплексного ВИС копии этого вектора должны быть посланы
из некоторого подмножества вершин, принадлежащих множеству Wфi^фj, по
некоторому подмножеству путей в орподграфе сЕЗУУф^Ф] и и!}) в
некоторое подмножество вершин из Tj.
Копию Уг, посланную из исправной вершины, например, рг € Wфi^фj и прошедшую в исправную вершину, например, qj только через исправные вершины множества Яф^ф^ иTj, будем называть правильной. Одинаковость значений правильных копий вектора У г, поступивших в вершину qj, позволяет этой вершине для вычисления согласованного значения вектора Уг = Уг использовать функцию мажорирования, которая принимает определенное значение, если это значение имеют более половины ее аргументов (для учета возможности неприхода сообщения в qj от рг можно применить метод из [2]). В противном случае значение функции не определено. Аргументами функции мажорирования являются поступившие копии векторов Уг.
Рассмотрим достаточные условия вычисления в вершине qj определенного значения У = Уг.
Назовем вершиной 0-го ранга такую вершину qj, в которой значение Уг = = Уг может быть вычислено только по результатам посылки копий Уг из вершин Wфi^фj в эту вершину qj без необходимости предварительного вычисления Уг = У г хотя бы в одной вершине rj € Т. Если в вершине Sj для вычисления значения Уг = Уг используется копия такого согласованного значения, предварительно вычисленного в вершине rj ранга Ь, то вершине Sj приписывается ранг не менее Ь + 1.
Определим достаточные условия вычисления Уг = Уг в вершине qj 0-го ранга. Рассмотрим некоторое 1-е подмножество Wфi^q. С Wфi^фj такое, что для него существует непустая ДНФ входящих пучков Б ЯР _ВЫЕ , qj, Кф^ ф^ и Tj) таких, что в каждом пути каждого пучка
имеется только одна вершина из Wфi^ф,. Пронумеруем начиная с единицы термы БКР_ВИЕ,qj, Ёф.„ф. и Т). Терм с г-м (г = 1, 2, 3,...) номером определяет отдельный входящий пучок Б ЯР , qj, Яф^ фj и Т).
Рассмотрим путь из вершины рг € Wlфi^q., принадлежащий
Б ЯР (Ш1^ ^ ,Яфг^фз и Т) .
Возможны следующие четыре типа такого пути:
1) а - путь содержит только одну дугу между начальной рг и конечной qj вершинами;
2) в - путь, все внутренние вершины которого принадлежат Яф^фj;
3) 7 - путь, все внутренние вершины которого принадлежат Tj;
4) 5 - путь, в котором часть внутренних вершин пути принадлежит Яф^фj, а другая часть - Tj.
Назовем орподграфом А-вида (В-, Г-, Д-вида) для входящего пучка Б ЯР , qj, Яф^ фj и Т) орподграф, содержащий все а-пути (в-, 7-,
5-пути соответственно) этого пучка и только их. Аналогично орподграфом
AB-вида (АГ-, AA-, ..., ГД-, АВГ-, ABA-, ЛГД-, БГД-, АВГА-вида) для SRP(W^^., qj, Rфi^фj U Tj) будет орподграф, содержащий все пути а- и в-типа (а- и 7-типа, а- и ¿-типа, ..., 7- и ¿-типа, а- и в- и 7-типа, а- и в- и ¿-типа, а- и 7- и ¿-типа, в- и 7- и ¿-типа, а- и в- и 7- и ¿-типа соответственно) этого пучка и только их.
Из простого анализа можно вывести следующие достаточные условия вычисления согласованного значения Y = Vi, в вершине qj ранга 0: У1) если в орподграфе A-вида для SRP(Wф__я., qj, кф^ф., UTj) имеются + 1 путей,
то однократной посылки копий Vi по этим путям (по орподграфу посылки) достаточно для вычисления в вершине qj значения Yi = Vi при помощи функции мажорирования. Аналогично достаточными условиями также являются: У2) наличие 2(ц) + 1 путей в орподграфе В-вида либо AB-вида; У3) наличие 2(^i + цj) + 1 путей в орподграфе Г-вида либо Ar-вида; У4) наличие 2(^i + + цj) + 1 путей в орграфе любого другого из оставшихся видов.
Доказательство правильности каждого из условий У1—У4 основывается на том, что в случае выполнения любого условия любая совокупность допустимых неисправностей при посылке в qj копий значений Yi по всем путям, соответствующим этому условию, может исказить только менее половины этих копий, а большинство поступивших в qj копий значений Yi будут правильными.
Возможно, что для вычисления Yi = Vi в некоторой вершине qj необходима посылка к qj копий согласованного значения вектора Yi, вычисленных уже в других вершинах из Tj, составляющих подмножество Fj.
Если такая возможность имеется, то вершине qj приписывается ранг, на единицу превышающий максимальный ранг вершин из Fj. Такое приписывание вершинам рангов является итеративным процессом ранжирования межкомплексного ВИС, в каждой итерации которого осуществляется ранжирование с учетом ранжирования на предыдущей итерации.
При выполнении 0-й итерации ранжирования потенциальными источниками копий согласованного значения Vi являются вершины из множества W t^j. Пусть после выполнения k-й итерации ранжирования все проран-жированные вершины из Tj составляют множество Zф._ф,. При выполнении (к + 1)-й итерации ранжирования вершины, являющиеся потенциальными источниками копий согласованного значения Vi, принадлежат множеству i,j U Zфi^фj.
В дополнение к названным типам путей, ведущим в вершину qj из верши-
_ тт rl.T „ „
ны pi € , назовем е-путем простой путь, ведущий из некоторой верши-
ны Uj € Tj в вершину qj, внутренними вершинами которого являются только вершины из множества Tj (возможность наличия в е-пути внутренних вершин из Rфф^ в данной статье не рассматривается). Посылка копии значения Yi, вычисленного в вершине Uj € Zk'-^^ф,, в вершину qj должна осуществляться по е-пути. Пусть I CWlp__qj и J С фj. В дополнение к приведенным видам орпо
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.