Лекции по параллельным вычислениям. Гергель В.П - 89 стр.

UptoLike

Составители:

Рубрика:

Лекция 7

Временные характеристики алгоритмов

7.1 Определение и характеристики информационного графа

Достаточно широким классом являются алгоритмы, при одной реализации

которых выполняются все операторы. Такие алгоритмы не содержат логиче-

ских операторов и представляются информационными графами, в которых от-

сутствуют связи по управлению. Для обозначения связей по информации будем

использовать символ (), а соответствующие элементы называть единичными.

На рис. 7.1 в качестве примера приведены граф-схема алгоритма и соответст-

вующие ему матрица следования и матрица следования, дополненная транзи-

тивными связями.

а б в

Рис. 7.1 Информационная граф-схема алгоритма со скалярными весами

вершин: а – информационный граф; б – матрица следования; в – матрица

следования S с транзитивными связями

Алгоритмы указанного типа, во-первых, имеют место, когда речь идет о

распараллеливании множества работ значительного объема, когда операторами

являются некоторые логически завершенные достаточно крупные взаимодейст-

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

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

но необходимо рассмотреть все возможные варианты, в которых все операторы

обязаны выполняться при одной реализации. Каждый отдельно взятый вариант

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