Классификация параллельных КС по структурно-функциональным признакам (стр. 6 )

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

3) Диаметр КС – метрическая характеристика, введенная на графе для определения кратчайшего пути между наиболее удаленными вершинами.

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

4) Структурная связность КС – способность противостоять разбиению (разделению) графа структуры на независимые части. Структурные связи позволяют выявлять наличие обрывов, мосты и т. д.

В теории графов существует несколько определений. Эти определения осуществляются различными критериями. Расчет характеристик позволяет оценить структурные связи

5) Надежность КС – способность структуры КС обеспечить функциональность КС в течение заданного промежутка времени. Надежность – важная многопараметрическая характеристика структуры, определяется как надежностью элементов, так и схемой объединения элементов.

6) Живучесть (отказоустойчивость) КС оценивает сохранность частей структуры КС, обеспечивающих выполнение поставленной задачи. Живучесть имеет тесную функциональную связь с показателями надежности КС.

7) Стоимость КС – характеристика, оценивающая стоимость реализации структуры. Наилучшей считается структура, которая наиболее эффективна при заданной стоимости, либо обладает заданными параметрами при минимальной стоимости. Стоимость элементов КС предполагается независящей от времени.

Представленные характеристики дают возможность полно характеризовать структуру КС. Но точное и целостное решение задачи анализа структур с большим количеством узлов затрудняется из-за большой величины. Поэтому большинство работ при анализе направлены на отыскание методов, позволяющих решить проблему с точностью и минимальными затратами.

44. Абсолютно однородная сеть (определение, примеры)

45. Какую [n,m]-сеть можно назвать уницентральной?

Требование однородности позволяет ограничиться сетями без петель и кратных ребер.

Абсолютно однородные сети – те, которые не имеют различий по взимной связи с другими узлами и ребрами

Абсолютно однородная сеть должна быть инвариантной. Но этого недостаточно, в качестве примера рассмотрим сеть. В сети 1 можно выделить 3 подмножества узлов. В сети 2 можно выделить 4 подмножества. Для пополнения числовых инвариант однородного масштаба использован диаметр сети. Так как сеть является связным графом, то для любой пары узлов существует пусть (без циклов), соединяющих эти узлы. Так как в сети между узлами нет крайних связей, то путь можно обозначить цепочкой <xi1,xi1,…,xj>. Число ребер пути называется длиной пути. Тогда расстояние p(xi, xj) между узлами будет определяться как минимальная длина пути между ними. P(xi)=max(xi, xj) – это является диаметром сети в узле xi d=max p(xi) – диаметр сети r=min p(xi) - радиус сети

Узел xi, для которого p(xi)=p называется центром сети. Сеть, у которой все узлы являются центрами называется уницентральной.

Абсолютно однородная сеть обязательно является унивалентной. Число узлов m и ребер n в такой сети связано: (***). Из этого соотношения следует, что далеко не для всех типов удовлетворяющих неравенству существует унивалентная сеть. Среди сетей разных валентностей особое место имеют довалентные сети, узлы которых имеют 2 значения валентности: p и p+1. Для таких сетей справедливо следующее утверждение: для любых m и n можно построить довалентную сеть, обозначаемую как (n, p,r)-сеть. Пусть X0 – подмножество узлов сети, имеющей валентность p, X1 – подмножество узлов сети, имеющей валентность p+1. Обозначим мощность

Из (***) следует: . Отсюда, учитывая, что n0+n1=n 2m=np+n, следовательно .

Пример:

n=10 m=12 p=[24/10]=2 n1=rest 24/n=4 n0=6

46. Построить коммутатор по схеме сети косвенного двоичного куба

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

Пример осуществимости решения задач КС.

Рассмотрим один из вариантов построения КМ по схеме косвенного двоичного куба.

Здесь КМ: и -входные полюса;-выходные полюса. U-управляющий сигнал, принимает 2 значения:

=0: =1:

Запишем уравнение:

В матричной форме: ; ;

Матрицу М с 2 входными и 2 выходными полюсами будем называть матрицей переключений.

Каскадное переключение:

Выполним последовательно действия , учитываю предыдущие:

Остальные уравнения аналитическим образом:

Т. о. матрица переключений для 2 каскадного:

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

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

