ОПРЕДЕЛЕНИЕ ПЛОТНОСТИ ЗАГРУЗКИ ДЛЯ I-ГО ТИПА ПРОЦЕССОРА И АЛГОРИТМ ЕЙ ВЫЧИСЛЕНИЯ.

Определение 20. Плотностью загрузки для i-го типа процессора, найденной для значений , назовем величину , где

Определение 21. Функцию назовем загрузкой отрезка [a,b] входящей в [0, T] для i-го типа процессора.

назовем минимальной загрузкой отрезка [a,b] для i-го типа процессора.

При определении по А12 необходимо учитывать только те операторы, которые выполняются на i-м типе процессора.

Алгоритм 18. (Ранние, поздние сроки)

1. с помощью А10 и Ф11 определяем и
2. i:=1
3. 
4. Анализируем последовательность операторов
5. 
6. После перебора всех операторов, выполняемых на i-м типе процессора, определяем загрузку i-го типа процессора
7. Переходим на вычисление загрузки следующего типа процессоров i++. Идем на шаг 3.
8. После перебора всех значений i получим загрузку всех типов процессоров.

Пример.

T=8

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

47. УТВЕРЖДЕНИЕ ОБ ОЦЕНКЕ ВРЕМЕНИ ВЫПОЛНЕНИЯ АЛГОРИТМА НА НАБОРЕ ПРОЦЕССОРОВ {NI} I=1..M ИЛИ О ДОСТАТОЧНОСТИ НАБОРА ПРОЦЕССОРОВ {NI} I=1..M ДЛЯ ВЫПОЛНЕНИЯ АЛГОРИТМА ЗА ВРЕМЯ T.

48. УТВЕРЖДЕНИЕ ОБ УТОЧНЕНИИ ОЦЕНКИ ВРЕМЕНИ ВЫПОЛНЕНИЯ АЛГОРИТМА НА НАБОРЕ ПРОЦЕССОРОВ {NI} I=1..M.

Утверждение 1. Пусть каждый оператор данного алгоритма может быть выполнен процессором одного и только одного типа из множества типов i=1,…,k. Тогда для того, чтобы Т было наименьшим временем реализации данного алгоритма, состоящего из множества { } процессоров, либо для того, чтобы набор { } был достаточен для выполнения данного алгоритма за время Т необходимо чтобы для любого отрезка времени выполнялось соотношение:

Утверждение 2. Об уточнении оценки времени выполнения алгоритма на наборе процессоров { }.

Пусть Алгоритм задан информационным графом со скалярными весами вершин, и каждый оператор может быть выполнен процессором одного и только одного типа из множества типов i=1,…,k. Пусть ВС состоит из процессоров указанного типа. Пусть далее оценка реализации данного алгоритма на ВС, для которого на некотором отрезке

.

Тогда время выполнения данного алгоритма .

49. АЛГОРИТМ ОЦЕНКИ МИНИМАЛЬНОГО КОЛИЧЕСТВА ПРОЦЕССОРОВ {NI} I=1..M , НЕОБХОДИМОГО ДЛЯ ВЫПОЛНЕНИЯ ЗАДАННОГО АЛГОРИТМА ЗА ВРЕМЯ T.

Алгоритм 19 (об оценке минимального количества процессоров , i=1,…,m необходимой для выполнения заданного алгоритма за время Т)

1. i=1
2. =0
3. Последовательно берутся интервалы , [0,1], [0,2], [1,2],…,[T-1, T]
4. по А18 вычисляем и затем

5. если i > m то конец алгоритма, иначе на ш.2

Пример Т=6

50. АЛГОРИТМ ОЦЕНКИ МИНИМАЛЬНОГО ВРЕМЕНИ ВЫПОЛНЕНИЯ АЛГОРИТМА НА НАБОРЕ ПРОЦЕССОРОВ {NI} I=1..M.

Алгоритм 20 (об оценке минимального времени выполнения алгоритма на наборе процессоров)

{ }, i = 1,…, m

1. i:=1,
2. Вычисляем
3. по А19
4. [a,b] по А18

1. 
2. , то
3. ,
4. 
5. i++

если i>m то конец алгоритма, иначе переходим на ш. 2.

Пример