assembly - 优化累积和
问题描述
我需要一些帮助来了解我尝试过的优化是如何工作的。
该cumsum函数获取一个向量，并用累积和写入一个向量。
我尝试了以下方法来优化这一点：我没有在整个向量上执行一个循环，而是编写了一个在向量的每四分之一上同时运行的循环。然后调整每个部分以考虑前面部分的总和。结果略有不同，但这不是问题。
这是程序：
module cumsum_mod
implicit none
integer, parameter, private :: dp = kind(1d0)
contains
! cumsum in one straight loop
subroutine cumsum1(n, a, b)
integer :: n, i
real(dp) :: a(n), b(n)
b(1) = a(1)
do i = 2, n
b(i) = a(i) + b(i-1)
end do
end subroutine
subroutine cumsum2(n, a, b)
integer :: n, i, m
real(dp) :: a(n), b(n)
m = n/4
! Loop over the four parts
b(1) = a(1)
b(1+m) = a(1+m)
b(1+2*m) = a(1+2*m)
b(1+3*m) = a(1+3*m)
do i = 2, m
b(i) = a(i) + b(i-1)
b(i+m) = a(i+m) + b(i+m-1)
b(i+2*m) = a(i+2*m) + b(i+2*m-1)
b(i+3*m) = a(i+3*m) + b(i+3*m-1)
end do
! Adjusting
b(m+1:2*m) = b(m+1:2*m) + b(m)
b(2*m+1:3*m) = b(2*m+1:3*m) + b(2*m)
b(3*m+1:4*m) = b(3*m+1:4*m) + b(3*m)
do i = 4*m+1, n
b(i) = a(i) + b(i-1)
end do
end subroutine
subroutine cumsum3(n, a, b)
integer :: n, i, m
real(dp) :: a(n), b(n)
real(dp) :: k1, k2, k3
m = n/4
! Loop over the four parts
b(1) = a(1)
b(1+m) = a(1+m)
b(1+2*m) = a(1+2*m)
b(1+3*m) = a(1+3*m)
do i = 2, m
b(i) = a(i) + b(i-1)
b(i+m) = a(i+m) + b(i+m-1)
b(i+2*m) = a(i+2*m) + b(i+2*m-1)
b(i+3*m) = a(i+3*m) + b(i+3*m-1)
end do
! Adjusting
k1 = b(m)
k2 = b(2*m) + k1
k3 = b(3*m) + k2
do i = 1, m
b(i+m) = b(i+m) + k1
b(i+2*m) = b(i+2*m) + k2
b(i+3*m) = b(i+3*m) + k3
end do
do i = 4*m+1, n
b(i) = a(i) + b(i-1)
end do
end subroutine
end module
program cumsum_test
use cumsum_mod
implicit none
integer, parameter :: dp = kind(1d0)
real(dp), allocatable :: a(:), b(:), b1(:), b2(:), b3(:)
integer :: n, m, i
real(dp) :: t1, t2
read *, n, m
allocate (a(n), b(n), b1(n), b2(n), b3(n))
call random_number(a)
! Heating up
do i = 1, 20
call cumsum1(n, a, b)
call cumsum2(n, a, b)
call cumsum3(n, a, b)
end do
call cpu_time(t1)
do i = 1, m
call cumsum1(n, a, b)
end do
call cpu_time(t2)
print *, t2-t1
call cpu_time(t1)
do i = 1, m
call cumsum2(n, a, b)
end do
call cpu_time(t2)
print *, t2-t1
call cpu_time(t1)
do i = 1, m
call cumsum3(n, a, b)
end do
call cpu_time(t2)
print *, t2-t1
! Quick check of the difference
call cumsum1(n, a, b1)
call cumsum2(n, a, b2)
call cumsum3(n, a, b3)
print *, maxval(abs(b2-b1))
print *, maxval(abs(b3-b1))
deallocate (a, b, b1, b2, b3)
end program
“优化”方式有两种形式：要么使用四个向量语句进行调整，例如b(m+1:2*m) = b(m+1:2*m) + b(m)，要么同时在三个部分上循环。
我用 Intel Fortran 编译，使用/O3 /QxHost，处理器是 Intel Core i7 9700F（即它有 AVX2）。
我不打算发布整个程序集输出（250 kb），但这是第一个循环的主要部分：
cumsum1
L1:
inc rcx
vaddsd xmm0, xmm0, QWORD PTR [8+rdx+r10]
vmovsd QWORD PTR [8+rdx+r8], xmm0
vaddsd xmm0, xmm0, QWORD PTR [16+rdx+r10]
vmovsd QWORD PTR [16+rdx+r8], xmm0
add rdx, 16
cmp rcx, r11
jb L1
cumsum2和cumsum3
L1:
vaddsd xmm0, xmm0, QWORD PTR [8+rdi+r14*8]
vaddsd xmm1, xmm1, QWORD PTR [8+r12+r14*8]
vaddsd xmm2, xmm2, QWORD PTR [8+r11+r14*8]
vaddsd xmm3, xmm3, QWORD PTR [8+r9+r14*8]
vmovsd QWORD PTR [8+r8+r14*8], xmm0
vmovsd QWORD PTR [8+rcx+r14*8], xmm1
vmovsd QWORD PTR [8+rbp+r14*8], xmm2
vmovsd QWORD PTR [8+rsi+r14*8], xmm3
inc r14
cmp r14, r10
jb L1
因此，两者本质上都是“标量”循环：不涉及并行 SIMD 操作。然而，该调整涉及预期的并行指令。
现在，问题是：为什么cumsum2/cumsum3比 快cumsum1？也就是说，长度为 1000 的速度提高了 3 倍，长度为 10000 的速度提高了 2 倍，长度为 100000 的速度提高了 30-60%：
length=1000 loops=100000000
cumsum1 85.8593750000000
cumsum2 27.2187500000000
cumsum3 28.0937500000000
length=10000 loops=1000000
cumsum1 8.78125000000000
cumsum2 4.51562500000000
cumsum3 4.56250000000000
length=100000 loops=1000000
cumsum1 87.8281250000000
cumsum2 52.9687500000000
cumsum3 63.3281250000000
我最初的想法是，也许这些添加会并行完成，从而带来一些改进。但是，这部分代码在所有版本中都是连续的，之后还有额外的工作来调整值，并且cumsum2/cumsum3仍然比cumsum1.
我怀疑它与内存缓存有关，但我不知道如何。
欢迎任何帮助！如果有聪明的方法可以让这更快，我也很感兴趣。
编辑，回答评论
cumsum3 中的第二个循环：
L1:
vaddpd ymm6, ymm5, YMMWORD PTR [rcx+r10*8]
vmovupd YMMWORD PTR [rcx+r10*8], ymm6
vaddpd ymm6, ymm4, YMMWORD PTR [rbp+r10*8]
vmovupd YMMWORD PTR [rbp+r10*8], ymm6
vaddpd ymm6, ymm3, YMMWORD PTR [rsi+r10*8]
vmovupd YMMWORD PTR [rsi+r10*8], ymm6
vaddpd ymm6, ymm5, YMMWORD PTR [32+rcx+r10*8]
vmovupd YMMWORD PTR [32+rcx+r10*8], ymm6
vaddpd ymm6, ymm4, YMMWORD PTR [32+rbp+r10*8]
vmovupd YMMWORD PTR [32+rbp+r10*8], ymm6
vaddpd ymm6, ymm3, YMMWORD PTR [32+rsi+r10*8]
vmovupd YMMWORD PTR [32+rsi+r10*8], ymm6
vaddpd ymm6, ymm5, YMMWORD PTR [64+rcx+r10*8]
vmovupd YMMWORD PTR [64+rcx+r10*8], ymm6
vaddpd ymm6, ymm4, YMMWORD PTR [64+rbp+r10*8]
vmovupd YMMWORD PTR [64+rbp+r10*8], ymm6
vaddpd ymm6, ymm3, YMMWORD PTR [64+rsi+r10*8]
vmovupd YMMWORD PTR [64+rsi+r10*8], ymm6
vaddpd ymm6, ymm5, YMMWORD PTR [96+rcx+r10*8]
vmovupd YMMWORD PTR [96+rcx+r10*8], ymm6
vaddpd ymm6, ymm4, YMMWORD PTR [96+rbp+r10*8]
vmovupd YMMWORD PTR [96+rbp+r10*8], ymm6
vaddpd ymm6, ymm3, YMMWORD PTR [96+rsi+r10*8]
vmovupd YMMWORD PTR [96+rsi+r10*8], ymm6
add r10, 16
cmp r10, r9
jb L1
而使用 cumsum2 时，三个循环也可以实现相同的效果，每个循环都像：
L1:
vaddpd ymm2, ymm1, YMMWORD PTR [rcx+r11*8]
vaddpd ymm3, ymm1, YMMWORD PTR [32+rcx+r11*8]
vaddpd ymm4, ymm1, YMMWORD PTR [64+rcx+r11*8]
vaddpd ymm5, ymm1, YMMWORD PTR [96+rcx+r11*8]
vmovupd YMMWORD PTR [rcx+r11*8], ymm2
vmovupd YMMWORD PTR [32+rcx+r11*8], ymm3
vmovupd YMMWORD PTR [64+rcx+r11*8], ymm4
vmovupd YMMWORD PTR [96+rcx+r11*8], ymm5
add r11, 16
cmp r11, r12
jb L1
解决方案
推荐阅读
- c# - 如何使用 AND / OR 运算符有效地将布尔列表减少为单个结果
- python - 有人可以解释 .extend() 如何在这个例子中深入工作吗？
- android - 从匕首 2 获取空实例
- c++ - 链表的 Push_front 和 push_back 方法似乎删除了一个节点
- azure - 如何在逻辑应用程序中使用撰写连接器创建新的 json 对象而不改变顺序？
- python - 如何演示python GIL（我怎么知道一次只有一个线程在执行）
- serial-port - 读取串行设备将输出复制到输入
- c# - UWP 文件缩略图保存在 SQL Server 数据库中
- azure - elasticsearch 天蓝色存储库验证异常
- mysql - 如何将 APNS/FCM 的推送设备令牌存储在带有索引的 MySQL 数据库中？