Повторяя операции можно получить Матрицу переключений для любых n.

Свойства матрицы М:

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

2. 

48. Понятие о сложности сети КС

Сложность сети растет c ростом числа составляющих ее элементов - узлов и ребер. Для связной сети число ребер не может быть меньше числа узлов без единицы, а связные сети максимальной однородности при числе узлов, большем двух, представляют собой кольца с числом узлов, равным числу ребер. Для неориентированной сети в качестве показателя сложности можно использовать показатель однородности ее элементов, определяемый с помощью числовых инвариантов. Сравнивая этот показатель для конкретной сети с заданным числом узлов n и ребер m с показателем максимально однородной сети с таким же числом элементов, можно определить, насколько данная сеть отличается от наименее сложной. Сложность сети зависит не только от числа элементов, но и от их взаимосвязи, которое можно охарактеризовать через разность числа ребер и числа узлов l = m - n.

Сложность сети зависит не только от числа элементов, но и от их взаимосвязи, определяемой по валентности узлов и максимально однородной двухвалентной сети. Сложность сети во многом определяет ее стоимостные характеристики. Суммарная стоимость элементов сети С1n + С2m, где C1 и C2 - стоимости оборудования узла и канала связи, задает средства, вложенные в создание сети и затрачиваемые на поддержание ее технической работоспособности.

49. Задача отображения множества программных модулей на множество процессоров.

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

Математическая формулировка задачи:

Введем программный граф , аналогично

Проблемный (программный?) граф можно рассмотреть как множество вершин Vp и функцию, такую, что

Если , то в множество Vp можно внести некоторое число вершин.

Если , случай сложен, не рассматриваем.

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

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

обозначают процессоры, на которые отображены задачи x и y.

При суммировании процессоры считаются дважды, следовательно множитель ½. Необходимо выбрать функцию fm с максимальной кардинальностью среди возможных функций

50. Проблемы адаптации структуры КС к алгоритмам решаемых задач в терминах теории графов

Основной задачей адаптация ВС к алгоритмам решаемых задач является обеспечение максимальной эффективности вычислительного процесса. Адаптация сводится к задаче изоморфного вложения сетей.

Изоморфное вложение - граф изоморфно вложим в граф , если в графе существует подграф, изоморфный графу.

Будем использовать понятие ВС – как совокупность ресурсов, которые задействуются при реализации задач.

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

Как саму ВС, так и выполняемые ею задачи, можно представить графом ресурсов.

Граф ресурсов – граф G=G(X, Y).

Вершины – ресурсы (включая резервные), а ребра - связи между вершинами.

Граф G – направленный, если ребра ориентированы и помечены. Если каждой его вершине приписано число ti – тип ресурса xi.

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

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

Будем говорить, что алгоритм А выполним на КС с именем S. Значит S содержит A, если А изоморфен некоторому графу S.

Переход к новому алгоритму требует поиска нового подграфа в графе S, изморфного А*.

Установление требуемых связей между ресурсами КС осуществляется с помощью коммутации.

Управляющие сигналы U управляют топологией коммутаторов так, что n входных сигналов Х и n выходных Y взаимно коммутируются требуемым способом.

Будем предполагать, что xi и yi подключаются к соотв. Двунаправленному каналу i-ой ВС, входящей в состав выч. системы.

Анализ процессов реконфигурации топологии позволяет исследовать возможности изменения связей между элементами ВС.

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

Сеть коммутации – множество взаимодействующих связей.

Для N входов и N* выходов существует N! четко определенных отображений от входов и выходов

Чтобы такие отображения не были пустые, сеть должна иметь столько же входов, сколько и выходов.

51. Диаметр и средний диаметр [n, m]-сети

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

Диаметр d – это максимальное расстояние, определяемое как

,

где dij – расстояние между вершинами i, j рассматриваемой КС. Расстояние dij есть минимальная длина простой цепи между вершинами i, j, где длина измеряется в количестве ребер между вершинами i, j.

Средний диаметр определяется как

где p – расстояние от текущей вершины до выделенной (произвольной),

np – число вершин, находящихся на расстоянии p от выделенной (мода).

