Essential issues of modern floating point arithmetic

An overview of modern floating point arithmetic is presented. Aspects that differ from real numbers arithmetic and thus being the source of many numeric problems are emphasized. These problems scale drastically given volume of a data is large and computations being parallel. Nevertheless, it is poss...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2018
1. Verfasser:	Iushchenko, R.A.
Format:	Artikel
Sprache:	rus
Veröffentlicht:	Інститут програмних систем НАН України 2018
Schlagworte:	Floating point arithmetic
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/37
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-37
record_format	ojs
resource_txt_mv	ppisoftskievua/2c/36f8d88283cb71b4ac7922390e16442c.pdf
spelling	pp_isofts_kiev_ua-article-372018-07-25T14:00:23Z Essential issues of modern floating point arithmetic Актуальные проблемы современной арифметики с плавающей запятой Актуальні проблеми сучасної арифметики з плаваючою комою Iushchenko, R.A. Floating point arithmetic Арифметики с плавающей точкой An overview of modern floating point arithmetic is presented. Aspects that differ from real numbers arithmetic and thus being the source of many numeric problems are emphasized. These problems scale drastically given volume of a data is large and computations being parallel. Nevertheless, it is possible to minimize and even guarantee a certain precision of the results even without considerable loss of performance. Представлен краткий обзор чисел с плавающей запятой и соответствующей арифметики. Подчеркнуты особенности, которые отличают ее от арифметики действительных чисел и часто являются причиной существенных проблем при численном решении задач на компьютере. Эти проблемы усиливаются для больших объемов данных и параллельных вычислений. Несмотря на все это, минимизировать и даже гарантировать точность решений возможно даже без существенных потерь в производительности. Представлено короткий огляд чисел із плаваючою комою й відповідної арифметики. Підкреслено особливості, які відрізняють її від арифметики дійсних чисел і часто є причиною істотних проблем при числовому розв'язанні задач на комп'ютері. Ці проблеми підсилюються для великих об'ємів даних і паралельних обчислень. Незважаючи на все це, мінімізувати й навіть гарантувати точність розв’язків можливо навіть без істотних втрат продуктивності. Інститут програмних систем НАН України 2018-07-23 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/37 PROBLEMS IN PROGRAMMING; No 1 (2012) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2012) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2012) 1727-4907 rus https://pp.isofts.kiev.ua/index.php/ojs1/article/view/37/39 Copyright (c) 2015 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2018-07-25T14:00:23Z
collection	OJS
language	rus
topic	Floating point arithmetic
spellingShingle	Floating point arithmetic Iushchenko, R.A. Essential issues of modern floating point arithmetic
topic_facet	Floating point arithmetic Арифметики с плавающей точкой
format	Article
author	Iushchenko, R.A.
author_facet	Iushchenko, R.A.
author_sort	Iushchenko, R.A.
title	Essential issues of modern floating point arithmetic
title_short	Essential issues of modern floating point arithmetic
title_full	Essential issues of modern floating point arithmetic
title_fullStr	Essential issues of modern floating point arithmetic
title_full_unstemmed	Essential issues of modern floating point arithmetic
title_sort	essential issues of modern floating point arithmetic
title_alt	Актуальные проблемы современной арифметики с плавающей запятой Актуальні проблеми сучасної арифметики з плаваючою комою
description	An overview of modern floating point arithmetic is presented. Aspects that differ from real numbers arithmetic and thus being the source of many numeric problems are emphasized. These problems scale drastically given volume of a data is large and computations being parallel. Nevertheless, it is possible to minimize and even guarantee a certain precision of the results even without considerable loss of performance.
publisher	Інститут програмних систем НАН України
publishDate	2018
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/37
work_keys_str_mv	AT iushchenkora essentialissuesofmodernfloatingpointarithmetic AT iushchenkora aktualʹnyeproblemysovremennojarifmetikisplavaûŝejzapâtoj AT iushchenkora aktualʹníproblemisučasnoíarifmetikizplavaûčoûkomoû
first_indexed	2025-07-17T09:50:29Z
last_indexed	2025-07-17T09:50:29Z
_version_	1838409649888428032
fulltext	Теоретичні та методологічні основи програмування © Р.А. Ющенко, 2012 52 ISSN 1727-4907. Проблеми програмування. 2012. № 1 УДК 004 Р.А. Ющенко АКТУАЛЬНЫЕ ПРОБЛЕМЫ СОВРЕМЕННОЙ АРИФМЕТИКИ С ПЛАВАЮЩЕЙ ЗАПЯТОЙ Представлен краткий обзор чисел с плавающей запятой и соответствующей арифметики. Подчеркнуты особенности, которые отличают ее от арифметики действительных чисел и часто являются причиной существенных проблем при численном решении задач на компьютере. Эти проблемы усиливаются для больших объемов данных и параллельных вычислений. Несмотря на все это, минимизировать и даже га- рантировать точность решений возможно даже без существенных потерь в производительности. Введение В 60-е и 70-е годы прошлого века компьютеры в основном использовались для решения сложных вычислительных задач моделирования физических и эконо- мических процессов. В таких расчетах ис- пользуются действительные числа и соот- ветствующая арифметика. Но представле- ние любого действительного числа в об- щем случае требует неограниченной памя- ти, что на компьютерах недостижимо. Это стимулировало исследования методов представлений действительных чисел, ис- пользуя конечное число двоичных разря- дов. Наиболее распространенным для вы- числительных задач и по сегодняшний день является представление с плавающей запятой, в котором обеспечивается ком- промисс амплитуды (абсолютной величи- ны) и точности. От способа представления числа зависят и свойства арифметики, по- этому разнообразие различных представ- лений в эти годы создало проблемы со- вместимости программ и аппаратуры. Од- ни и те же программы на компьютерах разных производителей возвращали раз- ный результат, иногда между решениями не было ничего общего, иногда ни одно их них вообще не имело физического смысла. Поэтому в 70-е годы была проведена ог- ромная работа по стандартизации чисел с плавающей запятой, в результате которой разработан и до настоящего времени су- ществует практически без изменений стан- дарт IEEE 754. В результате с 80-х годов работа с числами с плавающей запятой существенно упростилась, но для гарантии точности или даже осмысленности реше- ний, по-прежнему необходимо проводить специальные исследования в аксиоматике машинной арифметики [1]. Арифметика с плавающей запятой считается экзотической областью компью- терных наук, не смотря на то, что соответ- ствующие типы данных присутствуют в каждом языке программирования. И бла- годаря стандартам, в большинстве триви- альных случаев особенностью такой арифметики можно пренебречь. Но сейчас, спустя сорок лет, проблема представления чисел вновь стала актуальной сразу по не- скольким причинам. Во-первых, экспонен- циальное развитие суперкомпьютеров (за- кон Мура) привело к тому, что объемы обрабатываемых данных возросли на не- сколько порядков. В результате погреш- ность округления, не существенная для маленьких задач, снова стала значительной при обработке больших объемов данных [2]. Во-вторых, производители высокопро- изводительной техники и компиляторов часто отступают от стандартов для форси- рования скорости. Это характерно, напри- мер, для графических процессоров (гонка «мачо-флопсов») [3]. В-третьих, и здесь мы имеем дело с фундаментальной про- блемой, арифметика с плавающей запятой отличается от арифметики действительных чисел: действительные числа формируют закрытое множество, числа с плавающей запятой – нет, свойства ассоциативности и дистрибутивности в арифметике с пла- вающей запятой не выполняются, и т. д. [4]. Следствия таких побочных эффектов многократно усиливаются в параллельных вычислениях. Теоретичні та методологічні основи програмування 53 1. Основные понятия Множество целых чисел бесконечно, но всегда можно подобрать такое число разрядов (бит), чтобы представить любое целое число, возникающее при решении конкретной задачи. Множество действи- тельных чисел не только бесконечно, но еще и непрерывно, поэтому, независимо от числа разрядов, неизбежно возникнут чис- ла, которые не имеют точного представле- ния. Числа с плавающей запятой — один из возможных способов представления действительных чисел, который является компромиссом между точностью и ампли- тудой принимаемых значений. Число с плавающей запятой состоит из набора отдельных разрядов, условно разделенных на знак, порядок и мантиссу. Порядок и мантисса – наборы разрядов, которые вместе со знаком дают представ- ление числа с плавающей запятой как по- казано на рис. 1. Рис. 1. Преставление числа с плавающей запятой Математически это записывается так: (–1)s × M × BE, где s – знак, B – основание, E – порядок, а M – мантисса. Основание определяет систему счис- ления разрядов. Математически доказано [5], что числа с плавающей запятой с базой B = 2 (двоичное представление) наиболее устойчивы к ошибкам округления, поэто- му на практике встречаются только базы 2 и, реже, 10. Для простоты, не теряя общно- сти, для всех примеров будем полагать B = 2. Таким образом, формула числа с плавающей запятой будет иметь вид: (–1)s × M × 2E. Мантисса – это целое число фикси- рованной длины, которое представляет старшие разряды действительного числа. Допустим, мантисса состоит из трех бит (\|M\| = 3). Возьмем, например, число «5», которое в двоичной системе будет равно 1012. Старший бит соответствует 22 = 4, средний (который в нашем примере равен нулю) 21 = 2, а младший 20 = 1. Порядок – это степень базы (двойки) старшего разря- да. В нашем случае E = 2. Такие числа удобно записывать в так называемой «стандартной форме», например, «1.01e+2». Из такой записи видно, что мантисса состоит из трех знаков, а порядок равен двум. Допустим необходимо получить дробное число, используя те же 3 бита мантиссы. Это можно сделать, например, для E = 1. Тогда искомое число будет равно 1.01e+1 = 1×21 + 0×20 + 1×2-1 = 2 + 0,5 = 2,5. Очевидно, что таким образом одно и то же число можно представить по- разному. Рассмотрим пример с длиной мантиссы \|M\|=4. Число «2» можно пред- ставить в следующем виде: 2 = 10 (в двоичной системе) = = 1.000e+1 = 0.100e+2 = 0.010e+3. Существование нескольких пред- ставлений одного и того же числа сущест- венно усложняют сравнение этих чисел в процессоре. Поэтому уже в самых первых машинах числа представляли в так назы- ваемом нормализованном виде, когда пер- вый разряд мантиссы всегда подразуме- вался равным единице, как показано на рис. 2. Рис. 2. Нормализованное представление числа с плавающей запятой Строго говоря, нормализованное число имеет следующий вид: (–1)s × 1.M × 2E. Нормализация экономит один разряд (так как неявную единицу не нужно хра- нить в памяти) и обеспечивает уникаль- ность представления числа. В нашем при- мере «2» имеет единственное представле- ние («1.000e+1»), а мантисса хранится в памяти как «000», так как старшая единица подразумевается неявно. Но в нормализо- ванном представлении чисел возникает новая проблема – в такой форме невоз- можно представить ноль. Решений, обла- дающих своими преимуществами и недос- татками, потенциально существует множе- ство. Выбор, как и для многих парадигма- Теоретичні та методологічні основи програмування 54 тических концепций в компьютерных нау- ках, продиктован исторически сложившей- ся ситуацией. 2. Немного истории В 60-е и 70-е годы не было ни едино- го стандарта представления чисел с пла- вающей запятой, ни способов округления и арифметических операций. В результате программы были крайне не мобильны. Но еще большей проблемой было то, что у разных компьютеров были свои «странно- сти» и их нужно было знать и учитывать в программе. Например, разница двух не равных чисел могла возвращать ноль. В результате выражения «X = Y» и «X – Y = 0» вступали в противоречие. Умельцы обходили эту проблему хитрыми трюками, например, делали присваивание «X = (X – X) + X» перед операциями умно- жения и деления, чтобы избежать проблем. Инициатива создать единый стандарт для представления чисел с плавающей за- пятой совпала с попытками в 1976 году компанией Intel разработать «лучшую» арифметику для новых сопроцессоров к 8086 и i432. За разработку взялись ученые киты в этой области, проф. Джон Палмер и Уильям Кэхэн. Последний в своем интер- вью высказал мнение, что серьезность, с которой Intel разрабатывала свою арифме- тику, заставила другие компании объеди- ниться и начать процесс стандартизации [6]. Все были настроены серьезно, так как стандартизация существующей архи- тектуры давала огромное конкурентное преимущество компании, в которой такая архитектура уже реализована. Свои пред- ложения представили компании DEC, National Superconductor, Zilog, Motorola. Производители мейнфреймов Cray и IBM наблюдали со стороны. Компания Intel, разумеется, тоже представила свою новую арифметику. Авторами предложенной спе- цификации стали Уильям Кэхэн, Джероми Кунен и Гарольд Стоун и их предложение сразу прозвали «K-C-S». Практически сразу же были отбро- шены все предложения, кроме двух: VAX от DEC и «K-C-S» от Intel. Спецификация VAX была значительно проще, уже была реализована в компьютерах PDP-11, и бы- ло понятно, как на ней получить макси- мальную производительность. С другой стороны в «K-C-S» содержалось много полезной функциональности, такой как «специальные» и «денормализованные» числа (рассмотрены далее). В «K-C-S» все арифметические алго- ритмы заданы строго и требуется, чтобы в реализации результат с ними совпадал. Это позволяет выводить строгие выкладки в рамках этой спецификации. Если раньше математик решал задачу численными ме- тодами и доказывал свойства решения, не было никакой гарантии, что эти свойства сохранятся в программе. Строгость ариф- метики «K-C-S» сделала возможным дока- зательство теорем, опираясь на арифмети- ку с плавающей запятой. Компания DEC сделала все, чтобы ее спецификацию сделали стандартом. Она даже заручилась поддержкой некоторых авторитетных ученых в том, что арифме- тика «K-C-S» в принципе не может дос- тигнуть такой же производительности, как у DEC. Ирония в том, что Intel знала, как сделать свою спецификацию такой же производительной, но эти хитрости были коммерческой тайной. Если бы Intel не уступила и не открыла часть секретов, она бы не смогла сдержать натиск DEC. 3. Представление чисел с плаваю- щей запятой сегодня Разработчики «K-C-S» победили и теперь их детище воплотилось в стандарт IEEE 754, последняя редакция которого – IEEE 754-2008 [7]. Числа с плавающей за- пятой в нем представлены в виде знака (s), мантиссы (M) и порядка (E) следующим образом: (–1)s × 1.M × 2E. Вообще говоря, в стандарте IEE 754- 2008 кроме чисел с основанием 2 присут- ствуют числа с основанием 10, так назы- ваемые десятичные (decimal) числа с пла- вающей запятой. В данной статье для про- стоты такое представление не рассматри- вается. Чтобы не загромождать читателя чрезмерной информацией, рассмотрим только один тип данных, с одинарной точ- Теоретичні та методологічні основи програмування 55 ностью (single). Числа с половинной (half), двойной (double) и расширенной (extended) точностью обладают теми же особенно- стями, но отличаются числом разрядов порядка и мантиссы. В числах одинарной точности порядок состоит из 8 бит, а ман- тисса – из 23. Эффективный порядок опре- деляется как «E – 127». Например, число 0,15625 будет записано в памяти как Рис. 3. Пример числа с плавающей запятой в IEEE754 (из Википедии) В этом примере: знак s = 0 (положи- тельное число), порядок E = 011111002 – 12710 = –3, мантисса M = 1.012 (первая единица неяв- ная). В результате число F = 1.012e-3 = = 2 – 3 + 2 – 5 = 0,125 + 0,03125 = 0,15625 Специальные числа. IEEE 754 чис- ло «0» представляется значением с поряд- ком, равным «E = Emin – 1» (для single это – «127») и нулевой мантиссой. Введение нуля как самостоятельного числа (так как в нормализованном представлении нельзя представить ноль) позволило избежать многих странностей в арифметике. И хоть операции с нулем нужно обрабатывать отдельно, обычно они выполняются быст- рее, чем с обычными числами. Также в IEEE 754 предусмотрено представление для специальных чисел, работа с которыми вызывает исключение. К таким числам относится бесконечность (±∞) и неопределенность (NaN). Эти числа позволяет вернуть адекватное значение при возникновении исключительных си- туаций. Бесконечности представлены как числа с порядком E = Emax + 1 и нулевой мантиссой. Получить бесконечность мож- но при переполнении и при делении нену- левого числа на ноль. Бесконечность при делении разработчики определили исходя из существования пределов, когда делимое и делитель стремиться к какому-то числу. Соответственно, c/0 = ±∞ (например, 3/0 = +∞, а –3/0 = –∞), так как если де- лимое стремиться к константе, а делитель к нулю, предел равен бесконечности. При 0/0 предел не существует, поэтому резуль- татом будет неопределенность. Неопределенность или NaN (от not a number) – это представление, введенное для того, чтобы арифметическая операция могла всегда вернуть какое-то не бессмыс- ленное значение. В IEEE 754 NaN пред- ставлен как число, в котором E=Emax+1, а мантисса не нулевая. Любая операция с NaN возвращает NaN. При желании в ман- тиссу можно записывать информацию, которую программа сможет интерпретиро- вать. Стандартом это не оговорено и ман- тисса чаще всего игнорируется. Значение NaN возникает при выпол- нении любой из следующих операций: ∞ + (– ∞), 0 × ∞, 0/0, ∞/∞, sqrt(x), где x < 0. По определению NaN ≠ NaN, поэто- му, для проверки значения переменной нужно просто сравнить его с самим собой. Ноль со знаком. Поскольку в IEEE754 число «0» представлено фиксиро- ванным значением порядка и мантиссы, знак может быть произвольным. В резуль- тате число «0» имеет два представления, отличающиеся знаком. Так, «3·(+0)=+0», а «3 · (– 0) = – 0». В стандарте знак сохра- нили умышленно, чтобы выражения, кото- рые в результате переполнения или потери значимости превращаются в бесконеч- ность или в ноль, при умножении и деле- нии все же могли представить максималь- но корректный результат. Например, если бы у нуля не было знака, выражение «1 / (1 /x ) = x» не выполнялось бы верно при «x = ±∞», так как «1 / ∞» и «1 / –∞» равны «0». Однако по определению приня- то, что «+0 = –0». Это позволяет избежать дополнительных затруднений и странно- стей. Еще один пример: (+∞ / 0) + ∞ = +∞, тогда как (+∞ / –0) + ∞ = NaN. Чем бесконечность в данном случае лучше, чем «NaN»? Тем, что если в ариф- метическом выражении появился «NaN», результатом всего выражения всегда будет «NaN». Если же в выражении встретилась бесконечность, то результатом может быть Теоретичні та методологічні основи програмування 56 ноль, бесконечность или обычное число с плавающей запятой. Например, 1 / ∞ = 0. Денормализованные числа. Пусть имеем нормализованное представление с длиной мантиссы «\|M\| = 2» бита (плюс один бит нормализации) и диапазоном значений порядка «–1 ≤ E ≤ 2». В этом случае получим 16 чисел (рис. 4). Рис. 4. Нормализованное представление числа с плавающей запятой Крупными штрихами показаны числа с мантиссой, равной «1,00». Видно, что расстояние от нуля до ближайшего числа («0 – 0,5») больше, чем от этого числа к следующему («0,5 – 0,625»). Это значит, что разница двух любых чисел от «0,5» до «1» даст «0», даже если эти числа не рав- ны. Что еще хуже, в пропасть между «0,5» и «0» попадает разница чисел, больших 1. Например, 1,5 – 1,25 = 0 (см. рис. 4). В «околонулевую яму» подпадает не каждая программа. Согласно статистике 70-х годов в среднем каждый компьютер сталкивался с такой проблемой один раз в месяц. Учитывая, что компьютеры приоб- ретали массовость, разработчики «K-C-S» посчитали эту проблему достаточно серь- езной, чтобы решать ее на аппаратном уровне. Предложенное ими решение со- стояло в следующем. Мы знаем, что при «E = Emin – 1» (для single это «–127») и ну- левой мантиссе число считается равным нулю. Если же мантисса не нулевая, то число считается не нулевым, его порядок полагается «E = Emin», причем неявный старший бит мантиссы полагается равным нулю. Такие числа называются денормали- зованными. Строго говоря, числа с плавающей запятой теперь имеют вид: (–1)s × 1.M × 2E, если Emin ≤ E ≤Emax (нормализованные числа) (–1)s × 0.M × 2Emin, если E = Emin – 1. (денормализованные числа) Вернемся к примеру, в котором «Emin = –1». Введем новое значение поряд- ка, «E = –2», при котором числа являются денормализованными. В результате полу- чаем новое представление чисел (рис. 5). Рис. 5. Денормализованные числа Интервал от «0» до «0,5» заполняют денормализованные числа, что дает воз- можность не проваливаться в ноль в рас- смотренных выше примерах («0,5 – 0,25» и «1,5 – 1,25»). Это сделало представление более устойчивым к ошибкам округления для чисел, близких к нулю. Но роскошь использования денорма- лизованного представления чисел в про- цессоре не дается бесплатно. Из-за того, что такие числа нужно обрабатывать по- другому во всех арифметических операци- ях, трудно сделать работу такой арифме- тики эффективной. Это накладывает до- полнительные сложности при реализации АЛУ в процессоре. Кроме того, несмотря на свою полезность, денормализованные числа не являются панацеей и за округле- нием до нуля все равно нужно следить. Поэтому эта функциональность стала кам- нем преткновения при разработке стандар- та и встретила самое сильное сопротивле- ние разработчиков оборудования. Влияние денормализованных чи- сел на производительность. Денормали- зованные числа требуют особой обработки и, как показали эксперименты [8], это ска- зывается на производительности про- грамм. Причины и масштабы падения про- изводительности зависят от конкретной реализации арифметики на данном обору- довании. Наиболее пагубные последствия возникают в случае возникновения исклю- чений и программной нормализации. Поскольку в работе [8] эксперименты проведены на весьма устаревших процес- сорах, автор решил повторить его на со- временном оборудовании и проиллюстри- ровать в данном обзоре. Суть эксперимен- та в следующем: пусть дана матрица, на краях которой заданы некоторые значения, а все остальные элементы равны нулю. Эксперимент состоит из множества итера- Теоретичні та методологічні основи програмування 57 ций, на каждой из которых строиться но- вая матрица, каждый элемент которой представляет среднее значение от сосед- них элементов исходной матрицы. Такой класс алгоритмов является характерным для конечно-разностных методов числен- ного решения дифференциальных уравне- ний в частных производных. На рис. 6 схематически показано, как меняются элементы от итерации к итера- ции. Вначале все элементы матрицы, кро- ме крайних, равны нулю (рис. 6, а). Далее, через несколько десятков итераций сосед- ние элементы матрицы становятся на- сколько малыми, что их невозможно пред- ставить в нормализованном виде. Штри- хом на рис. 6, б показаны обычные значе- ния, а жирной линией – денормализован- ные числа. Некоторое время количество денормализованных чисел растет (рис. 6, в), после чего уменьшение площади внут- ренней границы уменьшается и с ними, со временем, исчезают и денормализованные числа. После определенной итерации в матрице таких чисел не остается совсем (рис. 6, г). а б в г Рис. 6. Заполнение матрицы денормали- зованными числами Из рис. 7 видно, что существует яв- ная корреляция времени вычисления ите- рации и количества денормализованных чисел в матрице в этот момент, что пока- зывает наличие проблем с производитель- ностью у денормализованных чисел даже на современных процессорах. Время вычисления итераций 0 4 8 12 16 20 1 201 401 601 801 1001 Итерация Вр ем я, м с а Количество денормализованных чисел 0 4 8 12 16 1 201 401 601 801 1001 Итерация N , т ы ся чи б Рис. 7. Графики: а – времени вычисления итераций; б – количество денорма- лизованных чисел на итерации Эксперимент проведен на компьюте- ре Intel Core 2 Duo 2.14 ГГц, использована матрица размером 500x500, и значение на краях V = 100, тип данных одинарной точ- ности. Отметим, что в эксперименте с двойной точностью наблюдается анало- гичная картина. На пике графика ~6% чи- сел являются денормализованными, при этом производительность падает в два раза, поэтому вычисления следует ожидать потерю производительности в 30 раз, если все числа являются денормализованными. Одним из побочных эффектов экспе- римента можно считать то, что на началь- ных итерациях время вычислений в два раза ниже, чем на 1000-ной. Таким обра- зом, работа со специальными числами (по Теоретичні та методологічні основи програмування 58 крайней мере с нулем), в два раза быстрее, чем с обычными числами с плавающей запятой. Очередность чисел в IEEE754. Од- на из особенностей представления чисел в формате IEEE754 состоит в том, что поря- док и мантисса расположены друг за дру- гом таким образом, что они вместе обра- зуют последовательность целых чисел {n} для которых выполняется: n < n + 1 � F(n) < F(n + 1), где F(n) – число с плавающей запятой, об- разованное от целого n, разбиением его битов на порядок и мантиссу. Поэтому если взять положительное число с плавающей запятой, преобразовать его к целому, прибавить «1», мы получим следующее число, которое представимо в этой арифметике. На Си это можно сделать так (Этот код будет выполняться коррект- но только на архитектуре с 32-битным ти- пом «int»): float a = 0.5; int n = ((int) &a); float b = ((float) &(++n)); printf("После %e следующее число: %e, разница (%e)\n", a, b, b-a); Округление. Анализ погрешностей округления охватывает слишком широкую область знаний, даже при попытке выде- лить наиболее важные аспекты, связанные со спецификой чисел с плавающей запя- той. Для подробного ознакомления смот- рите книгу Хигхема [9]. Ошибочные результаты при числен- ных расчетах в арифметике с плавающей запятой возникают по трем причинам: по- грешности исходных данных, погрешности представления, погрешности, вносимые арифметическими операциями. Последние два вида погрешностей характерны для чисел с плавающей запятой. Погрешность представления возникает из-за того, что действительные числа практически всегда невозможно представить в виде числа с конечным числом разрядов. Но такая по- грешность очень мала, и ее можно регули- ровать, выбирая тип данных. Погрешность, вносимая арифметическими операциями, может быть очень существенной, из-за аддитивного и мультипликативного эф- фектов, возникающих, если результаты одних операций используются в качестве аргументов для других. При увеличении числа итераций погрешность растет и очень быстро выходит за допустимые пре- делы. Наиболее опасная с точки зрения по- грешностей операция – вычитание разно- значных чисел. Такая операция уничтожа- ет значимые старшие разряды и усиливает младшие разряды, которые представлены с погрешностью. Используя алгебраические преобразования можно существенно сни- зить погрешность. Для многих широко распространенных математических фор- мул разработаны специальные формы, ко- торые позволяют значительно уменьшить погрешность. Например, формулу «x2 – y2» лучше вычислять следующим образом: «(x – y)(x – y)». В этом случае вычитание не окажет катастрофического воздействия на результат. В работах [5, 9] приведено множество формул, рекомендуемых при расчете в арифметике с плавающей запя- той, а также теоремы, доказывающие гра- ницы погрешности. Минимизировать погрешность ариф- метических операций помогает стандарт. В правилах округления в IEEE754 сказано, что результат любой арифметической опе- рации должен быть таким, как если бы он был выполнен над точными значениями и округлен до ближайшего числа, предста- вимого в этом формате. Уменьшить ошиб- ки округления помогают также денормали- зованные числа. Но такой подход требует от АЛУ наличия двух дополнительных скрытых разряда в регистрах, а также от- дельную ветку обработки денормализо- ванных чисел. Некоторые опции компиля- тора (такие как «–ffast-math» в gcc) могут отключить полную поддержку IEEE754, из-за чего погрешность округления может существенно возрасти. Неассоциативность арифметиче- ских операций. Неассоциативность ариф- метических операций над числами с пла- вающей запятой очевидна на следующем примере: (1020 + 1) – 1020 = 0 ≠ ≠ (1020 – 1020) + 1 = 1. Теоретичні та методологічні основи програмування 59 Допустим, имеем программу сумми- рования чисел: double s = 0.0; for (int i=0; i<n; i++) s = s + t[i]; Некоторые компиляторы по умолча- нию могут переписать код для использова- ния нескольких АЛУ одновременно (будем считать, что n делится на «2»): double sa[2], s; sa[0]=sa[1]=0.0; for (int i=0; i<n/2; i++) { sa[0]=sa[0]+t[i2+0]; sa[1]=sa[1]+t[i2+1]; } S=sa[0]+sa[1]; Поскольку операции суммирования не ассоциативны, эти две программы мо- гут выдать различный результат. Выбор минимума из двух значений. Допустим из двух значений нам нужно выбрать минимальное. В Си это можно сделать одним из следующих способов: x < y? x: y; x <= y? x: y; x > y? y: x; x >= y? y: x. Часто компилятор считает их эквива- лентными и всегда использует первый ва- риант, так как он выполняется за одну ин- струкцию процессора. Но если мы учтем ±0 и NaN, эти операции никак не эквива- лентны (таблица). Сравнение чисел. Очень распро- страненная ошибка при работе с числами с плавающей запятой возникает при провер- ке на равенство. Например, float fValue = 0.2; if (fValue == 0.2) DoStuff(); Ошибка здесь, во-первых, в том, что «0,2» не имеет точного двоичного пред- ставления, а, во-вторых, «0,2» – это кон- станта двойной точности, а переменная fValue – одинарной, и никакой гарантии о поведении этого сравнения нет. Немного лучший, но все равно ошибочный способ, это сравнивать разницу с допустимой аб- солютной погрешностью: if (fabs(fValue – fExpected) < 0.0001) DoStuff(); // fValue=fExpected? Недостаток такого подхода в том, что погрешность представления числа увели- чивается с ростом самого этого числа. Так, если программа ожидает «10000», то при- веденное равенство не будет выполняться для ближайшего соседнего числа «10000,000977». Это особенно актуально, если в программе имеется преобразование из одинарной точности в двойную и/или наоборот. Проблема выбора правильной проце- дуры сравнения хорошо описана в работе Брюса Доусона [10]. В ней предлагается сравнивать числа с плавающей запятой преобразованием к целочисленной пере- менной. Это – лучший способ, хотя и ра- ботает не на любом оборудовании. В этой программе maxUlps (от Units-In-Last-Place) – это максимальное количество чисел с плавающей запятой, которое может лежать между проверяемым и ожидаемым значе- нием. Другой смысл этой переменной – это количество двоичных разрядов (начиная с младшего) в сравниваемых числах разре- шается упустить. Например, «maxUlps=16», означает, что младшие 4 бита (log216) могут не совпадать, а числа все равно будут считаться равными. При этом, при сравнении с числом «10000» аб- солютная погрешность бу дет равна «0,0146», а при сравнении с «0.001», по- грешность будет менее 0.00000001 (10 – 8). Алгоритм проиллюстрирован на рис. 8. Параллельные вычисления. В па- раллельных вычислениях использование чисел с плавающей запятой иногда приво- дит к тому, что результат вычислений за- висит от количества процессов, использо- ванных в конкретном случае. Хорошим примером является эксперимент, сделан- ный Т. Мэттсоном [11], в котором сум- Таблица. Вычисление минимума и максимума для специальных чисел x y x < y ? x: y x <= y ? x: y x > y ? y: x x >= y ? y: x +0 –0 – 0 + 0 +0 –0 NaN 1 1 1 NaN NaN Теоретичні та методологічні основи програмування 60 bool AlmostEqual2sComplement(float A, float B, int maxUlps) { // maxUlps не должен быть отрицательным и не слишком большим, чтобы // NaN не был равен ни одному числу assert(maxUlps > 0 && maxUlps < 4 * 1024 * 1024); int aInt = (int)&A; // Уберем знак в aInt, если есть, чтобы получить правильно // упорядоченную последовательность if (aInt < 0) aInt = 0x80000000 - aInt; // Аналогично для bInt int bInt = (int)&B; if (bInt < 0) bInt = 0x80000000 - bInt; unsigned int intDiff = abs(aInt - bInt); if (intDiff <= maxUlps) return true; return false; } Рис. 8. Алгоритм Б. Доусона сравнения чисел с плавающей запятой мирование случайных чисел в массиве из 20 тысяч элементов приводит, в зависимо- сти от числа процессов, к значительной разнице в результате. Суть проблемы па- раллельной агрегации большого числа значений в том, что при разработке парал- лельного алгоритма применяются алгеб- раические преобразования, исходящие из ассоциативности арифметических опера- ций. Так, формулу можно пере- писать как . При этом частные суммы можно рассчитать независимо на отдельных процессорах. Повторяя разбиение можно получить эф- фективный каскадный параллельный алго- ритм, который с точки зрения арифметики с плавающей запятой содержит неодно- значности, так как конечный результат зависит от порядка суммирования (см. п. 3.7). Это приводит к недетерминированно- сти результата. ∑ = = n i ixS 1 ∑∑ +== +=+= n ni i n i i xxSSS 12/ 2/ 1 21 Хигхем [9] рекомендует использо- вать для агрегации переменную более вы- сокой точности, чем исходные значения – это наиболее простой способ сократить погрешность округления, который, к тому же, автоматически работает в параллель- ных вычислениях. Если же такой подход по какой-то причине не приемлем (напри- мер, значения и так представлены в мак- симально возможной точности), можно воспользоваться одним из рекомендован- ных алгоритмов «суммирования с компен- сацией» [12], например, показанным на рис. 9. double CompensatedSum(double *x, int count) { s=0; e=0; temp=0; y=0; for (i=0; i<count; i++) { temp = s; y = x[i] + e; s = temp + y; e = (temp – s) + y; } } Рис. 9. Алгоритм Кэхэна суммирования с компенсацией Несмотря на приведенные трудности, понимание свойств арифметики с плаваю- щей запятой позволяет использовать их для обеспечения точных результатов даже на пониженной разрядности. Так, в своей параллельной библиотеке PLASMA Д. До- нгарра и др. [13] комбинируют арифмети- ку одинарной и двойной точности для оп- тимизации скорости программы без ущер- ба точности конечного результата. Но не для всех задач фиксированная разрядность чисел с плавающей запятой подходит для достижения корректного результата. В этом случае применяют эму- лируемую арифметику с произвольной разрядностью. Скорость решения в этом случае падает в десятки раз. В работах Ни- колаевской и Чистяковой проведены ис- следования таких задач и проиллюстриро- Теоретичні та методологічні основи програмування 61 вано практическое применение эмулируе- мой арифметики [14]. Проверка полноты поддержки IEEE 754. Для того, чтобы арифметика с плавающей запятой удовлетворяла стан- дарту IEEE 754 необходима поддержка со стороны аппаратуры и компилятора. Ино- гда, даже если компилятор поддерживает арифметику IEEE 754, по умолчанию эта поддержка выключена для «оптимизации скорости». Уильям Кэхэн предложил про- грамму на Си и Фортране, которая позво- ляет проверить соответствие связки «архи- тектура – компилятор – опции» стандарту IEEE754 [15]. Аналогичная программа доступна и для графических процессоров [3]. Так, например, компилятор Intel (icc) по умолчанию использует «расслаблен- ную» модель IEEE754, и в результате не все тесты выполняются. Опция «–fp–model precise» позволяет компилировать про- грамму с точным соответствием стандарту. В компиляторе GCC использование опции «–ffast–math» приводит к несоответствию IEEE 754. Заключение Арифметика с плавающей IEEE 754, используемая практически во всех совре- менных компьютерах, спроектирована та- ким образом, который позволяет избавить- ся от многих странностей, возникающих при попытке представления действитель- ных чисел конечным числом разрядов. Наличие нуля, денормализованных чисел, специальных чисел (бесконечностей и не- определенности), устойчивых алгоритмов округления и требований к погрешности арифметических операций позволяет ана- литическими методами гарантировать точ- ность решений в рамках этой арифметики. Не смотря на это, так называемый «наив- ный подход», при котором не учитывается аксиоматика машинной арифметики, мо- жет привести к неожиданным результатам. Особенно следует отметить проявле- ние недетерминированности арифметики с плавающей запятой в параллельных вы- числениях при использовании каскадных алгоритмов агрегации, поскольку такие алгоритмы исходят из предположения ас- социативности, которые в этом случае не выполняются. Проблема точности реше- ний в параллельных компьютерах усили- вается тем, что на них как правило реша- ются задачи большого объема, а погреш- ность представления чисел увеличивается при росте числа итераций. Единого решения, которое смогло бы удовлетворить одновременно требованиям точности и скорости не сегодняшний день не существует, и в каждом конкретном случае приходится искать компромиссы. 1. Молчанов И.Н. Машинная математика. Проблемы и перспективы // Кибернетика и системный анализ. – 2004. – № 6. – С. 65 – 72. 2. Молчанов И.Н., Перевозчикова О.Л., Химич А.Н. Опыт разработки семейства кластер- ных комплексов «Инпарком» // Киберне- тика и системный анализ. – 2009. – № 6. – С. 88 – 96. 3. http://www.cs.unc.edu/~ibr/projects/paranoia/. 4. http://software.intel.com/en-us/videos/tim- mattson-floating-points-arent-real/. 5. Goldberg D. What Every Computer Scientist Should Know About Floating-Point Arithme- tic // ACM Computing Surveys. – 1991. – N 23, Vol. 1. – P. 5 – 48. 6. Severance C. An Interview with the Old Man of Floating-Point // IEEE Computer. – 1998. – N 1. – P. 114 – 115. 7. IEEE 754-2008 Standard for Floating-Point Arithmetic. 8. Bjørndalen J.M., Anshus O.J. Trusting float- ing point benchmarks - are your benchmarks really data independent?, Proceedings of the 8th international conference on Applied paral- lel computing: state of the art in scientific computing, June 18 – 21, 2006, Umeå, Swe- den. 9. Higham N. Accuracy and Stability of Numerical Algorithms. 10. http://www.cygnus- software.com/papers/comparingfloats/compari ngfloats.htm. 11. http://software.intel.com/en-us/videos/tim- mattson-floating-points-arent-real/. 12. Kahan W. Implementation of algorithms. Technical Report 20, Department of Computer Science, University of California, Berkeley, CA, USA, 1973. 13. Buttari A., Dongarra J., Kurzak J., Luszczek P., Tomov S. Using Mixed Precision for Теоретичні та методологічні основи програмування 62 Sparse Matrix Computations to Enhance the Performance while Achieving 64-bit Accu- racy // ACM Transactions on Mathematical Software. – 2008. – Vol. 34, N 4. – P. 17 – 22. 14. Николаевская Е.А., Чистякова Т.В. Про- граммно-алгоритмические методы повы- шения точности компьютерных решений // Кибернетика и системный анализ. – 2009. – № 6. – С. 172 – 176. 15. http://www.cs.unc.edu/~ibr/projects/paranoia/. Получено 21.06.2011 Об авторе: Ющенко Руслан Андреевич, кандидат физико-математических наук, научный сотрудник. Место работы автора: Институт кибернетики им. В.М. Глушкова НАН Украины, 03187, Киев, проспект Академика Глушкова, 40. Тел.: +38044 526 3603, e-mail: pgt@ukr.net АКТУАЛЬНЫЕ ПРОБЛЕМЫ СОВРЕМЕННОЙ АРИФМЕТИКИ С ПЛАВАЮЩЕЙ ЗАПЯТОЙ Введение 1. Основные понятия 2. Немного истории 3. Представление чисел с плавающей запятой сегодня Заключение

Essential issues of modern floating point arithmetic

Institution

Ähnliche Einträge