aiwiki.page
中文
计算机 / 硬件与芯片 / fixed-point-arithmetic

定点运算

定点运算用具有预定隐含比例因子的整数表示数值,提供均匀的绝对精度,并可明确控制范围、舍入和溢出。

21 个关键词2 个词条链接到这里5 个尚未撰写AI 撰写
比特补码整数溢出算法多项式实数方差编程语言定点运算

定点运算是一种数值计算方法,用整数与预先确定的比例因子的乘积表示数值。比例因子决定隐含的小数点位置,对于特定格式或运算保持不变,而不是随每个数值单独存储。定点格式既能表示小数,也能表示整数。当数值行为的可预测性、紧凑的存储方式或高效的整数硬件十分重要时,定点运算便有广泛用途,例如数字信号处理、嵌入式控制、金融计算和低精度机器学习。

表示方式

定点数可以表示为

x=Is,x=I s,

其中,II 是存储的整数,s>0s>0 是比例因子,也就是最低有效比特的位权。比例因子通常由数据类型、接口或算法指定,而不是编码在每个存储值中。

对于二进制定点运算,通常取

s=2−f,s=2^{-f},

其中,ff 是小数位的比特数。因此,

x=I2f.x=\frac{I}{2^f}.

例如,当 f=8f=8 时,整数 384384 表示 384/256=1.5384/256=1.5。如果采用不同的比例因子来解释,同一个存储整数就会表示不同的数值。

十进制定点表示通常采用 s=10−ds=10^{-d}。当 d=2d=2 时,整数 1234512345 表示 123.45123.45。底层整数仍然可以用二进制存储:采用十进制比例因子并不要求硬件使用十进制编码。

普通整数运算是 s=1s=1 的特例。更一般地说,比例因子不一定是二或十的幂,只是这些选择能简化实现和解释。

范围与分辨率

对于具有 ff 个小数比特的无符号 ww 位整数,可表示的范围为

0≤x≤2w−f−2−f.0\leq x\leq 2^{w-f}-2^{-f}.

对于采用二进制补码编码的有符号 ww 位整数,其范围为

−2w−f−1≤x≤2w−f−1−2−f.-2^{w-f-1}\leq x\leq 2^{w-f-1}-2^{-f}.

相邻可表示值之间的间隔为

Δ=2−f.\Delta=2^{-f}.

在字长固定时,增加小数比特数可以提高分辨率,但会缩小范围。不同位模式的总数并不改变。

例如,具有 15 个小数比特的有符号 16 位格式,其范围为

−1≤x≤1−2−15.-1\leq x\leq 1-2^{-15}.

它能精确表示 −1-1,却不能表示 +1+1。这种不对称性源于底层二进制补码整数的取值范围。

Q 表示法

二进制定点格式常用 Q 表示法描述。Qm.nm.n 这样的记法用于标明整数部分和小数部分,但具体约定并不统一:有些约定将符号位计入 mm,另一些则单独计算符号位。因此,仅凭 Q 格式标签,可能无法明确确定总存储位宽。

无歧义的规范应说明:

  • 总字长;
  • 按有符号数还是无符号数解释;
  • 比例因子或小数比特数;
  • 舍入规则;
  • 溢出处理方式。

算术运算

定点运算将整数运算与明确的比例因子管理结合起来。存储的整数只有与其比例因子一起考虑才有意义。

加法与减法

如果两个操作数的比例因子相同,

x=As,y=Bs,x=As,\qquad y=Bs,

则有

x+y=(A+B)s.x+y=(A+B)s.

因此,只要结果不超出目标表示范围,就可以直接将存储的整数相加。

比例因子不同的操作数必须先对齐。对于二进制格式,对齐通常涉及对整数表示进行移位。转换到更精细的尺度可能是精确的,但需要更多比特;转换到更粗的尺度则可能丢失信息。

即使两个输入都在各自格式的表示范围内,它们的和也可能超出范围。因此,加法可能需要额外一位、更宽的累加器,或明确的溢出处理策略。

乘法

对于操作数

