Алгоритмы параллельных вычислений и программирование. Бурова И.Г - 62 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

Следствие 4.1. Максимально возможное ускорение равно
пиковой производительности вычислительной системы: max U =
P
1
.
Д о к а з а т е л ь с т в о. При максимальной загруженности
устройств в формуле (4.1) имеем z
(i)
= 1. Отсюда max U =
P
s
i=1
p
1(i)
= P
1
.
Следствие 4.2. Если вычислительная система состоит из
s простых функциональных устройств, то максимально возмож-
ное ускорение равно s.
Д о к а з а т е л ь с т в о. Пиковая производительность простого
функционального устройства равна 1, так что p
1(i)
= 1 для всех
i = 1, . . . , s. Отсюда P
1
=
P
s
i=1
p
1(i)
= s.
Замечание. До сих пор рассматривалось только выполнение
операций и не учитывались затраты на пересылки, запоминание
промежуточных результатов и т.п. Однако, в реальных параллель-
ных системах именно эти затраты являются наиболее существен-
ными, ибо, например, каналы связи оказываются наиболее узким
местом этих систем. Но ситуацию легко поправить, введя в рассмот-
рение функциональные устройства, которые передают ее или пре-
образуют в другую форму (например, перекодируют). Такие функ-
циональные устройства тоже можно разделить на две группы: про-
стые и конвейерные. Граф расширенного таким образом алгоритма
получается из предыдущего графа добавлением вершин, соответ-
ствующих упомянутым устройствам.
Определение 4.2. Расширенный алгоритм назовем вычис-
лительным.
Заметим также, что в построенной теории можно вместо всей
системы рассматривать некоторую ее часть. Однако при оценке
времени реализации алгоритма следует учитывать все рассматри-
ваемые функциональные устройства.
Рассмотрим совокупность каналов связи вычислительной си-
стемы. Тогда s — число всех каналов, z
j
— загруженность j-го кана-
ла, N — суммарное число всех обменов, T — время занятости кана-
лов. Каналы считаем простыми функциональными устройствами;
тогда z
(j)
= R
(j)
— среднее число операций. Покажем, что
s
X
j=1
z
(j)
=
N
T
. (4.3)
Действительно, по определению обмен представляет собой опе-
63

Страницы