Оглавление (стр. 4 )

Каждая часть входит в одну группу; пустые группы исключаются.

Если разбиение вложимо в , то будем записывать это, используя обозначение включения множеств:

Элементарные свойства разбиений:

каким наиб быстрым способом можно определить вложимость?

,

Если выясняется, что , то k не вложимо во второе. Это утверждение лежит в основе экстремального подхода к построению быстрого способа проверки вложимости.

31.Ранговое условие вложимости; пример использования.

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

Теорема.

Пусть t является тем наименьшим t, при котором , тогда .

Следствие: если - наименьшее n, при котором , то

32.Принцип полного размещения; пример использования.

Пусть и дано r, все – натуральные числа. Наименьшее , при котором разбиение к вложимо в разбиение этого n на не более чем r частей.

Следствие: если для натуральных чисел выполнено условие и через обозначено наибольшее r, при котором каждое разбиение r на n частей вложимо в разбиение , то

Искомое r согласно принципу полного размещения есть необходимый целый корень неравенства

33.Вложимость с ограничениями; пример использования.

Иногда требуется гарантировать вложимость разбиения не во все разбиения чилс n на r частей, а только в некоторые. Экстремальный результат, гарантирующий вложимость фиксированного разбиения уже не во все разбиения данного ранга можно представить в виде следующего утверждения:

пусть - наименьшее n при котором каждое разбиение этого n на r частей такое, что , обладает тем свойством, что , тогда .

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

Особенностью распределения памяти в КС с сегментной организацией программ и данных (модель 2). Приведите пример.

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

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

Удовлетворение любого запроса на память реализуется последовательным выполнением 2 процессов:

- процесса поиска непрерывных участков адресного пространства не меньшего, чем размер запроса;

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

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

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

Понятие вложимости разбиений является интерпретацией процесса удовлетворения запросов свободной памяти КС.

34.Комбинаторная модель для оценки необходимого размера памяти КС (модель 4). Приведите пример.

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

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

При пиковых нагрузках КС должна оставаться работоспособной.

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

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

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

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

Пусть имеется m групп запросов на выделение памяти. Размер j-ой группы соответствует числу разбиений:

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

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

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

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

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

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

, где узлы 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|) возможных функций.

39.Классы характеристик КС.

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

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

Под [n, m]-сетью будем понимать связанный граф с числом вершин и числом ребер

Требование однородности позволяет ограничиться сетями без петель и кратных ребер с минимальной валентностью (p) узлов, равной 2

Если m=n, то [n, m]-сеть представляет собой кольцо: для все n абсолютно однородно.

Если , то получается -сеть, является полным графом, у которого для любого i.

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

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

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

Граф ресурсов – граф G – вершины ресурсы, ребра связи между ними.

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

Определите в узле КС и в КС (структура КС условно изображена на рис).

Решение:

Диаметр – максимальное расстояние, определенное на множестве кратчайших путей между парами вершин структуры КС: , где - расстояние, т. е. минимальное число ребер, образующих путь из вершины i в вершину j;

Средний диаметр узла , где – мода узла – число вершин, находящихся на расстоянии l от любой выделенной вершины. Средний диаметр в КС

Итого: N=2, d=1, , ,

Понятие о сложности сети КС. (?)

Сложность сети растет с ростом числа составляющих элементов. Для связной сети n(число ребер)≤m(число узлов)+1, а связные сети максимальной однородности при m(число узлов)>2 представляют собой кольца с числом узлов равным числу ребер. Для неориентированной сети в качестве показателя сложности можно использовать показатель однородности ее элементов.

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

Сложность сети также зависит от взаимосвязи элементов. Взаимосвязь можно охарактеризовать числом l=m-n.

Сложность сети определяется и числом элементов и их взаимосвязью по валентности узлов (она же степень вершины – количество рёбер, инцидентных вершине v).

Сложность сети обычно тесно связана с её стоимостными характеристиками: суммарная стоимость элемента сети , С1 и С2 – стоимость узла и канала.

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

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

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

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

