Размещено на http://www.allbest.ru/

1. Количественные характеристики, применяемые для оценок параметров ЭВМ

электронный транзитивный матрица дизъюнкция

1 МегаГц=1 МГц=1 MegaHz=1 MHz=106Гц - тактовая частота

1 ГигаГц=1 GigaHz=1 MHz=109 Гц - тактовая частота

Номинальное быстродействие (или быстродействие по Гибсону), учитывает операции с плавающей точкой.

А) 1MIPS(millions of instructions Pes Second)=106операций/секунду;

Б) 1GIPS=109 операций/секунду;

Быстродействие на текстовых наборах задач(учитывает операции с плавающей точкой)

1. 1 FLOPS (floaring point operation per second)=1 операции с плавающей точкой/секунду

2. 1 MegaFLOPS= 1 M FLOPS=106 FLOPS (миллион)

3. 1 GigaFLOPS=1 G FLOPS=109 FLOPS (миллиард)

4. 1 TeraFLOPS=1 T FLOPS=1012 FLOPS (триллион)

5. 1 PetaFLOPS=1 P FLOPS=1015 FLOPS

Емкость памяти ВС (вычислительных систем):

1. 1 KiloBit=1 Килобит=1 Кбит=1024 бит=210бит;

2. 1 KiloBуtе=1 Килобайт=1 Кбайт=1024 байт=210байт;

3. 1 MegaBit=1 Мегабит=1 Мбит=1024 Кбит=220бит;

4. 1 MegaBуtе=1 Мегабайт=1 Мбайт=1024 Кбайт=220байт;

5. 1 GigaBit=1 Гигабит=1 Гбит=1024 Мбит=230бит;

6. 1 GigaBуtе=1 Гигабайт=1 Гбайт=1024 Мбайт=230байт;

7. 1 TeraBit=1 Терабит=1 Тбит=1024 Гбит=240бит;

8. 1 TeraBуtе=1 Терабайт=1 Тбайт=1024 Гбайт=240байт;

9. 1 PetaBit=1 Петабит=1 Пбит=1024 Пбит=250бит;

10. 1 PetaBуtе=1 Петабайт=1 Пбайт=1024 Пбайт=250байт;

1. 1 bound=1 бод=1бит/сек

2. 1 byte/S=1 байт/сек

3. 1 Kilobound=1 Kbound=1Килобод=1 Кбод=103 бод

4. 1 Kilobyte/S=1 килобайт/сек=1 Кбайт/сек=103байт/сек

5. 1 Megabound=1 Mbound=1Мегабод=1 Мбод=106 бод

6. 1 Megabyte/S=1 мегабайт/сек=1 Мбайт/сек=106байт/сек

7. 1 Gigabound=1 Gbound=1Гигабод=1 Гбод=109 бод

8. 1 Gigabyte/S=1 гигабайт/сек=1 Гбайт/сек=109байт/сек

2. Современные ЭВМ

102 TFLOPS - быстродействие;

1000 Гб - память;

103 - пропускная способность;

Процесс совершенствования систем обработки данных развивался по трем направлениям:

1. Совершенствование элементной базы

А) использование БИС с увеличенной плотностью активных элементов (транзисторов) на 1 площади и скоростью их срабатывания;

Б) внедрение в БИС опто-электронных элементов;

В) перевод БИС на работу в оптическом диапазоне;

2. Совершенствование архитектуры СОИ:

А) сокращение + доступа к обработанным данным;

Б) уменьшение + выполнение инструкции СОИ;

В) создание архитектур, позволяющих реализовать вычисления.

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

Определение Коллектив аппаратно-програмных вычислений составляет в сущности ВС.

W={K,A}

K- описание конструкций ВС;

А- алгоритм работы коллектива вычислителей;

K={M,S}

М- множество вычислителей;

М={mi}, i=0,..., N-1

S - структура сети связей между вычислителями.

В конструкцию К закладываются следующие принципы:

A) Параллелизм при обработке информации, т.е. организация вычислений одновременно на множестве вычислителей М с организацией в сложной необходимости обмена данными через сеть S.

Б) Программируемости необходимой конфигурации сети S.

В) Однородность конструкции К, обеспечивающую высокую технологичность производства ВС.

Структура коллектива вычислителей представляется в виде графа V, вершине которого сопоставлены вычислители mi, а ребра - связи между ними.

Граф вычислителей V i = 0, … , N-1

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

,

где dij - расстояние между вершинами i, j рассматриваемой КС. Расстояние dij есть минимальная длина простой цепи между вершинами i, j, где длина измеряется в количестве ребер между вершинами i, j. Например, на рис. 1(а) длины между вершинами (0,5) есть 3 ((0,1),(1,2),(2,5)), 2 ((0,1),(1,5)), 2 ((0,4),(4,5)), 3 ((0,3),(3,4),(4,5)), 3 ((0,3),(3,6),(6,5)), 2 ((0,6,),(6,5,)) и др., длина которых больше 3-х. Следовательно, расстояние dij равно 2.

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

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

3. Наиболее популярные схемы ВС. "Общая шина", "линейка", "кольцо", "тор", "решетка"

Способы реализации обмена между вычислителями:

a) Реализация обмена через общую шину:

Недостатки: задержки, ненадёжность, трудоёмкость реализации.

b) “Линейка”.

Недостатки: отказ вычислителя - отказ линейки.

Достоинства: просто, дёшево.

c) “Кольцо ”, лучше линейки.

d) “Решётка”, по сравнению с кольцом и линейкой имеет преимущество: много альтернативных путей обхода - надёжность.

4. Структура ВС типа двумерный тор, n-мерный двоичный гиперкуб

e) “Двумерный тор”

Сложные:

f) n-мерный двоичный гиперкуб ( nD-куб)

g) n-мерный двоичный тор.

h) Обобщенный nD- куб.

i) Обобщённый nD-тор.

j) n-мерная циркулянта.

