如何避免循环中的条件语句

Question

在此link中，作者举了个例子

subroutine threshold(a, thresh, ic)
  real, dimension(:), intent(in) :: a
  real, intent(in) :: thresh
  integer, intent(out) :: ic
  real :: tt
  integer :: n

  ic = 0
  tt = 0.d0
  n = size(a)
  do j = 1, n
     tt = tt + a(j) * a(j)
     if (sqrt(tt) >= thresh) then
        ic = j
        return
     end if
  end do
end subroutine threshold

并且作者将这段代码评论为

An alternative approach, which would allow for many optimizations (loop unrolling, CPU pipelining, less time spent evaluating the conditional) would involve adding tt in blocks (e.g., blocks of size 128) and checking the conditional after each block. When it the condition is met, the last block can be repeated to determine the value of ic.

什么意思？循环展开？ CPU流水线？在块中添加 tt?

如何按照作者说的优化代码？

Answer 1

如果循环在适合 CPU 缓存的 chunks/blocks 中执行，您将减少缓存未命中的次数，从而减少缓存未命中的次数从内存中检索的缓存行。这提高了受内存操作限制的所有循环的性能。如果对应的块大小是BLOCKSIZE，这是通过

实现的

do j = 1, n, BLOCKSIZE
   do jj = j, j+BLOCKSIZE-1 
      tt = tt + a(jj) * a(jj)
   end do
end do

但是，这将留下未在主循环中处理的余数。为了说明这一点，考虑一个长度为 1000 的数组。前七个块 (1--896) 包含在循环中，但第八个块 (897--1024) 没有。因此，需要对余数进行另一个循环：

do j=(n/BLOCKSIZE)*BLOCKSIZE,n
   ! ...
enddo

虽然从余数循环中删除条件没有什么意义，但它可以在阻塞的主循环的外层循环中执行。由于现在内部循环中没有分支发生，因此可能需要进行积极的优化。
但是，这将确定位置的 "accuracy" 限制为块。要获得逐元素精度，您必须重复计算。

完整代码如下：

subroutine threshold_block(a, thresh, ic)
  implicit none
  real, dimension(:), intent(in) :: a
  real, intent(in) :: thresh
  integer, intent(out) :: ic
  real :: tt, tt_bak, thresh_sqr
  integer :: n, j, jj
  integer,parameter :: BLOCKSIZE = 128

  ic = 0
  tt = 0.d0
  thresh_sqr = thresh**2
  n = size(a)
  ! Perform the loop in chunks of BLOCKSIZE
  do j = 1, n, BLOCKSIZE
     tt_bak = tt
     do jj = j, j+BLOCKSIZE-1 
        tt = tt + a(jj) * a(jj)
     end do
     ! Perform the check on the block level
     if (tt >= thresh_sqr) then
        ! If the threshold is reached, repeat the last block 
        ! to determine the last position
        tt = tt_bak
        do jj = j, j+BLOCKSIZE-1 
           tt = tt + a(jj) * a(jj)
           if (tt >= thresh_sqr) then
              ic = jj
              return
           end if
        end do
     end if
  end do

  ! Remainder is treated element-wise
  do j=(n/BLOCKSIZE)*BLOCKSIZE,n
     tt = tt + a(j) * a(j)
     if (tt >= thresh_sqr) then
        ic = j
        return
     end if
  end do 
end subroutine threshold_block

请注意，现在的编译器非常善于结合其他优化来创建阻塞循环。根据我的经验，很难通过手动调整这种简单的循环来获得更好的性能。
使用编译器选项 -floop-block 在 gfortran 中启用循环阻塞。

循环展开可以手动完成，但应该留给编译器。这个想法是手动执行块中的循环，而不是如上所示的第二个循环，通过复制代码来执行操作。这是上面给出的内部循环的示例，用于因子四的循环展开：

do jj = j, j+BLOCKSIZE-1,4
   tt = tt + a(jj)   * a(jj)
   tt = tt + a(jj+1) * a(jj+1)
   tt = tt + a(jj+2) * a(jj+2)
   tt = tt + a(jj+3) * a(jj+3)
end do

此处，如果BLOCKSIZE是4的倍数，则不会出现余数。您可能可以在这里削减一些操作 ;-) 启用此功能的 gfortran 编译器选项是 -funroll-loops

据我所知，CPU Pipelining (Instruction Pipelining) 无法在 Fortran 中手动执行。这个任务由编译器来完成。

流水线设置指令管道。您将完整的数组输入该管道，在结束阶段之后，您将在每个时钟周期获得一个结果。这大大增加了吞吐量。然而，分支很难（不可能？）在管道中处理，并且阵列应该足够长以补偿设置管道、收紧和收紧阶段所需的时间。

如何避免循环中的条件语句

How to Avoid Conditionals in Loops

optimization

performance

fortran

fortran90