assembly - 如何减少阶乘循环的执行时间和周期数？和/或代码大小？

Question

基本上，我很难使执行时间比实际时间要短，并且要减少时钟周期和内存大小。有谁知道我该怎么做吗？该代码工作正常，我只想稍作更改。

编写了有效的代码，但是不想弄乱代码，也不想知道要进行哪些更改。

; Calculation of a factorial value using a simple loop

; set up the exception addresses
THUMB
AREA RESET, CODE, READONLY
EXPORT  __Vectors
EXPORT Reset_Handler
__Vectors 
DCD 0x00180000     ; top of the stack 
DCD Reset_Handler  ; reset vector - where the program starts

AREA 2a_Code, CODE, READONLY
Reset_Handler
ENTRY
start   
MOV r1,#0    ; count the number of multiplications performed 
MOV r2,#3    ; the final value in the factorial calculation
MOV r3,#1    ; the factorial result will be stored here

; loop r2 times forming the product  
fact
ADD r1,r1,#1  ; find the next multiplicand
MUL r3,r1,r3  ; form the next product - note that MUL r3,r3,r1 gives unpredictable output
CMP r1,r2     ; check if the final value has been reached
BMI fact      ; continue if all products have not been formed

exit    ; stay in an endless loop 
B exit
END

当前结果是：
内存大小：0x00000024
时钟周期：22
总执行时间：1.1微秒

我们正在使用Cortex M3

我只需要减少其中的任何一个，只要代码产生不同的结果，对代码的更改就可以很小。

Answer 1

通常，代码大小和性能是一个折衷方案。展开循环通常有助于提高性能（至少对于大型输入而言），但是在循环外部需要额外的逻辑来处理清理等。



大多数答案是假设使用诸如Cortex-A9或Cortex-A53之类的高性能CPU，其中通过软件流水线创建指令级并行性会有所帮助。 Cortex M3是标量的，具有单周期乘法指令，因此优化起来要容易得多。

（最初的问题没有指定内核，我期望即使是低端CPU也会具有多周期mul延迟。在编写它之后，我才发现Cortex-M3编号。）

您的代码可能会成为整数乘法延迟的瓶颈。与add不同，在下一个周期将准备好结果，而mul则很复杂，需要多个周期才能生成结果。

（除了在某些时钟非常慢的芯片上，例如Cortex-M3显然具有1周期的mul指令。但该指令的Cortex-M0/M0+/M23 are available with a choice的性能为1周期或32周期性能！缓慢的迭代=更小的硅。）



乘法执行单元本身通常是流水线式的，因此可以一次运行多个独立的乘法，但是阶乘循环需要将每个乘法结果作为下一次迭代的输入。 （仅适用于高性能内核，而不是Cortex-M系列。慢速Cortex-M芯片上的32周期乘法是迭代的，并且可能没有流水线，因此在运行时无法启动另一个乘法，因此没有任何好处。除了减少循环开销之外，还公开任何指令级并行性。）

请注意，乘法是关联的：1 * 2 * 3 = 3 * 2 * 1，因此我们可以从n倒数，就像@ensc的答案指出的那样。或(1*2) * (3*4) = 1*2*3*4。

相反，我们可以与1 * 2 * ... * (n/2)并行执行n/2+1 * n/2+2 * n/2+3 * ... * n，在这两个依赖链上进行交织工作。或者我们可以在执行1 * 3 * 5 * ... * n并从中计算出2 * 4 * 6 * ... n-1的循环中将n -= 2与n+1交错。 （然后，最后将这两个乘积相乘）。

显然，这将需要更多的代码大小，但可能会大大提高性能。



当然，查找表是另一个解决方法。如果您只关心不会溢出32位结果的输入，那将是一个很小的表。但是，这有很大的尺寸成本。



即使在有序CPU（指令执行必须以程序顺序开始）上，长时间运行的指令（如高速缓存未命中加载或乘法）也可能会被允许无序完成，例如在启动add之后但在回写mul结果之前，某些mul指令可能会运行。甚至在更早的mul延迟的阴影下启动另一个独立的mul指令。

我搜索了一些ARM性能数据，以了解典型的性能。

例如，Cortex-A9是一个较旧的，相当常见的高端ARMv7 CPU，它具有超标量（每个周期多条指令）且无序执行。

