Нотация Хокни для данного алгоритма:

X = D

DO L = 1,LOG2(N)

X = A * SHIFTR(X,2**(L-1)) + X

A = A * SHIFTR(A,2**(L-1))

ENDDO

1. Представление машинных чисел.

Подмножество вещественных чисел, которое может быть представлено в ЭВМ в форме чисел с плавающей запятой, принято обозначать буквой F и определять его элементы для конкретной архитектуры - "машинные числа", (по Форсайту и др.) четырьмя целочисленными параметрами: базой b, точностью t и интервалом значений показателя [L,U]. Множество F содержит число нуль и все f числа вида: f = (+/-).d1d2...dt * b**e, где е назы­вается показателем, число .d1d2...dt = (d1/b+ ....+dt/(b**t)) - дроб­ной частью - мантиссой, причем: 0<=di<b, L<=e<=U. Каноническая или нормализованная форма F определяется дополнительным соотношением d1 =/= 0; это условие позволяет устранить неоднозначность представления одинаковых чисел, дает наивысшую возможную точность представления чисел. Особенности F:

• для каждого ненулевого f верно: m<=|f|<=M, где m = b**(L-1), M = (b**U) * (1-b**(-t));

• множество F конечно и содержит 2*(b-1)*(b**(t-1))*(U-L+1)+1 чисел, которые отстоят друг от друга на числовой оси на неравные проме­жутки.

1. Арифметика машинных чисел.

1. Погрешности при вычислениях чисел на параллельных системах. Оценить полную ошибку суммирования положительных чисел.

Формулы оценки абсолютной и относительной погрешности арифметических операций.

1. Сложение: X=X1+X2 X1>0 , X2>0

Абсолютная погрешность: Dx = Dx1 + Dx2 , относительная: dx = dx1 + dx2

2. Вычитание: X=X1-X2 X1>X2>0

Абсолютная погрешность:Dx=Dx1 + Dx2, относительная: dx=(X1*dx1 + X2*dx2)/X

Если X1 >> (много больше) X2, то dx (почти равно) dx1.

Если X1 (почти равно) X2, то dx будет очень велико. При вычитании близких по величине чисел получается большая потеря верных знаков.

3. Произведение: X = X1+X2

Погрешности: Dx = (X/X1)*Dx1 + (X/X2)*Dx2 dx = dx1 + dx2

4. Частное двух величин: X = X1/X2

Погрешности:Dx = (|X2|*Dx1 + |X1|*Dx2)/X2**2 , dx = dx1 + dx2

Формулы дают выражения для определения ошибки результата каждого из 4 арифметических действий как функции от величины чисел, участвующих в операциях, и абсолютных ошибок для них (например, погрешностей исходных данных). Для определения полной ошибки результата нужно к этим ошибкам отдельно добавить ошибки округления.

Пример расчета полной ошибки для суммирования положительных чисел (Г.К. Боровин).

Формула полной ошибки для суммирования положительных чисел Ai(i=1,..,n) имеет вид:

Ds = A1*da1 + A2*da2 +...+ An*dan + d1*(A1+A2) +..+ d(n-1)*(A1+..+An) + dn , где

dai - относительные ошибки представления чисел в ЭВМ, а di - относительные ошибки округления чисел при каждой следующей операции сложения.

Пусть: все dai = da и di = d , a Ks = A1+A2+..+An, тогда:

Ds = da*Ks + d*[(n-1)*A1+(n-1)*A2 +...+ 2*A(n-1) + An]

Очевидно, что наибольший "вклад" в сумму ошибок вносят числа, суммируемые вначале. Следовательно, если суммируемые положительные числа упорядочить по возрастанию, максимально возможная ошибка суммы будет минимальной. Изменяя порядок суммирования чисел можно получать различные результаты. Но если даже слагаемые отличаются друг от друга незначительно, на точность результата может оказать влияние способ суммирования. Пусть суммируются 15 положительных чисел, тогда ошибка результата: Ds = da*Ks + d*(14*A1+14*A2+13*A3+....+2*A14+A15).

Слагаемое da*Ks не зависит от способа суммирования, и далее не учитывается.

Пусть слагаемые имеют вид: Ai = А0+ei, где i=1,...,15, тогда: Dss = 199*(A0+em)*d, где em = max(ei), d - ошибка округления при выполнении арифметической операции сложения.

Если провести суммирование этих чисел по группам (три группы по четыре числа и одна группа из трех чисел), то ошибки частных сумм имеют вид:

Ds1 = d*(3*A1+3*A2+2*A3+A4) <= 9*d*(A0+em)

Ds2 = d*(3*A5+3*A6+2*A7+A8) <= 9*d*(A0+em)

Ds3 = d*(3*A9+3*A10+2*A11+A12) <= 9*d*(A0+em)

Ds4 = d*(3*A13+2*A14+A15) <= 5*d*(A0+em)

а полная оценка ошибок округления будет Ds <= 32*d*(A0+em), что меньше Dss. Итак суммирование по группам дает меньшую ошибку результата.

Например, разделив процесс суммирования массива положительных чисел на параллельные процессы, и затем получив сумму частных сумм, можно получить результат, отличный от последовательного суммирования в одном процесс.

