ВУЗ:
Составители:
80
параллельных арифметических операторов. Далее каждый блок, помеченный
цифрой, мы будем называть оператором, независимо от того какую совокуп-
ность соотношений или задач он представляет.
Соответствующая блок-схеме ал-
горитма (рис. 6.1) граф-схема приведе-
на на рис. 6.2. Здесь множество
m,ii 1X вершин графа соответ-
ствует множеству операторов алгорит-
ма. Для определенности будем пола-
гать, что оператор 1 закреплен за про-
цессором 1, оператор 2 – за процессо-
ром 2 и т.д. Множество дуг состоит из двух типов, определяющих связи по
управлению (двойные стрелки) и по информации (обычные стрелки).
Для составления расписания выполнения алгоритма должно быть также
задано множество
i
tP , m,i 1 весов вершин, определяющих время выпол-
нения каждого оператора. На этапе решения задачи выявления операторов, ко-
торые могут выполняться независимо и параллельно, веса вершин могут не ис-
пользоваться. Поэтому, исходя из задачи настоящего раздела, на рис. 6.2 для
сокращения записей они не приводятся.
Переход от обычной блок-схемы алгоритма к модели в виде граф-схемы
дает более ясное представление о структуре алгоритма, его свойствах и воз-
можности направленных преобразований. Заметим, что каждая связь по управ-
лению одновременно является связью по информации, т.к. она определяет стро-
гий порядок следования операторов, задаваемый логической переменной. В
простых случаях выявить операторы, которые могут выполняться независимо и
параллельно, можно непосредственно по граф-схеме алгоритма. Если граф-
схема имеет большое число ветвей, такой анализ становится затруднительным.
В этом случае анализ граф-схем можно проводить с использованием формаль-
ных правил преобразований соответствующих матриц.
Рис. 6.2 Граф-схема алгоритма
Страницы
- « первая
- ‹ предыдущая
- …
- 78
- 79
- 80
- 81
- 82
- …
- следующая ›
- последняя »
