Структурные характеристики вычислительных систем

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

2. Структурная коммутируемость. Характеризуется вектор-функцией:

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

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

— При дифференцируемом обмене имелась возможность реализации 1 обмена между двумя вычислителями.

— При трансляционном обмене реализовалась одновременная передача информации от одного вычислителя во все остальные.

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

3. Структурная живучесть:

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

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

Ищется при заданных значениях N, r, , S, .

– количество связей в сети;

– оптимальная структура.

Существуют специальные решения для циркулянт и Л-графов :

1. обеспечивает max

2. Структура обладает наибольшей живучестью.

3. Структура оптимальна при заданном N, и имеет min диаметр.

2. Утверждение об оценке времени выполнения алгоритма на наборе процессоров { } i=1,…,m или о достаточности набора процессоров { } i=1,…,m для выполнения алгоритма за время Т.

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

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

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

.

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