1) Двоичный n-мерный гиперкуб описывается следующими соотношениями:

- вершины имеют номера N=2p, p=0,1,…n-1;

- каждая вершина V задана двоичным числом

;

- между вершинами V и U проводится ребро, если где - операция сложения по mod 2.

На рис. 1 представлены булевы кубы размерностей 2, 3, 4.

5. Реализация обмена информацией в структуре типа "обобщенный nd-куб" и "nd-тор"

Обобщенный гиперкуб размерности n

По каждой координате i, i=1,…,n вводятся точки 0,1,...,Ni-1, где Ni - размерность куба по координате i. Множество вершин графа КС задается декартовым произведением . Две вершины соединяются ребром, если декартовы произведения отличаются друг от друга для рассматриваемой точки и текущей на 1.

Для 3-х мерного куба образуются точки по координатам (0,1,2,3), (0,1,2), (0,1) и соответствующие декартовы произведения:

(0,0,0), (0,0,1), (0,1,0), (0,1,1), (0,2,0), (0,2,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1), (1,2,0), (1,2,1),

(2,0,0), (2,0,1), (2,1,0), (2,1,1), (2,2,0), (2,2,1), (3,0,0), (3,0,1), (3,1,0), (3,1,1), (3,2,0), (3,2,1).

Ребра проводятся между вершинами (0,0,0) и (0,0,1), (0,1,0), (1,0,0). Вершина (0,0,1) соединяется с вершинами (1,0,1), (0,1,1), (0,0,2) и т.д. Пример представления этой структуры показан на рис. 2.

Схема представления обобщенного 3-х мерного гиперкуба .

На основе кубических структур КС введены торы (для одномерного случая - кольцевые структуры). N-мерный тор образуется из n-мерных булевых кубов или обобщенных кубов построением ребер между отдельными или всеми вершинами, прилегающими к граничным плоскостям. Так, если КС построена из обобщенных 2D кубов (3х3), то ребра могут быть проведены, как показано на рис. 3(а). Степень вершины равна 4. На рис. 3(б) показано построение 3х мерного тора из обобщенного 3D куба (3x2x2) со степенью вершины равной 4.



КС типа двумерный тор (а) и трехмерный тор (б).

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

6. Структура ВС типа циркулянта и типа Л(N,v,g)

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

удовлетворяет условию :



q- мн-во образующих чисел таких, что имеют НОД=1, т.е. все q взаимно просты.

Вершины соеденены по закону , т.е. (mod N) - сложение по модулю N.

Матричный вид Хордовое кольцо

Структура выч сети типа Л(N,v,g) описывается как -

, i=0……..N-1

S- симметричная выч сеть описыв матрицей смежности из мн-ва L

N-вершины, v - степень вершин, qобхват графа кратчайший простой цикл.

Пример:

Л(8,4,4) граф d=2 <d>=1,43

Л(16,4,4) граф d=3 <d>=1,91

Л(32,3,7) d=5 <d>=2,94 Л(32,4,5) d=4 <d>=2,38

1 2 3 4 2 3 4 5

2 1 5 6 1 6 7 8

3 1 7 8 1 9 10 11

4 1 9 10 1 12 13 14

2 11 12 1 15 16 17

2 13 14 2 16 18 22

3 15 16 2 21 26 29

3 17 18 2 19 30 32

4 19 20 3 19 23 25

4 21 22 3 26 27 30

5 22 29 3 20 21 31

5 17 23 4 20 24 29

6 24 25 4 23 27 28

6 15 27 4 21 22 32

7 14 30 5 21 25 27

7 23 32 5 6 28 29

8 12 26 5 18 19 26

8 19 29 6 17 31 32

9 18 31 8 9 17 20

9 26 27 8 12 19 22

10 23 28 7 11 14 15

10 11 30 6 14 20 27

12 21 24 9 13 29 32

13 23 31 12 25 26 31

13 16 26 9 15 24 30

17 20 25 7 11 17 24

14 20 28 10 13 15 22

21 27 32 13 16 30 31

11 18 32 7 12 16 23

15 22 31 8 10 25 28

19 24 30 11 18 24 28

16 28 29 8 14 18 23

7. Структура ВС типа «бинарное дерево», мультидерево глубины n и ширине k

Структура ВС типа «бинарное дерево - глубины n описывается графом

, i=0……..N-1

S* бинарное дерево глубины n, r (0….n-1) - r рангов

вершин в каждой, так, что каждая вершина ранга r (0<r<n-2) соединяется со своей парой вершин ранга r+1

r=2

Структура ВС типа «мультидерево глубины n и ширине k»

n,k,

описывается графом

, i=0……..N-1

S* состоит из k двоичных деревьев , объедененных с помощью колец .

Корнев вершин (I=1…k) кажд из деревьев соединена ребром с вершиной I={1…k}.

Вершины …. образуют кольцо . Второе кольцо образуют вершинами листьев всех K деревьев (всеговершин)

8. Характеристика коммутаторов ВС

Коммутаторы в ВС

1.простые в временным разделением

2.простые с пространственным разделением

3.сосредоточ составные коммутаторы

4.распределены составные коммутаторы

1. - общая шина (простые обор, надежны)

- задержки при организации обмена ; работает лишь 1 арбитр шины,

синхронизация сигнала «запрос-ответ».

К=1 (S1,S2,S4,S8) - простые коммутаторы 1 типа

К=2 (S3,S5,S6,S9,S10,S12) коммутаторы 2 типа

К=3 (S7,S11,S13,S14) коммутаторы 3 типа

K=4 (S13) коммутаторы 4 типа

Комбин использование коммутаторов Клоза/бапьян -сети

Nвх , nвых (S15) сущ единств путь от каждого вх к

кажд выходу S5, S10

Получ рапространение рапсредкоммутаторы

Можно подключить пам/проц по шине (обычно размерность коммут 3*3)

Пример (Микрон Т)



Вершины Bj соединены через 2 и через 3.