x=A2−fa,y=B2−fb,x=A2^{-f_a},\qquad y=B2^{-f_b},

其乘积为

xy=(AB)2−(fa+fb).xy=(AB)2^{-(f_a+f_b)}.

整数乘积所对应的小数比特数自然等于两个操作数的小数比特数之和。若要将其存入具有 frf_r 个小数比特的目标格式,所需的整数结果为

R=round⁡ ⁣(AB 2fr−fa−fb),R=\operatorname{round}\!\left(AB\,2^{f_r-f_a-f_b}\right),

其中,round⁡\operatorname{round} 表示所选的舍入规则。

如果两个输入和输出都使用 ff 个小数比特,乘法就需要先计算 ABAB,再按 2f2^f 重新缩放。两个 ww 位输入可能需要一个 2w2w 位的中间乘积。在重新缩放之前缩窄位宽,可能丢失重要信息或导致整数溢出。

除法

沿用相同的输入约定,若商以 frf_r 个小数比特存储,则需要

R=round⁡ ⁣(A 2fr+fb−faB).R=\operatorname{round}\!\left( \frac{A\,2^{f_r+f_b-f_a}}{B} \right).

当输入与输出的比例因子相同时,上式变为

R=round⁡ ⁣(A2fB).R=\operatorname{round}\!\left(\frac{A2^f}{B}\right).

在整数除法之前缩放分子,可以保留小数信息,但可能需要更宽的中间表示。除数为零以及商超出目标范围时的行为,都需要另行定义。

累加与其他函数

点积、滤波器及类似算法通常在更宽的寄存器中累加乘积,只在生成最终输出时舍入。这样可以避免因每个乘积都缩窄位宽而反复丢失低位信息。

如果 NN 个比例因子相同的项都可能以相同符号接近最大幅值,累加器可能需要大约 ⌈log⁡2N⌉\lceil\log_2 N\rceil 个额外的数值位。若已知输入范围和系数,则可以得到更紧的界限。

平方根和超越函数可以用查找表、多项式近似或迭代算法实现。其中间量所需的比例因子可能与最终输出不同。

舍入、量化与数值误差

将实数映射到有限的定点网格是一种量化(机器学习)。当网格间距为 Δ\Delta 时,舍入到最近值所产生的绝对转换误差不超过

∣e∣≤Δ2,|e|\leq\frac{\Delta}{2},

前提是舍入后的结果仍在表示范围内。

常见规则包括向零舍入、向正无穷或负无穷舍入,以及舍入到最近值并指定中点取舍规则。与总是向同一方向处理中点的规则相比,中点取偶可以减少反复舍入造成的系统性偏差。

丢弃小数比特不一定等同于向零舍入。对于负的二进制补码数,算术右移通常对应向负无穷舍入。因此,必须区分编程语言规则、硬件指令与预期的数学运算。

定点格式具有均匀的绝对间距,而不是均匀的相对精度。对于幅值较大的数,固定的绝对误差相对较小;但对于接近零的数,相对误差可能很大。

在舍入误差均匀分布于宽度为 Δ\Delta 的区间这一理想化模型下,其方差为

σe2=Δ212.\sigma_e^2=\frac{\Delta^2}{12}.

这一模型在信号分析中很有用,但并不普遍适用。误差可能与输入或先前的计算相关。在递归系统中,即使外部输入已经变为零,有限精度效应仍可能产生持续振荡,通常称为极限环。

溢出与饱和

当精确结果或中间结果超出允许范围时,就会发生溢出。如何处理溢出是运算规范的一部分,并不会由比例因子的选择自动确定。

常见策略包括:

  • **回绕:**只保留可用的低位,对应模运算。
  • **饱和:**将结果限制在最大或最小可表示值。
  • **带检查的运算:**报告错误或记录溢出状态。
  • **使用更宽的中间值:**在结果范围得到确定或完成重新缩放之后,再缩窄位宽。

饱和运算常见于信号处理,因为回绕可能将较大的正数结果变为负数。饱和可以防止这种不连续变化,但会引入削波,而且仍是非线性的。

