gre*_*ard 5 algorithm avr multiplication
着眼于最坏情况周期计数,我为Atmel的AVR架构编码了整数乘法例程.
在一个特定的实现中,我遇到了2 + 1个最坏的情况,我为此寻求更快的实现.这些乘法乘法器具有偶数个字节,乘法器的8位部分的已知值:
* 11001011(203 10)
* 10101011(171 10)
* 10101101(173 10)
GCC(4.8.1)将这些计算为*29*7,*19*9和*(43*4 + 1) - 非常适合3地址机器,tinyAVR不是(相当:大多数寄存器对的移动速度是添加速度的两倍).对于双字节被乘数和乘积,它使用9 + 2,10 + 2和11 + 2加法(和减法)并分别移动20,22和24个周期.Radix-4 Booth将使用11 + 1次添加(在不完全可比的条件下)和23次循环.
由于超出这个问题的原因,我有16*被乘数预先计算(a5:a47个循环,包括移动); 原始和移位的被乘数都可以在以后使用(但对于MSByte).并且产品初始化为以下汇编程序代码片段的被乘数(其中我使用Booth样式的重新编码表示法:.对于NOP +,和-.owing是标签"之前的一条指令done",执行单周期修复) :
locb:; .-..+.++ ..--.-.- ++..++.- ++.+.-.- ..--.-.- 29*7
; WC?!? 11001011 s 18
add p0, p0;15 n 16 a4 15 s 16 n 15 s0 17
adc p1, p1
sub p0, a4;13 d 13 z 13 s0 15 s4 12 d 15
sbc p1, a5
add p0, p0;11 s4 11 d 12 z 13 z 10 s0 13
adc p1, p1
add p0, a0; 9 d 9 aZ 10 a4 12 s0 9 z 11
adc p1, a1
add p0, p0; 7 s4 7 d 8 a4 10 d 7 d 10
adc p1, p1
add p0, a0; 5 s0 5 d 6 d 8 az 5 aZ 8
adc p1, a1
rjmp owing; 3 owi 3 s0 4 d 6 owi 3 d 6
; aZ 4 aZ 4
(注释从左到右,循环计数("到达后退done"),以及使用"标签行"中相同列中的重新编码的其他代码序列,使用n否定的简写,d为double(部分) )产物,a0/ a4/ s0/ s4用于添加或减去被乘数移位0或4比特的左边,z用于存储在ZL的产品:ZH,和aZ/ sZ用于使用).
使用宏(另一个最坏的情况下和上述速记):
loab:; .-.-.-.- +.++.-.- +.+.+.++ .-.-+.++ +.+.++.-
; WC 10101011
negP ;15 set4 ;16 add4 ;15 d 16 a4 16
sub4 ;12 doubleP ;15 pp2Z ;13 s4 14 d 14
pp2Z ;10 subA ;13 doubleP ;12 z 12 a0 12
doubleP ; 9 pp2Z ;11 doubleP ;10 d 11 d 10
doubleP ; 7 doubleP ;10 addZ ; 8 d 9 a4 8
addZ ; 5 doubleP ; 8 doubleP ; 6 aZ 7 d 6
owing ; 3 addZ ; 6 addA ; 4 a0 5 s0 4
; add4 ; 4
loac:; +.+.++.. ++-.++.. .-.-.-..
load: ; .-.-..-- .-.-.-.+ .--.++.+ 0.9 1.8 0.8 (avg)
; WC 10101101
negP ;15 -1 negP ;16 a4 a0 a0 17
sub4 ;12 -16-1 sub4 ;13 d s4 a0
pp2Z ;10 -16-1 doubleP ;11 a0 Z s4
sub4 ; 9 -32-1 doubleP ; 9 d d d
doubleP ; 7 -64-2 sub4 ; 7 a4 aZ d
addZ ; 5 -80-3 addA ; 5 d d a0
owing ; 3 owing ; 3 a0 a0 s4
(我不会在任何一次调用中找到多个结果/作为任何单个调用的结果 - 但是如果你有办法在少于23个周期内获得两个或者在少于26个周期中获得全部三个,请让我知道.为了证实我对CSE的了解,(重新)使用vlad_tepesch引入的符号[rl] sh16和add16:
movw C, x ; 1
lsh16(C) ; 3 C=2x
movw A, C ; 4
swap Al ; 5
swap Ah ; 6
cbr Ah, 15 ; 7
add Ah, Al ; 8
cbr Al, 15 ; 9
sub Ah, Al ;10 A=32x
movw X, A ;11
add16(X, C) ;13 X=34x
movw B, X ;14
lsh16(X) ;16
lsh16(X) ;18 X=136X
add16(B, X) ;20 B=170X
add16(B, x) ;22 B=171X
add16(A, B) ;24 A=203X
add16(C, B) ;26 C=173X
- 注意到第一个结果的22个周期是相同的旧20个周期,加上两个寄存器对移动.除此之外的动作序列是在loab上面的标签之后的第三列/替代的行动.)
虽然20个周期(15-2(rjmp)+7(*16)看起来不那么糟糕,但这些是最坏的情况.一个没有mul指令的AVR CPU,
如何通过203,171和173中的每一个快速乘以实数？
(前一个移动一个案例,done或者owing让其他两个更快,将缩短关键路径/改善最坏情况周期数.)
我对 AVR-asm 不是很熟悉，但我很了解 AVR，所以我尝试一下
如果您在同一位置需要这些产品，您可以使用常见的中间结果并尝试添加 2 的倍数。
(a) 203: +128 +64 +8 +2 +1 = +128 +32 +8 +2 +1 +32
(b) 171: +128 +32 +8 +2 +1
(c) 173: +128 +32 +8 +4 +1 = +128 +32 +8 +2 +1 +2
关键是16位右移和16位加法必须高效。我不知道我是否遗漏了什么，但是：
rsh16 (X):
LSR Xh
ROR Xl
和
add16 (Y,X)
ADD Yl, Xl
ADDC Yh, Xh
都是2个周期。
一对寄存器保存当前的 x*2^n 值 (Xh, Xl)。其他 3 对（Ah、Ab、Bh、Bl、Ch、Cl）保存结果。
1. Xh <- x; Xl <- 0 (X = 256*x)
2. rsh16(X) (X = 128*x)
3. B = X (B = 128*x)
4. rsh16(X); rsh16(X) (X = 32*x)
5. add16(B, X) (B = 128*x + 32*x)
6. A = X (A = 32*X)
7. rsh16(X); rsh16(X) (X = 8*x)
8. add16(B, X) (B = 128*x + 32*x+ 8*x)
9. rsh16(X); rsh16(X) (X = 2*x)
10. add16(B, X) (B = 128*x + 32*x + 8*x + 2*x)
11. C = X (C = 2*X)
12. CLR Xh (clear Xh so we only add the carry below)
add Bl, x
addc Bh, Xh (B = 128*x + 32*x + 8*x + 2*x + x)
13. add16(A, B) (A = 32*X + B)
14. add16(C, B) (C = 2*X + B)
如果我是正确的，那么所有三个乘法总共需要 32 个周期，并且需要 9 个寄存器（1 个输入、6 个输出、2 个临时寄存器）