9. Архитектурные свойства вычислительной сети и описание процессов ее функционирования

Описание процесса функционирования ВС.

Описание общим алгоритмом А.



Алгоритм отображен программой

Pi - ветвь прогр, обслуживающ i-ый узел.

Данные:

Данные на узле

композиция

Вычислитель:

алг взаимод с др процессорами

алг обр данных и управление

Архитектурные св-ва ВС.

1.Масштабируемость (обеспечивает спос к наращиванию, что дает возм в течении длит времени делать систему адекватной задаче)

2.Универсальность

3.Производительность

4. Реконфигурируемость (2 класса систем: настр на класс задач и с прогр …)

5.Надежность/живучесть

6.Самоконтроль/самодиагностика.

10. Надежность и живучесть вычислительной сети

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

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

Полный отказ ВС - событ, сост в том, что ВС теряет возм вып || программ.

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

Важный фактор - самодиагностика.

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



11. Схема обмена информацией между ветвями параллельных алгоритмов

Пусть Р программа состоит из n ветвей. Ясно, что обмен информацией между ветвями P программы может быть реализован с помощью дифференциального обмена, при этом обмене производится передача из одной ветви в любую другую ветвь или, что тоже самое, из одного вычислителя к другому, от передатчика к приёмнику.

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

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

1-трансляционный.

2-трансляционно-циклический.

3-конвеерно-параллельный.

4-колекторный.



1)При трансляционном обмене (one to all broadcast) осуществляется передача одной и той же информации из одной любой ветви во все ветви параллельного алгоритма.

2)Трансляционно-циклический (all to all broadcast) реализует трансляцию информации из каждой ветви во все остальные, следовательно, если трансляционный обмен выполняется за 1 такт, то трансляционный цикл за n тактов.

3)Конвейерно-параллельный обмен, обеспечивает передачу информации между соседними ветвями, за 2 такта. например, при чётном n в первом такте осуществляется передача информации из ветвей Р1 , Р3 ,… , Рn-1 в ветви Р2 , Р4 , … , Рn , во втором такте наоборот.

4)коллекторный Это по сути инвертированный трансляционный обмен. Вычислитель передатчик становится приемником. В одну ветвь собирается информация из l? n ветвей. Такой обмен требует 1 тактов и реализуется как последовательность 1 дифференцируемых обменов.

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

Тип обмена	ДО	ТО	ТЦО	КПО	КО
Частота использования	2%	17%	40%	34%	7%



12. Структурные характеристики ВС

1) Структурные задержки при передаче информации между узлами (характеризуется диаметром и средним диаметром).

2) Структурная коммутируемость ВС.

К(G, S, S') = {Kn (G, S, S')}, n= Є {1, 2, … ]N/2[ }

Координата Кn - вероятность реализации в системе при заданной структуре сети G и коэффициентом готовности вычислителя S и S'(коэф готовности сети G) одновременных непересекающихся межмашинных взаимодействий.

При заданной структуре сети G и коэф готовности вычислителя S и коэф готовности сети S'.

n- одновременно непересекающихся межмашинных взаимодействий.

3) Структурная живучесть ВС. Оценивается вектор функцией.

L(G, S, S') = {Lr (G, S, S')}, r= Є {2, 3, …, N}.

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

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

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

При синтезе структур ВС может быть поставлена задача в следующем виде:

ищется maxLr(G, S, S') = Lr(G*), при заданных значениях N,r,V,S,S'.

V-кол-во связей вх/вых из узла.

Найденная структура сети G* считается оптимальной.

Делается упрощённая задача:

Для графа Dn L(N, v, q)- графов, Dn - граф семейства циркулянт.

При решении задач используются 2 гипотезы:

1) Структура G*, при которой достигается Ln(G*) максимум живучести Lr(G*)

2) Структура с минимальным диаметром относится к G*, т.е. обладает максимальной структурной живучестью. На практике, обычно, оптимальной называются структуры G*, имеющие при заданном порядке N, степени вершины v, минимальный диаметр.

13. Пример решения задачи умножения матриц с помощью вычислительной сети

A[1:N , 1:K] Ч B[1:K, 1:M] = C[1:N , 1:M]

, i=1,…,N , j = 1,…,M (1)

Пусть N>>n , M>>n , K>>n , n - количество процессоров.

Методика:

Исходные матрицы А и В разрезают на n равных горизонтальных и вертикальных полос.

Для 1-ого вычислителя: 1,2,…,] N/n [ , 1,2,…, ] M/n [ , где ] и [ ближайшее целое число.

] x [ - означает, что взято ближайшее целое число такое, что ] x [ ? x.

В 1-ом вычислителе

строки: (L-1) * ] N/n [ +1 ,

столбцы: (L-1)*]M/n[+1,…,L*]M/n[.

Для последнего n-ого вычислителя

строки: (n-1)*] N/n [ +1,…,n*]N/n[,

столбцы: (n-1)*]M/n[ +1,…,n*]M/n[.

A X B = C

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

Сначала 1-ый вычислитель передаёт остальным вычислителям 1-ую строку из своей полосы матрицы А. После этого все вычислители, используя формулу (1) осуществляет параллельный расчёт ]M/n[ элементов первой строки матрицы С. Затем первый вычислитель рассылает во все остальные вычислителям вторую строку своей полосы матрицы и производится расчёт элементов 2-ой строки матрицы С и т.д. до тех пор пока 1-ый вычислитель не перешлёт все строки своей части матрицы А. После этого пересылками будет заниматься последовательно 2й, 3й вычислитель и т.д. до n-ого. Матрица С получается распределённой по вычислителям, причём в каждой будет своя вертикальная полоса (см. рис.). Итак, в следствии однородного распределения данных получены одинаковые ветви параллельного алгоритма. Однако, эти ветви используют различные части данных. Т.к. для каждой ветви своих данных недостаточно, то ветви вступают во взаимодействие (между ними осуществляется обмен информацией).

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

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

1) При параллельном выполнении программ окончание алгоритма зависит от составленного плана решения задачи, поэтому символ «терминатор» конца алгоритма исключим.

2) Не ограничивая общности рассуждений можно считать, что при изображении параллельных алгоритмов можно ограничиться логическим символом с двумя выходами “FALSE” и “TRUE”.

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

Алгоритм 1.

1. Разобьем последовательно алгоритм на N линейных участков, к=1,…,N, исключив при этом терминаторы начала, конца и ввода-вывода информации. Перенумеруем сначала участок при к=1. u1=1,…,u1. Так как первый блок является входом в алгоритм , то вычислим MV:={1}- множество входов в алгоритм.

2. Вычислим v1:=u1, u1:=u1+1.

3. Если u1> u1 , то проверим, все ли блоки имеют выходные связи.

Если да, то переходим к п. 6, иначе проводим связи из блоков, не имеющих

выходных связей, в блок u1 и переходим к п.6.

Если u1<= u1 , то выполняется следующий шаг.

4. Если блок u1 использует результаты работы блока v1, то проводим связь из v1 в u1 и переходим к п.2. Иначе выполняется следующий шаг.

5. Вычислим v1:=v1-1.

Если v1<>0 , то переходим к п.4, иначе принимаем u1 как еще один вход в алгоритм MV:=MV U {u1} и переходим к п.2.

6. k:=k+1.

Если k>N, то конец алгоритма, иначе анализируем следующий шаг u, содержащий uk операторов.

7. Вычислим uk:=1.

8. Вычислим vk:=uk, uk:=uk+1.

Если uk> uk ,то проверим, все ли блоки имеют выходные связи.

Если да, то переходим к п. 6, иначе проводим связи из блоков, не имеющих выходных связей, в блок uk' и переходим к п.6.

При uk<= uk' выполняем следующий шаг.

9. Если блок uk использует результаты работы блока vk, то проводим связь из vk в uk и переходим к п.8. Иначе следующий шаг.

10. Вычислим vk:=vk-1.

Если vk<>1 , то переходим к п.9, иначе проводим связь из первого блока рассматриваемого участка в блок uk и переходим к п.8.

Конец описания алгоритма.

Классическая схема алгоритма



Схема модифицированного алгоритма

15. Представление алгоритмов взвешенными графами. Основные определения матрицы описания информационного графа. Алгоритмы ее получения

Изображение схем параллельных алгоритмов с помощью информационных (ИГ) и информационно-логических (ИЛГ) графов.

ИГ используются для представления схем алгоритмов, не содержащих логические операторы. ИЛГ - для содержащих

ИГ и ИЛГ представляются с помощью выражения G = (X, P, D), X -множество вершин i, X={1..m}. Это множество вершин графа, соответствующие множеству операторов параллельного алгоритма. P = {1..Pm} - множество весов вершин графа.

В общем случае Pi - вектор.

Если Pi - скаляр, то рассматривается решение этой задачи на однородной ВС ( с одинаковыми процессорами). Тогда Pi - время решения i-ой процедуры.

Если Pi - вектор, предполагается решение этой задачи на неоднородной ВС. И, тогда, если система содержит S разнотипных процессоров, то вектор Pi = { Pi1 ,… , Pis}, где Pi1 ,… , Pis - набор времен решения i-ой процедуры на некотором типе процессора из множества S.

D - множество дуг гафов.

Дуги бывают двух типов: di Є D1, dj Є D2 , D = D1 U D2

D1- множество информационных дуг графа.

D2 - множество информационно-логических дуг графа.

ИЛ дуги графа исходят из логических блоков графа. И дуги графа исходят из выполняемых блоков графа. Дуги dj нагружены метками True или False.

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

Аналогично - ИЛГ.

ИГ мы также будем называть информационный граф схемы алгоритма, аналогично ИЛГ.

ИГ: ИЛГ:

Нумерация в кружке - имя процедуры (номер вершины).

Скобки - вектора весов (тут 3х мерные вектора)

Номер позиции - тип процессора.

? - на этом процессоре данная процедура не выполняется.

Вычисление матриц следования, расширенных матриц следования и матриц следования с транзитивными связями.

Определение 1. Если в параллельном алгоритме существует связь между операторами б, в и б - исполнительный блок, то в графе G существует дуга di D1, исходящая из вершины б и входящая в вершину в. Эту связь будем обозначать б > в.

Определение 2. Если в параллельном алгоритме существует связь между операторами б, в и б - логический блок, то в графе G существует дуга di D2, исходящая из вершины б и входящая в вершину в. Эту связь будем обозначать или соответственно и называть связь по управлению.

Связь определяет связь между операторами, если оператор б принимает значение “ TRUE ”, связь - в противном случае.

Связи б > в, , назовём задающими связями.

Определение 3. Путями в графе G назовём последовательности вершин б1,…, бn , такие, что для любой пары вершин бi, бi+1 существует дуга uD1 U D2, исходящая из вершины бi и входящая в вершину бi+1.

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

Определение 4. Характеристикой пути в графе G назовем количество вершин, входящих в этот путь.

Определение 5. Длиной пути в графе G со скалярными весами вершин назовем сумму весов вершин, составляющих этот путь.

Определение 6. Путь максимальной длины Ткр в графе G со скалярными весами вершин назовем критическим.

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

В качестве примера алгоритмов в виде схемы последовательного и параллельного алгоритмов с некоторыми трехмерными весами вершин представлен рис. 3.



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

Более точное определение матрицы следования заключается в следующем: i -ой вершине графа G ставятся в соответствие i - ые столбец и строка матрицы, если существует связь по управлению , то элемент матрицы равен (i,j) = jT, порождает значение (i,j) = jF, при j > i образуется (i,j) = 1. Остальные элементы матрицы равны 0.

Если мы хотим сказать, что между элементом i и j существует некоторая связь, то будем писать i > j.

Для отражения весов вершин вводится понятие расширенной матрицы следования SR: прибавляется дополнительно k столбцов с номерами m+1,…,m+k, где k - размерность вектора весов вершин граф - схемы.

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

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

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

Определение 7. Если hб = hв = h, то вершины б и в принадлежат одному ярусу. Для обеспечения получения треугольной матрицы следования для графа G необходимо при нумерации вершин придерживаться следующего правила: вершины, принадлежащие (d+1) ярусу, должны иметь номера большие, чем номера вершин d - ого яруса. Внутри одного яруса вершины могут нумероваться произвольно. Такую нумерацию назовем нумерацией по ярусам.

Утверждение 1. Матрица следования получится треугольной, если в граф-схеме G произведена нумерация по ярусам.

Предположим, что в некоторой строке д матрицы следования существует ненулевой элемент правее главной диагонали. Это значит, что существует связь д+v>д. Т.к. номер д+v>д, то dд ? dд+v по условию построения матрицы S. Однако, любой путь в вершину д+v может быть продолжен в вершину д, поэтому dд > dд+v, что противоречит предыдущему неравенству. Элемент v был выбран произвольно, следовательно, утверждение теоремы справедливо для любого элемента, лежащего левее главной диагонали.

17. Матрица следования для информационно-логического графа. Построение транзитивных связей в этой матрице

Рассмотрим построение матрицы следования с транзитивными связями ST. Возьмем 3 произвольные вершины i, j, k такие, что между ними определены следующие связи: связь вершины i с вершиной j, вершины j с вершиной k, вершины i с вершиной k (рис. 7).

В матрице следования многоточием обозначены другие связи, которые для данного случая не представляют интереса. При построении матрицы S элементы матрицы, соответствующие логическим связям выписываются по формуле (1), а информационным - по формуле (2):

S'ij=iSij (1)

S'ij=1 (2)

	…	i	…	j	…
…	…	…	…	…	…
J	…	iS' ij	…	…	…
…	…	…	…	…	…
K	…	iS'ik	…	jS'jk	…
…	…	…	…	…	…

Рассмотрим пример построения S для графа, приведенного на рисунке 2. Для логических связей в этом графе произведем преобразование по формуле (1): S12=T, следовательно S'12=1T.S13=T, следовательно S'13=1F

Остальные связи в графе не являются логическими, поэтому соответствующие элементы S будут равны единице, согласно формуле (2). В результате этого преобразования получим S, отображенную в таблице 1.

	1	2	3	4	5
1	0	0	0	0	0
2	1T	0	0	0	0
3	1F	0	0	0	0
4	0	1	0	0	0
5	0	0	1	0	0

Алгоритм построения матрицы следования с транзитивными связями.

Алгоритм 2.

1.В матрице следования S размера RS просматриваются строки, начиная с первой.

2. Если в очередной i-й строке отыскивается элемент (i,j) <>0, то вычисляются значения элементов матрицы (i,1),…,(i,j-1), используя соотношение

(

i,k):= ((j,k) (i,j)) (i,k) (1)

для k= 1,…,j-1.

3. j:=j+1. Если j <= RS, то переход на шаг 2, иначе - работа алгоритма заканчивается (просмотрены все строки).

Конец описания алгоритма.

18. Обоснование транзитивных операций дизъюнкции и конъюнкции

При построении транзитивных связей необходимо произвести анализ значений типов связей между этими вершинами и определить, какую связь между вершинами i и k выбрать: непосредственную или через вершину j. (для построения матрицы следования с транзитивными связями)

Первое, что влияет на этот выбор - это наличие транзитивной связи из вершины i в вершину k через вершину j. Обозначим эту связь ST. Для существования такой связи, как было замечено выше, необходимо, чтобы обе связи Sij и Sjk были отличны от нуля. Для проверки этой связи введем операцию «», которая аналогична операции конъюнкции в булевой алгебре. Таблица истинности операции «» применительно к информационно-логическим графам представлена

Sij	Sjk	Sik = SijSjk
0 0 0 1 1 L1	0 1 L 1 L L2	0 0 0 1 L L1_ L2

Здесь L1, L2, L обозначают некоторые кортежи [5] из логических связей S', где S' либо некоторая логическая связь из вершины в вершину , либо ранее вычисленная транзитивная связь. Символ “_” - оператор конкатенации [5]. Как нетрудно убедиться операция «» коммутативна, поэтому в таблице приведены значения без учета перестановки операндов. Рассмотрим построение этой таблицы более подробно. Очевидно, что транзитивная связь есть, если обе связи Sij и Sjk отличны от нуля. Соответственно результат операции на наборах, где хотя бы одна из связей Sij или Sjk равна нулю, будет нулевым, т.е. транзитивная связь отсутствует. Далее, в связи с тем, что ход решения алгоритма отражается последовательностью выполненных логических операторов, то в ситуации, когда один операнд равен единице, а второй содержит логический тип связи, необходимо, чтобы результат операции отражал логическую связь. Поэтому на наборе (1,L) результатом выполнения операции «» будет L. Исходя из тех же рассуждений, можно сказать, что в случае, когда обе связи содержат логический тип связи необходимо их объединить, и результатом операции на наборе (L1, L2) будет выражение L1_ L2. Таким образом, данная операция дает нам транзитивную связь ST=SijSjk. Следующим шагом будет определение, какая связь нам более важна: непосредственная из вершины i в k (Sik) или новая, вычисленная ST. Первое, на что следует обратить внимание, как уже говорилось, это на типы связей. Более важной связью будем по-прежнему считать логическую. Такой выбор делается из тех же соображений, что и раньше. Второе, что определяет результат операции - это непосредственно наличие хотя бы одной из связей между вершинами i и k: транзитивной или задающей [1]. Т.е. необходимо выбрать ненулевую связь, если она есть, при нулевом значении другой связи. Обозначим операцию, осуществляющую такой выбор, «». Из изложенного выше можно сказать, что ее характер подобен операции ИЛИ булевой алгебры. Таблица истинности для операции «»:

Sik	SТ	Sik SТ
0 0 0 1 1 L1	0 1 L L 1 L2	0 1 L L 1 L1_ L2

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

Sik=Sik(SijSjk) (2)

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

(k,i)=(k,i) ((j,i) (k,j)) (3)

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

19. Алгоритм определения наличия контуров в информационной граф-схеме алгоритма

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

Определение контуров в граф-схеме алгоритма.

Алгоритм 3.

1. Вычисление матрицы STi:=S, i:=0.

2. С помощью алгоритма 2, используя матрицу STi вычислить матрицу STi+1;

3. На главной диагонали матрицы STi+1 определяется: есть ли ненулевые элементы? Если есть, то исследуемый граф имеет цикл. Если STi+1 = STi , то исследуемый граф не имеет контуров. Конец алгоритма. Иначе определяем STi := STi+1 , i:=i+1 и перейти к шагу 2.

Конец описания алгоритма.

20. Понятие о матрице логической несовместимости. Внешние и внутренние замыкания в матрице

Рассмотрим множество вершин, принадлежащих путям, начинающимся в вершине, соответствующей i-му логическому оператору и включающей дугу T. Это множество назовем MTi. Аналогично построим множество вершин для дуги F - это множество вершин, принадлежащих путям, начинающимся в вершине, соответствующей i-му логическому оператору и включающей дугу F - множество MFi. В множества MTi и MFi сама вершина i не входит.

Определение 1. Если вершина p MTi, а q MFi и соответствующие им операторы могут выполняться либо один, либо другой при однократном выполнении алгоритма, то эти операторы называются логически несовместимыми.

При реализации алгоритма в логическом операторе i выполняется либо ветвь T, либо F. Следовательно, при планировании параллельных вычислений следует исключать планирование параллельного выполнения операторов, принадлежащих разным ветвям, т.е. попросту исключить их из планирования. Однако встречаются ситуации, когда ветви F и T пересекаются MTi MFi=TFi<> Ш. В этом случае операторы S, , могут планироваться для параллельного выполнения. На рис.1 приведен граф, в котором на вершине 6 произошло пересечение логических ветвей логического оператора 1. Операторы 6,7,9,10 могут быть запланированы для параллельного выполнения:

Определение 2. Вершина zTFi и имеющая наименьший номер, называется минимальной внутренне замкнутой вершиной i-го логического оператора и обозначается inzi. Так, для примера, представленного на рис.2, inz1 =6. Замыкание логических путей может осуществляться за счет внешних информационных связей. Как показано на рис.17 замыкание может произойти за счет информационных связей, путями, идущими от операторов 3 или 4. При этом должен существовать информационный путь к вершинам 3 или 4 от входа в алгоритм (вершина 2).

,

,

,,

.

Целесообразно рассмотреть внешнее замыкание для ветвей T и F отдельно. Это связано с тем, что при рассмотрении возможности параллельного выполнения операторов, включенных в логические ветви, необходимо учитывать результаты, как внешнего, так и внутреннего замыканий совместно, имея в виду при этом, что возможно внешнее замыкание только одной ветви.

Определение 3. Если существует информационный путь в вершину от начальной вершины граф-схемы, то вершина Z называется внешне замкнутой в ветви T для i-го логического оператора. Если таких вершин несколько, то вершину Z с минимальным номером называют минимальной внешне замкнутой в ветви T для i-го логического оператора.

Обозначим эту вершину ezTi=xj. Аналогично определяется внешнее замыкание ветви F, обозначающееся ezFi.

Определение 4. Если множество MTi={x1,…,xj,…,xj'} содержит внешнее замыкание ezT = xj, то подмножество VTi = { xj,…,xj'} называется внешне замкнутым для ветви T логического оператора Li.

Определение 5. Если множество MFi={x1,…,xj,…,xj'} содержит внешнее замыкание ezF = xj, то подмножество VFi = { xj,…,xj'} называется внешне замкнутым для ветви F логического оператора Li.

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

1. внутреннее замыкание, как правило, порождает операторы, которые можно выполнять параллельно;

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

3. определение множества MZi всех замкнутых операторов i-го логического оператора требуется вычислить объединение множеств: MZi = TFi U VTi U VFi.

Ситуации, соответствующие пунктам 1, 2 проиллюстрированы на. Рассмотрена ситуация, соответствующая пункту 3.

TFi = {10, 12 },

VTi = {8, 10, 12}

MZi = {8, 10, 12}

21. Алгоритм построения матрицы логической несовместимости операторов

Обозначения, принятые в схеме алгоритма:

S - матрица следования;

RS - размерность матрицы S;

ST - матрица с транзитивными связями;

RST - размерность матрицы ST;

MLO - множество логических операторов

RMLO - размерность множества логических операторов;

M - множество вершин операторов;

MTk - мн-во вершин операторов, принадл-х путям, вкл-щим дугу Т k-го логич-го оператора;

VFk - мн-во вершин операторов, внешне замкнутых для k-ого логич-го оператора связи F;

MFk- мн-во вершин операторов, принадл-х путям, вкл-щим дугу F F k-го логич-го оператора;

RMTk - размерность множества логических операторов ветви T;

RMFk - размерность множества логических операторов ветви F.

TFk - мн-во вершин операторов, внутренне замкнутых для k-ого логического оператора;

VTk - мн-во вершин операторов, внешне замкнутых для k-ого логич-го оператора связи Т;

MZk - объединенное множество внешних и внутренних замыканий для k-го логического оператора;

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

1. В матрице S, размера RS берём первый столбец (j:=1), RMLO:=1,MLO:=Ш.

2. Просматриваем j-й столбец по строкам и определяем равенство текущего элемента матрицы jT или jF.

3. Если найден такой элемент, то полагаем

MLO:= MLO { j}; RMLO:= RMLO+1.

4. Вычислить j:=j+1.

5. Если j RS,то перейти к шагу 2, иначе - конец алгоритма.