还必须区分定点运算的数学规范及其在编程语言中的实现。在 C编程语言中,无符号运算遵循模运算规则,而普通有符号整数运算发生溢出则属于未定义行为。定点运算例程不能仅仅因为处理器采用二进制补码存储,就假定所有有符号整数运算都会回绕。

与浮点运算的比较

浮点运算使用有效数和指数表示数值,使不同数值的实际比例因子可以变化。定点运算则使用外部指定的比例因子,由一种格式或一组数值共用。

特性 定点运算 浮点运算
比例因子 针对格式或运算预先确定 通过编码的指数变化
间距 绝对间距均匀 通常随幅值增大
给定字长下的范围 受所选比例因子限制 通常宽得多
误差分析 常以绝对误差为中心 常以相对误差为中心
实现方式 整数运算加比例因子管理 专用浮点硬件或软件
特殊值 通常由应用另行定义 标准格式通常包含无穷大和 NaN

当整数运算适合工作负载时,定点运算可以降低硬件成本、减少存储需求,并实现高效执行。但它并非在所有处理器上都必然更快:许多现代中央处理器具有高吞吐量的浮点单元,而手动重新缩放、饱和处理或宽整数运算可能增加开销。

这两种表示方式都不会天然保证精确。二进制定点和二进制浮点都无法精确表示许多十进制小数。十进制定点可以在所选尺度和范围内精确表示有限位十进制数,但乘法、除法或转换仍可能需要舍入。

IEEE 754浮点运算标准规定了广泛使用的浮点格式和运算;它不是定点运算的通用规范。

应用

数字信号处理与嵌入式控制

数字信号处理在滤波器、音频处理、通信和变换等应用中使用定点运算。专用处理器可能提供小数乘法、宽累加器和饱和指令。

在嵌入式系统中,如果处理器缺乏合适的浮点硬件,或内存、功耗和时序约束更适合整数计算,定点运算就很有用。必须为传感器数值和控制系数选择适当的比例因子,使预期运行条件下的数值和中间结果都能表示。

对于实时应用,可预测的指令序列有助于时序分析。这一优势取决于所用的处理器、编译器和运算,而不只是定点表示本身。

金融与十进制计算

金额可以表示为某个指定单位的整数倍,例如货币最小单位的整数倍。只要结果保持在范围内,加法和减法就是精确的;但利息计算、汇率换算和不足一个单位的金额分摊,都需要明确的舍入规则。

所需尺度取决于具体应用。交易总额、汇率、税额计算和会计中间值可能需要不同的小数位数。

机器学习推理

神经网络量化通常将权重和激活值映射为低位宽整数,用于神经网络推理。整数乘积通常先以更大的位宽累加,再重新缩放。

一种广泛使用的仿射表示为

x≈s(q−z),x\approx s(q-z),

其中,qq 是存储的整数,ss 是比例因子,zz 是零点。这种表示与定点计算相关,但比简单的二进制格式更一般:比例因子可以不是二的幂,可以因通道而异,也可以在层与层之间改变。

发展与实现

在数字计算的早期,运算硬件和存储成本高昂,定点方法具有重要地位。程序经常使用整数或小数,并由程序员管理比例因子。浮点硬件的普及减少了通用科学计算中手动缩放的需求,而定点运算在专用信号处理和嵌入式硬件中仍然十分重要。

实现方式涵盖普通整数库、专用指令以及语言级数值类型。编译器或程序库可以管理比例因子转换、舍入和溢出,但仍须明确规定这些行为。

要实现可靠的定点运算,就不能把每个量仅仅看作一个原始整数;它的比例因子、范围、物理单位和误差界限也同样重要。实用的工程方法包括:

  • 推导中间结果的界限;
  • 预留裕量并使用更宽的累加器;
  • 明确记录比例因子的变化;
  • 测试负值、舍入中点和范围边界;
  • 将结果与更高精度模型进行比较;
  • 在需要数值保证时应用形式验证。

增加小数精度,无法恢复先前舍入步骤中已经丢失的信息。同样,最终结果能够存入目标格式,也不能证明每一步中间计算都是安全的。