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

UptoLike

ВУЗ: 

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

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

Рубрика: 

К существенным недостаткам системы G
0
следует отнести:
а) большое (часто — огромное) число функциональных уст-
ройств, необходимых для конструирования базовой системы G
0
;
б) чрезвычайная малость загрузки функциональных уст-
ройств;
в) отсутствие возможности использовать конвейерные функци-
ональные устройства.
§ 3. К построению графа вычислительной системы
Ввиду перечисленных в предыдущем параграфе недостатков
базовая система обычно неприемлема для практического примене-
ния. Поэтому в дальнейшем, используя базовую вычислительную
систему G
0
, будем строить другие системы, реализующие алгоритм
G. Основной аппарат таких построений — гомоморфизмы графов.
Граф вычислительной системы следует строить, руководству-
ясь следующими правилами:
1) граф вычислительной системы получается гомоморфизмом
ϕ из графа алгоритма G (или, что то же самое, из графа G
0
) с по-
мощью операции простого гомоморфизма для однотипных вершин;
2) если в базовой вычислительной системе G
0
функциональное
устройство F
0
j
получает информацию от устройства F
0
i
, то в графе
ϕG
0
вычислительной системы образ
e
F
j
def
=
ϕF
0
j
устройства F
0
j
может
получить соответствующую информацию только от образа
e
F
i
def
=
ϕF
0
i
устройства F
0
i
;
3) в случае необходимости сохранить результаты к функцио-
нальным устройствам подключается внешняя память нужного раз-
мера с мгновенным доступом; внешняя выборка не может происхо-
дить во время работы функционального устройства;
4) каждому функциональному устройству разрешается брать в
качестве данных результаты срабатывания другого функциональ-
ного устройства, связанного с ним линией связи, а некоторым из
них разрешается брать и входные данные; переключения связей
осуществляются программой.
Теорема 3.1. Пусть задан граф алгоритма G. Разобьем мно-
жество его вершин любым способом на непересекающиеся подмно-
жества и объединим вершины каждого из подмножеств в одну
вершину с помощью операции простого гомоморфизма. Возьмем
полученный граф в качестве графа вычислительной системы G
∗
,
70

Страницы