Граф ресурсов – граф G=(X, Y), Х (множество вершин) – ресурсы (включая резервные), Y={yi} – связи между ними. Граф G является направленным, если ребра ориентированы, и помеченным, если каждой вершине xi приписано число ti – тип ресурса.

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

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

Управляющие сигналы U управляют так, что x1, …, xn и yi взаимно коммутируются требуемым способом.

Далее будем полагать, что xi и yi подключаются в соответствии двунаправленным каналом i-ого процесса.

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

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

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

Наиболее распространенной является сеть Клоса (построена на основе двоичного n-куба).

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

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

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

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

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

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

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

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

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

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

.

Придавая управляющим сигналам 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

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

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

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

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

, где .

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

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

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

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

, где T – наработка на отказ, t – заданное время.

Аналогия с функцией надежности – функция ненадежности (вероятность отказа): . Из определения функции или . Если заданное время произвольное, то тогда , следовательно мерой Р может выступать значение Q, т. е. чем больше Q, тем меньше надежность.

Количественная надежность сети – вероятность разрушения связей сети.(?/Дальше в лекциях пробел)

Надежность кольцевой структуры КС (для сети [n,2]).

Рассчитаем надежность кольцевой структуры:

Если занумеровать узлы кольца так, чтобы связи между узлами задавать таблицей пар: , то вероятность отказа связей между узлами i и j будет определяться зависимостью: , при изменяется от 1 до .

Тогда достаточно определить вероятность отказа связей между узлами 0 и i=1,2,…l=[n/2]. Между этими узлами существует 2 пути:

1: , (i-1) промежуточных узлов

2: , n-i ребер.

– отказ узла, – отказ линий связи.

– для первого пути.

– для второго пути.

Вероятности и вероятности разрыва связи. Для того, чтобы разорвать связи между узлами 0 и I, нужно разорвать оба пути:

. Дальше найдем максимум.

При i=l выражение достигает максимума.

При n=2l получаем выражение:

Q – это глобальная, Q1 – реберная, Q2 – узловая.(вроде так…)

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

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

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

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.  достаточно связей между ресурсами.

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

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

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

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

, где и из определения сетей m=n+l.

– дополнительная относительная стоимость.

Для КС со структурой кольцо l=0 и A=0.

А для КС со структурой полный граф:

Вес кратных ребер : .

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

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

Функция стоимости:

.

– стоимость КС.

– тип топологической структуры

– число вершин (узлов) в топологической структуре.

– центральный процессор.

– стоимость канала связи коммутируемой сети между двумя узлами

–стоимость подключения процессора к сети

– число каналов связи подключенных к узлу (валентность)

– число ребер структуры КС.

Когда

– среднее число сообщение в узле i.

– средняя скорость сообщений в узле i/

– среднее время обслуживания сообщения в узле i.

– доля (вероятность)занятости узла i.

– плотность потока сообщений в узле i.

Когда число сообщений в КС становиться большим, занятость i→1:.

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

Для упрощения анализа, пусть все процессорные элементы обслуживают сообщения в течение времени равному , а линии связи заняты сообщениями в течение .

Учитывая однородность, считаем, что в дальнейшем каждая вершина с номером i имеет одну и ту же вероятность генерации сообщений. Функцию можно рассматривать как одну из метрик производительности систем. Среднее число обращений к каждому обрабатываемому процессором элементу, при условии, что число узлов n, предполагаем что отслеживается работа некоторого узла сети и (n-1) его адрес, полагаем:

что – число узлов, которые достижимы из произвольного узла при движении по кратчайшим путям и состоит из l ребер, кратным NT. Тогда среднее число ребер, через которые проходят сообщения: , lmax – max число ребер, которые должны пройти сообщения.

Среднее число ребер: .

.

Тип тополог. структуры	Число узлов	Число связей	Число ребер
общая шина	n	n	n
полный граф	n
двойное кольцо	n	4n	2n
кубически связанные цепи
Дерево

Тип тополог. структуры
общая шина
полный граф
двойное кольцо			, n чет. , n нечет.
кубически связанные цепи			, для D нечет. , для D чет
Дерево

n – Число узлов, D – размерность, k – глубина дерева..

Выбор топологической структуры производиться по критерию производительность/стоимость: