Ви є тут

Методи та засоби підвищення ефективності паралельних обчислювальних систем реального часу

Автор: 
Жабін Валерій Іванович
Тип роботи: 
Дис. докт. наук
Рік: 
2006
Артикул:
3506U000409
129 грн
Додати в кошик

Вміст

раздел 2
Теоретические основы построения модульных параллельных вычислительных систем
2.1. Выбор определяющей совокупности факторов, влияющих на эффективность
параллельных вычислений
Эффективность вычислений в параллельных системах определяется как структурой
выполняемых алгоритмов, так и архитектурными особенностями систем.
Если при реализации алгоритма необходимо выполнить последовательность операций,
которые нельзя распараллелить, то никакое увеличение процессоров (вычислителей)
не позволит сократить время однократного выполнения указанной
последовательности операций (конвейерный режим в данном случае не
рассматривается). Ускорить вычисления можно только за счет одновременного
выполнения операций, которые поддаются распараллеливанию. Например, если в
процессе вычислений доля последовательных операций составляет половину от
общего числа операций, то при любом числе процессоров нельзя добиться ускорения
даже в два раза. Естественно, в данном случае параллелизм рассматривается на
уровне операций.
Определить, во сколько раз теоретически можно ускорить вычисления при различной
доле последовательных операций, позволяет закон Амдала [93], который можно
представить в виде
где b – доля последовательных операций, а n – число процессоров (вычислителей).
Теоретически возможное ускорение вычислений при увеличении числа процессоров
иллюстрируется табл. 2.1.
Таблица 2.1

Зависимость отношения N от величин b и n

Доля последовательных операций (b)

0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1,81
1,66
1,53
1,42
1,33
1,25
1,17
1,11
1,05
3,07
2,50
2,10
1,81
1,60
1,42
1,29
1,17
1,08
4,70
3,33
2,58
2,10
1,77
1,53
1,35
1,21
1,09
16
6,40
4,00
2,90
2,28
1,88
1,60
1,39
1,23
1,10
32
7,80
4,44
3,10
2,38
1,93
1,63
1,41
1,24
1,10
64
8,76
4,70
3,21
2,44
1,96
1,64
1,41
1,24
1,10
128
9,34
4,84
3,27
2,47
1,98
1,65
1,42
1,24
1,11
256
9,66
4,92
3,30
2,48
1,99
1,66
1,42
1,24
1,11
512
9,82
4,96
3,31
2,49
1,99
1,66
1,42
1,24
1,11
1024
9,91
4,98
3,32
2,49
1,99
1,66
1,42
1,25
1,11
Задачи могут обладать скрытым параллелизмом.
Пусть задан граф в ярусно-параллельной форме (ЯПФ) [94]
где – множество вершин i–го яруса ();
– множество входных дуг вершин i–го яруса;
– множество весов вершин i–го яруса.
Вершинам графа соответствуют операторы, осуществляющие определенное
преобразование информации. Оператор i–го яруса активизируется только после
завершения работы всеми операторами предшествующих ярусов, связанных с ним
дугами. Каждой вершине vij приписан вес wij, определяющий длительность
преобразования информации. Число вершин на ярусе называют шириной яруса, а
максимальную ширину яруса называют шириной ЯПФ.
Вершину ЯПФ будем считать активной, если оператор в данный момент осуществляет
преобразование информации. В противном случае вершина считается пассивной.
Понятно, что в каждый момент времени число активных вершин определяет
максимальное число вычислителей (процессоров), которые могут одновременно
решать задачу, соответствующую ЯПФ.
Сам факт представления задачи в ЯПФ с шириной два и более означает, что задача
обладает внутренним параллелизмом. Зачастую на этапе статического анализа
программист определяет число параллельных процессов по ширине графа. Однако на
практике задача может обладать скрытым параллелизмом и распараллеливаться в
значительно большей степени.
Утверждение. В ЯПФ с шириной два и более при отсутствии ограничений на значения
весов wij число активных вершин в один момент времени может достигать значения
. (2.1)
Доказательство очевидно из приведенного рис.2.1. Цепочка вершин, связанных
двойными дугами (все вершины имеют только по одному входу), обеспечивает
быструю активизацию вершин на каждом ярусе, а цепочка вершин, соединенных
пунктирными дугами (все вершины имеют только по одному выходу), обеспечивает
поэтапный переход вершин в пассивное состояние. В каждом ярусе, кроме первого и
последнего, указанные функции выполняют по две вершины, а в первом и последнем
ярусе – только по одной. В зависимости от значения весов одновременно в
активном состоянииможет находиться разное число вершин, но не более, чем
указано в (2.1).
Рис. 2.1. Ярусно-параллельная форма графа
Вершины, которые могут одновременно находиться в активном состоянии, на рис.
2.1 затемнены. При ширине ЯПФ, равной 5-ти, одновременно могут выполняться 12
операторов.
Для регулярного ортогонального графа с шириной k и длиной s из (2.1) нетрудно
показать, что число активных вершин может составлять N=ks-2s+2.
Из приведенного очевидно, что число одновременно обрабатываемых операторов
может существенно превышать ширину ЯПФ. Следовательно, динамические методы
распараллеливания дают потенциальную возможность ускорения решения задач с
неявным параллелизмом.
Рассмотрим влияние архитектурных особенностей систем на эффективность
параллельных вычислений.
Для оценки производительности систем можно воспользоваться формулой [95]
(2.2)
где – коэффициент, учитывающий влияние архитектурных особенностей систем;
– среднее время выполнения команды в процессоре.
Для сравнительной оценки производительности систем может использоваться
усредненное значение
, (2.3)
где – средняя адресность команды;
– коэффициент, учитывающий уровень конвейеризации при выполнении команд в
процессоре;
– время цикла обращения к памяти;
– число команд в системе команд процессора;
– частота появления в программах команды –го типа;
– длительность выполнения команды –го типа.
Анализируя составляющие формулы (2.3), можно заключит