Составители:
Рубрика:
реву псевдоалгоритмов, листьями которого служат различные ал-
горитмы реализации, связанные с исходным псевдоалгоритмом —
корнем этого дерева.
В данном курсе будем использовать термин алгоритм как эк-
вивалент термина псевдоалгоритм.
§ 6. Параллельная форма алгоритма
Для реализации алгоритма на параллельной системе его сле-
дует представить в виде последовательности групп операций.
Отдельные операции в каждой группе должны обладать сле-
дующим свойством: их можно выполнять одновременно на имею-
щихся в системе функциональных устройствах.
Итак, пусть операции алгоритма разбиты на группы, а мно-
жество групп полностью упорядоченно так, что каждая операция
любой группы зависит либо от начальных данных, либо от резуль-
татов выполнения операций, находящихся в предыдущих группах.
Представление алгоритма в таком виде называется параллель-
ной формой алгоритма. Каждая группа операций называется яру-
сом, а число таких ярусов – высотой параллельной формы. Макси-
мальное число операций в ярусах (число привлекаемых процессов
в ярусах) — шириной параллельной формы.
Один и тот же алгоритм может иметь много параллельных
форм. Формы минимальной высоты называются максимальными.
Рассмотрим следующие примеры.
Пример 1. Пусть требуется вычислить выражение
(a
1
a
2
+ a
3
a
4
)(a
5
a
6
+ a
7
a
8
),
соблюдая лишь тот порядок выполнения операций, который пред-
ставлен в записи.
Фактически здесь фиксирован не один алгоритм, а несколько,
эквивалентных по результатам.
1.1. Приведем один из них:
Данные: a
1
, a
2
, a
3
, a
4
, a
5
, a
6
, a
7
, a
8
.
Ярус 1. a
1
a
2
, a
3
a
4
, a
5
a
6
, a
7
a
8
.
Ярус 2. a
1
a
2
+ a
3
a
4
, a
5
a
6
+ a
7
a
8
.
Ярус 3. (a
1
a
2
+ a
3
a
4
)(a
5
a
6
+ a
7
a
8
).
Высота этой параллельной формы равна 3, а ширина 4.
19
Страницы
- « первая
- ‹ предыдущая
- …
- 16
- 17
- 18
- 19
- 20
- …
- следующая ›
- последняя »