mul "takes" 2 cycles, and has 4 cycle result latency。他们没有解释非延迟成本的含义。也许这就是执行单元的互惠吞吐量，例如您可以多久启动一次新的独立操作。这是一个乱序的CPU，因此将其他指令停顿2个周期没有任何意义。在NEON SIMD instruction section中，他们解释了看起来像相同的“循环”数字：


这是特定指令消耗的发布周期数，如果没有操作数互锁，则是每条指令的绝对最小周期数。


（操作数互锁=如果较早的指令尚未产生结果，则等待输入操作数准备就绪）。

（Cortex-A9确实支持压缩整数乘法，因此对于大型阶乘，您可以使用vmul.32 q1, q1, q2每4个周期从一个向量开始并行执行4次乘法。或者使用64位d寄存器每2个周期进行2次乘法，但是那么您需要更多的vadd指令，而与乘法不同，vadd.32与128位q regs一样快，与64位向量一样快。因此，SIMD可以为您在Cortex- A9，如果您使用足够的寄存器来隐藏较大的延迟，但是SIMD可能仅对n有用，因为n!太大，以致mul溢出32位整数，因此得到模2 ^ 32的结果。）



较低延迟的ARM乘法指令：

muls是32x32 => 32位乘法。在Cortex-A9上，它具有2c的吞吐量和4c的延迟。

（mul是Thumb模式下的16位指令，除非不需要消除标志，否则应首选smulbb。Thumb模式下的smulxy仅在ARMv6T2和更高版本中可用。）

muls是16x16 => 32位有符号乘法，仅读取其输入的低半部分，但在A9上具有1c吞吐量和3c延迟。 （BB =底部，底部。也可以使用其他组合，以及乘累加和各种时髦的东西。）

没有2个字节的Thumb版本的smulxy，因此对于代码大小而言，这要比int16_t更糟糕。

不幸的是，uint16_t在无符号版本中不可用，因此将我们可以使用的输入范围限制为正数sqrt(n!)，而不是(n-1)! * n。

但是，如果我们只关心最终的32位结果没有溢出的情况，我们可以安排操作顺序，以便最后一个乘法具有2个大小相似的输入（均为大的16位数字）。即尽可能接近(n-1)!。所以赔率和偶数的乘积是合理的，但是n是最坏的情况，因为这需要1适应16位。实际上，最坏的情况是从smulbb开始倒数，因此最后一个是乘以3再乘以2。



将这些部分放在一起，请注意，乘以n-1是无操作的操作（n除外，它将输入截断为16位）。因此，我们可以根据输入为奇数或偶数，以乘以1或2后停止的方式展开。

因此，我们只知道lo（以subs开头）和hi（以smulbb开头）而不是知道奇数和偶数。

;; UNTESTED, but it does assemble with the GNU assembler, after sed -i 's/;/@/' arm-fact.S
;; and replacing THUMB with
; .thumb
; .syntax unified
THUMB

;; Input: n in r0.   (n is signed positive, otherwise we return n.)
;; Output: n! in r0.
;; clobbers: r1, r2, r3
;; pre-conditions: n! < 2^31.  Or maybe slightly lower.
fact:
    subs   r3, r0, #3   ; r3 = lo = n-3  (first multiplier for loprod)
    bls   .Ltiny_input
    subs   r2, r0, #2   ; r2 = hi = n-2  (first multiplier for hiprod)
    subs   r1, r0, #1   ; r1 = loprod = n-1
                        ; r0 = hiprod = n

