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

Введем обозначения:

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

Если система состоит из идентичных модулей, то функция h(r), будем записывать h(r), где

Функция связности h(r) так же обладает свойством монотонности: причём строгое неравенство для векторов понимается в том смысле, что для всех компонент этих векторов , причём хотя бы в одном из них имеется строгое неравенство.

28. Понятие о топологическом анализе структур КС.

Развитие современных информационных и телекоммуникационных технологий приводит к необходимости

фрактального моделирования и многокритериальной оптимизации КС [1,3,5].

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

соответствуют сетевые компьютеры, а ребрам – каналы связи [6]. При сравнительном анализе и

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

каналов связи, и критерии (признаки), отражающие наиболее важные аспекты функционирования КС.

Наиболее существенными критериями (признаками) эффективности КС являются

– надежность;

– стоимость;

– пропускная способность.

Базовыми топологиями КС будем называть совокупность следующих пяти типовых топологий:

– полноячеистая топология;

– кольцевая топология;

– топология «звезда»;

– линейная топология;

– смешанная топология.

Задача состоит в нахождении оптимальной топологической структуры проектируемой КС с учетом

описанных выше критериев (признаков).

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

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

Топологический анализ данных — новая область теоретических исследований для задач анализа данных (Data mining) и компьютерного зрения.

Основные вопросы:

·  Как из низкоразмерных представлений получать структуры высоких размерностей;

·  Как дискретные единицы складываются в глобальные структуры.

Основной метод топологического анализа данных:

·  Замена набора элементов данных некоторым семейством симплициальных комплексов в соответствии с параметром близости.

·  Анализ этих топологических комплексов с помощью алгебраической топологии, а конкретно новой теорией устойчивых гомологий.

·  Перекодировка устойчивой гомологии набора данных в параметризованную версию чисел Бетти, далее называемую штрихкодом.

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

Разбиение натурального числа 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 ящикам, то найдется ящик с двумя предметами.

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

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

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

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

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

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

,

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

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

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

Теорема.

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

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

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

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

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

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

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

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

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

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

34.Комбинаторные модели для исследования прцоесса распределеняи памяти КС.

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

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

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

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

Статическое распределение памяти – такое распределение, при котором I ->F (инф объекты – физич адреса) выбирается один раз до выполнения программы.

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

Стат. Распре-е инф-ее может применяться тогда, когда сведения о ресурсах и св-х ссылок программ имеются перед решением задачи(пр-мы). При использовании динамич распределения – наоборот.

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

Доп. Выделяемая часть памяти не использ и именно она определяет величину потерть в эфф-ти использования памяти в целом.

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

….т. е. сократив затраты проц. Времени на упр-е раср-ем памяти при сегментной организации можо повысить эфф-ть.

Поэтому все дальнейшие рассуждения – о распределении памяти с сегментнйо орг-ей программ и данных.

Сегментная орг-ия обладает следующими преимущствами перед страничной.

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

Облегчается управление пр-ми.

Исключаются потери в эфф-ти использования памяти изза округления размера запроса до принятого в система расзмера страницы.

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

==В любой момент времени фенцуионированя КС влияние внешней фрагментации на процесс распределения памяти характеризцется слеюущими парамтрами?

1-количество свободных/занятых участков памяти

2-размер свободных участков

3-суммарный размер своб\занятой памяти

Запросы на выделение памяти достаточно полно характеризуются слеюущими параметрами:

1-количество запросов в очереди на выделение памяти

2-тербования к размеру непрерывных участков адресного пространства

3-суммарный объем памяти

ПРИМЕР.. Q – р-р ОП КС. N – сумм р-р свободной памяти N принадлежит Z+, N<=Q, где Z+ - множетсво целых неотрицательных чисел.

Изза влияния внешн. Фрагментации память р-ра N окажется раздробленной на R участков. Такое состояние свободно памяти можно интерпретировать как вектор Z(N)=(n1,n2,….nR)

N=сумма от i=1 до R ni(n1>=n2>=…>=nR),

Где ni – размер итого свободного участка, принадлежащего Z+.

Два состояние свободной памяти: Z(N)=(n1…nR) Z’(n)=(n1’…nR’)

Будес считать различными, если они различны как векторы.

Аналогично любое состояние ханятой памяти характеризуется вектором g(D) = (d1….de)

Di – размер непрерывного итого участка занятой памяти. D=сумма di..

При моделировании запросов на выделение своб. Памяти из Z(N) предполагается, что они могут поступать одновременно, т. е. группами g(K)=(k1…..kt)

Запросы поступают по одному или группами, Ю где Ki – треб р-р свободной памяти для i-го запроса.

Группу запросов интерпр как в-р q(K).

Элементы ni di kj векторов Z(N),g(D), q(K) можно интепретировать как разбиение чисел N, D,K, t.e.

P(N)=(n1…nR)

P(K)=(k1…kR)

P(D)=(d1…dR)

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

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

Алгоритм мб любым, как ипорядок обслуживания.

Т. о. 1я модель является адекватной.

С помощью множества разбиений можно описать множество всех возможных состояний фрагм-й свободной памяти.

Используя свойства множества разбиения числе, а именно

P(N1) объ P(N2) .. P(Nr)=0

Где P(Ni)-мн-во разб числа Ni<>Nj

Можно показать, что множество состояний фрагм-ой памяти кс р-ра Q опред множество разбиений чисел.

Разбиение соотв одноми из состояний свободной памяти КС р-ром Q.

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

…блабла про моедль 2 это в др вопросах.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть имеется 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|) возможных функций.

38.Влияние топологии на технические характеристики сетей.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение:

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

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

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

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-куба).

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

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

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

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

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

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

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

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

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