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

Задача безопасности и ограниченности сети Петри.

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

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

Безопасность – очень важное свойство для устройств аппаратного обеспечения. Если позиция безопасна, то число фишек в ней равно 0 или 1. Следовательно, позицию можно реализовать одним триггером.

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

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

Если и , тогда добавить к .

Если и , тогда добавить к .

Цель введения этой новой позиции - представить условие « пуста». Следовательно, и дополнительны; имеет фишку, только если не имеет фишки и наоборот.

Любой переход, удаляющий фишку из , должен помещать фишку в и наоборот.

Рис.1. Сеть Петри, не являющаяся безопасной

Рис.2. Безопасная сеть Петри, эквивалентная сети на Рис.1.

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

Безопасность – частный случай ограниченности.

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

Позиция является k-безопасной или k-ограниченной, если количество фишек в ней не может превышать целое число k.

Определение: Позиция сети Петри с начальной маркировкой является k-ограниченной, если для всех .

Граница k’ по числу фишек, которые могут находиться в позиции, может быть функцией от позиции (например, позиция может быть 3-ораниченной, тогда как позиция - 8-ограниченной). Однако, если позиция k-ограничена, то она так же и k’- ограничена для всех k’ >k.

Моделирование сетями Петри задач синхронизации при взаимодействии процессов в КС

Синхронизация.

Взаимосисключение – это метод создания таких программ, что одновременно не более чем 1 ресурс имеет доступ к разделяемому объекту.

Для предотвращения проблем такого рода необходимо обеспечить механизм взаимного исключения. Взаимное исключение это метод создания таких программ, что одновременно не более чем один процесс имеет доступ к разделяемому объекту данных. Участок кода, в котором осуществляется доступ к разделяемому объекту и который требует защиты от вмешательства других процессов, называется критической секцией. Идея состоит в том, что когда процесс готов выполнить свою критическую секцию, он сначала ждет, пока другой процесс не выполнит свою собственную критическую секцию. Затем он «блокирует» доступ к критической секции, не давая возможности никакому другому процессу войти в свою критическую секцию. Он входит в критическую секцию, выполняет ее и, выйдя из нее, освобождает ее для доступа со стороны других процессов.

Эта задача может быть решена сетью Петри, как показано на рис. 3.28. Позиция т представляет собой разрешение для входа в критическую секцию. Для того чтобы какой-либо процесс вошел в критическую секцию, он должен иметь фишку в р1 или в р2 соответственно, свидетельствующую о желании попасть в критическую секцию, а также должна существовать фишка в m, дающая раз- разрешение на вход. Если оба процесса пытаются войти в критическую секцию одновременно, то переходы t1 и t2 вступят в конфликт, и только один из них сможет запуститься. Запуск t1 запретит переход t2, вынуждая процесс 2 ждать, пока первый процесс выйдет из своей критической секции и возвратит фишку обратно в позицию m

.

В задаче о производителе/потребителе также присутствует совместно используемый объект, но в этом случае разделяемый объект точно определен и является буфером. Процесс-производитель cоздает объекты, которые помещаются в буфер. Потребитель ждет, пока объект не будет помещен в буфер, удаляет его оттуда и использует. Такая ситуация может быть промоделирована сетью Петри так, как показано на рис. 3.29. Позиция В представляет буфер, каждая фишка соответствует элементу данных, который произведен, но еще не использован. Один из вариантов этой задачи — это задача о нескольких производителях/нескольких потребителях. В этом случае несколько производителей порождают элементы данных, помещаемые в общий буфер, для нескольких потребителей. На рис. 3.30 представлено решение этой задачи в виде сети Петри. Эта сеть совпадает с сетью на рис. 3.29, Существует несколько вариантов задачи о чтении/записи, однако основная структура их остается неизменной. Имеются процессы двух типов: процессы чтения и процессы записи. Все процессы совместно используют общий файл или переменную или элемент данных. Процессы чтения не изменяют объект в отличие от процессов записи. Таким образом, процессы записи должны взаимно исключать все другие процессы чтения и записи, в то время как несколько процессов чтения могут иметь доступ к разделяемым данным одновременно. Задача состоит в определении структуры управления, которая не приведет к тупику и не допустит нарушения критерия взаимного исключения.

На рис. 3.33 иллюстрируется решение задачи в том случае, когда количество процессов чтения ограничено величиной п. Если в системе количество процессов чтения не ограничено, то только процессов могут выполняться в одно и то же время. Проблема возникает в том случае, если количество процессов чтения не ограничено и мы хотим предоставить возможность ограниченному количеству процессов читать одновременно. В этом случае можно утверждать, что возникает необходимость хранения количества читающих процессов. При инициализации каждого процесса чтения в счетчик добавляется единица, а по окончании процесса единица вычитается. Это легко моделируется позицией, в которой количество фишек равно количеству процессов чтения. Однако, для того, чтобы предоставить процессу записи возможность приступить к записи, необходимо, чтобы счетчик был нулевым, т. е. соответствующая позиция была бы пустой. В сетях Петри нет механизма, который бы осуществлял проверку на нуль неограниченной позиции1'. Таким образом, оказывается, что задача о чтении/записи с неограниченным числом процессов чтения не может быть решена с помощью сетей Петри. Это первый случай, когда мы столкнулись с тем, что сети Петри не способны моделировать все системы.

Анализ сетей Петри матричным методом

Второй подход к анализу сетей Петри основан на матричном представлении сетей Петри. Альтернативным по отношению к определению сети Петри в виде (Р, T, I, O) является определение двух матриц D+ и D-, представляющих входную и выходную функции. (Они эквивалентны функциям F и В определения Хэка сетей Пет - Петри, см. разд. 2.6.) Каждая матрица имеет m строк (по одной на переход) и n столбцов (по одному на позицию). Определим D-[j, i]= , a , D- определяет входы в переходы, D+ — выходы.

Матричная форма определения сети Петри (Р, T, D- , D+) эквивалентна стандартной форме, используемой нами, но позволяет дать определения в терминах векторов и матриц. Пусть e[j] — m-вектор, содержащий нули везде, за исключением j-й компоненты. Переход tj представляется m-вектором e[j]2). Теперь переход tj в маркировке μ разрешен, если μ > e[j] • D-, а результат запуска перехода tj в маркировке μ записывается как

D - составная матрица измененй, тогда для последовательности запусков имеем

Вектор называется вектором за - запусков последовательности i-и элемент вектора , — это число запусков перехода ti в последовательности . Вектор запусков, следовательно, является вектором с неотрицательными целыми компонентами.

Матричный метод анализа сетей Петри достоинства и недостатки метода

Для того чтобы показать полезность такого матричного подхода к сетям Петри, рассмотрим, например, задачу сохранения: является ли данная маркированная сеть Петри сохраняющей? Для того чтобы показать сохранение, необходимо найти (ненулевой) вектор взвешивания, для которого взвешенная сумма по всем достижимым маркировкам постоянна. Пусть— вектор-столбец. Тогда, если — начальная маркировка, а ' — произвольная достижимая маркировка, необходимо, чтобы. Теперь, поскольку ' достижима, существует последовательность запусков переходов а, которая переводит сеть из в '. Поэтому Следовательно, , поэтому.

Поскольку это должно быть верно для всех , имеем . Таким образом, сеть Петри является сохраняющей тогда и только тогда, когда существует такой положительный вектор w, что D • w = 0. Это обеспечивает простой алгоритм проверки сохранения, а также позволяет получать вектор взвешивания w. Развитая матричная теория сетей Петри является инструментом для решения проблемы достижимости. Предположим, что маркировка ' достижима из маркировки . Тогда существует последовательность (возможно, пустая) запусков переходов а, которая приводит из к '. Это означает, что является неотрицательным целым решением следующего матричного уравнения для х: . Следовательно, если достижима из тогда уравнениеимеет решение в неотрицательных целых; если уравнение ) не имеет решения, тогда ' недостижима из .

Границы возможности моделирования с помощью сетей Петри

Дейкстра определил свои Р - и V-операции над семафорами для обеспечения инхронизации и связи в системах взаимодействующих процессов [78]. Семафор может рассматриваться как целочисленная переменная, которая принимает только нтрицательные значения.

