Использование алгебраических преобразований в параллельных вычислениях
Пример №2.6. Пусть требуется вычислить величину:
X26 = a2c─5abc─a2d + b2c + 5abd─b2d (2.9)
ПФ непосредственного решения этой задачи на 4-процессорной ПВМ (p = 4) можно представить в виде табл.2.5:
Табл. 2.5. Вычисление величины X26 на 4-процессорной ПВМ (Пример №2.6)
Как отмечалось выше, различные порядки выполнения операций и различные разбиения операций на группы порождают различные ПФ. Поэтому ПФ, представленная в табл.2.5, может быть и не оптимальной с точки зрения ее минимальной высоты.
Определим характеристики алгоритма, ПФ которого представлена в табл.2.5:
а) ускорение S4 = H1 / H4 = 16 / 6 = 2,67;
б) эффективностьE4 = 2,67 / 4 = 0,667;
в) высота H4 = 6;
г) загруженность процессоров : Z4 = (16 / 24) 100% = 66,7%.
Вопрос об устойчивости параллельных алгоритмов был рассмотрен выше.Таким образом, для вычисления величины X26 (2.9) необходимо осуществить 6 шагов и выполнить 16 операций. Однако выражение для X26 путем алгебраических преобразований можно представить в виде:
X*26 =(a2c + 5abc + b2c) – ( a2d + 5abd + b2d ) =
= ( a2 + 5ab + b2) c – ( a2 + 5ab + b2) d )=
= [( a2 + 5ab + b2) ( c – d )] = [( a2 + 2ab + b2) + 3ab] ( c – d ).
Окончательно в результате преобразований получим:
X*26 = [( a + b )2 + 3ab] ( c – d ) (2.10)
ПФ вычисления величины X*26на 4-процессорной ПВМ можно представить в виде табл.2.6:
Табл. 2.6. Вычисление величины X*26 на 4-процессорной ПВМ (Пример №2.6)
Определим характеристики алгоритма, представленного в ПФ табл.2.6:
а) ускорение S4 = H1 / H4 = 7 / 4 = 1,75;
б) эффективностьE2 = 1,75 / 4 = 0,44;
в) высота H2 = 4;
г) загруженность процессоров: Z4 = (7 / 16) 100% = 43,7%.
Таким образом, для решения поставленной задачи (Пример №2.6) с использованием алгебраических преобразований понадобилось осуществить лишь 4 шага и выполнить 7 операций для вычисления величины X*26(2.10).
Теперь построим ПФ алгоритма решения той же задачи на 2-процессорной ПВМ (табл.2.7).
Табл. 2.7. Вычисление величины X*26 на 2-процессорной ПВМ (Пример №2.6)
Определим характеристики алгоритма, представленного в ПФ табл.2.7:
а) ускорение S2 = H1 / H2 = 7 / 4 = 1,75;
б) эффективностьE2 = 1,75 / 2 = 0,875;
в) высота H2 = 4;
г) загруженность процессоров : Z2 = (7 / 8) 100% = 87,5%.
Сравнивая алгоритмы вычислений в ПФ табл.2.6 и табл.2.7, можно видеть, что для решения поставленной задачи следует использовать 2-процессорную ПВМ, поскольку она имеет лучшие характеристики (эффективность и загруженность) по сравнению с 4 - процессорной ПВМ.
Пример №2.7. Пусть требуется вычислить величину:
X27 = [a3 + 4 a b (a – b) – b3] [ c3 – 4 c d (c – d) + d3 ] (2.11)
Для непосредственного вычисления величины X27(2.11) на 4-процессорной ПВМ необходимо осуществить 8 шагов и выполнить 21 операцию. Преобразуем выражение для X27:
X27 =(a3 + 4a2 b – 4ab2 – b3) ( c3 – 4c2 d – 4cd2 + d3 ) =
= (a3 + 5a2 b – a2 b – 5ab2 + ab2 – b3) ( c3 – 5c2 d + c2 d – 5cd2 + cd2 + d3 ) =
= [(a3 + 2a2 b + ab2)– (a2 b + 2ab2 + b3) + (3a2 b – 3ab2 )] ×
× [( c3 – 2c2 d + cd2 ) + (c2 d – 2cd2 + d3) – ( 3c2 d +3cd2 )] =
= [ а (a + b)2 – b ( a + b)2 + 3ab (а – b)] [ c (c – d )2 + d (c – d)2 – 3cd (с + d )] .
В результате преобразований получим:
X27 = { [ ( a + b )2 + 3ab] ( a –b) } { [ ( c – d )2 – 3cd ] (c + d) }(2.12)
ПФ вычисления величины X27 на 4-процессорной ПВМ представлена в табл.2.8.
Табл. 2.8. Вычисление величины X27 на 4-процессорной ПВМ (Пример №2.7)
Определим характеристики алгоритма, представленного в ПФ табл.2.8:
а) ускорение S4 = H1 / H4 = 15 / 5 = 3;
б) эффективностьE2 = 3 / 4 = 0,75;
в) высота H2 = 5;
г) загруженность процессоров: Z4 = (15 / 20) 100% = 75%.
Таким образом, для решения поставленной задачи (Пример №2.7) с использованием алгебраических преобразований понадобилось осуществить лишь 5 шагов и выполнить 15 операций для вычисления величины X27(2.12).
Дата добавления: 2023-09-28; просмотров: 346;