我在哪里可以了解微控制器（例如 ARMv7）上 C 语言的最佳数学运算？

Question

我正在尝试优化某些功能，但我意识到我对某些事情需要多长时间几乎一无所知。

我可以在这里提出所有问题，但如果有人知道的话，我宁愿找到一篇关于该主题的好文章。

我正在使用 IAR 为 ATMEL SAM7S 处理器编写 C 程序。我有一个需要 500uS 左右的排序函数，我想看看是否可以加快速度。我也可以将其发布在这里，但我希望自己学习。

例如，两个 16 位整数相减比两个 32 位整数相减更快吗？这样的手术需要多长时间？只是一个周期还是多个周期？与减法相比，乘法需要多长时间？

有人知道哪里可以看吗？我尝试用谷歌搜索一些东西，但找不到任何有用的搜索词。

如果有人对我的具体功能有任何想法，我可以发布详细信息。我基本上试图将两个模拟值与校准值表中最接近的索引相匹配。现在，我迭代整个表并使用最小二乘法来确定最接近的匹配。它非常简单，我不确定是否有更快的方法而不对我的表应用一些额外的逻辑。但如果我至少知道某些事情花了多长时间，我可能可以自己优化它。

Answer 1

一个好的第一阶段可能是研究您正在编码的架构的汇编语言。

之后，您应该能够读取编译器生成的二进制文件，并最终比较计算机对两种不同实现的实际操作。

Answer 2

您可以使用 SAM7S 中的计时器。在开始时读取一个计时器，并在 N 次搜索后读取它并减去以获得差值。尝试不同的算法，看看你会看到什么。

至于 16 位数学与 32 位数学，是的，可能存在巨大差异，但您必须查看您的架构。两个寄存器之间的减法运算将占用相同的一个时钟，无论是 16 位还是 32 位。但是来自 C 代码的变量最终可能会进入内存，你必须知道你是否有 16 位或 32 位数据总线（是的 ARM7 可以有 16 位总线，看看 GameBoy Advance，拇指代码的运行速度明显快于该处理器上的 ARM 代码）。在 16 位总线上读取或写入 32 位数字需要两倍的周期。不过，您可能没有 16 位总线。在 32 位处理器上使用 16 位变量会导致处理器必须添加额外的指令来剥离或扩展高位，以便 16 位变量的数学计算正确。这些额外的指令可能会导致性能下降，一个简单的减法可能是 3 或 4 条指令，最坏的情况现在可能是 5 或 6 条，如果它处于紧密循环中，这会很明显。一般来说，您希望使用与处理器寄存器大小相匹配的变量，在 32 位 ARM 上，即使您只数到 10，也尽可能使用 32 位变量。

希望我能理解您在这里试图解决的问题，如果不是的话让我知道，我将编辑/删除此响应：

根据测量中的位数，您正在做的事情的典型解决方案是使用查找表。我可以举一个例子，假设您正在进行 4 位测量并想要校准。将其称为 0 到 15。传感器的校准生成了一个数据点列表，可以说：

raw cal
0x03  16
0x08  31
0x14  49

我假设您在运行时所做的事情是这样的，如果传感器读取 0x5，您将查看列表以查找传感器读取的条目匹配或位于两个校准点之间。

搜索你会发现它在 0x03 和 0x08 之间，以从原始 0x05 测量中获取校准结果。