1. Точность плавающей арифметики. Машинный эпсилон.

Точность плавающей арифметики можно характеризовать посредством машинного эпсилона.

Максимальное число Е такое, что 1.+ Е = 1. является мерой точности представления чисел на данной ЭВМ (машинное эпсилон). Грубая схема вычисления эпсилона:

EPS = 1.0

1 EPS = 0.5 * EPS

EPS1 = EPS + 1.0

IF (EPS1 .GT. 1.0) GO TO 1 >

Погрешности округления при вычислениях

При выполнении арифметических операций на ЭВМ могут появляться числа с большим количеством значащих цифр, чем у исходных чисел, и большим, чем может быть представимо на данной ЭВМ. Например, при умножении, число значащих цифр может удвоиться. Поэтому необходимо проводить округление результата вычислений.

Простейший способ округления состоит в отбрасывания младших разрядов. Пусть при вычислении получен неотрицательный результат (q-ичная дробь): X = 0.An A(n-1) A(n-2)....As A(s-1) A(s-2)....A1 .

Тогда, округленное число есть: Xs= 0.An A(n-1)A(n-2)....As , а ошибка округления (абсолютная): Dx=|Xs-X|<=q**(-[n-(s-1)]), где n-(s-1) число значащих цифр в Xs. Максимально возможная относительная ошибка при этом будет равна:

dx = Dx/X <= (q**(-[n-(s-1)]))/(1/q) = q**(-(n-s)).

Другим общепринятым способом округления считается "симметричное" округление, при котором:

Xs = Xs + q**(-(n-s)), если |Xs-X| >= 0.5**q(-(n-s)) и

Xs = Xs, если |Xs-X| < 0.5**q(-(n-s))

При этом способе округления максимально возможное значение относительной ошибки: dx <= 0.5*q**(-(n-s)+1).

1. Перечислить алгоритмы оптимизации объектных программ, которые могут повлиять на точность вычислений.

Оптимизационные преобразования программ для их оптимального выполнения на конвейерных вычислителях могут проводиться системами программирования. Эти преобразования, алгебраически эквивалентные, могут нарушить порядок вычислений, предписанный исходным текстом программы.

Последствия таких преобразований обсуждались выше. Наиболее характерные преобразования следующие.

1. Балансировка дерева вычислений

Балансировка дерева вычислений (tree-height reduction or balancing) выражений позволяют использовать конвейерное АУ без пропуска рабочих тактов. Так, вычисление суммы вещественных чисел: A+B+C+D+E+F+G+H, будет запрограммировано как последовательность операций: (((A+B)+(C+D))+((E+F)+(G+H))); это нарушает заданную по умолчанию последовательность вычислений с накоплением одной частной суммы и может повлиять на результат.

2. Исключение общих подвыражений

Алгоритмы исключения общих подвыражений (Common subexpession elimination) также могут изменить порядок вычислений.

Если компилятор распознает в выражениях повторяющееся вычисление, то это вычисление производятся один раз, его результат сохраняется на регистре, и в дальнейшем используется этот регистр. Тем самым исключается избыточность вычислений.

X = A + B + C + D ----> REG = B + C

Y = B + E + C X = A + D + REG

Y = E + REG

3. Разворачивание циклов

Разворачивание циклов (loop unrolling) - расписывание цикла последовательностью операторов присваивания: либо полностью, либо размножение тела цикла с некоторым коэффициентом (фактором) размножения.

Производится частичное или полное разворачивание цикла в последовательный участок кода. При частичном разворачивании используется так называемый фактор разворачивания (который можно задавать в директиве компилятору).

DO I=1,100 DO I=1,100,4

A(I) = B(I) + C(I) A(I) = B(I) + C(I)

ENDDO A(I+1) = B(I+1) + C(I+1)

A(I+2) = B(I+2) + C(I+2)

A(I+3) = B(I+3) + C(I+3)

ENDDO

При этом преобразовании снижается количество анализов итерационной переменной. Данный алгоритм также может привести к нарушению предписанного первоначально порядка вычислений. Например:

DO I=1,10 DO I=1,10,2

S = S + A(I) S = S + A(I)

ENDDO S1 = S1 + A(A+1)

ENDDO

S = S + S1

Здесь, суммирование проводится отдельно для четных и нечетных элементов с последующем сложением частных сумм.

По аналогии с этим принято считать, что парадигма в программировании -- способ концептуализации, который определяет, как следует проводить вычисления, и как работа, выполняемая компьютером, должна быть структурирована и организована.

§9. Средства автоматического распараллеливания программ

Средства автоматического распараллеливания – наиболее быстрый способ получить параллельную программу из последовательной, но степень параллелизма кодов, полученных автоматически, ниже степени параллелизма кодов программ, в которых параллелизм закладывается программистом. Так или иначе, но машина предпочтет не распараллеливать любой подозрительный фрагмент программы, в то время как программист знает, какая часть алгоритма, не являющаяся заведомо параллельной, тем не менее может быть распараллелена.

Некоторые средства автоматического распараллеливания представлены в табл. 4.

Таблица 4

61