Процедура PMTF. Для получения множеств MT и MF k-го логического оператора необходимо просмотреть k-й столбец и включить в множество MT номера операторов, которые в соответствующих строках имеют значение kT, а множество MF номера операторов, которые в соответствующих строках имеют значение kF. Получение множества MT и MF k-го логического оператора.

1. В соответствии со значением k, выбираем элемент множества , в столбце матрицы ST; просматриваем i-е строки, i:=1 (номер строки), l:=1 (номер позиции в множестве MT), m:=1 (номер позиции в множестве MF);

2. если элемент матрицы ST(i,k) = jT, то MT[l]:=I, l:=l+1 и шаг 5;

3. если ST(I,k)=jF, то MF[m]:=i; m:=m+1 и шаг 5;

4. если условия пунктов 2, 3 не выполняются, то шаг 5;

5. i:=i+1; если i>RST, то RMT:=l, RMF:=m.

Процедура PREZ. Процедура PREZ формирует множество внешних замыканий для рассматриваемого логического оператора, используя свойства матрицы ST. Берётся i-ая строка матрицы ST, содержащая все нули (вход ИЛГ). Затем - для i-ого столбца номера всех элементов, равных 1, фиксируются в множестве WZ. Если для рассматриваемого k-ого логического оператора пересечения множеств WZ ? MTk и WZ ? MFk не пусты, то обнаружены внешние замыкания для ветвей k-ого логического оператора(номера внешне замкнутых операндов входят в эти пересечения).

1. Формируем множество из номеров нулевых строк матрицы ST : ZS := {i1,...,iq}. Полагаем VT := Ш, VF := Ш.

2. Для всех элементов ip c ZS строим множество EDp номеров строк, содержащих единичные элементы в ip столбцах.

3. Исключим из множеств EDp p = 1,…,q элементы, равные номеру рассматриваемого логического оператора k. Перенумеруем множества EDp, учитывая удаленные элементы. Получим множества EDu, u = 1,…,f , f<q. Если все EDu = Ш, то VT := Ш, VF := Ш.

4. Вычислить множества VT := VT U (MT ? EDu), VF := VF U (MF ? EDu), u = 1,…,f, где MT и MF - множества операторов для текущего вложенного оператора.

22. Понятие о матрице независимости в граф-схемах алгоритмов

Для определения возможности распараллеливания операторов необходимо провести анализ независимости операторов по данным и по управлению. Для этих целей вводится матрица независимости операторов М.

Определение 1. Симметричная матрица M(i,j) = S'(i,j) V L(i,j), где V - операция дизъюнкции булевой алгебры, Si(i,j) = ST(i,j), если ST(i,j) = 0 и S'(i,j) = 1, если ST(i,j) ? 0 для i = 1,..,RST и j = 1,..,RST, а L(i,j) - матрица логической несовместимости, называется матрицей независимости операторов.

Примечание: Здесь матрица ST не треугольная, а получается зеркальным отображением относительно главной диагонали. М - матрица независимости операторов.

Частный случай: Для информационного графа матрица М совпадает с матрицей S'.

Определение 2. Операторы и - взаимно независимые (ВНО), если в матрице независимости .

Определение 3. Операторы , , образуют полное множество ВНО, если для любого оператора существует пара элементов матрицы независимости , .

Определение 4. Множество, содержащее наибольшее число элементов для данного графа, называется максимально полным.

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

23. Взаимно независимые операторы. Определение независимости. Полные и максимально полные множества ВНО

Определение 1. Симметричная матрица M(i,j) = S'(i,j) V L(i,j), где V - операция дизъюнкции булевой алгебры, Si(i,j) = ST(i,j), если ST(i,j) = 0 и S'(i,j) = 1, если

ST(i,j) ? 0 для i = 1,..,RST и j = 1,..,RST, а L(i,j) - матрица логической несовместимости, называется матрицей независимости операторов.

Примечание: Здесь матрица ST не треугольная, а получается зеркальным отображением относительно главной диагонали. М - матрица независимости операторов.

Частный случай: Для информационного графа матрица М совпадает с матрицей S'.

Определение 2. Операторы и - взаимно независимые (ВНО), если в матрице независимости .

Определение 3. Операторы , , образуют полное множество ВНО, если для любого оператора существует пара элементов матрицы независимости , .

Определение 4. Множество, содержащее наибольшее число элементов для данного графа, называется максимально полным.

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

24. Алгоритм нахождения полных множеств ВНО

Определение 2. Операторы и - взаимно независимые (ВНО), если в матрице независимости . Определение 3. Операторы , , образуют полное множество ВНО, если для любого оператора существует пара элементов матрицы независимости , .

Работа алгоритма поиска полного множество ВНО основана на использовании стека. В стек поочерёдно заносятся строки матрицы М, а также строки, получаемые в результате сложения строк матрицы М по правилу дизъюнкции: , где n - размер матрицы М, а m - складываемые строки. В стеке также хранится информация о том, на каком элементе закончился просмотр строки, и какое множество ВНО при этом сформировалось. Эта информация нужна для того, чтобы возобновить просмотр строки с того места, где была сделана остановка (очередной виток рекурсии) и с тем же набором операторов во множестве ВНО. Структура стека показана на рис. 3.

Алгоритм

1. Пусть W - массив полных множеств ВНО. Максимальное полное множество ВНО обозначим через A, а l - число элементов в нём. Очередное формируемое множество ВНО обозначим через D (см. рис. 3), d - количество элементов в нём. Номер очередного найденного нулевого элемента в строке обозначим через k. Изначально полагаем, что стек пуст, W=, A=, l=0, D=, d=0, k=0.

2. Загружаем очередную i-ю строку в стек, i=1, …, n, где n - размер матрицы М. Полагаем . Если все строки обработаны, то выполнение алгоритма заканчивается. Найдены все полные множества ВНО (W) и определено максимальное (A).

