间距对速度、错误和内存使用的影响
比较断点间距类型的标准
下面几节比较了使用断点的查找表的实现,这些断点的间距是不均匀的、均匀的和2的幂。比较的重点是:
命令执行速度
插补时舍入误差
用于存放数据的只读存储器(ROM)的容量
命令的ROM容量
这种比较仅在断点不可调时有效。如果在生成的代码中断点是可调的,那么所有三种情况都会生成相同的代码。有关断点间距对执行速度、错误和内存使用的影响的摘要,请参见断点间隔的影响总结.
说明断点间距影响的模型
这个比较使用了模型fxpdemo_approx_sin
.这个模型中出现了三个定点查找表。这三个表都近似于这个函数罪(2 *π* u)
在第一象限上,实现最坏情况误差小于2 ^ 8
.但是,它们对断点间距有不同的限制。
你可以使用这个模型fxpdemo_approx
,这fxpdemo_approx_sin
打开,生成金宝app®编码器™代码(金宝app仿真软件编码器需要软件许可证)。下面几节给出了生成的几段代码,以强调关键区别。
要打开模型,请在MATLAB中输入®提示:
fxpdemo_approx_sin
每个查找表所需的数据ROM
本节将介绍三种间距选项中每一种所需的数据ROM。
不均匀的情况
不均匀间距需要Y个数据点和断点:
int16_T yuneven [8];uint16_T xuneven [8];
使用的总字节数为32。
甚至情况
即使间隔只需要Y个数据点:
int16_T yeven [10];
使用的总字节数为20。断点不是明确要求的。代码使用断点之间的间距,并可能使用最小和最大的断点。最多需要三个与断点相关的值。
两种情况的幂
两次间隔的幂只需要Y个数据点:
int16_T ypow2 [17];
使用的总字节为34。断点不是明确要求的。代码使用断点之间的间距,并可能使用最小和最大的断点。最多需要三个与断点相关的值。
确定超出范围的输入
在这三种情况下,都必须防止输入小于最小断点或大于最大断点。在处理这些可能性的方式上可能存在差异。然而,这些差异通常很小,通常不是决定使用一种间距方法而不是另一种间距方法的关键因素。后面的部分假设超出范围的输入是不可能的或者已经处理过了。
查找表如何确定输入位置
本节描述三个定点查找表如何确定当前输入相对于断点的位置。
不均匀的情况
间隔不均匀的断点需要通用算法(如二进制搜索)来确定输入相对于断点的位置。下面的代码提供了一个示例:
iLeft = 0;右= 7;/*断点个数减1 */ while ((iLeft - iLeft) > 1) {i = (iLeft + iright) >> 1;if (uAngle < xequal [i]) {irt = i;} else {iLeft = i;}}
while循环执行到log2(N)次,其中N是断点的个数。
甚至情况
均匀间隔的中断点只需要一个步骤来确定输入相对于中断点的位置:
iLeft = uAngle / 455U;
的因子455 u
表示断点之间的间距。一般来说,红利是(uAngle - SmallestBreakPoint)
.在本例中,最小的断点为零,因此代码优化了减法。
两种情况的幂
两个间隔断点的幂只需要一步来确定输入相对于断点的位置:
iLeft = uAngle >> 8;
移位的次数是8,因为断点有间隔2 ^ 8
.最小的断点是0,所以uAngle
的一般情况(uAngle - SmallestBreakPoint)
.
比较
为了确定输入相对于断点的位置,间隔不均匀的情况比其他两种情况需要更多的代码。这段代码需要额外的命令ROM。如果许多查找表共享二进制搜索算法作为一个函数,您可以减少这个ROM损失。即使代码是共享的,在间隔不均匀的情况下,确定输入位置所需的时钟周期数量也比其他两种情况要高得多。如果代码是共享的,函数调用开销会稍微降低执行速度。
在等距情况和两倍距情况下,您可以用一行代码确定输入的位置。等距情况使用一般整数除法。2的幂使用移位而不是一般除法,因为除数是2的幂。如果不知道具体的处理器,就不能确定移位比除法更好。
许多处理器可以用一个汇编语言指令实现除法,所以代码会比较小。然而,这条指令通常需要很多时钟周期才能完成。许多处理器不提供除法指令。这些处理器上的除法是通过重复的减法进行的。这个过程很慢,需要大量的机器代码,但是这些代码可以共享。
大多数处理器都提供了一种左移和右移的逻辑和算术方法。关键的区别在于处理器是可以在一条指令中进行N次移位(桶移位),还是需要N条指令一次移位一位。桶移位需要更少的代码。枪管换挡是否也能提高速度取决于支持操作的硬件。金宝app
编译器也会使比较变得复杂。在前面的例子中,命令8 . uAngle >>
本质上是取16位字的上8位。编译器可以检测到这种情况,并使用直接取位的指令替换位移位。如果移位数是其他值,例如7,则不会发生这种优化。
每个查找表的插值
理论上,你可以用下面的代码计算插值:
y = (yData[iLeft] - yData[iLeft]) * (u - xData[iLeft])…/ (xData[iLeft] - xData[iLeft]) + yData[iLeft]
这个词(xData[iright] - xData[iLeft])
相邻断点之间的间距。如果这个值是常数,由于间隔均匀,一些简化是可能的。如果间距不仅是偶数,而且是2的幂,那么对于定点实现来说,就有可能进行重大简化。
不均匀的情况
对于不均匀情况,理想插值在不动点上的一种可能实现方式是:
xNum = uAngle - xequal [iLeft];xDen = xequal [right] - xequal [iLeft];yDiff = yuneven[右]- yuneven[左];MUL_S32_S16_U16(bigProd, yDiff, xNum);DIV_NZP_S16_S32_U16_FLOOR(yDiff, bigProd, xDen);yUneven = yUneven [iLeft] + yDiff;
这里没有显示乘法和除法例程。这些例程可能很复杂,并且依赖于目标处理器。例如,这些例程在16位处理器和32位处理器中看起来是不同的。
甚至情况
均匀间隔断点实现插值的计算方法与不均匀间隔断点略有不同。关键的区别在于计算不直接使用断点。当ROM中不需要断点时,可以节省大量内存。
xNum = uAngle - (iLeft * 455U);yDiff = yeven[iLeft+1] - yeven[iLeft];MUL_S32_S16_U16(bigProd, yDiff, xNum);DIV_NZP_S16_S32_U16_FLOOR(yDiff, bigProd, 455U);yEven = yEven [iLeft] + yDiff;
两种情况的幂
两个间隔断点的幂实现插值使用与其他两种情况非常不同的计算。与偶数情况一样,在生成的代码中不使用断点,因此在ROM中不需要。
lambda = uAngle & 0x00FFU;yPow2 = yPow2 [iLeft] +1] - yPow2 [iLeft];MUL_S16_U16_S16_SR8 (yPow2λ,yPow2);yPow2 += yPow2 [iLeft];
与不均匀的实现相比,这种实现具有显著的优势:
一个按位与运算加上乘法运算末尾的右移运算将取代减法运算和除法运算。
这个词
(u - xData[iLeft]) / (xData[iright] - xData[iLeft])
结果在精度上没有损失,因为间距是2的幂。而对于不均匀和均匀情况,在计算时通常会引入舍入误差。
断点间隔的影响总结
下表总结了断点间隔对执行速度、错误和内存使用的影响。
参数 |
2间隔数据的偶数次幂 |
等距数据 |
非均匀间隔数据 |
---|---|---|---|
执行速度 |
执行速度最快。位置搜索和插值与等间距数据相同。然而,为了进一步提高速度,位移位取代了位置搜索,位掩码取代了插值。 |
执行速度比不均匀间隔数据快,因为位置搜索更快,插值需要简单的除法。 |
执行速度是不同间距中最慢的,因为位置搜索较慢,插值需要更多的操作。 |
错误 |
误差可能比非均匀间隔的数据更大,因为近似具有非均匀曲率的函数需要更多的点才能达到相同的精度。 |
误差可能比非均匀间隔的数据更大,因为近似具有非均匀曲率的函数需要更多的点才能达到相同的精度。 |
误差可以更小,因为近似一个具有非均匀曲率的函数需要更少的点来实现相同的精度。 |
罗的使用 |
使用更少的命令ROM,但更多的数据ROM。 |
使用更少的命令ROM,但更多的数据ROM。 |
使用更多的命令ROM,但更少的数据ROM。 |
内存使用情况 |
不显著。 |
不显著。 |
不显著。 |
Y个数点遵循预期的模式。对于同样的最坏情况错误,不受限制的间距(不均匀)需要最少的数据点,而两个间隔的幂的断点需要最多的数据点。但是,在生成的代码中实现等距和幂的两种情况并不需要断点。这使他们的数据ROM需求减少了一半。因此,均匀间隔的情况实际上比非均匀间隔的情况使用更少的数据ROM。而且,两种情况下的功率只需要比不均匀情况下稍多一点的ROM。改变最坏情况的错误可以改变这些排名。尽管如此,当您比较数据ROM的使用情况时,您应该始终考虑到这样一个事实,即两种间隔情况的均匀间隔和幂不需要在ROM中设置它们的断点。
确定当前输入相对于断点的位置的工作强烈倾向于均匀间隔和两种间隔情况的幂。对于间隔不均匀的情况,您可以使用循环到log2(N)次的二分搜索方法。使用偶数和幂二的间距,您可以通过执行一行C代码来确定位置。但是,如果不了解硬件和C编译器的详细知识,您就无法判断两个函数和均匀间隔函数的相对优势。
计算插值的努力有利于两种情况的力量,它使用按位AND操作和移位来取代减法和除法。这种行为的优势取决于特定的硬件,但可以预期在代码大小、速度和准确性方面具有优势。均匀间隔的情况计算插值的效率比非均匀间隔的情况略有提高。