СКИПОД ответы на билеты (1127807), страница 14
Текст из файла (страница 14)
Источники погрешности при вычислениях на параллельных системах. В общем случае, арифметические операции над элементами дискретного подмножества вещественных чисел F не корректны. Результат арифметических операций чисел с плавающей запятой может:
-
иметь абсолютное значение, больше M (максимального числа) - машинное переполнение;
-
иметь ненулевое значение, меньшее m (минимального числа) по абсолютной величине - машинный нуль;
-
иметь значение в диапазоне [m:M] и тем не не менее не принадлежать множеству F (произведение двух чисел из F, как правило, записывается посредством 2t либо 2t-1 значащих цифр);
Поэтому, на множестве чисел с плавающей запятой определяются и "плавающие" арифметические операции, за результаты которых, если они не выходит за границы множества F, принимается ближайшие по значению элементы F. Примеры из четырехразрядной десятичной арифметики по Н. Вирту.
-
Пусть x=9.900 y=1.000 z=-0.999 и тогда:
-
-
(x+y)+z = 9.910
-
x+(y+z) = 9.901
-
-
Пусть x=1100. y=-5.000 z=5.001 и тогда:
-
-
(x*y)+(x*z) = 1.000
-
x*(y+z) = 1.100
-
Здесь операции + и * - плавающие машинные операции. Такие 'чиcленные' процессы называют иногда 'неточными', здесь нарушаются ассоциативный и дистрибутивный законы арифметики..
[править] Причины возникновения ошибок
Вначале рассмотрим простейший метод вычисления суммы чисел с плавающей точкой.
/* Simple Summation */
float f_add(float * flt_arr)
{
long i;
float sum = 0.0;
for (i = 0; i < ARR_SIZE; i++)
sum += flt_arr[i];
return sum;
}
Чаще всего результат применения данного метода оказывается неудовлетворительным. Проблема заключается в том, что складывание чисел с плавающей точкой сильно отличается от применения той же операции к целым числам. И основное отличие между ними — то, что при сложение вещественных чисел сначала их нужно преобразовать так, чтобы складывались цифры чисел одинакового порядка. При этом, если порядки чисел значительно различаются, тогда цифры младших разрядов отбрасываются. Если необходимо найти сумму сравнительно небольшого количества чисел, например, двух или трех, то данную ошибку можно и не заметить. Но при сложении большого множества чисел существенно отличающихся по величине, ошибка вычисления может оказаться неприемлемой.
Приведем простейший пример
Числа в компьютере представляются приближенно, что обусловлено конечностью разрядной сетки . Допустим, что порядок мантиссы не позволяет различить цифры порядка в 10 биллионов. Мы хотим сложить числа:
1.0 + 1.0e10 + −1.0e10
Выполняя суммирования чисел в различном порядке, мы получаем различный результат:
(1.0 + 1.0e10) + −1.0e10
= 1.0e10 + -1.0e10
= 0.0
но
1.0 + (1.0e10 + −1.0e10)
= 1.0 + 0.0
= 1.0
В первом случае информация о первом слагаемом была полностью потеряна, поскольку два других слагаемых значительно больше по величине. При суммировании небольшого числа слагаемых ошибку можно и не заметить, но при суммировании большого множества чисел с плавающей точкой ошибка будет накапливаться за счет этих небольших погрешностей, и также за счет разницы между промежуточной суммой и текущем членом.
[править] Упорядоченное суммирование
Как было показано выше, ошибка вычисления сильно зависит от порядка выполнения операций. При сложении двух чисел, значительно различающихся по величине, точность вычисления сильно снижается. Представим, что мы суммируем большое множество чисел. Тогда одним из операндов всегда будет сумма, причем в большинстве случаев она по величине значительно превосходит числа, которые мы постепенно к ней прибавляем. Данный эффект потери точности вычислений можно минимизировать путем упорядоченного суммирования чисел от наименьшего к наибольшему по абсолютному значению.
/* Sorted Summation */
float fs_add(float * flt_arr)
{
long i;
float lcl_arr[ARR_SIZE], sum = 0.0;
for (i = 0; i < ARR_SIZE; i++)
lcl_arr[i] = flt_arr[i];
qsort(lcl_arr, ARR_SIZE, sizeof(float),
flt_abs_compare);
for (i = 0; i < ARR_SIZE; i++)
sum += lcl_arr[i];
return sum;
}
Сначала создаем локальную копию массива flt_arr — lcl_arr. Сортируем полученный массив с помощью qsort. Затем суммируем элементы отсортированного массива. Но результаты по-прежнему остаются неудовлетворительными. Это происходит из-за того, что сумма очень быстро становится значительно больше по порядку, чем прибавляемые числа. В результате этого, точность вычисления повышается незначительно.
На самом деле, особенности суммируемых чисел сильно влияют на сортировку. Лучший случай, когда сумма принимает значения около нуля, а распределение примерно симметричное. Это условие способствует тому, что сумма всегда имеет примерно тот же порядок, что и суммируемые числа. Этот случай рассмотрен на примерах. Однако на практике он встречается довольно редко. Иногда сортировку чисел невозможно предугадать. Упорядоченное суммирование всегда дает один и тот же результат на одних и тех же множеств чисел, даже если числа следуют в разном порядке. Но это не совсем верно в случае, например, если использовать функцию сравнения:
/* Simple comparison */
int flt_abs_compare(const void * a, const void * b)
{
float fa = fabs(*(float *)a);
float fb = fabs(*(float *)b);
if (fa == fb)
return 0;
else if (fa < fb)
return -1;
else
return 1;
}
В этом случае число и обратная (по знаку) ему величина считаются одинаковыми. А это означает, что они могут оказаться в любом порядке следования в упорядоченной последовательности. Когда же нам нужна уверенность, необходимо использовать функцию сравнения вида:
/* Tie-breaking comparison */
int flt_abs_compare(const void * a,
const void * b)
{
float va = *(float *)a;
float vb = *(float *)b;
float fa = fabs(va);
float fb = fabs(vb);
if (fa < fb)
return -1;
else if (fa > fb)
return 1;
else if (va < vb)
return -1;
else if (va > vb)
return 1;
else
return 0;
}
Данная функция добивается полной предсказуемости следования элементов.
[править] Попарное суммирование
Ниже представлен алгоритм, в цикле обрабатывающий массив — на каждой итерации суммируются числа парами, при этом размер массива уменьшается вдвое.
/* Pairwise Summation */
float fp_add(float * flt_arr)
{
long i, j, limit;
float sum[ARR_SIZE / 2 + 1];
if (ARR_SIZE == 2)
return flt_arr[0] + flt_arr[1];
else if (ARR_SIZE == 1)
return flt_arr[0];
for (i = j = 0; i < ARR_SIZE / 2; i++, j += 2)
sum[i] = flt_arr[j] + flt_arr[j + 1];
if (ARR_SIZE & 1)
sum[ARR_SIZE / 2] = flt_arr[ARR_SIZE - 1];
limit = (ARR_SIZE + 1) / 2;
while (limit > 2) {
for (i = j = 0; i < limit / 2; i++, j += 2)
sum[i] = sum[j] + sum[j + 1];
if (limit & 1)
sum[limit / 2] = sum[limit - 1];
limit = (limit + 1) / 2;
}
return sum[0] + sum[1];
}
Данный алгоритм работает быстрее, чем упорядоченное суммирование, и при этом дает более аккуратный результат.
[править] Оценка полной ошибки для суммирования положительных чисел.
Пример расчета полной ошибки для суммирования положительных чисел Формула полной ошибки для суммирования положительных чисел
Ai (i=1,..,n) имеет вид: 
, где
- относительные ошибки представления чисел в ЭВМ, а di - относительные ошибки округления чисел при каждой следующей операции сложения. Пусть: все 
и di = d, a 
, тогда: 
Очевидно, что наибольший "вклад" в сумму ошибок вносят числа, суммируемые вначале. Следовательно, если суммируемые положительные числа упорядочить по возрастанию, максимально возможная ошибка суммы будет минимальной. Изменяя порядок суммирования чисел можно получать различные результаты. Но если даже слагаемые отличаются друг от друга незначительно, на точность результата может оказать влияние способ суммирования.
Пусть суммируются 15 положительных чисел, тогда ошибка результата: 
. Слагаемое daKs не зависит от способа суммирования, и далее не учитывается. Пусть слагаемые имеют вид: Ai = A0 + ei, где 
, тогда: 
, где 
, d - ошибка округления при выполнении арифметической операции сложения. Если провести суммирование этих чисел по группам (три группы по четыре числа и одна группа из трех чисел), то ошибки частных сумм имеют вид:
Полная оценка ошибок округления будет 
, что меньше 
. Итак суммирование по группам дает меньшую ошибку результата. Например, разделив процесс суммирования массива положительных чисел на параллельные процессы, и затем получив сумму частных сумм, можно получить результат, отличный от последовательного суммирования в одном процесс.
[править] Алгоритмы оптимизации программ, влияющие на точность вычислений.
Оптимизационные преобразования программ для их оптимального выполнения на конвейерных вычислителях могут проводиться системами программирования. Эти преобразования, алгебраически эквивалентные, могут нарушить порядок вычислений, предписанный исходным текстом программы. Последствия таких преобразований обсуждались выше. Наиболее характерные преобразования следующие.
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(I+1)
ENDDO
S = S + S1
Здесь, суммирование проводится отдельно для четных и нечетных элементов с последующем сложением частных сумм.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
