Классификация параллельных КС (стр. 5 )

Известны следующие подходы к исследованию отказоустойчивости:

1.  Создание модели живучести на основании анализа взаимодействия ВС (КС) и окружающей среды.

2.  Определение предельной живучести и вероятностный анализ сохранения системы своих функций.

3.  Определение степени живучести КС по отношению к некоторому стандартному возмущению, характерному для данного класса.

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

Используется:

-  выбор базовой структуры ВС;

-  повышению надежности элементов ВС;

-  обеспечение адекватной реакции ВС на изменяющиеся условия эксплуатации;

-  создание средств перестройки структуры ВС и поведения.

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

-  модель внешней сети

-  модель взаимодействия аппаратных средств ВС

-  модель взаимодействия компонент ПО

-  модель контроля и диагностики аппаратных и программных средств

-  модель вычислительного процесса при решении задачи

-  модель надежности.

ВС, представляемая графом S, содержит все требуемые алгоритмом ресурсы и связи, тогда k-кратной неисправностью F в КС считается удаление из графа S любых k вершин и всех связанных с ними ребер.

Неисправности F соответствуют новому графу SF.

КС S является толерантной относительно алгоритма A и неисправности F, если А выполним КС системой SF. …

КС S является толерантной относительно множества алгоритмов (А1, …, Аn) и множества неисправностей (F1, … Fq), если Ai выполним в КСи этой КС соответствует граф SFj, где j=1,…, q.

В данной модели исследования живучести неявно предполагается, что в КС имеется некоторое заведомо исправное ядро, выполняющее функции обнаружения и локализации неисправности, выполняется реконфигурация и восстановление системы, поэтому при оценке толерантности системы S участвуют следующие два момента:

1.  содержит ли SF все ресурсы для выполнения А.

2.  достаточно связей между ресурсами.

43. Определение путей и разрезов на графе(пример).

Путем в ненаправленном(2хполюсном) графе называется такое подмножество его ребер, которое позволяет, переходя от одного ребра к другому через инцидентные им обоим вершины пройти от одного полюса графа к другому.

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

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

Иначе говоря, мин путь – путь без петель(циклов) – без висячих ребер. Мин путь также называется простым.

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

В частности в последовательной системе мин путем является мн-во всех ее ребер, а в параллельной каждый мин путь состоит из 1 ребра, а число путей = число ребер в системе.

Связность 2хполюсного графа обеспечивается наличием хотя бы 1 пути(или мин пути) в графе системы. Структ. ф-ию 2хполюсного графа можно выразить через структ функцию путей , где N-число мин путей в графе.

Окончательно :

Перечисление простых путей – сложный вопрос перечисл-ой комбинаторики.

Разрезом в ненаправленном 2хполюсном графе (НДГ) наз-ся такое подмн-во его ребер, удаление которых из графа разрывает все пути этого графа. В этом случае различных разрезов может быть много. Единственный разрез имеется только в параллельной системе, причем подмн-во ребер, обр-х этот разрез совпадает со всем мн-вом ребер графа.

При анализе свзяности удобнее всего использовать мин разрез.

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

В параллельной системе мин разрезом является мно-во всех ее ребер, в последовательной каждый мин разрез состоит из 1 ребра, число таких разрезов = число ребер в системе. Из определения -> для нарушения связности НДГ достаточно исключение рер принадлежащих хотя бы 1 мин разрезу. Иначе в графе не должно быть ни одного разреза, чтобы он оставался связным. Структ функцию можно записать

М – число мин разрезов в НДГ. Мин разрезы могут быть зависимыми, если в их состав входит одни и теже ребра. Перечисление мин разрезов представляет сложную задачу.

44. Граничные оценки показателей связности.

Вычисление различных значений показателей связности(вероятность связности ребер в графе) на практике сталкивается со значительными вычислительными трудностями, т. к. решение этой задачи сводится к простому перебору.

Однако, используя пути и разрезы, удается получить достаточно простые, по сравнению с точными методами нахождение соответствующих характеристик, граничные оценки (верхнего и нижнего) требуемого показателя. Первые разрезы были получены для оценки вероятности связности НДГ(?) с ненадежными ребрами. Другими словами рассматривается граф, ребра которого могут существовать или исключаются из графа с определенными вероятностями (отказами). Отказы ребер предполагаются независимыми. Введем понятие связанных случайных величин(ССВ). Впервые понятие ССВ ввели Барлоу и Прошон. Случайные величины епс1,епс2,епс3 называются связанными, если