V-операция над семафором S увеличивает значение семафора на единицу: S = S + 1. Р-операция, наоборот, уменьшает S на едиединицу до тех пор, пока результат не становится равным нулю; при S = 0 процесс, прежде чем продолжать свою работу, должен ждать

момента, когда S можно будет уменьшить. Связь между семафорами и сетями Петри была выявлена в разд. 3.4.8.

Поскольку Р - и V-операции были предложены как механизм для решения всех задач синхронизации программ, то естественно возникает вопрос о полноте, т. е. об их способности к решению всех задач координации. Патил в 1971 г. [233] предложил доказательство того, что Р - и V-операции недостаточно мощное средство для решения всех задач координации. Его подход был весьма прост: он сформулировал задачу синхронизации, которая не может быть решена с помощью Р - и V-операций, — это задача о курильщиках сигарет.

Задача о курильщиках сигарет включает (по меньшей мере) четыре процесса, которые моделируют агента и трех курильщиков. Каждый курильщик непрерывно изготавливает сигарету и курит ее. Чтобы сделать сигарету, необходимы три составные части: татабак, бумага и спички. Один из курильщиков всегда имеет бумагу, другой — табак, а третий — спички. Агент обладает бесконечными запасами всех трех составных частей. Агент кладет две составные части на стол. Курильщик, имеющий третий недостающий, может сделать и закурить сигарету, сигнализируя об этом агенту. Тогда агент помещает другие два из трех инградиентов, и цикл повторяется.

Если семафор поставить в соответствие каждой составной части, задача о курильщиках формулируется в терминах семафоров. Семафоры первоначально равны нулю. Агент увеличит два из трех семафоров с помощью V-операций, а затем ждет семафора «сделано».

Соответствующий процесс курильщика уменьшает два семафора (с помощью Р-операций), а затем, произведя действия «сделать сигарету» и «закурить сигарету», увеличивает семафор, указывая «сделано». Задача заключается в том, чтобы разработать программу процессов курильщиков для того, чтобы определить, какой из трех процессов должен действовать в очередной момент. Действия агента фиксированны и не могут быть изменены.

Рис. 7.3 иллюстрирует очевидное «решение». Предположим, агент кладет табак и бумагу [V(t), V(p)]. Тогда курильщик с бумагой может взять табак [P(t)], а курильщик с табаком может взять бумагу [Р(р)], что в результате приводит к тупику. Патил доказал, что никакая последовательность Р - и V-операций не может корректно решить эту задачу. Это было показано с помощью доказательства того, что все Р- и V-«peшeния» могут быть промоделированы сетями Петри определенного вида (каждый переход имеет не более двух входов), но что решением является сеть Петри другого вида, и нет способа преобразовать сеть одного вида в сеть другого вида, не допуская возможности возникновения тупика.

Более конкретно ограничение на моделирование с помощью сетей Петри состоит в неспособности проверить на наличие точно определенной маркировки в некоторой неограниченной позиции и осуществить действие в зависимости от результатов проверки. Это ограничение общеизвестно как неспособность к проверке на нулевую маркировку в некоторой позиции, и поэтому это свойство известно как проверка на нуль [150]. Сети Петри не могут проверить неограниченную позицию на нуль. [Если позиция ограниченна, то нуль может быть выявлен. Для ограниченной позиции pi с границей k мы можем создать дополнительную позицию рi — такую, что сумма является константой, равной k для всех достижимых маркировок. Это позволяет нам проверить,

равняется ли нулю, проверяя, равно ли k (см. разд. 5.6).]

Сети Петри и их особенности

Def. Сеть Петри – четверка С=(P,T,I,O), где P – множество позиций, T – множество переходов, I – является входной функцией (отображением из переходов в комплекты позиций), O – выходная функция (отображения из переходов в позиции).

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

Возможно несколько подходов к использованию сетей Петри при проектировании и анализе ВС:

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

Ответы на вопросы №31,32,33 (для всех один и тот же рисунок)

Матрицы, представляющие входную и выходную функцию:

Составная матрица изменений:

Покажите, используя матричный метод анализа сетей Петри, что маркировка (0, 7, 0, 1) недостижима из маркировки (1, 0, 1, 0) для сети Петри, изображенной на рисунке.

Решение:

Начальная маркировка: , маркировка, которую нужно проверить на достижимость , тогда должен существовать такой вектор запусков , что

( должны быть неотрицательными целыми) Получим систему уравнений, которая не имеет решения

Маркировка недостижима.

Дана последовательность запусков переходов s = t3 t2 t3 t2 t1 сети Петри, изображенной на рисунке. Определите вектор запуска и маркировку m’ сети Петри.

Решение:

Последовательность s = t3 t2 t3 t2 t1 представляется вектором запусков t1 в s встречается 1 раз, t2 – 2 раза, t3 тоже 2 раза, тогда.

Из рисунка начальная маркировка . Маркировка

Определите является ли маркировка (1, 8, 0, 1) достижимой из маркировки (1, 0, 1, 0) для сети Петри, изображенной на рисунке. Найдите последовательность запусков переходов s.

Решение:

Начальная маркировка: , маркировка, которую нужно проверить на достижимость , тогда должен существовать такой вектор запусков , что

( должны быть неотрицательными целыми) Получим систему уравнений:

,

Что соответствует последовательности запусков s = t3 t2 t3 t2 t3 t2 t3 t2 t3. Маркировка достижима.

Понятия множества и мультимножества и операции со множествами и мультимножествами.

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

Атрибутными свойствами множества являются:

1.  различимость всех частей множества

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

3.  целостность множества

Различают 2 типа частей множества:

1.  элементы – неделимые и непустые части множества

2.  подмножества – остальные его части

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

Отказ от различимости элементов приводит к понятию мультимножества или комплекта.

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

Всякое мультимножество можно представить:

1.  его основанием, т е множеством всех его различимых элементов

2.  кратностями – числами повторений каждого элемента основания этого мультимножества.

В теории множетсв основным понятием является включение – это отношение связывает элементы и мн-ва и определяет, какие эл-ты являются членами какого мн-ва.

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

Обозначим число экземпляров X в комплекте B как

Над комплектами можно производить 4 операции:

Ниже перечислены основные операции над множествами:

пересечение:

объединение:

Если множества A и B не пересекаются: то их объединение обозначают также:

дополнение:

Операция дополнения подразумевает некоторый универсум (множество U, которое содержит A):

разность:

симметрическая разность:

Декартово или прямое произведение:

Разбиения чисел. Основные понятия и определения. Принцип Дирихле.

Разбиение натурального числа n, есть его представление неупорядоченной суммой натуральных слагаемых: . Эти слагаемые и называются частями, а их число r – рангом разбиения.

Композиция – это представление натурального числа n упорядоченной суммой натуральных слагаемых

n=6

ранг 1: 6=6;

ранг 2: 6=5+1, 6=4+2, 6=3+3;

ранг 3: 6=4+1+1, 6=3+2+1, 6=2+2+2;и т. д.

ранг 6: 6=1+1+1+1+1+1;

Как найти число композиций натурального числа n=r? Это будет число способов, которыми можно разместить r-1 черточек между n-1 промежутками.

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

Разбиение изображают при помощи векторной записи: .

или в сокращенной записи:

Часть присутствует в разбиении раз, т. о.

Всякое разбиение можно представить в виде , где - целое, неотрицательное число, которое указывает сколько раз число i присутствует в этом разбиении в виде части (-ранг разбиения)

Разбиение можно изобразить графически, с помощью графа Ферре (Ферррер)

Принцип Дирихле.

Если является наименьшим целым n, при котором в каждом разбиении этого n на r частей, найдется часть не меньшая, чем k, то тогда

Принцип Дирихле можно сформулировать в виде размещения (принцип ящика):

при любом размещении r+1 предметов по r ящикам, то найдется ящик с двумя предметами.

Вложимость разбиений.

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

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

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

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

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

,

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

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

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

Теорема.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Комбинаторная модель для оценки необходимого размера памяти КС (модель 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|) возможных функций.

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение:

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

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

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