区间算术的优化方法

在进行浮点运算时,计算结果的准确性是一个重要的考量。区间算术提供了一种方法来评估和保证计算的准确性。它通过将单个浮点数替换为包含该值的数值范围来实现这一点。例如,使用米制卷尺测量一个3米乘4米的房间可能会得到精确到0.5厘米的结果,这可以表示为[2.995, 3.005]乘以[3.995, 4.005]。区间算术的任何操作都以一种保持这种属性的方式执行。例如,区间的加法([a_inf, a_sup], [b_inf, b_sup])将得到[a_inf + b_inf, a_sup + b_sup]。

基本实现

区间算术的基本思想是对每个操作执行两次——一次在“舍入到负无穷大”(RD)模式下,一次在“舍入到正无穷大”(RU)模式下。虽然这种方法保证有效,但它有以下缺点:每次操作都需要三次改变舍入模式——到RU,到RD,然后回到默认模式(通常是“舍入到最近”或RN)。在大多数现代处理器上,这些切换非常昂贵。例如,在最新的Intel处理器上,读取SSE舍入模式是昂贵的,而设置它是一个序列化操作!

RU方法

对于某些操作,一种有效的方法是利用RD(a) == -RU(-a)的事实。为了做到这一点,将区间存储为[-a, b]而不是[a, b]。很明显,加法/减法可以直接使用RU执行,而乘法和除法可能需要一些额外的符号位翻转。这种方法的优点是:每次操作只需要两次舍入模式切换;允许使用SIMD指令进行加法/减法。然而,它不能普遍使用。例如,sqrt(-a) == NaN,而不是-sqrt(a)。

“舍入到最近”方法

区间算术的问题归结为选择问题。给定一个无限精确的结果A作为其中一个界限,如果要计算区间的下界,需要向下舍入,或者如果要计算区间的上界,需要向上舍入。发现这个信息是可用的。此外,为了使这个工作,需要使用“舍入到最近”模式。

精确变换

给定两个浮点数a和b,可以按照以下方式计算精确变换:

TwoSum() - (a, b)被转换为(s,e),使得s = RN(a + b)和e = a + b - s

s = RN(a + b)

a' = RN(s - b)

b' = RN(s - a')

da = RN(a - a')

db = RN(b - b')

e = RN(da + db)

TwoSum()算法需要6次浮点运算。

TwoProd - (a, b)被转换为(p, e),使得p = RN(a * b)和e = a * b - p

Split(x, n)需要C = 2^n + 1,其中n = (mantissa的位数 + 1)/2

t1 = RN(C * x)

t2 = RN(x - t1)

xh = RN(t1 + t2)

xl = RN(x - xh)

TwoProd(x, y)

(xh, xl) = Split(x, s)

(yh, yl) = Split(y, s)

p = RN(x * y)

t1 = RN(-p + RN(xh * yh))

t2 = RN(t1 + RN(xh * yl))

t3 = RN(t2 + RN(xl * yh))

e = RN(t3 + RN(xl * yl))

TwoProd()算法需要17次浮点运算。

如果e是负数,那么RN(a + b) == RU(a + b),RD(a + b) == prev(s)。如果e是正数,那么RN(a + b) == RD(a + b),RU(a + b) == succ(s)。TwoProd()也有类似的论证。

基本函数

TwoSum()和TwoProd()过程足以执行区间加法/减法和乘法。如果存在fma()操作(在IEEE 754-2008下是强制性的),可以计算以下函数:

TwoProdFMA(a, b)

p = RN(a * b)

e = fma(a, b, -p)

TwoProdFMA()算法执行TwoProd(),但只需要2次浮点运算,而不是17次。

Division() - q = RN(a / b); r = -fma(q, b, -a)

Reciprocal() - q = RN(1.0 / b); r = -fma(q, b, -1.0)

Sqrt() - q = RN(sqrt(a)); r = -fma(q, q, -a)

如果r是负数,那么结果 = RN(A) == RU(A),RD(A) == prev(result)。如果r是正数,那么结果 = RN(A) == RD(A),RU(A) == succ(result)。

注意:prev(x)和succ(x)由IEEE Std 754要求,并且在C++ 2011中作为std::nextafter()实现。如果硬件中没有fma()操作,可以使用TwoProd()和TwoSum()操作在软件中模拟。这需要总共35次浮点运算——17次用于TwoProd(),18次用于所需的3次TwoSum()操作。

测试

测试了以下C++实现的区间算术:

“基本”区间算术——根据需要设置RU、RD和默认舍入模式

“RU”区间算术——将[a, b]存储为[-a, b],消除了在许多情况下将舍入模式设置为RD的要求。

“舍入到最近”区间算术——实现了本文中定义的算法。

在所有情况下,如果可用且有用,都使用了SIMD指令。

测试涉及1亿次操作,使用随机操作数,如下所示:

加法

乘法

除法(分母的区间不包括0.0)

平方sqr(x) = (x*x)

平方根

hypot(x, y) = sqrt(sqr(x), sqr(y))。

选择hypot()函数是因为它包括加法(可以通过RU方法优化),平方(也可以通过RU方法优化),以及平方根(只能通过“舍入到最近”方法优化)。它也可以很容易地用简单的C++代码计算。

代码使用Visual Studio 2013在x64 Release模式下编译,使用/fp:strict编译器选项。注意,如果需要获得准确的结果,使用这个选项是必要的。

在Intel Core i7 2670QM处理器上的测试结果(以每次操作的纳秒数表示)如下:

速度测试结果

操作 基本 RU 舍入到最近
加法 104 79 25
乘法 230 194 61
除法 280 217 94
平方 238 185 42
平方根 139 83 44
hypot() 804 702 173

注意:时间是在减去循环开销和生成随机输入所需的时间后给出的。与最新的Intel处理器不同,这个2670QM处理器没有硬件中的fma(),并且必须在软件中模拟它。这显著降低了“舍入到最近”方法在乘法、除法、平方和平方根操作中的优势。

使用舍入到最近模式的区间算术库是可行的,并且在当前流行的硬件上——比定向舍入方法快3倍以上。

目前正在开发一个区间数学包,它将包括IEEE-1788标准为区间算术所需的大部分前向函数。

IEEE Std 754-2008

IEEE Std 1788-2015

《浮点数运算手册》,Jean-Michel Muller等人,Birkhäuser

沪ICP备2024098111号-1
上海秋旦网络科技中心:上海市奉贤区金大公路8218号1幢 联系电话:17898875485