Или

Связность случайных величин можно понимать как одну из форм положительной корреляции. В рассматриваемых случаях имеем дело лишь с бинарными случайными величинами. Упоминалось, что пути и разрезы, в т. ч. min, м. б. зависимыми из-за того, что в их состав могут входить одни и те же ребра. В этом случае имеется связь соответствующих структурных функций αi(x) и αj(x) ∀ i, j={1,N}и соответственно βi(X) и βj(X) ∀ i, j= {1,M}. такая зависимость возникает, если все элементы какого-либо устройства одновременно подвергаются одному и тому же внешнему воздействию, при этом показатели всех элементов ухудшаются одновременно. Если xi и xj связанные случайные величины, принимающие значение 1 с вероятностью ri=P(xi=1)=1, rj=P(xj=1)=1, то структурная функция φ(xi, xj)=xi ∧ xj принимает значение 1 с вероятностью R=P(φ(xi, xj)=1)=ri+rj+cov(xi, xj), где cov(xi, xj)-ковариация случайных величин xi, xj. Ковариация xi, xj –неотрицательная величина для положительных корреляционных чисел. Обобщим для полож величин

Для двух случайных величин ri=P(xi=1)=1 совпадает с мат. ожиданием этой величины:

При рассматривании дизъюнкций связанных булевых переменных можно записать

Окончательно

Используя дополнительные сведения и полученное выражение к оценке граничных условий вероятности связности НДГ.

45. Двухсторонние граничные оценки Эзари-Прошана для вероятности связанности двухполюсного графа

46-47. Структура магистрально-модульных КС, особенности построения структур магистральных КС и их отличие от других типов комп сетей.

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

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