.Lloop:                 ; do {
    smulbb  r0,r0, r2      ; hiprod *= hi
    subs    r2, #2         ; hi -= 2 for next iter
    smulbb  r1,r1, r3
    subs    r3, #2         ; lo -= 2 for next iter
    bgt     .Lloop       ; while((lo-=2) > 0);  signed condition
    ; r3 = 0 or -1, r2 = 1 or 0.  The last multiplies were:
    ;       hiprod *= 2 and loprod *= 1  for even n
    ;   or  hiprod *= 3 and loprod *= 2  for odd n

    ; muls  r0, r1
    smulbb  r0,r0, r1      ; return  hiprod *= loprod

    bx lr    ; or inline this

.Ltiny_input:   ; alternate return path for tiny inputs
    ; r0 = n.   flags still set from  n - 3
    IT eq                  ; GAS insists on explicit IT for thumb mode
    moveq   r0, #6         ; 3! = 6, else n! = n for smaller n=1 or 2.
                           ; 0! = 1 case is not handled, nor are negative inputs
    bx lr

（标签名称中的.L使其成为一个本地标签，至少在GAS语法中没有显示在目标文件中。如果使用的是汇编器，则可能不在ARMASM中。）

ARM汇编使您可以在目标与第一个源相同的情况下忽略目标，而对于某些说明，如 subs r2, r2, #2却不是 muls r0, r1。如果需要，您可以每次将其写为 hiprod。

您可能将 loprod用于最终产品，因为最终的 hiprod比 mul d,d, src高一点。即使 sub> max int16_t，产品也可能不会溢出。这也将节省2个字节的代码大小，但会在Cortex-A9上增加1个周期的延迟。 （顺便说一句，ARMv6用 subs怪异修正了“不可预测的结果”，并且您的代码使用了32位Thumb2指令，因此无论如何它仅适用于ARMv6T2及更高版本。）



如果有2个用于产品的累加器，那么在Cortex-A9上，这可能每3个周期以2倍的速度运行，这在很大程度上取决于CPU的微体系结构及其前端是否可以保持。在有序ARM上，我担心它在乘法完成之前能够启动其他指令。

最好在 smulbb而不是 loprod上多花2个字节，以便我们可以在分支之前计算几个指令的标志，从而减少分支的错误预测损失并避免有序CPU停顿。 hi不会触摸标志，因此我们可以先执行 r3并使 r2东西不触摸标志。

.loop:                  ; do {
    smulbb  r1, r3       ; loprod *= lo
    subs    r3, #2       ; lo -= 2 for next iter, and set flags
    smulbb  r0, r2       ; hiprod *= hi
    sub     r2, #2       ; hi -= 2 for next iter (no flags)
    bgt     .loop       ; while((lo-=2) >= 0);

请注意，在 smulbb读取它们之后，我们将立即修改 subs Rd, Rn, #imm和 sub，以避免为顺序芯片上的数据相关性造成停顿。



您正在使用Thumb模式并针对代码大小进行优化，因此了解哪些形式的指令可以使用2字节/ 16位编码以及哪种形式仅可作为32位Thumb2编码非常重要。

SP can be encoded as a 16-bit Thumb instruction for imm=0..7（3位立即数）。或使用与src和目的地相同的寄存器，用于imm = 0..255。因此，我的复制和订阅说明非常紧凑。

除IT块内部或以 moveq r0, #6作为操作数外，无标志设置的 IT不能是16位指令。

Thumb模式下的谓词指令（例如 n==0）要求汇编器使用 cmp r0,#0 instruction为下一个最多4条指令引入谓词。在ARM模式下，每个指令的高4位表示预测。 （如果您不使用后缀，则汇编程序会将其编码为始终（即不带谓词）。）

我们可以用 moveq r0, #1 / cbnz处理另外4或6个字节的 mov r0, #1情况。如果我们将tst / mov放在同一IT块中，则可能将其减少到4个字节。 IT不会快照实际的标志条件，而是快照谓词，因此IT块中的标志设置指令可能会影响同一块中的后续指令。 （我认为这是正确的，但我不确定100％）。

tiny_input:    ; r0 = n,  flags set according to n-3
    ITET EQ
    moveq  r0, #6
    cmpne  r0, #0
    moveq  r0, #1

或者，有 16-bit cbnz有条件地跳过 0! = 1。但是分支目标必须在 mov之后从4到130个字节，因此，显然我们不能仅跳过一条16位指令！



我的版本的代码大小：

$ arm-none-eabi-gcc -g -c -mcpu=cortex-a9 arm-fact.S
$ arm-none-eabi-objdump -drwC arm-fact.o 

arm-fact.o:     file format elf32-littlearm


Disassembly of section .text:

00000000 <fact>:
   0:   1ec3            subs    r3, r0, #3
   2:   d90b            bls.n   1c <.tiny_input>
   4:   1e82            subs    r2, r0, #2
   6:   1e41            subs    r1, r0, #1

00000008 <.loop>:
   8:   fb10 f002       smulbb  r0, r0, r2
   c:   3a02            subs    r2, #2
   e:   fb11 f103       smulbb  r1, r1, r3
  12:   3b02            subs    r3, #2
  14:   dcf8            bgt.n   8 <.loop>
  16:   fb10 f001       smulbb  r0, r0, r1
  1a:   4770            bx      lr

0000001c <.tiny_input>:
  1c:   bf08            it      eq
  1e:   2006            moveq   r0, #6
  20:   4770            bx      lr

因此，此功能为0x22字节。 （如果要处理 mul，则为0x26。）

它比您的版本大（您的字节数包括内存中的一些常量以及 b<cond>指令来产生输入），但是从理论上讲，对于具有流水线乘法器的CPU，大输入的速度可能要快两倍。对于从1到3的输入来说，它可能要快得多，它只分支一次并产生结果。



您可能没有Cortex-A9之类的东西，因为您的1.1微秒= 22个时钟周期意味着20MHz的时钟速度，而Cortex-A9的可用频率为0.8至2GHz。

因此，也许您有一个像 Cortex M3这样更简单的有序内核？ M3确实支持 bx lr指令和Thumb2模式。维基百科说它的乘法是1个周期！所以这很奇怪，我很惊讶它具有如此高效的乘数。或仅仅是因为它的时钟太慢，以至于在1级中有很多门延迟的时间，而这只是3级流水线。



Cortex-M3版本：

subs和muls是Cortex-M3上的单周期。我没有在树枝上找到性能数字，但是它们很常见，所以我假设它可能是1个周期，并且不会引起较大的读取泡沫（如果正确预测……）。 Cortex-M3 HTML手册的 Branch target forwarding部分有一个关于减少获取气泡的部分。

其 instruction timing table表示 0! = 1花费1个周期（未使用）或2个周期（使用）。 （1用于分支，1用于在立即移位后重新加载管道。）。因此，与sub / mul相比，采用分支的速度慢，展开很有价值，因此上面的代码仍然可以正常工作。 （但是不需要多个产品累加器，因此可以简化）。

针对代码大小进行优化：

;; UNTESTED
THUMB

;; Input: n in r0.   (n is signed positive, otherwise we return n.)
;; Output: n! in r0.
;; clobbers: r1
fact:
    subs   r1, r0, #1     ; i = n-1
    bls   .Ltiny_input    ; jump if n<=1

.Lloop:                 ; do {
    muls    r0, r1         ; prod *= i
    subs    r1, #1         ; --i
    bgt     .Lloop      ; while(--i > 0);  signed condition
    ; r1 = 0, r0 = n! 
    ; last multiply was a redundant prod *= 1 but avoiding that would take a cmp
.Ltiny_input:   ; alternate return path for tiny inputs
    ; 0! = 1 case is not handled, nor are negative inputs


    bx lr    ; or inline this

我认为这是我们可以管理的最小事务。该循环有3条指令，每次迭代可能花费4个周期（1 + 1 + 2，所采用的分支花费2个周期）。

00000000 <fact>:
   0:   1e41            subs    r1, r0, #1
   2:   d902            bls.n   a <fact+0xa>
   4:   4348            muls    r0, r1
   6:   3901            subs    r1, #1
   8:   dcfc            bgt.n   4 <fact+0x4>
   a:   4770            bx      lr           # don't count this if inlining

因此，这是0xa = 10字节，不计算 IT返回指令。

我们可以在分支的第一个 subs之后，在分支之前使用 itt ls块来处理 movls r0, #1情况，因此我们仍然可以在循环之后跳到右边（而不是像我的Cortex-A9版本那样跳到单独的块）。您也可以为此使用技巧。

    subs   r1, r0, #1     ; i = n-1
    it lt
    movlt  r0, #1         ; n = 1 for  n<1
    bls   .Ltiny_input    ; return n if n was <=1

如果分支需要更大的范围，则可以使用 r0 / r0 == 1，因此分支位于IT块内（分支指令可以使用一种编码，该编码在位移上花费更多的位，而在谓词上不花费任何位）。但是在这种情况下，它的范围很短，因此在 cmp情况下，我选择不修改<​​cc>。我不知道是否有任何CPU使谓词指令成为NOP而不是运行它的效率更高或等待时间更短，但可能存在。



如果不展开，将 *=1放入循环中以避免最后一次 n=2迭代将使我们每次迭代花费一个额外的周期（4个周期而不是3个周期），因此只能通过 n=3或 sub来偿还费用。

对于较大的输入，展开可显着提高速度，从每3个周期1 mul逐渐达到每2周期1 mul渐近（sub + mul +摊销循环开销）。我看不出有什么方法可以避免像 mov或 mul这样的指令为每个 n生成单独的输入，除非通过对每个 *2 * 4的特殊情况序列进行硬编码（例如 *8 = < cc> =左移3），而您可以将答案硬编码。