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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§ 2. Базовая вычислительная система
В реальной ситуации при указанном соответствии после запус-
ка системы происходит одно из двух: либо система срабатывает и
реализует алгоритм, либо система срабатывает не до конца и оста-
навливается. Последнее может происходить по различным причи-
нам технического характера (слишком большое время реализации,
слишком низкая загруженность системы и т.д.); сюда же можно от-
нести отсутствие желаемой эффективности. Поэтому переходят к
решению задачи: среди множеств программ указать приемлемую.
Пусть G — граф рассматриваемого алгоритма (сам алгоритм
будем обозначать тем же символом G). Формально заменим его вер-
шины функциональными устройствами, которые могут выполнять
соответствующие операции, а кроме того, заменим его дуги соответ-
ствующими связями для передачи данных. В результате формально
получается вычислительная система G
0
— реализация графа G.
Вычислительная система G
0
называется базовой для алгорит-
ма G. Очевидно, граф вычислительной системы G
0
изоморфен
графу G.
Всю совокупность P
G
программ, каждая из которых реализу-
ет G на системе G
0
, также будем называть базовой совокупностью
(программы упомянутой совокупности также называем базовыми).
Определение 2.2. Перенумеруем вершины графа G
0
и обо-
значим t
i
момент включения i-го функционального устройства.
Вектор t = (t
1
, t
2
, . . .) называется временн´ой разверткой базовой
вычислительной системы.
Нетрудно видеть, что вектор t взаимно однозначно определяет
программу из базовой совокупности программ; в дальнейшем век-
тор t будем называть также программой из базовой совокупности.
Отметим следующие свойства:
1) временн´ых разверток t базовой вычислительной системы ал-
горитма G существует бесконечно много;
2) время T реализации алгоритма определяется по формуле
T = max
i
(t
i
+ τ
i
) − min
i
t
i
,
где τ
i
— время реализации самой длинной из начинающихся в мо-
мент t
i
операций;
3) по временн´ой развертке однозначно определяется порядок
операций;
68

Страницы