Дополнительно: Так как сеть является связанным графом для любой пары узлов, существует путь без циклов, соединяющий эти узлы. Число ребер в пути естественно назвать его длиной. Тогда расстояние r(xi, xj) между узлами будет определяться как минимальная длина пути между ними.

Напомним, что является диаметром сети в узле xi, величина - диаметром, а величина радиусом сети. Узел xi, для которого назовем центром сети. Тогда, сеть, у которой все узлы являются центрами, называется уницентральной.

52. Надежность сети КС

53. Надежность кольцевой структуры КС

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

Под надежностью КС понимают свойство КС выполнять все заданные функции при определенных условиях эксплуатации в течение заданного времени с сохранением значений основных параметров в заранее установленных пределах.

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

Основной количественной характеристикой надежности является P(t), которая определяется вероятностью безотказной работы КС, т. е. вероятностью того, что при заданных режимах и условиях эксплуатации в течение заданного времени работы КС отказ в ней не возникает

Р(t) = Р{T > t},

где Т - наработка на отказ КС; t - заданное время; Р{А} - вероятность события А, в данном случае событие А состоит в том, что T > t.

По аналогии с функцией надежности введем функцию ненадежности (вероятность отказа) Q (t) = Р{Т £ t}.

Из определений функций P(t) и Q(t) следует P(t)+ Q(t) = 1 или P(t) = 1 - Q(t).

Если заданное время t произвольно, то Р = 1 - Q. Из последнего равенства следует, что мерой Р может служить Q: чем выше значение Q, тем хуже надежность КС.

Количественно ненадежность сети определяется вероятностью разрушения связей между узлами сети, если известны вероятности отказов линий связи и узлов коммутации. При топологическом проектировании сетей естественно полагать, что отказы каких-либо узлов и ребер являются независимыми случайными событиями, характеризуемыми одинаковыми для всех узлов (q1) и ребер (q2) вероятностями появления. Если в этих предположениях вычислить вероятности Qij отказа связи между узлами сети i, j = l, 2, ..., n, то надежность сети можно определить выражением

(4.9)

На практике часто оказывается удобным рассматривать отдельно реберную (q1 = 0) и узловую (q2 = 0) надежности сети, определяемые через реберную Q2ij и узловую Q1ij вероятности отказа связи между узлами ij сети, когда соответственно отказывают только ребра или только узлы. Глобальные реберная Q2 и узловая Q1 оценки надежности сети могут быть определены аналогично (4.9).

Надежность – вероятность безотказной работы.

Q = 1 – P

Рассчитаем надежность кольцевой сети. Необходимо пройти сеть от 0 до i по часовой стрелки, либо против. Надежность будет равна:

q1 – отказ узла

q2 – отказ ЛС

Если n = 2l, i=l =>

Расчет надежности сложен даже для простых систем.

54. Отказоустойчивость (живучесть) топологической структуры КС

Живучесть – свойство систем адаптироваться к новой ситуации и противостоять неблагоприятным воздействиям, при этом выполняя свою целевую функцию, за счет изменения структуры и поведения системы даже при повреждении ее частей.

Есть след. подходы:

Создание модели живучести на основе анализа взаимодействия системыв и среды Определение предельной живучести КС и вероятностный анализ сохранения системой своих функций Определение степени живучести КС по отношению к некоторому стандартному возмущению

Живучесть системы должна проектироваться исходя из возможного кртерия и круга задач.

Уровни проектирования живучести

Микроуровень – улучшение качества элементов Подсистем – вопросы компоновки и избыточности элементов Макросистем – организация подсистем и блоков

Если есть задача, чтобы система работала при одном отказе с вероятностью 1, то необходимо трансформирование системы.

Живучесть – многокритериальная задача оптимизации.

Модели анализа живучести

Модель внешней сети Модель взаимодействия аппаратных средств системы Модель взаимодействия компонент ПО Модель контроля и диагностики аппаратных и программных средств Модель вычислительного процесса при решении задач Модель надежности

Будем говорить, что алгоритм А выполним на КС с именем S, если структура А изоморфна некоторому подграфу S, т. е. суцествует отображение A->S.

Удаление из графа S любых к-вершин - к-кратная неисправность. Система S является толерантной относительно алгоритма А и неисправности F…

Система толерантна относительно мн-ва алгоритмов А1…АN и множества неисправностей F1..Fq, если Аi выполним системой при всех Fj.

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

