Отчёт по лабораторной работе по дисциплине: "Вычислительные системы" на тему: "Оценка характеристик параллелизма задач"
Цель работы: ознакомление с основными характеристиками параллелизма задач по ярусно-параллельной форме (ЯПФ) алгоритма, приобретение навыков построения ЯПФ и оценки ее характеристик на примере вычисления арифметического выражения.
Ход работы:
|
Вариант |
α |
b |
Арифметическое выражение |
|
27 |
3 |
5 |
(a/b + c/d + e/f + g/h)(k + m) |
Трудоёмкость операции сложения tc=1;
Трудоёмкость операции умножения tu=α.tc;
Трудоёмкость операции умножения td=b.tu;
Представим независимые ветви распараллеленной задачи в виде ярусной параллельной формы(ЯПФ).
Вычисление основных характеристик параллелизма.
Ширина В ЯПФ:
;
где Вi - ширина i-го яруса - количество ветвей в этом ярусе. (B0=5, B1=2, B2=1, B3=1)
Длина L ЯПФ:
где li - длина i-го яруса:
l0=5; l1=1; l2=1; l3=3;
Если допустить, что в многопроцессорной(МП) вычислительной системе(ВС) все процессоры функционально идентичны, число процессоров не ограничено, и ЯПФ на ВС реализуется синхронно, то характеристику В можно рассматривать как минимальное число процессоров для полного распараллеливания, а L как минимальное время решения задачи на ВС.
L = Lmin .
Однако, при числе процессоров ВС равном 1, время решения задачи максимально:
.
и время L(n) решения задачи на n - процессорной ВС, n ≤ B, всегда лежит в пределах
Lmin ≤ L (n) ≤ Lmax .
Кроме L и B существуют также следующие показатели эффективности вычислений:
Коэффициент ускорения вычислений
.
он характеризует степень повышения производительности при использовании МП ВС.
Коэффициент загрузки:
,
или
ρ = K/n = 2.7/5 = 0.54
n = B = 5,
который показывает эффективность использования процессоров при решении распараллеленой задачи.
Вывод: рассмотренные четыре характеристики в достаточной мере оценивают построенную ЯПФ, но хотелось бы располагать и другими характеристиками, которае позволяют оценить оптимальность построения каждого яруса. Ведь очевидно, что ЯПФ рассмотренной задачй можно реализовать менее чем на пяти процессорах с тем же временем выполнения. Однако такой показатель невозможно определить в виде отдельного коэффициента, и скорее всего он будет выглядеть как группа условий оптимальности яруса. Например: условие оптимальности
Если li+1<li-1 то выражение 
должно быть больше либо равно единице.
где li - длина i-го яруса.
Ni - максимальная длина несвязанных ветвей i-го яруса (т. е. ветви выходы которых не используются в следующем ярусе)
Si - максимальная длина связанных ветвей i-го яруса.