cal=  (((0x05-0x03)/(0x08-0x03))*(31-16)+16 = 22

其中有一个除法，这对大多数处理器来说是一个巨大的性能杀手，特别是 ARM7，因为它没有除法。不确定繁殖情况，但你也想避免像瘟疫这样的疾病。如果您考虑一下所有这些需要多少条指令。

相反，您要做的是采用运行时使用的算法，并在临时程序中从所有可能的输入生成所有可能的输出：

0  7
1  10
2  13
3  16
4  19
5  22
6  25
7  28
8  31
9  34
10 37
11 40
12 43
13 46
14 49
15 52

现在将其转换为运行时代码中的表：

unsigned char cal_table[ 16]={7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52};

然后运行时

cal = cal_table[raw&15];

实现此功能的代码如下所示：

ldr r3, =cal_table
and r0, r0, #15
ldrb    r0, [r3, r0]

需要 5 个时钟来执行。

搜索完表格后，从原始数据中找到 cal 的数学计算如下：

cal=  (((raw-xlo)/(xhi-xlo))*(yhi-ylo)+ylo);

看起来像这样：

docal:
    stmfd   sp!, {r3, r4, r5, lr}
    ldr r3, .L2
    ldr r5, .L2+4
    ldr lr, .L2+8
    ldr ip, [r5, #0]
    ldr r0, [r3, #0]
    ldr r1, [lr, #0]
    ldr r2, .L2+12
    rsb r0, ip, r0
    rsb r1, ip, r1
    ldr r5, [r2, #0]
    bl  __aeabi_uidiv
    ldr r4, .L2+16
    ldr r3, .L2+20
    ldr r4, [r4, #0]
    rsb r5, r4, r5
    mla r4, r0, r5, r4
    str r4, [r3, #0]
    ldmfd   sp!, {r3, r4, r5, pc}

除法函数即使不是更糟，也同样糟糕。查找表应该使您的代码运行速度提高数十倍。

查找表的问题是你需要用内存来换取性能，因此你必须有一个足够大的表来涵盖所有可能的输入。例如，12 位传感器会在查找表中提供多达 4096 个条目。如果你知道测量值永远不会低于 0x100，你可以将表设置为 0x1000 - 0x100 或 3840 个条目，并在查找之前从原始值中减去 0x100，在运行时交换几个指令以节省几百个字节记忆。

如果表太大，您可以尝试一些其他技巧，例如制作高位的查找表，其输出可能是校准表中预先计算的偏移量以开始搜索。因此，如果您有一个 12 位 ADC，但没有空间容纳 4096 个条目查找表，您可以制作一个 16 个条目查找表，获取 ADC 输出的高 4 位并用它来查找表。该表将包含校准表中要开始搜索的条目。假设您的校准表有这些条目：

....
entry 27 raw = 0x598 cal = 1005
entry 28 raw = 0x634 cal = 1600
entry 29 raw = 0x6AB cal = 1800
entry 30 raw = 0x777 cal = 2000

您的 16 深度查找表将有这些条目

...
[6] = 27;
[7] = 29;
...

您将如何使用它而

start = lut[raw>>8];
for(i=start;i<cal_tab_len;i++)
{
...
}

不是

for(i=0;i<cal_tabl_len;i++)
{
}

它可能会大大缩短在表中查找条目以供您执行数学运算所需的时间需要。

对于获取原始值并在运行时将其转换为校准值的特定问题，有许多类似的快捷方式。我不知道有哪一本书可以涵盖所有这些内容。采用哪条路径与您的处理器、内存系统和可用性以及数据的大小和性质有很大关系。如果您的处理器不支持除法（使用很少的时钟周期），您通常希望避免特别是除法和乘法。大多数处理器没有。 （是的，大多数程序员瞄准的一两个处理器确实具有单周期乘法和除法）。即使对于具有单周期乘法和除法的处理器，它们通常也必须用 C 库包装，以确定使用硬件指令执行操作是否安全，或者是否必须使用库进行综合。我上面提到，对于大多数变量，您希望匹配处理器的本机寄存器大小。如果您有定点乘法或除法，您通常会希望使用处理器寄存器大小的一半。对于 32 位处理器，除非您花时间详细检查指令，否则您可能希望将倍数限制为具有 32 位输出的 16 位输入，并除以具有 16 位输出的 32 位输入，并希望优化器可以帮助您出去。

再次强调，如果我错误地假设了您试图解决的问题是什么，请发表评论，我将编辑/修改此回复。

Answer 3

两个 16 位整数相减比两个 32 位整数相减更快吗？

不是在具有本机 32 位寄存器的 ARM 架构上，不是。

有人知道哪里可以看吗？

指令周期计时的规范位置是芯片实现的特定架构的技术参考手册，例如。 ARM7TDMI;简单的 alu 操作的时间这里是的，这是一个周期。如果您还不太熟悉说明集，那么这不是一个友好的文档，但是......

现在我遍历整个表

在这里查看算法优化（例如索引表、按一个坐标排序以缩小范围等）比担心指令级微优化要好得多。