Математическое моделирование на графах. Часть 1. Берцун В.Н. - 41 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

Глава 1. Основные понятия теории графов 41
тельных формул. Например, пусть требуется вычислить
123456
(( ) )S aaa aa a=++. (1)
С учетом правил действий с алгебраическими выражениями (1) пе-
репишем в иной форме
12 35 45 6
()()()Saaaa aa a=++. (2)
Формула (2) более удобна для распараллеливания. На рис. 1.45
приведены соответствующие графы последовательного алгоритма
(формула 1) и параллельного (формула 2).
1
4
2
3
5
S
S
a
1
a
2
a
3
a
4
a
5
a
6
a
1
a
2
a
3
a
4
a
5
a
6
Рис. 1.45
Как следует из этого рисунка, форма записи алгебраического вы-
ражения может изменить число операций и высоту ПФА.
При реализации алгоритма на МВС операции на ярусе ПФА вы-
полняются за один такт, а количество тактов совпадает с высотой
ПФА. Например, на рис. 1.44 для четырехпроцессорной вычисли-
тельной системы по алгоритму сдваивания результат получается за
три такта, а для двух процессоров – за четыре такта.
При суммировании по алгоритму сдваивания четного числа сла-
гаемых N = 2
k
общее число операций суммирования

Страницы