3. В строке-вершине стека находим очередной нуль, занимающий позицию . Переходим к выполнению шага 6.

4. Если такого нуля нет или все нули найдены, выполняем проверку на полноту найденного множества D. Если в строке-вершине стека все нули соответствуют всем операторам из D, то найденное множество полное. Производим сохранение и переходим к шагу 7. Если в строке-вершине есть хотя бы один нуль, не соответствующий операторам из D, то найденное множество не является полным. Переходим к следующему шагу.

5. Исключаем из стека строку-вершину (не будем забывать, что, исключая строку, мы уничтожаем и текущее значение k и D, и возвращаемся к их предыдущим значениям) Если после этого стек исчерпан, выполняем шаг 2. В противном случае выполняем шаг 3.

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

7. Сравниваем значения d и l. Если , то A=D, l=d. Независимо от результата сравнения переходим к шагу 5.

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

Если задан граф, то известно:

1) Частичная упорядоченность выполнения алгоритма.

2) Заданы веса операторов (в частности - времена выполнения процедур)

3) Считаем началом отсчёта выполнения 1-ого логического оператора (это может быть i- оператор).

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

t1j - ранний срок выполнения оператора.

t2j - поздний срок выполнения оператора.

Рассматривается ИГ без контуров j = 1...m - вершины.

Ранние сроки

1. :=, где j:=1,…,RS.

2. Просматриваются строки матрицы S сверху вниз, выбирается первая необработанная строка матрицы, переход к следующему шагу; если обработаны все строки - конец алгоритма.

3. Пусть выбрана j-я строка, не содержащая единичных элементов, то вычисляется , где Pj - вес j-го оператора, шаг 15.

4. Если j-я строка содержит единичные элементы, то вычисляется по множеству , где обрабатывается времен, которым соответствует единица в данной строке; если в множестве есть -е элементы, то выполняется шаг 6.

5. Обработанная j-я строка исключается из рассмотрения.

6. Если имеется строка =, то производится поиск необработанной строки, и переход на шаг 3.

Примечание: пункт 6 используется для не треугольной матрицы S

Поздние сроки

1. :=, где j:=1,…,RS;

2. Просматриваются столбцы матрицы S слева направо, выбирается первый необработанный столбец матрицы, переход к следующему шагу;

3. если обработаны все столбцы, то - конец алгоритма.

4. Пусть j - номер каждого необработанного столбца, если он не содержит единичных элементов, то вычислим =T, где Т - время решения задачи, и переходим на шаг 5.

5. Если столбец j содержит единичные элементы, то вычисляется , т.е. определяем все единичные элементы j-го столбца. Если =, то выполняется шаг 3.

6. Обработанный j-й столбец исключаем из рассмотрения, затем выполняется шаг 2.

7. Для = отыскивается необработанный столбец, и осуществляется переход на шаг 3.

Примечание: пункт 6 используется для треугольной матрицы S.



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

Назовём множество А минорантой рассматриваемого графа. А - множество начальных вершин. Множество В - мажоранта. В - множество конечных вершин.

Зададим области определения для сроков окончания выполнения операторов для множества вершин графов.

1. tj ? Pj , если j Є A.

2. tj - Pj ? tj , если существует связь i>j , i Є X\B, j Є X\ A

3. tj ? T, если j Є B

Pj - вес j-го оператора, T - время решения задач.

Множество значений, определяемых этими неравенствами задает многоугольник MT в RS мерном пространстве:(t1,... , tRS) Є MT.

Функция , где ,

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

Значение функции PZ в каждый момент времени формируется операторами множества ВНО, т.е. в каждый момент времени значение функции PZ совпадает с числом одновременно выполняемых операторов.

Функция

называется загрузкой отрезка для

С помощью функции Z определяется загрузка отрезка [a,b], выполняемыми на этом отрезке операторами.

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

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

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

Функция называется загрузкой отрезка для

С помощью функции Z определяется загрузка отрезка [a,b], выполняемыми на этом отрезке операторами.

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

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

Для составления алгоритма вычисления данной функции введем функцию :

Алгоритм вычисления функции

1. Вычисляются раньше и поздние сроки окончания выполнения операторов.

2. Полагаем .

3. Анализируем последовательность оператора

4. Вычислим

После перебора всех операторов получаем значение

Конец описания алгоритма.

28. Об оценке сверху и снизу необходимого числа процессоров для решения поставленной задачи

Лемма «Об оценке сверху требуемого количества процессоров для решения задачи за время Т»:

Минимальное количество однородных процессоров N, способных выполнить данный алгоритм за время , не превышает , где - число операторов, входящих в i-ое полное множество ВНО, полученное для информационного графа G, соответствующего исследуемому алгоритму.

Следствие: При N=E время решения данного алгоритма Т=Ткр

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

Утверждение «Об оценке снизу числа процессов, необходимых для решения задачи за время Т »:

Для того чтобы N процессоров было достаточно для выполнения заданного алгоритма за время Т необходимо, чтобы для отрезка выполнялось соотношение

Утверждение «Об оценке снизу времени выполнения задачи при заданном количестве процессоров»:

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

29. Об оценке снизу времени выполнения задачи при заданном количестве процессоров. Уточнение оценки снизу времени выполнения задачи на N процессорах

Утверждение «Об оценке снизу времени выполнения задачи при заданном количестве процессоров»:

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

.

Утверждение «Об уточнении оценки снизу времени выполнения задачи на N процессорах»:

Если Т1 - оценка снизу времени выполнения алгоритма, представленного информационным графом со скалярными весами вершин на ВС, имеющей N процессоров, и на отрезке выполняется соотношение

тогда наименьшее время Т реализации алгоритма удовлетворяем соотношению

.

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

1. Положим N:=0.

2. Последовательно берутся интервалы в порядке:

[0,1] [0,2], [1,2], [0,3], [1,3], [2,3] [0,T], [1,T],…, [T-1,T]. Всего отрезков: . Для очередного интервала [a,b] вычислим