Вычислительные методы алгебры и оценивания. Семушин И.В. - 57 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

3.2 Распараллеливание вычислений
Пример 3.1. Пусть требуется сложить два n-мерных вектора a и b.
Сложения их элементов
a
i
+ b
i
, i = 1, . . . , n (3.3)
независимы и потому могут выполняться параллельно. Степень паралле-
лизма этого алгоритма равна n.
Пример 3.2. Пусть требуется сложить n чисел a
1
, . . . , a
n
. Обычный
последовательный алгоритм
s := a
1
, s := s + a
i
, i = 1, . . . , n
не пригоден для параллельных вычислений. Однако в са мо й задаче заклю-
чен немалый параллелизм. Можно разбить операнды на «двойки», т.е. скла-
дывать их по двое на каждом этапе операции. П олнос т ь ю эффект этой идеи
проявляется, когда число операндов равно степени двойки, т.е. n = 2
q
. Если,
например, q = 3, то все сложение займет q = 3 этапа, на каждом этапе дей-
ствия выполняются параллельно, как показано на рис. 3.3.
a
1
a
2
a
3
a
8
a
4
a
5
a
6
a
7
a
1
+ a
2
a
3
+ a
4
a
5
+ a
6
a
7
+ a
8
a
1
+ a
2
+ a
3
+ a
4
a
5
+ a
6
+ a
7
+ a
8
a
1
+ a
2
+ a
3
+ a
4
+ a
5
+ a
6
+ a
7
+ a
8
Рис. 3.3. Сложение n чисел методом сдваивания для n = 8 [8]
Очевидно, на первом этапе степень параллелизма равна n/2, на втором
n/4 и т. д. В связи с этим приходим к обновленному определению.
Определение 3.3. Средней степенью параллелизма численной задачи
называется отношение общего числа операций ее вычислительного алго-
ритма к числу последовательных этапов алгоритма.
57

Страницы