ПОД конспект (1184369), страница 23
Текст из файла (страница 23)
Арифметика машинных чисел.76. Погрешности при вычислениях чисел на параллельных системах. Оценить полнуюошибку суммирования положительных чисел.Формулы оценки абсолютной и относительной погрешности арифметических операций.1. Сложение: X=X1+X2 X1>0 , X2>0Абсолютная погрешность: Dx = Dx1 + Dx2 , относительная: dx = dx1 + dx22. Вычитание: 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 + dx24. Частное двух величин: 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 , где58dai - относительные ошибки представления чисел в ЭВМ, а 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.
Итак суммирование погруппам дает меньшую ошибку результата.Например, разделив процесс суммирования массива положительных чисел на параллельные процессы, изатем получив сумму частных сумм, можно получить результат, отличный от последовательногосуммирования в одном процесс.77. Точность плавающей арифметики. Машинный эпсилон.Точность плавающей арифметики можно характеризовать посредством машинного эпсилона.Максимальное число Е такое, что 1.+ Е = 1. является мерой точности представления чисел на данной ЭВМ(машинное эпсилон). Грубая схема вычисления эпсилона:EPS = 1.01 EPS = 0.5 * EPSEPS1 = EPS + 1.0IF (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=|XsX|<=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**(-(ns)+1).5978.
Перечислить алгоритмы оптимизации объектных программ, которые могут повлиять наточность вычислений.Оптимизационные преобразованияпрограммдля их оптимального выполнения на конвейерныхвычислителях могут проводиться системами программирования. Эти преобразования, алгебраическиэквивалентные, могут нарушить порядок вычислений, предписанный исходным текстом программы.Последствия таких преобразований обсуждались выше.
Наиболее характерные преобразования следующие.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 + CY = B + E + CX= A + D + REGY= E + REG3. Разворачивание цикловРазворачивание циклов(loop unrolling) - расписывание цикла последовательностью операторовприсваивания: либо полностью, либо размножение тела цикла с некоторым коэффициентом (фактором)размножения.Производится частичное или полное разворачивание цикла в последовательный участок кода.
Причастичном разворачивании используется так называемый фактор разворачивания (который можно задаватьв директиве компилятору).DO I=1,100DO I=1,100,4A(I) = B(I) + C(I)A(I) = B(I) + C(I)ENDDOA(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,10DO I=1,10,2S = S + A(I)S = S + A(I)ENDDOS1 = S1 + A(A+1)ENDDOS = S + S1Здесь, суммирование проводится отдельно для четных и нечетных элементов с последующем сложениемчастных сумм.По аналогии с этим принято считать, что парадигма в программировании -- способконцептуализации, который определяет, как следует проводить вычисления, и как работа,выполняемая компьютером, должна быть структурирована и организована.§9.
Средства автоматического распараллеливанияпрограммСредства автоматического распараллеливания – наиболее быстрый способ получитьпараллельную программу из последовательной, но степень параллелизма кодов,полученных автоматически, ниже степени параллелизма кодов программ, в которыхпараллелизм закладывается программистом. Так или иначе, но машина предпочтет нераспараллеливать любой подозрительный фрагмент программы, в то время как60программист знает, какая часть алгоритма, не являющаяся заведомо параллельной, тем неменее может быть распараллелена.Некоторые средства автоматического распараллеливания представлены в табл. 4.Таблица 4НазваниеBERT 77Дополнительные сведенияРаспараллеливает Fortran-программыРаспараллеливает Fortran-программы дляSMP и MPP платформРаспараллеливает Fortran-программыРаспараллеливает Fortran/C-программыдля SMP-платформAPIPVM, MPIFORGExplorerPIPSOpenMP, MPI, PVMVAST/ParallelOpenMP61.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