55. Связь стоимостных характеристик и топологии КС

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

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

При топологическом проектировании сетей технические характеристики узлов и ребер, составляющих сеть, одинаковы. В этих предположениях, задав стоимость узла C1 и стоимость ребра С2, получим стоимость [n, m]-сети

При заданном n наименьшую стоимость имеет кольцо (n, 2), а наибольшую - полный граф (n, n-1)

Как правило, проектирование сети заключается в выборе числа ребер и распределении их между узлами так, чтобы получить требуемые значения надежности и пропускной способности. При этом удобно пользоваться относительной стоимостью Из определения сети следует, что m = n + l, тогда относительная стоимость будет иметь вид где и в качестве функции стоимости сети удобно использовать выражение

Для КС со структурой «кольца» - а для КС со структурой полного графа: и

Тогда для произвольной сети без кратных ребер

Функцию А(n, l) можно интерпретировать как относительную дополнительную стоимость сети.

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

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

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

57. Определите в узле КС и в КС

Мода узла (nl) – число узлов, находящихся на расстоянии l от выделенного.

;

;

;

58. Дайте определение реберного графа и постройте граф L(G), если граф G имеет вид:

Реберный граф Gl графа G имеет столько же вершин, сколько ребер у графа G. Ребро между двумя вершинами графа Gl существует тогда и только тогда, когда ребра графа G, соответствующие этим двум вершинам, смежны (т. е. инцидентны одной и той же вершине графа G).

59. Приведите определение и поясните особенности параллельных КС с магистральными связями.

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

Магистральная сеть КС представляет собой соединение 2х видов равноправных узлов – процессор и магистраль – общей шиной.

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

Для примера рассмотрены топологии и их особенности:

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

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

60. Приведите математическое описание магистрально-модульной КС.

Магистрально-модульная КС может быть описана реберным графом.

Реберный граф Gl графа G имеет столько же вершин, сколько ребер у графа G. Ребро между двумя вершинами графа Gl существует тогда и только тогда, когда ребра графа G, соответствующие этим двум вершинам, смежны (т. е. инцидентны одной и той же вершине графа G).

Магистральная сеть из n узлов и m магистралей может быть описана матрицей инцидентности (, если узлу i инцидентна магистраль j).

Магистральная сеть – пара конечных множеств (X, Y), , с установленными между этими множествами инциденциями матрицы . Если обозначить число магистралей, инцидентных i через pi (валентность узла), а число узлов, инцидентных магистрали j – qj (валентность магистрали), то для любой (n, m) магистрали можно записать:

В отличие от (n, m) сети, у (n, m) магистрали всегда есть магистральная сеть с транспонированной матрицей инцидентности.

Магистральные сети структурно эквивалентны гиперграфу. Их можно исследовать, используя p-сеть (кёнингово представление).

p-сеть (n, m) магистральной сети G c матрицей А называют (n+m, b) сеть с матрицей смежности:

p-сеть в кёнинговом представлении указывает на то, что это двудольный граф с числом узлов , .

61. Структура магистрально-модульных КС; особенности построения структур магистральных КС и их отличие от других типов структур компьютерных сетей?

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

Характеристики модулей делятся на основные и дополнительные.

Основные – числовые характеристики функции модуля (быстродействие процессора, объём памяти). Модуль коммутатора не имеет основных характеристик.

Дополнительные – одинаковы для всех модулей (p – надёжность, c – стоимость, w – энергопотребление).

Под основными модулями понимаются модули, влияющие на изменение эффективности ВС. Список основных модулей определяется составом задач, решаемых ВС и требованиями к их решению.

Под однородными понимаются модули одного наименования, имеющие одинаковые характеристики – основные и дополнительные.

Все модули разделены на две группы: совмещаемые (для повышения надёжности допускают аппаратное и программное резервирование (процессоры, модули обмена, модули связи)) и несовмещаемые (допускают только аппаратное резервирование).

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

Реберный граф Gl графа G имеет столько же вершин, сколько ребер у графа G. Ребро между двумя вершинами графа Gl существует тогда и только тогда, когда ребра графа G, соответствующие этим двум вершинам, смежны (т. е. инцидентны одной и той же вершине графа G).

C4 – цикл.