Магистрально-модульная КС м. б. описана в виде реберного графа L(G) реберный граф L (G) неориентированного графа G без петель и кратных ребер называется граф, множество вершин которого поставлено во взаимно-однозначное соответствие множеству ребер графа G`.

Две вершины графа L(G) смежны ó соответствующие им ребра являются ребрами графа G/

2 вершины L (G) ó смежны соотв-е им ребра графа G.

Yij=xixj – ребро графа G, тогда степень вершин y в графе L (G) равна deg xi + deg xj-2

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

Если G-это (n, m) – граф, n –число вершин, m-число ребер с вершинами имеющими степень di, то L(G) имеет m вершин и ml ребер, где

ml=-m + 0.5 (cумма от i=1 до n)di*di

По определению у реберного графа имеется M вершин, каждые di ребер инфиндентных вершинам xi дают вклад в число ребер графа L(G): (di\2)=Сd*Cd

Связвнный граф G изоморфен своему реберном графу L(G) ó G – простой цикл. Т. о. для графа G: G=L (G) ó G – регулярный граф степени 2. Если графы G1 b G2 изоморфны то графы L(G1) b L(G2) также изоморфны. Т. о. магистральная сеть, состоящая из n узлов и m магистралей моет быть описана матрицей инфиденций А n х m, Элемент этой матрицы aij равен 1, если узлу с номером i=0,1,..,n-1 инфидентна на магистрали с номером j=0,1,…,m-1.Иначе aij=0. Из определении матрицы инциденций следует, что магистральная сеть не допускает кратных инциденций (петель) ни по магистралям, ни по узлам. Т. о. можем записать определение магистральной сети: магистральной сетью называется пара конечных сножеств (x, y), где |x|=n, |y|=m с между элементами этих множеств инцидентными с помощью матрицы А. Если обозначить число магистралей, иницидентных узлу i через Pi (валетность узла), а число узлов, инцидентных магистрали j через qj, то запишем

В отличие от n x m сети в n x m магистралей сети с матрицей инциден-й А всегда существует n x m магистральная сеть с трансп-й мат-й инценд-й .

Такую сеть нзывают транспртной сетью [n, m]. Магистральные сети структурно эквивалентны гиперграфам. Исследовать их можно с помощью аппаратов обычных графов.

48. Приведите определение реберного графа и постойте граф L(G) неориентированного графа

Если G – это (n, m) граф, n –число вершин, m – число ребер, с вершинами, имеющими степень , то L (G) имеет m вершин и ребер, где

По определению у реберного графа имеется m вершин, каждые ребер инцидентных вершинам дают вклад в число ребер графа L(G):

Таким образом, получается:

49. Приведите общее выражение для переключающей матрицы.

Свойства матрицы переключения:

1.  Матрица симметрична относительно главной диагонали.

2.  Общее выражение для матриц подключения:

, где .

50. Дайте определение реберного графа и постойте граф L(G) , если граф G представляется как граф

По определению у реберного графа имеется m вершин, каждые ребер инцидентных вершинам дают вклад в число ребер графа L(G):

Таким образом, получается:

Связывающий граф G изоморфен своему реберному графу L(G) <=> G – простой цикл.

Таким образом, для графа G: <=> G – регулярный граф степени 2. Если и изоморфны, то => графы и также изоморфны. Таким образом, магистральная сеть, состоящая из n узлов и m магистралей может быть описана матрицей инциденций А размерности n*m

51. Построить коммутатор по схеме сети косвенного двоичного n-куба (сеть Клоса).

Рассмотрим один из примеров построения коммутатора по схеме двоичного куба. Пусть А – коммутатор, у которого:

U принимает 2 значения:

– логика соединение входных и выходных полюсов.

, где – элементарная матрица переключений.

51. Построить двухкаскадный коммутатор компьютерной сети.

Построим двухкаскадный коммутатор:

Последовательность действий заключается в постановке этого элементарного коммутатора:

Матричная запись уравнения:

Матрица переключений двухкаскадного коммутатора:

.

Придавая управляющим сигналам 0 или 1 можно подключать любой входной полюс к любому выходу.

Управляющие сигналы	Коммутация вх. и вых. полюсов	Матрица переключений
0	0	0	0
1	1
2	2
3	3
1	1	0	3
1	2
2	1
3	0
0	1	0	2
1	3
2	0
3	1
1	0	0	1
1	0
2	3
3	2

52. Совместное исследование параллельных КС и алгоритмов.

Адаптация КС к алгоритму(так звучит в лекциях)

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

Проблема отображения формулируется в терминах графов и сводится к проблеме изоморфности графов. Эта задача близка к сужению полосы в разреженных матрицах.

Мат. формулировка задачи: вводится проблемный (программный) граф

, где узлы Vp – соответствуют программным модулям, а дуги Ep – обозначают связи между модулями.

Вводится также Ga(Va, Ea), где Va – мн-во процессоров; Ea – связи между процессорами.

; Gp(x,x)=0 ;

между x и y дуга

Аналогично с Ga

Предполагается |Vp|=|Va| .

Если |Vp|<|Va| , то в мн-во Vp можно ввести число формальных вершин. Если |Vp|>|Va|, то не рассматриваем.

Отображение мн-ва модулей алгоритма на мн-во процессоров записывается

Качество отображения определяется количеством совпадений дуг программного и процессорного графов. Это число называется кординальностью отображения и обозначается как |fm|.

Gp(x, y)=1, если x и y в программном графе связаны одной дугой.

fm(x) и fm(y) обозначают процессоры, на которые отображены алгоритмы x и y.

процессоры соответствуют алгоритмам x и y и связаны.

Таким образом выражение под знаком суммы равно 1 только когда дуга, связывающая 2 модуля программы, совпадает с дугой, связывающей 2 процессора.

При суммировании каждый процессор считается дважды поэтому коэф ½.

Необходимо выбрать функцию fm с максимальной кординальностью среди (|Vp|) возможных функций.

53. Диаграммы Ферре и инверсии в бинарных последовательностях

Прямоугольник с α (строки) *β (столбцы) квадратами одинакового размера.

Разбиение

,

,

,

2.

Разбиению n, имеющему диаграмму Ферре α*β поставим во взаимное однозначное соответствие последовательность, элементами которой являются 0 и 1. Для этого, из правой верхней вершины прямоугольника построим траекторию – «огибающую диаграммы Ферре». Она проходит по верхней стороне прямоугольника и затем движется на заштрихованной части диаграммы Ферре. На каждом шаге, если траектория касается горизонтальной стороны квадрата, то «0», а если вертикальной, то «1».

Бинарная последовательность имеет длину α+β. Будет α «0» и β «1». Число «0» правее «1» называется числом инверсий.